Weighted Truth Tables

Recall that a truth table describes all possible ways of assigning truth values to some atomic formulas. For example, if there are two atomic propositions $A$ and $R$, then there are 4 ways of assigning truth values to these atomic propositions:

	$A$	$R$
1.	$\mathsf{T}$	$\mathsf{T}$
2.	$\mathsf{T}$	$\mathsf{F}$
3.	$\mathsf{F}$	$\mathsf{T}$
4.	$\mathsf{F}$	$\mathsf{F}$

Each of the 4 rows describes an assignment of truth values to the two atomic propositions. For instance, $A$ is assigned $\mathsf{T}$ (true) and $R$ is assigned $\mathsf{F}$ (false) in row 2.

In this section, we extend a truth table so that it not only represents the truth value of a formula, but also how many ways a formula can be assigned a truth value. For example, suppose that there is a normal deck of cards (consisting of 52 cards, 26 are red and 26 are black) and you are dealt one of the cards.

Let $A$ be true when the card you are dealt is an Ace and $R$ be true when the card you are dealt is a red card. In this scenario, we have the following:

• for row 1 in the above truth table, there are 2 ways that $A$ can be true and $R$ can be true: You could be dealt any one of the red Ace cards (e.g., the Ace of hearts or the Ace of diamond);
• for row 2 in the above truth table, there are 2 ways that $A$ can be true and $R$ can be false: You could be dealt any one of the black Ace cards (e.g., the Ace of clubs or the Ace of spades);
• for row 3 in the above truth table, there are 24 ways that $A$ can be false and $R$ can be true: You could be dealt any one of the red cards that are not the Ace card (e.g., the 10 of hearts, the Jack of diamond, etc.); and
• for row 4 in the above truth table, there are 24 ways that $A$ can be false and $R$ can be false: You could be dealt any one of the black cards that are not the Ace card (e.g., the 2 of clubs, the King of spades, etc.).

To represent this additional information, we extend a truth table with a column labeling each row with the number of ways that the atomic formulas can be assigned the truth values in that row.

Weighted Truth Table

A weighted truth table is a truth table where each row is assigned a nonnegative integer (an integer greater than or equal to 0).

For instance, the above situation is represented by the following weighted truth table:

	$A$	$R$
$2$	$\mathsf{T}$	$\mathsf{T}$
$2$	$\mathsf{T}$	$\mathsf{F}$
$24$	$\mathsf{F}$	$\mathsf{T}$
$24$	$\mathsf{F}$	$\mathsf{F}$

In a weighted truth table, we can count the number of ways that a formula is true.

Weight of a Formula in a Weighted Truth Table

Suppose that $X$ is a formula of Propositional Logic and $\mathcal{T}$ is a weighted truth table. The number of ways that $X$ is true in $\mathcal{T}$, denoted $\#_\mathcal{T}(X)$, is the sum of the numbers assigned to the rows that make $X$ true. We write $\#(X)$ when the weighted truth table is clear from context.

For example, in the above weighted truth table we have the following:

1. $\#(A) = 2 + 2 = 4$
   Explanation: $A$ is true in rows 1 and 2.
2. $\#(R) = 2 + 24 = 26$
   Explanation: $R$ is true in rows 1 and 3.
3. $\#(A\vee R) = 2 + 2 + 24 = 28$
   Explanation: $A\vee R$ is true in rows 1, 2, and 3.
4. $\#(A\wedge \neg R) = 2$
   Explanation: $A\wedge\neg R$ is true in row 2.
5. $\#(A\rightarrow R) = 2 + 24 + 24 = 50$
   Explanation: $A\rightarrow R$ is true in rows 1, 3, and 4.
6. $\#(A\vee \neg A) = 2 + 2 + 24 + 24 = 52$
   Explanation: $A\vee \neg A$ is true in all of the rows.
7. $\#(A\wedge \neg A) = 0$
   Explanation: $A\wedge \neg A$ is not true an any of the rows.

Properties of Weighted Truth Tables

