Propositional Logic: Statements, Connectives & Truth Tables
Discrete Mathematics Fundamentals
Chapter 2 · Propositional Logic: Statements, Connectives & Truth Tables
Chapter 1 claimed that "every if statement, every boolean expression ... is propositional logic wearing different syntax." This chapter makes that literal — the formal system for reasoning about statements that are simply true or false, and the exact operations that combine them: the same operations as &&, ||, and !, just written with mathematical symbols instead of code syntax.
What Counts as a Proposition
A proposition is a statement that is unambiguously either true or false — never both, never neither, and never a matter of opinion.
| Statement | Is it a proposition? |
|---|---|
5 > 3 | Yes — true |
| "Paris is the capital of France" | Yes — true |
| "What time is it?" | No — a question, not a statement that's true or false |
x > 3 | No — not yet. Its truth depends on a value x hasn't been given. This is a predicate, and Chapter 3 is entirely about it. |
The Five Core Connectives
Propositions combine using connectives — and every one of them already has a direct equivalent in code you've used before.
| Connective | Symbol | Meaning | Code equivalent |
|---|---|---|---|
| NOT | ¬p | True exactly when p is false | not p / !p |
| AND | p ∧ q | True only when both are true | p and q / p && q |
| OR | p ∨ q | True when at least one is true | p or q / p || q |
| XOR | p ⊕ q | True when exactly one is true, not both | p != q (on booleans) / p ^ q |
| IMPLIES | p → q | False only when p is true and q is false | No direct operator — built from (not p) or q |
Truth Tables — Defining a Connective by Every Possible Case
A truth table lists every combination of inputs and the resulting output — the formal, complete definition of what a connective actually means.
| p | ¬p |
|---|---|
| T | F |
| F | T |
| p | q | p ∧ q | p ∨ q | p ⊕ q | p → q |
|---|---|---|---|---|---|
| T | T | T | T | F | T |
| T | F | F | T | T | F |
| F | T | F | T | T | T |
| F | F | F | F | F | T |
if not condition: return works the way it does: when the precondition doesn't hold, the rest of the logic is vacuously satisfied, because there was never a case to check in the first place.
De Morgan's Laws — Simplifying Negated Conditions
Two of the most practically useful identities in this entire chapter, both directly checkable against the truth tables above:
| Law | Statement |
|---|---|
| De Morgan's (AND) | ¬(p ∧ q) ≡ ¬p ∨ ¬q |
| De Morgan's (OR) | ¬(p ∨ q) ≡ ¬p ∧ ¬q |
In plain terms: negating an AND flips it to an OR of the negations, and negating an OR flips it to an AND of the negations — the connective itself flips, not just the individual pieces.
not a and not b looks like a natural way to write "not both" but it's actually the truth table for "neither" — a genuinely different condition. De Morgan's Law is exactly the tool that tells you the correct rewrite of not (a and b) is (not a) or (not b), not (not a) and (not b).
Logical Equivalence
Two propositions are logically equivalent (written ≡) when they produce the same output for every possible combination of inputs — verified by comparing their truth tables row by row. De Morgan's Laws above are exactly this: two differently-written expressions that are provably, always, the same thing. This matters directly for refactoring — if two boolean expressions are logically equivalent, replacing one with the other can never change what your program does.
Short-Circuit Evaluation — A Runtime Detail, Not a Logic Change
Python and JavaScript's and/or (&&/||) don't always evaluate both sides — if the left side of and is already false, the right side is never even run, since the overall result is already determined. This is called short-circuit evaluation. It doesn't change the truth table at all — the logical result is identical either way — but it does matter if the right-hand side has a side effect (like calling a function), since that side effect might never actually happen.
Hands-On Exercises
Build a complete truth table for the compound proposition (p ∨ q) ∧ ¬p, and state in plain English what condition it actually captures.
A function contains the condition if not (is_valid and is_authorized):. Using De Morgan's Law, rewrite this without a negated compound expression, and explain why your rewrite is guaranteed to behave identically for every possible combination of is_valid and is_authorized.
Determine whether p → q and q → p are logically equivalent, by building both truth tables and comparing them row by row. If they're not equivalent, give a concrete real-world example of a true "if p then q" statement whose reverse is false.
Chapter 2 Quick Reference
- A proposition is a statement that's unambiguously true or false — a statement with an unknown variable is a predicate instead (Chapter 3)
- Five connectives: NOT (¬), AND (∧), OR (∨), XOR (⊕), IMPLIES (→) — each with a direct code equivalent
- A truth table defines a connective completely, by listing the output for every combination of inputs
- p → q is true whenever p is false, regardless of q — the source of "vacuous truth"
- De Morgan's Laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q — the connective itself flips
- Logically equivalent expressions can always be swapped for each other without changing program behavior
- Short-circuit evaluation is a runtime detail — it doesn't change the logical truth table, only whether side effects on the right-hand side actually run
- Next chapter: Predicate logic and quantifiers — what happens once a statement has a variable in it