3.2 Constructing Truth Tables for Simple Propositions

Truth Tables

Truth tables let you systematically determine the truth value of any compound proposition by examining every possible combination of truth values for its simple propositions. They're the core analytical tool in propositional logic, and building them correctly is a skill you'll rely on throughout this course.

Components of a Truth Table

A simple proposition is a declarative sentence that is either true or false. In truth tables, each simple proposition gets a letter name like $p$, $q$, or $r$.

A truth table has four key parts:

• Columns for simple propositions: One column for each simple proposition ($p$, $q$, etc.), plus one or more columns for the compound proposition you're evaluating.
• Rows: Each row represents one truth value assignment, meaning a specific combination of true/false values for every simple proposition. For instance, in a table with $p$ and $q$, one row might assign $p = \text{True}$ and $q = \text{False}$.
• Truth values: The entries in each cell, either T (true) or F (false).
• Compound proposition column(s): The final column(s) showing the result of evaluating the compound proposition under each truth value assignment.

Constructing Truth Tables

Follow these steps to build a truth table from scratch:

1. Identify the simple propositions in your compound proposition. Each one gets its own column. For example, $p \wedge q$ has two simple propositions: $p$ and $q$.

2. Calculate the number of rows using the formula $2^n$, where $n$ is the number of simple propositions. Two propositions give you $2^2 = 4$ rows; three propositions give you $2^3 = 8$ rows. Every doubling accounts for the new true/false option each proposition introduces.

3. Fill in the truth values for each simple proposition column using a systematic alternating pattern:

   • The rightmost simple proposition column alternates every single row: T, F, T, F, ...
   • The next column to the left alternates every two rows: T, T, F, F, T, T, F, F, ...
   • Each subsequent column to the left doubles the alternation length.
   • This pattern guarantees you cover every possible combination exactly once.

4. Evaluate the compound proposition for each row by applying the logical connectives to the truth values in that row. Write the result in the compound proposition column.

Here's what a completed table looks like for $p \wedge q$:

Logical Connectives

Types of Logical Connectives

A logical connective is a symbol used to combine simple propositions into compound propositions. Each connective has a fixed truth function, meaning the truth value of the compound proposition depends entirely on the truth values of its parts. This is what makes propositional logic "truth-functional."

The five standard connectives are:

• Negation ($\neg p$): "not $p$"
• Conjunction ($p \wedge q$): "$p$ and $q$"
• Disjunction ($p \vee q$): "$p$ or $q$"
• Conditional ($p \rightarrow q$): "if $p$, then $q$"
• Biconditional ($p \leftrightarrow q$): "$p$ if and only if $q$"

Evaluating Compound Propositions

When a compound proposition contains multiple connectives, first identify the main connective. Parentheses tell you the order of operations, just like in arithmetic. The main connective is the one that applies last, governing the overall structure of the proposition.

Then evaluate each row of the truth table using these truth functions:

• Negation ($\neg p$): The truth value is the opposite of $p$. If $p$ is true, $\neg p$ is false, and vice versa.
• Conjunction ($p \wedge q$): True only when both $p$ and $q$ are true. False in every other case.
• Disjunction ($p \vee q$): True when at least one of $p$ or $q$ is true. The only way it's false is if both are false. (Note: this is inclusive or, not "one or the other but not both.")
• Conditional ($p \rightarrow q$): False only when $p$ is true and $q$ is false. This trips people up: a conditional with a false antecedent ($p$ is false) is always true, regardless of $q$.
• Biconditional ($p \leftrightarrow q$): True when $p$ and $q$ have the same truth value (both true or both false). False when they differ.

For compound propositions with nested connectives, work from the innermost parentheses outward. Evaluate sub-expressions first, then use those results to evaluate the main connective.