How to use this book#

This is a self-study book. It was written for a reader who may know nothing about logic: not the symbols, not the vocabulary, not the habits of mathematical writing. Everything is explained before it is used. If you already know the connectives (∧, ∨, ¬, →) and can fill in truth tables, you can skip parts of Part Zero, but you are encouraged to skim them: many "obvious" things (what exactly a proposition is, why → behaves oddly, what a variable really is) are where later confusion starts.

The book has four layers.

Suggested reading orders.

• Complete beginner: Part Zero (Z1 → Z5), then for each chapter: core sections, companion, problems.
• You know truth tables but cannot prove anything: skim Z1–Z3, read Z4 once, then Chapter 1 quickly, and slow down at Chapter 2.
• You want only the practical engine: Chapters 1, 3, 7, 8 (plus the companions 7.9 and 8.8), consulting others when needed.
• You are stuck on a symbol or word: Z4 (symbols) or Appendix D (glossary). Stuck on how to type or run something: Appendix E.

Structure of every chapter: ideas, then worked examples, then the companion, then problems.

Difficulty marks on problems:

• ★ warm-up, should take a few minutes
• ★★ standard, the core of the course
• ★★★ challenging, expect to get stuck and come back

Rules for effective study:

1. Write proofs on paper. Reading a proof and producing a proof are different skills. Only the second one is the goal.
2. Struggle first. Spend at least 15-20 minutes on a problem before opening the hints in Appendix C.
3. Justify every line. In formal proofs, each line gets a rule name and line references. In informal proofs, each sentence should follow from earlier ones for a reason you could state.
4. Redo, don't re-read. A week later, redo a proof you solved from a blank page. If you can't, you memorized it instead of understanding it.
5. Keep an error log. Whenever you make a mistake (wrong quantifier order, illegal ∀-introduction, circular reasoning), write it down. Your mistakes are very repetitive, and the log makes them visible.
6. Build the project in parallel (Chapter 8). Implementing a rule is the strictest test of whether you understood it.
7. Use the quick-checks. Each companion ends with a quick-check with answers. Cover the answer, write yours, then compare.

Reading conventions in this book.

• Code and formulas typed on a keyboard appear in monospace; mathematical formulas are usually in ordinary text with symbols such as ∀x (P(x) → Q(x)).
• Italics introduce a term at its definition. Bold marks something you must not forget.
• "Section 3.5" means the numbered section in the core text; "3.8.5" means subsection 5 of the Chapter 3 companion (section 3.8).
• Where a statement was checked by computer (truth tables, the SAT solver, Z3, the Chapter 8 test-suite), the text says so.

Companion files. The Chapter 8 starter kit is shipped as two files next to this document: logic_engine_starter.py (the engine) and test_starter.py (its 2,520 checks). Section 8.8 explains how to use them.

Suggested pace: about 12 weeks at 6-8 hours per week for the core text (Chapter 9, Section 9.3); about 16 weeks if you start from zero and read all of Part Zero and the companions (Section 9.4).

PART ZERO. Starting from absolute zero ↑ Top#

This part assumes nothing. If a word, a symbol, or a habit of mathematical writing appears later in the course, it is explained here first. Read it in order the first time. Later you can use it as a reference: Chapter Z4 is a complete atlas of symbols, and Appendix D is an A-Z glossary.

Chapter Z1. What logic is, and what we are trying to do ↑ Top#

Z1.1 Reasoning, statements and arguments#

Every day you move from things you accept to new things you accept:

"The shop closes at 6. It is now 6:30. So the shop is closed."

You did not look at the shop. You reasoned. Logic is the study of which such moves are correct, and why.

To study reasoning precisely we need names for its parts.

A statement (also called a proposition or declarative sentence) is a sentence that claims something is the case, so that it makes sense to ask "is it true or false?". Examples:

A statement has exactly one truth value: true or false. (In classical logic, which is the main subject of this course, there is no third option and no "both".)

Things that are not statements:

An argument is a collection of statements in which some, the premises, are offered as support for another, the conclusion. Words that often signal a conclusion: therefore, thus, hence, so, consequently, it follows that. Words that often signal a premise: because, since, given that, for, as.

Premise 1: All humans are mortal. Premise 2: Socrates is a human. Conclusion: Therefore, Socrates is mortal.

Z1.2 Validity: the central idea#

The most important concept in all of logic:

An argument is valid when it is impossible for all the premises to be true and the conclusion false at the same time.

Equivalently: if the premises were all true, the conclusion would have to be true. Validity is about the connection between premises and conclusion, not about whether the premises are actually true.

Study these four arguments carefully.

Argument 2 is valid even though everything in it is false. The shape is perfect: if all dogs really were reptiles, and Rex really were a dog, then Rex would have to be a reptile. Argument 3 is invalid even though its premises and conclusion might all be true: the premises do not force the conclusion (Rex could be a cat, which is also a mammal).

Soundness of an argument (a different, everyday word that logicians also use): an argument is sound if it is valid and all its premises are true. A sound argument guarantees a true conclusion. Argument 1 is sound. Argument 2 is valid but unsound.

Warning on vocabulary. In everyday speech "valid" is used loosely ("that is a valid point"). In logic it has only the meaning above, and it applies to arguments, never to single statements. Single statements are called true/false (in one situation) or logically true/tautologies (in all situations). We will make this precise in Chapters 1 and 3. Also, in Chapter 6, "soundness" gets a second, technical meaning for proof systems.

Z1.3 Form versus content#

Why is argument 1 valid? Look at what happens when we erase the specific words and keep only the pattern:

All A are B.
x is an A.
Therefore x is a B.

Any argument with this shape is valid, whatever A, B, and x stand for:

• A = "birds", B = "animals", x = "Tweety": valid.
• A = "prime numbers greater than 2", B = "odd numbers", x = "17": valid.

Logic is the study of forms (patterns, schemas) of arguments. We replace words by letters (variables) so that the pattern is what remains. This is the reason logic uses symbols at all: not to look scary, but to isolate the pattern from the subject matter. A form is valid when every argument of that form is valid.

Invalid form (affirming the consequent):

If A then B.
B.
Therefore A.

Counterexample: "If it is raining, the street is wet. The street is wet. Therefore it is raining." (Perhaps a street cleaner passed by.)

A counterexample to an argument form is an argument of that exact form with true premises and a false conclusion. One counterexample proves invalidity. This idea (find a world where premises are true and conclusion is false) will return as the countermodel in Chapter 3.

Z1.4 Kinds of reasoning#

Mathematical logic is about deduction. (Do not confuse mathematical induction, a deductive proof technique in Chapter 5, with inductive reasoning.)

Z1.5 Why make logic formal?#

Natural language is wonderful but ambiguous.

To reason with total certainty we need a language where each sentence has exactly one meaning. That is a formal language: a collection of symbols, together with exact rules for which strings of symbols count as legitimate sentences (syntax), what each sentence means (semantics), and how to derive sentences from others using mechanical rules (proof theory, or deduction).

Advantages of formalization:

1. No ambiguity. One formula, one meaning.
2. Checkability. A proof becomes a finite object that a program can verify, step by step, with no understanding at all. (This is how proof assistants such as Lean work.)
3. Generality. The same rules apply to arithmetic, geometry, software specifications, legal contracts, circuit design.
4. Theorems about reasoning itself. Once reasoning is a mathematical object, we can prove things about it: that it is correct, that it is complete, that some questions cannot be settled by any algorithm (Chapter 6).

Z1.6 The three pillars#

Every logical system we study has three components. Keep this triangle in mind for the entire course:

                SYNTAX
        (symbols, formulas, rules
         for what is well-formed)
               /        \
              /          \
     SEMANTICS ────────── PROOF THEORY
   (meaning: truth,       (derivations:
    models, ⊨)             rules, proofs, ⊢)

The deepest results (soundness and completeness, Chapter 6) say that the last two pillars agree.

Z1.7 A map of the field#

Z1.8 A very short history#

Z1.9 Try it#

Q1. Which of these are statements? (a) "7 is prime." (b) "Is 7 prime?" (c) "x + 1 = 8." (d) "Every planet has a moon." (e) "Stop!" Q2. Is this argument valid? "If I win the lottery, I'll be rich. I am rich. Therefore I won the lottery." Why or why not? Q3. Give an example of a valid but unsound argument. Q4. What is the form of: "If the battery is dead then the car won't start. The battery is dead. So the car won't start."?

Answers. A1. (a) and (d) are statements ((d) is false but still a statement). (b) is a question, (e) a command, (c) is an open sentence (depends on x). A2. Invalid (affirming the consequent): one can be rich for other reasons (inheritance). A3. "All fish can fly. A shark is a fish. So a shark can fly." Valid form, false premise. A4. "If A then B. A. Therefore B." (modus ponens, valid).

Chapter Z2. The language of mathematics ↑ Top#

Mathematical writing has its own grammar and vocabulary. Misreading it is the most common source of mistakes for beginners. This chapter is a field guide.

Z2.1 Kinds of mathematical text#

End-of-proof marks: ∎ (the "tombstone" or Halmos symbol), □, ■, Q.E.D. (Latin quod erat demonstrandum, "which was to be shown"), sometimes // or "as required". All mean "the proof is complete".

Defined terms vs. defining symbols. When a definition introduces notation, mathematicians use one of: :=, ≔, =:, ≝, ≜, def=, :⇔ (for statements), or just words ("we write ... for ..."). The colon sits on the side of the thing being defined: A := B defines A to be B.

A subtle but crucial convention: definitions are "if and only if", even when written with "if". "An integer is even if it is divisible by 2." really means even exactly when divisible by 2. It is a definition, so both directions hold. (Theorems written with "if" are one-directional. Context tells you which you are reading.)

Z2.2 A dictionary of mathematical English#

Six traps that catch every beginner#

1. "Or" is inclusive. "n is even or n > 10" is true for n = 12 (both). Everyday "or" is often exclusive ("soup or salad"), so you must override your habit.

2. "Some" means "at least one" (possibly all). "Some primes are odd" is true. It does not suggest that some primes are not odd.

3. "A" can mean "any" or "some". "A prime greater than 2 is odd" means every prime greater than 2 is odd. "A prime is bigger than 100" means some prime. Always decide whether a hidden "for all" or "there exists" is present.

4. "Any" is slippery. "If any student fails, the class is delayed" (= some: if at least one fails). "Any student can answer this" (= every). Replace "any" by "every" or "some" explicitly when writing mathematics.

5. Order of quantifiers. "For every person there is someone they love" is not the same as "there is someone whom every person loves". Compare: ∀x ∃y L(x, y) and ∃y ∀x L(x, y). In ordinary mathematical prose the order of phrases is the order of quantifiers: read left to right.

