### 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 |

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.

We use the following truth table to find the answer.

#p# | #q# | #p\lor q# | #(p \lor q) \land q# |

true | true | true | true |

true | false | true | false |

false | true | true | true |

false | false | false | false |

**Pass Your Math**independent of your university. See pricing and more.

Or visit omptest.org if jou are taking an OMPT exam.