Stochastic Truth Tables

Recall the example of a weighted truth table describing a single card from a normal deck of cards being placed on a table where $A$ means the card is an Ace and $R$ means the card is a red card:

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

Typically, we are interested in the proportion or probability of ways that a formula can be true. For a formula $X$, let $Pr(X)$ be the proportion of ways that $X$ is true in a weighted truth table. This is determined as follows:

$$Pr(X) = \frac{\#(X)}{\#(\top)}$$

Then, we have that:

• $Pr(A)=\frac{\#(A)}{\#(\top)} = \frac{4}{52}=\frac{1}{13}$
• $Pr(R)=\frac{\#(R)}{\#(\top)} = \frac{26}{52}=\frac{1}{2}$
• $Pr(A\wedge R)=\frac{\#(A\wedge R)}{\#(\top)} = \frac{2}{52}=\frac{1}{26}$
• $Pr(A\rightarrow R)=\frac{\#(A\rightarrow R)}{\#(\top)} = \frac{50}{52}=\frac{25}{26}$

Rather than starting with a weighted truth table, in many cases it is more convenient to describe the probability of each row of a truth table directly. For example, the probabilities of each row in the above weighted truth table are:

	$A$	$R$
$1/26$	$\mathsf{T}$	$\mathsf{T}$
$1/26$	$\mathsf{T}$	$\mathsf{F}$
$6/13$	$\mathsf{F}$	$\mathsf{T}$
$6/13$	$\mathsf{F}$	$\mathsf{F}$

A stochastic truth table is a weighted truth table where the weights represent the proportion of ways that a row can be realized (given some process of assigning truth values to the atomic propositions).

Stochastic Truth Table

A stochastic truth table is a truth table where each row is assigned a number between 0 and 1, and the sum of these numbers is 1. That is, if the stochastic truth table has $n$ rows, where each row $i$ is assigned the number $p_i$, then for each $i$, $0\le p_i\le 1$ and $p_1+p_2+\cdots + p_n=1$. When row $i$ is assigned the number $p_i$, then we say that the probability of row $i$ is $p_i$.

Stochastic truth tables are used to assign probabilities to formulas.

Probability of a formula

Given a stochastic truth table with a column for a formula $X$, the probability of $X$, denoted $Pr(X)$, is the sum of the probabilities of the rows where the formula is true.

For example, consider the following stochastic truth table for $P\vee Q$, $P\wedge Q$, and $P\rightarrow Q$:

	$P$	$Q$	$(P\vee Q)$	$(P\wedge Q)$	$(P\rightarrow Q)$
$0.4$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$0.2$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$0.25$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$0.15$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$

The probabilities of the formulas is determined as follows:

1. Since $P\vee Q$ is true in rows 1, 2 and 3, we have $Pr(P\vee Q) = 0.4+ 0.2 + 0.25 = 0.85$.

2. Since $P\wedge Q$ is true in row 1, we have $Pr(P\wedge Q) = 0.4$.

3. Since $P\rightarrow Q$ is true in rows 1, 3 and 4, we have $Pr(P\rightarrow Q) = 0.4 + 0.25 + 0.15 = 0.8$.

Tutorials

Lecture

Slides

Lecture

Slides

Practice Questions

1. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\vee Q)$	$\neg P$	$\neg Q$
   0.25	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
   0.25	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0.25	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
   0.25	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$

   $Pr(P\vee Q)$$\ =\$$0.75$

   $Pr(\neg P$)$\ =\$$0.50$

   $Pr(\neg Q$)$\ =\$$0.50$

2. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\vee Q)$	$\neg P$	$\neg Q$	$(P\wedge Q)$
   0	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
   0.5	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
   0.5	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
   0	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$

   $Pr(P\vee Q)$$\ =\$$1.00$

   $Pr(\neg P$)$\ =\$$0.50$

   $Pr(\neg Q$)$\ =\$$0.50$

   $Pr(P\wedge Q)$$\ =\$$0.00$

3. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$R$	$(P\vee Q)$	$\neg P$	$\neg Q$	$R$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
   0.05	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
   0.05	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
   0.2	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.2	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$

   $Pr(P\vee Q)$$\ =\$$0.60$

   $Pr(\neg P$)$\ =\$$0.50$

   $Pr(\neg Q$)$\ =\$$0.50$

   $Pr(R$)$\ =\$$0.50$

4. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$R$	$((P\wedge Q)\rightarrow R)$	$(\neg R\rightarrow \neg (P\vee Q))$
   0.1	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
   0.3	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.05	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
   0.1	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.15	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$

   $Pr((P\wedge Q)\rightarrow R)$$\ =\$$0.80$

   $Pr(\neg R\rightarrow \neg (P\vee Q))$$\ =\$$0.70$

5. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$R$	$(P\vee R)$	$(P\vee Q)$	$(Q\vee R)$
   0.1	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.3	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.05	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.05	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
   0.1	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0.15	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$

   $Pr(P\vee R)$$\ =\$$0.80$

   $Pr(P\vee Q)$$\ =\$$0.75$

   $Pr(Q\vee R)$$\ =\$$0.80$

6. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\rightarrow Q)$	$(Q\rightarrow P)$	$((P\rightarrow Q)\vee (Q\rightarrow P))$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.3	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
   0.2	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0.3	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

   $Pr(P\rightarrow Q)$$\ =\$$0.70$

   $Pr(Q\rightarrow P)$$\ =\$$0.80$

   $Pr((P\rightarrow Q)\vee (Q\rightarrow P))$$\ =\$$1.00$

7. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\wedge \neg Q)$	$(\neg P\wedge Q)$	$(P\wedge Q)$	$(P\rightarrow Q)$
   0.4	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
   0.1	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
   0.1	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0.4	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$

   $Pr(P\wedge \neg Q)$$\ =\$$0.10$

   $Pr(\neg P\wedge Q)$$\ =\$$0.10$

   $Pr(P\wedge Q)$$\ =\$$0.40$

   $Pr(P\rightarrow Q)$$\ =\$$0.90$

8. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\rightarrow Q)$	$(Q\rightarrow P)$	$P$	$Q$
   0.2	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
   0.3	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
   0.1	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
   0.4	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$

   $Pr(P\rightarrow Q)$$\ =\$$0.70$

   $Pr(Q\rightarrow P)$$\ =\$$0.90$

   $Pr(P$)$\ =\$$0.50$

   $Pr(Q$)$\ =\$$0.30$

9. Fill in the remaining truth values and find the probabilities of the formulas.

   	$P$	$Q$	$(P\rightarrow Q)$	$(\neg P\rightarrow Q)$	$(Q\rightarrow P)$	$(\neg P\wedge Q)$
   1	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
   0	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
   0	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
   0	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$

   $Pr(P\rightarrow Q)$$\ =\$$1.00$

   $Pr(\neg P\rightarrow Q)$$\ =\$$1.00$

   $Pr(Q\rightarrow P)$$\ =\$$1.00$

   $Pr(\neg P\wedge Q)$$\ =\$$0.00$

10. Fill in the remaining truth values and find the probabilities of the formulas.

    	$P$	$Q$	$R$	$(P\vee Q)$	$(P\rightarrow Q)$	$(Q\rightarrow R)$	$(P\rightarrow R)$
    0	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
    0	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
    0.25	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
    0.25	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
    0.25	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
    0.25	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
    0	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
    0	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

    $Pr(P\vee Q)$$\ =\$$1.00$

    $Pr(P\rightarrow Q)$$\ =\$$0.50$

    $Pr(Q\rightarrow R)$$\ =\$$0.75$

    $Pr(P\rightarrow R)$$\ =\$$0.75$