Week 1 Introduction, Mathematical Statements, Propositional Logic, First Steps in Predicate Logic

Sources covered

Lecture 1 (introduction and teasers), Lecture 2 (propositional logic), Lecture 3 (propositional logic continued, start of predicate logic, mock interview). Script: Chapter 1 (§1.1–1.3), §2.1–2.3 complete, §2.4.1–2.4.2. The rest of §2.4 (quantifiers in detail), §2.5 and §2.6 (proof patterns) follow in Week 2. Material that appears only in the script and was not discussed in the lecture is marked (script only).

---

1. Executive Overview & Core Objectives

Week 1 lays the foundation for the whole course: what a mathematical statement is, what it means to prove one, and how propositional logic gives us a precise “toy world” of formulas in which we can compute with truth values like we compute with polynomials. The central conceptual point, stressed repeatedly by the lecturer, is the strict separation between statements (true or false, natural-language level, connected by $⟹$) and formulas (syntactic objects with symbols that need a truth assignment, connected by $\to ,\wedge ,\vee ,\neg$). Relations between formulas such as $\equiv$ and $\models$ produce statements about formulas. The week ends with the motivation and the building blocks of predicate logic.

Learning objectives. After this week you should be able to:

• decide whether a sentence is a well-defined mathematical statement, and distinguish “well-defined” from “known to be true”;
• evaluate composed statements, especially $S⟹T$, and explain why implication has nothing to do with causality;
• solve the chessboard L-tiling teaser (counting argument + doubling theorem) and the chocolate teaser (invariant argument);
• build truth tables (function tables) for arbitrary propositional formulas;
• define and check logical equivalence ($\equiv$), logical consequence ($\models$), tautology/validity, and (un)satisfiability;
• derive equivalences by algebraic manipulation using Lemma 2.1 instead of truth tables;
• state and prove Lemma 2.3 ($F\to G$ is a tautology $⟺F\models G$) and justify modus ponens;
• spot circular reasoning (“assuming what you want to prove”) in a false proof;
• name the building blocks of predicate logic (universe, predicates, functions, constants, operators, quantifiers).

Course logistics (Lecture 1)

• Lectures Monday and Wednesday. One exercise class (Übungsgruppe) on Monday or Tuesday, groups A–Y, in German or English. Registration is on Moodle, not myStudies.
• Exercise sheets come out on Thursdays. Each sheet has a bonus exercise.
• Bonus system: two one-on-one oral interviews with a TA per semester, max 6 points each, so 12 points total, converted to a bonus of $0$ to $0.25$ added to the exam grade. Each interview covers the bonus exercise of the previous Thursday’s sheet. Four students per time slot, ordered alphabetically by surname. You may bring handwritten notes for yourself, but you present the solution from scratch.
• Mock-interview grading (Lecture 3): partial points per sub-question. Extra questions can make up for lost points, but the cap stays at 6.
• Exam: on paper, on site, 3 hours, in the exam session (late Jan/early Feb). You can choose an English or German version.
• Sections marked with $\ast$ in the script are not exam relevant.
• The board content is not uploaded. It either matches the script or is a slight variant, and the lecturer announces explicitly when it isn’t.

---

2. Core Concepts & Formal Definitions

2.1 Why discrete mathematics? (Script §1.1, §1.3)

Discrete mathematics (Diskrete Mathematik) studies finite and countably infinite structures, such as graphs, integers and finite algebraic structures, as opposed to the continuum ($\mathbb{R}$) of analysis. The script gives three reasons it is central to computer science:

1. Discrete structures. Networks are graphs, and cryptography and coding theory use algebraic groups and fields.
2. Abstraction. Computer systems can only be understood in layers of abstraction.
3. Mathematical derivations. In CS, reasoning usually takes the form of a proof (e.g. “this program terminates”, “this system is secure”), not a numerical calculation.

Abstraction (Abstraktion) in this course means two things:

• simplification: ignore every aspect that is irrelevant to the problem;
• generalization: a property proved at the abstract level holds for every system with the same abstraction.

The lecturer’s three goals for the course:

1. build everything from scratch;
2. abstract as much as possible (e.g. talk about groups and rings rather than $\mathbb{N}$);
3. make everything formal and proved.

Course roadmap: logic (start) → sets/relations, number theory, algebra (middle) → logic again (mid-November to the end).

2.2 Mathematical statements (Script §2.1.1)

Definition 2.1 (Mathematical statement)

A mathematical statement (mathematische Aussage), also called a proposition, is a statement that is true or false in an absolute, indisputable sense, according to the laws of mathematics.

Terminology:

Term	Meaning
theorem (Theorem/Satz)	a true statement, usually an important result
lemma (Lemma)	a true, intermediate, often technical result used in later proofs
corollary (Korollar)	a simple consequence (e.g. special case) of a theorem or lemma
conjecture (Vermutung)	a statement not known to be true or false, but believed to be one of them
assumption (Annahme)	not known to be true, but assumed true within a line of reasoning
assertion / claim (Behauptung)	a true statement before its proof has been given

The lecture asks two separate questions for every sentence:

1. Is it a well-defined statement, i.e. does it definitely have a truth value?
2. If so, is it true or false, and do we know which?

Examples from the lecture (Lecture 1)

• $S$: “101 is a prime number.” Well-defined and true. The number is meant in decimal. A student also asked about that.
• $T$: “There are infinitely many twin primes.” Twin primes are pairs of primes that differ by 2, e.g. $(3,5),(5,7),(11,13)$. Well-defined, but its truth value is unknown (open research problem). Well-defined does not mean known.
• “I love you.” Grammatically a statement, but not a mathematical statement: there is no precise definition that fixes a truth value.
• $U$: “This statement is false.” Not well-defined. If $U$ were true, then what it says holds, so it is false. If $U$ were false, then what it says fails, so it is true. A statement must be exactly one of true/false, so $U$ is not a statement. The problem is self-reference. Later in the course there are statements that fail to be well-defined in much subtler ways.

Script examples (§2.1.1) (script only)

Statement	Status
71 is a prime number.	true (easy)
If $p$ is prime, then $2^p-1$ is prime.	false. Counterexample: $p=11$, $2^{11}-1=2047=23\cdot 89$
Every natural number is the sum of at most four squares.	true, but needs a sophisticated proof (e.g. $74=6^2+5^2+3^2+2^2$)
Every even natural number $>2$ is the sum of two primes (Goldbach).	unknown
Any $n$ pairwise non-parallel lines in the plane intersect in one point.	false (see the false proof, Example 2.4)
In chess, the first player (“white”) has a winning strategy.	unknown

Example 2.1: “There is no algorithm factoring any $n$-bit integer in $n^3$ steps” is not a precise statement. Its truth depends on the computational model, which theoretical CS has to fix first.

Two uses of stating $S$: (a) claiming that $S$ is true, or (b) merely discussing $S$ (e.g. as an assumption). Keep them apart.

2.3 Composing statements; the implication $⟹$ (Script §2.1.2)

From statements $S,T$ we form new statements:

• Negation: ”$S$ is false.”
• And: ”$S$ and $T$ are (both) true.”
• Or: “At least one of $S$ and $T$ is true.” (Inclusive.)
• Implication (Implikation): “If $S$ is true, then $T$ is true”, written $S⟹T$, read ”$S$ implies $T$”.

Truth value of $S⟹T$

$S⟹T$ is false exactly when $S$ is true and $T$ is false. In all other three cases it is true.
$S⟺T$ means ”$S$ is true if and only if $T$ is true”, i.e. $S⟹T$ and $T⟹S$.

Script examples: the first three are true, the last is false.

• “4 is even $⟹$ 71 is prime” (T ⇒ T: true)
• “5 is even $⟹$ 71 is prime” (F ⇒ T: true)
• “5 is even $⟹$ 70 is prime” (F ⇒ F: true)
• “4 is even $⟹$ 70 is prime” (T ⇒ F: false)

For negation, “and” and “or” between statements there is no symbol in this course. Writing $S\wedge T$ for statements is forbidden here, because $\wedge$ is reserved for formulas (see 2.13).

Exam Trap: implication is not causality

$S⟹T$ only says something about the truth values of $S$ and $T$. The statements need not be related at all. Lecture example: “If it rains, the ground gets wet” looks causal. Its contrapositive (Kontraposition), “If the ground is not wet, it did not rain”, is just as true but makes no causal sense (“not wet” does not cause “no rain”).

Exam Trap: false premise

If $S$ is false, $S⟹T$ is true regardless of $T$: there is “no obligation” to fulfil. And from ”$S⟹T$ is true and $S$ is false” you cannot conclude that $T$ is false (script, after Example 2.2).

Source note (Lecture 1)

The lecturer misspoke twice:

