Truth Tables and Equivalence

Having introduced propositions and logical operators, let’s talk about atomic propositions, compound propositions, and truth tables.

An atomic proposition is one that cannot be decomposed any further into simpler propositions. The word “atomic” here simply means “indivisible.” Here are some examples of atomic propositions:

$10 \div 2 = 5$.
5 students in Professor Jones’ Spring 2009 Introductory Physics class received an A.
$x > y + 2$.

A compound proposition is built up from simpler propositions using the logical operators. Here are some examples:

$(x < y) \vee ((x = y) \vee (x > y))$.
$(w = v) \Leftrightarrow (v = w)$.
$(x = \mathsf{red}) \Rightarrow ((y = \mathsf{red}) \wedge (z = \mathsf{red}))$.

As with arithmetic expressions, we use parentheses to indicate grouping; e.g., in the last compound proposition above the placement of the parentheses indicates that the $\wedge$ (AND) operator applies to the propositions $(y = \mathsf{red})$ and $(z = \mathsf{red})$.

Every proposition is either atomic or compound.

Every proposition has a (possibly unknown) truth value, either $\mathsf{T}$ (true) or $\mathsf{F}$ (false). You can then think of the logical operators as operations on truth values, much as the arithmetic operators $+$, $\times$, etc., operate on numbers.

A truth table lists the truth value of a compound proposition for all possible combinations of truth values of the propositions from which it was constructed. Here is the truth table for NOT ($\neg$):

$A$	$\neg A$
$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$

Here is the truth table for AND ($\wedge$):

$A$	$B$	$A\wedge B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

Here is the truth table for OR ($\vee$):

$A$	$B$	$A\vee B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

Here is the truth table for IF-THEN ($\Rightarrow$):

$A$	$B$	$A\Rightarrow B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

Here is the truth table for IF-AND-ONLY-IF ($\Leftrightarrow$):

$A$	$B$	$A\Leftrightarrow B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

In general, to work out out the truth table for a more complicated compound proposition we build it up one operation at a time, including a column for each intermediate proposition. For example, here we build up the truth table for $(\neg A) \vee B$:

$A$	$B$	$\neg A$	$(\neg A) \vee B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$

Let’s omit the column for $\neg A$ and add a column for $A \Rightarrow B$ for comparison:

$A$	$B$	$(\neg A) \vee B$	$A \Rightarrow B$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

We see that the two columns are identical: regardless of what combination of truth values $A$ and $B$ have, the two propositions $(\neg A)\vee B$ and $A \Rightarrow B$ end up with the same truth value. We say that they are equivalent. They are really just two different ways of saying the same thing.

Furthermore, this is so for any two propositions $A$ and $B$, even if one or both of them are compound propositions. In particular,

