Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Are you looking for a general algorithm or for an approach for this specific example? –  Code-Guru Jan 16 '13 at 0:06
1  
I'm looking for a general algorithm, but an approach could help me find the general case myself - I guess I just need some guidance. :) –  Khaled Jan 16 '13 at 0:16
    
AFAIK, the combinatoric method of "subtracting common rows" is the only other way than simply writing out the truth table. –  Code-Guru Jan 16 '13 at 0:21
    
I've asked about this on se.CS. If I learn anything useful, I will post it here. –  MJD Jan 16 '13 at 0:22
    
@MJD Thank you very much, do keep me posted. –  Khaled Jan 16 '13 at 0:25
show 2 more comments

3 Answers 3

up vote 2 down vote accepted

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:

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.

share|improve this answer
add comment

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.]

share|improve this answer
    
Thank you for your answer, however I specified I wanted the answer mathematically (ie. no drawing of a truth table). I don't understand why it is impossible - did you read my last paragraph? –  Khaled Jan 15 '13 at 20:47
    
What's unmathematical about a truth-table? –  Peter Smith Jan 15 '13 at 20:48
    
Say I have a $64$-input function, I don't want to generate a TT of $2^64$ rows just to count what could probably be counted using a summation. –  Khaled Jan 15 '13 at 20:52
1  
Of course you don't want to: but you can't in general determine this sort of thing in less than exponential time. UNless P = NP, and if you can show that you win a million dollars. –  Peter Smith Jan 15 '13 at 20:55
1  
While this is a useful answer, it is not as useful as it ought to be. Counting the number of satisfying assignments for a boolean formula is #P-hard, and therefore NP-hard. There are well-known resolution methods for SAT that can solve many instances rapidly and have exponential behavior only in difficult cases. There may be algorithms for this counting problem that are similarly useful on typical instances. Perhaps not, since this sort of counting problem can be very difficult, but if there is a truly useful answer to this question, it will lie in this direction. –  MJD Jan 16 '13 at 0:05
show 2 more comments

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.

share|improve this answer
    
Why do you say that $|L(A)\cap L(B)| = |L(A)|\cdot|L(B)|$? That seems patently false. Moreover, the final formula will in general have an exponential number of terms, so evaluating it won't be any more efficient than enumerating the rows of the truth table. –  MJD Jan 16 '13 at 1:19
    
@MJD When I wrote that, I think I was considering $A$ and $B$ as variables, not expressions. I believe it is true in that specific case, but I need to think about it. –  Code-Guru Jan 16 '13 at 1:21
    
@MJD My answer isn't addressing the efficiency concerns. Rather I wanted to illustrate a solution which doesn't use a truth table as the OP asked. –  Code-Guru Jan 16 '13 at 1:22
    
Your Property 1 is incorrect. If $A$ and $B$ are distinct variables from a collection of $n$ variables, then your $|L(A)\cap L(B)|$ will be $2^{n-2}$, since you can assign any truth values you want to the other $n-2$ variables. In addition, your example is missing a few cases and a few bars and parentheses are misplaced. –  Rick Decker Jan 16 '13 at 1:24
    
$|L(A)\cap L(B)| = |L(A)|\cdot|L(B)|$ is false even for the extremely simple case of $A\land B$. –  MJD Jan 16 '13 at 1:30
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.