6. "If...then" is not about causes. "If 2 + 2 = 5 then the moon is cheese" is true in logic. It is a claim about truth values only (we will explain why in Chapter 1.3).

Z2.3 The common shapes of mathematical statements#

Almost every theorem fits one of these shapes. Recognizing the shape tells you what the proof must look like (this becomes precise in Chapter 5).

How to negate each shape (essential skill)#

Examples:

• Negate "Every student passed." → "At least one student did not pass." (Not "No student passed"!)
• Negate "Some birds can't fly." → "Every bird can fly."
• Negate "If it rains, I stay home." → "It rains and I do not stay home."

Z2.4 Anatomy of a proof (a first complete example, narrated)#

We prove this very simple statement and mark every move.

Theorem. If n is an even integer, then n + 1 is odd.

Definitions used. An integer n is even if there exists an integer k with n = 2k. An integer n is odd if there exists an integer k with n = 2k + 1.

The pattern identify the shape, unpack definitions, calculate, repack definitions is the heart of most introductory proofs. In Chapter 5 we make each move precise as a rule of logic.

Z2.5 How to read mathematics#

1. Slowly, with a pencil. A page of mathematics can need an hour.
2. Read definitions twice, and write examples. If a definition says "n is even if n = 2k", test n = 6 (k = 3), n = 7 (impossible), n = 0 (k = 0).
3. When you meet a symbol you do not know, look it up (Chapter Z4) before continuing.
4. For a theorem, find the hypotheses and the conclusion. Rewrite it as "Assume ... Then ...".
5. Test with an example, then a non-example, then see where the proof uses each hypothesis. A proof that never uses a hypothesis is suspicious (or the hypothesis is redundant).
6. Rewrite the proof in your own words from memory.

Z2.6 A note on notation habits#

• Variables and letters. Mathematicians use letters as placeholders. Typical conventions: n, m, k, i, j for integers; x, y, z for real numbers or "any object"; a, b, c for fixed constants; ε, δ for small positive numbers; f, g, h for functions; A, B, C for sets; P, Q, R for statements or predicates. These are only habits, not rules. Always check the author's declaration ("Let n be an integer...").
• Subscripts distinguish related objects: x₁, x₂, ..., xₙ.
• Primes and bars ( x′, x″, x̄ ) distinguish related objects too; context decides whether x̄ is a complement, a conjugate, or a mean.
• Parentheses group, but also appear in function application f(x) and in tuples (a, b). Context decides.
• A comma between conditions usually means "and": "x > 0, y > 0" means x > 0 and y > 0.
• Equality signs in a chain a = b = c mean a = b and b = c. A chain of inequalities a ≤ b < c means a ≤ b and b < c, so a < c.

Z2.7 Try it#

Q1. Rewrite using "if...then": (a) "n is divisible by 6 only if n is even." (b) "A number is positive if it is greater than 5." (c) "Passing the exam is necessary for graduating." Q2. Negate: (a) "All dogs bark." (b) "There is a number which is both even and prime greater than 2." (c) "If it is Monday then the shop is open." Q3. Is "If 2 is odd then 3 is even" true or false? Explain. Q4. What does "for every real x there is a real y with y > x" say? What does "there is a real y such that for every real x, y > x" say? Are both true? Q5. What is the contrapositive of "If n is prime and n > 2 then n is odd"?

Answers. A1. (a) If n is divisible by 6 then n is even. (b) If a number is greater than 5 then it is positive. (c) If you graduate then you passed the exam. A2. (a) Some dog does not bark. (b) Every number that is even is either not prime or is not greater than 2 (equivalently: every even prime is ≤ 2). (c) It is Monday and the shop is not open. A3. True: the "if" part (2 is odd) is false, so the conditional is vacuously true (Chapter 1.3). A4. The first says there is no largest real number (true). The second says there is a largest real number (false). So order of quantifiers changes the meaning. A5. If n is not odd (i.e., n is even) then n is not prime or n ≤ 2. (Negating a conjunction: ¬(n prime ∧ n > 2) = n not prime ∨ n ≤ 2.)

Chapter Z3. The mathematics you need first: sets, numbers, functions, relations, strings, trees ↑ Top#

Logic talks about things, collections of things, and connections between things. Mathematics gives us standard words for these. You need them for predicate logic (Chapter 3) and for every proof in Chapter 5. Everything below is introduced from scratch.

Z3.1 Sets#

Z3.1.1 What a set is#

A set is a collection of distinct objects, called its elements or members. What matters is which objects are in it. Not order, not repetition.

Z3.1.2 Ways to describe a set#

1. Listing (roster notation): {1, 2, 3}, {red, green, blue}. Order and repetition do not matter: {1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3}.

2. Dots for pattern: {1, 2, 3, ..., 100}, {2, 4, 6, ...} (infinite). Only use when the pattern is obvious.

3. Set-builder notation: { x | P(x) } or { x : P(x) }, read "the set of all x such that P(x)". Examples:

Note: the vertical bar | here means "such that". Elsewhere | means "divides" (3 | 12) or absolute value (|x|). Context disambiguates, which is why many authors prefer the colon in set-builder.

4. By a rule or definition ("the set of all prime numbers").

Z3.1.3 Special sets#

Z3.1.4 Equality, subsets, supersets#

Two sets are equal when they have exactly the same elements (extensionality):

A = B iff for every x: x ∈ A ↔ x ∈ B.

Subset. A ⊆ B ("A is a subset of B", "A is contained in B") means every element of A is also an element of B:

A ⊆ B iff ∀x (x ∈ A → x ∈ B).

Facts: ∅ ⊆ A for every set A (vacuously true: there is no element of ∅ that could fail to be in A). A ⊆ A. If A ⊆ B and B ⊆ C then A ⊆ C. A = B iff A ⊆ B and B ⊆ A (this is how equality of sets is proved: show both inclusions).

Z3.1.5 Operations on sets#

Let A and B be sets, inside a universe U.

The correspondence with logic is exact (and worth memorizing):

Because of this, every logical law has a set-theoretic twin: De Morgan's law ¬(P ∧ Q) ≡ ¬P ∨ ¬Q becomes (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

Example. A = {1, 2, 3, 4}, B = {3, 4, 5}, U = {1, 2, 3, 4, 5, 6}.

• A ∪ B = {1, 2, 3, 4, 5}
• A ∩ B = {3, 4}
• A ∖ B = {1, 2}; B ∖ A = {5}
• A △ B = {1, 2, 5}
• Aᶜ = {5, 6}
• |A| = 4; 𝒫({1, 2}) = {∅, {1}, {2}, {1, 2}}, which has 2² = 4 elements. In general |𝒫(A)| = 2^|A|.

Z3.1.6 Venn diagrams#

A Venn diagram draws sets as overlapping regions inside a rectangle (the universe). Text sketch for two sets:

 ┌──────────────────────────────────────┐
 │ U                                    │
 │      ╭──────────╮╭──────────╮        │
 │     ╱   A only   ╳  A ∩ B   ╲ B only│
 │     ╲            ╳           ╱       │
 │      ╰──────────╯╰──────────╯        │
 │                 outside both = (A ∪ B)ᶜ│
 └──────────────────────────────────────┘

The four regions are exactly the four rows of a two-variable truth table (A and B, A only, B only, neither). That is why Venn diagrams can verify propositional laws.

Z3.1.7 Ordered pairs, tuples, Cartesian products#

A set ignores order. When order matters we use an ordered pair (a, b): it satisfies (a, b) = (c, d) iff a = c and b = d. So (1, 2) ≠ (2, 1) but {1, 2} = {2, 1}. (Formally one can define (a, b) as the set {{a}, {a, b}}, but you only need the equality property.)

An n-tuple (a₁, a₂, ..., aₙ) generalizes: ordered, repetition allowed. A × B is the set of all pairs with first entry from A and second from B. Aⁿ is the set of n-tuples of elements of A: A² = A × A, ℝ³ is 3-dimensional space. If |A| = m and |B| = n then |A × B| = m·n.

Z3.1.8 Indexed families, big union, big intersection#

If for each i in an index set I we have a set Aᵢ:

• ⋃ᵢ∈I Aᵢ = { x | ∃i ∈ I, x ∈ Aᵢ } (x lies in at least one Aᵢ)
• ⋂ᵢ∈I Aᵢ = { x | ∀i ∈ I, x ∈ Aᵢ } (x lies in every Aᵢ)

Notice the pattern: big union is an existential statement, big intersection is a universal one. Same as ∃ and ∀.

Z3.1.9 Partitions#

A partition of a set S is a family of non-empty, pairwise disjoint sets whose union is S. Example: the even and the odd integers partition ℤ.

Z3.1.10 Intervals of real numbers#

Warning: (a, b) also denotes an ordered pair. Context decides.

Z3.1.11 A caution: not every collection is a set#

If we allowed "the set of all sets that are not members of themselves", we would get Russell's paradox (it would belong to itself exactly when it does not). Modern set theory (ZFC) avoids this by restricting how sets can be formed. You will meet this again in Chapter 6.

Z3.2 Numbers and arithmetic notation#

Z3.2.1 The standard number systems#

Inclusions: ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ ⊆ ℂ.

Z3.2.2 Order and comparison#

Z3.2.3 Operations and common functions#

The sign ≡ is overloaded: in logic it means "logically equivalent"; in number theory "congruent modulo n"; in some books "is defined as" or "identically equal". Always read it in context.

Z3.2.4 Basic number-theory vocabulary#

Note: 1 is not prime; 0 is even; negative integers can be even or odd (−4 = 2·(−2)).

Z3.3 Functions#

Z3.3.1 Definition#

A function f from a set A to a set B, written f : A → B, assigns to each element x of A exactly one element f(x) of B.

Example. f : ℤ → ℤ, f(x) = x². Domain ℤ, codomain ℤ, range {0, 1, 4, 9, ...}. Two things to note: every input has exactly one output (so f(2) = 4 only), but different inputs can share an output (f(2) = f(−2) = 4).

Functions with several inputs: f : A × B → C, written f(a, b). Equivalent: a function of an n-tuple. We say f has arity n. A constant is a function of arity 0 (no inputs): it just names an element.

Partial functions are defined only on part of the domain (division is a partial function on ℝ, undefined at 0). "Function" without qualification means total: defined everywhere on the domain.

Predicates as functions: a statement-valued function P : A → {true, false} is a predicate. For instance Even(n) is true exactly when n is even. The set { x ∈ A | P(x) } is the extension of P (the set of things the predicate holds of).

Z3.3.2 Composition, identity, inverse#

Caution: f⁻¹ can mean the inverse function or the preimage operation, and f⁻¹(x) is not 1/f(x).

Z3.3.3 Three key properties#

