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 at ETH Zürich, taught by Prof. Ueli Maurer, provides essential mathematical foundations for computer science. Starting with logic and set theory, the course progresses to number theory and abstract algebra, covering modular arithmetic, groups, rings, and fields, culminating in the construction and application of finite fields. Students learn about proof techniques, algebraic structures, and their applications in areas like cryptography and error-correcting codes. The course also explores the formalization of proof systems, examining soundness, completeness, and their limitations, connecting to complexity theory. This rigorous course equips students with the mathematical tools and reasoning skills crucial for advanced computer science.

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

Script (WIP)

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

Other Stuff

• Useful Resources