Logic and Discrete Structures

What you'll learn

• Explain why proof, not testing alone, establishes facts about all inputs, read mathematical definitions, theorems and conjectures, and use Python to explore small cases and find counterexamples before attempting a proof.
• Identify propositions, evaluate compound propositions with the connectives and truth tables, interpret the conditional correctly including vacuous truth and only if, and distinguish a conditional from its converse, inverse and contrapositive.
• Prove and apply logical equivalences including De Morgan's laws, convert formulas to conjunctive and disjunctive normal form, solve small satisfiability problems by brute force, and recognize valid rules of inference and common fallacies.
• Translate English statements and specifications into predicate logic with correct domains, restricted quantifiers and nested quantifiers, and negate quantified statements to describe counterexamples.
• Write direct proofs and proofs by contrapositive about integers and divisibility, prove biconditionals in both directions, disprove universal claims with counterexamples, and present proofs clearly in complete sentences.
• Write proofs by contradiction, including the irrationality of the square root of 2 and the infinitude of primes, proofs by cases and exhaustion, and constructive and non-constructive existence and uniqueness proofs.
• Describe sets in roster and set-builder notation, apply union, intersection, difference, complement, power sets and Cartesian products, prove set identities by double inclusion, and count with inclusion–exclusion.
• Classify functions as injective, surjective or bijective, compose and invert functions, apply the pigeonhole principle, and compare cardinalities of infinite sets using bijections and Cantor's diagonal argument.
• Determine whether relations are reflexive, symmetric, antisymmetric or transitive, work with equivalence classes and partitions, draw Hasse diagrams of partial orders, topologically sort, and compute transitive closures with Warshall's algorithm.
• Prove statements by ordinary, strong and structural induction, write and reason about recursive definitions, and prove recursive functions correct and terminating.
• Count arrangements and selections with the sum and product rules, permutations, combinations and the binomial theorem, and apply divisibility, Euclid's algorithm, modular arithmetic and modular inverses, including a toy RSA example.
• Specify code with preconditions, postconditions and Hoare triples, prove loops correct with invariants and progress measures, and model problems as graphs using degrees, paths, trees and Euler paths.