Discrete Mathematics PDF

# Set Theory ## Basic Definitions * **Set:** A collection of well-defined objects, elements, or things. * For example: * S = {2, 4, 6, 8} * **Types of sets:** * **Singleton set:** S = {5} * **Empty/Null set:** S = {} or Φ * **Finite set:** S = {2, 4, 6, 8} * **Infinite...

# Set Theory ## Basic Definitions * **Set:** A collection of well-defined objects, elements, or things. * For example: * S = {2, 4, 6, 8} * **Types of sets:** * **Singleton set:** S = {5} * **Empty/Null set:** S = {} or Φ * **Finite set:** S = {2, 4, 6, 8} * **Infinite set:** Set of Natural Numbers: {1, 2, 3, 4, 5, ... ∞} * **Subset:** S = {1, 2, 3}, A = {1, 2, 3, 4, 5} * S ⊆ A * **Power set:** A = {1, 2} * P(A) = {Φ, {1}, {2}, {1, 2}} * 'n' no. of elements (A) * 2^n no. of elements (P(A)) * **Universal set:** A = {1, 2}, B = {4, 5}, {cd, 6 , 7} * U = {1, 2, 4, 5, 6, 7} * **Disjoint set:** A = {1, 2}, B = {4, 5} * A ∩ B = Φ ## Basic Operations of a Set - **Union (U):** * A = = {1, 2, 3, 4} * B = {3, 4, 5, 6} * A ∪ B = {1, 2, 3, 4, 5, 6} - **Intersection (∩):** * A = {1, 2, 3, 4} * B = {3, 4, 5, 6} * A ∩ B = {3, 4} - **Difference (-):** * A = {1, 2, 3, 4} * B = {3, 4, 5, 6} * A - B = {1, 2} - **Cartesian product of 2 sets (×):** * X = {1, 2} * Y = {8, 9} * X × Y = {(1, 8), (1, 9), (2, 8), (2, 9)} * Eg: * x ∩ (Y - x) = Φ * x ∩ (Y - x) = Φ ## Relations * **Relation:** A subset of X × Y * X = {1, 2} * Y = {8, 9} * X × Y = {(1, 8), (1, 9), (2, 8), (2, 9)} * Total no. of Relations: 2^m+n * Domain: {1, 2} * Range: {8, 9} ## Types of Relations * **Empty:** No relation exists between any items of a set. * Eg: A = {1, 2, 3}, B = {8, 9} * R = {(a, b) ϵR iff & only if a=b} * R = {}. * **Universal (Full):** R = A × A * If each element of A is related to every element of A (have all elements). * Eg: "height of students greater than 5 cm" * **Identity:** A = {1, 2, 3} * R = {(1, 1), (2, 2), (3, 3)} * **Inverse:** * R = {(1, 2), (2, 5), (6, 4)} * R⁻¹ = {(2, 1), (5, 2), (4, 6)} * **Reflexive:** A = {1, 2, 3} * A × A = {(a, a)} pairs * R = {(1, 1), (2, 2), (3, 3)} = `{(1, 1),` `(2, 2),` `(3, 3)}` * **Symmetric:** A = {1, 2}, B = {1, 2, 4} * R = {(1, 2), (2, 1)} * R = {(1, 2), (2, 1), (2, 2)} * R = {} * **Antisymmetric:** (a, b) ϵR, (b, a) ϵR iff a = b. * A = {1, 2, 3} * R = {(1, 2), (2, 1)} × R = {} √ * R = {(1, 2), (1, 1)} √ * **Transitive:** A→B, B→C, A→C * (A, B), (B, C), (A, C) * R₁ = {} * R₂ = {(1, 1)} * R₃ = {(1, 2), (2, 1), (1, 1)} * R₄ = {(5, 6), (6, 7), (5, 7)} * **Equivalence Relation:** R + S + T * X = {a, b, c} * R₁ = {} * R₂ = {(a, a), (b, b), (c, c)} * R₃ = {(a, a), (b, b), (c, c), (b, a), (a, b)} * R₄ = {(a, a), (b, b), (c, c), (a, b)} * **POSET:** Partial ordering Relation * Partially Ordered Set: R + Antisy + T * → [X, R] * X = {a, b, c} * R₁ = {(a, a), (b, b), (c, c)} * R₂ = {(a, a), (b, b) (c, c), (a, b), (b, c), (a, c)} * R₃ = {} ## Hasse Diagram * **Convert POR into Hasse diagram:** 1. Plot a vertex for every element of set. 2. Draw an edge between x & y if (x, y) ϵR . 3. No need of Reflexive & Transitive edges. Remove them.. 4. No directions needed (edges) (upwards orientation). * Eg: A = {4, 5, 6, 7} * R = {(4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 7), (4, 4), (5, 5), (6, 6), (7, 7)} ## Lattice * A Hasse Diagram with a condition: * (Join & Meet for each pair of element). * **Join:** 3 ∨ 4 = 7 * 3 ∨ 4 = 2 ↑ * **Meet:** 2 ∨ 3 = 4 * 2 ∨ 3 = 1 * but 5 ∨ 6 = 4 * **Eg:** * R = {( 2, 2), (2, 3), (2, 4), (2, 7), (3, 3), (3, 7), (4, 4), (4, 7), (7, 7)}. * A = {2, 3, 4, 7} * 2 is Covering, or related to all. ## Finding Complement * **Eg:** * 2 ∨ 3 = 4 ϵUB * 2 ∧ 3 = 1 ϵLB * So 2 & 3 are complement of each other. * e ∨ eᶜ = UB * e ∧ eᶜ = LB * **Distributive:** (0 or 1) atmost 1 * **Complement:** (1 or more) at least ## Totally Ordered Set * POSET + All elements in set are comparable with each other. * Eg: X = {a, b, c} * Relation: a ≤ b, a ≤ c, b ≤ c ## Venn Diagram * U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} * A = {1, 2, 3} * B = {3, 4, 5} * AUB = {1, 2, 3, 4, 5} * A∩B = {3} ## Symmetric Difference * A + B = {1, 2, 4, 5} (not for both) * A = {4, 5, 6, 7, 8, 9, 10} * B = {3, 4, 5} * (AUB) - B = {1, 2, 3, 4, 5} - {3, 4, 5} * = {1, 2} ## Difference * A–B = {1, 2} ## Multiset * A = {Multiple Copies of elements in a set}. * Eg: {1, 1, 2, 2, 3, 3} * Multiplicity {1 = 2, 2 = 2, 3 = 2} * A = [1 ,1, 2, 2, 3, 4] * B = [1, 1, 2, 2, 6, 6, 6] * AUB → [1, 1, 2, 2, 3, 4, 6, 6] * A∩B → [1, 1, 2, 2] * A–B → [3, 4] ## Inclusion and Exclusion Principle - **n(AUB) = n(A) + n(B) – n(A∩B)** - **n(AUBUC) = n(A) + n(B) + n(C) – n(A∩B) – n(A∩C) – n(B∩C) + n(A∩B∩C)** * Eg: * n(S1) → 49 * n(S2) → 37 * n(S3) → 21 * n(S1∩S2) → 9 * n(S1∩S3) → 5 * n(S2∩S3) → 4 * n(S1∩S2∩S3) = 3 * To find: * n(S1US2US3) = n(S1) + n(S2) + n(S3) – n(S1∩S2) – n(S1∩S3) – n(S2∩S3) + n(S1∩S2∩S3) * = 49 + 37 + 21 – 9 – 4 – 5 + 3 * = 92 * n(S1US2US3) = U – n(S1US2US3) * = 100 – 92 * = 8 ## Mathematical Induction 1. **n = 1 (k is any integer)** 2. **n = k** 3. **n = k + 1** * Eg: 1 + 3 + 5 +...(2n-1) = n^2 1. **L.H.S (1 + 3 + 5 + ... + (2n-1)** * ↓ * 2(1)-1 = 1 2. **R.H.S: (n)^2 ** * (1)^2 = 1 * L.H.S = R.H.S [True for n = 1] 3. **Assume result is true for n = k** * 1 + 3 + 5 + ... + (2k – 1) = k^2 4. **Check it for n = k+1** * 1 + 3 + 5 + ... + (2(k+1) – 1) = (k+1)^2 * 1 + 3 + 5 + ... + (2k – 1) + (2(k+1) – 1) = (k+1)^2 * ↓ * k^2 + (2(k+1) – 1) = (k+1)^2 * k^2 + 2k + 2 – 1 = (k+1)^2 * k^2 + 2k + 1 = (k+1)^2 * (k+1)^2 = (k+1)^2 * L.H.S = R.H.S [True for n = k+1] * Eg: 1 + 2 + 3 +... n = n(n+1)/2 1. **n = 1** * L.H.S: 1 * R.H.S: 1(1+1)/2 = 1 [True for n = 1] 2. **Assume result is true for n = k:** * 1 + 2 + 3 +... k = k(k+1)/2 3. **n = k+1** * 1 + 2 + 3 +... + (k+1) = (k+1)(k+1+1)/2 * 1 + 2 + 3 +... k + (k+1) = (k+1)(k+2)/2 * ↓ * k(k+1)/2 + (k+1) = (k+1)(k+2)/2 * (k+1)(k + 2)/2 = (k+1)(k+2)/2 * L.H.S = R.H.S [True for n = k+1] ## Propositional Logic * **Basic unit of Logic:** A statement/ sentence that can be T or F but not both.. * 2 + 3 = 5 √ * "Hello. & welcome Dasto" X ## Connectives (operators) * **NOT/ Negation (~):** Given → Result(~) * T → F * F → T * **Conjunction (∧) (and)** * | A | B | A ∧ B | * |---|---|---| * | T | T | T | * | T | F | F | * | F | T | F | * | F | F | F | * **Disjunction (∨) (or)** * | A | B | A ∨ B | * |---|---|---| * | T | T | T | * | T | F | T | * | F | T | T | * | F | F | F | * **Implication (→):** If A then B * | A | B | (A → B) | * |---|---|---| * | T | T | T | * | T | F | F | * | F | T | T | * | F | F | T | * **Exclusive Or (⊕):** * | A | B | A ⊕ B | * |---|---|---| * | T | T | F | * | T | F | T | * | F | T | T | * | F | F | F | * **Double Implication (↔):** Same (T) * | A | B | A ↔ B | * |---|---|---| * | T | T | T | * | T | F | F | * | F | T | F | * | F | F | T | * **Converse:** "Given A → B" * B → A * **Inverse:** ~A → ~B * **Contrapositive:** ~B → ~A ## Tautology, Contradiction, and Contingency * **Tautology:** (All True) * **Contradiction:** (All False) * **Contingency:** (both True & False) * **Eg:** * (A ∧ B) ^ ~(A V B) * | A | B | A ∧ B | A V B | ~(A V B) | (A ∧ B) ^ ~(A V B) | * |---|---|---|---|---|---| * | T | T | T | T | F | F | * | T | F | F | T | F | F | * | F | T | F | T | F | F | * | F | F | F | F | T | F | * Contradiction * **Eg:** [(A → B) ∧ A] → B * | A | B | A → B | (A → B) ∧ A | [(A → B) ∧ A] → B | * |---|---|---|---|---| * | T | T | T | T | T | * | T | F | F | F | T | * | F | T | T | F | T | * | F | F | T | F | T | * Tautology * **Eg:** (A V B) ^ (~ A) * | A | B | ~A | A V B | (A V B) ∧ (~A) | * |---|---|---|---|---| * | T | T | F | T | F | * | T | F | F | T | F | * | F | T | T | T | T | * | F | F | T | F | F | * Contingency ## Propositional Equivalences * **Same truth values:** (Truth table match) * **A → B is Tautology** * **I) ~(A V B)** * **II) (~A) ∧ (~B)** * | A | B | ~A | ~B | (A V B) | ~(A V B) | ~A ∧ ~B | * |---|---|---|---|---|---|---| * | T | T | F | F | T | F | F | * | T | F | F | T | T | F | F | * | F | T | T | F | T | F | F | * | F | F | T | T | F | T | T | * [~(A V B)] ↔ [(~ A) ∧ (~B)] * T → T * T → T * T → T * T → T * Tautology ## Laws * **Idempotence** * P ∨ P = P * P ∧ P = P * **Commutative:** * P ∨ q = q ∨ p * P ∧ q = q ∧ p * **Associative:** * P ∨ (q ∨ r) = (p ∨ q) ∨ r * P ∧ (q ∧ r) = (p ∧ q) ∧ r * **Distributive:** * P ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) * P ∨ (q ∧ r) = (p ∨ q) ∧ (p ∨ r) * **Double negation:** * ~( ~p) = p * **De Morgan:** * ~(p ∧ q) = ~p ∨ ~q * ~(p ∨ q) = ~p ∧ ~q ## Identity * P ∨ T = T * P ∨ F = P * P ∧ T = P * P ∧ F = F ## Normal Form * **Disjunctive (DNF)** * Disjunction (OR) between conjunction.(AND * (A ∧ B) ∨ (A ∧ B) * (A and B) OR (¬A and B) * **Conjunctive (CNF)** * Conjunction (AND) between Disjunction (OR) * (A ∨ B) ∧ (¬A ∨ B) * ( A OR B) and (¬A OR B) * **Eg:** * (¬x ∨ ¬y) ∧ (¬y ∨ x) (find DNF) * [(¬x ∨ ¬y) ∧ ¬y] ∨ [(¬x ∨ ¬y) ∧ x] * [(¬x ∨ ¬y) ∨ (¬y ∧ x) ] ∨ [(¬x ∧ x) ∨ (¬y ∧ x)] * [(¬x ∨ ¬y) ∨ F ] ∨ [F ∨ (¬y ∧ x)] * (¬x ∧ ¬y) ∨ (Y ∧ X) → DNF * **Eg:** A ∧ (A → B) * A ∧ (~A ∨ B) * (A ∧ ¬A) ∨ (A ∧ B) * F ∨ (A ∧ B) * (A ∧ B) → CNF ## Argument * (P₁ ∧ P₂ ∧ … ∧ Pₙ) * (P₁ , P₂ … Pₙ) * (P₁ ∧ P₂ ∧ … ∧ Pₙ) → C ## Modus Ponens (Given (True), Find Given (True)) * P₁: P → q (True) * P₂: P (True) * | P | q | P → q | * |---|---|---| * | T | T | T | √ * | T | F | F | * | F | T | T | * | F | F | T | ## Modus Tollen * P₁: P → q (True) * P₂: ¬q (False) * ¬p (False) ] * Here q & P are false (Given) ## Hypothetical Syllogism * P₁: P → q (True) * P₂: q → r (True) * P → r (True) * (P → q) ∧ (q → r) → (P → r) * | P | q | r | P → q | q → r | (p → q) ∧ (q → r) | (p → q) ∧ (q → r) → (p → r) | * |---|---|---|---|---|---|---| * | T | T | T | T | T | T | T | * | T | T | F | T | F | F | T | * | T | F | T | F | T | F | T | * | T | F | F | F | T | F | T | * | F | T | T | T | T | T | T | * | F | T | F | T | F | F | T | * | F | F | T | T | T | T | T | * | F | F | F | T | T | T | T | * Eg: * A: I will study. * B: I will play. * P₁: (I will study) or (I will play) * P₂: (I will not study) * P₁: A ∨ B * P₂: ¬A * B √ valid Argument * Eg: * A: I study from 5ME. * B: I am prepared for exam. * C: I will pass my exam. * If I study from 5ME, I am prepared for exam. If I am prepared for exam, I will pass my exam. Therefore if I study from 5ME then I will pass my exam. * P₁: A → B * P₂: B → C * A → C √ valid ## Quantifiers * **For all (∀):** Universal * **There exists (∃):** Existential * ∀x f(x) * ∃x f(x) * Eg: * All Engineers love 5ME * Some Engineers love 5ME or at least one engineer love 5ME ## Negation * ∀x f(x) → ∃x¬f(x) * ∀x[¬f(x)] → ∃x[f(x)] * Eg: P(x): x is student Q(x): x is a boy * Every child is not a student * ∀x [¬P(x)] * Every child is a student * ∀x [P(x)] * Every child is girl * ∀x [¬Q(x)] * ¬(∀x f(x)) = ∃x ¬f(x) * ¬(∃x f(x)) = ∀x ¬f(x) * Eg: Not all students are naughty. * ∃x [Student(x) ∧ ¬Naughty(x)] * ∀x [¬S(x) ∨ ¬N(x)] = ∀x [S(x) → ¬N(x)] ## Function * **Set 1:** x, y, z * **Set 2:** a, b, c * **Function Composition:** * f(g(x)) = f o g(x) * g(f(x)) = g o f(x) * **Eg:** * x | f | y | g | z * ---|---|---|---|---| * 1 | 5 | 5 | 8 | 8 * 2 | 7 | 6 | 3 | 9 * 3 | 6 | 7 | 9 | * f = {(1, 5), (2, 7), (3, 6)} * g = {(5, 8), (6, 3), (7, 9)} * f(x) → y * 1 → 5 * 2 → 7 * 3 → 6 * g(y) → z * 5 → 8 * 6 → 3 * 7 → 9 * g o f (f(x)) = {(1, 8), (2, 3), (3, 8)} * **Eg:** f(x) = 2x + 1, g(x) = x + 1 find f o g(x) if x = 1 * f → g * f o g(x) = f(g(x)) * = f(x + 1) * = 2(x + 1) * Now put x = 1 * ... 2 (1 + 1) = 2 x 2 = 4 ## Injective Function (one to One) * | A | B | * |---|---| * | 1 | a | * | 2 | b | * | 3 | c | * | 1 | a | * | 2 | b | * | 3 | c | * | 1 | a | * | 2 | b | * | 3 | c | * | 4 | d | * Possible no. of fn. * | 1 | 2 | 3 | 4 | * |---|---|---|---| * | 1 | a | b | c | * | 2 | a | b | c | * | 3 | a | b | c | * 4 × 3 × 2 = 24 * Formula = n / (n – m)! * = 4! / (4 - 4)! * = 4! / 0! * = 24 / 1 * = 4 × 3 × 2 × 1 * = 24 ## Surjective Function (visit/ covers all elements of Range) * | A | B | * |---|---| * | 1 | a | (onto) * | 2 | b | * | 3 | c | * | A | B | * |---|---| * | 1 | a | * | 2 | b | * | 3 | c | * | A | B | * |---|---| * | 1 | a | * | 2 | b | √ one to one * | 3 | a | onto * | 3 | c | * | 3 | d | * Domain - Range * n(A) > n(B) ## Bijective Function * n(A) = n(B) * | A | B | * |---|---| * | 1 | a | * | 2 | b | * | 3 | c | * | A | B | * |---|---| * | 1 | a | * | 2 | b | * | 3 | c | * | A | B | * |---|---| * | 1 | a | * | 2 | b | * | 3 | c | * Possible fns. * | 1 | 2 | 3 | … | n | * |---|---|---|---|---| * | 1 | a | b | … | n | * | 2 | a | b | … | n | * | 3 | a | b | … | n | * | … | a | b | … | n | * | n| a | b | … | n | * n! ## Inverse of Function (Reverse) * f(x) = y then f⁻¹(y) = x. * f⁻¹ must be bijective * Not possible with one to one or onto * Eg: f(x) = 1 + 2x f⁻¹(y) = (y – 1)/2 * Let x = 1 * 1 + 2 (1) = 3 * (3-1)/2 = 1 ## Combinatorics * **Combination:** Order does not matter. * Eg: Faluda * ⁿCₖ = n! / (k! (n – k)!) * Eg: Select 5 out of 25: * ²⁵C₅ = 25! / (5! (25 - 5)!) * = 25 × 24 × 23 × 22 × 21 / 5 × 4 × 3 × 2 × 1 * = 53130 * **Permutation:** Order matters. * Eg: Lock-key-password * ⁿPₖ= n! / (n – k)! * Eg: Set (n items). Want K items arrangements. * 1 2 3 4 * n = 4 * K = 2 * ⁴P₂ = 4! / (4 – 2)! * = 4 × 3 × 2 × 1 / 2 × 1 * = 12 * **Sum Rule:** * 'OR' * Task 1 * m choices * Task 2 * n choices * m + n * (2 tasks cannot be done at same time) * n(AUB) = n(A) + n(B) ## Product Rule - Task 1 * m choices - Task 2 * n choices - m x n * n(A x B) = n(A) . n(B) (Task 2 after Task 1) * Eg: 3-digit numbers from digits 1, 2, 3, 4, 5 * (Repetition allowed) * H T U = 5 × 5 × 5 = 5^3 = 125 * (Without Repetition) (1, 2, 3, 4, 5) * H T U * n = 5 * K = 3 * ⁵P₃ = 5! / (5 – 3)! * = 5 × 4 × 3 × 2 ×