Truth Tables for Compound Propositions

The Structure of a Truth Table

In the last lesson, you saw a simple truth table for the basic connectives. Now, we will formalize their construction for any compound proposition. A truth table provides an exhaustive analysis of a proposition by listing every possible combination of truth values for its simple components.

The key principles are:

• Rows: For a proposition with $n$ distinct simple propositions (e.g., $p,q,r,...$), there are $2^n$ possible combinations of truth values. Therefore, the truth table will have $2^n$ rows, plus a header row. Your experience in software development will make this principle intuitive; it's analogous to the number of states representable by $n$ bits.
• Columns: We need a column for each simple proposition, a column for each intermediate sub-expression, and a final column for the entire compound proposition.

To construct the initial columns for the simple propositions systematically, a common method is to model binary counting. For three variables $p,q,r$:

• The column for $r$ (the rightmost variable) alternates T, F, T, F, ...
• The column for $q$ alternates TT, FF, TT, FF, ...
• The column for $p$ (the leftmost) alternates TTTT, FFFF, ...

This ensures all $2^3=8$ combinations are covered without repetition or omission.

Constructing and Evaluating a Truth Table

The best way to learn this process is to see it in action. The following video provides an excellent, clear walkthrough of how to set up and fill out a truth table for a compound proposition involving three variables.

As you saw, the process involves breaking down the complex proposition into its smallest parts and evaluating them one step at a time, just as you would evaluate a complex arithmetic or programming expression.

Let's use an image to visualize this "building up" process. The table below is partially completed for the expression $(p\vee q)\wedge \neg r$. Columns for the simple propositions ($p,q,r$) are filled, and columns for the sub-expressions ($p\vee q$ and $\neg r$) are also filled. The final step would be to compute the main connective, $\wedge$, using the values from the two preceding columns.

Now, let's solidify this procedure with a formal reading that breaks down the process and provides another worked example.

Tautologies, Contradictions, and Contingencies

Truth tables allow us to classify compound propositions based on their truth values. This is a crucial step towards understanding the nature of logical laws.

• A tautology is a proposition that is true in every row of the truth table. Its truth is independent of the truth values of its components. Tautologies represent universal logical truths. A simple example is $p\vee \neg p$ ("A statement is either true or it is not true").
• A contradiction is a proposition that is false in every row. An example is $p\wedge \neg p$.
• A contingency is a proposition that is true in some rows and false in others. Most complex propositions fall into this category.

Let's consider a slightly more complex tautology, which represents a fundamental rule of inference called Modus Ponens: $((p\to q)\wedge p)\to q$. In words: "If $p$ implies $q$, and $p$ is true, then $q$ must be true." Try to construct the truth table for this proposition yourself. You will find that the final column contains only 'T's, confirming it as a law of logic.

Logical Equivalence

A primary application of truth tables in mathematics is to establish logical equivalence. Two propositions are logically equivalent if they have identical truth tables. We denote this with the symbol $\equiv$.

For example, in the previous lesson, we asserted that the conditional statement $p\to q$ is difficult to grasp. One way to clarify its meaning is to show that it is logically equivalent to $\neg p\vee q$. Let's verify this.

Since the columns for $\neg p\vee q$ and $p\to q$ are identical, we can state that $(p\to q)\equiv (\neg p\vee q)$. This equivalence is extremely useful in proofs, as it allows us to replace a conditional statement with a disjunction, which can sometimes be easier to work with.

One of the most important sets of logical equivalences are De Morgan's Laws.

Practice Problem

Let's test your understanding. Take a moment to construct a full truth table for the following proposition:
$(p\vee \neg q)\to (p\wedge q)$

This will require columns for $p,q,\neg q,p\vee \neg q,p\wedge q$, and finally the full expression. After you have attempted it, you can check your work against the solution presented in the following video.

Conclusion

In this lesson, you have learned the systematic process of using truth tables to analyze compound propositions. The key takeaways are:

• Truth tables provide a mechanical, error-proof method to evaluate the truth of a logical statement for all possible scenarios.
• The construction follows a clear algorithm: establish $2^n$ rows for $n$ variables, and build columns for simple propositions, sub-expressions, and the final expression.
• The final column of a truth table allows us to classify propositions as tautologies (always true), contradictions (always false), or contingencies.
• Truth tables are the definitive tool for verifying logical equivalence, a concept that is indispensable for manipulating expressions within mathematical proofs.

While powerful, truth tables become unwieldy as the number of variables grows. For statements about infinite sets (e.g., "all integers have a certain property"), we cannot use a truth table. In the next lesson, we will begin our study of predicate logic, introducing the universal quantifier ("for all", $\forall$) and the existential quantifier ("there exists", $\exists$), which give us the language to reason about such general statements.