Skip to main content

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 AA means the card is an Ace and RR means the card is a red card:

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}

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

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

Then, we have that:

  • Pr(A)=#(A)#(⊤)=452=113Pr(A)=\frac{\#(A)}{\#(\top)} = \frac{4}{52}=\frac{1}{13}
  • Pr(R)=#(R)#(⊤)=2652=12Pr(R)=\frac{\#(R)}{\#(\top)} = \frac{26}{52}=\frac{1}{2}
  • Pr(A∧R)=#(A∧R)#(⊤)=252=126Pr(A\wedge R)=\frac{\#(A\wedge R)}{\#(\top)} = \frac{2}{52}=\frac{1}{26}
  • Pr(A→R)=#(A→R)#(⊤)=5052=2526Pr(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:

AARR
1/261/26 T\mathsf{T}T\mathsf{T}
1/261/26 T\mathsf{T}F\mathsf{F}
6/136/13 F\mathsf{F}T\mathsf{T}
6/136/13 F\mathsf{F}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 nn rows, where each row ii is assigned the number pip_i, then for each ii, 0≤pi≤10\le p_i\le 1 and p1+p2+⋯+pn=1p_1+p_2+\cdots + p_n=1. When row ii is assigned the number pip_i, then we say that the probability of row ii is pip_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 XX, the probability of XX, denoted Pr(X)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∨QP\vee Q, P∧QP\wedge Q, and P→QP\rightarrow Q:

PPQQ(P∨Q)(P\vee Q)(P∧Q)(P\wedge Q)(P→Q)(P\rightarrow Q)
0.40.4 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
0.20.2 T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}F\mathsf{F}
0.250.25 F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
0.150.15 F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}

The probabilities of the formulas is determined as follows:

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

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

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

Tutorials#



