3.3 Truth Tables for Complex Propositions

Truth tables let you determine the truth value of any compound statement, no matter how complicated, by breaking it into pieces and evaluating each piece systematically. Once you can build these tables reliably, you'll be able to identify tautologies, contradictions, and logical equivalences, which are central skills for the rest of this course.

Compound Statements

Complex Propositions and Compound Statements

A complex proposition contains two or more simple propositions joined by logical connectives (and, or, if...then, if and only if). The truth value of the whole statement depends entirely on the truth values of its parts and which connectives join them.

For example, the statement "If it is raining and the ground is wet, then the game is canceled" combines three simple propositions with a conjunction and a conditional. You can't evaluate the whole thing at once; you need to work from the inside out.

Connectives in Compound Statements

When a statement uses multiple connectives, you need to know which one to evaluate last. That last-evaluated connective is called the main connective, and it determines the overall logical structure of the statement.

The standard precedence hierarchy, from highest to lowest:

1. Parentheses (evaluate innermost first)
2. Negation ($\neg$)
3. Conjunction ($\land$)
4. Disjunction ($\lor$)
5. Conditional ($\rightarrow$)
6. Biconditional ($\leftrightarrow$)

So in $\neg p \land q \rightarrow r$, the main connective is the conditional ($\rightarrow$), because it has the lowest precedence of the connectives present. The negation applies only to $p$, the conjunction binds $\neg p$ and $q$ together, and the conditional is evaluated last.

Parentheses always override this hierarchy. If the statement were $\neg (p \land q) \rightarrow r$, the conjunction inside the parentheses gets evaluated first, then the negation applies to the result of that conjunction, and the conditional is still the main connective.

Truth Table Construction

Order of Operations in Truth Tables

Building a truth table for a complex proposition follows a clear sequence:

1. Identify all simple propositions in the statement. If there are $n$ simple propositions, your table will have $2^n$ rows (so 2 propositions give 4 rows, 3 give 8 rows, etc.).
2. List every possible combination of truth values for those propositions. A standard approach: alternate T and F every row for the rightmost variable, every two rows for the next, every four for the next, and so on.
3. Identify the subformulas by applying the order of operations. Work from the innermost parentheses and highest-precedence connectives outward toward the main connective.
4. Create a column for each subformula, evaluating them left to right in order of precedence.
5. The final column (the main connective's column) gives the truth value of the entire compound statement for each row.

Subformulas in Truth Tables

Subformulas are the smaller expressions you evaluate on your way to the final result. Each one gets its own column in the truth table.

Consider $\neg (p \lor q) \land r$. The subformulas, in evaluation order, are:

• $p \lor q$ (inside parentheses, evaluate first)
• $\neg (p \lor q)$ (negation applied to the result)
• $\neg (p \lor q) \land r$ (conjunction, the main connective, evaluated last)

Giving each subformula its own column keeps your work organized and makes errors much easier to catch. If you try to skip steps and jump straight to the final column, mistakes pile up fast, especially with three or more variables.

Logical Properties

Evaluating Logical Properties with Truth Tables

Once you've built a truth table, the pattern in the final column tells you what kind of statement you're dealing with:

• Tautology: The final column is all T. The statement is true under every possible assignment of truth values. Example: $p \lor \neg p$.
• Contradiction: The final column is all F. The statement is false under every possible assignment. Example: $p \land \neg p$.
• Contingency: The final column has a mix of T and F. The statement's truth depends on the actual truth values of its components. Most everyday compound statements are contingencies.

Logical equivalence is a relationship between two statements: they are logically equivalent if and only if their truth tables produce identical final columns across all rows. For instance, $\neg (p \land q)$ and $\neg p \lor \neg q$ are logically equivalent (this is De Morgan's Law). You can verify this by building both truth tables and comparing the results row by row.

Truth-Functional Completeness

A set of connectives is truth-functionally complete if it can express every possible truth function. The standard set ($\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$) is truth-functionally complete, but you don't actually need all five. For example, just $\neg$ and $\land$ together are sufficient, since you can define disjunction, the conditional, and the biconditional in terms of those two.

This matters because it shows that the expressive power of a logical system doesn't depend on having a large number of connectives. Any compound statement, no matter how complex, can be rewritten using a truth-functionally complete subset.