Skip to main content

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 AA and RR, then there are 4 ways of assigning truth values to these atomic propositions:

AARR
1. T\mathsf{T}T\mathsf{T}
2. T\mathsf{T}F\mathsf{F}
3. F\mathsf{F}T\mathsf{T}
4. F\mathsf{F}F\mathsf{F}

Each of the 4 rows describes an assignment of truth values to the two atomic propositions. For instance, AA is assigned T\mathsf{T} (true) and RR is assigned F\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.

cards

Let AA be true when the card you are dealt is an Ace and RR 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 AA can be true and RR 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 AA can be true and RR 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 AA can be false and RR 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 AA can be false and RR 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:

AARR
22 T\mathsf{T}T\mathsf{T}
22 T\mathsf{T}F\mathsf{F}
2424 F\mathsf{F}T\mathsf{T}
2424 F\mathsf{F}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 XX is a formula of Propositional Logic and T\mathcal{T} is a weighted truth table. The number of ways that XX is true in T\mathcal{T}, denoted #T(X)\#_\mathcal{T}(X), is the sum of the numbers assigned to the rows that make XX true. We write #(X)\#(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\#(A) = 2 + 2 = 4
    Explanation: AA is true in rows 1 and 2.
  2. #(R)=2+24=26\#(R) = 2 + 24 = 26
    Explanation: RR is true in rows 1 and 3.
  3. #(A∨R)=2+2+24=28\#(A\vee R) = 2 + 2 + 24 = 28
    Explanation: A∨RA\vee R is true in rows 1, 2, and 3.
  4. #(A∧¬R)=2\#(A\wedge \neg R) = 2
    Explanation: A∧¬RA\wedge\neg R is true in row 2.
  5. #(A→R)=2+24+24=50\#(A\rightarrow R) = 2 + 24 + 24 = 50
    Explanation: A→RA\rightarrow R is true in rows 1, 3, and 4.
  6. #(A∨¬A)=2+2+24+24=52\#(A\vee \neg A) = 2 + 2 + 24 + 24 = 52
    Explanation: A∨¬AA\vee \neg A is true in all of the rows.
  7. #(A∧¬A)=0\#(A\wedge \neg A) = 0
    Explanation: A∧¬AA\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 XX, for any weighted truth table for XX,

#(¬X)=#(⊤)−#(X).\#(\neg X) = \#(\top) - \#(X).

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

#(¬¬X)=#(⊤)−#(¬X)=#(⊤)−(#(⊤)−#(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 XX and YY, for any weighted truth table for XX and YY, if X≈YX\approx Y (i.e., XX and YY are tautologically equivalent), then #(X)=#(Y)\#(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 PP and QQ:

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

PPQQ
55 T\mathsf{T}T\mathsf{T}
3030 T\mathsf{T}F\mathsf{F}
1010 F\mathsf{F}T\mathsf{T}
5555 F\mathsf{F}F\mathsf{F}

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

PPQQ
1010 T\mathsf{T}T\mathsf{T}
2525 T\mathsf{T}F\mathsf{F}
55 F\mathsf{F}T\mathsf{T}
5555 F\mathsf{F}F\mathsf{F}

Note that PP and QQ are assigned the same weight in both weighted truth tables:

#T1(P)=#T2(P)=35 and #T1(Q)=#T2(Q)=15\#_{\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∨QP\vee Q has different weights in the different weighted truth tables:

#T1(P∨Q)=45≠40=#T2(P∨Q)\#_{\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 PP and QQ are true (i.e., #T1(P∧Q)=5≠10=#T2(P∧Q)\#_{\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 XX and YY, for any weighted truth table for XX and YY,

#(X∨Y)=#(X)+#(Y)−#(X∧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.

AABBCC
55 T\mathsf{T}T\mathsf{T}T\mathsf{T}
1515 T\mathsf{T}T\mathsf{T}F\mathsf{F}
55 T\mathsf{T}F\mathsf{F}T\mathsf{T}
55 T\mathsf{T}F\mathsf{F}F\mathsf{F}
1515 F\mathsf{F}T\mathsf{T}T\mathsf{T}
1010 F\mathsf{F}T\mathsf{T}F\mathsf{F}
55 F\mathsf{F}F\mathsf{F}T\mathsf{T}
4040 F\mathsf{F}F\mathsf{F}F\mathsf{F}
  1. #(A∧B)\#(A\wedge B)
  1. #((A∧C)→B)\#((A\wedge C) \rightarrow B)
  1. #((A↔B)\#((A \leftrightarrow B)
  1. #(A∧(A→B))\#(A\wedge (A\rightarrow B))
  1. #(¬(A∨C)∧B)\#(\neg (A\vee C) \wedge B)

II. Answer the following questions.

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

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

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

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

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

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

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

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

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

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

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