1. He first called $S$ (“101 is prime”) false and argued that $S⟹T$ is therefore true. A student pointed out that 101 is prime; he had a different number from the script in mind. Correct: since $S$ is true, $S⟹T$ has the same truth value as $T$, which is unknown.
2. He once said ”$S⟹T$ is true iff $S$ is true or $T$ is false” and “false if $S$ is false and $T$ is not true”. Both are swapped. Correct (and what he said at the end): $S⟹T$ is true iff $S$ is false or $T$ is true.

2.4 Two meanings of $⟹$ (Script §2.2.3)

In the literature, $⟹$ is used for:

1. the composed statement $S⟹T$ (§2.1.2);
2. a derivation step in a proof.

The script and lecture use a dotted arrow for the second meaning.

Notation: proof step

$S\stackrel{\cdot }{⟹}T$ means: $T$ can be obtained from $S$ by one (simple) proof step. Analogously, $S\stackrel{\cdot }{⟺}T$ means each follows from the other by one simple step.

If $S\stackrel{\cdot }{⟹}T$ holds, then the statement $S⟹T$ is true. The converse fails: $S⟹T$ can be true without a single proof step from $S$ to $T$. This notation is not standard; it is only used in this course.

2.5 The concept of a proof (Script §2.2.5–2.2.8) (mostly script only; the lecture returns to proof patterns in Week 2)

Definition 2.2 (Proof, informal)

A proof (Beweis) of a statement $S$ is a sequence of simple, easily verifiable, consecutive steps. It starts from a set of axioms (postulated to be true) and known (previously proved) facts. Each step applies a derivation rule to a few already proven statements, giving a newly proved statement, until the final step yields $S$.

Proofs differ in which axioms/facts they assume, what counts as “easy to verify”, how much is explicit, and how much notation (like $\stackrel{\cdot }{⟹}$) they use.

There are three reasons for formal proofs: (1) prevention of errors; (2) proof complexity and automatic verification (computers need formalized statements); (3) precision and deeper understanding. There is a trade-off between rigour and readability. Chapters 3–5 use informal proofs; Chapter 6 formalizes proofs.

Role of logic (§2.2.7). Logic answers three questions:

1. In which language are statements written? (syntax)
2. What does it mean for a statement to be true? (semantics)
3. What constitutes a proof from given axioms? (calculus)

Proof levels in this course (§2.2.8)

• Proof sketch / proof idea: the non-obvious ideas, not spelled out with every definition.
• Complete proof: every definition used is explicit, and every step is justified by naming the rule or definition applied.
• Formal proof: entirely phrased in a given proof calculus (e.g. resolution in Chapter 6).

Exercises and exams always say which level is expected and which rules are allowed (confirmed in Lecture 3).

2.6 Propositional logic: symbols, operators, formulas (Script §2.3.1)

Motivation (Lecture 2). Around 1900, paradoxes in natural-language reasoning caused a foundational crisis. Example, the barber paradox: “The barber of Seville shaves exactly those people who do not shave themselves.” Does he shave himself? If yes, he belongs to those who shave themselves, so he must not shave himself. If no, he must shave himself. The answer: build reasoning from the ground up, starting with a formalism in which nothing can go wrong, and then arithmetize it, i.e. compute with statements mechanically, the way one expands $(x+1)(x+2)=x^2+3x+2$ without thinking about graphs.

Building blocks of propositional logic (Aussagenlogik):

• Propositional symbols (Aussagensymbole) $A,B,C,\dots$ (or $A_1,A_2,\dots$). They are like variables (placeholders for basic statements) and take the values $0$ or $1$.
• Logical operators (Operatoren / Junktoren): $\neg$ (NOT), $\wedge$ (AND), $\vee$ (OR), $\to$ (the lecturer calls it just “arrow”, Pfeil), and $\leftrightarrow$.

Definition 2.3 (Logical values)

The logical values (constants) “true” and “false” are denoted $1$ and $0$. They are not the numbers 1 and 0, despite the same symbols.

Definition 2.4 (Negation, conjunction, disjunction)

1. The negation (Negation) $\neg A$ is true iff $A$ is false.
2. The conjunction (Konjunktion) $A\wedge B$ is true iff both $A$ and $B$ are true.
3. The disjunction (Disjunktion) $A\vee B$ is true iff $A$ or $B$ (or both) is true.

As functions: $\neg :\{0,1\}\to \{0,1\}$ and $\wedge ,\vee :\{0,1\}\times \{0,1\}\to \{0,1\}$.

In the lecture these tables are the definitions of the operators. We do not derive them from intuition; we define the computation rules.

$A$	$B$	$\neg A$	$A\wedge B$	$A\vee B$	$A\to B$	$A\leftrightarrow B$
0	0	1	0	0	1	1
0	1	1	0	1	1	0
1	0	0	0	1	0	0
1	1	0	1	1	1	1

Definition 2.5 (Formula)

A correctly formed (well-formed) expression involving the propositional symbols $A,B,C,\dots$ and logical operators is called a formula (Formel) of propositional logic.

Building rules (lecture): every symbol is a formula; if $F,G$ are formulas, then $\neg F$, $(F\wedge G)$, $(F\vee G)$, $(F\to G)$, $(F\leftrightarrow G)$ are formulas. $\neg$ is unary (one operand); the others are binary (a formula on each side). Formulas are named $F,G,H$; symbols $A,B,C$.

Exam Trap (mock interview)

“A formula is an expression of symbols and operators” got only half a point. The well-formedness requirement is missing: $A\wedge \vee B$ is not a formula.

Implication (arrow) and two-sided implication. $A\to B$ is false iff $A=1$ and $B=0$. It is an alternative notation for $\neg A\vee B$ (same function table, see 4.2), so we could drop $\to$ entirely. It is kept because it is intuitive and pleasant to write. $A\leftrightarrow B$ is $1$ iff $A$ and $B$ have the same value; it is equivalent to $(A\to B)\wedge (B\to A)$.

Notational conventions.

• $\neg$ binds stronger than everything else: $\neg A\vee B$ means $(\neg A)\vee B$, and $A\to \neg B$ means $A\to (\neg B)$.
• No other precedence rules are used. When in doubt, parenthesize; extra parentheses are never wrong.
• Because of associativity, $A\wedge B\wedge C$ and $A\vee B\vee C$ may be written without parentheses.
• Negation is written $\neg A$, not $\overline{A}$. Some other courses use the overbar; here it may be misunderstood.
• “Or” is inclusive. An exclusive or (XOR, “entweder … oder”) would be a separate operator, often written $\oplus$, with table $0,1,1,0$. It is not introduced officially.

2.7 Formulas as functions (Script §2.3.2)

Just as the arithmetic expression $(a+b)\cdot c$ defines a function ${\mathbb{N}}^3\to \mathbb{N}$, a formula with $n$ symbols defines a function

$$f_F:\{0,1{\}}^n\to \{0,1\}.$$

Here $\{0,1{\}}^n$ is the set of all $n$-tuples of bits, i.e. all truth assignments (Belegungen). Each element corresponds to one row of the function table, so there are $2^n$ rows (e.g. $n=2$: $\{(0,0),(0,1),(1,0),(1,1)\}$; $n=5$: 32 rows). Since the domain is finite, the function table characterizes the function completely. This is true for propositional logic only, not for predicate logic.

Intuition: formula vs. function

Formula and function are not interchangeable words. Different formulas can induce the same function: $\neg A\vee B$ and $A\to B$ are different formulas with one function. The formula is the syntax (a string or tree); the function is its meaning.

2.8 Logical equivalence, $\top$ and $\perp$ (Script §2.3.3, §2.3.6)

Definition 2.6 (Logical equivalence)

Two formulas $F$ and $G$ are (logically) equivalent (logisch äquivalent), written $F\equiv G$, if they correspond to the same function, i.e. their truth values are equal for all truth assignments to the symbols appearing in $F$ or $G$.

Notation: $\top$ and $\perp$

• $\top$ (“top”) is the formula that is always 1 (a tautology). $\perp$ (“bottom”) is the formula that is always 0 (unsatisfiable).
• They adapt to as many symbols as the context needs.
• $F\equiv \top$: $F$ is a tautology / valid (allgemeingültig). $F\equiv \perp$: $F$ is unsatisfiable (unerfüllbar).
• For every formula $F$: $F\vee \neg F\equiv \top$ and $F\wedge \neg F\equiv \perp$.

Exam Trap

$\top ,\perp$ are formulas, not the constants $1,0$. You substitute $0/1$ into symbols; you cannot substitute $\top$ into a symbol the same way, and $0$ by itself is not a formula (Lecture 2 Q&A). Also: every symbol is a formula, but not every formula is a symbol.

2.9 Basic equivalences: Lemma 2.1 (Script §2.3.3)

Lemma 2.1

