# How can I calculate the number of models in which a logical sentence is true?

How can I calculate the number of models in which a logical sentence is true? Or maybe more precisely, the number of models that satisfy the logical sentence.

In a knowledge base, I have 100 variables, labeled $A1,A2,...A100$ which are either $true$ or $false$. This gives $2^{100}$ possible combinations, or $models$. Say the number of models is $Q$.
Then I have a couple of logical sentences.

$A1 \vee A73$
This sentence will be true in $\frac{3}{4}Q$ models as both will be true in $\frac{1}{2}$, and removing the overlapping parts.

$A7 \vee (A19 \wedge A33)$
Is true in $\frac{5}{8}Q$ models as the parenthesis is true in a quarter of the models, A7 in half of them, and removing the overlap.

$(A11 \Rightarrow A22) \vee (A55 \Rightarrow A66)$ I convert to
$\neg A11 \vee A22 \vee \neg A55 \vee A66$ which I say is true in $\frac{15}{16}Q$ models, as the first one contributes with a half, the second a quarter and so on because of the overlap.

So far, so good. However, I'm mostly calculating this by thinking it through and removing the overlaps I find. It's error prone, and I often get the wrong results until I find a method that agrees with the table in my book.

And I'm unable to answer more advanced stuff, as I can't reason of how much "overlap" there is. For instance
$(\neg A11 \vee A22) \wedge (\neg A55 \vee A66)$

So any formulas or "ways of thinking" that can make this clearer? Thanks.

This isn't homework, but a part of AI-class I'm having a bit trouble understanding.

It is not possible to efficiently compute the number of assignments to variables $A_i$ that satisfy a given Boolean formula. This problem is #P-hard and unless #P=P there is no polynomial-time algorithm for this problem. In fact, even checking whether there is at least one assignment satisfying a given 3-SAT formula is NP-hard.

Of course, you can just go over all possible assignments and count those that satisfy your formula. This requires exponential time.

• Bummer, hehe. Doing 2^100 with pen&paper will take some time. Commented Dec 14, 2012 at 23:36
• Unfortunately, even a computer cannot try all $2^{100}$ assignments :-(
– Yury
Commented Dec 14, 2012 at 23:41
• Yeah, so lucky for me Brian's answer covers my needs. Commented Dec 14, 2012 at 23:53
• Don't worry oo much about theoretical intractability. The Simplex Method for linear programming has bad worst case behaviour. Yet methods in that family are still best for very large problems. So far, theoretically "better" (polynomial time) algorithms have not been faster in practice. Commented Dec 15, 2012 at 1:48
• @AndréNicolas: That's not the case for constraint satisfaction problems. There are no algorithms that solve NP-hard problems.
– Yury
Commented Dec 15, 2012 at 4:33

Assign the value $\frac12$ to each $A$ and $\neg A$. Suppose that you’ve assigned values $v_1,\dots,v_n$, respectively, to terms $t_1,\dots,t_n$, and that no $A$ appears more than once in these terms; then the value of the disjunction $$t_1\lor t_2\lor\ldots\lor t_n$$ is $$1-\prod_{k=1}^n(1-v_k)\;,$$ and the value of the conjunction $$t_1\land t_2\land\ldots\land t_n$$ is $$\prod_{k=1}^nv_k\;.$$

These values are the fraction of models satisfying the Boolean expression in question. For example, for $$(\neg A11 \vee A22) \wedge (\neg A55 \vee A66)$$ you get

$$\left(1-\left(\frac12\right)^2\right)\left(1-\left(\frac12\right)^2\right)=\left(\frac34\right)^2=\frac9{16}\;.$$

Similarly, the value of $A7 \vee (A19 \wedge A33)$ is $$1-\left(1-\frac12\right)\left(1-\frac12\cdot\frac12\right)=1-\frac12\cdot\frac34=\frac58\;.$$

• Thanks. The assumption that they appear only once is true in my cases. Will try these out. Commented Dec 14, 2012 at 23:37
• @Matsemann: You’re welcome. Commented Dec 14, 2012 at 23:38
• @BrianM.Scott, I see this is years ago but I'll try anyway: Do you know if there's a similar solution but when A do appear more than once? Commented Mar 4, 2019 at 8:11

A parse tree is the the structure for expression evaluation:

Put a parantheses pair to enclose every term in the expression-- so that there are as many valid parantheses pairs in your expression as possible. Then for a parse tree, each expression is a child of the expression that is enclosed by the parantheses pair exactly one level up.

Eg.: In (((a .AND. b) .AND. (c .OR. d)) => q)

(a .AND. b) and (c .OR. d) are the two children of the node ((a .AND. b) .AND. (c .OR. d)) and so forth. Then start with the leaves and keep evaluating until you reach the root. Or, for more efficiency, use a postfix traversal algorithm that starts at the root and evaluates the children of each node before the node itself.

EDIT: parse tree and the postfix evaluation is the structure used by compilers in expression evaluation.

• Thanks for your answer. I'm unsure about what you mean by "then evaluate until you reach the root". Could you be a bit more specific about how I evaluate? Commented Dec 14, 2012 at 23:34
• @Matsemann: The evaluation that ashley has in mind is the $n=2$ version of the one that I suggested in my answer. Commented Dec 14, 2012 at 23:36
• Take the postfix traversal. It evaluates the tree for expression more efficiently, looks much better in the code and is an old structure-- very well covered in literature. I've put the first, "start w.the leaves and working it up to the root" rather as a comment for explaining the structure. Commented Dec 14, 2012 at 23:46
• I know about trees&stuff, it was the "evaluate" part I was unsure about. But after reading @BrianM.Scott 's answer I now see what you meant. :) Commented Dec 14, 2012 at 23:55