DMS
Discrete Mathematics
The mathematics under computer science: logic, proofs, sets, relations, functions, counting, recurrences, graph theory, number theory and Boolean algebra.
0%complete
- Lessons
- 18
- Runnable examples
- 31
- Quiz questions
- 72
- Visualizers
- 4
What you will be able to do
- Build truth tables and simplify logical expressions
- Write direct, contradiction and induction proofs
- Work with sets, relations, functions and partial orders
- Count with permutations, combinations and inclusion–exclusion
- Solve recurrence relations
- Reason about graphs, trees, modular arithmetic and Boolean algebra
Syllabus
Unit 1Logic & Proofs
- 1Propositional LogicPropositions and the logical connectives — negation, AND, OR, XOR, implication and biconditional — with truth tables, converse and contrapositive, and translating English.
- 2Logical Equivalences & Normal FormsWhen two formulas mean the same thing: the laws of logic including De Morgan's, simplifying expressions step by step, and converting to disjunctive and conjunctive normal form.
- 3Predicates & QuantifiersStatements with variables: predicates, the universal and existential quantifiers, domains, negating quantified statements, nested quantifiers and translating English.
- 4Proof TechniquesHow mathematicians and computer scientists prove things: rules of inference, direct proof, proof by contrapositive, contradiction, cases, counterexamples, and existence proofs.
- 5Mathematical InductionProve statements for all natural numbers: the base case and inductive step, sums, divisibility and inequalities, strong induction, and the link to recursion and loop invariants.
Unit 2Sets, Relations & Functions
- 6SetsSets and their notation, subsets and power sets, union, intersection, difference and complement with Venn diagrams, set identities, Cartesian products and cardinality.
- 7RelationsRelations as sets of ordered pairs, matrix and digraph representations, the reflexive, symmetric, antisymmetric and transitive properties, equivalence relations and classes, and closures.
- 8Partial Orders & LatticesOrdering things that are not all comparable: posets, Hasse diagrams, maximal and minimal elements, upper and lower bounds, lattices and topological sorting.
- 9FunctionsFunctions as special relations: domain, codomain and range, one-to-one, onto and bijective functions, composition, inverses, floor and ceiling, and counting functions.
Unit 3Counting
- 10Counting Principles & PigeonholeThe sum and product rules, counting with complements, tree diagrams, and the pigeonhole principle with its generalised form and classic applications.
- 11Permutations & CombinationsOrdered arrangements and unordered selections: nPr and nCr, factorials, repetition, arrangements with identical items, circular permutations and stars and bars.
- 12Inclusion–Exclusion & the Binomial TheoremCount unions without double counting using inclusion–exclusion, apply it to divisibility and derangements, and expand (x + y)ⁿ with the binomial theorem and Pascal's triangle.
- 13Recurrence RelationsDefine sequences recursively, model counting problems with recurrences, and solve linear homogeneous recurrences with constant coefficients using the characteristic equation.
Unit 4Graphs, Number Theory & Algebra
- 14Graph TheoryGraphs as mathematics: simple graphs and multigraphs, degree and the handshake lemma, special graphs, isomorphism, Euler and Hamilton paths, planarity and graph colouring.
- 15TreesTrees in discrete mathematics: characterisations, rooted and m-ary trees with their counting formulas, spanning trees, Cayley's formula and prefix codes.
- 16Number TheoryDivisibility, primes and the fundamental theorem of arithmetic, GCD and LCM with Euclid's algorithm, modular arithmetic, congruences, modular inverses, fast exponentiation and an RSA preview.
- 17Boolean AlgebraThe algebra of 0 and 1 behind every circuit: Boolean operations and laws, duality, Boolean functions, sum-of-products and product-of-sums forms, logic gates and Karnaugh-map simplification.
- 18Discrete Mathematics Formula SheetEvery rule, law and formula from Discrete Mathematics on one page — logic, proofs, sets, relations, functions, counting, recurrences, graphs, trees, number theory and Boolean algebra.