Discrete Mathematics Study Center

Truth Tables

How can we determine the truth value of compound propositions?

we need the truth values of the propositions that make them up
we can use truth tables to look at all possible combinations

To make a truth table:

one column for every proposition
break the compound proposition into parts
one row for every truth value combination
fill the table in by working with smaller parts first and building to the whole compound proposition

A truth table for $(p \wedge q) \rightarrow \neg(p \vee q)$ is: \begin{array}{cc|ccc|c} p & q & p \wedge q & p \vee q & \neg(p \vee q) & (p \wedge q) \rightarrow \neg(p \vee q) \\\hline T & T & T & T & F & F \\ T & F & F & T & F & T \\ F & T & F & T & F & T \\ F & F & F & F & T & T \\ \end{array} Now, given values for $p$ and $q$, we can look at the appropriate row of the last column to find the truth value of the whole expression. Adding more variables means adding more rows. The truth table for $p \rightarrow (\neg q \vee r)$ is: \begin{array}{ccc|cc|c} p & q & r & \neg q & \neg q \vee r & p \rightarrow (\neg q \vee r) \\\hline T & T & T & F & T & T \\ T & T & F & F & F & F \\ T & F & T & T & T & T \\ T & F & F & T & T & T \\ F & T & T & F & T & T \\ F & T & F & F & F & T \\ F & F & T & T & T & T \\ F & F & F & T & T & T \\ \end{array} If there are $n$ variables, there are $2^n$ different truth value combinations and therefore $2^n$ rows. To make the table, fill the first half of the first column with $T$ and the last half with $F$. Then fill the second column by repeating this pattern in each half, and so on. This is an easy way to guarantee all possibilities are covered. Here is another example of a truth table, this time for $(\neg p \leftrightarrow \neg q) \leftrightarrow (q \leftrightarrow r)$: \begin{array}{ccc|cccc|c} p & q & r & \neg p & \neg q & \neg p \leftrightarrow \neg q & q \leftrightarrow r & (\neg p \leftrightarrow \neg q) \leftrightarrow (q \leftrightarrow r) \\\hline T & T & T & F & F & T & T & T \\ T & T & F & F & F & T & F & F \\ T & F & T & F & T & F & F & F \\ T & F & F & F & T & F & T & F \\ F & T & T & T & F & F & T & F \\ F & T & F & T & F & F & F & T \\ F & F & T & T & T & T & F & F \\ F & F & F & T & T & T & T & T \\ \end{array} Sometimes truth value doesn't depend on the other truth values: the compound proposition is always true or always false, regardless of the truth assignments of the propositions. For example, $p \vee \neg p$ is always true, regardless of whether $p$ is true or false: \begin{array}{cc|c} p & \neg p & p \vee \neg p \\\hline T & F & T \\ F & T & T \\ \end{array} Such a statement is a tautology. On the other hand, $p \wedge \neg p$ is always false, regardless of whether $p$ is true or false: \begin{array}{cc|c} p & \neg p & p \wedge \neg p \\\hline T & F & F \\ F & T & F \\ \end{array} Such a statement is a contradiction. If a statement is neither a tautology nor a contradiction, then the truth values do alter the outcome and we say that the statement is a contingency. Here are some examples that we will classify as tautologies, contradictions, or contingencies:

$((a \vee b) \wedge (\neg a \vee c)) \rightarrow (b \vee c)$ \begin{array}{ccc|ccccc|c} a & b & c & a \vee b & \neg a & \neg a \vee c & (a \vee b) \wedge (\neg a \vee c) & b \vee c & ((a \vee b) \wedge (\neg a \vee c)) \rightarrow (b \vee c)\\\hline T & T & T & T & F & T & T & T & T \\ T & T & F & T & F & F & F & T & T \\ T & F & T & T & F & T & T & T & T \\ T & F & F & T & F & F & F & F & T \\ F & T & T & T & T & T & T & T & T \\ F & T & F & T & T & T & T & T & T \\ F & F & T & F & T & T & F & T & T \\ F & F & F & F & T & T & F & F & T \\ \end{array} Observe that every row in the last column has value $T$. Therefore, the proposition is a tautology.
$\neg ((\neg a \rightarrow (\neg b \vee c)) \leftrightarrow (b \rightarrow (a \vee c)))$ \begin{array}{ccc|ccccccc|c} a & b & c & \neg a & \neg b & \neg b \vee c & \overbrace{\neg a \rightarrow (\neg b \vee c)}^X & a \vee c & \overbrace{b \rightarrow (a \vee c)}^Y & X \leftrightarrow Y & \neg (X \leftrightarrow Y) \\\hline T & T & T & F & F & T & T & T & T & T & F \\ T & T & F & F & F & F & T & T & T & T & F \\ T & F & T & F & T & T & T & T & T & T & F \\ T & F & F & F & T & T & T & T & T & T & F \\ F & T & T & T & F & T & T & T & T & T & F \\ F & T & F & T & F & F & F & F & F & T & F \\ F & F & T & T & T & T & T & T & T & T & F \\ F & F & F & T & T & T & T & F & T & T & F \\ \end{array} Observe that every row in the last column has value $F$. Therefore, the proposition is a contradiction. Notice how we relabelled two large compound propositions in order to save space in the truth table.
$\neg(a \wedge b) \leftrightarrow ((a \vee b) \wedge \neg(a \vee \neg b))$ \begin{array}{cc|ccccccc|c} a & b & a \wedge b & \overbrace{\neg(a \wedge b)}^X & a \vee b & \neg b & a \vee \neg b & \neg(a \vee \neg b) & \overbrace{(a \vee b) \wedge \neg(a \vee \neg b)}^Y & X \leftrightarrow Y \\\hline T & T & T & F & T & F & T & F & F & F \\ T & F & F & T & T & T & T & F & F & T \\ F & T & F & T & T & F & F & T & T & T \\ F & F & F & T & F & T & T & F & F & T \\ \end{array} Observe that the rows of the last column have both $T$s and $F$s. Therefore, the proposition is a contingency.