1. $A\wedge A\equiv A$ and $A\vee A\equiv A$ (idempotence, Idempotenz)
2. $A\wedge B\equiv B\wedge A$ and $A\vee B\equiv B\vee A$ (commutativity, Kommutativität)
3. $(A\wedge B)\wedge C\equiv A\wedge (B\wedge C)$ and $(A\vee B)\vee C\equiv A\vee (B\vee C)$ (associativity, Assoziativität)
4. $A\wedge (A\vee B)\equiv A$ and $A\vee (A\wedge B)\equiv A$ (absorption, Absorption)
5. $A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$ (first distributive law)
6. $A\vee (B\wedge C)\equiv (A\vee B)\wedge (A\vee C)$ (second distributive law)
7. $\neg \neg A\equiv A$ (double negation, doppelte Negation)
8. $\neg (A\wedge B)\equiv \neg A\vee \neg B$ and $\neg (A\vee B)\equiv \neg A\wedge \neg B$ (de Morgan’s rules)

Proof: each part is checked by a truth table (“brute force”, “Holzhammer”). The tables of both sides agree in every row. Example for 7: $A=0\Rightarrow \neg A=1\Rightarrow \neg \neg A=0$; $A=1\Rightarrow \neg \neg A=1$.

Further simple facts used in the lecture (each provable by a 1- or 2-row truth table):

$$F\wedge \neg F\equiv \perp ,F\vee \neg F\equiv \top ,F\vee \perp \equiv F,F\wedge \top \equiv F.$$

Script examples (script only):

• $A\vee B\equiv \neg (\neg A\wedge \neg B)$. So $\neg$ and $\wedge$ suffice to express every function.
• Example 2.8: $A\leftrightarrow B\equiv (A\to B)\wedge (B\to A)\equiv (A\wedge B)\vee (\neg A\wedge \neg B)$.
• Example 2.9: $(A\wedge \neg B)\vee (B\wedge \neg C)\equiv (A\vee B)\wedge \neg (B\wedge C)$ (verified in 4.6).
• Example 2.10: $(A\wedge B)\vee C\equiv (A\vee C)\wedge (B\vee C)$.

2.10 Logical consequence (Script §2.3.4)

Definition 2.7 (Logical consequence)

A formula $G$ is a logical consequence (logische Folgerung / logische Konsequenz) of a formula $F$, written
$F\models G,$
if for all truth assignments to the symbols appearing in $F$ or $G$, the truth value of $G$ is $1$ whenever the truth value of $F$ is $1$.

How to check with a table: look at only the rows where $F=1$. In each of them $G$ must be $1$. Rows with $F=0$ impose no condition.

Intuition

If we (wrongly, but as a picture) read $0,1$ as numbers, $F\models G$ means $F\le G$ pointwise as functions. Equivalence is then "$=$", consequence is "$\le$", just as $a+b\le a+b+c^2$ holds for all values.

Equivalence vs. consequence (Script §2.3.4)

$F\equiv G⟺F\models G\text{ and }G\models F.$

Exam Trap: footnote 16

Write ”$F\models G$ and $G\models F$” with the word “and”. Never write $F\models G\wedge G\models F$. $\wedge$ only combines formulas, and $F\models G$ is a statement, not a formula.

2.11 Lifting to formulas (Script §2.3.5)

Equivalences and consequences remain valid if the symbols $A,B,C,\dots$ are replaced by arbitrary formulas $F,G,H,\dots$ (consistently). The script states this without proof. The reason (Lecture 3): a truth-table proof only uses the value ($0$ or $1$) that each symbol takes, and a substituted formula also only evaluates to $0$ or $1$. Analogy: $(a+b)c=ac+bc$ for all reals implies $(f+g)h=fh+gh$ for all expressions $f,g,h$.

Example 2.14: since $(A\to B)\wedge (B\to C)\models A\to C$, also $(F\to G)\wedge (G\to H)\models F\to H$ for all formulas $F,G,H$.

A second, related principle used constantly in derivations (Lecture 3): replacing a subformula by an equivalent subformula yields an equivalent formula, because the subformula’s value is the same in every row, so everything around it evaluates the same.

2.12 Tautologies and satisfiability (Script §2.3.6)

Definition 2.8 (Tautology / valid)

A formula $F$ is a tautology (Tautologie) or valid (allgemeingültig) if it is true for all truth assignments of the involved symbols. Notation: $\models F$. “Tautology” and “valid” mean exactly the same.

Definition 2.9 (Satisfiable)

$F$ is satisfiable (erfüllbar) if it is true for at least one truth assignment, and unsatisfiable (unerfüllbar) otherwise.

Examples:

• Example 2.15: $A\vee \neg A$ and $(A\wedge (A\to B))\to B$ are tautologies.
• Example 2.16: $(A\wedge \neg A)\wedge (B\vee C)$ is unsatisfiable; $A\wedge B$ is satisfiable (but not valid).

Notation $\models F$ (Lecture 3)

$\models F$ is shorthand for $\top \models F$. Every assignment makes $\top$ true, so $F$ must be true under every assignment. Hence
$\models F⟺\top \models F⟺F\text{ is a tautology}⟺F\equiv \top .$
(A student noted that $\top \equiv F$ would express the same thing. Correct, but the course uses only $\models F$.)

Lemma 2.2

A formula $F$ is a tautology if and only if $\neg F$ is unsatisfiable.

Lemma 2.3

For any formulas $F$ and $G$: $F\to G$ is a tautology if and only if $F\models G$.

(Proofs in §3.5.)

2.13 Two worlds: statements vs. formulas (Lectures 2 and 3)

This is the single most important conceptual distinction of the week; the lecturer repeated it in every lecture.

Symbol	Name	Input	Output	Defined by
$⟹$	implication	two statements	statement	false iff left true, right false
$\to$	arrow (formula implication)	two formulas	formula	table $1,1,0,1$
$\models$	logical consequence	two formulas	statement	Def. 2.7
$⟺$	equivalence of statements	two statements	statement	both true or both false
$\leftrightarrow$	two-sided implication	two formulas	formula	table $1,0,0,1$
$\equiv$	logical equivalence	two formulas	statement	Def. 2.6
$\wedge ,\vee ,\neg$	and, or, not	formulas	formula	Def. 2.4 (never between statements here)
$\stackrel{\cdot }{⟹}$	proof step	statements	(claim of one derivation step)	§2.2.3

• A statement is always either true or false.
• A formula is in general neither true nor false. It gets a truth value only once all its symbols are assigned. It is a different data type.
• ”$F$ is valid”, ”$F$ is unsatisfiable”, "$F\models G$", "$F\equiv G$" are statements about formulas.

Parsing a mixed line (Lecture 2 Q&A)

$(F\models G\text{ and }G\models F)⟺F\equiv G$
$F$, $G$ are formulas. $F\models G$, $G\models F$ and $F\equiv G$ are statements. “and” joins two statements into a statement; $⟺$ joins two statements into a statement. Likewise, in $A\wedge (A\to B)\models B$, the left and right sides are formulas, and the whole line is a (true) statement.

By convention, anything asserted in the script or lecture is claimed to be true unless stated otherwise.

Source note (Lecture 2)

When introducing $\leftrightarrow$, the lecturer said its table is “exactly XOR … no, NOT XOR”. The correct table is $1,0,0,1$ (the negation of XOR, “XNOR”). He also said $\leftrightarrow$ had “not yet been defined”; the script already defines it in §2.3.1.

2.14 Formulas as trees and functional completeness (Lecture 3; Script §2.3.7*)

A formula can be drawn as a tree:

• leaves are the symbols;
• inner nodes are the operators;
• the root is the outermost operator.

Evaluation proceeds bottom-up (recursively). Script §2.3.7 (starred) adds that such trees correspond to digital circuits: the operators become logic gates (topic of “Digitaltechnik”).

Every function $f:\{0,1{\}}^n\to \{0,1\}$ is induced by some formula. In the lecture poll, almost everyone guessed this correctly. The formula may be exponentially large in $n$. Finding compact formulas is a problem of technical computer science, attacked e.g. by covering the 1-rows of the table with large sub-terms. The lecture stated this without proof; a construction is in §3.9.

2.15 Predicate logic: building blocks (Script §2.4.1–2.4.2; Lecture 3)

Motivation. Propositional logic is too weak. It cannot express “11 is prime” or “there are infinitely many primes”: there are no objects such as numbers to talk about, only 0/1-valued symbols. Predicate logic (Prädikatenlogik) extends it with quantifiers, predicates and functions. It is much more powerful and correspondingly more involved.

Building blocks (the propositional symbols disappear):

