Purpose. These notes are my write-up of the course Logic and Set Theory. I restructured the TU/e self-study guide into a blog-friendly format while keeping the proof style used in the course. Proofs are presented in TU/e’s preferred formats: block style with side bars, proof trees, and diamonds. Exercises are renumbered (1.1, 1.2, …) and occasionally summarized where routine.
1. Propositional Logic
Concepts
- Syntax: propositional variables, connectives $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$.
- Semantics: truth values under assignments.
- Tautology = always true, Contradiction = always false, Contingency = sometimes true/false.
- Logical equivalence and consequence.
Example 1.1: Truth Table Check
Determine whether $(p \Rightarrow q) \Leftrightarrow (\neg p \lor q)$ is a tautology.
Solution (summary). Build the truth table; both formulas agree on all rows. Therefore equivalence holds; the formula is a tautology.
Example 1.2: Contingency Proof
Show $((a \land b) \Leftrightarrow (\neg c \lor b)) \land \neg(a \Rightarrow c)$ is a contingency.
Solution.
- If $a=0$, then $a \Rightarrow c = 1$, so the right conjunct is false; whole formula false. Not a tautology.
- If $a=1, b=1, c=0$, then left conjunct true, right conjunct true; whole formula true. Not a contradiction.
Thus it is a contingency.
Example 1.3: Proof Block
Prove $(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)$.
\[\begin{array}{l l} 1. & p \Rightarrow q \quad \text{Assume} \\ 2. & \neg q \quad \text{Assume} \\ 3. & p \quad \text{Assume} \\ 4. & q \quad \Rightarrow\text{-elim on 1,3} \\ 5. & \bot \quad \neg\text{-elim on 2,4} \\ 6. & \neg p \quad \neg\text{-intro on 3--5} \\ 7. & \neg q \Rightarrow \neg p \quad \Rightarrow\text{-intro on 2--6} \\ 8. & (p \Rightarrow q) \Rightarrow (\neg q \Rightarrow \neg p) \quad \Rightarrow\text{-intro on 1--7} \end{array}\]By symmetry, the converse holds. So equivalence is proven.
2. Predicate Logic
Concepts
- Quantifiers $\forall, \exists$.
- Free vs bound variables.
- Closed formulas have no free variables.
Example 2.1: Translation
“Anna has only read books she liked.”
Formula: $\forall b[(R(Anna,b)) \Rightarrow L(Anna,b)]$.
Example 2.2: Proof Tree
Show $\forall x.P(x)\land \forall x.Q(x) \Rightarrow \forall x.(P(x)\land Q(x))$.
\[\cfrac{ \cfrac{P(a) \quad Q(a)}{P(a) \land Q(a)} (\land I) }{ \forall x.P(x)\land \forall x.Q(x) \Rightarrow \forall x.(P(x)\land Q(x)) }\]Since $a$ was arbitrary, generalization gives the result.
Example 2.3: Closed Formula Check
Check truth of $\forall x\in\mathbb{Z} \; \exists y\in\mathbb{Z} \; (2x-y=3)$.
Solution. For given $x$, choose $y=2x-3$. Always works. Formula is true.
3. Derivations (Natural Deduction)
Concepts
- Proofs as derivations in natural deduction.
- Assumptions introduced and discharged.
Example 3.1: Proof Block
Prove $(\neg(P \land Q) \Rightarrow (Q \land R)) \Rightarrow Q$.
(Block proof already shown in 1.2, repeated here for style practice.)
Example 3.2: Contradiction
Prove $\neg\neg P \Rightarrow P$.
\[\begin{array}{l l} 1. & \neg\neg P \quad \text{Assume} \\ 2. & \neg P \quad \text{Assume} \\ 3. & \bot \quad \neg\text{-elim on 1,2} \\ 4. & P \quad \neg\text{-intro+elim on 2--3} \\ 5. & \neg\neg P \Rightarrow P \quad \Rightarrow\text{-intro on 1--4} \end{array}\]4. Proof Strategies
Concepts
- Direct proof.
- Proof by contrapositive.
- Proof by contradiction.
Example 4.1: Contrapositive
Prove “If $n^2$ is even, then $n$ is even.”
Contrapositive: If $n$ is odd, then $n^2$ is odd. Proof: $n=2k+1$, then $n^2=4k^2+4k+1=2(2k^2+2k)+1$, odd.
5. Sets
Concepts
- Basic set operations $\cup, \cap, \setminus$.
- Identities and power sets.
Example 5.1: Proof Diamond
Show distributivity $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
\[\begin{array}{ccc} & x \in A \cap (B \cup C) & \\ \swarrow & & \searrow \\ x \in A \cap B & & x \in A \cap C \\ \searrow & & \swarrow \\ & x \in (A \cap B)\cup(A \cap C) & \end{array}\]Example 5.2: Power Set
Compute $P({0,1})\times P(\emptyset)$.
Answer: ${(\emptyset,\emptyset),({0},\emptyset),({1},\emptyset),({0,1},\emptyset)}$.
6. Relations
Concepts
- Reflexive, symmetric, transitive.
- Equivalence relations, equivalence classes.
- Partial orders, Hasse diagrams.
Example 6.1: Equivalence Relation
Relation $xSy \iff \exists a>0: y=ax$.
\[\begin{array}{l l} 1. & xSx \quad (a=1) \\ 2. & y=ax \Rightarrow x=(1/a)y,\;1/a>0 \quad (\text{symmetric}) \\ 3. & y=ax, z=by \Rightarrow z=(ba)x,\; ba>0 \quad (\text{transitive}) \end{array}\]Classes: $\mathbb{R}^+$, $\mathbb{R}^-$, ${0}$.
Example 6.2: Partial Order Diagram
Divisibility on ${2,4,8}$:
\[\begin{array}{c} 2 \\ \;|\; \\ 4 \\ \;|\; \\ 8 \end{array}\]7. Functions
Concepts
- Injective: one-to-one.
- Surjective: onto.
- Bijective: both.
- Inverses.
Example 7.1: Injectivity Test
$f(x)=x^2-4x+4$.
- $f(1)=f(3)=1$. Not injective.
- $f^{-1}({1})={1,3}$.
8. Induction
Concepts
- Weak induction: base case + step.
- Strong induction.
- Structural induction.
Example 8.1: Weak Induction
Prove $n^3-n$ divisible by 3.
\[\begin{array}{l l} 1. & n=0: 0 \quad \text{divisible} \\ 2. & \text{Assume } n^3-n \text{ divisible} \\ 3. & (n+1)^3-(n+1)=(n^3-n)+3n^2+3n \\ 4. & \text{Also divisible by 3. Done.} \end{array}\]Example 8.2: Strong Induction
Prove every $n\ge2$ is divisible by a prime.
- Base: $n=2$ prime.
- Step: If $n+1$ is prime, done. Else factorize $n+1=ab$ with $a,b<n+1$. By induction hypothesis, $a$ or $b$ divisible by a prime. So $n+1$ divisible by a prime.
9. Orderings
Concepts
- Partial orders.
- Hasse diagrams.
- Minimal/maximal, least/greatest.
Example 9.1: Hasse Diagram
Set ${2,3,6}$ under divisibility. $2 3 \ / 6$ —
10. Cardinality
Concepts
- Finite, countable, uncountable sets.
- Cantor’s diagonal argument.
Example 10.1: Countability
$\mathbb{N}\times \mathbb{N}$ is countable by diagonal enumeration $(0,0),(0,1),(1,0),(0,2),\dots$.
Example 10.2: Uncountability
Cantor’s theorem: $\mathcal{P}(\mathbb{N})$ is uncountable.
Proof idea. Assume enumeration $S_0,S_1,\dots$. Define $D={n\mid n\notin S_n}$. Then $D$ differs from each $S_n$ at position $n$. Contradiction. So $\mathcal{P}(\mathbb{N})$ uncountable.
References
- TU/e Self-study guide: Logic and Set Theory.
- Huth, M., Ryan, M. Logic in Computer Science: Modelling and Reasoning about Systems.
- Enderton, H. A Mathematical Introduction to Logic.
- Velleman, D. How to Prove It: A Structured Approach.