Discrete Mathematics: High-Level Study and Review Notes

Propositional Logic and Truth Tables

  • Mathematical Statement (Proposition): A declarative sentence that is either strictly true (11 or TT) or strictly false (00 or FF), but never both. Statements with unassigned variables (e.g., x+2=5x + 2 = 5) are open statements until quantified or assigned a specific value.

  • Truth Table Construction: For nn logical variables, the truth table consists of 2n2^n rows. The first variable alternates blocks of 2n−12^{n-1} ones and zeros; the second alternates blocks of 2n−22^{n-2}, continuing to the final variable which alternates every 11 row.

  • Logical Connectives:

    • Negation (¬p\neg p or ∼p\sim p): Reverses truth value (¬1=0\neg 1 = 0, ¬0=1\neg 0 = 1).

    • Conjunction (p∧qp \wedge q): True (11) only when both pp and qq are 11.

    • Disjunction (p∨qp \vee q): True (11) if at least one of pp or qq is 11.

    • Conditional (p→qp \rightarrow q): False (00) only when p=1p = 1 and q=0q = 0; true (11) in all other cases.

    • Biconditional (p↔qp \leftrightarrow q): True (11) when pp and qq share identical truth values.

    • Exclusive OR (p⊕qp \oplus q): True (11) when truth values differ; false (00) when both are equal.

  • Fundamental Logical Equivalences:

    • Domination Laws: p∨1≡1p \vee 1 \equiv 1, p∧0≡0p \wedge 0 \equiv 0

    • Identity Laws: p∧1≡pp \wedge 1 \equiv p, p∨0≡pp \vee 0 \equiv p

    • Commutative Laws: p∨q≡q∨pp \vee q \equiv q \vee p, p∧q≡q∧pp \wedge q \equiv q \wedge p

    • Associative Laws: (p∨q)∨r≡p∨(q∨r)(p \vee q) \vee r \equiv p \vee (q \vee r), (p∧q)∧r≡p∧(q∧r)(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)

    • Distributive Laws: p∨(q∧r)≡(p∨q)∧(p∨r)p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r), p∧(q∨r)≡(p∧q)∨(p∧r)p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)

    • De Morgan's Laws: ¬(p∧q)≡¬p∨¬q\neg (p \wedge q) \equiv \neg p \vee \neg q, ¬(p∨q)≡¬p∧¬q\neg (p \vee q) \equiv \neg p \wedge \neg q

  • Double Negation Law: ¬(¬p)≡p\neg (\neg p) \equiv p

  • Absorption Laws: p∨(p∧q)≡pp \vee (p \wedge q) \equiv p, p∧(p∨q)≡pp \wedge (p \vee q) \equiv p

  • Inverse (Negation) Laws: p∨¬p≡1p \vee \neg p \equiv 1, p∧¬p≡0p \wedge \neg p \equiv 0

  • Idempotent Laws: p∨p≡pp \vee p \equiv p, p∧p≡pp \wedge p \equiv p

Set Theory and Relations

  • Standard Number Sets:

    • Natural Numbers: N={1,2,3,4,… }\mathbf{N} = \{1, 2, 3, 4, \dots\}

    • Integers: Z={…,−2,−1,0,1,2,… }\mathbf{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}

    • Rational Numbers: Q={ab∣a,b∈Z,b≠0}\mathbf{Q} = \{\frac{a}{b} \mid a, b \in \mathbf{Z}, b \neq 0\}

    • Irrational Numbers: Q′\mathbf{Q}' (cannot be written as a simple fraction, e.g., 2\sqrt{2}, π\pi, ee)

    • Real Numbers: R\mathbf{R} (all rational and irrational numbers)

  • Set Membership vs. Containment:

    • Element-to-set: x∈Ax \in A (is an element of), x∉Ax \notin A (not an element of).

    • Set-to-set: A⊂BA \subset B or A⊆BA \subseteq B (subset); the empty set ∅\emptyset is a subset of every set (∅⊆A\emptyset \subseteq A).

  • Core Set Operations:

    • Intersection (A∩BA \cap B): Common elements belonging to both AA and BB.

Intersection of sets A and B
  • Union (A∪BA \cup B): All elements in AA, BB, or both.