In this section, we present some key properties concerning the weights assigned to formulas of Propositional Logic in a weighted truth table. We first need some notation:

Top/Bottom

Let $\top$ (called "top" or "true") be an atomic proposition that is always true in every row a truth table. Then, define $\bot$ (called "bottom" or "falsum") as $\neg\top$, so $\bot$ is false in every row of a (weighted) truth table.

The first observation is immediate from the definition of truth for negation:

Observation

For any propositional formula $X$, for any weighted truth table for $X$,

$$\#(\neg X) = \#(\top) - \#(X).$$

Using this observation, we can show that for any propositional formula $X$, $\#(\neg\neg X) =\#(X)$:

$$\#(\neg \neg X) = \#(\top) - \#(\neg X) = \#(\top) - (\#(\top) - \#(X)) = \#(X)$$

More generally, since tautologically equivalent formulas are true on the same rows in any truth table, they must be assigned the same weight in any weighted truth table.

Observation

For any propositional formulas $X$ and $Y$, for any weighted truth table for $X$ and $Y$, if $X\approx Y$ (i.e., $X$ and $Y$ are tautologically equivalent), then $\#(X)=\#(Y)$

The next observation is the underlying reason why reasoning with probabilities can be more complicated than reasoning in Propositional Logic. Consider the following two weighted truth tables for the atomic propositions $P$ and $Q$:

Weighted Truth Table 1 ($\mathcal{T}_1$)

	$P$	$Q$
$5$	$\mathsf{T}$	$\mathsf{T}$
$30$	$\mathsf{T}$	$\mathsf{F}$
$10$	$\mathsf{F}$	$\mathsf{T}$
$55$	$\mathsf{F}$	$\mathsf{F}$

Weighted Truth Table 2 ($\mathcal{T}_2$)

	$P$	$Q$
$10$	$\mathsf{T}$	$\mathsf{T}$
$25$	$\mathsf{T}$	$\mathsf{F}$
$5$	$\mathsf{F}$	$\mathsf{T}$
$55$	$\mathsf{F}$	$\mathsf{F}$

Note that $P$ and $Q$ are assigned the same weight in both weighted truth tables:

$$\#_{\mathcal{T}_1}(P) = \#_{\mathcal{T}_2}(P) = 35\qquad \text{ and }\qquad \#_{\mathcal{T}_1}(Q) = \#_{\mathcal{T}_2}(Q) = 15$$

However, the disjuction $P\vee Q$ has different weights in the different weighted truth tables:

$$\#_{\mathcal{T}_1}(P\vee Q) = 45 \ne 40 = \#_{\mathcal{T}_2}(P\vee Q)$$

