Discrete Mathematics
Topics Set Theory & Boolean Algebra Logic & Proof Techniques Combinatorics & Counting Graph Theory Number Theory (Divisibility, Modular Arithmetic) Recurrence Relations Finite Automata & Formal Languages Discrete Probability
Important Theorems De Morgan’s Laws (Logic & Boolean Algebra) Pigeonhole Principle (Combinatorics) Inclusion-Exclusion Principle (Counting) Euler’s Formula for Graphs ( Handshaking Lemma ( Chinese Remainder Theorem (Number Theory) Fermat’s Little Theorem ( RSA Cryptosystem & Modular Inverses Master Theorem (Recurrence Relations)
"The introduction of suitable abstractions is our only mentail aid to organize and master complexity" — E. W. Dijkstra. 1930-2002
Sets
Proper Subset
Let A and B be sets. A is proper subset of B \(\iff \exists \forall a \in A, a \in B\), but \(\exists\) at least one element of B \(\not\in A\).
Cartesian Product
Given sets \(A_1, A_2, ..., A_n\), their Cartesian Product is the set of all ordered n-tuples \((a_1, a_2, ..., a_n)\) where \(a_1\in A_1, a_2\in A_2, ..., a_n\in A_n\).