2.3 Truth tables

Truth tables give you a systematic way to evaluate any logical statement by listing every possible combination of truth values for its variables. They're one of the most concrete tools in this course: if you can build a truth table, you can determine whether an argument is valid, check if two statements are equivalent, and identify tautologies and contradictions with certainty.

Basics of Truth Tables

A truth table is a grid that maps out every possible scenario for a logical statement. Each row represents one combination of truth values, and each column tracks either a variable or a compound expression built from those variables.

Components of Truth Tables

• Rows represent all possible combinations of truth values for your variables
• Columns show individual variables, intermediate steps, and the final compound statement
• Headers use capital letters (P, Q, R) to represent simple propositions
• Truth values are written as T (true) and F (false), or sometimes 1 and 0

The number of rows you need is $2^n$, where $n$ is the number of variables. So 2 variables give you 4 rows, 3 variables give you 8, and 4 variables give you 16. This grows fast, which is why truth tables work best for statements with a small number of variables.

Purpose and Applications

• Determine whether a logical argument is valid
• Check if two statements are logically equivalent
• Identify tautologies (always true) and contradictions (always false)
• Simplify Boolean expressions in computer science
• Support the design of digital circuits

Logical Connectives

Each connective has a specific rule for how it combines truth values. You need to know all five cold.

Conjunction (AND)

The conjunction $P \wedge Q$ is true only when both P and Q are true. Think of it as a strict requirement: every part must hold.

</>Code
P | Q | P ∧ Q
T | T |   T
T | F |   F
F | T |   F
F | F |   F

Disjunction (OR)

The disjunction $P \vee Q$ is true when at least one of P or Q is true. The only way it's false is if both are false. Note that this is inclusive OR, meaning it's also true when both are true.

</>Code
P | Q | P ∨ Q
T | T |   T
T | F |   T
F | T |   T
F | F |   F

Negation (NOT)

Negation $\neg P$ simply flips the truth value. True becomes false, false becomes true.

</>Code
P | ¬P
T |  F
F |  T

Conditional (IF-THEN)

The conditional $P \rightarrow Q$ is the one that trips people up the most. It's false in exactly one case: when P is true and Q is false. In every other case, it's true.

</>Code
P | Q | P → Q
T | T |   T
T | F |   F
F | T |   T
F | F |   T

The rows where P is false deserve attention. When the hypothesis (P) is false, the conditional is automatically true regardless of Q. This is called vacuous truth. It feels strange at first, but it makes the logic consistent. Think of it this way: "If it rains, I'll bring an umbrella." On a sunny day, you haven't broken your promise whether you bring an umbrella or not.

Biconditional (IF AND ONLY IF)

The biconditional $P \leftrightarrow Q$ is true when both sides have the same truth value. It captures the idea of "necessary and sufficient": P happens exactly when Q happens.

</>Code
P | Q | P ↔ Q
T | T |   T
T | F |   F
F | T |   F
F | F |   T

Construction of Truth Tables

Setting Up the Variables

1. Count the number of distinct variables in your statement. Call this $n$.
2. Create $2^n$ rows beneath your header.
3. Fill in truth values systematically. For two variables P and Q, a standard pattern is:
   • P: T, T, F, F
   • Q: T, F, T, F

This pattern works like binary counting and guarantees you cover every combination.

Building Compound Statements

For a complex expression like $\neg P \wedge (Q \vee P)$, don't try to evaluate it all at once. Break it into pieces:

1. Create a column for each intermediate expression (e.g., $\neg P$, then $Q \vee P$)
2. Evaluate the innermost or simplest parts first
3. Combine intermediate results to get the final column

Here's what that looks like:

</>Code
P | Q | ¬P | Q ∨ P | ¬P ∧ (Q ∨ P)
T | T |  F |   T   |      F
T | F |  F |   T   |      F
F | T |  T |   T   |      T
F | F |  T |   F   |      F

