Final Exam Syllabus – Discrete Math (V63.0120)

{$ \gdef\NN{\mathbb{N}} \gdef\QQ{\mathbb{Q}} \gdef\RR{\mathbb{R}} \gdef\ZZ{\mathbb{Z}} \gdef\P{\mathsf{P}} \gdef\cross{\times} \gdef\o{\circ} \gdef\id{\iota} \gdef\st{\; : \;} \gdef\mod{\text{ mod }} \gdef\union{\cup} \gdef\inter{\cap} \gdef\tor{\text{ or }} \gdef\tand{\text{ and }} \gdef\setdiff{\setminus} $}

Sections 4.1-4.5 – Relations

A relation {$R$} with domain {$A$} and codomain {$B$} is a subset of {$A \cross B$}: {$R \subseteq A \cross B$}.

Can be defined using one of the following:

Possible properties of a relation

You should be able to prove or disprove any of the properties below.

For relations with the same domain and co-domain ({$A=B$}), the following additional properties may hold:

Special combinations

Function {$f: A \rightarrow B$}

All three properties above are conserved via composition. E.g. the composition of two invertible functions is invertible.

Set cardinality

Sections 5.1-5.4 (5.5 skipped) – Combinatorics

Counting rules

Useful operators

Ways to pick {$r$} items from {$n$}

Ways to pick {$r$} items from {$n$} order matters?
E.g. Pick 2 from {$\{a,b,c\}$}YN
repetitions allowed? Y {$n^r$} ordered lists
(a,a), (a,b), (a,c)
(b,a), (b,b), (b,c)
(c,a), (c,b), (c,c)
unordered lists or bags

(a,a), {a,b}, {a,c}
       (b,b), {b,c}
N {$P(n,r)$} permutations
       (a,b), (a,c)
(b,a),        (b,c)
(c,a), (c,b),      
{$C(n,r)=C(n,n-r)$} sets
       {a,b}, {a,c}

Intuition and examples

Sections 6.1-6.3 – Probability


Disjoint events = Mutually-exclusive events

Mutually-independent, or simply independent

Sections 7.1, 7.3 (7.2 skipped) – Graphs:

Terminology and definitions

Eulerian trails/circuits