Truth Tables

How can we determine the truth value of compound propositions? To make a truth table: 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:

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: Some examples: The second method is to use a series of known logical equivalences to go from one propostion to the other Any equivalence can be used, but let's stick with these. Let's see some examples. 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. Here are several more examples that use logical equivalences: