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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.