#\newcommand{\propcol}[1]{\blue{#1}}\newcommand{\compcol}[1]{\green{#1}}#We have already seen the logical operators and, or, not, implication (if ... then), and bi-implication (if and only if). We have also seen that using these operators, we can construct compound propositions, which can also evaluate to either true or false. It is however quite difficult to see when a complicated compound proposition such as #(\neg\propcol p \rightarrow\propcol q)\land(\propcol p \lor\propcol r) \leftrightarrow(\propcol q\rightarrow\neg\propcol r)# is true. In order to do so, we introduce truth tables. First we look at an example.
Consider the proposition "I have a bicycle and a car.".
This proposition is precisely true when the propositions
"I have a bicycle." and "I have a car." are both true.
In proposition letters, we can write
\[\begin{array}{ccl}\propcol p&=&\text{ "I have a bicycle."}\\ \propcol{q}&=&\text{ "I have a car."}\\ \propcol p \land\propcol q&=&\text{ "I have a bicycle}\textit{ and }\text{a car."}\end{array}\]
Truth table
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p \land \propcol q# |
| true |
true |
true |
| true |
false |
false |
| false |
true |
false |
| false |
false |
false |
The first two columns correspond to the propositions #\propcol{p}# and #\propcol{q}#. The last column corresponds to compound proposition #\compcol\Phi(\propcol{p}, \propcol{q})#. In the columns we list the values of these propositions in the various cases.
The cases that may occur are the simultaneous evaluations of #\propcol{p}# and #\propcol{q}#. The values are true and false, and so there are four cases, leading to four rows (not counting the header line). The cases are listed lexicographically with true coming before false.
For instance, the entry in the column corresponding to #\compcol\Phi# and in the row with values false for #\propcol{p}# and true for #\propcol{q}# indicates the value of #\propcol p \land\propcol q# for this case, which is false.
The truth table for a single proposition #\propcol p# looks like
| #\propcol{p}# |
#\propcol{p }# |
| true |
true |
| false |
false |
The truth table for the proposition #\neg\propcol{p}# looks like
| #\propcol{p}# |
#\neg \propcol p# |
| true |
false |
| false |
true |
There are exactly two possibilities for the value of #\propcol p# (true or false). For each of these possibilities there are two possible values for the compound expression involving only #\propcol p#. Therefore, there are exactly #2\cdot 2 = 4# essentially different (that is, inequivalent) propositions involving only #\propcol p#. Above, we have seen two.
The other two are simply the propositions true (which is always true) and false (which is always false). These could be written in more complicated ways to make them look like having arguments involving #\propcol p#; for instance #\propcol p\lor\neg\propcol p# for true and #\propcol p\land \neg\propcol p# for false.
Here is the general case.
Let #\compcol{\Phi}=\compcol{\Phi}\left(\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}\right)# be a compound proposition depending on #n# variables #\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}#.
The truth table for #\compcol{\Phi}# is the table that has #n+1# columns, one for each of the dependent variables #\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}# and a column for #\compcol{\Phi}# showing, for each of the values of the #\propcol{\text{variables}}#, the value of the #\compcol{\text{compound proposition}}#.
If so desired for ease of computation or for clarity, auxiliary columns with propositions occurring in #\compcol{\Phi}# can be added directly after the first #n# columns.
The entries of a truth table are the values true or false. This indicates whether the proposition at the top of that column is either true or false when we substitute the values of #\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}# found in the same row of the #n# leftmost columns of the table.
Example
The truth table for #\compcol\Phi=(\propcol p\lor\propcol q)\lor (\propcol p \land\propcol q)# is given by
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p\lor\propcol q# |
#\propcol p\land\propcol q# |
#\blue{\Phi}# |
| true |
true |
true |
true |
true |
| true |
false |
true |
false |
true |
| false |
true |
true |
false |
true |
| false |
false |
false |
false |
false |
The auxiliary columns are those headed by #\propcol p\lor\propcol q# and #\propcol p\land\propcol q#.
Inspection of the table shows that #\compcol{\Phi}# is false precisely when #\propcol{p}# and #\propcol{q}# are both false.
It is customary to list the rows in a fixed order. Most frequently used is the lexicographical order where true comes before false. In the first row, all entries for #\propcol{p_1}, \propcol{p_2},\ldots,\propcol{p_n}# are true and in the last row all these entries are false. If #n\gt 1#, then the second row begins with #n-1# entries true and the #n#-th entry is false, and so on.
The proposition #\neg\propcol p# is true exactly when #\propcol{p}# is false. An example of a negation, in words, is
\[\begin{array}{ccl}\propcol{p}&=&\text{ "It is raining."}\\ \neg\propcol p&=&\text{ "It is }\textit{not}\text{ raining."}\end{array}\]
| #\propcol{p}# |
#\neg\propcol p# |
| true |
false |
| false |
true |
The proposition #\propcol p \land\propcol q# is true when exactly both #\propcol{p}# and #\propcol{q}# are true. An example of a conjunction, in words, is
\[\begin{array}{ccl}\propcol{p}&=&\text{ "It is raining."}\\ \propcol{q}&=&\text{ "I am wearing a rain coat."}\\ \propcol p \land \propcol q&=&\text{ "It is raining }\textit{and}\text{ I am wearing a rain coat."}\end{array}\]
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p \land \propcol q# |
| true |
true |
true |
| true |
false |
false |
| false |
true |
false |
| false |
false |
false |
The proposition #\propcol p\lor\propcol q# is true exactly when #\propcol{p}# is true, #\propcol{q}# is true, or both #\propcol{p}# and #\propcol{q}# are true. An example of a disjunction, in words, is
\[\begin{array}{ccl}\propcol{p}&=&\text{ "It is raining."}\\ \propcol{q}&=&\text{ "It is snowing."}\\ \propcol p \lor\propcol q&=&\text{ "It is raining}\textit{ or }\text{it is snowing."}\end{array}\]
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p \lor \propcol q# |
| true |
true |
true |
| true |
false |
true |
| false |
true |
true |
| false |
false |
false |
The proposition #\propcol p\rightarrow\propcol q# is true when we can say that #\propcol{p}# implies #\propcol{q}#. This is true when both #\propcol{p}# and #\propcol{q}# are true, and when #\propcol{p}# is false. An example of an implication, in words, is
\[\begin{array}{ccl}\propcol{p}&=&\text{ "It is raining."} \\ \propcol{q}&=&\text{ "The ground becomes wet."} \\ \propcol p \rightarrow\propcol q&=&\textit{ "If }\text{it is raining, }\textit{then}\text{ the ground becomes wet."} \end{array}\]
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p \rightarrow \propcol q# |
| true |
true |
true |
| true |
false |
false |
| false |
true |
true |
| false |
false |
true |
The proposition #\propcol p\leftrightarrow\propcol q# is true when #\propcol{p}# and #\propcol{q}# both have the same value. An example of a bi-implication, in words, is
\[\begin{array}{ccl}\propcol{p}&=&\text{ "The sky is clear."}\\ \propcol{q}&=&\text{ "There are no clouds."}\\ \propcol p \leftrightarrow\propcol q&=&\text{ "The sky is clear }\textit{if and only if}\\ && \quad \text{ there are no clouds."}\end{array}\]
| #\propcol{p}# |
#\propcol{q}# |
#\propcol p \leftrightarrow \propcol q# |
| true |
true |
true |
| true |
false |
false |
| false |
true |
false |
| false |
false |
true |
The truth table is a tool for evaluating propositions. It is important to know how to use them. The truth table for #\compcol{\Phi}(\propcol p,\propcol q,\propcol r)# determines the assignment of the value true or false to #\compcol{\Phi}# for each of the eight simultaneous evaluations of the variables #\propcol p#, #\propcol q#, and #\propcol r#. Each row of the table (not counting the header of the table) corresponds to a single simultaneous evaluation. Thus the truth table in case of three variables has eight rows.
Let #n# be a natural number and consider the the truth table of the compound proposition #\compcol{\Phi}(\propcol{p_1},\ldots,\propcol{p_n})#. We will disregard the auxiliary columns.
Each of the propositions #\propcol{p_1},\propcol{p_2},\ldots,\propcol{p_n}# can take two values, so there are #2^n# simultaneous evaluations of the variables occurring in #\compcol{\Phi}#. Each row of the truth table (not counting the header of the table) corresponds to a unique evaluation, so we have #2^n# rows. Each row can be completed with the value of #\compcol\Phi# in the last column, giving us two possibilities (true or false) again. This means that there are #2^{2^n}# different truth tables in the case of #n# variables.
Above, we saw that, indeed, for #n=1#, this number is #4#. If #n=2#, the number is #16#. For #n=3#, there are already #256# different tables.
Is the proposition #(p \land q) \lor p# always true?
No, the proposition #(p \land q) \lor p# is not always true.
We use the following truth table to find the answer.
| #p# |
#q# |
#p\land q# |
#(p \land q) \lor p# |
| true |
true |
true |
true |
| true |
false |
false |
true |
| false |
true |
false |
false |
| false |
false |
false |
false |
We conclude that #(p \land q) \lor p#
is not true for all values of #p# and #q#, and therefore, this proposition is not always true.
Truth tables
