# CDM — Lectures / Лекції

Lecture component of *Discrete Mathematics* (English). The `.md` chapters here are
a **textbook-style, self-contained** set of lecture notes — motivation, definitions,
**proved** theorems, worked examples, remarks, exercises, and a summary — one chapter
per lecture. The course has **15 lecture slots**; **lecture 9** and **lecture 15** are
**tests** (module / final control) and have no chapter.

## Layout

This folder holds the lecture chapters `CDM-L<NN>.md` directly, their figures in
`img/`, and the presentations in [`Slides/`](Slides/). The chapter number is the
**new** lecture number; `CDM-L09` and `CDM-L15` (tests) have no file.

## Contents

### Part I — Sets & relations
| Ch. | Title | Focus |
|:--:|---|---|
| 1 | [Set theory](CDM-L01.md) | sets, membership, numeric hierarchy, subsets, cardinality, power sets, tuples |
| 2 | [Set algebra](CDM-L02.md) | operations, the algebra of sets (proved), duality, inclusion–exclusion, Cartesian product |
| 3 | [Relations](CDM-L03.md) | binary relations, properties, equivalence & partitions, composition, closures, partial orders |

### Part II — Logic, proof & number theory
| Ch. | Title | Focus |
|:--:|---|---|
| 4 | [Boolean algebra — basics](CDM-L04.md) | statements, operations, identities & duality, counting Boolean functions, the sets↔logic↔bits isomorphism |
| 5 | [Boolean algebra](CDM-L05.md) | functional completeness, canonical forms, Karnaugh maps, Quine–McCluskey, gates |
| 6 | [Propositional logic](CDM-L06.md) | syntax & semantics, equivalences, satisfiability & entailment, CNF/DNF, SAT |
| 7 | [Proofing — methods of proof](CDM-L07.md) | direct/contrapositive/contradiction/cases, induction (weak & strong), inference rules, fallacies |
| 8 | [Number theory](CDM-L08.md) | divisibility, primes & Euclid's algorithm, unique factorization, congruences, Euler's totient, pigeonhole |
| *9* | *Test — module control* | *(no chapter)* |

### Part III — Graph theory
| Ch. | Title | Focus |
|:--:|---|---|
| 10 | [Graph theory — basics](CDM-L10.md) | terminology, handshaking lemma, representations, isomorphism, planarity, Euler's formula |
| 11 | [Graph theory — algorithms](CDM-L11.md) | greedy colouring, Dijkstra, Prim & Kruskal (with correctness proofs), union–find |
| 12 | [Special graphs](CDM-L12.md) | trees (characterizations proved), traversals, spanning trees, Euler/Hamilton, bipartite |

### Part IV — Probability & computation
| Ch. | Title | Focus |
|:--:|---|---|
| 13 | [Probabilities](CDM-L13.md) | axioms & derived rules, combinatorics, conditional probability, total probability & Bayes |
| 14 | [Automata theory](CDM-L14.md) | DFA/NFA, subset construction, Mealy/Moore, regular languages, pumping lemma |
| *15* | *Test — final control* | *(no chapter)* |

## How to use

Work chapters in order; each assumes the previous ones. Read the proofs **actively** —
the techniques on display (direct proof, contradiction, cases, induction, bijection,
the cut property, the subset construction, …) recur across the whole course.
Definitions are in **bold**; results you should be able to prove are stated as
Theorems / Propositions / Lemmas. Do the Warm-up exercises as you read and attempt a
selection of Standard / Challenge problems afterward.

## Slides

The presentations live in [`Slides/`](Slides/), one per lecture, and are **numbered
in step with the chapters**: `CDM-L01`–`L08` and `CDM-L10`–`L14`. (Lectures 9 and 15
are tests, so they have no deck.)

## Notation quick reference

| Symbol | Meaning | | Symbol | Meaning |
|:--:|---|---|:--:|---|
| $\in,\notin$ | (non-)membership | | $\wedge,\vee,\neg$ | and, or, not |
| $\subseteq,\subset$ | subset, proper subset | | $\to,\leftrightarrow$ | implies, iff |
| $\varnothing$ | empty set | | $\forall,\exists$ | for all, exists |
| $\cup,\cap,\setminus$ | union, intersection, difference | | $\equiv$ | logical equivalence |
| $\triangle$ | symmetric difference | | $\models$ | entails / models |
| $\overline{A}$ | complement | | $\binom{n}{k}$ | binomial coefficient |
| $A\times B$ | Cartesian product | | $P(A\mid B)$ | conditional probability |
| $\lvert A\rvert$ | cardinality | | $\deg(v)$ | vertex degree |
| $\mathcal P(A),\,2^{A}$ | power set | | $\delta,\hat\delta$ | automaton transition function |
| $\mathbb{N,Z,Q,R,C}$ | number sets | | $\square,\blacksquare$ | end of proof |

## Further reading

- K. Rosen, *Discrete Mathematics and Its Applications*.
- S. Epp, *Discrete Mathematics with Applications*.
- D. West, *Introduction to Graph Theory*; T. Cormen et al., *Introduction to Algorithms*.
- M. Sipser, *Introduction to the Theory of Computation*; S. Ross, *A First Course in Probability*.