Logical Equivalences

There is often more than one way to write a proposition. For instance, $p$ and $\neg \neg p$ mean the same thing. We write $p \equiv \neg \neg p$ to mean "the proposition $p$ is logically equivalent to the proposition $\neg \neg p$". How do we tell if two expressions are logically equivalent? The first method is to use truth tables:

logical equivalence = same truth tables
to see if two expressions are logically equivalent, just check their truth tables to see if they match

Some examples:

To check if $\neg (p \vee q)$ and $\neg p \wedge \neg q$ are logically equivalent: \begin{array}{cc|ccccc} p & q & p \vee q & \neg (p \vee q) & \neg p & \neg q & \neg p \wedge \neg q \\\hline T & T & T & F & F & F & F \\ T & F & T & F & F & T & F \\ F & T & T & F & T & F & F \\ F & F & F & T & T & T & T \\ \end{array} Since columns corresponding to $\neg (p \vee q)$ and $(\neg p \wedge \neg q)$ match, the propositions are logically equivalent. This particular equivalence is known as De Morgan's Law.
Are $p \vee (q \wedge r)$ and $(p \vee q) \wedge (p \vee r)$ logically equivalent? \begin{array}{ccc|ccccc} p & q & r & q \wedge r & p \vee (q \wedge r) & p \vee q & p \vee r & (p \vee q) \wedge (p \vee r) \\\hline T & T & T & T & T & T & T & T \\ T & T & F & F & T & T & T & T \\ T & F & T & F & T & T & T & T \\ T & F & F & F & T & T & T & T \\ F & T & T & T & T & T & T & T \\ F & T & F & F & F & T & F & F \\ F & F & T & F & F & F & T & F \\ F & F & F & F & F & F & F & F \\ \end{array} Since columns corresponding to $p \vee (q \wedge r)$ and $(p \vee q) \wedge (p \vee r)$ match, the propositions are logically equivalent. This particular equivalence is known as the Distributive Law.

The second method is to use a series of known logical equivalences to go from one propostion to the other

Identity Law: $p \wedge T \equiv p$ and $p \vee F \equiv p$
Idempotent Law: $p \vee p \equiv p$ and $p \wedge p \equiv p$
Domination Law: $p \vee T \equiv T$ and $p \wedge F \equiv F$
Negation Law: $p \vee \neg p \equiv T$ and $p \wedge \neg p \equiv F$
Double Negation Law: $\neg(\neg p) \equiv p$
Commutative Law: $p \vee q \equiv q \vee p$ and $p \wedge q \equiv q \wedge p$
Associative Law: $(p \vee q) \vee r \equiv p \vee (q \vee r)$ and $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$
Distributive Law: $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ and $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
Absorption Law: $p \vee (p \wedge q) \equiv p$ and $p \wedge (p \vee q) \equiv p$
De Morgan's Law: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$
Implication Equivalence: $p \rightarrow q \equiv \neg p \vee q$
Biconditional Equivalence: $p \leftrightarrow q \equiv (p \rightarrow q) \wedge (q \rightarrow p)$

Any equivalence can be used, but let's stick with these. Let's see some examples.

$\neg(p \vee (\neg p \wedge q))$ and $\neg p \wedge \neg q$ \begin{array}{llll} \neg(p \vee (\neg p \wedge q)) & \equiv & \neg p \wedge \neg(\neg p \wedge q)) & \text{De Morgan's Law} \\ & \equiv & \neg p \wedge (\neg\neg p \vee \neg q)) & \text{De Morgan's Law} \\ & \equiv & \neg p \wedge (p \vee \neg q)) & \text{Double Negation Law} \\ & \equiv & (\neg p \wedge p) \vee (\neg p \wedge q)) & \text{Distributive Law} \\ & \equiv & F \vee (\neg p \wedge q)) & \text{Negation Law} \\ & \equiv & \neg p \wedge \neg q & \text{Identity Law} \\ \end{array} Since each proposition is logically equivalent to the next, we must have that $\neg(p \vee (\neg p \wedge q))$ and $\neg p \wedge \neg q$ are logically equivalent.