Examples:

• f : ℤ → ℤ, f(x) = x²: neither (f(2) = f(−2); −1 is never hit).
• f : ℤ → ℤ, f(x) = x + 1: bijective (inverse x − 1).
• f : ℕ → ℤ, f(n) = n: injective, not surjective.
• f : ℝ → ℝ, f(x) = x³: bijective.

Z3.3.4 Counting with functions: cardinality#

Two sets have the same cardinality if there is a bijection between them. A set is finite if it has the same cardinality as {1, ..., n} for some n; otherwise infinite. A set is countably infinite if it has the same cardinality as ℕ ("it can be listed in a sequence"); ℤ and ℚ are countably infinite. Uncountable sets (like ℝ, and 𝒫(ℕ)) are infinite sets too big to list; Cantor proved this with a diagonal argument (Chapter 5.12). The cardinality of ℕ is written ℵ₀ ("aleph-null").

Z3.4 Relations#

Z3.4.1 Definition#

A binary relation R from A to B is a subset of A × B. If (a, b) ∈ R we say "a is related to b by R" and write a R b, R(a, b), or (a, b) ∈ R.

Examples (relations on a set, meaning A = B):

• < on ℤ: 3 < 5.
• = on any set.
• "divides" on ℕ: 3 | 12.
• "is a parent of" on a set of people.
• "is connected by an edge to" on the vertices of a graph.

An n-ary relation on A is a subset of Aⁿ: e.g., the ternary relation "x is between y and z".

Relations are the semantics of predicates. The predicate "L(x, y): x loves y" corresponds to the set of pairs { (x, y) | x loves y }.

Z3.4.2 Properties of a relation R on a set A#

Examples: ≤ on ℤ is reflexive, antisymmetric, transitive, total. < is irreflexive, asymmetric, transitive, connected. "Is a sibling of" is symmetric, not reflexive (usually), not transitive in general. = is reflexive, symmetric, transitive.

Z3.4.3 Two especially important kinds of relation#

Equivalence relation: reflexive + symmetric + transitive. It formalizes "being the same in some respect". Example: congruence modulo n on ℤ ("a and b have the same remainder"). An equivalence relation splits the set into equivalence classes [a] = { x | x R a }, and these classes form a partition of the set (and every partition comes from an equivalence relation).

Partial order: reflexive + antisymmetric + transitive (like ≤ or ⊆). A strict partial order: irreflexive + transitive (like < or ⊂). A total (linear) order is a partial order in which every two elements are comparable. A well-order is a total order in which every non-empty subset has a least element (ℕ with ≤ is one; ℤ and ℝ are not, because they have no least element). Partial orders are drawn as Hasse diagrams, with a line going upward from x to y whenever x < y with nothing in between.

Z3.4.4 Graphs as relations (we will use them as examples)#

A directed graph is a set V of vertices (nodes) and a relation E ⊆ V × V of edges. Drawing: dots and arrows. An undirected graph has a symmetric E. A path is a sequence of vertices with an edge between consecutive ones. Graphs are the easiest nontrivial structures for practicing predicate logic: the sentence ∀x ∃y E(x, y) says "every vertex has an outgoing edge".

Z3.5 Sequences, strings, alphabets, languages#

A sequence is an ordered list a₁, a₂, ..., aₙ (finite) or a₁, a₂, ... (infinite). Same as a function from {1, ..., n} or ℕ.

An alphabet Σ is a finite non-empty set of symbols. A string (or word) over Σ is a finite sequence of symbols. Examples over Σ = {a, b}: a, abba, and the empty string (written ε or λ or ""), which has length 0. |w| is the length of w. Concatenation uv (or u · v) puts strings end to end: ab · ba = abba. Σ* is the set of all finite strings over Σ. A formal language is any subset of Σ*.

Why this matters for logic: a formula is a string of symbols from the logical alphabet. "Is this string a well-formed formula?" is a question about membership in a formal language, settled by exact formation rules (Chapter 1.1 and 3.2). The statement "(P → Q" is a string but not a formula (unbalanced bracket).

Z3.6 Trees and recursive (inductive) definitions#

Z3.6.1 Trees#

A tree is a graph with a designated root where every other node is reached from the root by exactly one path. Vocabulary: node, edge, parent / child, leaf (no children), depth (distance from the root), height (maximum depth). Trees are drawn upside-down, the root at the top:

          →             ← root (the main connective)
         / \
        ∧   R
       / \
      P   Q

This is the parse tree (syntax tree) of (P ∧ Q) → R. Every formula has such a tree. Reading a formula means reconstructing its tree.

Z3.6.2 Inductive definitions#

Many objects in logic are defined inductively: by stating (1) some base objects, (2) construction rules that build new objects from old ones, and (3) a closure clause: "nothing else is an object of this kind". Example, the set of propositional formulas over atoms p, q, r:

1. (Base) p, q, r are formulas.
2. (Rule) If A is a formula then ¬A is a formula.
3. (Rule) If A and B are formulas then (A ∧ B) is a formula, and likewise (A ∨ B), (A → B), (A ↔ B).
4. (Closure) Nothing else is a formula.

Two powerful consequences:

• Definition by recursion. To define a function on formulas it is enough to say what it does on the base cases and how to compute it for ¬A, (A ∧ B), ... from the values for A and B. Example: the number of connectives c: c(p) = 0; c(¬A) = c(A) + 1; c((A ∧ B)) = c(A) + c(B) + 1.
• Proof by induction (structural). To prove that every formula has some property, prove it for the base cases, and show that the construction rules preserve it (Chapter 5.10).

Unique readability. Each formula can be built in only one way, so its parse tree is unique. That is why the parentheses in the definition matter; without them P ∨ Q ∧ R would be ambiguous.

Z3.6.3 The same idea for numbers#

The natural numbers are inductively defined: 0 is a natural number; if n is, so is its successor n + 1; nothing else is. That is the source of mathematical induction (Chapter 5.8).

Z3.7 Try it#

Q1. Let A = {2, 4, 6}, B = {4, 6, 8, 10}, U = {1, ..., 10}. Compute A ∪ B, A ∩ B, A ∖ B, Aᶜ, |𝒫(A)|, and the number of elements of A × B. Q2. Is ∅ ⊆ {1, 2}? Is ∅ ∈ {1, 2}? Is ∅ ∈ {∅}? Q3. For f : ℤ → ℤ, f(n) = 2n: is f injective? surjective? What is its range? Q4. For each relation on ℤ decide reflexive / symmetric / transitive: (a) a R b iff a ≤ b; (b) a R b iff a − b is even; (c) a R b iff a ≠ b. Q5. Which of these is a well-formed formula built by Z3.6.2: (a) (P ∧ Q) (b) P ∧ Q (c) ¬¬P (d) (P ∧ ¬)?

Answers. A1. A ∪ B = {2, 4, 6, 8, 10}; A ∩ B = {4, 6}; A ∖ B = {2}; Aᶜ = {1, 3, 5, 7, 8, 9, 10}; |𝒫(A)| = 2³ = 8; |A × B| = 3·4 = 12. A2. ∅ ⊆ {1, 2}: yes (empty set is a subset of every set). ∅ ∈ {1, 2}: no (the elements are 1 and 2). ∅ ∈ {∅}: yes (the only element of {∅} is ∅). A3. Injective: yes (2a = 2b ⇒ a = b). Surjective: no (1 is not hit). Range: the even integers. A4. (a) reflexive, transitive, not symmetric. (b) all three: it is an equivalence relation (same parity). (c) symmetric only: not reflexive (a = a fails), not transitive (1 ≠ 2, 2 ≠ 1, but 1 = 1). A5. (a) yes; (b) no under the strict grammar of Z3.6.2 (binary connectives need parentheses; many books allow dropping the outermost pair, which is why we say "under the strict grammar"); (c) yes: ¬¬P is ¬ applied to the formula ¬P; (d) no: ¬ needs a formula after it.

Chapter Z4. The Symbol Atlas: every sign you will meet ↑ Top#

Logic is written in symbols. The same idea is often written in several different ways by different authors, and the same symbol sometimes means different things in different books. This chapter is the dictionary. Use it in three ways:

1. First reading: skim to see the symbols once.
2. Whenever you meet an unknown sign anywhere in the course: look it up here.
3. When reading other books: use the "variants" columns and the tables in Z4.11 (ambiguities) and Z5 (dialects).

Columns: Symbol; Name; Read aloud; Meaning; Variants (other signs for the same idea); LaTeX (how to typeset it); Unicode (code point, so you can type or copy it).

Z4.1 The core connectives (propositional logic)#

Z4.1.1 Where the variants come from#

• ¬ vs ~: ~ is the ASCII tilde, the usual keyboard substitute for ¬. Frege used a small vertical stroke; Russell and Whitehead wrote ~p; Heyting wrote ¬p.
• ∧ vs & vs ·: Boole (and Boolean algebra, electrical engineering) used multiplication: AB or A·B. Principia used the dot. Hilbert wrote &. Modern logic uses ∧, which looks like the "intersection" ∩ turned sharp.
• ∨ vs +: from Latin vel ("or"). Boolean algebra writes A + B. In Boolean algebra 1 + 1 = 1, since "true or true" is true.
• → vs ⊃ vs ⇒: Peano and Russell introduced ⊃ (a reversed "C" for "consequence"). Modern logic prefers →. In many books ⇒ is the metalanguage "implies" between statements about statements (see Z4.5), while → is the object-language connective.
• ↔ vs ≡ vs ⇔: similarly. ≡ in older books is the biconditional connective; in modern books it often means "logically equivalent" (a metalanguage claim), and ⇔ often means "iff" in mathematical prose.

Z4.1.2 Names of the parts#

Z4.2 Quantifiers, binders, and related symbols (predicate logic)#

All binders do the same job: they introduce a bound variable whose name does not matter (∀x P(x) and ∀y P(y) say the same). See Chapter 3.3.

Quantifier scope conventions differ. After ∀x, some authors apply the quantifier only to the next immediate formula (as with ¬); others extend it as far to the right as possible. Always parenthesize: ∀x (P(x) → Q(x)).

Z4.3 Symbols of consequence, proof and metalanguage#

These symbols are not part of the formulas. They are used to talk about formulas (metalanguage).

Z4.3.1 Reading the notations out loud#

• A ⊢ B — "A proves B".
• A, B ⊢ C — "from A and B one can prove C" (comma = both premises).
• ⊢ A → A — "A implies A is a theorem" (it can be proved with no premises).
• Γ ⊨ A — "every model of Γ makes A true".
• A₁, ..., Aₙ ⊢ B — an argument or sequent with n premises and a conclusion.

Z4.3.2 ⊢ versus ⊨ versus → versus ⇒ (the confusion table)#