Order of Operations

When parentheses don't make the grouping obvious, follow this precedence (highest to lowest):

1. Parentheses (always first)
2. Negation $\neg$
3. Conjunction $\wedge$
4. Disjunction $\vee$
5. Conditional $\rightarrow$
6. Biconditional $\leftrightarrow$

For connectives at the same level, evaluate left to right. When in doubt, add parentheses to make your intended grouping explicit.

Evaluating Logical Expressions

Determining Validity of Arguments

An argument is valid if there's no possible scenario where all the premises are true and the conclusion is false. Here's how to check:

1. Translate the premises and conclusion into symbolic logic
2. Build a truth table that includes columns for each premise and the conclusion
3. Look at only the rows where every premise is true
4. Check whether the conclusion is also true in all of those rows

If you find even one row where all premises are true but the conclusion is false, the argument is invalid.

Tautologies, Contradictions, and Contingencies

• A tautology is a statement that's true in every row of its truth table. Example: $P \vee \neg P$
• A contradiction is a statement that's false in every row. Example: $P \wedge \neg P$
• A contingency is everything else: true in some rows, false in others

You can spot these by looking at the final column. All T's means tautology. All F's means contradiction.

Equivalence of Statements

Two statements are logically equivalent if their truth tables produce identical final columns. You write this as $P \equiv Q$ (or sometimes $P \Leftrightarrow Q$).

Some equivalences you should recognize:

• Double negation: $\neg(\neg P) \equiv P$
• De Morgan's laws:
  • $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$
  • $\neg(P \vee Q) \equiv \neg P \wedge \neg Q$
• Contrapositive: $P \rightarrow Q \equiv \neg Q \rightarrow \neg P$
• Conditional as disjunction: $P \rightarrow Q \equiv \neg P \vee Q$

You can verify any of these by building truth tables for both sides and confirming the columns match.

Applications in Logic

Argument Analysis

To analyze an argument with a truth table:

1. Identify the premises and conclusion
2. Assign variables to each simple proposition
3. Write the premises and conclusion in symbolic form
4. Build the truth table
5. Check all rows where premises are simultaneously true
6. If the conclusion is true in every such row, the argument is valid

Proof Techniques

Truth tables serve as a form of proof by exhaustion: you literally check every possible case. This makes them a reliable (if sometimes tedious) way to:

• Prove that a statement is a tautology
• Show that two expressions are logically equivalent
• Demonstrate that an argument form is valid
• Reveal contradictions in a set of assumptions

Truth Tables in Computer Science

Truth tables connect directly to Boolean algebra, which underlies digital computing. Every logic gate (AND, OR, NOT, etc.) corresponds to one of the connectives above, and its behavior is defined by a truth table.

In programming, truth tables help you reason about complex conditional logic. If you have a tangled chain of if-else statements, writing out the truth table for your conditions can reveal redundancies, missed cases, or logical errors.

Common Pitfalls and Misconceptions

Inclusive vs. exclusive OR. In everyday English, "or" often means "one or the other but not both" (exclusive OR). In logic, $\vee$ is inclusive: it's true when both are true. Watch for this when translating English into symbols.

The conditional feels backward. Many students expect $P \rightarrow Q$ to be false when P is false. It's not. The conditional only makes a claim about what happens when P is true. When P is false, the conditional is vacuously true.

Validity vs. truth. A valid argument can have a false conclusion (if one of its premises is false). Validity means the form of the reasoning is correct. Soundness means the argument is valid and all premises are actually true. Don't confuse the two.

Missing rows. With 3 or more variables, it's easy to accidentally skip combinations. Always use the $2^n$ formula and fill in your variable columns systematically before evaluating anything.

Confusing equivalence with the biconditional. The biconditional $P \leftrightarrow Q$ is a statement within your logical system. Logical equivalence ($\equiv$) is a claim about two statements having the same truth table. They're related but operate at different levels.