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/. The chapter number is the new lecture number; CDM-L09 and CDM-L15 (tests) have no file.

Part I — Sets & relations

Ch.	Title	Focus
1	Set theory	sets, membership, numeric hierarchy, subsets, cardinality, power sets, tuples
2	Set algebra	operations, the algebra of sets (proved), duality, inclusion–exclusion, Cartesian product
3	Relations	binary relations, properties, equivalence & partitions, composition, closures, partial orders

Part II — Logic, proof & number theory

Ch.	Title	Focus
4	Boolean algebra — basics	statements, operations, identities & duality, counting Boolean functions, the sets↔logic↔bits isomorphism
5	Boolean algebra	functional completeness, canonical forms, Karnaugh maps, Quine–McCluskey, gates
6	Propositional logic	syntax & semantics, equivalences, satisfiability & entailment, CNF/DNF, SAT
7	Proofing — methods of proof	direct/contrapositive/contradiction/cases, induction (weak & strong), inference rules, fallacies
8	Number theory	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	terminology, handshaking lemma, representations, isomorphism, planarity, Euler’s formula
11	Graph theory — algorithms	greedy colouring, Dijkstra, Prim & Kruskal (with correctness proofs), union–find
12	Special graphs	trees (characterizations proved), traversals, spanning trees, Euler/Hamilton, bipartite

Part IV — Probability & computation

Ch.	Title	Focus
13	Probabilities	axioms & derived rules, combinatorics, conditional probability, total probability & Bayes
14	Automata theory	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/, 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

CDM — Lectures / Лекції

Layout

Contents

Part I — Sets & relations

Part II — Logic, proof & number theory

Part III — Graph theory

Part IV — Probability & computation

How to use

Slides

Notation quick reference

Further reading

CDM — Lectures / Лекції #

Layout #

Contents #

Part I — Sets & relations #

Part II — Logic, proof & number theory #

Part III — Graph theory #

Part IV — Probability & computation #

How to use #

Slides #

Notation quick reference #

Further reading #

CDM — Lectures / Лекції

Layout

Contents

Part I — Sets & relations

Part II — Logic, proof & number theory

Part III — Graph theory

Part IV — Probability & computation

How to use

Slides

Notation quick reference

Further reading