5/9 5. Truth Tables

Basic propositions and connectives

A proposition is a statement that has one of two truth values: $T$ for true or $F$ for false. Lowercase letters such as $p$, $q$, and $r$ represent basic propositions. A compound proposition combines basic propositions with logical connectives.

A connective is truth-functional when the truth value of the compound expression is determined entirely by the truth values of its component propositions. The main connectives are:

• Negation: $\neg p$, read as “not $p$.” It reverses the truth value.

• Conjunction: $p \land q$, read as “$p$ and $q$.” It is true only when both components are true.

• Disjunction: $p \lor q$, read as “$p$ or $q$.” In standard logic, it is inclusive and is true when at least one component is true, including when both are true.

• Conditional: $p \to q$, read as “if $p$, then $q$.”

• Biconditional: $p \leftrightarrow q$, read as “$p$ if and only if $q$.”

The connective determines the truth condition for the compound proposition. For example, $p \land q$ requires two true components, while $p \lor q$ requires at least one true component.

Takeaway: Identify the basic propositions first, then identify the connective that determines how their truth values combine.

Truth conditions for the connectives

The individual connectives can be understood by focusing on the rows that make them true or false.

• Negation: $\neg p$ is true when $p$ is false, and false when $p$ is true.

• Conjunction: $p \land q$ is true only in the $T,T$ case. Every case containing at least one $F$ makes it false.

• Disjunction: $p \lor q$ is false only in the $F,F$ case. It is true in the other three cases.

• Conditional: $p \to q$ is false only in the $T,F$ case. Here, the condition occurs but the promised result does not. The antecedent is $p$, and the consequent is $q$.

• Biconditional: $p \leftrightarrow q$ is true when the two components match: both are true or both are false.

For example, if $p$ means “the light is on,” then $\neg p$ means “the light is not on.” If $p$ means “the door is open” and $q$ means “the alarm is on,” then $p \land q$ is true only when both statements are true.

Takeaway: Memorize the exceptional rows: conjunction is true only at $T,T$; disjunction is false only at $F,F$; a conditional is false only at $T,F$; and a biconditional is true when values match.

Determining the number of rows

A truth table must contain one row for every possible assignment of truth values to the distinct basic propositions. If there are $n$ distinct basic propositions, the table requires

rows. Thus, one proposition requires $2^1=2$ rows, two propositions require $2^2=4$ rows, three propositions require $2^3=8$ rows, and four propositions require $2^4=16$ rows.

For two propositions, the assignments are $TT$, $TF$, $FT$, and $FF$. Each assignment must appear exactly once. With three propositions, every combination of $T$ and $F$ across $p$, $q$, and $r$ must appear.

A truth table is therefore complete only when it includes all assignments, without omissions or repetitions.

Takeaway: Count the distinct basic propositions before writing rows, and use $2^n$ to determine the required total.

Building a compound truth table

Construct a compound-proposition table in a fixed sequence:

1. List the distinct basic propositions.

2. Calculate the number of rows with $2^n$.

3. List every possible assignment of $T$ and $F$.

4. Add a column for each important intermediate expression.

5. Evaluate from the inside out, following parentheses and connective precedence.

6. Use the final column to classify the proposition or answer the logical question.

Unless parentheses specify another grouping, the usual order is

For $\neg p \lor q$, first calculate $\neg p$, then combine that result with $q$. The final expression is false only when $p$ is true and $q$ is false.

For $(p \lor q) \land \neg q$, calculate $p \lor q$ and $\neg q$ in separate intermediate columns. The final expression is true only when at least one of $p$ and $q$ is true while $q$ itself is false; this occurs when $p$ is true and $q$ is false.

Parentheses are essential. The expressions $\neg(p \land q)$ and $(\neg p) \land q$ do not generally have the same truth value.

Takeaway: Intermediate columns make each operation visible and reduce errors in the final column.

Reading truth conditions

The truth conditions of a proposition describe exactly the circumstances under which it is true. A truth table makes those circumstances explicit by checking every possible assignment.

• $p \land q$ is true when both $p$ and $q$ are true.

• $p \lor q$ is true when at least one of $p$ and $q$ is true.

• $p \to q$ is false only when $p$ is true and $q$ is false.

• $p \leftrightarrow q$ is true when $p$ and $q$ have matching truth values.

This perspective is useful when explaining a result in words. Instead of merely reporting the final column, state which assignments make the proposition true or false.

For example, the proposition $p \lor \neg p$ is true whether $p$ is true or false. Its truth condition covers every possible assignment. By contrast, $p \land \neg p$ has no assignment under which it is true.

Takeaway: Read a completed table as a precise description of the situations in which the proposition succeeds or fails.

Classifying propositions

Inspect the final column after the table is complete.

• A tautology has only $T$ values. It is true under every possible assignment. For example, $p \lor \neg p$ is a tautology, and so is $p \to p$.

• A contradiction has only $F$ values. It cannot be true under any assignment. For example, $p \land \neg p$ is a contradiction.

• A contingency has both $T$ and $F$ values. Its truth depends on the assignment. For example, $p \land q$ is a contingency because it is true when both components are true and false in the other cases.

Do not classify a proposition from a single row. The classification depends on the entire final column.

Takeaway: All $T$ means tautology, all $F$ means contradiction, and a mixture means contingency.

Testing logical equivalence

To test whether two propositions are logically equivalent, compare their truth values row by row using the same assignments. They are equivalent exactly when their columns match on every row. The notation is

For example, De Morgan’s law states

Build columns for $p \land q$, $\neg(p \land q)$, $\neg p$, $\neg q$, and $\neg p \lor \neg q$. The two final expressions have identical values on all four rows, so the equivalence is established.

A difference on even one row is enough to show that the propositions are not logically equivalent.

Takeaway: Equivalence requires complete row-by-row agreement, not merely agreement on some examples.

Testing argument validity

Truth tables test an argument by looking for a counterexample: a row on which every premise is true while the conclusion is false. If no such row exists, the argument is valid.

An equivalent method combines the premises into one conjunction and makes the conclusion the consequent of a conditional. For premises $P_1$, $P_2$, and so on, test

If this conditional is a tautology, the argument is valid.

For the argument with premises $p \to q$ and $p$, and conclusion $q$, test

Its final column contains only $T$, so the argument is valid. The row where $p$ is true and $q$ is false cannot serve as a counterexample because the premise $p \to q$ is false on that row.

Takeaway: An argument fails only when all premises are true and the conclusion is false; otherwise, the argument is valid.

Avoiding common errors

Most errors come from incomplete enumeration or incorrect evaluation. Check the following points:

• Use $2^n$ rows for $n$ distinct basic propositions.

• Include every assignment exactly once.

• Treat standard disjunction as inclusive: $p \lor q$ is true when both components are true as well as when only one is true.

• Remember that a conditional is false only in the $T,F$ case, not whenever its antecedent is false.

• Respect parentheses; changing the grouping can change the proposition.

• Compute intermediate expressions in separate columns.

• Inspect all rows before deciding whether the result is a tautology, contradiction, or contingency.

A reliable final check is to compare the number of rows with $2^n$, verify that each row is unique, and recalculate every final-column value from its intermediate columns.