Propositional logic

Core idea

Propositional logic is the second major formal system in the book and the one most beginners settle into first. It treats whole sentences as atomic propositions — labelled p, q, r, and so on — and studies how their truth values combine when connected by five logical connectives: negation (¬p, "not p"), conjunction (p ∧ q, "p and q"), disjunction (p ∨ q, "p or q"), the conditional (p → q, "if p then q"), and the biconditional (p ↔ q, "p if and only if q").

The system is complete in a precise technical sense: every truth-functional combination of propositions can be expressed using these five connectives, and validity can be decided for any argument in a finite number of steps by writing out its truth table. This is the system's signature achievement — for the first time in the history of logic, the validity question has an algorithm that always terminates. The cost is that the system can only see the structure of compound sentences; it cannot see inside them. The topic on predicate logic next supplies that finer resolution.

Why it matters

Why this is the heart of formal logic

Almost every digital circuit, every programming-language conditional, every mathematical proof, and every formal system in computer science traces its grammar back to propositional logic. The connectives are the algebraic operations on a two-element set {true, false}, and the truth table is the multiplication table of that algebra. Once you internalize how the truth values flow through compound sentences, the rest of formal reasoning becomes manipulating that flow.

Why beginners hit a wall on the conditional

The conditional p → q ("if p then q") is the one connective whose truth table surprises new learners. It is false only when p is true and q is false. When p is false, p → q is true regardless of q. This "vacuous truth" of conditionals with false antecedents is not a defect of the formal system — it is the cleanest way to make the connective truth-functional. Most natural-language uses of "if-then" carry extra content (causation, temporal sequence, relevance) that the connective deliberately strips out.

Mental model

The five connectives and their truth tables

Copy sourceZoom

The truth-table method

Truth tables are the algorithmic core. To test whether an argument is valid, list every atomic proposition; enumerate all 2ⁿ rows of possible truth assignments; compute the truth value of each premise and the conclusion in every row. The argument is valid if and only if there is no row where all premises are true and the conclusion is false.

For a single connective p → q, the truth table is:

| p | q | p → q | |---|---|---------| | T | T | T | | T | F | F | | F | T | T | | F | F | T |

For a full argument like modus ponens (p → q, p, therefore q), enumerate rows and check the critical row — the one where the premises are all true. Modus ponens has one such row (row 1 in the above table, where both premises p → q and p are true). In that row, the conclusion q is also true. No row has true premises with false conclusion. Valid.

Copy sourceZoom

Tautology, contradiction, and contingency

Three classes of formulas, defined entirely by the truth table:

• A tautology is true in every row. Example: p ∨ ¬p (the law of excluded middle).
• A contradiction is false in every row. Example: p ∧ ¬p (the law of non-contradiction inverted).
• A contingency is true in some rows, false in others. Most everyday sentences are contingent.

Tautologies are the logical truths of the system; contradictions are the logical falsehoods. Two formulas are logically equivalent if they have identical truth tables — equivalently, if A ↔ B is a tautology.

Natural deduction — proof without enumeration

For arguments with many atoms, truth tables become impractical. Natural deduction offers a small set of inference rules that you apply step by step to derive the conclusion from the premises. The rules pair an introduction rule (how to construct a connective) with an elimination rule (how to use it).

Copy sourceZoom

Practical application

For any argument involving "and", "or", "not", "if-then", the workflow is:

1. Symbolize. Replace each atomic English clause with a propositional variable. Translate connectives carefully — beware that English or is ambiguous (inclusive vs exclusive) and English if-then carries extra meaning the connective strips.
2. Choose a method. For two or three atoms, a truth table is fastest. For four or more, switch to natural deduction.
3. For truth tables, write out all rows, compute each premise and conclusion, check critical rows. Locating a counter-example row is enough to declare invalidity.
4. For natural deduction, write the premises, then apply inference rules step by step to derive the conclusion. Reductio ad absurdum (proof by contradiction) is often the cleanest move for negative conclusions.

Example

A real engineering decision:

• "If the build is green, the release ships on Friday. If the release ships on Friday, marketing's launch goes live Monday. The launch is not going live Monday. Therefore, the build is not green."

Symbolize:

• Let B = "the build is green"
• Let R = "the release ships on Friday"
• Let M = "marketing's launch goes live Monday"

Premises and conclusion:

• Premise 1: B → R
• Premise 2: R → M
• Premise 3: ¬M
• Conclusion: ¬B

Natural-deduction proof:

1. B → R (premise 1)
2. R → M (premise 2)
3. ¬M (premise 3)
4. B → M (hypothetical syllogism on 1, 2)
5. ¬B (modus tollens on 4, 3) — the conclusion.

Or verify by truth table. With three atoms, there are 8 rows. The conclusion fails only if there is some row where premises 1, 2, 3 are all true but ¬B is false (i.e., B is true). If B is true and B → R is true, then R is true. If R is true and R → M is true, then M is true. But then ¬M is false. So no row has all premises true with B true. The argument is valid.

Now look at the soundness layer. Is B → R actually true? Maybe — but maybe a green build still produces a hotfix that delays the ship. Is R → M actually true? Maybe — but if marketing wants more lead time, they might launch later regardless. The validity check tells us the form is correct; whether the conclusion is true in the real world depends on whether the conditional premises are real causal claims about your release process. Validity is mechanical. Soundness is engineering judgement.

Related lessons