Note 1.3.1.
In fact, if there are \(n\) variables, then there are exactly \(2^n\) different combinations of truth values for the variables.
Section 1.3 Logical analysis
We will now leave the English language behind and concentrate on logical statements consisting only of variables and connectives. Keep in mind that variables are not limited to representing simple statements; they can represent compound statements as well.
- truth value
- the property of being true or false
Given a logical statement, view the variables as inputs and the truth value of the entire statement as an output. We would like a systematic way to determine how the truth value of the output changes as we vary the truth values of the inputs.
- logical analysis
- the process of determining the truth value of a statement based on the truth values of its variable substatements
- truth table
- tabular method of carrying out logical analysis
If a statement involves a finite number of variables, then since each variable can have one of only two possible truth values, there are a finite number of different combinations of input truth values for the statement. So we can test each combination one after the other to determine all possible outputs. Arrange this analysis in a table with all possibilities for the input variables on the left and the resulting outputs on the right.
First, let’s establish the truth tables of the basic connectives (that is, of statements containing exactly one connective).
| Negation | |
| \(p\) | \(\lgcnot p\) |
| \(\lgctrue\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgctrue\) |
| Conjunction | ||
| \(p\) | \(q\) | \(p \lgcand q\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) |
| Disjunction | ||
| \(p\) | \(q\) | \(p \lgcor q\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) |
| Conditional | ||
| \(p\) | \(q\) | \(p \lgccond q\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| Biconditional | ||
| \(p\) | \(q\) | \(p \lgcbicond q\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
Note 1.3.3.
- Conjunction \(p \lgcand q\) is true only when both \(p\) and \(q\) are true.
-
Disjunction \(p \lgcor q\) is true when at least one of \(p\) and \(q\) is true.
- The first two rows of the truth table for \(p \lgccond q\) are consistent with the reading “if \(p\) is true then \(q\) is also true.” Really, this reading of the conditional says nothing in the case that \(p\) is actually false, but we cannot leave the “output” column of the truth table blank for the corresponding rows where \(p = \lgcfalse\text{.}\) Instead, the outputs in the last two rows of the truth table for \(p \lgccond q\) are “default” values chosen to avoid inconsistencies. (See Exercise 1.6.3.)
- Looking at all four rows of the truth table for \(p \lgccond q\text{,}\) we can succinctly say that \(p \lgccond q\) is true except when \(p\) is true but \(q\) is false.
- Biconditional \(p \lgcbicond q\) reads “\(p\) is true when \(q\) is true, and only when \(q\) is true.” But this means that when \(q\) is false, \(p\) cannot be true, hence must by false, which explains the fourth row of the truth table.
- Looking at all four rows of the truth table for \(p \lgcbicond q\text{,}\) we can succinctly say that \(p \lgcbicond q\) is true when \(p\) and \(q\) have the same truth value.
We can now use the truth tables of the basic connectives to analyze more complicated statements. Liberal use of extra “intermediate” columns to analyze substatements separately is highly recommended.
Worked Example 1.3.4.
Analyze \(\lgcnot (p \lgcbicond q)\text{.}\)
Solution.
| \(p\) | \(q\) | \(p \lgcbicond q\) | \(\lgcnot (p \lgcbicond q)\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgcfalse\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) |
Note 1.3.5.
The logical statement \(\lgcnot (p \lgcbicond q)\) analyzed in Worked Example 1.3.4 is one way to realize exclusive or: \(p\) or \(q\) but not both.
Worked Example 1.3.6.
Analyze \((p \lgcand q) \lgccond (p \lgcbicond r)\text{.}\)
Solution.
| \(p\) | \(q\) | \(r\) | \(p \lgcand q\) | \(p \lgcbicond r\) | \((p \lgcand q) \lgccond (p \lgcbicond r)\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) |
Worked Example 1.3.7.
Analyze \(\bbrac{(p\lgccond q) \lgccond r} \lgcbicond \bbrac{p \lgccond (q \lgccond r)}\text{.}\)
Solution.
| \(p\) | \(q\) | \(r\) | \(p \lgccond q\) | \(q \lgccond r\) | \(A\) | \(B\) | \(A \lgcbicond B\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgctrue\) |
| \(\lgcfalse\) | \(\lgcfalse\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgctrue\) | \(\lgcfalse\) | \(\lgctrue\) | \(\lgcfalse\) |