Union of sets A and B
  • Difference (A−BA - B or A∖BA \setminus B): Elements belonging to AA that do not belong to BB.

Difference of sets A and B
  • Complement (A′A' or AcA^c): Elements of universal set UU not in AA.

Complement of set A
  • Set Properties: Complements follow (A′)′=A(A')' = A, A∪A′=UA \cup A' = U, and A∩A′=∅A \cap A' = \emptyset. De Morgan's Laws state (A∪B)′=A′∩B′(A \cup B)' = A' \cap B' and (A∩B)′=A′∪B′(A \cap B)' = A' \cup B'.

  • Power Set (P(A)P(A)): The set of all subsets of AA. Cardinality is 2n2^n, where nn is the number of elements in AA.

  • Cartesian Product (A×BA \times B): Set of ordered pairs {(a,b)∣a∈A,b∈B}\{(a, b) \mid a \in A, b \in B\}, with total elements n(A)×n(B)n(A) \times n(B). Always A×∅=∅A \times \emptyset = \emptyset.

  • Binary Relation: Any subset R⊆A×BR \subseteq A \times B.

  • Partition of a Set: A collection of non-empty, pairwise disjoint subsets of XX whose union equals XX.

Functions and Properties

  • Function Definition (f:X→Yf: X \rightarrow Y): A relation assigning each element in domain XX to exactly one element in codomain YY. The range/image is the set of actual outputs (Range⊆Y\text{Range} \subseteq Y).

  • Function Classifications:

    • One-to-One (Injective): Distinct inputs produce distinct codomain outputs (f(a)=f(b)  ⟹  a=bf(a) = f(b) \implies a = b).

    • Onto (Surjective): Every element of codomain YY has at least one pre-image (Range=Y\text{Range} = Y).

    • Bijective (One-to-One Correspondence): Both injective and surjective; this is the necessary and sufficient condition for the existence of an inverse function (f−1(x)f^{-1}(x)).

  • Symmetry:

    • Even Function: f(−x)=f(x)f(-x) = f(x); symmetric across the y-axis.

    • Odd Function: f(−x)=−f(x)f(-x) = -f(x); symmetric across the origin (0,0)(0, 0).

  • Operations and Special Types:

    • Composition: (f∘g)(x)=f(g(x))(f \circ g)(x) = f(g(x)).

    • Identity Function: f(x)=xf(x) = x.

    • Constant Function: f(x)=cf(x) = c.

    • Floor & Ceiling: ⌊x⌋\lfloor x \rfloor (greatest integer ≤x\le x); ⌈x⌉\lceil x \rceil (least integer ≥x\ge x).

    • Piecewise Functions: Functions defined by multiple sub-rules according to different intervals of xx.

Combinatorics and Counting Principles

  • Sum Rule: If tasks are mutually exclusive, total ways to choose = n1+n2n_1 + n_2.

  • Product Rule: If a procedure consists of sequential, independent stages, total ways = n1×n2n_1 \times n_2.

  • Permutations (P(n,k)P(n, k)): Ordered arrangements of kk items from nn distinct elements:

P(n,k)=n!(n−k)!P(n, k) = \frac{n!}{(n - k)!}

  • Combinations (Binomial Coefficients): Unordered selections of kk items from nn distinct elements:

(nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n - k)!}

  • Core Combinatorial Identities:

    • Symmetry Identity: (nk)=(nn−k)\binom{n}{k} = \binom{n}{n - k}

    • Pascal's Identity: (nk)=(n−1k−1)+(n−1k)\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}

    • Sum of Binomial Coefficients: ∑k=0n(nk)=2n\sum_{k=0}^{n} \binom{n}{k} = 2^n

  • Binomial Theorem:

(x+y)n=∑k=0n(nk)xn−kyk(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n - k} y^k

  • Stars and Bars Method: Distributes nn identical items into kk distinct categories (solutions to x1+x2+⋯+xk=nx_1 + x_2 + \dots + x_k = n):

    • Non-negative integer solutions (xi≥0x_i \ge 0): (n+k−1k−1)\binom{n + k - 1}{k - 1}

    • Positive integer solutions (xi≥1x_i \ge 1): (n−1k−1)\binom{n - 1}{k - 1}

Sequences and Finite Differences

  • Sequence: A function from positive integers to real values, expressed via explicit formulas (an=f(n)a_n = f(n)) or recurrence formulas.

  • Arithmetic Sequence: Defined by a constant common difference d=an−an−1d = a_n - a_{n-1}.

    • General term: an=a1+(n−1)da_n = a_1 + (n - 1)d

    • Sum of first nn terms: Sn=n2(a1+an)=n2(2a1+(n−1)d)S_n = \frac{n}{2}(a_1 + a_n) = \frac{n}{2}(2a_1 + (n - 1)d)

  • Geometric Sequence: Defined by a constant common ratio r=anan−1r = \frac{a_n}{a_{n-1}}.

    • General term: an=a1⋅rn−1a_n = a_1 \cdot r^{n - 1}

    • Sum of first nn terms (r≠1r \neq 1): Sn=a1(rn−1)r−1S_n = \frac{a_1(r^n - 1)}{r - 1}

  • Method of Finite Differences (Polynomial Fitting):

    • Differences: First difference Δan=an+1−an\Delta a_n = a_{n+1} - a_n; second difference Δ2an=Δan+1−Δan\Delta^2 a_n = \Delta a_{n+1} - \Delta a_n.

    • Criterion: If the kk-th differences are constant, the sequence matches a polynomial of degree kk: an=cknk+⋯+c1n+c0a_n = c_k n^k + \dots + c_1 n + c_0.

    • Quadratic relation (k=2k = 2): Leading coefficient satisfies 2c2=Constant Second Difference2c_2 = \text{Constant Second Difference}.

Solving Recurrence Relations

  • Iteration / Substitution Method: Repeatedly substituting preceding terms backward until an algebraic pattern emerges, then generalizing into an explicit closed-form formula.

  • Second-Order Linear Homogeneous Recurrence Relations:

    • Standard Form: an=c1an−1+c2an−2a_n = c_1 a_{n-1} + c_2 a_{n-2} with c2≠0c_2 \neq 0.

    • Characteristic Equation: r2−c1r−c2=0r^2 - c_1 r - c_2 = 0.

  • Solution Cases:

    • Distinct Real Roots (r1≠r2r_1 \neq r_2):

an=α1(r1)n+α2(r2)na_n = \alpha_1 (r_1)^n + \alpha_2 (r_2)^n

  • Repeated Real Root (r1=r2=rr_1 = r_2 = r):

an=(α1+nα2)rna_n = (\alpha_1 + n\alpha_2) r^n

  • Initial Conditions: Constants α1\alpha_1 and α2\alpha_2 are computed by setting n=0n = 0 and n=1n = 1 using given boundary conditions a0a_0 and a1a_1.

Hashing and Hash Tables

  • Hash Table Fundamentals: Data structure storing key-value pairs providing average-case O(1)\mathcal{O}(1) time complexity for search, insert, and delete (O(n)\mathcal{O}(n) worst case).

  • Hash Function Methods (h(k)h(k)):

    • Division Method: h(k)=k mod mh(k) = k \bmod m (where mm is typically prime).

    • Multiplication Method: h(k)=⌊m(kA mod 1)⌋h(k) = \lfloor m (k A \bmod 1) \rfloor (where 0<A<10 < A < 1).

  • Collision Resolution Strategies:

    • Open Addressing: Stores all entries directly within table slots.

    • Linear Probing: h(k,i)=(h′(k)+i) mod mh(k, i) = (h'(k) + i) \bmod m (susceptible to primary clustering).

    • Quadratic Probing: h(k,i)=(h′(k)+c1i+c2i2) mod mh(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m (susceptible to secondary clustering).

    • Double Hashing: h(k,i)=(h1(k)+i⋅h2(k)) mod mh(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m.

    • Separate Chaining: Each slot maintains an external linked list of colliding elements; the table never completely fills.

  • Load Factor (α\alpha) & Rehashing:

    • Formula: α=nm\alpha = \frac{n}{m}, where nn is total stored keys and mm is table size.

    • Constraints: α≤1\alpha \le 1 in open addressing; α\alpha can exceed 11 in separate chaining.

    • Rehashing: Triggered when α\alpha exceeds a threshold (typically 0.750.75). The table size is doubled (2m2m) and adjusted to the nearest subsequent prime number (mnewm_{new}), followed by re-inserting all keys.