Skip to content
DoingCamp CS

Make it comfy

Lesson style

Quick mode shows the key picture, a summary and the practice. Good for a refresher.

Theme
Font

Both fonts are designed to be easy to read. Some readers with dyslexia prefer Lexend.

Text size
Spacing
Animations

F05

Logic & Proofs

“How to win every argument fairly”

Lessons

Start the course →0 of 16 lessons done
  1. What is a proof?FreeA proof is an argument that leaves no room for doubt. You'll see a pattern that works for 40 numbers in a row and then breaks, learn why examples alone can't prove anything, and put together your first real proof. · 12 min
  2. Propositions and connectivesFreeLogic starts with statements that are true or false, glued together with and, or and not. You'll build truth tables, see why "or" in logic means "at least one", and turn a real-world rule into exact logic. · 12 min
  3. If–thenFree"If p then q" is the most important sentence in mathematics, and the most misunderstood. You'll learn exactly when an implication is true, why its converse is a different claim, and why its contrapositive is the same one. · 14 min
  4. Logical equivalence🔒 MembersTwo formulas are equivalent when they agree in every row of the truth table. You'll learn De Morgan's laws, the rules that let you push a "not" inside parentheses, and use them to simplify tangled conditions in code. · 14 min
  5. Satisfiability🔒 MembersCan a set of rules all be true at once? That question, called SAT, sits behind party planning, package managers and chip design. You'll solve it by checking every row, see why that gets slow fast, and plan a party that keeps everyone happy. · 14 min
  6. Predicates and quantifiers🔒 Members"Every student passed" and "some student got 100" are claims about a whole group. You'll learn predicates (statements with a blank), the quantifiers "for all" (∀) and "there exists" (∃), and how Python's all() and any() check them. · 13 min
  7. Negating and nesting quantifiers🔒 Members"Not everyone loves pizza" doesn't mean "nobody loves pizza". You'll learn how a "not" moves through ∀ and ∃, why the order of quantifiers changes the meaning completely, and check a famous unsolved claim about primes. · 15 min
  8. Direct proof🔒 MembersThe most common kind of proof walks straight from what you know to what you want. You'll learn the template (let, unpack the definition, compute, repack), prove facts about odd numbers and divisibility, and spot a sneaky mistake in a proof that looks fine. · 14 min
  9. Contrapositive and cases🔒 MembersWhen a direct proof gets stuck, two tools help. Prove the contrapositive instead (it means the same thing), or split the problem into cases and handle each one. You'll prove that if n² is even then n is even, and use remainders to learn which digits a perfect square can end in. · 14 min
  10. Proof by contradiction🔒 MembersAssume the opposite of what you want, and follow it until something impossible happens. You'll use this to prove two of the oldest and most beautiful results in mathematics, that there are infinitely many primes and that √2 is not a fraction, and then turn one of them into code. · 15 min
  11. Counterexamples and disproof🔒 MembersProving a "for all" claim takes a careful argument, but disproving one takes a single example. You'll learn what a counterexample is, why computers are brilliant at finding them, and hunt down the number that broke one of Goldbach's guesses. · 13 min
  12. Induction🔒 MembersInduction proves a statement for every whole number with just two steps, like knocking down an endless line of dominoes. You'll prove sum formulas, see why the base case matters, and catch the flaw in a famous fake proof that all horses are the same color. · 16 min
  13. Strong induction🔒 MembersSometimes the next domino is knocked over by one several steps back, not the one just before it. Strong induction lets you assume every smaller case at once. You'll prove that stamps can make any big enough amount, that every number splits into primes, and write both proofs as recursive code. · 15 min
  14. Proving programs correct🔒 MembersTests check some inputs, but a proof covers all of them. You'll learn loop invariants (a fact that stays true every time around a loop), how to show a loop always stops, and use both to fix a binary search and write an exact square root for huge numbers. · 16 min
  15. Invariants and impossible puzzles🔒 MembersHow do you prove something can never happen, no matter how many moves you try? Find a property that every move preserves. You'll use invariants to show a robot can't reach a square, a chessboard can't be tiled, and a famous movie puzzle can't be solved with the wrong jugs. · 15 min
  16. Boss level: the island of knights and knaves🔒 MembersOn an island where knights always tell the truth and knaves always lie, every sentence is a logic puzzle. You'll translate what islanders say into formulas, prove who's who by cases, build a solver that cracks any puzzle, and design a puzzle of your own with exactly one answer. · 45 min

💼 Already know this course?

Placement tests are coming soon. Until then, you can mark it as known so it’s colored in on your map. You can undo this any time.