Logic, Proof, and Computation

What you will learn

• Explain how formal logic and set theory define proof, and what Cantor and Gödel showed about their limits
• Count arrangements and analyze simple networks with combinatorial and graph-theoretic reasoning
• Explain what an algorithm is and why some problems can't be solved by any algorithm
• Describe the P versus NP problem and the current role of computers in proof

Contents

1. Module 1 Logic and Set Theory 2 lessons

   This module covers the branches of mathematics that study proof itself. You'll see how logic turned valid reasoning into rules you can check, how Cantor showed that some infinities are larger than others, and how Gödel proved that no system of rules can capture every mathematical truth. The same logic runs every digital circuit and database you use.

   Module overview and further reading

   1. 1.1Logic and Set Theory: From Aristotle's syllogisms to Cantor's infinities: the logic of proof1h 3m
   2. 1.2Logic and Set Theory: Gödel's incompleteness, the continuum hypothesis, and logic in circuits and databases1h 33m
2. Module 2 Combinatorics and Graph Theory 2 lessons

   This module covers the branches of mathematics that count possibilities and study networks. You'll see how a puzzle about crossing seven bridges became the start of network science, learn to count arrangements without listing them, and meet the mathematics behind route finding, scheduling, and coloring maps. You'll also meet a question about parties and friendships that the world's computers still can't settle.

   Module overview and further reading

   1. 2.1Graph Theory: Counting arrangements and the bridges of Königsberg1h 3m
   2. 2.2Graph Theory: Networks, scheduling, map coloring, and Ramsey numbers1h 33m
3. Module 3 Computation 2 lessons

   This module covers the mathematics of computing: what an algorithm is, how fast one can be, and what no algorithm can ever do. You'll follow the idea from Euclid's method for common divisors to Turing's imaginary machine, see why some problems are easy to check but seem hard to solve, and look at how computers, and now AI systems, are taking part in proving theorems. It's where mathematics meets the machines it made possible.

   Module overview and further reading

   1. 3.1Computation: Algorithms and the limits of computation, from Euclid's algorithm to Turing1h 3m
   2. 3.2Computation: Efficient algorithms, P versus NP, and computers that help prove theorems1h 33m

Course project