The reason that the weight of the disjunction is different in the two weighted truth tables despite the fact that the weights of the disjuncts are the same in both weighted truth tables is that the weighted truth tables give different weights to the row in which both $P$ and $Q$ are true (i.e., $\#_{\mathcal{T}_1}(P\wedge Q) = 5\ne 10 =\#_{\mathcal{T}_2}(P\wedge Q)$). This means that, in general, it is not true that the weight of a disjunction is the sum of the weights of the disjuncts. We do have the following:

Observation

For any propositional formulas $X$ and $Y$, for any weighted truth table for $X$ and $Y$,

$$\#(X\vee Y) = \#(X) + \#(Y) - \#(X\wedge Y).$$

Practice Questions

I. Given the weighted truth table below, find the weights of the following formulas.

	$A$	$B$	$C$
$5$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$15$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$5$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$5$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$15$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$10$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$5$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$40$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$

1. $\#(A\wedge B)$

2. $\#((A\wedge C) \rightarrow B)$

3. $\#((A \leftrightarrow B)$

4. $\#(A\wedge (A\rightarrow B))$

5. $\#(\neg (A\vee C) \wedge B)$

II. Answer the following questions.

1. True or False: For any formula $X$ of Propositional Logic, if $X$ is a contradiction, then $\#(X) = 0$.

   True False

   ​

   If $X$ is a contradiction, then $X$ is not true on any row of a truth table, so in any weighted truth table, $\#(X)$ must be $0$.

2. True or False: For any formulas $X$ and $Y$ of Propositional Logic, if $X$ and $Y$ are contraries, then $\#(X\vee Y)= \#(X) + \#(Y)$.

   True False

   ​

   If $X$ and $Y$ are contraries, then $X\wedge Y$ is not true on any row of a truth table, so $\#(X\wedge Y) = 0$. Then,

   $$\#(X\vee Y)=\#(X)+\#(Y) -\#(X\wedge Y) = \#(X)+\#(Y) - 0 = \#(X)+\#(Y)$$

3. True or False: If $\#(X) = 0$, then $X$ is a contradiction.

   True False

   ​

   To illustrate, consider the following weighted truth table:

   	$P$	$Q$
   $0$	$\mathsf{T}$	$\mathsf{T}$
   $10$	$\mathsf{T}$	$\mathsf{F}$
   $0$	$\mathsf{F}$	$\mathsf{T}$
   $90$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(Q)=0$; however, $Q$ is not a contradiction.

4. True or False: If $\#(X) = \#(\top)$, then $X$ is a tautology.

   True False

   ​

   To illustrate, consider the following weighted truth table:

   	$P$	$Q$
   $0$	$\mathsf{T}$	$\mathsf{T}$
   $10$	$\mathsf{T}$	$\mathsf{F}$
   $0$	$\mathsf{F}$	$\mathsf{T}$
   $90$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(\neg Q)=100 = \#(\top)$; however, $\neg Q$ is not a contradiction.

5. True or False: There is a weighted truth table in which $\#(P\vee Q) = \#(P) + \#(Q)$.

   True False

   ​

   This is true. Consider the following weighted truth table:

   	$P$	$Q$
   $0$	$\mathsf{T}$	$\mathsf{T}$
   $10$	$\mathsf{T}$	$\mathsf{F}$
   $20$	$\mathsf{F}$	$\mathsf{T}$
   $70$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(P\vee Q)=30$, $\#(P) = 10$, and $\#(Q)=20$. So, $\#(P\vee Q) = \#(P) + \#(Q)$. More generally, we have that if $\#(X\wedge Y)=0$, then $\#(X\vee Y) = \#(X) + \#(Y)$: Since $\#(X\vee Y) = \#(X) + \#(Y) - \#(X\wedge Y)$ and $\#(X\wedge Y)=0$, we have that

   $$\#(X\vee Y) = \#(X) + \#(Y) - \#(X\wedge Y) = \#(X) + \#(Y) - 0 = \#(X) + \#(Y)$$

6. True or False: There is a a weighted truth table in which $\#(P\vee Q) = \#(\neg P\wedge \neg Q)$.

   True False

   ​

   This is true. Consider the following weighted truth table:

   	$P$	$Q$
   $0$	$\mathsf{T}$	$\mathsf{T}$
   $10$	$\mathsf{T}$	$\mathsf{F}$
   $20$	$\mathsf{F}$	$\mathsf{T}$
   $30$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(P\vee Q)=30 = \#(\neg P\wedge \neg Q)$. Note that since $(\neg P\wedge\neg Q)\approx \neg (P\vee Q)$, we needed to define a weighted truth table in which 1/2 of the total weight is distributed on the rows where $X\vee Y$ is true and the other 1/2 is distributed on the rows in which $X\vee Y$ is false.

7. True or False: There is a weighted truth table in which $\#(P) < \#(P\wedge Q)$.

   True False

   ​

   This is false. A weighted truth table for $P$ and $Q$ has the following form:

   	$P$	$Q$
   $w_1$	$\mathsf{T}$	$\mathsf{T}$
   $w_2$	$\mathsf{T}$	$\mathsf{F}$
   $w_3$	$\mathsf{F}$	$\mathsf{T}$
   $w_4$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(P)= w_1 + w_2$ and $\#(P\wedge Q)=w_1$. If $\#(P) < \#(P\wedge Q)$, we have that $w_1+w_2 < w_1$ and so $w_2 < 0$. This contradicts the assumption that the weights are nonnegative integers.

8. True or False: There is a weighted truth table in which $\#(P\rightarrow Q) < \#(Q)$.

   True False

   ​

   This is false. A weighted truth table for $P$ and $Q$ has the following form:

   	$P$	$Q$
   $w_1$	$\mathsf{T}$	$\mathsf{T}$
   $w_2$	$\mathsf{T}$	$\mathsf{F}$
   $w_3$	$\mathsf{F}$	$\mathsf{T}$
   $w_4$	$\mathsf{F}$	$\mathsf{F}$

   We have that $\#(Q)= w_1 + w_3$ and $\#(P\rightarrow Q)=w_1 + w_3 + w_4$. If $$\#(P\rightarrow Q) < \#(Q)$, we have that $w_1 + w_3 + w_4< w_1 + w_3$, and so $w_4 < 0$. This contradicts the assumption that the weights are nonnegative integers.

9. Suppose that $\#(P\wedge Q) = 10$ and $\#(P\wedge \neg Q) = 30$. What is $\#(P)$?

   $\#(P) = 20$

   $\#(P) = 3$

   $\#(P) = 40$

   Not enough information to answer the question.

   ​

   Since $P\approx (P\wedge Q) \vee (P\wedge \neg Q)$ and $P\wedge Q$ and $P\wedge\neg Q$ are not true on the same rows, we have $\#(P)=\#((P\wedge Q)\vee (P\wedge\neg Q))$. Then,

   $$\#(P)=\#((P\wedge Q)\vee (P\wedge\neg Q)) = \#(P\wedge Q) + \#(P\wedge\neg Q) = 10 + 30 = 40$$

10. Suppose that $\#(\top)=100$, $\#(\neg P\vee \neg Q) = 30$ and $\#(\neg (P\rightarrow Q)) = 10$. What is $\#(P)$?

    $\#(P) = 40$

    $\#(P) = 80$

    $\#(P) = 60$

    Not enough information to answer the question.

    ​

    Since $\#(\top)=100$, we have $30 = \#(\neg P\vee \neg Q) = \#(\neg(P\wedge Q)) = \#(\top) - \#(P\wedge Q) = 100 - \#(P\wedge Q)$, so $\#(P\wedge Q) = 70$. Since $\neg (P\rightarrow Q)\approx (P\wedge \neg Q)$, we have that $10=\#(\neg(P\rightarrow Q)) = \#(P\wedge\neg Q)$. Then since $P\approx (P\wedge Q) \vee (P\wedge \neg Q)$ and that $P\wedge Q$ and $P\wedge\neg Q$ are contraries, we have that:

    $$\#(P)=\#((P\wedge Q)\vee (P\wedge\neg Q)) = \#(P\wedge Q) + \#(P\wedge\neg Q) = 70 + 10 = 80$$

11. Suppose that $X\models Y$. What can you conclude about the relationship between $\#(X)$ and $\#(Y)$?

    $\#(X) = \#(Y)$

    $\#(X) \ge \#(Y)$

    $\#(X) \le \#(Y)$

    Not enough information to answer the question.

    ​

    If $X\models Y$, then $X\rightarrow Y$ is a tautology, so $\#(X\rightarrow Y) = \#(\top)$.

    Then, since $(X\rightarrow Y) \approx (\neg X \vee Y)$, we have that

    $$\#(\top) = \#(X\rightarrow Y) = \#(\neg X\vee Y) = \#(\neg X) + \#(Y) - \#(\neg X\wedge Y)$$

    $$= \#(\top) - \#(X) + \#(Y) - \#(\neg X\wedge Y)$$

    Rearranging the terms in the above equation, we have that:

    $$\#(X) + \#(\neg X\wedge Y) = \#(Y)$$

    Now, recall the following fact about numbers: if there is a $b\ge 0$ such that $a + b = c$, then $a\le b$. Then, since $\#(\neg X\wedge Y) \ge 0$, we have that $\#(X)\le \#(Y)$.