Building block	Notation	Description	Examples
universe (Universum)	$U$	the collection of objects we reason about; non-empty	$\mathbb{N}$, $\mathbb{R}$, $\{0,1{\}}^{\ast }$, $\{0,\dots ,6\}$, all humans
predicates (Prädikate)	$P,Q,R,S$	take $k\ge 1$ objects of $U$, output a truth value	$\text{prime}(x)$, $\text{even}(x)$, $\text{less}(x,y)$, $\text{child}(x,y)$
functions (Funktionen)	$f,g,h$ (lower case)	take objects of $U$, output an object of $U$	$\text{square}(x)$, $\text{add}(x,y)$, $\text{mult}(x,y)$
constants (Konstanten)	$a,b,c$	fixed elements of $U$	$0$, $1$, $\pi$; $3$, $5$
operators	$\neg ,\wedge ,\vee ,\to$	as before: truth values in, truth value out
quantifiers (Quantoren)	$\forall x$, $\exists x$	“for all $x$”, “there exists $x$”	$\forall x\exists yP(x,y)$

Definition 2.10 (Predicate)

Let $U$ be a non-empty set (the universe). A $k$-ary predicate $P$ on $U$ is a function
$P:U^k\to \{0,1\}.$
It assigns to each list $(x_1,\dots ,x_k)$ of elements of $U$ the truth value $P(x_1,\dots ,x_k)$.

Examples on $U=\mathbb{N}$:

