Counting Rows of a Truth Table that Satisfy a Condition

Question

How can I mathematically count the number of rows in a truth table of n-inputs that will satisfy a certain boolean condition?

For example, say I have a 4-input truth table that will in turn have 16 rows. The inputs are $A, B, C, D$, and I wish to mathematically count how many rows satisfy (ie. evaluate to TRUE) the following condition:

$A + BD + BC + CD$

I understand that exactly $8$ rows would satisfy the first condition $A$ and exactly $4$ rows would satisfy the condition $BD$, however I would have to subtract the common rows between the two conditions $ABD$ and this would get messy rather quickly when I would try to evaluate the entire condition.

Answer 1

Algorithmically, this is the #SAT problem (also known as Sharp-SAT). The general problem statement is: given a propositional logic formula $\phi(x_1,\dots,x_n)$ on $n$ boolean variables $x_1,\dots,x_n$, count the number of satisfying assignments. In other words, count the size of the set $\{(x_1,\dots,x_n) : \phi(x_1,\dots,x_n)\}$.

The #SAT problem is known to be NP-hard, which (likely) means there is no general algorithm for this problem that is efficient.

If $n$ is small, you can enumerate all $2^n$ assignments and check which ones are satisfying assignments, but this becomes inefficient very quickly as $n$ becomes large. If $\phi$ has some special structure, you may be able to count the number of satisfying assignments more quickly than enumerating them, but this requires cleverness, and it is believed there is no general technique (no technique that works for all $\phi$) to do this efficiently.

Nonetheless, there has been significant work on heuristics and techniques for solving the #SAT problem. Those techniques might prove effective enough in practice for many conditions that you run into in practice (because in practice the condition often has some structure that can be exploited to speed up the counting process). There's a rich and detailed literature on this subject in the computer science literature, too deep to cover in this answer, but if you search for research on #SAT, you should find some entry points into the literature.

This question would probably be better asked on the Computer Science or Theoretical Computer Science sites -- you'll get better answers there. For example, see the following questions, which address aspects of this:

• #SAT Solver download

• Is there a sometimes-efficient algorithm to compute the number of satisfying assignments for a boolean formula?

• Starting SAT solver papers

• What is the counting complexity of random 2-SAT?

If you just want to get the answer rapidly for a particular formula, your best bet is to find an existing #SAT solver and use it. It'll implement sophisticated techniques, but you don't need to know how those techniques work to use the solver and (with any luck) get an answer.

Answer 2

Do a truth-table.

For can there be any method which is [always] more efficient than doing a truth-table? If you could, e.g., find a way of computing the number of lines on which an $n$-variable sentence is true which is always faster than exponential-in-$n$, then I guess you'd win a Clay prize ...

---

[To explain: a polynomial-fast way of counting true valuations would be a polynomial-fast way of determining what's a tautology, and that is widely thought to be impossible to achieve for the general case. Proving it is possible after all would involve settling the question whether P = NP, thus settling one of the Clay Millennium Problems.]

Answer 3

Let $L(A)$ be the set of lines in a truth table where expression $A$ is true. Now we can discuss this in terms of the sizes of sets. Note that we have the following two properties:

1. $|L(AB)| = |L(A) \cap L(B)|$

2. $|L(A + B) = |L(A) \cup L(B)| = |L(A)| + |L(B)| - |L(AB)|$

Property 2 can be applied inductively (i.e. recursively) to disjunctions of three or more boolean expressions. Let's see how this works with your example that is disjunction of four boolean expressions:

$$|L(A+BD+BC+CD)|$$ $$= |L(A)| + |L(BD+BC+CD)| - |L(ABD+ABC+ACD)|$$ $$ = |L(A)| + |L(BD)| + |L(BC+CD)| - |L(BCD + BCD)| - (|L(ABD)| + |L(ABC+ACD)| - |L(ABCD+ABCD)|)$$ $$ = |L(A)| + |L(BD)| + |L(BC)| + |L(CD)| - |L(BCD)| - |L(BCD)| - (|L(ABD)| + |L(ABC)| + |L(ACD)| - |L(ABCD)|)$$

You might be able to further simplify this final formula. The main point is that it is in terms of boolean expressions which only contain conjunctions. Those values of $L$ can be determined using property 1.