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 : 
(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;
- (or empty) are combinable (and result in two availability entries).
1 are combinable,
- are combinable.
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!