$$\text{prime}(x)=\{\begin{array}{ll}1& \text{if }x\text{ is prime}\\ 0& \text{else}\end{array}\text{less}(x,y)=\{\begin{array}{ll}1& \text{if }x<y\\ 0& \text{else}\end{array}$$

Binary predicates are often written in infix notation ($x<y$ instead of $\text{less}(x,y)$). With functions and constants, $\text{less}(\text{add}(x,3),\text{add}(x,5))$ is written $x+3<x+5$. It is true for every $x\in \mathbb{N}$, and quantifiers will let us express exactly this (“for all $x$”).

Source note (Lecture 3)

• The lecturer said the universe “need not be a set”. The script defines $U$ as a non-empty set; use the script’s version.
• He first called constants “A, B and C” and then corrected himself, since capital letters are the propositional symbols. Use lower-case $a,b,c$.
• Interpretations (fixing $U$ and the meaning of predicate/function symbols) and quantifiers (Def. 2.11) are treated next week.

---

3. Step-by-Step Derivations & Mathematical Proofs

3.1 The chessboard L-tiling problem (Example 1.1; Lecture 1)

Problem. $P(k)$: “A $k\times k$ chessboard on which an arbitrary square is marked (blocked) can be covered completely and without overlaps by L-shaped pieces of 3 squares each (any rotation allowed).”

$P$ is a predicate $\mathbb{N}\to \{0,1\}$: $P(k)=1$ means the statement is true for $k$. The original question is $P(8)$.

Well-definedness first

Students asked for two clarifications, and both are needed for $P$ to be a statement:

• What is an L-piece? It is $3$ squares forming an “L”, in any orientation.
• What size is the board? Hence the parameter $k$.

$P(0)$ makes no sense: a $0\times 0$ board has no square to mark. So $k\ge 1$.

Step 1: small cases.

• $P(1)=1$ trivially: the only square is marked, nothing remains to cover.
• $P(2)=1$: whichever square of the $2\times 2$ board is marked, the other three form an L.

Theorem (necessary condition, Lecture 1)

$k^2-1/{\equiv }_{3}0⟹P(k)=0.$

Proof. Every L-piece covers exactly $3$ previously uncovered squares. If a tiling uses $t$ pieces, it covers $3t$ squares. The squares to be covered are $k^2-1$, so a tiling forces $k^2-1=3t$, i.e. $3$ divides $k^2-1$. Contrapositive: if $3\nmid k^2-1$, no tiling exists, so $P(k)=0$. $\square$

Which $k$ satisfy the condition? Compute $k^2\mathrm{mod}3$ by cases on $k\mathrm{mod}3$:

$k\mathrm{mod}3$	$k^2\mathrm{mod}3$	$(k^2-1)\mathrm{mod}3$
0	0	2
1	1	0
2	4 ≡ 1	0

So $k^2{\equiv }_{3}1⟺k{\equiv }_{3}1$ or $k{\equiv }_{3}2$ (script’s formulation). Hence $P(k)=0$ for all $k$ divisible by 3 ($P(3)=P(6)=P(9)=\cdots =0$). For $k=3$: $9-1=8{\equiv }_{3}2$, so two squares are always left over.

Exam Trap: necessary is not sufficient

$3\mid k^2-1$ only says there is the right amount of space (an integer number of pieces). It does not prove that a tiling exists. The theorem says nothing when its premise is false: $5^2-1=24$ is divisible by 3, yet $P(5)=0$ according to the script.

Theorem (doubling, Lecture 1; Script §1.2)

$P(k)=1⟹P(2k)=1(k\ge 1).$

Proof (found in the lecture by a student).

1. Take a $2k\times 2k$ board with one marked square. Split it into four $k\times k$ quadrants.
2. The marked square lies in exactly one quadrant. Rotating the board by multiples of $90°$ doesn’t change the problem, so w.l.o.g. it lies in the top-left quadrant $Q_1$.
3. $Q_1$ is a $k\times k$ board with one marked square. By the assumption $P(k)=1$ it can be tiled completely.
4. Look at the four squares at the centre of the big board (one corner square from each quadrant). The three of them belonging to $Q_2,Q_3,Q_4$ form an L-shape. Place one L-piece exactly there. This is the only piece we place explicitly.
5. Now each of $Q_2,Q_3,Q_4$ is a $k\times k$ board with exactly one already-covered square (its centre corner). By $P(k)=1$, each can be tiled completely.
6. All four quadrants are now covered without overlap. $\square$

Why this works for every $k$

We never need to know how the quadrants are tiled (“wie genau weiß der Kuckuck”). The assumption $P(k)=1$ is a “recipe” that works for any marked square, and we use it four times: once with the original marked square, three times with the centre square as the “marked” square. Only the central L is concrete. This is the core idea of induction (formalized in §2.6.10).

Consequences.

• $P(1)=1\Rightarrow P(2)=1\Rightarrow P(4)=1\Rightarrow P(8)=1$. The original problem is solved: the $8\times 8$ board can always be tiled.
• In general $P(2^i)=1$ for all $i\ge 0$. If $P(7)=1$ (script exercise), then $P(7\cdot 2^i)=1$ for all $i$.
• Generalization (exercise, not proved in lecture or script): $P(k)=1$ and $P(\ell )=1⟹P(k\ell )=1$. The lecturer says the proof needs more than “plugging in other numbers” and gives a nice “aha” moment.
• Status per script: $P(1)=P(2)=P(4)=P(7)=P(8)=1$; $P(3)=P(5)=P(6)=P(9)=0$; next open cases $P(10)$, $P(11)$.

Source note (Example 1.1)

• Script: $P(4)=1$ via proof by case distinction (marked square in a corner, on an edge, or in the interior; give a tiling for each). Lecture: $P(4)=1$ via the doubling theorem from $P(2)=1$. Both are valid.
• Script: $P(5)=0$ via counterexample. If the square next to the centre square is marked, the rest cannot be tiled; the script asserts this without the case check. In the lecture, the lecturer was unsure whether $P(5)$ was 0 or 1 and said “clever trial and error”. The script value is $P(5)=0$.

Morals of the example (lecturer): (1) attack a hard instance via simplified instances and look for regularities; (2) abstraction from $8$ to general $k$ made the problem easier, and taught us facts about many $k$ at once.

3.2 Chocolate breaking (Example 1.5; Lecture 1)

Problem. A $6\times 4$ Swiss chocolate bar has 24 pieces. A move takes one current piece and breaks it along one groove. Stacking pieces is not allowed. What is the minimal number of moves to get 24 single pieces?

Claim

Every strategy needs exactly $23$ breaks; in general an $m\times n$ bar needs exactly $mn-1$.

Proof (invariant).

1. Before any move there is $1$ piece.
2. Each move takes one piece and replaces it by two, so the number of pieces increases by exactly 1.
3. By repeating this, after $j$ moves there are exactly $j+1$ pieces, independently of the strategy.
4. We are done exactly when there are $24$ pieces, i.e. after $j=23$ moves.
5. Hence minimum = maximum = $23$; for $m\times n$ it is $mn-1$. $\square$

Exam Trap

Students’ answers of 15, 18 and 21 in the lecture came from breaking several pieces at once along a full line. That is the forbidden “stacking”. With the rule “one piece per move”, the answer 23 holds for every strategy. Questions like “Is it better to halve first or break off a row?” have the answer “it doesn’t matter”.

The abstraction

The only thing that matters is “pieces $=$ moves $+1$”. Everything else (shape, chocolate, grooves) is irrelevant. A problem with the same abstraction (my addition): a knock-out tournament with $n$ players needs exactly $n-1$ matches, because each match eliminates exactly one player.

3.3 Proof that $2^{143}-1$ is not prime (Example 2.2) (script only)

Claim. $n$ is not prime $⟹2^n-1$ is not prime.

Proof.

1. If $n$ is not prime, then $n=ab$ with $1<a<n$ (definition of prime), so also $1<b$.
2. Factor using the geometric sum:

$$2^{ab}-1=(2^a-1)\sum _{i=0}^{b-1}{2}^{ia}=(2^a-1)(2^{(b-1)a}+2^{(b-2)a}+\cdots +2^a+1).$$

(Multiply out: the sum telescopes to $2^{ab}-1$.)
3. Since $a>1$, we have $2^a-1>1$. Since $a<ab$, we have $2^a-1<2^{ab}-1$.
4. So $2^a-1$ is a non-trivial divisor of $2^{ab}-1$, which is therefore not prime. $\square$

Application: $143=11\cdot 13$, so $2^{11}-1=2047$ divides $2^{143}-1$.

Exam Trap

The converse ”$n$ prime $⟹2^n-1$ prime” is false ($n=11$). From ”$S⟹T$ is true” you cannot conclude "$\neg S⟹\neg T$".

3.4 A proof as a chain of steps (Example 2.3) (script only)

Claim. If $a$ and $b$ are squares, then so is $ab$. ($n$ is a square if $n=m\cdot m$ for some integer $m$.)

$$\begin{array}{rlrl}& a\text{ and }b\text{ are squares}& & \\ \stackrel{\cdot }{⟹}& a=u\cdot u\text{ and }b=v\cdot v\text{ for some }u,v& & \text{(def. of square)}\\ \stackrel{\cdot }{⟹}& a\cdot b=(u\cdot u)\cdot (v\cdot v)& & \text{(substitution)}\\ \stackrel{\cdot }{⟹}& a\cdot b=(u\cdot v)\cdot (u\cdot v)& & \text{(commutative and associative laws)}\\ \stackrel{\cdot }{⟹}& a\cdot b\text{ is a square}& & \text{(def. of square)}\end{array}$$

Every step names its justification. Proofs may also be non-linear (§2.2.4): from true $S_1,S_2$ one may prove $S_1\stackrel{\cdot }{⟹}{S}_3$, $S_1\stackrel{\cdot }{⟹}{S}_4$, $S_2\stackrel{\cdot }{⟹}{S}_5$, ”$S_3$ and $S_5$” $\stackrel{\cdot }{⟹}{S}_6$, ”$S_1$ and $S_4$” $\stackrel{\cdot }{⟹}{S}_7$, and finally ”$S_6$ and $S_7$” $\stackrel{\cdot }{⟹}T$.

3.5 Proofs of Lemma 2.2, Lemma 2.3, and $F\equiv G⟺(F\models G$ and $G\models F)$

Lemma 2.2 (the script omits this proof since it follows from the definitions). $F$ is a tautology $⟺$ $F$ takes value $1$ under every assignment $⟺$ $\neg F$ takes value $0$ under every assignment (definition of $\neg$) $⟺$ $\neg F$ is unsatisfiable (Def. 2.9). $\square$

Lemma 2.3. $F\to G$ is a tautology $⟺F\models G$.

Proof. Two directions.

• ($⟹$) Assume $F\to G$ is a tautology. Fix any assignment. By the table of $\to$, the pair $(F,G)$ of truth values is $(0,0)$, $(0,1)$ or $(1,1)$; never $(1,0)$, since that would make $F\to G=0$. In each of the three cases, if $F=1$ then $G=1$. As the assignment was arbitrary, $F\models G$.
• ($⟸$) Assume $F\models G$. Then no assignment makes $F=1$ and $G=0$. That combination is the only row where $\to$ gives $0$, so $F\to G$ evaluates to $1$ under every assignment, i.e. it is a tautology. $\square$

In Lecture 3 this was presented as the “observation”:

$$(F\to G\text{ is valid})⟺F\models G,\text{equivalently}\models (F\to G)⟺F\models G.$$

$F\equiv G⟺F\models G$ and $G\models F$.

• ($⟹$) If $F$ and $G$ agree everywhere, then $F=1$ implies $G=1$ and vice versa.
• ($⟸$) Suppose some assignment gave different values. Either $F=1,G=0$, contradicting $F\models G$, or $F=0,G=1$, contradicting $G\models F$. So they agree everywhere. $\square$

3.6 Modus ponens: tautology by truth table and by algebra (Lectures 2 and 3)

Claim (Example 2.15, Lecture 2): $A\wedge (A\to B)\models B$, equivalently (Lemma 2.3) $(A\wedge (A\to B))\to B$ is a tautology.

Method 1: truth table.

$A$	$B$	$A\to B$	$A\wedge (A\to B)$	$(A\wedge (A\to B))\to B$
0	0	1	0	1
0	1	1	0	1
1	0	0	0	1
1	1	1	1	1

The last column is all 1s, so it is a tautology. The only row with $A\wedge (A\to B)=1$ is row 4, where $B=1$, so $\models$ holds.

Method 2: algebraic derivation (Lecture 3). This scales to larger formulas where truth tables explode.

$$\begin{array}{rlrl}A\wedge (A\to B)& \equiv A\wedge (\neg A\vee B)& & \text{(replace subformula: }A\to B\equiv \neg A\vee B)\\ & \equiv (A\wedge \neg A)\vee (A\wedge B)& & \text{(Lemma 2.1, 5: first distributive law)}\\ & \equiv \perp \vee (A\wedge B)& & (F\wedge \neg F\equiv \perp )\\ & \equiv (A\wedge B)\vee \perp & & \text{(Lemma 2.1, 2: commutativity of }\vee )\\ & \equiv A\wedge B& & (F\vee \perp \equiv F)\\ & \models B& & (A\wedge B\models B\text{, 4-row truth table})\end{array}$$

Why each step is legitimate:

• Step 1 uses that $A\to B$ and $\neg A\vee B$ have identical tables (Lecture 2). Replacing a subformula by an equivalent one does not change the value of the surrounding formula in any row (§2.11).
• Step 2 instantiates Lemma 2.1(5) with $A:=A$, $B:=\neg A$, $C:=B$. This is allowed by lifting (§2.11).
• Step 3 makes things “more complicated first in order to simplify later”: the distributive law created the contradictory subformula $A\wedge \neg A$, which we can now kill.
• Step 4 is only a reordering, so that the rule $F\vee \perp \equiv F$ applies in exactly the form it is stated. (Proving $\perp \vee F\equiv F$ directly would have saved this step.)
• Final step: a chain of $\equiv$ ending in $\models$ gives $\models$ overall. Equal tables followed by "$\le$" is "$\le$".

Every step must use either a proven rule or something provable on the side (a small truth table).

Then by Lemma 2.3 with $F:=A\wedge (A\to B)$, $G:=B$, the formula $(A\wedge (A\to B))\to B$ is a tautology. The two directions are “equivalent as statements”.

Exam Trap: which rules may I use?

In the exam, the task specifies the allowed rules (e.g. “using only Lemma 2.1”, with the lemma reprinted). You then have to stick to them. Small helper facts like $F\vee \perp \equiv F$ are either explicitly allowed or must be justified by a side truth table. Not every proof has to be in formal logic: the task says whether a formal-logic proof or a normal proof is wanted.

3.7 Modus ponens as a proof strategy (Lecture 3)

The tautology $(A\wedge (A\to B))\to B$ inspires a proof strategy for statements:

Proof strategy: Modus ponens

Goal: prove a statement $S$.

1. Find a suitable statement $R$.
2. Prove $R$.
3. Prove $R⟹S$.

Then $S$ is proved.

Points the lecturer stressed:

• $R,S$ are statements, connected by $⟹$ (double arrow), not formulas.
• In the formula world the strategy is a theorem: we proved $A\wedge (A\to B)\models B$, and by lifting it holds for any formulas.
• Transferring it to the statement world (proofs in natural language) is a heuristic that is universally accepted. We cannot prove ”$R$ and ($R⟹S$) $⟹S$” for arbitrary statements, because we haven’t formally defined what a statement is. That is the sense of “inspired”.
• Modus ponens doesn’t tell you how to prove $R$: it turns one problem into three (find $R$, prove $R$, prove $R⟹S$). The point is that these should be easier.
• Transitivity (Example 2.13), $(A\to B)\wedge (B\to C)\models A\to C$, inspires a second strategy: to prove $A⟹C$, prove $A⟹B$ and $B⟹C$ for an intermediate claim $B$. Week 2 covers proof patterns systematically.

3.8 Proof of transitivity (Example 2.13)

Claim. $(A\to B)\wedge (B\to C)\models A\to C$.

Proof (contrapositive style, equivalent to checking the table). We must show there is no assignment with the left side $=1$ and $A\to C=0$.

• $A\to C=0$ forces $A=1,C=0$.
• If $B=0$: $A\to B=1\to 0=0$, so the left side is $0$.
• If $B=1$: $B\to C=1\to 0=0$, so the left side is $0$.

In both remaining rows the left side is $0$, so whenever the left side is $1$, the right side is $1$. $\square$

The full table has 8 rows. The lecturer suggested computing columns $A\to B$, $B\to C$, their $\wedge$, and $A\to C$, then comparing.

3.9 Every Boolean function is a formula (supplement: claimed in Lecture 3, construction added here)

Claim. For every $n\ge 1$ and every $f:\{0,1{\}}^n\to \{0,1\}$ there is a formula $F$ in $A_1,\dots ,A_n$ inducing $f$.

Construction.

1. For each $a=(a_1,\dots ,a_n)$ with $f(a)=1$, define the minterm $M_a=L_1\wedge \cdots \wedge L_n$, where $L_i=A_i$ if $a_i=1$ and $L_i=\neg A_i$ if $a_i=0$.
2. $M_a$ evaluates to $1$ exactly at the assignment $a$: all literals are $1$ there, and at any other assignment some $L_i$ is $0$.
3. Let $F={\bigvee }_{a:f(a)=1}{M}_a$. Then $F=1$ iff the assignment equals some $a$ with $f(a)=1$, i.e. iff $f=1$. If $f$ is never $1$, take $F=A_1\wedge \neg A_1$.
4. $F$ can have up to $2^n$ minterms, so it is exponentially large in the worst case, matching the lecturer’s remark. By de Morgan, $\vee$ can be replaced by $\neg$ and $\wedge$, so these two operators suffice (script §2.3.3). $\square$

---

4. Worked Examples & Applications

4.1 $\neg A\vee B$ vs. $A\to B$ (Lecture 2)

Evaluate $\neg A$ first (it binds strongest), then OR with $B$:

$A$	$B$	$\neg A$	$\neg A\vee B$	$A\to B$	$(\neg A\vee B)\wedge (A\to B)$
0	0	1	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	1	0	1	1	1

• Row 1: $\neg A=1$, and $1\vee$ anything $=1$. The result is $0$ only when $\neg A=0$ and $B=0$, i.e. row 3.
• Columns 4 and 5 agree: $\neg A\vee B\equiv A\to B$.

Tip from the lecture: for complex formulas, write intermediate columns for the subformulas first. For the last column you then only need to AND columns 4 and 5, which are always $1,1$ or $0,0$.

4.2 Flatmate search (WG-Mitbewohner, Lecture 2)

Candidates $A,B,C$, where $A=1$ means “A moves in”; any number from 0 to 3 may move in. Three current flatmates’ opinions are formulas:

$$F=(A\vee B)\wedge \neg C,G=B\vee C,H=\neg B\vee A.$$

$F$: “A or B is fine, but definitely not C”. $G$: “B or C, and A doesn’t matter”. $H=(\neg B)\vee A$: “either B doesn’t move in or A does”. $H$ has nothing against B per se; $H\equiv B\to A$.

$A$	$B$	$C$	$F$	$G$	$H$	$F\wedge G$	$F\wedge G\wedge H$
0	0	0	0	0	1	0	0
0	0	1	0	1	1	0	0
0	1	0	1	1	0	1	0
0	1	1	0	1	0	0	0
1	0	0	1	0	1	0	0
1	0	1	0	1	1	0	0
1	1	0	1	1	1	1	1
1	1	1	0	1	1	0	0

Computing the columns:

• $F$: $A\vee B$ is $0$ in rows 1–2, so $F=0$ there. Otherwise $F=\neg C$: 1 when $C=0$ (rows 3, 5, 7), 0 when $C=1$.
• $G$: $0$ only when $B=C=0$ (rows 1, 5).
• $H$: $0$ only when $B=1$ and $A=0$ (rows 3, 4).
• $F\wedge G$: $1$ in rows 3 and 7, i.e. “only B” or “A and B”.
• $F\wedge G\wedge H$ (everybody happy): row 3 fails because $H=0$, so only row 7 remains: A and B move in, C does not. Check: $F=(1\vee 1)\wedge \neg 0=1$, $G=1\vee 0=1$, $H=\neg 1\vee 1=0\vee 1=1$.

Because the solution is unique, $F\wedge G\wedge H\equiv A\wedge B\wedge \neg C$. This is exactly the minterm of row 7 (cf. §3.9). Adding the requirement $\neg A$ gives $F\wedge G\wedge H\wedge \neg A\equiv \perp$ (an all-zero column), which is unsatisfiable. $F\wedge G\wedge H$ itself is satisfiable but not valid.

Source note (Lecture 2)

The lecturer’s prepared notes said “there is no solution”. Re-checking the table on the board, he found that his notes contained a computation error. Correct: exactly one solution, $A=B=1$, $C=0$. He also briefly doubted the $F\wedge G$ column; it is correct as above.

4.3 Logical consequence checks (Lecture 2, Script 2.11–2.12)

• $A\wedge B\models A$ and $A\wedge B\models B$: $A\wedge B=1$ only for $A=B=1$, where both $A$ and $B$ are $1$. The converse fails: at $A=1,B=0$ the right side $A$ is $1$ but the left is $0$. That is allowed for $\models$ but rules out $\equiv$.
• $G/\models H$ (flatmates): row 3 ($A=0,B=1,C=0$) has $G=1$ but $H=0$. The lecturer first pointed at the wrong row (row 5) and then corrected to row 3.
• Example 2.11: $A\wedge B\models A\vee B$. The left side is $1$ only at $(1,1)$, where $A\vee B=1$.
• Example 2.12: $(A\wedge B)\vee (A\wedge C)\models \neg B\to (A\vee C)$. If the left side is $1$, then $A=1$, so $A\vee C=1$, so the implication is $1$. The two formulas are not equivalent: at $A=0,B=1,C=0$ the right side is $\neg 1\to \cdots =0\to 0=1$, while the left side is $0$.

4.4 Script truth tables (§2.3.1) and Example 2.9

$A$	$B$	$C$	$A\vee (B\wedge C)$	$(A\wedge \neg B)\vee (B\wedge \neg C)$	$(A\vee B)\wedge \neg (B\wedge C)$
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	1	0	0
1	0	0	1	1	1
1	0	1	1	1	1
1	1	0	1	1	1
1	1	1	1	0	0

Columns 5 and 6 agree, which verifies Example 2.9. Spot check for row 4 ($0,1,1$): $(0\wedge 0)\vee (1\wedge 0)=0$, and $(0\vee 1)\wedge \neg (1)=0$.

4.5 The tree of $(A\vee B)\wedge (A\vee C)\wedge (\neg A\vee \neg C)$ (Lecture 3)

                 ∧
       ┌─────────┼──────────┐
       ∨         ∨          ∨
      / \       / \        / \
     A   B     A   C      ¬   ¬
                          |   |
                          A   C

Evaluation is bottom-up. At $A=B=C=0$, the first $\vee$ gives $0$, so the root gives $0$. At $A=0,B=1,C=0$, the second $\vee$ gives $0$, so again $0$. At $A=0,B=1,C=1$: $1\wedge 1\wedge (1\vee 0)=1$.

(The transcript only describes the tree; the formula is reconstructed from it.)

4.6 A false proof: “1 < 0” (Lecture 3)

“Theorem”: $1<0$.

$$\begin{array}{rlrl}1<0& \stackrel{\cdot }{⟹}2<1& & (+1\text{ on both sides})\\ & \stackrel{\cdot }{⟹}2>1& & (\cdot 1\text{ on both sides; }1<0\text{, so }1\text{ is "negative" and the inequality flips})\end{array}$$

$2>1$ is true, so ”$1<0$ is proved”?

What went wrong. Each individual step is a valid manipulation. A student asked whether the second step should be $\cdot (-1)$; it is intentionally $\cdot 1$, using the assumed $1<0$. The error is that we started from the claim itself and derived a true statement. We showed "$S⟹R$" (with $S$: $1<0$, $R$: $2>1$) and ”$R$ is true”, and concluded $S$. That is modus ponens backwards: ”$R$ and $(S⟹R)$ $⟹S$” is not a valid pattern.

In the formula world: $(B\wedge (A\to B))\to A$ is not a tautology. At $A=0,B=1$: $(1\wedge (0\to 1))\to 0=(1\wedge 1)\to 0=0$.

Exam Trap: circular proofs

Deriving something true from the claim proves nothing. From a false statement you can derive true statements. A valid proof derives the claim from known facts. This error is different from the one in the script’s false proofs (Examples 2.4 and 2.5).

4.7 A false proof by induction: “all lines meet in one point” (Example 2.4) (script only)

“Claim”: any $n$ pairwise non-parallel lines in the plane pass through one common point.

“Proof”:

• Base case $n=2$: two non-parallel lines meet in a point.
• Step: given ${\ell }_1,\dots ,{\ell }_{n+1}$, the lines ${\ell }_1,\dots ,{\ell }_n$ meet in a point $P$, and ${\ell }_1,\dots ,{\ell }_{n-1},{\ell }_{n+1}$ meet in a point $Q$.
• ${\ell }_1$ and ${\ell }_{n-1}$ lie in both groups, so both contain $P$ and $Q$. Two distinct non-parallel lines meet in only one point, so $P=Q$.

What is wrong? (the script asks "Something must be wrong! (What?)")

The step $n\to n+1$ needs two distinct lines ${\ell }_1$ and ${\ell }_{n-1}$ in both groups. For $n=2$, i.e. the step from 2 to 3 lines, we have ${\ell }_{n-1}={\ell }_1$. The groups $\{{\ell }_1,{\ell }_2\}$ and $\{{\ell }_1,{\ell }_3\}$ share only one line, so nothing forces $P=Q$. The step from 2 to 3 fails, so the chain breaks immediately. The step argument does work for $n\ge 3$, but that is useless without $2\to 3$. Moral: check that the induction step is valid for every $n$ from the base case on.

4.8 Mock-interview exercise (Lecture 3, Moodle “Mock Interview”)

The exact sheet wasn’t visible in the recording; the formulas below are reconstructed from the spoken solution and are consistent with every value stated.

(a) “What is a formula of propositional logic?” A well-formed (correctly formed) expression built from propositional symbols and logical operators (Def. 2.5).

(b) “What does $F\models G$ mean? How would you show it?” For every truth assignment under which $F$ evaluates to $1$, $G$ also evaluates to $1$. Two ways to show it:

1. A truth table: check every row with $F=1$.
2. Show that $F\to G$ is a tautology (Lemma 2.3). This was the extra question.

(c) New operator $\diamond$ with table $A\diamond B=0,1,1,0$ (rows $00,01,10,11$), i.e. XOR. Compute the table of $F=((A\diamond B)\wedge A)\vee B$:

$A$	$B$	$A\diamond B$	$(A\diamond B)\wedge A$	$F$
0	0	0	0	0
0	1	1	0	1
1	0	1	1	1
1	1	0	0	1

Follow-up question, simplify $F$: the column is $0,1,1,1$, so $F\equiv A\vee B$.

Exam Trap (interview)

Showing only the final column (“0,1,1,1”) is not enough. You must show the intermediate steps.

(d) Define an operator $♡$ such that
$((B\to A)\to \neg (A♡B))\wedge ((A\vee \neg B)\vee (A♡B))$
is a tautology. First: a tautology is a formula that evaluates to $1$ for every assignment.

• Strategy: a conjunction is a tautology iff both conjuncts are.
• Left conjunct: $B\to A$ is $0$ only at $A=0,B=1$. In the other three rows ($00$, $10$, $11$) the premise is $1$, so we need $\neg (A♡B)=1$, i.e. $A♡B=0$. Row $01$ is unconstrained (”?”).
• Right conjunct: $A\vee \neg B$ is $0$ only at $A=0,B=1$. There we need $A♡B=1$. Elsewhere unconstrained.
• Combined: $A♡B=0,1,0,0$ (rows $00,01,10,11$), i.e. $A♡B\equiv \neg A\wedge B$.

In the mock, the student first gave $1,1,0,0$ (wrong), because he had computed $B\to A$ as false at $B=0,A=1$ instead of $B=1,A=0$. A check of row $00$ exposed this: $1\to 0$.

Exam Trap: the most common slip

$X\to Y$ is $0$ only for $X=1,Y=0$. For $B\to A$ that is $B=1,A=0$, not the other way round. Also: before the interview, verify your solution in at least one row.

Mock grading: (a) 0.5/1 (well-formedness missing), (b) 1/1, (c) 1/1, simplification 1/1, (d) 1/2 (needed hints), extra question +1. Extra questions make up for lost points, capped at 6.

---

5. Intuition & Conceptual Bridges

Formulas are to statements what polynomials are to numbers

A polynomial $x^2+3x+2$ is not a number; it becomes one when you plug in $x$. A formula $A\wedge \neg B$ is not true or false; it becomes so when you plug in values for $A$ and $B$. ”$x^2+3x+2=(x+1)(x+2)$ for all $x$” is a statement about polynomials. In the same way, "$\neg (A\wedge B)\equiv \neg A\vee \neg B$" is a statement about formulas. Lemma 2.1 is the “algebra rule sheet” of this arithmetic.

$\models$ is "$\le$" and $\equiv$ is "$=$"

If you picture each formula as its column of 0/1 values, $F\models G$ means “column $F$ $\le$ column $G$ in every row” and $F\equiv G$ means “the columns are equal”. Many facts follow at once:

• $F\equiv G⟺F\le G$ and $G\le F$;
• $\perp \le F\le \top$, so $\perp \models F$ and $F\models \top$ for every $F$;
• $\models F$ means $\top \le F$, i.e. $F=\top$;
• a chain $\equiv ,\equiv ,\dots ,\models$ gives $\models$.

Why $\to$ is true when the premise is false

Think of $A\to B$ as a promise: “if $A$ happens, I guarantee $B$”. The promise is only broken when $A$ happens and $B$ doesn’t. If $A$ never happens, the promise was not broken, so it counts as kept (true). That is all; there is no causality involved.

The two teasers are about invariants and reduction

• Chocolate: find a quantity that changes predictably with each move (“pieces $-$ moves $=1$”). Then the answer doesn’t depend on the strategy. Invariants return in algorithm analysis (loop invariants) and in group theory.
• Chessboard: reduce size $2k$ to size $k$, using the smaller solution as a black box. This is the template of induction and recursion, and of divide-and-conquer algorithms (formal induction: §2.6.10).
• The counting argument ($3\mid k^2-1$) is your first modular arithmetic (${\equiv }_3$), formalized in Chapter 4.

Connections across the course.

• Backwards: this week builds the vocabulary everything else uses. Statements, proofs, $⟹$ versus $\to$.
• Next week (Week 2): quantifiers $\forall ,\exists$ in detail (Def. 2.11), nested quantifiers, interpretations, the rules in §2.4.8 such as $\neg \forall xP(x)\equiv \exists x\neg P(x)$, formulas vs. statements (§2.5), and proof patterns (§2.6): direct proof, contrapositive, contradiction, case distinction, counterexample, induction. Modus ponens and transitivity are the first of these.
• Chapters 3–5: set theory, number theory (congruences ${\equiv }_m$, Fermat test of Example 1.2), algebra (groups, rings, fields; Examples 1.3, 1.4, 1.8 about cancellation, interpolation and Euclid’s algorithm).
• Chapter 6: fully formal logic. Syntax vs. semantics, proof calculi, resolution. Lemma 2.1 and logical consequence come back rigorously, and “mechanical transformation from left to right” replaces truth tables.

Other teasers from Script §1.2–1.3 (not discussed in lecture)

• 1.2 (Fermat test): Is odd $n$ prime $⟺2^{n-1}{\equiv }_{n}1$? It holds for small primes and fails for small composites. The answer comes in Chapter 4: the "$\Leftarrow$" direction is false. The smallest counterexample, $341=11\cdot 31$, satisfies $2^{340}{\equiv }_{341}1$ (my addition).
• 1.3 (cancellation law): $ab=ac,a\ne 0\Rightarrow b=c$. Does it hold for polynomials, for integers mod $m$, for permutations? This is an algebra question (Chapter 5).
• 1.4 (interpolation): A degree-$d$ polynomial is determined by $d+1$ values. Does this survive over finite domains (e.g. mod 5, with $5^3=125$ polynomials of degree $\le 2$)? Chapter 5 (finite fields).
• 1.6: Can the shape in Fig. 1.1 be cut into 9 identical pieces? Find the abstraction.
• 1.7: Continue $0,1,1,3,5,11,21,43,85,\dots$. Several rules fit; one is $a_n=a_{n-1}+2a_{n-2}$ (my addition).
• 1.8: Euclid’s gcd algorithm works for integers and polynomials. The common abstraction is the Euclidean domain, a special integral domain, which is a special ring (Chapter 5).

---

6. Summary & Self-Assessment Questions

Cheat sheet

Concept	Definition / fact
Statement (Aussage)	true or false in an absolute sense (Def. 2.1)
$S⟹T$	false iff $S$ true and $T$ false; no causality
$S\stackrel{\cdot }{⟹}T$	$T$ follows from $S$ by one proof step
Formula	well-formed expression of symbols and operators (Def. 2.5)
$A\to B$	table $1,1,0,1$; $\equiv \neg A\vee B$
$A\leftrightarrow B$	table $1,0,0,1$; $\equiv (A\to B)\wedge (B\to A)$
Precedence	$\neg$ binds strongest; otherwise parenthesize
Formula ↦ function	$f_F:\{0,1{\}}^n\to \{0,1\}$, $2^n$ rows
$F\equiv G$	same value under all assignments (Def. 2.6)
$F\models G$	$F=1\Rightarrow G=1$ under all assignments (Def. 2.7)
$F\equiv G$	iff $F\models G$ and $G\models F$
Tautology / valid	true under all assignments; $\models F$; $F\equiv \top$ (Def. 2.8)
Satisfiable	true under at least one assignment (Def. 2.9)
Unsatisfiable	$F\equiv \perp$
Lemma 2.2	$F$ tautology $⟺\neg F$ unsatisfiable
Lemma 2.3	$F\to G$ tautology $⟺F\models G$
Lemma 2.1	idempotence, commutativity, associativity, absorption, two distributive laws, double negation, de Morgan
Extra rules	$F\wedge \neg F\equiv \perp$, $F\vee \neg F\equiv \top$, $F\vee \perp \equiv F$, $F\wedge \top \equiv F$
Lifting	laws hold with symbols replaced by formulas; equivalent subformulas can be swapped
Modus ponens	$A\wedge (A\to B)\models B$; strategy: find $R$, prove $R$, prove $R⟹S$
Transitivity	$(A\to B)\wedge (B\to C)\models A\to C$
Invalid	$(B\wedge (A\to B))\to A$ is not a tautology (proving the claim backwards)
Chessboard	$3\nmid k^2-1\Rightarrow P(k)=0$ (i.e. $3\mid k$); $P(k)=1\Rightarrow P(2k)=1$; $P(8)=1$
Chocolate	$m\times n$ bar needs exactly $mn-1$ breaks
$k$-ary predicate	$P:U^k\to \{0,1\}$, $U$ a non-empty set (Def. 2.10)

Source notes: where lecture and correct version differ

1. L1: 101 is prime (first called false); so "$S⟹T$" has the unknown truth value of $T$.
2. L1: truth condition of $⟹$ was misspoken once. Correct: true iff $S$ false or $T$ true.
3. L1: $P(5)$: the lecturer was unsure; the script says $P(5)=0$. $P(4)$: case distinction in the script, doubling in the lecture.
4. L2: "$A\vee A$" as a tautology was misspoken; it is $A\vee \neg A$.
5. L2: flatmates: the notes said “no solution”; correct is the unique solution $A=B=1,C=0$.
6. L2: $\leftrightarrow$ is not XOR but its negation; it is already defined in the script.
7. L3: the universe is a non-empty set (script); constants are $a,b,c$ in lower case.

Self-assessment questions

Question 1. For each sentence, decide (i) whether it is a well-defined mathematical statement and (ii) if so, its truth value or that it is unknown:
(a) ”$5$ is even $⟹$ $70$ is prime.”
(b) ”$2^{11}-1$ is prime $⟹$ $4$ is even.”
(c) “There are infinitely many twin primes $⟹$ $101$ is prime.”
(d) “The sentence you are reading right now is false.”
(e) ”$101$ is prime $⟹$ there are infinitely many twin primes.”

Solution to Question 1

(a) Well-defined. Premise false, so the implication is true (F ⇒ F).
(b) Well-defined. $2^{11}-1=2047=23\cdot 89$ is not prime, so the premise is false and the implication is true. (The conclusion is also true.)
(c) Well-defined. The conclusion is true, so the implication is true no matter what the premise is, even though the premise is an open problem.
(d) Not well-defined: self-reference. If true, then false; if false, then true.
(e) Well-defined. The premise is true, so the implication’s value equals that of the twin-prime conjecture: unknown. (This is the corrected version of the lecture example.)

Question 2. Using only Lemma 2.1 plus the facts $F\vee \neg F\equiv \top$ and $F\wedge \top \equiv F$ (and lifting), prove
$\neg (A\vee (\neg A\wedge B))\equiv \neg A\wedge \neg B.$

Solution to Question 2

First simplify the inner formula:

$$\begin{array}{rlrl}A\vee (\neg A\wedge B)& \equiv (A\vee \neg A)\wedge (A\vee B)& & \text{(Lemma 2.1, 6: second distributive law, with }B:=\neg A,C:=B)\\ & \equiv \top \wedge (A\vee B)& & (F\vee \neg F\equiv \top )\\ & \equiv (A\vee B)\wedge \top & & \text{(Lemma 2.1, 2: commutativity of }\wedge )\\ & \equiv A\vee B& & (F\wedge \top \equiv F)\end{array}$$

Replacing this subformula under the $\neg$ by its equivalent (equivalent subformulas may be swapped):
$\neg (A\vee (\neg A\wedge B))\equiv \neg (A\vee B)\equiv \neg A\wedge \neg B\text{(Lemma 2.1, 8: de Morgan)}.$
$\square$ Check one row: $A=0,B=0$. Left: $\neg (0\vee (1\wedge 0))=\neg 0=1$. Right: $1\wedge 1=1$.

Question 3. Let $F=(A\vee B)\wedge \neg C$, $G=B\vee C$ and $H=\neg B\vee A$ (flatmate example). Decide, with justification: (a) $F\models G$? (b) $F\wedge G\models H$? (c) $F\wedge G\wedge H\models A$? (d) Is $F\wedge G\wedge H\wedge \neg B$ satisfiable?

Solution to Question 3

Use the table in §4.2.
(a) No. $F=1$ in rows $010,100,110$. In row $100$, $G=0\vee 0=0$. Counterexample: $A=1,B=0,C=0$.
(b) No. $F\wedge G=1$ in rows $010$ and $110$. In row $010$, $H=\neg 1\vee 0=0$.
(c) Yes. $F\wedge G\wedge H=1$ only in row $110$, where $A=1$.
(d) No. $F\wedge G\wedge H$ is $1$ only at $B=1$, so adding $\neg B$ leaves no satisfying row. The formula is $\equiv \perp$.

Question 4. (a) Prove that $(B\wedge (A\to B))\to A$ is not a tautology. (b) Explain why this shows that the “proof” of $1<0$ in §4.6 is invalid, even though each algebraic step was correct. (c) Using Lemma 2.3, what statement about $\models$ is equivalent to (a)?

Solution to Question 4

(a) Take $A=0,B=1$: $A\to B=0\to 1=1$, so $B\wedge (A\to B)=1$, and the formula is $1\to 0=0$. One falsifying assignment suffices.
(b) The “proof” had the shape: from $S$ ($1<0$) derive $R$ ($2>1$), observe $R$ is true, conclude $S$. That is the pattern ”$R$ and ($S⟹R$), therefore $S$”. Its formula counterpart (with $A:=S$, $B:=R$) is exactly the non-tautology from (a). The pattern can lead from a true $R$ to a false $S$. Correct steps don’t help if the overall reasoning pattern is invalid. The proof assumed what it wanted to show.
(c) By Lemma 2.3, ”$F\to G$ is a tautology” $⟺F\models G$. So (a) is equivalent to $B\wedge (A\to B)/\models A$.

Question 5. (a) Show that $P(k)=0$ whenever $3\mid k$. (b) Using only the doubling theorem and $P(1)=1$, list all $k\le 40$ for which $P(k)=1$ follows. If you additionally know $P(5)=0$, can you conclude anything about $P(10)$? (c) In the proof of the doubling theorem, where exactly is the hypothesis $P(k)=1$ used, and why must it hold for every marked square?

Solution to Question 5

(a) If $k=3m$, then $k^2-1=9m^2-1{\equiv }_3-1{\equiv }_{3}2$. So $3\nmid k^2-1$, and by the counting theorem (each L covers 3 squares, so $3t=k^2-1$ would be needed) $P(k)=0$.
(b) $P(1)=1\Rightarrow P(2)\Rightarrow P(4)\Rightarrow P(8)\Rightarrow P(16)\Rightarrow P(32)$. So $k\in \{1,2,4,8,16,32\}$. With $P(7)=1$ (script exercise) you would also get $14,28$.
$P(5)=0$ tells us nothing about $P(10)$. The theorem $P(k)=1⟹P(2k)=1$ has a false premise for $k=5$, and a false premise makes the implication true without saying anything about the conclusion. (Also $10^2-1=99$ is divisible by 3, so the counting theorem doesn’t exclude it either. $P(10)$ is listed as open in the script.)
(c) It is used four times:

1. On the quadrant containing the original marked square; that square can be anywhere in the quadrant.
2. On each of the three other quadrants, whose “marked” square is the centre-corner square covered by the central L.

The marked positions differ (arbitrary, or a specific corner after rotation), so we need the recipe for every possible marked square. That is exactly what $P(k)$ says (“an arbitrary square is marked”). A weaker hypothesis such as “tileable when a corner is marked” would not cover the first quadrant.