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

share|improve this question

3 Answers 3

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\;.$$

share|improve this answer
    
Thanks. The assumption that they appear only once is true in my cases. Will try these out. –  Matsemann Dec 14 '12 at 23:37
    
@Matsemann: You’re welcome. –  Brian M. Scott Dec 14 '12 at 23:38

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.

share|improve this answer
    
Bummer, hehe. Doing 2^100 with pen&paper will take some time. –  Matsemann Dec 14 '12 at 23:36
    
Unfortunately, even a computer cannot try all $2^{100}$ assignments :-( –  Yury Dec 14 '12 at 23:41
    
Yeah, so lucky for me Brian's answer covers my needs. –  Matsemann Dec 14 '12 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. –  André Nicolas Dec 15 '12 at 1:48
    
@AndréNicolas: That's not the case for constraint satisfaction problems. There are no algorithms that solve NP-hard problems. –  Yury Dec 15 '12 at 4:33

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.

share|improve this answer
    
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? –  Matsemann Dec 14 '12 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. –  Brian M. Scott Dec 14 '12 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. –  ashley Dec 14 '12 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. :) –  Matsemann Dec 14 '12 at 23:55

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.