Optimized Boolean Form

About

Summary: Any Boolean expressions may be converted into positive-form, which has only union and intersection operators. Let E be a positive-form expression with n literals. Assume that the truth-values of the literals are read one at a time. The numbers s(n) of steps (operations) and b(n) of working memory bits (footprint) needed to evaluate E depend on E and on the evaluation technique. A recursive evaluation performs s(n)=n-l steps but requires b(n)=log(n)+l bits. Evaluating the disjunctive form of E uses only b(n)=2 bits, but may lead to an exponential growth of s(n). We propose a new Optimized Blist Form (OBF) that requires only s(n)=n steps and b(n)=⌠log2j⌡ bits, where j=⌠log2(n+2)+log2(4/3)⌡. We provide a simple and linear cost algorithm for converting positive form expressions to their OBF. A few example applications include (1) Direct CSG rendering, where a candidate surfel stored at a pixel is classified against an arbitrarily complex Boolean expression using a footprint of only 6 stencil bits; (2) the new Logic Matrix (LM), which evaluates any positive form logical expression of n literals in a single cycle and uses a matrix of at most nxj wire/line connections; and (3) the new Logic Pipe (LP), which uses n gates that are connected by a pipe of ⌠log2j⌡ lines and when receiving a staggered stream of input vectors produces a value of a logical expression at each cycle.