Practice Questions#

  1. Fill in the remaining truth values and find the probabilities of the formulas.
    PPQQ(P∨Q)(P\vee Q)¬P\neg P¬Q\neg Q
    0.25 T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
    0.25 T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0.25 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    0.25 F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    Pr(P∨Q)Pr(P\vee Q) = \ =\ 0.750.75
    Pr(¬PPr(\neg P) = \ =\ 0.500.50
    Pr(¬QPr(\neg Q) = \ =\ 0.500.50
  1. Fill in the remaining truth values and find the probabilities of the formulas.

    PPQQ(P∨Q)(P\vee Q)¬P\neg P¬Q\neg Q(P∧Q)(P\wedge Q)
    0 T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}
    0.5 T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    0.5 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
    0 F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    Pr(P∨Q)Pr(P\vee Q) = \ =\ 1.001.00
    Pr(¬PPr(\neg P) = \ =\ 0.500.50
    Pr(¬QPr(\neg Q) = \ =\ 0.500.50
    Pr(P∧Q)Pr(P\wedge Q) = \ =\ 0.000.00

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

    PPQQRR(P∨Q)(P\vee Q)¬P\neg P¬Q\neg QRR
    0.2 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}
    0.2 T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}F\mathsf{F}F\mathsf{F}
    0.05 T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    0.05 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    0.05 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0.05 F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
    0.2 F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.2 F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    Pr(P∨Q)Pr(P\vee Q) = \ =\ 0.600.60
    Pr(¬PPr(\neg P) = \ =\ 0.500.50
    Pr(¬QPr(\neg Q) = \ =\ 0.500.50
    Pr(RPr(R) = \ =\ 0.500.50

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

    PPQQRR((P∧Q)→R)((P\wedge Q)\rightarrow R)(¬R→¬(P∨Q))(\neg R\rightarrow \neg (P\vee Q))
    0.1 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.2 T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}F\mathsf{F}
    0.3 T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.05 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    0.05 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.05 F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    0.1 F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.15 F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    Pr((P∧Q)→R)Pr((P\wedge Q)\rightarrow R) = \ =\ 0.800.80
    Pr(¬R→¬(P∨Q))Pr(\neg R\rightarrow \neg (P\vee Q)) = \ =\ 0.700.70

  1. Fill in the remaining truth values and find the probabilities of the formulas.
    PPQQRR(P∨R)(P\vee R)(P∨Q)(P\vee Q)(Q∨R)(Q\vee R)
    0.1 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.2 T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.3 T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.05 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    0.05 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.05 F\mathsf{F}T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    0.1 F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0.15 F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}
    Pr(P∨R)Pr(P\vee R) = \ =\ 0.800.80
    Pr(P∨Q)Pr(P\vee Q) = \ =\ 0.750.75
    Pr(Q∨R)Pr(Q\vee R) = \ =\ 0.800.80
  1. Fill in the remaining truth values and find the probabilities of the formulas.
    PPQQ(P→Q)(P\rightarrow Q)(Q→P)(Q\rightarrow P)((P→Q)∨(Q→P))((P\rightarrow Q)\vee (Q\rightarrow P))
    0.2 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.3 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    0.2 F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0.3 F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    Pr(P→Q)Pr(P\rightarrow Q) = \ =\ 0.700.70
    Pr(Q→P)Pr(Q\rightarrow P) = \ =\ 0.800.80
    Pr((P→Q)∨(Q→P))Pr((P\rightarrow Q)\vee (Q\rightarrow P)) = \ =\ 1.001.00
  1. Fill in the remaining truth values and find the probabilities of the formulas.

    PPQQ(P∧¬Q)(P\wedge \neg Q)(¬P∧Q)(\neg P\wedge Q)(P∧Q)(P\wedge Q)(P→Q)(P\rightarrow Q)
    0.4 T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    0.1 T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}F\mathsf{F}F\mathsf{F}
    0.1 F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0.4 F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}
    Pr(P∧¬Q)Pr(P\wedge \neg Q) = \ =\ 0.100.10
    Pr(¬P∧Q)Pr(\neg P\wedge Q) = \ =\ 0.100.10
    Pr(P∧Q)Pr(P\wedge Q) = \ =\ 0.400.40
    Pr(P→Q)Pr(P\rightarrow Q) = \ =\ 0.900.90

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

    PPQQ(P→Q)(P\rightarrow Q)(Q→P)(Q\rightarrow P)PPQQ
    0.2 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.3 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    0.1 F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}
    0.4 F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
    Pr(P→Q)Pr(P\rightarrow Q) = \ =\ 0.700.70
    Pr(Q→P)Pr(Q\rightarrow P) = \ =\ 0.900.90
    Pr(PPr(P) = \ =\ 0.500.50
    Pr(QPr(Q) = \ =\ 0.300.30

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

    PPQQ(P→Q)(P\rightarrow Q)(¬P→Q)(\neg P\rightarrow Q)(Q→P)(Q\rightarrow P)(¬P∧Q)(\neg P\wedge Q)
    1 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    0 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}
    0 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0 F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    Pr(P→Q)Pr(P\rightarrow Q) = \ =\ 1.001.00
    Pr(¬P→Q)Pr(\neg P\rightarrow Q) = \ =\ 1.001.00
    Pr(Q→P)Pr(Q\rightarrow P) = \ =\ 1.001.00
    Pr(¬P∧Q)Pr(\neg P\wedge Q) = \ =\ 0.000.00

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

    PPQQRR(P∨Q)(P\vee Q)(P→Q)(P\rightarrow Q)(Q→R)(Q\rightarrow R)(P→R)(P\rightarrow R)
    0 T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0 T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}F\mathsf{F}
    0.25 T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}
    0.25 T\mathsf{T}F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}F\mathsf{F}
    0.25 F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0.25 F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}F\mathsf{F}T\mathsf{T}
    0 F\mathsf{F}F\mathsf{F}T\mathsf{T}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    0 F\mathsf{F}F\mathsf{F}F\mathsf{F}F\mathsf{F}T\mathsf{T}T\mathsf{T}T\mathsf{T}
    Pr(P∨Q)Pr(P\vee Q) = \ =\ 1.001.00
    Pr(P→Q)Pr(P\rightarrow Q) = \ =\ 0.500.50
    Pr(Q→R)Pr(Q\rightarrow R) = \ =\ 0.750.75
    Pr(P→R)Pr(P\rightarrow R) = \ =\ 0.750.75