\usepackagepifont You can't use 'macro parameter character #' in math mode You can't use 'macro parameter character #' in math mode

Truth tables

A truth table for a set of formulas over n variables is a table that enumerates all the possible truth assignments over the variables and the corresponding evaluated values of the formulas in its rows. In practise, building truth tables is only applicable for formulas with few variables because a truth table for formulas involving n variables has 2n rows.

Example: Truth tables for the connectives

  • ​ Negation

    x¬xFTTF
  • ​ Conjunction

    xyxyFFFFTFTFFTTT
  • ​ Disjunction

    xyxyFFFFTTTFTTTT
  • ​ Exclusive-or

    xyxyFFFFTTTFTTTF
  • ​ Implication

    xyxyFFTFTTTFFTTT
  • ​ Bi-implication

    xyxyFFTFTFTFFTTT

Example: Constructing a truth table

Consider the formula

(ab)¬c

and its non-variable sub-formulas (ab) and ¬c. Let’s build the truth table for them, step-by-step. We start with the table below that lists in its rows all the 8 possible value combinations (i.e., truth assignments) for the variables {a,b,c} appearing in the formulas.

abc(ab)¬c(ab)¬cFFFFFTFTFFTTTFFTFTTTFTTT

Based on the columns for a, b and c, it is easy to next evaluate the values in the columns ab and ¬c.

abc(ab)¬c(ab)¬cFFFFTFFTFFFTFFTFTTFFTFFFTTFTFFTTFTTTTTTF

Finally, we can evaluate the values in the column (ab)¬c by using the ones in the columns (ab) and ¬c.

abc(ab)¬c(ab)¬cFFFFTTFFTFFFFTFFTTFTTFFFTFFFTTTFTFFFTTFTTFTTTTFT

Observe that if we have a truth table for a formula, then it is easy to manually check whether the formula is satisfiable (at least one row contains T in the column of the formula) or valid (all rows contain T). For instance, we see that the formula (ab)¬c is satisfiable but not valid. In addition, it is easy to enumerate all its satisfying truth assignments by using the truth table.