Mathematical Logic
Learning Objectives
By the end of this page, you will be able to:
- Build truth tables for propositions formed with negation, conjunction, disjunction, implication, and biconditional.
- Determine whether a compound statement is a tautology, a contradiction, or a contingency.
- Translate everyday statements into predicate logic using universal (∀) and existential (∃) quantifiers.
- Apply standard rules of inference (modus ponens, modus tollens, hypothetical syllogism, etc.) to construct valid arguments.
- Write and evaluate proofs using direct proof, contrapositive, contradiction, and mathematical induction.
- Identify common logical fallacies and explain why they fail.
Quick Answer
Mathematical logic is the formal study of how to represent statements and reason about them precisely. Propositional logic works with whole statements (propositions) that are either true or false, combined using operators like AND, OR, NOT, and IF-THEN. Predicate logic extends this by looking inside statements, using variables, predicates, and quantifiers ("for all," "there exists") to express things propositional logic cannot, like "every prime greater than 2 is odd." Logic matters because it is the backbone of correct reasoning: it underlies how compilers check program correctness, how databases evaluate queries, how digital circuits are designed, and how mathematicians write rigorous proofs. Without a formal system for reasoning, "valid" arguments would be a matter of opinion rather than something you could check mechanically.
Propositional Logic
Definition
A proposition is a declarative sentence that is unambiguously either true (T) or false (F), never both, and never neither. "8 is an even number" is a proposition (true). "Please close the door" and "x + 2 = 5" are not propositions — the first is a command, and the second is only true or false once you know what x is (it becomes a proposition once x is fixed).
Explanation
Propositions are combined into compound statements using logical connectives:
| Connective | Symbol | Reads as | True when |
|---|---|---|---|
| Negation | ¬p (or ~p) | "not p" | p is false |
| Conjunction | p ∧ q | "p and q" | both p and q are true |
| Disjunction | p ∨ q | "p or q" | at least one of p, q is true |
| Implication | p → q | "if p then q" | p is false, or q is true |
| Biconditional | p ↔ q | "p if and only if q" | p and q have the same truth value |
The trickiest of these is implication. Students often expect p → q to be false whenever p is false, but by definition it is automatically true whenever the hypothesis p is false — a false premise makes the conditional "vacuously true." For example, "If 2 + 2 = 5, then I am the Queen" is treated as true in formal logic, because the "if" part never holds.
A truth table lists every combination of truth values for the input propositions and shows the resulting value of the compound statement. It is the definitive tool for checking whether two statements are logically equivalent, or whether a statement is always true (a tautology), always false (a contradiction), or sometimes true and sometimes false (a contingency).
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Example
Let p = "It is raining" and q = "The ground is wet." Then:
- ¬p = "It is not raining"
- p → q = "If it is raining, the ground is wet"
- p ∧ ¬q = "It is raining and the ground is not wet" — this is false whenever p → q is true, which is exactly why p ∧ ¬q is used to disprove an implication.
Real-World Example
Search engines and database query systems (like SQL's WHERE clause) evaluate compound boolean conditions exactly this way. A query like WHERE (price < 500) AND (in_stock = true) is a conjunction of two propositions, and the database engine effectively builds a truth table row for every record to decide whether to include it.
Why It Matters
Digital circuits (AND gates, OR gates, NOT gates) are physical implementations of these same logical connectives. Every if statement in a program, every filter condition in a spreadsheet, and every access-control rule ("allow if authenticated AND role = admin") is propositional logic in disguise. Learning to read truth tables lets you predict program behavior without running the code.
Common Misunderstanding
Students frequently assume p → q means the same thing as q → p. It does not: "If it rains, the ground gets wet" does not mean "If the ground is wet, it rained" (a sprinkler could have wet it). Confusing a conditional with its converse is one of the most common logical errors in everyday and mathematical reasoning.
Predicate Logic and Quantifiers
Definition
A predicate is a statement containing one or more variables that becomes a proposition once the variables are given specific values. P(x): "x is a prime number" is a predicate — not true or false on its own, but P(7) is true and P(8) is false. Quantifiers bind these variables to state how many elements of a domain satisfy the predicate.
Explanation
Two quantifiers matter most:
- Universal quantifier (∀): ∀x P(x) means "P(x) is true for every x in the domain." To disprove it, you only need one counterexample.
- Existential quantifier (∃): ∃x P(x) means "there is at least one x in the domain for which P(x) is true." To prove it, one example suffices; to disprove it, you must show P(x) fails for every x.
Negating quantified statements follows a precise rule (De Morgan's laws for quantifiers):
- ¬(∀x P(x)) ≡ ∃x ¬P(x) — "not everyone" means "someone doesn't."
- ¬(∃x P(x)) ≡ ∀x ¬P(x) — "no one" means "everyone doesn't."
Example
Let the domain be all integers, and P(x): "x is even."
- ∀x P(x) is false (3 is a counterexample).
- ∃x P(x) is true (2 satisfies it).
- ∀x (Person(x) → Human(x)) reads "For every x, if x is a person, then x is human" — a universal statement built from an implication, which is the standard pattern for "all A are B" statements.
Real-World Example
Form validation on a website checks a universal statement: "every required field is non-empty" (∀ field, filled(field)). A search feature checks an existential one: "does there exist a record matching these keywords" (∃ record, matches(record, keywords)). Recognizing the quantifier tells you exactly what counts as a failure case.
Why It Matters
Predicate logic is the foundation of formal verification, database query languages (SQL's EXISTS and NOT EXISTS are direct translations of ∃ and its negation), and automated theorem proving. It lets you express precise mathematical claims — like the definition of a limit in calculus, or "every graph with more edges than vertices has a cycle" — that propositional logic is too coarse to capture.
Common Misunderstanding
Students often think swapping the order of two different quantifiers doesn't change meaning. It does. "∀x ∃y (y > x)" ("for every number there's a bigger one") is true for integers, but "∃y ∀x (y > x)" ("there's a number bigger than every number") is false. Order matters whenever the quantifiers are mixed.
Rules of Inference and Proof Techniques
Definition
Rules of inference are logically valid patterns that let you derive new true statements from ones already accepted as true. A proof is a chain of such steps that establishes a conclusion beyond doubt, starting from axioms or given premises.
Explanation
The most-used rules of inference:
| Rule | Pattern | Meaning |
|---|---|---|
| Modus Ponens | p → q, p ⊢ q | If p implies q, and p holds, then q holds |
| Modus Tollens | p → q, ¬q ⊢ ¬p | If p implies q, and q is false, then p is false |
| Hypothetical Syllogism | p → q, q → r ⊢ p → r | Implications chain together |
| Disjunctive Syllogism | p ∨ q, ¬p ⊢ q | If one of two options is ruled out, the other holds |
| Conjunction | p, q ⊢ p ∧ q | Two true statements can be combined |
Common proof techniques built on these rules:
- Direct proof: Assume p, use definitions and known results, derive q.
- Proof by contrapositive: To prove p → q, instead prove ¬q → ¬p (logically equivalent, sometimes far easier).
- Proof by contradiction: Assume p is true and the conclusion is false; derive an impossible statement, so the conclusion must actually be true.
- Mathematical induction: Prove a base case, then prove that truth for case k forces truth for case k + 1 — establishing the statement for all natural numbers at once.
Worked Proof Example
Claim: For all integers n ≥ 0, 2ⁿ ≥ n + 1.
Proof by induction:
Base case (n = 0): 2⁰ = 1, and n + 1 = 1. Since 1 ≥ 1, the base case holds.
Inductive hypothesis: Assume 2ᵏ ≥ k + 1 holds for some integer k ≥ 0.
Inductive step: Show 2ᵏ⁺¹ ≥ k + 2.
2^(k+1) = 2 · 2^k
≥ 2 · (k + 1) [by the inductive hypothesis]
= 2k + 2
≥ k + 2 [since k ≥ 0]
Since the base case holds and each case implies the next, by the principle of mathematical induction, 2ⁿ ≥ n + 1 for all integers n ≥ 0. ∎
This same skeleton — base case, inductive hypothesis, inductive step — is what you will reuse for almost every induction proof you write.
Reasoning Flow
Real-World Example
Compiler type-checkers use rules of inference to prove that a program is well-typed before it ever runs: "if expression a has type int and expression b has type int, then a + b has type int" is a modus-ponens-style inference rule applied automatically, thousands of times, to your source code.
Why It Matters
Every algorithm's correctness proof, every cryptographic security guarantee, and every safety-critical system verification (aircraft software, medical devices) relies on chains of valid inference. A single invalid step invalidates the entire proof, so learning to recognize valid inference patterns is what separates a rigorous argument from a plausible-sounding one.
Common Misunderstanding
A frequent error is affirming the consequent: from p → q and q, students conclude p. This is invalid — q could be true for reasons unrelated to p. ("If it rained, the ground is wet" plus "the ground is wet" does not prove it rained; a sprinkler could be the cause.) Only modus ponens (p → q, p ⊢ q) and modus tollens (p → q, ¬q ⊢ ¬p) are valid; affirming the consequent and denying the antecedent are both fallacies.
Key Terms
| Term | Definition |
|---|---|
| Proposition | A declarative statement that is definitively true or false |
| Logical connective | An operator (¬, ∧, ∨, →, ↔) that combines or modifies propositions |
| Truth table | A table listing every truth-value combination of inputs and the resulting output |
| Tautology | A compound statement that is true for every possible truth-value assignment |
| Contradiction | A compound statement that is false for every possible truth-value assignment |
| Predicate | A statement with variables that becomes a proposition once the variables are assigned values |
| Universal quantifier (∀) | Asserts a predicate holds for every element in the domain |
| Existential quantifier (∃) | Asserts a predicate holds for at least one element in the domain |
| Rule of inference | A logically valid pattern for deriving a new true statement from existing ones |
| Modus ponens | The inference rule: from p → q and p, conclude q |
| Modus tollens | The inference rule: from p → q and ¬q, conclude ¬p |
| Proof by contradiction | A proof technique that assumes the negation of the goal and derives an impossibility |
| Mathematical induction | A proof technique for "for all n" claims using a base case and an inductive step |
Common Mistakes
Misconception 1: "p → q is false whenever p is false." Why it's wrong: This confuses everyday intuition about "if...then" with the formal definition. In formal logic, p → q is only false when p is true and q is false. Correct understanding: p → q is true in every row except T/F. A false hypothesis makes the implication vacuously true.
Misconception 2: "p → q and q → p mean the same thing." Why it's wrong: Swapping hypothesis and conclusion produces the converse, which is a logically different statement and is not guaranteed to have the same truth value. Correct understanding: p → q is only logically equivalent to its contrapositive, ¬q → ¬p — not to its converse or inverse.
Misconception 3: "Reversing the order of two quantifiers doesn't change the meaning." Why it's wrong: When quantifiers of different types are mixed (∀ and ∃), swapping their order can turn a true statement into a false one, because the choice of the existential variable is allowed to depend on the universal one only when ∀ comes first. Correct understanding: ∀x ∃y P(x, y) generally is not equivalent to ∃y ∀x P(x, y); always keep the original quantifier order when translating or negating statements.
Comparison and Connections
| Concept A | Concept B | Key Difference |
|---|---|---|
| Propositional logic | Predicate logic | Propositional logic treats statements as atomic units; predicate logic looks inside statements using variables and quantifiers |
| Converse (q → p) | Contrapositive (¬q → ¬p) | The contrapositive is always logically equivalent to the original implication; the converse generally is not |
| Modus ponens | Affirming the consequent | Modus ponens (p → q, p ⊢ q) is valid; affirming the consequent (p → q, q ⊢ p) is a fallacy |
| Direct proof | Proof by contradiction | Direct proof builds forward from premises to conclusion; contradiction assumes the conclusion is false and derives an impossibility |
| Universal quantifier (∀) | Existential quantifier (∃) | ∀ requires the predicate to hold for every element; ∃ requires it to hold for at least one, and their negations swap into each other |
Practice Questions
Recall
- What are the five basic logical connectives, and what symbol represents each? Answer guidance: Negation (¬), conjunction (∧), disjunction (∨), implication (→), biconditional (↔) — list each symbol with its plain-English reading.
- State the modus tollens rule of inference. Answer guidance: From p → q and ¬q, conclude ¬p.
Understanding
- Explain why p → q is considered true when p is false, using a concrete example. Answer guidance: Should reference the "vacuous truth" idea — a false hypothesis places no real condition on q, so the implication can't be violated. Use an example like "If pigs can fly, then 1 = 2" being classified true.
- Explain the difference between a proposition's converse and its contrapositive, and state which one is logically equivalent to the original. Answer guidance: Converse swaps p and q (q → p); contrapositive negates and swaps (¬q → ¬p). Only the contrapositive is guaranteed equivalent.
Application
- Translate the statement "Every student who studies passes the exam" into predicate logic, and negate it. Answer guidance: ∀x (Student(x) ∧ Studies(x) → Passes(x)). Negation: ∃x (Student(x) ∧ Studies(x) ∧ ¬Passes(x)) — "there is a student who studies but does not pass."
- A login system allows access if
(username is valid) AND (password is correct). Write the truth table logic for when access is denied, and identify which row(s) represent a wrong password with a valid username. Answer guidance: Access = U ∧ P; denied whenever U ∧ P is false, i.e., the T/F, F/T, and F/F rows. Valid username with wrong password is the T/F row.
Analysis
- Compare proof by contradiction and proof by contrapositive for proving "if n² is even, then n is even." Which is more natural here, and why? Answer guidance: Contrapositive ("if n is odd, then n² is odd") is more direct — assume n = 2k+1 and compute n² = 2(2k²+2k)+1, which is odd. Contradiction would assume n² even and n odd simultaneously and derive the same clash, but contrapositive avoids the extra negation step.
- A classmate argues: "If it's a weekday, the library is open. The library is open today, so it must be a weekday." Identify the fallacy and explain why the conclusion doesn't follow. Answer guidance: This is affirming the consequent (p → q, q ⊢ p), which is invalid — the library could be open on a weekend too, so "library open" does not guarantee "weekday."
FAQ
Is mathematical logic the same as "being logical" in everyday conversation? Not quite. Everyday reasoning is often loose and context-dependent, while mathematical logic requires every symbol and rule to be defined precisely, so an argument's validity can be checked mechanically rather than debated.
Why is p → q true when p is false — that feels wrong? It matches how mathematicians use "if...then" to state universal claims. If the "if" condition never applies to a case, that case can't be used to prove the statement false, so it's counted as true by default (vacuous truth).
Do I need predicate logic if I already understand propositional logic? Yes — propositional logic cannot express statements about "all" or "some" elements of a set, such as "every prime greater than two is odd." Predicate logic is required for most of real mathematics, database queries, and formal specifications.
What's the difference between a proof by contradiction and a disproof by counterexample? A counterexample disproves a universal statement by finding one case where it fails. Proof by contradiction proves a statement is true by showing that assuming it's false leads to a logical impossibility — they serve opposite purposes.
How does this connect to programming?
Boolean expressions in code (if, while, &&, ||) are propositional logic. Type systems and static analyzers use predicate logic and inference rules to prove programs behave correctly before execution.
Quick Revision
- A proposition is a statement that is definitively true or false.
- Connectives: ¬ (not), ∧ (and), ∨ (or), → (implies), ↔ (iff).
- p → q is false only when p is true and q is false — otherwise it's true.
- A tautology is always true; a contradiction is always false; a contingency depends on the inputs.
- Predicates need a quantifier (∀ or ∃) to become full propositions.
- ¬(∀x P(x)) ≡ ∃x ¬P(x), and ¬(∃x P(x)) ≡ ∀x ¬P(x).
- Modus ponens: p → q, p ⊢ q. Modus tollens: p → q, ¬q ⊢ ¬p.
- Affirming the consequent and denying the antecedent are invalid inference patterns.
- The contrapositive (¬q → ¬p) is always equivalent to p → q; the converse (q → p) generally is not.
- Induction proofs need a base case and an inductive step showing k implies k+1.
- Proof by contradiction assumes the negation of the goal and derives an impossibility.
- Mixed quantifier order matters: ∀x∃y P(x,y) is not the same as ∃y∀x P(x,y).
Related Topics
Prerequisites
- Basic set notation and operations
- Boolean algebra fundamentals
Related Topics
- Automata Theory
- Set Theory
- Digital Logic Design
Next Topics
- Proof techniques and mathematical induction (in depth)
- Set Theory and Relations
- Graph Theory