# Maximum number of truths in an optimized truth table.

I have a math-related question:

I have a set of predicates that need to be evaluated. These predicates can have two kinds of operators; AND/OR. When such an expression is constructed my code builds an expression tree, evaluates it and builds a truth table out of it. Entries in this truth table are bitmasks that define the positively passing conditions. For example if we have this logical expression:

(a && b) || (c && d) || !a (|| is OR, && is AND), then predicates (a, b, c and d) are indexed starting from 0. This expression will produce the following truth table:

--11
11--
0---


Then, as an optimization step, these entries are compressed into something like:

1111 : [0011, 1100] <-- (1)
0000 : [1000]


(1): This indicates what predicates has to have their result ready in an expression to qualify for being evaluated against this entry. Let's leave aside the actual benefits from this form of optimization.

Now during this optimization step, entries are combined if their values are not conflicting; 1 and - (or empty) are combinable (and result in two availability entries). 1 and 1 are combinable, 0 and - are combinable. 1 and 0 on the same index are not combinable and they have to land in two separate entries.

Also, if two predicates are not combinable and they have the AND operator they cancel each other and don't end up in the truth table. (Example: (a && !a) || c => the left part of this expression cancels itself and is ignored).

To calculate the number of possible entries in a truth table without this optimization is pretty simple, in the worst-case scenario we will end up having $3^n$ entries, where n is the number of predicates. I'm a little bit confused how to calculate the number of possible truth table entries (let's leave the availability entries aside for now) in the worst-case scenario when they can be combined and are ignored if they cancel each other.

I would be more than thankful for any pointers. Thanks!

-
I think I understand the question, but I'm not sure. Two things that are confusing me: I don't see how what I take the question in the body to be has anything to do with the title. And I don't understand why the worst case for the unoptimized table is $2^n$. If all $n$-letter strings of 0, 1 and - are allowed, it would be $3^n$, and if, as the example might suggest, 0 and 1 can't occur in the same string, it would still be $2\cdot2^n$ for all strings of 0and - plus all strings of 1 and -. – joriki Oct 1 '12 at 6:29
I think it would be good if you would a) describe exactly the possible forms of the unoptimized truth table (not just the strings in the worst case but all admissible combinations, since the worst case for the unoptimized table probably won't be the worst case for the optimized table), and the admissible operations in optimizing the table. – joriki Oct 1 '12 at 6:32
You can use $\TeX$ here by enclosing formulas in dollar signs; single dollar signs for inline formulas and double formulas for displayed equations. – joriki Oct 1 '12 at 6:44
Note that I don't get notified if you just change the question without leaving a comment, so if you want me to revisit the question you'll have to start responding to the comments. The apparent discrepancy between the title and the body and the lack of math formatting remain. Two more questions: Is it possible for none of the predicates to be ANDed? In that case it would seem clear that the worst case is the one where we have all $3^n$ strings and none of them can be cancelled? And can we only combine two strings at a time? If not, what are the rules for combining more than two? – joriki Oct 1 '12 at 8:02
I'm sorry. Yes I have updated the question after you've corrected my mistake with $3^n$ rather than $2^n$. Please excuse my slow responses. I'm going to update the question with all the missing nuances that I missed. – Karim Agha Oct 1 '12 at 8:41