$(\neg (x=1)) \vee (x=2)$ is equivalent to $(x=1) \Rightarrow (x=2)$;
$(\neg ((x = y) \vee (x = z)) \vee (x \leq y + z )$ is equivalent to $((x = y) \vee (x = z)) \Rightarrow (x \leq y + z )$;
$\neg(C \wedge D) \vee E$ is equivalent to $(C \wedge D) \Rightarrow E$ for any three propositions $C$, $D$, and $E$.

Now let’s build up the truth table for $\neg((\neg A) \wedge (\neg B))$:

$A$	$B$	$\neg A$	$\neg B$	$(\neg A) \wedge (\neg B)$	$\neg( (\neg A) \wedge (\neg B))$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$

If you compare the final column of this truth table to the truth table for $A\vee B$, they are the same. Thus, $\neg((\neg A) \wedge (\neg B))$ is equivalent to $A\vee B$ for any two propositions $A$ and $B$.

Finally, here we build up the truth table for $A \Rightarrow (B \Rightarrow C)$

$A$	$B$	$C$	$B\Rightarrow C$	$A \Rightarrow (B \Rightarrow C) $
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

and for $(A \wedge B) \Rightarrow C$:

$A$	$B$	$C$	$A \wedge B$	$(A \wedge B) \Rightarrow C$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{F}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{F}$	$\mathsf{T}$	$\mathsf{F}$
$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$	$\mathsf{T}$

The final columns are the same, giving us another equivalence: $A \Rightarrow (B \Rightarrow C)$ is equivalent to $(A \wedge B) \Rightarrow C$.

Propositions and Logical Operators

Logic is an essential tool for rational thought. In this and the next several posts I present the basics of propositional logic, which is the logic of certain kinds of elementary statements. Propositional logic has two main elements:

A language for combining simple statements into more complex statements.
Rules that tell us when it is logically valid to draw some conclusion from a collection of premises, based only on the logical form of the premises and conclusion.

This post discusses (1), the language of propositional logic.

A proposition is a statement (or claim, or assertion) that is objectively either true or false, although we may not know which. Here are some examples of propositions:

$2 + 3 = 5$.
$5 – 7 = 10$.
John F. Kennedy died on December 3, 1916.
The Earth’s diameter is less than 10,000 miles.
The Greek philosopher Socrates awoke between 6:22 a.m. and 6:41 a.m. local time in Athens on the morning of May 27, 412 B. C. (Gregorian calendar).

Propositions (2) and (3) are known to be false; propositions (1) and (4) are known to be true; and nobody knows whether proposition (5) is true.

The following, however, are not propositions:

Johnny is a big kid.
You should treat other people the way you would want them to treat you.
Braveheart is the best movie of all time.
Mary gets angry too quickly.

(1) is simply too vague — is 5 feet 8 inches enough to qualify as “big”? Is 170 pounds large enough? (2) and (4) are value statements, and (3) is an aesthetic judgment; all of these are subjective.

We can combine propositions to make more complex propositions, using logical operators. In describing these operators we will use the variables $A$ and $B$ to stand for any two propositions (they may even be the same proposition). Here are descriptions of the most important logical operators:

Not: $\neg A$ is the proposition stating that $A$ is false. For example, $\neg (\mbox{John’s birthday is in December})$ is the same as the proposition “John’s birthday is not in December.” If $A$ is true, then $\neg A$ is false; if $A$ is false, then $\neg A$ is true.

And: $A \wedge B$ is the proposition stating that both $A$ and $B$ are true. That is, the proposition $A \wedge B$ is true if both $A$ and $B$ are true, and is false if $A$ is false or $B$ is false. Some examples:

$(\mbox{dogs are mammals}) \wedge (3 – 6 = 4)$ is the proposition stating that both “dogs are mammals” and “$3 – 6 = 4$” are true. This particular proposition is false: although “dogs are mammals” is true, “$3 – 6 = 4$” is false, and that’s enough to make the combined proposition false.
$(\mbox{triangles have three sides}) \wedge (\mbox{frogs are amphibians})$ is a proposition that is true, since “triangles have three sides” is true, and “frogs are amphibians” is also true.

Or: $A \vee B$ is the proposition stating that $A$ is true or $B$ is true (possibly both). That is, the proposition $A \vee B$ is true if at least one of the propositions $A$, $B$ are true; it is false only if both of them are false. Some examples:

$(3 < 10) \vee (3 > 0)$ is true.
$(9 < 10) \vee (9 > 20)$ is true, since $9 < 10$ is true.
$(\mbox{the moon is made of green cheese}) \vee (\mbox{dogs are mammals})$ is true, since “dogs are mammals” is true.
$(\mbox{Einstein had 3 eyes}) \vee (\mbox{the Earth is 3 miles across})$ is false, since Einstein assuredly did not have three eyes, and the Earth is much more than 3 miles across.

If and only if: $A \Leftrightarrow B$ is the proposition stating that either both $A$ and $B$ are true, or both $A$ and $B$ are false. Put another way, $A \Leftrightarrow B$ says that $A$ is true if, and only if, $B$ is true. Some examples:

$(x=y) \Leftrightarrow (y=x)$ is true for any two numbers $x$ and $y$.
$(\mbox{dogs are mammals} \Leftrightarrow (\mbox{cheese is a food})$ is true, since both “dogs are mammals” and “cheese is a food” are true.
$(\mbox{triangles have four sides}) \Leftrightarrow (\mbox{2+2=5})$ is true, since both “triangles have four sides” and $2+2=5$ are false.
$(\mbox{there are 12 inches to a foot}) \Leftrightarrow (\mbox{3 is a letter of the alphabet})$ is false, since “there are 12 inches to a foot” is true, but “3 is a letter of the alphabet” is false.

If … then: $A \Rightarrow B$ is the proposition stating that if $A$ is true, then so is $B$. That is, $A \Rightarrow B$ is false only if $A$ is true but $B$ is not; it is, by definition, true in all other cases. Some examples:

$(3 > 5) \Rightarrow (3 > 4)$ is true, since $3 > 5$ is false.
$(5 > 3) \Rightarrow (5 > 2)$ is true, since $5 > 2$ is true.
$(\mbox{dogs are mammals}) \Rightarrow (\mbox{cats breathe motor oil})$ is false, since “dogs are mammals” is true but “cats breathe motor oil” is false.
$(\mbox{cats breathe motor oil}) \Rightarrow (\mbox{dogs are mammals})$ is true, since “cats breathe motor oil” is false (also because “dogs are mammals” is true).

Here are some examples of English sentences re-expressed using logical operators:

“Fred is unemployed”: \[\neg (\mbox{Fred is employed}).\]
“Susan ate a carrot and a hot dog”: \[(\mbox{Susan ate a carrot}) \wedge (\mbox{Susan ate a hot dog}).\]
“Todd lives in Orem or Provo”: \[(\mbox{Todd lives in Orem}) \vee (\mbox{Todd lives in Provo}).\]
“If Mars has life then it must have water”: \[(\mbox{Mars has life}) \Rightarrow (\mbox{Mars has water}). \]
“My computer turns on only if I jiggle the plug”: \[ (\mbox{My computer turns on}) \Rightarrow (\mbox{I jiggle the plug}).\] There’s a subtlety here: the English statement does not say that jiggling the plug is sufficient for the computer to turn on, but only that it is necessary. That is we cannot have “my computer turns on” being true without “I jiggle the plug” also being true.
“I will accept the job if you give me a signing bonus; otherwise I won’t”: \[ (\mbox{I will accept the job}) \Leftrightarrow (\mbox{you give me a signing bonus}). \]

To recap, here’s a quick summary of the logical operators:

$\neg A$ means “not $A$,” or, equivalently, “$A$ is false.”
$A \wedge B$ means “both $A$ and $B$ are true.”
$A \vee B$ means “either $A$ or $B$ (or both) is true.”
$A \Leftrightarrow B$ means “$A$ is true if, and only if, $B$ is true.”
$A \Rightarrow B$ means “if $A$ is true then so is $B$.”

Closed Worlds and Bayesian Inference

Bayesian inference has at times been criticized as relying on the closed world assumption: that one of the hypotheses we are considering is true. That is, Bayes’ rule

$$
P(H_i \mid D, X) = \frac{P(H_i \mid X) P(D \mid H_i, X)}{
\sum_j P(H_j \mid X) P(D \mid H_j, X)}
$$

(where $X$ is our background knowledge, $D$ is the data, and the $H_1,\ldots,H_n$ are our hypotheses) is valid only when the background knowledge $X$ establishes that exactly one of the hypotheses $H_i$ must be true. The use of Bayes’ rule would then seem to presuppose that one has actually identified and considered all possible hypotheses — a practically impossible task in most (all?) real-world situations.

To illustrate the problem, let’s take a look at a real-world example of considerable practical interest to some people. In December 2002 an article appeared on the Wizard of Odds website claiming that the Casino Bar online blackjack game was not dealing fairly — that it rigged the card draws in certain circumstances to favor the dealer. Here are the specifics:

The article states, “Previously somebody approached me with what he claimed was a section of computer code he said was taken from the Casino Bar blackjack game. My interpretation of that code is that if the player has a total of 16-21 and the dealer must take a third card, if that hit card will cause the dealer to bust, then it will be rejected and the dealer will get a second chance card. This second chance card is final, whether or not it will bust the dealer. […] This is what would be known in a real casino as dealing seconds.”
Under hypothesis $H_0$ (fair dealing), here are the probabilities of the dealer going bust on the third card depending on the two-card total:
- total = 12: probability = 0.3077
- total = 13: probability = 0.3846
- total = 14: probability = 0.4615
- total = 15: probability = 0.5385
- total = 16: probability = 0.6154
Under hypothesis $H_1$ (dealing seconds), here are the probabilities of the dealer going bust under the same conditions:
- total = 12: probability = 0.0947
- total = 13: probability = 0.1479
- total = 14: probability = 0.2130
- total = 15: probability = 0.2899
- total = 16: probability = 0.3787
The author ran an experiment to test the blackjack game, and out of 332 hands got these results:

dealer two-card total # times occurred # times dealer bust on next card

12 84 11

13 13 61

14 18 67

15 21 61

16 26 59

dealer two-card total	# times occurred	# times dealer bust on next card
12	84	11
13	13	61
14	18	67
15	21	61
16	26	59

Now for our analysis. $H_0$ and $H_1$ are the two hypotheses we are especially interested in, but there are a large number of different ways in which the dealing could deviate from a fair deal. Perhaps the first, second, or both cards are not drawn in the required manner (draws from a uniform distribution without replacement). Perhaps the casino deals seconds only every other hand; perhaps the casino occasionally deals seconds for the player (!); and so on. Accounting for the myriad possibilities in our analysis is a daunting task.

What is a good Bayesian to do? We sidestep the problem by considering ratios of posterior probabilities instead of the posterior probabilities themselves. That is, instead of computing $P(H_0 \mid D, X)$ and $P(H_1 \mid D, X)$ we will compute

$$\frac{P(H_1 \mid D, X)}{P(H_0 \mid D, X)}.$$

Plugging Bayes’ rule into the above fraction we see that the denominators cancel and we end up with

$$\frac{P(H_1 \mid D, X)}{P(H_0 \mid D, X)} =
\frac{P(H_1 \mid X)}{P(H_0 \mid X)} \cdot
\frac{P(D \mid H_1, X)}{P(D \mid H_0, X)}.$$

In words: to get the ratio of the posterior probabilities of two hypotheses, multiply the ratio of their prior probabilities by the ratio of their likelihoods. And — this is the important point — this formula holds regardless of how many other hypotheses $H_2, H_3, \ldots$ there may be to consider.

Now let’s apply this formula to the Casino Bar question. First let’s look at the prior probabilities. The prior probability must be split between $H_0$, $H_1$, and myriad other possibilities; however, our prior information $X$ includes that the article’s author was shown what was purported to be source code for the online casino’s blackjack game, implementing the scheme postulated by $H_1$. This prior information elevates $H_1$ to a position of prominence that it would otherwise lack. Given this prior information, it is hard to argue that the prior odds ratio $P(H_1)/P(H_0)$ should be less than 1/100; likewise, it would be hard to argue that the author should have had such a high degree of confidence in his source as to justify a prior odds ratio of greater than 100/1.

The likelihood for $H_0$ is

$$\begin{array}{rcl} P(D \mid H_0, X) & = & {0.3077}^{11} \times (1 – 0.3077)^{73} \times \\ & & {0.3846}^{13} \times (1 – 0.3846)^{48} \times \\ & & {0.4615}^{18} \times (1 – 0.4615)^{49} \times \\ & & {0.5385}^{21} \times (1 – 0.5385)^{40} \times \\ & & {0.6154}^{26} \times (1 – 0.6154)^{33} \\ & = & {5.296} \times {10}^{-91} \end{array}.$$

The likelihood for $H_1$ is

$$\begin{array}{rcl} P(D \mid H_0, X) & = & {0.0947}^{11} \times (1 – 0.0947)^{73} \times \\ & & {0.1479}^{13} \times (1 – 0.1479)^{48} \times \\ & & {0.2130}^{18} \times (1 – 0.2130)^{49} \times \\ & & {0.2899}^{21} \times (1 – 0.2899)^{40} \times \\ & & {0.3787}^{26} \times (1 – 0.3787)^{33} \\ & = & {1.766} \times {10}^{-81} \end{array} .$$

The likelihood ratio is then

$$\frac{P(D \mid H_1, X)}{P(D \mid H_0, X)} = \frac{1.766\times 10^{-81}}{5.296\times 10^{-91}} = 3.335\times 10^9.$$

That is, the data are overwhelmingly more likely for $H_1$ than they are for $H_0$. Combining this with a prior ratio anywhere from 1/100 to 100/1, we get

$$3.335\times 10^7 \leq \frac{P(H_1 \mid D, X)}{P(H_0 \mid D, X)} \leq 3.335\times 10^{11}.$$

That is, the posterior probability of $H_1$ (cheating by dealing seconds) is overwhelmingly greater than the posterior probability of $H_0$ (fair dealing).

Does this mean that we can be nearly certain that the casino is cheating by dealing seconds? Not based on this analysis, because we’ve only looked at two possible hypotheses. But — and here is the other important point — we have decisively ruled out $H_0$. We know that $ P(H_1 \mid D, X) < 1$, so even using the prior ratio most favorable to $H_0$ we have

$$P(H_0 \mid D, X) = \frac{P(H_1 \mid D, X)}{3.335\times 10^7} < 0.2999 \times 10^{-7}.$$

Thus we see that, in spite of the closed-world limitation, Bayesian inference is quite capable of disproving a hypothesis to a high degree of certainty.

\(A\)	\(\neg A\)
\(\mathsf{F}\)	\(\mathsf{T}\)
\(\mathsf{T}\)	\(\mathsf{F}\)

\(A\)	\(B\)	\(A\wedge B\)
\(\mathsf{F}\)	\(\mathsf{F}\)	\(\mathsf{F}\)
\(\mathsf{F}\)	\(\mathsf{T}\)	\(\mathsf{F}\)
\(\mathsf{T}\)	\(\mathsf{F}\)	\(\mathsf{F}\)
\(\mathsf{T}\)	\(\mathsf{T}\)	\(\mathsf{T}\)

\(A\)	\(B\)	\(A\vee B\)
\(\mathsf{F}\)	\(\mathsf{F}\)	\(\mathsf{F}\)
\(\mathsf{F}\)	\(\mathsf{T}\)	\(\mathsf{T}\)
\(\mathsf{T}\)	\(\mathsf{F}\)	\(\mathsf{T}\)
\(\mathsf{T}\)	\(\mathsf{T}\)	\(\mathsf{T}\)

\(A\)	\(B\)	\(A\Rightarrow B\)
\(\mathsf{F}\)	\(\mathsf{F}\)	\(\mathsf{T}\)
\(\mathsf{F}\)	\(\mathsf{T}\)	\(\mathsf{T}\)
\(\mathsf{T}\)	\(\mathsf{F}\)	\(\mathsf{F}\)
\(\mathsf{T}\)	\(\mathsf{T}\)	\(\mathsf{T}\)

\(A\)	\(B\)	\(A\Leftrightarrow B\)
\(\mathsf{F}\)	\(\mathsf{F}\)	\(\mathsf{T}\)
\(\mathsf{F}\)	\(\mathsf{T}\)	\(\mathsf{F}\)
\(\mathsf{T}\)	\(\mathsf{F}\)	\(\mathsf{F}\)
\(\mathsf{T}\)	\(\mathsf{T}\)	\(\mathsf{T}\)