We can also use this technique to classify a proposition as a tautology or a contradiction by determining if the proposition is logically equivalent to $T$ or $F$, respectively.

Is $(p \wedge q) \rightarrow (p \vee q)$ a tautology, contradiction or contingency? \begin{array}{llll} (p \wedge q) \rightarrow (p \vee q) & \equiv & \neg(p \wedge q) \vee (p \vee q) & \text{Implication Equivalence} \\ & \equiv & (\neg p \vee \neg q) \vee (p \vee q) & \text{De Morgan's Law} \\ & \equiv & (\neg p \vee p) \vee (q \vee \neg q) & \text{Associative and Commutative Laws} \\ & \equiv & T \vee T & \text{Negation Law} \\ & \equiv & T & \text{Domination Law} \\ \end{array} Since each proposition is logically equivalent to the next, we must have that $(p \wedge q) \rightarrow (p \vee q)$ and $T$ are logically equivalent. Therefore, regardless of the truth values of $p$ and $q$, the truth value of $(p \wedge q) \rightarrow (p \vee q)$ is $T$. Thus, $(p \wedge q) \rightarrow (p \vee q)$ is a tautology.

Here are several more examples that use logical equivalences:

$\neg p \vee \neg q$ and $p \wedge q$ \begin{array}{llll} \neg p \vee \neg q & \equiv & \neg(p \wedge q) & \text{De Morgan's Law} \\ \end{array} However, $p \wedge q$ is not equivalent to $\neg(p \wedge q)$, since it is its negation. Therefore, the two propositions are not logically equivalent.
$(p \rightarrow q) \rightarrow r)$ and $p \rightarrow (q \rightarrow r)$ \begin{array}{ccc|cccc} p & q & r & p \rightarrow q & q \rightarrow r & (p \rightarrow q) \rightarrow r & p \rightarrow (q \rightarrow r) \\\hline T & T & T & T & T & T & T \\ T & T & F & T & F & F & F \\ T & F & T & F & T & T & T \\ T & F & F & F & T & T & T \\ F & T & T & T & T & T & T \\ F & T & F & T & F & F & T \\ F & F & T & T & T & T & T \\ F & F & F & T & T & F & T \\ \end{array} Since the last two columns do not match, the propositions are not logically equivalent.
$\neg p \rightarrow (q \rightarrow r)$ and $q \rightarrow (p \vee r)$ \begin{array}{ccc|ccccc} p & q & r & \neg p & q \rightarrow r & p \vee r & \neg p \rightarrow (q \rightarrow r) & q \rightarrow (p \vee r) \\\hline T & T & T & F & T & T & T & T \\ T & T & F & F & F & T & T & T \\ T & F & T & F & T & T & T & T \\ T & F & F & F & T & T & T & T \\ F & T & T & T & T & T & T & T \\ F & T & F & T & F & F & F & F \\ F & F & T & T & T & T & T & T \\ F & F & F & T & T & F & T & T \\ \end{array} Since the last two columns match, the propositions are logically equivalent. We can also see this using logical equivalences: \begin{array}{llll} \neg p \rightarrow (q \rightarrow r) & \equiv & \neg \neg p \vee (q \rightarrow r) & \text{Implication Equivalence} \\ & \equiv & p \vee (q \rightarrow r) & \text{Double Negation Law} \\ & \equiv & p \vee (\neg q \vee r) & \text{Implication Equivalence} \\ & \equiv & \neg q \vee (p \vee r) & \text{Associative and Commutative Laws} \\ & \equiv & q \rightarrow (p \vee r) & \text{Implication Equivalence} \\ \end{array} Since each proposition is logically equivalent to the next, we must have that the two propositions are logically equivalent.
Are the statements "if food is good, it is not cheap" and "if food is cheap, it is not good" saying the same thing? Let $g$ be the proposition "food is good" and $c$ be the proposition "food is cheap." The first statement is $g \rightarrow \neg c$ and the second statement is $c \rightarrow \neg g$. We now apply some logical equivalences. \begin{array}{llll} g \rightarrow \neg c & \equiv & \neg g \vee \neg c & \text{Implication Equivalence} \\ & \equiv & \neg c \vee \neg g & \text{Commutative Law} \\ & \equiv & c \rightarrow \neg g & \text{Implication Equivalence} \\ \end{array} Since the two statements are logically equivalent, they are saying the same thing.