Discrete Maths

• Profs: Ueli Maurer
• Website: https://crypto.ethz.ch/teaching/DM24/
• Exercises: https://dm.crypto.ethz.ch/
• Admin: Admin
• Material: Material
• Videos: Videos ETHZ

This discrete mathematics course, taught by Professor Maurer, covered four main areas: logic systems (propositional and predicate logic, proofs), set theory (relations, functions, countability), number theory, and abstract algebra. It was my most enjoyable and interesting course in the first semester.

Professor Maurer’s teaching style is exceptional — he breaks down complex topics into intuitive, easily digestible explanations rather than relying on heavy formalism, which I really appreciated. The course was well-structured and provided a solid grasp of the material.

While initially intimidating due to its different mathematical perspective compared to high school, over time, especially when reviewing for exams, everything started to click. The course emphasized rigor while also exploring practical applications, such as cryptographic concepts like key exchanges and error-correcting codes. A truly wonderful course taught by an outstanding professor.

Lecture Notes

• 01 Intro and Statements
• 02 Propositional Logic and Formulas
• 03 Logical Equivalence, Tautological Implication and Modus Ponens
• 04 Quantifiers
• 05 Proof Types
• 06 Set Theory and Russels Paradox
• 07 Equality, Ordered Pairs, Cartesian Product, Power Set and Relationships
• 08 Relations, Compositions and Properties
• 09 Equivalency Relation and Classes, Partitions, Partially Ordered Sets
• 10 Posets, Hasse Diagrams, Lexicographical Ordering, Special Elements, Functions, Countability, Infinities
• 11 Functions, Relations, Cardinality, Countability, Cantor’s Diagonalization Argument
• 12 Cardinality, Number Theory, Rings, Euclidian Rings, Ideal, Congruence, Modular Arithmetic, Diophantine Equations
• 13 Modular Arithmetics, Set of Residues, Diffie-Hellman, Multiplicative Inverse, Chinese Remainder Theorem
• 14 Algebraic Structures and Operations, Monoids, Inverses, Groups, Group Properties, Landscape of Groups
• 15 Groups, Homomorphism, Isomorphism, Preservation of Identity and Inverses
• 16 Isomorphism, Powers, Order, Generators, Lagrange’s Theorem, Multiplicative Groups, Euler’s Totient Function, RSA
• 17 Rings, Polynomial Rings, Integral Domains, Units
• 18 Rings, Fields, Real Polynomial Fields, Polynomial Fields, Galois Fields
• 19 Factorizations, Polynomial Fields and Division, Polynomial Interpolation, Constructing Galois Fields
• 20 Generators in Finite Fields, Properties of Finite Fields, Error Correcting Codes, Reed-Solomon Codes
• 21 Logic, Proof Systems, Logical Consequence, Syntactic Derivation
• 22 Proof Systems, Syntax, Semantics, Equivalence, Satisfiability, Tautologies, Normal Forms, Types of Statements
• 23 Predicate Logic Reintroduced, Syntax, Semantics, Universe Size
• 24 Evaluating and Proving Formulas in Predicate Logic, Equivalences, Transformations, Variable Substitution, Universal Instantiation, Equality, Prenex Normal Form
• 25 Skolem Normal Form, Russell’s Paradox, Cantor’s Diagonalization, Existence of Uncomputable Functions, Higher-Order Logic, Calculi
• 26 Syntactic Derivation vs Semantic Entailment, Logic Calculus, Sequent Calculus, Resolution Calculus
• 27 Soundness and Completeness of Resolution Calculus, NP and SAT problem

Script

• Chapter 2 - Math. Reasoning, Proofs, and a First Approach to Logic
• Chapter 3 - Sets, Relations, and Functions
• Chapter 4 - Number Theory
• Chapter 5 - Algebra
• Chapter 6 - Logic

Other Stuff

• Useful Resources