Z4.4 The many signs of "equals", "defined as", and "equivalent"#

Z4.5 Sets, functions, relations#

(Defined in Z3. This is the compact atlas.)

Z4.6 Arithmetic and number-theory symbols#

Z4.7 Brackets, punctuation and layout#

Substitution notation varies. The following all mean "A with t substituted for the free occurrences of x": A[t/x], A(t/x), A_x[t], A[x := t], A[x ↦ t], A{x ↦ t}, {x/t}A, A(t) (if A has been written as A(x)). In this course we use A[t/x].

Z4.8 Letters: the conventional use of Latin and Greek symbols#

These are habits, not laws. Always trust the author's declaration.

Z4.9 Symbols with multiple meanings: the ambiguity table#

This is where most beginner confusion hides.

How to survive this: at the start of any text, look for a "Notation" section or the first definitions. When in doubt, ask yourself which kind of object each side of the sign is: formulas? sets? numbers? statements about formulas?

Z4.10 Symbols of other logics (preview)#

You will not need these for the core course, but you will meet them next.

Z4.11 Reading formulas aloud#

The skill of reading a formula in good English is the best test that you understand it.

Try it: decode and encode#

Q1. Read aloud (in plain English): (a) ¬∃x (P(x) ∧ ¬Q(x)) (b) ∀x ∀y (x < y → ∃z (x < z ∧ z < y)) (c) A, B ⊢ A ∧ B. Q2. Write in symbols: (a) "No S is P." (b) "If it rains or snows, the game is cancelled." (c) "Every number has a successor." Q3. Which sign: (i) "the empty set", (ii) "therefore", (iii) "is not a subset of", (iv) "is provable from", (v) "is true in every model of". Q4. What is the difference between A → B, A ⇒ B and A ⊢ B? Q5. Rewrite P ⊃ (Q ≡ R) (older style) in modern symbols.

Answers. A1. (a) "It is not the case that there is something that is P and not Q" (= every P is Q). (b) "For all x and y, if x is less than y then there is a z strictly between them." (c) "From A and B one can prove A and B." A2. (a) ∀x (S(x) → ¬P(x)) or ¬∃x (S(x) ∧ P(x)). (b) (R ∨ S) → C. (c) ∀n ∃m (m = n + 1) or ∀n ∃m Succ(n, m). A3. (i) ∅, (ii) ∴, (iii) ⊄ (or ⊈), (iv) ⊢, (v) ⊨. A4. A → B is a formula (object language). A ⇒ B usually means "if A [is true / holds] then B" said about statements (metalanguage). A ⊢ B says that a proof of B from A exists. A5. P → (Q ↔ R).

Chapter Z5. Dialects and formats: the same logic in many costumes ↑ Top#

Logic has one core and many costumes. Two things vary from book to book and tool to tool:

1. Notation dialects: how formulas are written (which symbols, which precedence, prefix or infix).
2. Proof formats: how proofs are laid out (a table, a tree, a boxed list, a one-sided tableau, a set of clauses...).

Nothing in this chapter adds new logical power. Everything here is a different way to write down the same truths. The skill you want is fluent translation: when a book or tool uses a different costume, you recognize it and mentally convert.

Z5.1 Notation dialects for formulas#

Z5.1.1 Precedence and associativity (how to drop brackets)#

A formula like P ∨ Q ∧ R is ambiguous unless we agree on binding strength. The most common convention:

So under this convention ¬P ∧ Q → R ∨ S means ((¬P) ∧ Q) → (R ∨ S), and P → Q → R means P → (Q → R).

Quantifiers are the troublemakers. Books disagree: some let ∀x bind only the next formula (like ¬), so ∀x P(x) → Q(x) means (∀x P(x)) → Q(x); others let the scope extend as far right as possible, so the same string means ∀x (P(x) → Q(x)). This course uses the second convention (Section 3.2), but you should never rely on it: always parenthesize the body of a quantifier.

Warnings.

• Some books give ∧ and ∨ equal strength, or make → left-associative. Programming languages differ again (in C, && binds tighter than ||, as here, but there is no implication operator).
• ∧ and ∨ are associative, so P ∧ Q ∧ R is harmless. But → is not associative: (P → Q) → R and P → (Q → R) are different formulas.
• Rule for this course: whenever in doubt, add brackets. Brackets are free.

Z5.1.2 Infix, prefix, postfix#

Prefix and postfix need no brackets and no precedence rules: the structure is determined by the arity of each symbol.

Z5.1.3 Łukasiewicz (Polish) notation#

Jan Łukasiewicz (1920s) used capital letters as prefix operators:

Atoms are lowercase: p, q, r.

How to read Polish notation: scan left to right; every operator "demands" its arguments: C wants two formulas. CKpqr: C takes (1) Kpq and (2) r. K takes p and q.

Z5.1.4 Principia Mathematica (dot notation)#

Whitehead and Russell avoided brackets by using dots whose number indicates the strength of the grouping.

You rarely meet dots today, but ⊃, ≡, ~ and (x) survive in philosophy texts and older papers.

Z5.1.5 Boolean-algebra / engineering dialect#

Laws look like arithmetic but are not identical: in Boolean algebra P + P = P and P + 1 = 1.

Z5.1.6 ASCII and keyboard dialects#

Warning on programming languages. In programs && and || are usually short-circuit (they may skip evaluating the second argument), which has no counterpart in logic; and P -> Q is often not an implication at all (in C, -> is field access; in Haskell, -> is the function type). Programming "if" is control flow, not the logical conditional.

Z5.1.7 Theorem-prover input languages (a preview of Appendix E)#

Conventions: in TPTP, variables start with an uppercase letter, constants and predicates with lowercase; in Prover9, variables are the lowercase letters u-z by default. We study these in detail in Appendix E and Chapter 8.

Z5.1.8 Typesetting dialects: LaTeX vs Unicode vs plain text#

For notes, Unicode is easiest (copy from Z4). For papers, LaTeX. For machines, ASCII or the tool's own syntax.

Z5.2 Proof formats: an overview#

A proof format (or proof system, calculus) fixes the rules of the game: what a legal proof line looks like and how lines may be combined. The main families:

We now show one running example in all of them.

Running example (hypothetical syllogism). From P → Q and Q → R, conclude P → R. In sequent notation: P → Q, Q → R ⊢ P → R.

Z5.3 The running example in every format#

Format 1. Truth table (semantic)#

We want to show {P → Q, Q → R} ⊨ P → R: every row making both premises true makes the conclusion true. There are 2³ = 8 rows.

Every row that makes both premises true makes the conclusion true. So the entailment holds. This shows ⊨, not ⊢ (it is not a derivation), and it does not scale to predicate logic (infinitely many structures).

Format 2. Informal mathematical proof#

Claim. If P → Q and Q → R, then P → R. Proof. Assume P → Q and Q → R. To show P → R, assume P. By P → Q and P we get Q. By Q → R and Q we get R. Since assuming P led to R, we conclude P → R. ∎

This is the style of real mathematics. Every step is secretly an instance of a formal rule (modus ponens, then implication introduction).

Format 3. Hilbert-style (axiomatic)#

Axiom schemes (for the → fragment):

• K: A → (B → A)
• S: (A → (B → C)) → ((A → B) → (A → C))

Single rule: modus ponens (MP): from A and A → B, infer B.

Notice how unnatural this is: no assumptions can be made "temporarily". Hilbert systems are short to specify (good for proving metatheorems) but painful to use. The Deduction Theorem (Chapter 6) repairs this: it proves that if Γ, A ⊢ B then Γ ⊢ A → B, which is exactly what natural deduction builds in.

Format 4. Natural deduction, Gentzen tree style#

Each inference is a horizontal line; premises above, conclusion below; a bracketed [P]¹ is a discharged assumption and the superscript names the rule that discharges it.

             [P]¹   P → Q
             ──────────── →E
                  Q            Q → R
                  ─────────────────── →E
                            R
                  ─────────────────── →I¹
                          P → R

Read bottom-up: to get P → R, use →I discharging assumption 1 (P); this needs R; get R by →E from Q and Q → R; get Q by →E from P and P → Q. Premises P → Q and Q → R remain open (undischarged) hypotheses of the whole proof.

Format 5. Natural deduction, Fitch style (used in this course)#

1 │ P → Q                 premise
2 │ Q → R                 premise
3 │ ┌─ P                  assumption (for →I)
4 │ │  Q                  →E 1, 3
5 │ │  R                  →E 2, 4
6 │ └───
  │ P → R                 →I 3–5

The indented box (lines 3-5) is a subproof: inside it we may use P, but nothing derived inside escapes the box except through the closing rule (→I).

Format 6. Natural deduction, Lemmon style#

Each line carries the set of premise line numbers it depends on (left), a line number, the formula, and its justification.

{1}       (1)  P → Q    Premise
{2}       (2)  Q → R    Premise
{3}       (3)  P        Assumption
{1,3}     (4)  Q        1,3 →E (modus ponens)
{1,2,3}   (5)  R        2,4 →E
{1,2}     (6)  P → R    3,5 →I (conditional proof; discharges 3)

Line 6 depends on lines 1 and 2 only: the dependency on line 3 has been removed (discharged).

