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\).