Truth tables

Logic: Propositional logic

Truth tables

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

One variable

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.

Truth table

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.

Row order

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.

Negation

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

Conjunction

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

Disjunction

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

Implication

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

Bi-implication

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

Tool

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.

New example