Format 7. Sequent calculus (Gentzen's LK, two-sided)#

A sequent Γ ⇒ Δ means: "if all formulas in Γ are true, then at least one in Δ is true". A proof is a tree of sequents whose leaves are axioms A, Γ ⇒ A, Δ. We search bottom-up:

                                       ─────────── ax            ───────────── ax
                                       Q, P ⇒ Q, R              R, Q, P ⇒ R
 ───────────────── ax                  ─────────────────────────────────────── →L
 P, Q→R ⇒ P, R                                  Q, P, Q→R ⇒ R
 ─────────────────────────────────────────────────────────────── →L
                   P, P→Q, Q→R ⇒ R
                   ──────────────────── →R
                   P→Q, Q→R ⇒ P→R

Reading bottom-up: →R moves the antecedent P to the left; →L on P→Q splits into two goals (prove P, or use Q); →L on Q→R again splits; every leaf closes by the axiom (the same formula appears on both sides). Each step only decomposes a formula, which is why sequent calculus is ideal for automatic proof search.

Format 8. Analytic tableau (refutation tree)#

To prove the entailment, assume the premises and the negation of the conclusion and look for a contradiction.

 P → Q                         (premise)
 Q → R                         (premise)
 ¬(P → R)                      (negated conclusion)
   │
   P                           (from ¬(P→R))
   ¬R                          (from ¬(P→R))
   ├── ¬P   ✗ (clashes with P)         (branch for P→Q)
   └── Q
        ├── ¬Q  ✗ (clashes with Q)     (branch for Q→R)
        └── R   ✗ (clashes with ¬R)

Rules used: ¬(A→B) yields A and ¬B (no branching); A→B branches into ¬A | B. Every branch closes, so the premises together with ¬(P→R) are unsatisfiable: the entailment holds.

Format 9. Resolution#

Convert premises and the negated conclusion to clauses (sets of literals; read as a disjunction):

Resolve (cancel a literal against its negation):

1. {P} and {¬P, Q} give {Q}
2. {Q} and {¬Q, R} give {R}
3. {R} and {¬R} give {} (the empty clause ⊥)

The empty clause means the clause set is unsatisfiable, so the entailment holds.

Format 10. Equational / calculational proof#

This format shines for equivalences rather than single entailments. Example: the contrapositive law P → Q ≡ ¬Q → ¬P.

      P → Q
  ≡     { definition of → }
      ¬P ∨ Q
  ≡     { commutativity of ∨ }
      Q ∨ ¬P
  ≡     { double negation: Q ≡ ¬¬Q }
      ¬¬Q ∨ ¬P
  ≡     { definition of →, read right to left }
      ¬Q → ¬P

Each step says "this equals that, because of <law>" in braces. Chains of equivalences are transitive, so the first and last lines are equivalent.

Format 11. Type-theoretic / proof assistant#

Under Curry-Howard, a proof of P → Q is a function turning proofs of P into proofs of Q.

Lean 4 (term mode):

theorem hs (p q r : Prop) (h1 : p → q) (h2 : q → r) : p → r :=
  fun hp => h2 (h1 hp)

Lean 4 (tactic mode):

theorem hs (p q r : Prop) (h1 : p → q) (h2 : q → r) : p → r := by
  intro hp
  apply h2
  apply h1
  exact hp

Coq / Rocq:

Theorem hs : forall p q r : Prop, (p -> q) -> (q -> r) -> p -> r.
Proof.
  intros p q r h1 h2 hp.
  apply h2.
  apply h1.
  exact hp.
Qed.

intro hp is →I (assume p); apply h2 reduces goal r to goal q (backwards →E); exact hp closes the final goal.

Z5.4 Comparison: which format when?#

Soundness and completeness cut across all of them: each of Formats 3-9 is a sound and complete calculus for classical propositional logic (and, with quantifier rules, for first-order logic). They differ only in convenience, never in what can be proved. This is Chapter 6.

Z5.5 Translating between formats: a cheat table#

Z5.6 Quick-check#

Q1. Write (p ∨ q) → ¬r in Łukasiewicz notation. Q2. Insert all hidden brackets in ¬P ∧ Q → R ∨ S ↔ T. Q3. In which format would you naturally find a "closed branch"? "The empty clause"? "A discharged assumption with a superscript"? "Dependency set"? Q4. Translate ∀x (P(x) → Q(x)) into TPTP and into Prover9 syntax. Q5. Why can a truth table not serve as a proof format for predicate logic? Q6. What does Lean's intro hp correspond to in Fitch style?

Answers. A1. CApqNr. (C first; its first argument is Apq, its second is Nr.) A2. (((¬P) ∧ Q) → (R ∨ S)) ↔ T. The ↔ is loosest, so the whole implication is its left side. A3. Tableau; resolution; Gentzen-tree natural deduction; Lemmon. A4. TPTP: ![X]: (p(X) => q(X)). Prover9: all x (P(x) -> Q(x)). A5. A structure can have an infinite domain, and there are infinitely many structures; you cannot enumerate them all. Predicate logic needs proof calculi (or countermodel search), and by Church-Turing it is only semi-decidable (Chapter 6). A6. Opening a box with the assumption p (the start of an →I subproof).

Chapter 0. The big picture ↑ Top#

0.1 Two sides of logic#

Logic studies reasoning from two complementary angles.

Truth tables are semantic: you inspect every interpretation. A proof is syntactic: you start from premises and apply rules that preserve truth, never looking at a model at all.

The deep fact that connects the two sides is that, for first-order logic, Γ ⊨ A if and only if Γ ⊢ A (soundness and completeness, Chapter 6). This is why proofs are trustworthy and why they are enough.

0.2 Why a proof is a different skill from a truth table#

A truth table is an algorithm: follow the procedure and you get the answer. A proof is a search through a space of possible arguments. There is no mechanical recipe, but there are strategies, and the main one is:

The goal determines the shape of the proof. Look at the main connective of what you want to prove, and that tells you how to start.

This single idea, developed in Chapters 2 and 4, removes most of the apparent mystery.

0.3 Three levels#

1. Formal proofs in a proof system (natural deduction). Every step is a named rule. This is how a computer checks a proof, and how you will learn the anatomy of proofs.
2. Informal mathematical proofs ("Let ε > 0 be arbitrary. Choose δ = ε/2..."). These are the same arguments written in prose. Chapter 5 shows the translation precisely.
3. Metatheory: theorems about logic itself (soundness, completeness, Gödel). Chapter 6.

You will move between the three constantly. Formal proofs teach you why informal proofs work. Informal proofs show you what formal proofs are for.

0.4 Object language vs. metalanguage#

When you write "P → Q", the arrow is a symbol inside the formal language (the object language). When you write "if A is a tautology then A ∨ B is a tautology" in English, you are reasoning about formulas in the metalanguage. Keep these separate. Confusing → (a connective) with ⊢ or ⊨ (relations between sets of formulas and formulas) is a classic beginner error.

Chapter 1. Propositional logic: precise foundations ↑ Top#

You know the basics. This chapter makes them precise, because precision is what proofs need.

1.1 Syntax: formulas are defined inductively#

Formulas are built from atoms p, q, r, ... by this grammar:

A ::= p | ⊤ | ⊥ | ¬A | (A ∧ A) | (A ∨ A) | (A → A) | (A ↔ A)

This is an inductive definition: every formula is either an atom or built from smaller formulas by exactly one connective. Two consequences matter a lot:

• You can define functions by recursion on formulas (for example, "the number of connectives" or "the truth value under v").
• You can prove statements about all formulas by structural induction (Chapter 5).

Precedence (tightest first): ¬, ∧, ∨, →, ↔. Implication is right-associative: P → Q → R means P → (Q → R). When in doubt, use parentheses.

1.2 Semantics#

A valuation v assigns T or F to each atom. It extends uniquely to all formulas using the truth tables. Write ⟦A⟧ᵥ for the value of A under v.

Three facts you will use constantly:

• (F1) Refutation principle. Γ ⊨ A ⇔ Γ ∪ {¬A} is unsatisfiable. (This is how SAT solvers and resolution provers work: to prove A, try to refute ¬A.)
• (F2) Semantic deduction theorem. Γ, A ⊨ B ⇔ Γ ⊨ A → B. In particular, A ⊨ B ⇔ ⊨ A → B.
• (F3) A ≡ B ⇔ ⊨ A ↔ B.

Explosion. If Γ is unsatisfiable, then Γ ⊨ B for every B (there is no valuation to check, so the condition holds vacuously). This semantic fact is the reason the proof rule "from ⊥ derive anything" is sound.

1.3 Implication in depth#

Implication causes more confusion than all other connectives combined.

The promise reading. "If A then B" is a promise. It is broken (false) only when A happens and B does not. If A never happens, the promise is not broken, so it is true.

Why vacuous truth is forced. Consider the claim: "for every integer n, if n > 2 then n² > 4." This is true. Now test n = 1: the antecedent (1 > 2) is false, and the claim must not be refuted by it. A universal statement is a big conjunction of its instances, so each instance, including the ones with false antecedent, must come out true. That is exactly the truth table of →.

Four related statements (for "if A then B"):

English vocabulary dictionary:

The pair "A only if B" versus "A if B" trips everyone at first: only if is the arrow pointing toward the necessary condition.

1.4 The laws you must know cold#

1.5 Normal forms#

• NNF (negation normal form): negations only in front of atoms, only ∧, ∨ otherwise.
• CNF (conjunctive normal form): an AND of ORs of literals (a literal is an atom or a negated atom). Example: (P ∨ ¬Q) ∧ (Q ∨ R).
• DNF: an OR of ANDs of literals.

Algorithm to reach CNF:

1. Eliminate ↔ and →: A → B becomes ¬A ∨ B, and A ↔ B becomes (¬A ∨ B) ∧ (¬B ∨ A).
2. Push negations inward with De Morgan and double negation (this gives NNF).
3. Distribute ∨ over ∧.

Example. Convert (P → Q) → R.

• Eliminate: ¬(¬P ∨ Q) ∨ R
• Push negation: (P ∧ ¬Q) ∨ R
• Distribute: (P ∨ R) ∧ (¬Q ∨ R)

Step 3 can cause exponential blowup. Practical SAT tools use the Tseitin transformation, which introduces fresh atoms and produces a CNF that is only equisatisfiable (not equivalent) but linear in size. You will meet this again in Chapter 7.

1.6 Functional completeness#

A set of connectives is functionally complete if every truth function can be expressed with it. The sets {¬, ∧}, {¬, ∨}, {¬, →} are complete, and so is the single connective NAND (A | B ≡ ¬(A ∧ B)). On the other hand, {∧, ∨, →, ↔} is not complete (Problem 1.9). This matters later: a prover can restrict itself to a minimal set of connectives without losing expressive power.

1.7 Why truth tables are not enough#

A truth table for n atoms has 2ⁿ rows. That is already hopeless for n = 60 (SAT solvers do better, but the problem is NP-complete). For predicate logic it is worse: "every structure" includes infinite ones, so there is no finite table at all. We need a method that does not enumerate worlds. That method is proof.

1.8 Chapter 1 in complete detail (the from-zero companion)#

Sections 1.1-1.7 gave you the skeleton of propositional logic. This companion rebuilds the whole subject from absolute zero, slowly, with every definition spelled out, every connective examined, and every standard fact proved or demonstrated. If you already feel solid, skim the headings and use the tables as reference. If anything above felt too fast, read this section from the top.

1.8.1 What is a proposition?#

Definition. A proposition (also called a statement or sentence in the logician's sense) is a declarative sentence that is, in the situation under discussion, either true or false, but not both.

Two requirements are hidden in that sentence:

1. Declarative: it asserts something about the world.
2. Bivalent: it has exactly one of two truth values, True (T) or False (F). Classical logic assumes this (the principle of bivalence).

Key point: logic cares about truth conditions, not about whether we know the truth. "There is life on Mars" is a proposition even though we do not know its value.

Atomic and compound propositions#

• An atomic proposition (atom) is one that we do not analyze further: "It is raining." We give it a letter: R.
• A compound proposition is built from others using connectives: "It is raining and it is cold."

Atoms are a choice. "John is tall" might be an atom T, or it might be analyzed in predicate logic as Tall(john). In propositional logic we decide where to stop.

Golden rule for choosing atoms:

1. Each atom should be a complete declarative sentence (not a fragment).
2. Use the same letter for the same statement every time.
3. Make atoms as small as the argument requires, no smaller than necessary, and positive (prefer R = "it rains" over N = "it does not rain"; negation is the job of ¬).

1.8.2 The connectives, one at a time#

For each connective: its truth table, its English forms, its traps.

Negation ¬A#

English: "not A"; "it is not the case that A"; "it is false that A"; "A is not true"; "A fails". Traps:

• Negation flips the whole statement. The negation of "All swans are white" is not "All swans are black" but "Not all swans are white" (Chapter 3).
• The negation of "A and B" is "not A or not B" (De Morgan), never "not A and not B".
• "A is unhappy" is not necessarily ¬"A is happy" in ordinary language (there may be a middle ground). In logic, ¬ always means exactly "not true".

Conjunction A ∧ B#

English: "A and B"; "both A and B"; "A but B"; "A although B"; "A however B"; "A yet B"; "A while B"; "A moreover B"; "A, B" (comma); "not only A but also B"; "A as well as B". Traps:

• "But" is logically "and". "It is sunny but cold" = S ∧ C. The contrast is rhetorical, not logical.
• "and" in ordinary English can mean "and then" ("He opened the door and walked out" is order-sensitive) or a collective meaning ("Ann and Bob lifted the piano" probably means together). Logic's ∧ is only "both are true". It is commutative: A ∧ B ≡ B ∧ A.
• "John and Mary are married" does not always split as "John is married and Mary is married".

Disjunction A ∨ B (inclusive or)#

English: "A or B"; "A or B or both"; "at least one of A, B"; "A and/or B"; "either A or B" (often, but see below). Traps:

• Inclusive vs. exclusive. Logic's ∨ is inclusive: true when both hold. The English "or" is sometimes exclusive ("soup or salad" usually means one but not both). The exclusive or is ⊕: A ⊕ B ≡ (A ∨ B) ∧ ¬(A ∧ B).
• In legal and mathematical texts "or" is inclusive unless it says "exactly one of" or "but not both".
• The word vel (Latin for inclusive "or") is the origin of the symbol ∨. Latin aut is exclusive.

Conditional (implication) A → B#

Parts: A = antecedent (hypothesis, premise, "if-part"); B = consequent (conclusion, "then-part").

English forms, all meaning A → B:

Why is the table the way it is? A → B says "you will never find A true and B false." It is violated only in row 2. In rows 3-4 the antecedent is false, so the promise "if A then B" is vacuously true (nothing was promised for those cases). This is the material conditional (also material implication). It is not the "because" or "causes" of ordinary speech:

• "If 2 + 2 = 5 then the moon is cheese" is true (false antecedent).
• "If the moon is cheese then 2 + 2 = 4" is true (true consequent).
• "If it rains, the street is wet" says nothing about causation; it only rules out (rain ∧ dry street).

These are the so-called paradoxes of material implication. They are not errors; they are the price of making → truth-functional (its value depends only on the values of A and B). Other logics (relevance logic, conditional logic, Chapter 7) refine →, but classical mathematics uses the material conditional, and so does this course.

Four statements around A → B (see Section 1.3): converse B → A, inverse ¬A → ¬B, contrapositive ¬B → ¬A (equivalent to the original), negation A ∧ ¬B.

Necessary vs. sufficient, once and for all: "A is sufficient for B" = having A is enough to get B = A → B. "B is necessary for A" = you can't have A without B = A → B. (Same statement, viewed from the two ends.) Example: "Being a square is sufficient for being a rectangle; being a rectangle is necessary for being a square."

Unless. "A unless B" has two readings; the standard logical reading is ¬B → A, equivalent to A ∨ B. ("You will fail unless you study" = if you don't study you fail = you fail or you study.) If you want to also say "if you study you pass", add the converse: that is a biconditional.

Biconditional A ↔ B#

English: "A if and only if B"; "A iff B" (math shorthand); "A exactly when B"; "A precisely if B"; "A just in case B"; "A is necessary and sufficient for B"; "A is equivalent to B". Facts: A ↔ B ≡ (A → B) ∧ (B → A); it says A and B always have the same truth value; it is commutative and associative; ¬(A ↔ B) ≡ A ⊕ B. Trap: English "if" in definitions often means "iff" ("A number is even if it is divisible by 2" is a definition, meaning iff). In theorems, "if" means →.

Exclusive or A ⊕ B#

True exactly when A and B have different values: A ⊕ B ≡ ¬(A ↔ B) ≡ (A ∨ B) ∧ ¬(A ∧ B). Properties: commutative, associative, A ⊕ A ≡ ⊥, A ⊕ ⊥ ≡ A, A ⊕ ⊤ ≡ ¬A. It is addition modulo 2.

NAND (A ↑ B) and NOR (A ↓ B)#

NAND = "not both": ¬(A ∧ B). NOR = "neither": ¬(A ∨ B). Each of them alone can express every other connective (Section 1.8.8). Real computer chips are built from NAND or NOR gates.

The constants ⊤ and ⊥#

⊤ is a formula that is always true; ⊥ is a formula that is always false. They are 0-ary connectives (take no arguments). They behave like identity/zero elements: A ∧ ⊤ ≡ A, A ∨ ⊥ ≡ A, A ∧ ⊥ ≡ ⊥, A ∨ ⊤ ≡ ⊤. Many proof systems define ¬A as an abbreviation for A → ⊥.

Summary: common English patterns#

1.8.3 Syntax in complete detail#

Syntax is the study of the form of formulas (what strings count as well-formed), with no mention of truth.

The alphabet (vocabulary)#

A propositional language has:

1. Atoms (propositional variables): p, q, r, s, ... or p₀, p₁, p₂, ...; a countable (usually infinite) supply.
2. Connectives: ¬ ∧ ∨ → ↔ (and optionally ⊤ ⊥ ⊕ ↑ ↓).
3. Auxiliary symbols: parentheses ( and ).

Everything not in the alphabet is not part of the formal language. (When we write A, B, Γ we are using metavariables, which stand for formulas but are not themselves part of the language. Compare "Let n be any integer": n is not one specific integer.)

The formation rules (inductive definition)#

The set Form of formulas is the smallest set such that:

1. Every atom is a formula; ⊤ and ⊥ are formulas.
2. If A is a formula, so is ¬A.
3. If A and B are formulas, so are (A ∧ B), (A ∨ B), (A → B), (A ↔ B).

"Smallest" means: nothing else is a formula. In BNF (the grammar notation used in Section 1.1):

A ::= p | ⊤ | ⊥ | ¬A | (A ∧ A) | (A ∨ A) | (A → A) | (A ↔ A)

Read ::= as "is defined as" and | as "or" (here | is part of BNF, not the logical connective).

Examples

Parse trees (syntax trees)#

Every formula has a unique tree: the main connective is the root, immediate subformulas are children, atoms are leaves.

Formula: (P ∧ ¬Q) → (R ∨ P)

            →
          /   \
        ∧       ∨
       / \     / \
      P   ¬   R   P
          |
          Q

• The main connective (principal connective) is the root: →. Everything about the formula's type is decided by it: this formula is an implication.
• Immediate subformulas of the root: P ∧ ¬Q and R ∨ P.
• Subformulas (all): P, Q, ¬Q, P ∧ ¬Q, R, R ∨ P, and the whole formula. That is 7 distinct subformulas, though the tree has 8 nodes because P occurs twice. A subformula occurrence is a particular position in the tree.
• Atoms: P, Q, R (3 distinct atoms). Connectives: 4 occurrences (→, ∧, ¬, ∨).
• Height (depth): the number of edges on the longest root-to-leaf path: here 3 (→, ∧, ¬, Q).
• Size: number of nodes (8), or sometimes the number of symbols.

Why the main connective matters: a rule or law only applies to the main connective. (P ∧ Q) → R is an implication, not a conjunction, even though it contains ∧. This is the source of error #5 in Section 2.8.

Unique readability#

Theorem (unique readability). Every formula can be parsed in exactly one way.

This is why brackets matter. Without them, P ∧ Q ∨ R has two parses with different meanings. Take the valuation P = F, Q = F, R = T:

• (P ∧ Q) ∨ R = (F ∧ F) ∨ T = T
• P ∧ (Q ∨ R) = F ∧ (F ∨ T) = F

so the two readings really differ. Precedence conventions (Z5.1.1) tell you which brackets may be omitted. Prefix (Polish) notation needs no brackets at all.

Defining functions by recursion on formulas#

Because formulas are built inductively, you can define a function on them by saying what it does to each kind of formula.

Number of connectives c(A):

• c(p) = 0, c(⊤) = c(⊥) = 0
• c(¬A) = 1 + c(A)
• c(A ∘ B) = 1 + c(A) + c(B) for each binary connective ∘

Set of atoms atoms(A):

• atoms(p) = {p}, atoms(⊤) = atoms(⊥) = ∅
• atoms(¬A) = atoms(A)
• atoms(A ∘ B) = atoms(A) ∪ atoms(B)

Truth value ⟦A⟧ᵥ (the semantics, next section) is defined the same way.

Example: c((P ∧ ¬Q) → (R ∨ P)) = 1 + c(P ∧ ¬Q) + c(R ∨ P) = 1 + (1 + 0 + 1) + (1 + 0 + 0) = 4. ✓.

Proving things by structural induction (preview of Chapter 5)#

To prove a property for all formulas, prove it for atoms (base case) and show it is preserved by each connective (inductive step). Example: every formula has as many "(" as ")".

• Base: an atom has 0 and 0.
• ¬A: parentheses are exactly those of A. Equal by hypothesis.
• (A ∘ B): one "(" and one ")" added to those of A and B. Equal by hypothesis.

Hence true for all formulas. ∎

1.8.4 Semantics in complete detail#

Semantics gives formulas meaning: which are true, in which situations.

Valuations#

A valuation (assignment, interpretation, "world") is a function v from atoms to {T, F}. It says, for each atom, whether it is true or false in the situation being considered. With n atoms there are exactly 2ⁿ valuations: one for each row of the truth table.

Truth value of a compound: the recursive definition#

The valuation extends uniquely to all formulas by:

This is the only place truth tables come from. A truth table is just this definition tabulated for all valuations.

Evaluating a formula under one valuation#

Evaluate (P ∧ ¬Q) → (R ∨ P) under v: P = T, Q = F, R = F. Work bottom-up on the parse tree:

Building a truth table systematically#

1. List the atoms: n of them. You need 2ⁿ rows.
2. Fill the atom columns in a standard order so none is missed. Convention: first atom changes slowest, last atom changes fastest, starting with all T: TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF for n = 3.
3. Add one column per subformula, smallest first, so every column only uses columns to its left.
4. The last column is the formula's value for each row.

n atoms → 2ⁿ rows: 5 atoms → 32 rows; 10 atoms → 1 024; 20 atoms → 1 048 576; 60 atoms → 2⁶⁰ ≈ 10¹⁸ rows (Section 1.7).

Classification of formulas#

Relationships you should be able to recite:

• A is a tautology ⇔ ¬A is a contradiction.
• A is satisfiable ⇔ ¬A is falsifiable ⇔ A is not a contradiction.
• A is valid ⇔ A is not falsifiable.

Semantic relations between formulas#

A valuation that makes Γ true is called a model of Γ (written v ⊨ Γ). Entailment is "truth-preservation in all models".

Important consequences (be able to prove each):

1. Γ ⊨ A and Γ is inconsistent: holds vacuously (explosion).
2. If ⊨ A then Γ ⊨ A for any Γ (a tautology follows from anything).
3. Monotonicity: if Γ ⊨ A and Γ ⊆ Δ, then Δ ⊨ A. (More premises never hurt.)
4. Cut/transitivity: if Γ ⊨ A and Γ, A ⊨ B then Γ ⊨ B.
5. A ≡ B iff A ⊨ B and B ⊨ A.

Four methods to decide validity#

Short truth table demonstration. Is ((P → Q) ∧ (Q → R)) → (P → R) a tautology? Try to make it false:

• An implication is false only if antecedent T and consequent F: need (P → Q) ∧ (Q → R) = T and P → R = F.
• P → R = F forces P = T and R = F.
• P → Q = T with P = T forces Q = T.
• Q → R with Q = T, R = F is F, but we needed it T. Contradiction.
• So no valuation falsifies it: it is a tautology. ∎

If the forcing had not collided, the surviving valuation would be a countermodel, a concrete falsifying world.

Complexity note. Deciding satisfiability (SAT) is NP-complete (Cook-Levin, 1971); deciding validity is coNP-complete. All known algorithms are exponential in the worst case, yet modern SAT solvers routinely handle millions of variables on structured problems. Propositional logic is decidable (the truth table is an algorithm), unlike predicate logic (Chapter 6).

Proving an equivalence without a table (semantic argument template)#

Claim: ¬(A ∧ B) ≡ ¬A ∨ ¬B. Proof. Let v be an arbitrary valuation. Then

⟦¬(A ∧ B)⟧ᵥ = T ⇔ ⟦A ∧ B⟧ᵥ = F (def. of ¬) ⇔ not both ⟦A⟧ᵥ = T and ⟦B⟧ᵥ = T (def. of ∧) ⇔ ⟦A⟧ᵥ = F or ⟦B⟧ᵥ = F ⇔ ⟦¬A⟧ᵥ = T or ⟦¬B⟧ᵥ = T (def. of ¬) ⇔ ⟦¬A ∨ ¬B⟧ᵥ = T (def. of ∨). Since v was arbitrary, the formulas are equivalent. ∎

The pattern is: take an arbitrary valuation, unfold definitions, chain of ⇔. This is your first taste of a proof about logic, which prepares you for Chapter 6.

1.8.5 All truth functions#

A truth function (Boolean function) of n arguments is any rule giving T or F for each of the 2ⁿ combinations of inputs. The number of different n-ary truth functions is

2^(2ⁿ): n = 0 → 2 (the constants ⊤, ⊥); n = 1 → 4; n = 2 → 16; n = 3 → 256; n = 4 → 65 536.

The 4 unary functions#

The 16 binary functions#

Patterns list the output for rows (A,B) = TT, TF, FT, FF in that order.

Observations.

• Only functions 8, 14, 11 (and 9, 6, 7, 1) are conventionally used as binary connectives. Functions 0, 3, 5, 10, 12, 15 do not really depend on both inputs.
• Pairs of duals/negations: 8↔7 (∧, NAND), 14↔1 (∨, NOR), 9↔6 (↔, ⊕), 11↔4 (→, ↛), 13↔2.
• Commutative: 1, 6, 7, 8, 9, 14. Not commutative: 11, 13, 4, 2.
• → is function 11. Every other implication-like function is a flip or negation of it.

A ternary example: if-then-else ITE(A, B, C) ≡ (A ∧ B) ∨ (¬A ∧ C): "if A then B else C". Majority: MAJ(A,B,C) ≡ (A∧B) ∨ (A∧C) ∨ (B∧C).

1.8.6 The complete table of laws, with names#

Below, A, B, C are arbitrary formulas. Each line is an equivalence ≡ (and thus also a tautology after replacing ≡ by ↔).

Laws for ∧, ∨, ¬ (Boolean algebra)#

Laws for →#

Laws for ↔ and ⊕#

Things that are not valid (common false laws)#

Using the laws: a derivation by equational reasoning#

Prove absorption A ∨ (A ∧ B) ≡ A:

      A ∨ (A ∧ B)
  ≡     { identity: A ≡ A ∧ ⊤ }
      (A ∧ ⊤) ∨ (A ∧ B)
  ≡     { distributivity, factoring out A }
      A ∧ (⊤ ∨ B)
  ≡     { domination: ⊤ ∨ B ≡ ⊤ }
      A ∧ ⊤
  ≡     { identity }
      A

Two meta-theorems that make laws usable#

Replacement theorem. If B ≡ B′, then replacing an occurrence of B inside a formula C by B′ gives a formula equivalent to C. (Equivalent subformulas are interchangeable. This is what justifies chains of ≡.)

Substitution theorem. If A is a tautology and you replace every occurrence of an atom p in A uniformly by any formula B, the result is still a tautology. (So p ∨ ¬p being valid yields (Q ∧ R) ∨ ¬(Q ∧ R) being valid.)

Care: uniform is essential. Replacing only one of two occurrences of p in p → p by ¬p gives ¬p → p, which is not valid.

This is why laws are written with metavariables A, B, C: each is a schema with infinitely many instances.

1.8.7 Normal forms in complete detail#

Vocabulary#

• Literal: an atom p or a negated atom ¬p.
• Clause: a disjunction of literals: p ∨ ¬q ∨ r. (A single literal is a clause; the empty disjunction is ⊥, called the empty clause.)
• Term (or cube, conjunctive clause): a conjunction of literals.
• NNF: negation only on atoms; connectives only ∧, ∨ (and ¬ at the atoms).
• CNF: a conjunction of clauses. DNF: a disjunction of terms.
• Canonical (full) forms: every clause/term mentions every atom exactly once.

Every formula is equivalent to a CNF and to a DNF.

Reading a DNF/CNF off a truth table (canonical forms)#

Canonical DNF: take every row where the formula is T; write the term that is true only on that row (atom if T, negated atom if F); OR them together. Canonical CNF: take every row where the formula is F; write the clause that is false only on that row (atom if F, negated atom if T); AND them together.

Example. Majority of three, MAJ(P,Q,R) = "at least two true":

• Canonical DNF (4 true rows): (P∧Q∧R) ∨ (P∧Q∧¬R) ∨ (P∧¬Q∧R) ∨ (¬P∧Q∧R)
• Canonical CNF (4 false rows): (¬P∨Q∨R) ∧ (P∨¬Q∨R) ∧ (P∨Q∨¬R) ∧ (P∨Q∨R)
• Minimal forms (simplified by laws): DNF (P∧Q) ∨ (P∧R) ∨ (Q∧R); CNF (P∨Q) ∧ (P∨R) ∧ (Q∨R).

This construction proves functional completeness of {¬, ∧, ∨}: every truth function (every table) equals its canonical DNF. Two special cases: if there are no T rows the formula is ⊥; if no F rows, ⊤.

Conversion algorithm (syntactic), step by step#

1. Eliminate ↔, ⊕, → : A ↔ B ⟹ (¬A ∨ B) ∧ (¬B ∨ A); A ⊕ B ⟹ (A ∨ B) ∧ (¬A ∨ ¬B); A → B ⟹ ¬A ∨ B.
2. Push negations inward (reach NNF): ¬¬A ⟹ A; ¬(A ∧ B) ⟹ ¬A ∨ ¬B; ¬(A ∨ B) ⟹ ¬A ∧ ¬B; ¬⊤ ⟹ ⊥; ¬⊥ ⟹ ⊤.
3. Distribute ∨ over ∧ to reach CNF (or ∧ over ∨ for DNF): A ∨ (B ∧ C) ⟹ (A ∨ B) ∧ (A ∨ C).
4. Clean up: remove duplicates, drop clauses containing both p and ¬p (they are tautologies), apply absorption.

Worked example. Convert ¬((P ∨ Q) → (P ∧ R)) to CNF.

• Eliminate →: ¬(¬(P ∨ Q) ∨ (P ∧ R))
• De Morgan: ¬¬(P ∨ Q) ∧ ¬(P ∧ R)
• Double negation and De Morgan: (P ∨ Q) ∧ (¬P ∨ ¬R)

Already in CNF: two clauses P ∨ Q and ¬P ∨ ¬R. ✓.

Blow-up. Converting (a₁ ∧ b₁) ∨ (a₂ ∧ b₂) ∨ ... ∨ (aₙ ∧ bₙ) to CNF gives 2ⁿ clauses. That is why Tseitin exists.

Tseitin transformation (equisatisfiable CNF in linear size)#

Introduce a fresh atom xᵢ for each non-atomic subformula and assert that xᵢ is equivalent to it, written as clauses.

Gate clauses:

Example. (P ∧ Q) ∨ R: name x₁ ↔ (P ∧ Q) and x₂ ↔ (x₁ ∨ R), then assert x₂:

(¬x₁ ∨ P) ∧ (¬x₁ ∨ Q) ∧ (x₁ ∨ ¬P ∨ ¬Q)        -- defines x₁
∧ (¬x₂ ∨ x₁ ∨ R) ∧ (x₂ ∨ ¬x₁) ∧ (x₂ ∨ ¬R)    -- defines x₂
∧ x₂                                            -- assert the whole formula

The result is satisfiable iff (P ∧ Q) ∨ R is satisfiable (equisatisfiable), but it is not equivalent (it mentions new atoms) and its size grows only linearly.

Why normal forms matter#

• CNF is the input format of SAT solvers and of resolution provers.
• DNF makes satisfiability trivial (a term is satisfiable iff it has no clashing literals) but makes validity hard.
• CNF makes validity trivial (check each clause for p and ¬p) but makes satisfiability hard.
• This asymmetry is exactly why SAT is NP-complete.

1.8.8 Functional completeness in complete detail#

A set of connectives is functionally complete (adequate) if every truth function is expressible using only them.

Proofs and expressions#

• {¬, ∧, ∨} is complete: canonical DNF (Section 1.8.7).
• {¬, ∧} is complete: A ∨ B ≡ ¬(¬A ∧ ¬B) (De Morgan), then use the previous result.
• {¬, ∨} is complete: A ∧ B ≡ ¬(¬A ∨ ¬B).
• {¬, →} is complete: A ∨ B ≡ ¬A → B; A ∧ B ≡ ¬(A → ¬B).
• {→, ⊥} is complete: ¬A ≡ A → ⊥; A ∨ B ≡ (A → ⊥) → B; A ∧ B ≡ (A → (B → ⊥)) → ⊥.
• {↑} alone (NAND): ¬A ≡ A ↑ A; A ∧ B ≡ (A ↑ B) ↑ (A ↑ B); A ∨ B ≡ (A ↑ A) ↑ (B ↑ B).
• {↓} alone (NOR): ¬A ≡ A ↓ A; A ∨ B ≡ (A ↓ B) ↓ (A ↓ B); A ∧ B ≡ (A ↓ A) ↓ (B ↓ B).

Some incomplete sets, and why#

Post's criterion (Emil Post, 1941): a set of truth functions is complete iff it is not entirely contained in any one of five classes: functions that preserve F (T₀), preserve T (T₁), are monotone, are self-dual, or are affine. NAND and NOR escape all five. That is a classification theorem you can study later.

Why you care#

• Hardware: every circuit can be built from NAND gates only.
• Provers: restricting to few connectives shrinks the number of rules.
• Proof systems: minimal systems (like Hilbert's {→, ⊥}) are shorter to analyze.

1.8.9 Arguments in propositional logic: valid forms and fallacies#

An argument is a list of premises A₁, ..., Aₙ and a conclusion C. It is valid iff A₁, ..., Aₙ ⊨ C. Validity depends on form only.

Named valid forms (rules of inference)#

Named fallacies (invalid forms that look valid)#

Concrete English instances:

• Affirming the consequent: "If it rained, the grass is wet. The grass is wet. So it rained." (A sprinkler could be responsible.)
• Denying the antecedent: "If you study, you pass. You didn't study. So you won't pass." (You may be lucky or brilliant.)

How to test any argument: (1) formalize premises and conclusion; (2) search for a valuation making all premises T and the conclusion F (short truth table). If one exists, the argument is invalid and that valuation is your counterexample. If none exists, it is valid.

1.8.10 Quick-check (with answers)#

Q1. Which of these are propositions: (a) "Is 7 prime?" (b) "7 is prime." (c) "x > 3." (d) "Every even number greater than 2 is a sum of two primes." Q2. Translate "You may enter only if you have a ticket and are not drunk" with E, T, D. Q3. What are the main connective, the immediate subformulas, and the number of connectives of ¬(P ∨ Q) → (R ↔ ¬S)? Q4. How many valuations are there for a formula with 7 distinct atoms? How many different 3-ary truth functions exist? Q5. Use the short-truth-table method on (P → Q) → (¬Q → ¬P). Valid? Q6. True or false: (a) A → B ≡ ¬B → ¬A; (b) A → (B → C) ≡ (A → B) → C; (c) {P ∨ Q, ¬P} ⊨ Q; (d) P ↔ Q ≡ (P ∧ Q) ∨ (¬P ∧ ¬Q). Q7. Give canonical DNF for P ⊕ Q and canonical CNF for P → Q. Q8. Express A → B using only NAND. Q9. Why does a conditional with a false antecedent count as true?

Answers. A1. (b) and (d). (a) is a question, (c) is an open sentence. A2. E → (T ∧ ¬D). ("Only if" gives the arrow from E to the conditions.) A3. Main connective: →. Immediate subformulas: ¬(P ∨ Q) and R ↔ ¬S. Connectives: ¬, ∨, →, ↔, ¬ = 5. A4. 2⁷ = 128 valuations. 2^(2³) = 2⁸ = 256 ternary functions. A5. To falsify: need P → Q = T and ¬Q → ¬P = F. The latter forces ¬Q = T (Q = F) and ¬P = F (P = T). Then P → Q = T → F = F, contradiction. So it is valid. A6. (a) True. (b) False (A = F, C = F). (c) True. (d) True. A7. P ⊕ Q: true rows TF and FT: (P ∧ ¬Q) ∨ (¬P ∧ Q). P → Q: only false row TF: (¬P ∨ Q). A8. A → B ≡ ¬A ∨ B ≡ A ↑ ¬B ≡ A ↑ (B ↑ B). Check: A ↑ (B ↑ B) = ¬(A ∧ ¬B) = ¬A ∨ B ✓. A9. Because → promises only that "A true and B false" never occurs. If A is false, that situation did not occur, so the promise is not broken. Also, a universal claim "for all n, if n > 2 then ..." must not be refuted by n = 1 (Section 1.3).

Problems for Chapter 1#

1.1 ★ Use a truth table to show that P → Q, ¬P ∨ Q, ¬(P ∧ ¬Q), and ¬Q → ¬P are all equivalent.

1.2 ★ State the converse, inverse, and contrapositive of "if a number is divisible by 6, then it is divisible by 3". Which of the four statements are true?

1.3 ★ Translate into propositional logic, naming your atoms:

• (a) "You can have dessert only if you finish dinner."
• (b) "Unless you hurry, you will miss the train."
• (c) "Passing the exam is necessary but not sufficient for getting the degree."
• (d) "Neither the server nor the backup is responding."

1.4 ★★ Decide, with justification, whether each entailment holds:

• (a) {P → Q, Q → R, P} ⊨ R
• (b) {P → Q, Q} ⊨ P
• (c) {P ∨ Q, ¬P} ⊨ Q
• (d) {P → Q, ¬P} ⊨ ¬Q

1.5 ★★ Show that P → (Q → R) ≡ (P ∧ Q) → R using the laws of Section 1.4 (no truth table).

1.6 ★★ Convert (P ↔ Q) ∨ R to CNF and to DNF.

1.7 ★★ Using (F1), show {P → Q, Q → R} ⊨ P → R by proving that {P → Q, Q → R, ¬(P → R)} is unsatisfiable.

1.8 ★★ Show that NAND is functionally complete by expressing ¬P and P ∧ Q using only |.

1.9 ★★★ Prove that no formula built from atoms using only ∧, ∨, →, ↔ is equivalent to ¬P. (Hint: look at the valuation making every atom true.)

1.10 ★★★ On an island, knights always tell the truth and knaves always lie. A says "B is a knave." B says "A and I are of the same kind." Who is the knight and who is the knave? Formalize with atoms a = "A is a knight" and b = "B is a knight" and solve algebraically.

Chapter 2. Natural deduction for propositional logic ↑ Top#

2.1 What is a proof?#

A formal proof of A from premises Γ (written Γ ⊢ A) is a finite sequence of lines. Each line is either a premise, an assumption (temporarily made), or follows from earlier lines by an inference rule. The last line is A.

The point is that a proof is a purely mechanical object. A computer (or a skeptical friend) can check it line by line without understanding what the formulas mean. This is what makes it trustworthy.

We use natural deduction in Fitch style: nested sub-proofs, where each sub-proof opens with an assumption and ends when we discharge it.

2.2 Reading and writing Fitch proofs#

1.  P → Q              premise
2.  Q → R              premise
3.  |  P               assumption
4.  |  Q               →E 1,3
5.  |  R               →E 2,4
6.  P → R              →I 3-5

• The vertical bar | marks a sub-proof. Everything inside is true only under the assumption that opened it.
• A line may use any earlier line in its own sub-proof or an enclosing one, never from a closed sub-proof.
• When the sub-proof closes (line 6), the assumption is discharged: line 6 does not depend on P any more. It says "if P then R", which depends only on lines 1 and 2.
• Justifications: rule name plus the line numbers it uses. A sub-proof is cited as a range, like 3-5.

2.3 The rules#

Each connective has an introduction rule (how to prove a statement of that form) and an elimination rule (how to use a statement of that form). This pairing is the heart of natural deduction.

Two rules to treat with respect:

• ¬I vs. RAA. They look similar but differ crucially. ¬I proves a negation (assume A, reach ⊥, conclude ¬A). RAA proves any statement (assume ¬A, reach ⊥, conclude A). RAA is the rule that makes the logic classical. Without it you have intuitionistic logic (Section 2.7).
• ∨E needs both branches to reach the same conclusion C. C is chosen by you, usually the current goal.

2.4 How to find proofs: the strategy#

Two questions, in this order:

1. What is my goal? Look at its main connective.

2. What do I have? Look at the main connective of each available line.

Golden rule: work backwards from the goal and forwards from the premises, and meet in the middle. When stuck, ask "what would give me a contradiction?"

2.5 Worked examples#

Example 1. Hypothetical syllogism: P → Q, Q → R ⊢ P → R#

The goal is an implication, so assume the antecedent.

1.  P → Q              premise
2.  Q → R              premise
3.  |  P               assumption
4.  |  Q               →E 1,3
5.  |  R               →E 2,4
6.  P → R              →I 3-5

Example 2. Contrapositive: P → Q ⊢ ¬Q → ¬P#

Goal is an implication, so assume ¬Q. Its conclusion ¬P is a negation, so assume P and look for ⊥.

1.  P → Q              premise
2.  |  ¬Q              assumption
3.  |  |  P            assumption
4.  |  |  Q            →E 1,3
5.  |  |  ⊥            ¬E 4,2
6.  |  ¬P              ¬I 3-5
7.  ¬Q → ¬P            →I 2-6

Example 3. Disjunctive syllogism: P ∨ Q, ¬P ⊢ Q#

We use a disjunction, so do cases.

1.  P ∨ Q              premise
2.  ¬P                 premise
3.  |  P               assumption (case 1)
4.  |  ⊥               ¬E 3,2
5.  |  Q               ⊥E 4
6.  |  Q               assumption (case 2)
7.  Q                  ∨E 1, 3-5, 6-6

Case 1 is impossible (it contradicts ¬P), so ex falso gives Q. Case 2 is trivial.

Example 4. De Morgan: ¬(P ∨ Q) ⊢ ¬P ∧ ¬Q#

Goal is a conjunction, so prove each part. Each part is a negation, so assume and refute.

1.  ¬(P ∨ Q)           premise
2.  |  P               assumption
3.  |  P ∨ Q           ∨I 2
4.  |  ⊥               ¬E 3,1
5.  ¬P                 ¬I 2-4
6.  |  Q               assumption
7.  |  P ∨ Q           ∨I 6
8.  |  ⊥               ¬E 7,1
9.  ¬Q                 ¬I 6-8
10. ¬P ∧ ¬Q            ∧I 5,9