Mathematical Logic and Set Theory Tutorial
Learn Mathematical Logic and Set Theory step by step: 37 lessons in 9 chapters with examples, quizzes, diagrams and projects.
Start learning →
of lessons completed
Getting Started
- What Is Mathematical Logic? Learn what mathematical logic and set theory study, why programmers need them, and how this course uses runnable Python to make every idea concrete.
- Statements, Truth Values and Notation Learn what counts as a logical statement, how truth values work, and the notation (β§ β¨ Β¬ β β β β) used throughout logic, with runnable Python examples.
- A Python Toolkit for Logic Build a small Python toolkit for logic: formula classes with operator overloading, evaluation, variable discovery, and a comparison with the SymPy library.
- Arguments, Validity and Fallacies Learn the difference between valid and sound arguments, how to test validity with counterexamples, and how to spot common logical fallacies, with Python checks.
Propositional Logic
- Connectives and Truth Tables Master truth tables for negation, conjunction, disjunction, implication and the biconditional, generate them with Python, and learn why implication is false only once.
- Tautologies, Contradictions and Logical Equivalence Classify formulas as tautologies, contradictions or contingencies, learn De Morgan's laws and the standard equivalences, and verify them all with Python.
- Normal Forms: CNF and DNF Convert any propositional formula to conjunctive or disjunctive normal form, understand minterms and maxterms, and implement the conversion in Python and SymPy.
- Propositional Proofs with Natural Deduction Learn natural deduction for propositional logic: introduction and elimination rules, discharging assumptions, worked proofs, and a Python proof checker you can run.
- SAT and Resolution: Automated Propositional Reasoning Learn the Boolean satisfiability problem, the resolution rule, and the DPLL algorithm, then write a working SAT solver in Python and test it on puzzles.
Predicate Logic
- Predicates and Quantifiers Learn predicates, domains and the universal and existential quantifiers, how to read and write quantified statements, and how Python's all() and any() model them.
- Nested Quantifiers and Negating Quantified Statements Understand why the order of nested quantifiers matters, how to negate β and β statements correctly, and how to check them with Python loops over finite domains.
- Models, Interpretations and Truth in First-Order Logic Understand structures, interpretations and satisfaction in first-order logic, write a finite model checker in Python, and see why validity cannot be checked by finite search.
- Translating English into Predicate Logic Learn reliable patterns for turning English sentences into first-order formulas, avoid classic ambiguities, and test translations against small models in Python.
- Predicate Equivalences and Inference Rules Learn which quantifier equivalences hold, which are common traps, and the four inference rules (universal and existential instantiation and generalization) with examples.
Proof Techniques
- Direct Proof and Proof by Cases Learn how to write direct proofs and proofs by cases and exhaustion, with worked number-theory examples, proof-writing habits and Python experiments that guide the proof.
- Proof by Contrapositive and Proof by Contradiction Learn when to prove the contrapositive and when to argue by contradiction, with classic proofs (irrationality of β2, infinitely many primes) and numeric Python checks.
- Mathematical Induction Learn mathematical induction from the domino picture to complete proofs: sums, divisibility and inequalities, common pitfalls, and Python checks of the formulas.
- Strong Induction, Structural Induction and Recursive Definitions Learn strong induction, structural induction on lists and trees, and recursive definitions, with proofs about primes, Fibonacci numbers and binary trees, plus Python checks.
Sets, Relations and Functions
- Sets and Set Operations Learn what a set is, how to write sets, and how union, intersection, difference, complement and power sets work, with Python code that checks every law.
- Relations and Their Properties Understand binary relations as sets of pairs, test reflexive, symmetric, antisymmetric and transitive properties, and compute closures and compositions in Python.
- Equivalence Relations and Partitions See how equivalence relations split a set into classes, why they match partitions exactly, and build modular arithmetic and union-find in runnable Python.
- Functions: Injective, Surjective, Bijective Define functions as special relations, then master injective, surjective and bijective maps, composition, inverses and the pigeonhole principle with Python checks.
Cardinality and Orders
- Cardinality and Countable Sets Compare the sizes of infinite sets using bijections. Learn countable sets, Hilbert's hotel, why the integers and rationals are countable, and the Schroeder-Bernstein theorem.
- Cantor's Diagonal Argument and Uncountability Walk through Cantor's diagonal argument and Cantor's theorem on power sets, see why the real numbers cannot be listed, and meet the continuum hypothesis with runnable code.
- Partial Orders and Lattices Learn partial and total orders, Hasse diagrams, minimal and maximal elements, bounds, topological sorting and lattices, with Python code on divisibility and subsets.
- Well-Orders, Induction and Ordinals Understand well-orders, well-founded induction, ordinal numbers beyond infinity, ordinal arithmetic and the axiom of choice, with runnable Python examples of termination orders.
Formal Systems and Completeness
- ZFC Axioms and Russell's Paradox See why naive set theory breaks with Russell's paradox and how the Zermelo-Fraenkel axioms with choice repair it, with Python models of sets built from nothing.
- Formal Systems and Proof Calculi Learn what a formal system is, how axioms and inference rules produce theorems, and write a Hilbert-style proof checker for propositional logic in Python.
- Soundness and Completeness of Propositional Logic Connect proof and truth: see why propositional proofs are sound and complete, build a semantic tableau prover, and test it against truth tables and Hilbert axioms in Python.
- GΓΆdel's Incompleteness and Computability Understand GΓΆdel numbering, the idea behind the incompleteness theorems, the halting problem and Turing's diagonal proof, with runnable Python for encoding and self-reference.
Applications in CS
- DPLL and SAT Solvers Learn CNF, the satisfiability problem and the DPLL algorithm with unit propagation and pure literals, then solve puzzles with a SAT solver you write in Python.
- Boolean Algebra and Logic Circuits Connect logic to hardware: Boolean algebra laws, sum-of-products and product-of-sums, minimization, NAND universality and adders built from gates, with Python simulations.
- Hoare Logic and Program Verification Prove programs correct with Hoare triples, loop invariants and weakest preconditions, and build a small verification-condition checker for an imperative mini-language in Python.
- Relational Algebra, Sets and SQL See databases as set theory and logic: relations as sets of tuples, the relational algebra operators, first-order queries and Datalog recursion, checked against SQLite in Python.
Projects and Practice
- Project: A Resolution Theorem Prover Build a propositional theorem prover step by step: parse formulas, convert to clause form, apply the resolution rule and print a proof, then test it against truth tables.
- Project: A Finite Model Checker Write a first-order logic evaluator for finite structures, count models of relation axioms, find countermodels to invalid claims and see why some theories have only infinite models.
- Practice: Sets, Relations and Logic Problems Work through graded practice problems on sets, relations, functions, cardinality, orders and formal logic, each with a worked answer and a Python check.