SET THEORY A Practical Guide for MCA, BCA & Computer Science Students Concepts • Operations • Laws • Applications • Solved Examples • Practice Questions
Table of Contents CHAPTER 1: Introduction to Sets CHAPTER 2: Set Operations CHAPTER 3: Laws of Set Theory CHAPTER 4: Relations CHAPTER 5: Functions CHAPTER 6: Cardinality and Countability CHAPTER 7: Ordered Sets and Lattices CHAPTER 8: Boolean Algebra CHAPTER 9: Propositional Logic CHAPTER 10: Predicate Logic CHAPTER 11: Set Theory in Databases CHAPTER 12: Set Theory in SQL CHAPTER 13: Set Theory in Python CHAPTER 14: Set Theory in Java CHAPTER 15: Graph Theory Basics CHAPTER 16: Trees and Hierarchies CHAPTER 17: Combinatorics CHAPTER 18: Probability Theory CHAPTER 19: Set Theory in Machine Learning CHAPTER 20: Advanced Topics and Applications Solved Examples Quick Revision & Formula Sheet Key Points to Remember References
CHAPTER 1: Introduction to Sets 1.1 What Is a Set? A set is a well-defined collection of distinct objects, considered as an object in its own right. Objects in a set are called elements or members. Sets are denoted by capital letters (A, B, C) and elements by lowercase letters (a, b, c). If element a belongs to set A, we write: a ∈ A (read: "a is an element of A") If a does not belong to A, we write: a ∉ A 📘 Definition: A set is a well-defined collection of distinct objects. "Well-defined" means we can unambiguously determine whether any object belongs to the set or not. 1.2 Notation Methods Three ways to represent sets: Roster Form: A = {2, 4, 6, 8, 10} Set-Builder Form: A = {x | x is even, 1 ≤ x ≤ 10} Descriptive Form: "The set of first five even positive integers" 1.3 Types of Sets Empty Set (∅): Contains no elements. Example: {x | x² = −1, x ∈ ℝ} Singleton Set: Contains exactly one element. Example: {7} Finite Set: Has countable elements. Example: {1, 2, 3, ..., 100} Infinite Set: Has unlimited elements. Example: ℕ = {1, 2, 3, ...} Equal Sets: A = B if they contain exactly the same elements Equivalent Sets: |A| = |B| if they have the same cardinality 1.4 Examples Beginner: A = {Alice, Bob, Carol} — students in a class Intermediate: B = {x | x is a book on Data Structures in the library} Practical: C = {all contacts in your WhatsApp} 💡 Quick Tip: In Python, use set() to create sets. Sets automatically eliminate duplicates. ⚠ Common Mistake: Confusing equal sets with equivalent sets. Equal sets must have identical elements; equivalent sets just need the same count. 🎯 Exam Point: Always verify if a set is well-defined before working with it. 🚀 MCA Application: Sets form the foundation of Data Structures, Databases, and Relational Algebra. 💻 Programming Insight: Python sets use {1, 2, 3} syntax and support operations like union (|), intersection (&), difference (-). 1.5 Chapter Summary Key Takeaways Sets are fundamental to discrete mathematics and computer science Important Symbols ∈ (element of), ∉ (not element of), ∅ (empty set) Memory Tip "Well-defined" = you can always tell if something is in or out Quick Revision Three notation methods, six types of sets, clear definitions Practice Questions MCQ: Which is a well-defined set? (a) Beautiful flowers (b) Even numbers (c) Tall students (d) Good books1. MCQ: If A = {1, 2, 3} and B = {3, 2, 1}, then A and B are: (a) Equal (b) Equivalent (c) Disjoint (d) Subsets2. MCQ: The cardinality of {a, b, c} is: (a) 0 (b) 1 (c) 3 (d) Infinite3. Short Answer: Define a singleton set with an example.4. Short Answer: Write {x | x is a prime number less than 10} in roster form.5. Application: Your college has 500 students. How would you represent this as a set in a database?6. Answer Key: 1-b, 2-a, 3-c, 4-A set with exactly one element, e.g., {5}, 5-{2,3,5,7}, 6-Students = {s₁, s₂, ..., s₅₀₀} where each sᵢ is a student record
CHAPTER 2: Set Operations 2.1 Union of Sets The union of sets A and B is the set of all elements that belong to A, or B, or both. Denoted: A ∪ B = {x | x ∈ A or x ∈ B} Example: A = {1, 2, 3}, B = {3, 4, 5} → A ∪ B = {1, 2, 3, 4, 5} 📘 Definition: Union combines all elements from both sets without repetition. 💡 Quick Tip: In SQL, UNION combines rows from multiple tables. 🚀 MCA Application: Database queries use UNION to merge result sets. 💻 Programming: A | B in Python performs union operation. 2.2 Intersection of Sets The intersection of A and B is the set of all elements in both A and B. Denoted: A ∩ B = {x | x ∈ A and x ∈ B} Example: A = {1, 2, 3}, B = {3, 4, 5} → A ∩ B = {3} 📘 Definition: Intersection finds common elements. ⚠ Common Mistake: Confusing union with intersection. 🎯 Exam Point: If A ∩ B = ∅, sets are disjoint. 💻 Programming: A & B in Python performs intersection. 2.3 Complement of a Set The complement of A (denoted A' or Aᶜ) is the set of all elements in universal set U that are not in A. A' = {x | x ∈ U and x ∉ A} Example: If U = {1, 2, 3, 4, 5} and A = {1, 3}, then A' = {2, 4, 5} 📘 Definition: Complement contains everything outside the set. 🚀 MCA Application: Database NOT operations use complement logic. 2.4 Difference of Sets The difference A − B is the set of elements in A but not in B. A − B = {x | x ∈ A and x ∉ B} Example: A = {1, 2, 3}, B = {3, 4, 5} → A − B = {1, 2} 💻 Programming: A - B in Python performs difference. 2.5 Symmetric Difference The symmetric difference A △ B contains elements in either A or B but not both. A △ B = (A − B) ∪ (B − A) Example: A = {1, 2, 3}, B = {3, 4, 5} → A △ B = {1, 2, 4, 5} 💻 Programming: A ^ B in Python performs symmetric difference. 2.6 Venn Diagrams Visual representation of sets and their operations using overlapping circles. Helps understand relationships between sets intuitively. 2.7 Examples Beginner: Library books — Union finds all books, Intersection finds books in multiple categories Intermediate: Database tables — UNION ALL combines records, INTERSECT finds common records Practical: Social media — Union of followers, Intersection of mutual friends 2.8 Chapter Summary Key Operations Union (∪), Intersection (∩), Complement ('), Difference (−), Symmetric Difference (△) Important Formulas De Morgan's Laws, Distributive Laws Memory Tip Union = OR, Intersection = AND, Complement = NOT Quick Revision Five main operations with clear definitions and examples Practice Questions MCQ: If A = {1,2,3} and B = {2,3,4}, then A ∪ B = ? (a) {2,3} (b) {1,2,3,4} (c) {1,4} (d) ∅1. MCQ: A ∩ B when A and B are disjoint equals: (a) A (b) B (c) ∅ (d) U2. MCQ: If U = {1,2,3,4,5} and A = {1,3,5}, then A' = ? (a) {2,4} (b) {1,3,5} (c) ∅ (d) U3. Short Answer: Find A − B where A = {a,b,c,d} and B = {c,d,e,f}4. Short Answer: Explain symmetric difference with an example.5. Application: In a college database, how would you find students who are in CS department OR IT department?6. Answer Key: 1-b, 2-c, 3-a, 4-{a,b}, 5-Elements in either set but not both, e.g., {1,2,3} △ {2,3,4} = {1,4}, 6-SELECT * FROM Students WHERE Department = 'CS' UNION SELECT * FROM Students WHERE Department = 'IT'
CHAPTER 3: Laws of Set Theory 3.1 Commutative Laws A ∪ B = B ∪ A (Union is commutative) A ∩ B = B ∩ A (Intersection is commutative) Meaning: Order doesn't matter in union and intersection operations. 3.2 Associative Laws (A ∪ B) ∪ C = A ∪ (B ∪ C) (A ∩ B) ∩ C = A ∩ (B ∩ C) Meaning: Grouping doesn't matter in union and intersection. 3.3 Distributive Laws A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) Meaning: Union distributes over intersection and vice versa. 3.4 Identity Laws A ∪ ∅ = A (Union with empty set) A ∩ U = A (Intersection with universal set) 3.5 Complement Laws A ∪ A' = U (Union with complement gives universal set) A ∩ A' = ∅ (Intersection with complement gives empty set) (A')' = A (Double complement equals original set) 3.6 De Morgan's Laws (A ∪ B)' = A' ∩ B' (Complement of union equals intersection of complements) (A ∩ B)' = A' ∪ B' (Complement of intersection equals union of complements) 💡 Quick Tip: De Morgan's Laws are crucial in logic and database queries. 🎯 Exam Point: These laws are frequently tested in exams. 🚀 MCA Application: Used in SQL WHERE clauses and boolean logic. 3.7 Idempotent Laws A ∪ A = A A ∩ A = A 3.8 Absorption Laws A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A 3.9 Examples Beginner: Verify A ∪ B = B ∪ A with A = {1,2}, B = {2,3} Intermediate: Apply De Morgan's Law to database queries Practical: Use distributive law to simplify complex set expressions 3.10 Chapter Summary Key Laws Commutative, Associative, Distributive, Identity, Complement, De Morgan's Important De Morgan's Laws are most frequently used Memory Tip Laws help simplify complex set expressions Quick Revision 8 major laws with clear definitions Practice Questions MCQ: Which law states (A ∪ B)' = A' ∩ B'? (a) Distributive (b) De Morgan's (c) Associative (d) Commutative1. MCQ: A ∪ A = ? (a) ∅ (b) A (c) U (d) A'2. MCQ: (A')' = ? (a) A (b) ∅ (c) U (d) A'3. Short Answer: Verify the distributive law A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) with A = {1,2,3}, B = {2,3,4}, C = {3,4,5}4. Short Answer: Apply De Morgan's Law to simplify (A ∪ B)'5. Application: How would you use De Morgan's Law in a SQL NOT query?6. Answer Key: 1-b, 2-b, 3-a, 4-LHS = {1,2,3} ∩ {2,3,4,5} = {2,3}, RHS = {2,3} ∪ {3} = {2,3} ✓, 5-A' ∩ B', 6-NOT (A OR B) = (NOT A) AND (NOT B)
CHAPTER 4: Relations 4.1 What Is a Relation? A relation R from set A to set B is a subset of the Cartesian product A × B. It defines a connection between elements of A and elements of B. Notation: R ⊆ A × B Example: If A = {1, 2} and B = {a, b}, then A × B = {(1,a), (1,b), (2,a), (2,b)} A relation could be R = {(1,a), (2,b)} 📘 Definition: A relation is a set of ordered pairs showing connections between elements. 4.2 Types of Relations Reflexive: Every element is related to itself. (a,a) ∈ R for all a ∈ A Symmetric: If (a,b) ∈ R, then (b,a) ∈ R Transitive: If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R Equivalence: Reflexive, symmetric, and transitive 4.3 Domain and Range Domain: Set of all first elements in ordered pairs Range: Set of all second elements in ordered pairs Example: R = {(1,a), (2,b), (3,a)} Domain = {1, 2, 3}, Range = {a, b} 4.4 Representation of Relations Set notation: R = {(1,a), (2,b)} Matrix representation: Using 0s and 1s Directed graph: Using nodes and arrows 4.5 Cartesian Product A × B = {(a,b) | a ∈ A and b ∈ B} Properties: A × B ≠ B × A (not commutative) |A × B| = |A| × |B| 4.6 Examples Beginner: Student-Course relation showing which students take which courses Intermediate: Employee-Department relation in a database Practical: Social media "follows" relation between users 💻 Programming: Relations are implemented as tables in databases with foreign keys. 🚀 MCA Application: Database design heavily relies on relations. 4.7 Chapter Summary Key Concepts Cartesian product, domain, range, types of relations Important Equivalence relations partition sets Memory Tip Relations connect elements from two sets Quick Revision Definition, types, and representations Practice Questions MCQ: If A = {1,2} and B = {a,b}, then |A × B| = ? (a) 2 (b) 4 (c) 6 (d) 81. MCQ: A relation that is reflexive, symmetric, and transitive is: (a) Partial order (b) Equivalence (c) Function (d) Bijection2. MCQ: If R = {(1,2), (2,3), (3,4)}, the domain is: (a) {1,2,3} (b) {2,3,4} (c) {1,2,3,4} (d) ∅3. Short Answer: Define a reflexive relation with an example.4. Short Answer: Find the Cartesian product A × B where A = {1,2} and B = {x,y,z}5. Application: How would you represent a student-course enrollment as a relation in a database?6. Answer Key: 1-b, 2-b, 3-a, 4-A relation where every element is related to itself, e.g., "equals" relation, 5-{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}, 6-Enrollment table with StudentID and CourseID as foreign keys
CHAPTER 5: Functions 5.1 What Is a Function? A function f from set A to set B is a special relation where each element of A is related to exactly one element of B. Notation: f: A → B Meaning: For every a ∈ A, there exists exactly one b ∈ B such that f(a) = b 📘 Definition: A function is a relation where each input has exactly one output. 5.2 Domain, Codomain, and Range Domain: Set A (all possible inputs) Codomain: Set B (all possible outputs) Range: Subset of B containing actual outputs Example: f: {1,2,3} → {a,b,c,d} where f(1)=a, f(2)=b, f(3)=a Domain = {1,2,3}, Codomain = {a,b,c,d}, Range = {a,b} 5.3 Types of Functions Injective (One-to-One): Different inputs map to different outputs. If f(a) = f(b), then a = b Surjective (Onto): Every element in codomain is mapped to. Range = Codomain Bijective: Both injective and surjective. Perfect one-to-one correspondence 5.4 Function Composition If f: A → B and g: B → C, then (g f): A → C (g f)(a) = g(f(a)) Example: f(x) = 2x, g(x) = x + 1 (g f)(3) = g(f(3)) = g(6) = 7 5.5 Inverse Functions If f: A → B is bijective, then f⁻¹: B → A exists f⁻¹(f(a)) = a for all a ∈ A 5.6 Examples Beginner: f(x) = 2x from {1,2,3} to {2,4,6} Intermediate: Database query mapping StudentID to StudentName Practical: Hash function mapping data to hash values 💻 Programming: Functions are fundamental in all programming languages. 🚀 MCA Application: Functions model data transformations in databases. 🗄 SQL Example: SELECT StudentName FROM Students WHERE StudentID = 5 (function application) 5.7 Chapter Summary Key Concepts Domain, codomain, range, types of functions Important Bijective functions have inverses Memory Tip Each input maps to exactly one output Quick Revision Definition, types, composition, and inverses Practice Questions MCQ: A function where each output has at most one input is: (a) Surjective (b) Injective (c) Bijective (d) Composite1. MCQ: If f: {1,2,3} → {a,b}, can f be surjective? (a) Yes (b) No (c) Only if injective (d) Only if bijective2. MCQ: If f(x) = x² from ℝ to ℝ, is f injective? (a) Yes (b) No (c) Only for positive x (d) Only for integers3. Short Answer: Define an injective function with an example.4. Short Answer: If f(x) = 2x + 1 and g(x) = x - 1, find (g f)(2)5. Application: How would you use functions to map employee IDs to salaries in a database?6. Answer Key: 1-b, 2-a, 3-b (f(-2) = f(2) = 4), 4-A function where different inputs give different outputs, e.g., f(x) = 2x, 5-(g f)(2) = g(f(2)) = 4, 6-CREATE FUNCTION GetSalary(EmpID INT) RETURNS DECIMAL AS SELECT Salary FROM Employees WHERE EmployeeID = EmpID
CHAPTER 6: Cardinality and Countability 6.1 What Is Cardinality? Cardinality is the number of elements in a set. Denoted |A| or card(A). Example: |{1, 2, 3}| = 3, |∅| = 0, |ℕ| = ∞ 📘 Definition: Cardinality measures the "size" of a set. 6.2 Finite and Infinite Sets Finite Set: Has a definite number of elements Infinite Set: Has unlimited elements Countably Infinite: Can be listed in sequence (ℕ, ℤ, ℚ) Uncountably Infinite: Cannot be listed (ℝ, ℂ) 6.3 Cardinality of Infinite Sets Two infinite sets have the same cardinality if there exists a bijection between them. Example: |ℕ| = |ℤ| (both countably infinite) But |ℕ| < |ℝ| (ℝ is uncountably infinite) 6.4 Cantor's Diagonal Argument Proves that ℝ is uncountable. No bijection exists between ℕ and ℝ. Cantor's diagonal argument is a groundbreaking proof demonstrating that the set of real numbers (ℝ) is "larger" than the set of natural numbers (ℕ), meaning ℝ is uncountably infinite. 6.5 Power Set The power set P(A) is the set of all subsets of A. |P(A)| = 2^|A| Example: If A = {1, 2}, then P(A) = {∅, {1}, {2}, {1,2}} |P(A)| = 2² = 4 6.6 Examples Beginner: Cardinality of {a, b, c, d} is 4 Intermediate: Comparing cardinalities of ℕ and ℤ Practical: Database table cardinality (number of rows) 🚀 MCA Application: Cardinality is crucial in database design and query optimization. 💻 Programming: Understanding cardinality helps optimize data structures. 6.7 Chapter Summary Key Concepts Cardinality, finite/infinite sets, countability Important Cantor's theorem on power sets Memory Tip |P(A)| = 2^|A| Quick Revision Definition and types of cardinality Practice Questions
CHAPTER 7: Ordered Sets and Lattices 7.1 Partially Ordered Sets (Posets) A partially ordered set is a set with a relation that is reflexive, antisymmetric, and transitive. Notation: (A, ≤) where ≤ is the partial order Example: (ℕ, ≤) where ≤ is the "less than or equal to" relation 7.2 Total Order A total order is a partial order where every two elements are comparable. Example: (ℝ, ≤) is a total order 7.3 Lattices A lattice is a partially ordered set where every two elements have a least upper bound (join) and greatest lower bound (meet). Notation: L = (A, ∨, ∧) where ∨ is join and ∧ is meet 7.4 Properties of Lattices Commutative: a ∨ b = b ∨ a Associative: (a ∨ b) ∨ c = a ∨ (b ∨ c) Idempotent: a ∨ a = a Absorption: a ∨ (a ∧ b) = a 7.5 Boolean Lattices A Boolean lattice is a complemented distributive lattice. Example: The power set P(A) with union and intersection forms a Boolean lattice 7.6 Examples Beginner: Divisibility relation on {1, 2, 3, 4, 6, 12} Intermediate: Subset relation on power sets Practical: Organizational hierarchy in a company 🚀 MCA Application: Lattices model database schemas and type hierarchies. 7.7 Chapter Summary Key Concepts Partial orders, total orders, lattices Important Lattices have join and meet operations Memory Tip Lattices are structured partially ordered sets Quick Revision Definition and properties Practice Questions MCQ: A relation that is reflexive, antisymmetric, and transitive is: (a) Equivalence (b) Partial order (c) Function (d) Bijection1. MCQ: In a lattice, the join of a and b is: (a) Minimum (b) Maximum (c) Least upper bound (d) Greatest lower bound2. Short Answer: Define a total order with an example.3. Short Answer: Explain the difference between partial order and total order.4. Application: How are lattices used in database schema design?5. Answer Key: 1-b, 2-c, 3-A partial order where all elements are comparable, e.g., (ℝ, ≤), 4-Partial order: not all elements comparable; Total order: all elements comparable, 5- Lattices model inheritance hierarchies and type relationships in databases
CHAPTER 8: Boolean Algebra 8.1 What Is Boolean Algebra? Boolean algebra is an algebraic structure with two binary operations (AND, OR) and one unary operation (NOT) on a set of two values: true (1) and false (0). Notation: B = {0, 1} with operations ∧ (AND), ∨ (OR), ' (NOT) 8.2 Basic Operations AND (∧): 1 ∧ 1 = 1, all others = 0 OR (∨): 0 ∨ 0 = 0, all others = 1 NOT ('): 0' = 1, 1' = 0 8.3 Boolean Laws Commutative: a ∨ b = b ∨ a, a ∧ b = b ∧ a Associative: (a ∨ b) ∨ c = a ∨ (b ∨ c) Distributive: a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) De Morgan's: (a ∨ b)' = a' ∧ b', (a ∧ b)' = a' ∨ b' Complement: a ∨ a' = 1, a ∧ a' = 0 Identity: a ∨ 0 = a, a ∧ 1 = a 8.4 Boolean Expressions Expressions combining variables with Boolean operations. Example: f(a,b,c) = (a ∧ b) ∨ (a' ∧ c) 8.5 Simplification Using Boolean laws to simplify expressions. Example: a ∨ (a ∧ b) = a (absorption law) 8.6 Applications Digital circuits and logic gates SQL WHERE clauses Programming conditional statements Database query optimization 💻 Programming: Boolean algebra is fundamental to all digital systems. 🚀 MCA Application: Used in circuit design and logic programming. 8.7 Chapter Summary Key Concepts Boolean operations, laws, expressions Important De Morgan's Laws for simplification Memory Tip 0 = false, 1 = true Quick Revision Three operations and six major laws Practice Questions MCQ: 1 ∧ 0 = ? (a) 0 (b) 1 (c) Undefined (d) Both1. MCQ: (a ∨ b)' = ? (a) a' ∨ b' (b) a' ∧ b' (c) a ∧ b (d) a ∨ b2. MCQ: a ∨ a' = ? (a) 0 (b) 1 (c) a (d) a'3. Short Answer: Simplify a ∨ (a ∧ b) using Boolean laws.4. Short Answer: Write the Boolean expression for "a AND (b OR c)"5. Application: How would you use Boolean algebra in a SQL WHERE clause?6. Answer Key: 1-a, 2-b, 3-b, 4-a (absorption law), 5-a ∧ (b ∨ c), 6-WHERE (condition1 AND (condition2 OR condition3))
CHAPTER 9: Propositional Logic 9.1 What Is Propositional Logic? Propositional logic deals with propositions (statements that are either true or false) and logical connectives. A proposition is a declarative sentence that is either true (T) or false (F). Example: "2 + 2 = 4" is a proposition (true), "5 > 10" is a proposition (false) 9.2 Logical Connectives Negation (¬): NOT p Conjunction (∧): p AND q Disjunction (∨): p OR q Implication (→): if p then q Biconditional (↔): p if and only if q 9.3 Truth Tables Truth tables show the truth value of compound propositions for all possible combinations of component propositions. Example: p ∧ q p q p ∧ q T T T T F F F T F F F F 9.4 Tautologies and Contradictions Tautology: Always true (p ∨ ¬p) Contradiction: Always false (p ∧ ¬p) Contingency: Sometimes true, sometimes false 9.5 Logical Equivalence Two propositions are logically equivalent if they have the same truth value in all cases. Example: ¬(p ∨ q) ≡ ¬p ∧ ¬q (De Morgan's Law) 9.6 Examples Beginner: Simple propositions and truth tables Intermediate: Complex compound propositions Practical: SQL WHERE clauses using logical operators 💻 Programming: Propositional logic is used in conditional statements and boolean expressions. 9.7 Chapter Summary Key Concepts Propositions, connectives, truth tables Important Tautologies and contradictions Memory Tip Truth tables show all possible outcomes Quick Revision Five connectives and their definitions Practice Questions MCQ: Which is a tautology? (a) p ∧ ¬p (b) p ∨ ¬p (c) p ∧ q (d) p → q1. MCQ: ¬(p ∧ q) ≡ ? (a) ¬p ∧ ¬q (b) ¬p ∨ ¬q (c) p ∨ q (d) p ∧ q2. Short Answer: Create a truth table for p → q3. Short Answer: Determine if p ∨ (q ∧ r) is a tautology.4. Application: How would you use propositional logic in a database query?5. Answer Key: 1-b, 2-b, 3-Truth table shows F only when p=T and q=F, 4-No, it depends on values of p, q, r, 5-Use AND/OR operators in WHERE clause to combine conditions
CHAPTER 10: Predicate Logic 10.1 What Is Predicate Logic? Predicate logic extends propositional logic by introducing predicates and quantifiers to express more complex statements. A predicate is a function that returns true or false for given arguments. Example: P(x) = "x is even", Q(x,y) = "x > y" 10.2 Quantifiers Universal Quantifier (∀): "for all" - ∀x P(x) means P(x) is true for all x Existential Quantifier (∃): "there exists" - ∃x P(x) means P(x) is true for at least one x Example: (all natural numbers are ≥ 1)∀x ∈ N, x ≥ 1 Example: (there exists a real number whose square is 2)∃x ∈ R, x =2 2 10.3 Negation of Quantified Statements ¬(∀xP (x)) ≡ ∃x¬P (x) ¬(∃xP (x)) ≡ ∀x¬P (x) 10.4 Predicates with Multiple Variables P(x,y) = "x loves y" = "For every person x, there exists a person y that x loves"∀x∃yP (x, y) = "There exists a person x who loves everyone"∃x∀yP (x, y) 10.5 Scope of Quantifiers The scope of a quantifier is the part of the formula where the quantifier applies. Example: - quantifier applies to entire formula∀x(P (x) ∧ Q(x)) Example: - quantifier applies only to P(x)(∀xP (x)) ∧ Q(x) 10.6 Applications Database queries with conditions Mathematical proofs Formal specification of systems Artificial intelligence and knowledge representation 🚀 MCA Application: Predicate logic is used in database query languages and AI systems. 💻 Programming: Used in formal verification and constraint satisfaction problems. 10.7 Chapter Summary Key Concepts Predicates, universal and existential quantifiers Important Negation rules for quantifiers Memory Tip ∀ = "for all", ∃ = "there exists" Quick Revision Quantifiers and their scope Practice Questions MCQ: means: (a) P(x) is true for some x (b) P(x) is true for all x (c) P(x) is sometimes true (d) P(x) is never true1. ∀xP (x) MCQ: ? (a) (b) (c) (d)2. ¬(∀xP (x)) ≡ ∀x¬P (x) ∃x¬P (x) ∃xP (x) ¬∃xP (x) Short Answer: Write in predicate logic: "All students are intelligent"3. Short Answer: Write in predicate logic: "There exists a student who passed the exam"4. Application: How would you express a database query using predicate logic?5. Answer Key: 1-b, 2-b, 3- , 4- , 5-SELECT * FROM Students WHERE GPA > 3.5 can be expressed as∀x(Student(x) → Intelligent(x)) ∃x(Student(x) ∧ Passed(x)) ∃x(Student(x) ∧ GPA(x) > 3.5)
CHAPTER 11: Set Theory in Databases 11.1 Relational Database Model The relational model is based on set theory. A relation is a set of tuples (rows). Table = Relation, Row = Tuple, Column = Attribute Example: Students table = {(1, "Alice", "CS"), (2, "Bob", "IT"), ...} 11.2 Keys and Constraints Primary Key: Uniquely identifies each tuple Foreign Key: References primary key in another table Unique Constraint: Ensures uniqueness of values NOT NULL: Ensures value is not empty 11.3 Relational Algebra Operations Selection ( ): Filters rows based on conditionσ Projection ( ): Selects specific columnsπ Union ( ): Combines tuples from two relations∪ Intersection ( ): Common tuples from two relations∩ Difference ( ): Tuples in first relation but not second− Cartesian Product ( ): All combinations of tuples× Join ( ): Combines tuples from two relations based on condition⋈ 11.4 Set Operations in SQL UNION: Combines result sets INTERSECT: Common rows EXCEPT/MINUS: Rows in first but not second 11.5 Normalization Process of organizing data to minimize redundancy using set theory principles. 11.6 Examples Beginner: Simple SELECT queries Intermediate: Joins and set operations Practical: Complex database queries with multiple conditions MCA Application: Database design fundamentally relies on set theory. SQL Example: SELECT * FROM Students WHERE Department = 'CS' UNION SELECT * FROM Students WHERE GPA > 3.51 11.7 Chapter Summary Key Concepts Relations, keys, relational algebra Important Set operations in SQL Memory Tip Table = Relation, Row = Tuple Quick Revision Seven relational algebra operations Practice Questions MCQ: In relational model, a table is called: (a) Set (b) Relation (c) Tuple (d) Attribute1. MCQ: Which operation combines rows from two tables? (a) Selection (b) Projection (c) Union (d) Join2. Short Answer: Explain the difference between UNION and INTERSECT in SQL.3. Short Answer: What is a foreign key and why is it important?4. Application: Design a simple database schema for a college using set theory concepts.5. Answer Key: 1-b, 2-c (Union combines rows, Join combines based on condition), 3-UNION combines all rows, INTERSECT returns common rows, 4-Foreign key references primary key in another table to maintain referential integrity, 5-Students(StudentID, Name, DeptID), Departments(DeptID, DeptName), Courses(CourseID, CourseName, DeptID)
CHAPTER 12: Set Theory in SQL SQL provides three main set operations: UNION, INTERSECT, and EXCEPT (or MINUS in some databases). 12.2 UNION Combines result sets from two queries, removing duplicates. Syntax: SELECT ... FROM table1 UNION SELECT ... FROM table2 Example: SELECT Name FROM Students WHERE GPA > 3.5 UNION SELECT Name FROM Faculty WHERE Salary > 100000 12.3 UNION ALL Like UNION but includes duplicates. 12.4 INTERSECT Returns rows that appear in both result sets. Syntax: SELECT ... FROM table1 INTERSECT SELECT ... FROM table2 Example: SELECT StudentID FROM Enrolled WHERE CourseID = 'CS101' INTERSECT SELECT StudentID FROM Enrolled WHERE CourseID = 'CS102' 12.5 EXCEPT (MINUS) Returns rows from first query that don't appear in second query. Syntax: SELECT ... FROM table1 EXCEPT SELECT ... FROM table2 Example: SELECT StudentID FROM AllStudents EXCEPT SELECT StudentID FROM Graduated 12.6 Practical Examples Finding common students in two courses Finding students who took CS but not IT Combining results from multiple departments 💻 Programming: SQL set operations are essential for complex queries. 🗄 SQL Example: SELECT * FROM Students WHERE Department = 'CS' INTERSECT SELECT * FROM Students WHERE GPA > 3.5 12.7 Chapter Summary Key Operations UNION, INTERSECT, EXCEPT Important UNION removes duplicates, UNION ALL keeps them Memory Tip Think of SQL operations as set operations Quick Revision Three main set operations with examples Practice Questions MCQ: UNION removes: (a) Rows (b) Columns (c) Duplicates (d) NULL values1. MCQ: INTERSECT returns: (a) All rows (b) Common rows (c) Different rows (d) First table rows2. Short Answer: Write a query to find students in both CS and IT departments.3. Short Answer: Explain the difference between UNION and UNION ALL.4. Application: Write a query to find students who took CS101 but not CS102.5. Answer Key: 1-c, 2-b, 3-SELECT StudentID FROM Students WHERE Department = 'CS' INTERSECT SELECT StudentID FROM Students WHERE Department = 'IT', 4-UNION removes duplicates, UNION ALL keeps them, 5-SELECT StudentID FROM Enrolled WHERE CourseID = 'CS101' EXCEPT SELECT StudentID FROM Enrolled WHERE CourseID = 'CS102'
CHAPTER 13: Set Theory in Python Python provides a built-in set data type for working with sets. Syntax: s = {1, 2, 3} or s = set([1, 2, 3]) 13.2 Creating Sets Empty set: s = set() (not {}, which creates empty dict) From list: s = set([1, 2, 3]) Set literal: s = {1, 2, 3} Set comprehension: s = {x for x in range(10) if x % 2 == 0} 13.3 Set Operations in Python Union: A | B or A.union(B) Intersection: A & B or A.intersection(B) Difference: A - B or A.difference(B) Symmetric Difference: A ^ B or A.symmetric_difference(B) 13.4 Set Methods add(x): Add element remove(x): Remove element (raises error if not found) discard(x): Remove element (no error if not found) pop(): Remove and return arbitrary element clear(): Remove all elements copy(): Create shallow copy 13.5 Set Membership and Comparison x in s: Check membership s1 <= s2: Check if s1 is subset of s2 s1 < s2: Check if s1 is proper subset of s2 s1 == s2: Check equality s1.isdisjoint(s2): Check if no common elements 13.6 Practical Examples # Finding common elements students_cs = {'Alice', 'Bob', 'Carol'} students_it = {'Bob', 'David', 'Eve'} common = students_cs & students_it # {'Bob'} # Removing duplicates data = [1, 2, 2, 3, 3, 3] unique = set(data) # {1, 2, 3} # Finding unique elements list1 = [1, 2, 3, 4] list2 = [3, 4, 5, 6] unique_to_list1 = set(list1) - set(list2) # {1, 2} 💻 Programming: Sets are efficient for membership testing and removing duplicates. 13.7 Chapter Summary Key Concepts Set creation, operations, methods Important Sets are unordered and contain unique elements Memory Tip Use sets for fast membership testing Quick Revision Six main operations and common methods Practice Questions MCQ: How do you create an empty set in Python? (a) {} (b) set() (c) set([]) (d) Both b and c1. MCQ: What does A | B do? (a) Intersection (b) Union (c) Difference (d) Symmetric difference2. Short Answer: Write Python code to find common elements in two lists.3. Short Answer: Explain the difference between remove() and discard() methods.4. Application: Write a Python program to remove duplicates from a list using sets.5. Answer Key: 1-d, 2-b, 3-set(list1) & set(list2), 4-remove() raises error if element not found, discard() doesn't, 5-unique_list = list(set(original_list))
CHAPTER 14: Set Theory in Java Java provides Set interface and implementations like HashSet, TreeSet, and LinkedHashSet. 14.2 HashSet Unordered set with O(1) average time complexity for add, remove, and contains operations. Set<Integer> set = new HashSet<>(); set.add(1); set.add(2); set.add(3); 14.3 TreeSet Ordered set (sorted) with O(log n) time complexity. Set<Integer> set = new TreeSet<>(); set.add(3); set.add(1); set.add(2); // Automatically sorted: {1, 2, 3} 14.4 LinkedHashSet Maintains insertion order with O(1) average time complexity. 14.5 Set Operations in Java Union: addAll() Intersection: retainAll() Difference: removeAll() Set<Integer> A = new HashSet<>(Arrays.asList(1, 2, 3)); Set<Integer> B = new HashSet<>(Arrays.asList(2, 3, 4)); // Union Set<Integer> union = new HashSet<>(A); union.addAll(B); // {1, 2, 3, 4} // Intersection Set<Integer> intersection = new HashSet<>(A); intersection.retainAll(B); // {2, 3} // Difference Set<Integer> difference = new HashSet<>(A); difference.removeAll(B); // {1} 14.6 Set Methods add(E e): Add element remove(Object o): Remove element contains(Object o): Check membership size(): Get number of elements isEmpty(): Check if empty clear(): Remove all elements 14.7 Examples Beginner: Creating and populating sets Intermediate: Set operations Practical: Finding duplicates in arrays 💻 Programming: Java sets are essential for efficient data management. 14.8 Chapter Summary Key Concepts HashSet, TreeSet, LinkedHashSet Important Choose set type based on requirements Memory Tip HashSet for speed, TreeSet for order Quick Revision Three main implementations and operations Practice Questions MCQ: Which set maintains insertion order? (a) HashSet (b) TreeSet (c) LinkedHashSet (d) None1. MCQ: What is the time complexity of HashSet.contains()? (a) O(1) (b) O(n) (c) O(log n) (d) O(n²)2. Short Answer: Write Java code to find common elements in two sets.3. Short Answer: Explain the difference between HashSet and TreeSet.4. Application: Write a Java program to remove duplicates from an array using sets.5. Answer Key: 1-c, 2-a, 3-intersection.retainAll(otherSet), 4-HashSet is unordered O(1), TreeSet is sorted O(log n), 5-Set<Integer> unique = new HashSet<>(Arrays.asList(array))
CHAPTER 15: Graph Theory Basics 15.1 What Is a Graph? A graph G = (V, E) consists of a set of vertices (nodes) V and a set of edges E connecting pairs of vertices. Example: V = {A, B, C, D}, E = {(A,B), (B,C), (C,D), (A,D)} 15.2 Types of Graphs Undirected Graph: Edges have no direction Directed Graph (Digraph): Edges have direction Weighted Graph: Edges have weights/costs Unweighted Graph: All edges have equal weight 15.3 Graph Terminology Vertex (Node): A point in the graph Edge: Connection between two vertices Degree: Number of edges connected to a vertex Path: Sequence of vertices connected by edges Cycle: Path that starts and ends at same vertex Connected Graph: Path exists between any two vertices Disconnected Graph: Some vertices have no path between them 15.4 Graph Representations Adjacency Matrix: 2D array where A[i][j] = 1 if edge exists Adjacency List: List of neighbors for each vertex Edge List: List of all edges 15.5 Graph Traversal Depth-First Search (DFS): Explores as far as possible along each branch Breadth-First Search (BFS): Explores all neighbors before moving deeper 15.6 Applications Social networks (friends as vertices, friendships as edges) Transportation networks (cities as vertices, roads as edges) Computer networks (computers as vertices, connections as edges) Web pages (pages as vertices, links as edges) 🚀 MCA Application: Graphs are fundamental in computer science and AI. 💻 Programming: Graph algorithms are used in pathfinding, networking, and data analysis. 15.7 Chapter Summary Key Concepts Vertices, edges, types of graphs Important Graph representations and traversal methods Memory Tip G = (V, E) where V is vertices, E is edges Quick Revision Terminology and basic algorithms Practice Questions MCQ: A graph with directed edges is called: (a) Undirected (b) Directed (c) Weighted (d) Bipartite1. MCQ: The degree of a vertex is: (a) Number of edges (b) Number of vertices (c) Number of paths (d) Number of cycles2. Short Answer: Explain the difference between DFS and BFS.3. Short Answer: Draw an adjacency matrix for a graph with vertices {A, B, C} and edges {(A,B), (B,C)}.4. Application: How would you represent a social network as a graph?5. Answer Key: 1-b, 2-a, 3-DFS explores deeply, BFS explores breadth-first, 4-Matrix with 1s at (A,B), (B,A), (B,C), (C,B) for undirected, 5-Vertices = users, Edges = friendships
CHAPTER 16: Trees and Hierarchies 16.1 What Is a Tree? A tree is a connected acyclic graph. It's a special type of graph with no cycles. Properties: n vertices, n-1 edges, connected, acyclic 16.2 Tree Terminology Root: Top node (no parent) Parent: Node with children Child: Node with parent Leaf: Node with no children Height: Maximum distance from root to leaf Depth: Distance from root to node Subtree: Tree formed by node and its descendants 16.3 Types of Trees Binary Tree: Each node has at most 2 children Binary Search Tree (BST): Left child < parent < right child Balanced Tree: Heights of subtrees differ by at most 1 Complete Binary Tree: All levels filled except possibly last 16.4 Tree Traversal Trees can be traversed in various ways to visit each node. The most common methods include: 1 Inorder Traversal Left, Root, Right (for BST gives sorted order) 2 Preorder Traversal Root, Left, Right 3 Postorder Traversal Left, Right, Root 4 Level-order Traversal Level by level 16.5 Applications File systems (folders as nodes) Organization hierarchies (employees as nodes) Database indexes (B-trees) Expression parsing (syntax trees) Decision making (decision trees) 🚀 MCA Application: Trees are fundamental in data structures and algorithms. 💻 Programming: Trees are used in searching, sorting, and hierarchical data representation. 16.6 Chapter Summary Key Concepts Root, parent, child, leaf, height Important Binary trees and BSTs Memory Tip Tree = connected acyclic graph Quick Revision Types and traversal methods Practice Questions MCQ: A tree with n vertices has: (a) n edges (b) n-1 edges (c) n+1 edges (d) 2n edges1. MCQ: In a binary tree, each node has at most: (a) 1 child (b) 2 children (c) 3 children (d) n children2. Short Answer: Explain the difference between inorder and preorder traversal.3. Short Answer: What is the height of a tree with only root node?4. Application: How would you represent a company hierarchy as a tree?5. Answer Key: 1-b, 2-b, 3-Inorder: Left-Root-Right, Preorder: Root-Left-Right, 4-Height = 0, 5-Root = CEO, children = department heads, leaves = employees
CHAPTER 17: Combinatorics 17.1 What Is Combinatorics? Combinatorics is the study of counting, arranging, and selecting objects from sets. 17.2 Permutations Arrangement of objects where order matters. Formula: P(n,r) = n! / (n-r)! Example: Arranging 3 students from 5 = P(5,3) = 5!/(5-3)! = 60 17.3 Combinations Selection of objects where order doesn't matter. Formula: C(n,r) = n! / (r!(n-r)!) Example: Choosing 3 students from 5 = C(5,3) = 5!/(3!2!) = 10 17.4 Binomial Theorem (a + b)ⁿ = Σ C(n,k) aⁿ⁻ᵏ bᵏ 17.5 Pigeonhole Principle If n items are put into m containers with n > m, at least one container has more than one item. 17.6 Inclusion-Exclusion Principle |A ∪ B| = |A| + |B| - |A ∩ B| 17.7 Applications Probability calculations Password generation Lottery odds Database query optimization 💻 Programming: Combinatorics is used in algorithm analysis and optimization. 17.8 Chapter Summary Key Concepts Permutations, combinations, principles Important P(n,r) vs C(n,r) Memory Tip Permutation = order matters, Combination = order doesn't Quick Revision Formulas and applications Practice Questions MCQ: P(5,2) = ? (a) 10 (b) 20 (c) 25 (d) 1201. MCQ: C(5,2) = ? (a) 10 (b) 20 (c) 25 (d) 1202. Short Answer: Explain the difference between permutation and combination.3. Short Answer: Calculate the number of ways to arrange 4 books on a shelf.4. Application: How many 4-digit passwords can be created using digits 0-9?5. Answer Key: 1-b (5×4=20), 2-a (5!/(2!3!)=10), 3-Permutation: order matters, Combination: order doesn't, 4-P(4,4)=4!=24, 5-10⁴=10000
CHAPTER 18: Probability Theory 18.1 Basic Concepts Probability is the measure of likelihood of an event occurring. P (A) = Number of favorable outcomes/Total number of outcomes Range: 0 ≤ P (A) ≤ 1 18.2 Sample Space and Events Sample Space (S): Set of all possible outcomes Event (A): Subset of sample space Complement (A'): All outcomes not in A 18.3 Probability Rules Addition Rule: P (A ∪ B) = P (A) + P (B) − P (A ∩ B) Multiplication Rule: P (A ∩ B) = P (A) × P (B∣A) Complement Rule: P (A ) =′ 1 − P (A) 18.4 Conditional Probability P (A∣B) = P (A ∩ B)/P (B) Probability of A given B has occurred 18.5 Independent Events Events A and B are independent if P (A ∩ B) = P (A) × P (B) 18.6 Bayes' Theorem P (A∣B) = P (B∣A) × P (A)/P (B) 18.7 Applications Machine learning and AI Risk assessment Quality control Medical diagnosis Data analysis 🚀 MCA Application: Probability is fundamental in machine learning and data science. 18.8 Chapter Summary Key Concepts Sample space, events, probability rules Important Conditional probability and independence Memory Tip P(A) = favorable / total Quick Revision Rules and applications Practice Questions MCQ: If P(A) = 0.3, then P(A') = ? (a) 0.3 (b) 0.7 (c) 0 (d) 11. MCQ: For independent events, P(A ∩ B) = ? (a) P(A) + P(B) (b) P(A) × P(B) (c) P(A|B) (d) P(A) - P(B)2. Short Answer: Define conditional probability with an example.3. Short Answer: If P(A) = 0.4 and P(B) = 0.5, and A and B are independent, find P(A ∩ B).4. Application: How would you use probability in machine learning?5. Answer Key: 1-b, 2-b, 3-P(A|B) = probability of A given B occurred, e.g., P(rain|clouds), 4-P(A ∩ B) = 0.4 × 0.5 = 0.2, 5-Probability models predict likelihood of outcomes, used in classification and regression
CHAPTER 19: Set Theory in Machine Learning 19.1 Sets in Data Representation Machine learning uses sets to represent datasets, features, and classes. D = {(x , y ), (x , y ), ..., (x , y )}1 1 2 2 n n where xᵢ is input, yᵢ is output 19.2 Feature Sets Features represent attributes of dataF = {f , f , ..., f }1 2 m Example: For student data, F = {Age, GPA, Attendance, Test_Score} 19.3 Class Sets Classes represent output categoriesC = {c , c , ..., c }1 2 k Example: For classification, C = {Pass, Fail} or C = {Cat, Dog, Bird} 19.4 Training and Test Sets Training Set: Used to train the model Test Set: Used to evaluate the model Validation Set: Used to tune hyperparameters Training ∪ Test ∪ Validation = Dataset (disjoint sets) 19.5 Set Operations in ML Union Combining datasets Intersection Finding common samples Difference Finding unique samples Complement Finding samples not in a set 19.6 Dimensionality Reduction Selecting subset of features: F ⊂′ F 19.7 Applications Data preprocessing Feature selection Cross-validation Ensemble methods Clustering 🚀 MCA Application: Set theory is fundamental in machine learning algorithms. 💻 Programming: Used in data preparation and model evaluation. 19.8 Chapter Summary Key Concepts Datasets, features, classes, sets Important Training/test/validation sets Memory Tip Dataset = union of disjoint training, test, validation sets Quick Revision Set operations in ML context Practice Questions MCQ: Training and test sets should be: (a) Overlapping (b) Disjoint (c) Equal (d) Identical1. MCQ: Feature selection is: (a) F = F' (b) F' ⊂ F (c) F ⊂ F' (d) F ∩ F' = ∅2. Short Answer: Explain why training and test sets must be disjoint.3. Short Answer: If dataset has 1000 samples, how would you split into training (70%), validation (15%), test (15%)?4. Application: How would you use set operations to handle imbalanced datasets?5. Answer Key: 1-b, 2-b, 3-To avoid overfitting and ensure unbiased evaluation, 4-Training: 700, Validation: 150, Test: 150, 5-Use set operations to balance class distributions
CHAPTER 20: Advanced Topics and Applications 20.1 Fuzzy Sets Sets where membership is not binary (0 or 1) but a degree between 0 and 1. μ(x) ∈ [0, 1] Example: Temperature = {Cold, Warm, Hot} with fuzzy membership 20.2 Rough Sets Sets with uncertain or incomplete information. Used in data mining and knowledge discovery. 20.3 Multisets Sets where elements can appear multiple times. Example: {1, 1, 2, 2, 2, 3} is a multiset 20.4 Infinite Sets and Cardinality Comparing sizes of infinite sets using bijections. Aleph numbers ( , , ...) represent different infinities.ℵ0 ℵ1 20.5 Set Theory in Cryptography Key spaces as sets Permutations and combinations for encryption Hash functions mapping sets to sets 20.6 Set Theory in Artificial Intelligence Knowledge representation using sets Semantic networks Ontologies Description logics 20.7 Set Theory in Big Data Distributed sets across multiple nodes MapReduce operations on sets Set operations in Spark and Hadoop 20.8 Emerging Applications Blockchain and distributed systems Quantum computing Natural language processing Computer vision 🚀 MCA Application: Advanced set theory is crucial for cutting-edge technologies. 💻 Programming: Used in modern frameworks and libraries. 20.9 Chapter Summary Key Concepts Fuzzy sets, rough sets, multisets Important Applications in AI, cryptography, big data Memory Tip Set theory extends beyond classical mathematics Quick Revision Advanced topics and real-world applications Practice Questions MCQ: In fuzzy sets, membership value is: (a) 0 or 1 (b) Between 0 and 1 (c) Always 1 (d) Undefined1. MCQ: A multiset allows: (a) No duplicates (b) Duplicate elements (c) Only unique elements (d) Infinite elements2. Short Answer: Explain the difference between classical sets and fuzzy sets.3. Short Answer: How are sets used in cryptography?4. Application: Describe how set theory is applied in machine learning and AI.5. Answer Key: 1-b, 2-b, 3-Classical: membership is 0 or 1, Fuzzy: membership is degree between 0 and 1, 4-Key spaces, permutations for encryption, hash functions, 5-Knowledge representation, semantic networks, ontologies, classification
Detailed Solutions Step-by-step problem-solving SOLVED EXAMPLES Example 1: Set Operations Problem: If A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, and C = {5, 6, 7, 8, 9}, find: (a) A ∪ B (b) A ∩ B (c) A − B (d) (A ∪ B) ∩ C Solution: (a) A ∪ B = {1, 2, 3, 4, 5, 6, 7} (b) A ∩ B = {3, 4, 5} (c) A − B = {1, 2} (d) (A ∪ B) ∩ C = {1, 2, 3, 4, 5, 6, 7} ∩ {5, 6, 7, 8, 9} = {5, 6, 7} Example 2: De Morgan's Laws Problem: Verify De Morgan's Law: (A ∪ B)' = A' ∩ B' for A = {1, 2, 3}, B = {2, 3, 4}, U = {1, 2, 3, 4, 5} Solution: LHS: (A ∪ B)' = ({1, 2, 3} ∪ {2, 3, 4})' = {1, 2, 3, 4}' = {5} RHS: A' ∩ B' = {4, 5} ∩ {1, 5} = {5} LHS = RHS ✓ Example 3: Cardinality and Power Set Problem: If A = {a, b, c}, find |P(A)| and list all elements of P(A). Solution: 1 P(A) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} Example 4: Relations and Functions Problem: If A = {1, 2, 3} and B = {x, y}, find A × B and determine if R = {(1,x), (2,y), (3,x)} is a function. Solution: A × B = {(1,x), (1,y), (2,x), (2,y), (3,x), (3,y)} R is a function because each element of A maps to exactly one element of B. Example 5: Combinatorics Problem: In how many ways can 5 students be arranged in a line? How many ways can 3 students be selected from 5? Solution: Arrangements (Permutations): P(5,5) = 5! = 120 Selections (Combinations): C(5,3) = 5!/(3!2!) = 10 Example 6: Probability Problem: A die is rolled. Find P(even number) and P(number > 3). Solution: Sample space S = {1, 2, 3, 4, 5, 6} Even numbers = {2, 4, 6}, so P(even) = 3/6 = 1/2 Numbers > 3 = {4, 5, 6}, so P(>3) = 3/6 = 1/2 Example 7: SQL Set Operations Problem: Write SQL queries to find: (a) All students in CS or IT department (b) Students in both CS and IT (c) Students in CS but not IT Solution: (a) SELECT * FROM Students WHERE Department = 'CS' UNION SELECT * FROM Students WHERE Department = 'IT' (b) SELECT * FROM Students WHERE Department = 'CS' INTERSECT SELECT * FROM Students WHERE Department = 'IT' (c) SELECT * FROM Students WHERE Department = 'CS' EXCEPT SELECT * FROM Students WHERE Department = 'IT' Example 8: Python Set Operations Problem: Given sets A = {1, 2, 3, 4} and B = {3, 4, 5, 6}, find union, intersection, and difference. Solution: A = {1, 2, 3, 4} B = {3, 4, 5, 6} print(A | B) # {1, 2, 3, 4, 5, 6} print(A & B) # {3, 4} print(A - B) # {1, 2} print(A ^ B) # {1, 2, 5, 6}
QUICK REVISION & FORMULA SHEET FUNDAMENTAL DEFINITIONS Set: Well-defined collection of distinct objects Element: Object in a set, denoted a ∈ A Cardinality: Number of elements, |A| Empty Set: ∅ or {}, contains no elements Universal Set: U, contains all elements under consideration SET NOTATION Roster Form: A = {1, 2, 3} Set-Builder Form: A = {x | x is even, x < 10} Descriptive Form: "Set of even numbers less than 10" SET OPERATIONS Operation Symbol Definition Formula Union A ∪ B All elements in A or B {x | x ∈ A or x ∈ B} Intersection A ∩ B Common elements {x | x ∈ A and x ∈ B} Complement A' Elements not in A {x | x ∈ U, x ∉ A} Difference A − B In A but not B {x | x ∈ A, x ∉ B} Symmetric Diff A △ B In A or B but not both (A − B) ∪ (B − A) LAWS OF SET THEORY Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C) Distributive: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) De Morgan's: (A ∪ B)' = A' ∩ B', (A ∩ B)' = A' ∪ B' Identity: A ∪ ∅ = A, A ∩ U = A Complement: A ∪ A' = U, A ∩ A' = ∅ Idempotent: A ∪ A = A, A ∩ A = A RELATIONS & FUNCTIONS Cartesian Product: A × B = {(a,b) | a ∈ A, b ∈ B} Relation: R ⊆ A × B Function: f: A → B where each a ∈ A maps to exactly one b ∈ B Injective: Different inputs → different outputs Surjective: Every element in codomain is mapped Bijective: Both injective and surjective CARDINALITY |A| = number of elements in A |P(A)| = 2^|A| (power set cardinality) |A × B| = |A| × |B| Countably Infinite: Can be listed (ℕ, ℤ, ℚ) Uncountably Infinite: Cannot be listed (ℝ) COMBINATORICS Permutation: P(n,r) = n! / (n-r)! Combination: C(n,r) = n! / (r!(n-r)!) Factorial: n! = n × (n-1) × ... × 1 Binomial: (a+b)^n = Σ C(n,k) a^(n-k) b^k PROBABILITY P(A) = favorable outcomes / total outcomes P(A ∪ B) = P(A) + P(B) − P(A ∩ B) P(A ∩ B) = P(A) × P(B|A) P(A|B) = P(A ∩ B) / P(B) P(A') = 1 − P(A) BOOLEAN ALGEBRA AND (∧): 1 ∧ 1 = 1, else 0 OR (∨): 0 ∨ 0 = 0, else 1 NOT ('): 0' = 1, 1' = 0 De Morgan's: (a ∨ b)' = a' ∧ b' SQL SET OPERATIONS UNION: Combines rows, removes duplicates UNION ALL: Combines rows, keeps duplicates INTERSECT: Common rows EXCEPT/MINUS: Rows in first but not second PYTHON SET OPERATIONS Union: A | B or A.union(B) Intersection: A & B or A.intersection(B) Difference: A − B or A.difference(B) Symmetric Difference: A ^ B GRAPH THEORY Graph: G = (V, E) where V = vertices, E = edges Degree: Number of edges connected to vertex Path: Sequence of vertices connected by edges Cycle: Path starting and ending at same vertex Tree: Connected acyclic graph with n−1 edges KEY SYMBOLS Symbol Meaning ∈ Element of ∉ Not element of ⊆ Subset of ⊂ Proper subset of
KEY POINTS TO REMEMBER Foundation Concepts ✓ A set is a well-defined collection of distinct objects ✓ Elements are either in a set or not (no partial membership in classical sets) ✓ Order doesn't matter in sets: {1,2,3} = {3,2,1} ✓ Duplicates are not allowed: {1,1,2} = {1,2} ✓ The empty set ∅ is a subset of every set Set Operations ✓ Union (∪) combines all elements from both sets ✓ Intersection (∩) finds common elements ✓ Complement (') contains elements NOT in the set ✓ Difference (−) contains elements in first set but not second ✓ Symmetric difference (△) contains elements in either set but not both Critical Laws ✓ De Morgan's Laws are the most frequently tested ✓ 1 ✓ Distributive law: 2 ✓ Idempotent law: 3 ✓ Absorption law: 4 Relations and Functions ✓ A relation is any subset of Cartesian product A × B ✓ A function is a special relation where each input has exactly one output ✓ Injective (one-to-one): Different inputs → different outputs ✓ Surjective (onto): Every element in codomain is mapped ✓ Bijective: Both injective and surjective (has inverse) Cardinality ✓ (power set has 2^n elements)5 ✓ 6 ✓ Countably infinite sets: ℕ, ℤ, ℚ (can be listed) ✓ Uncountably infinite sets: ℝ (cannot be listed) ✓ Cantor's theorem: for any set A7 Combinatorics ✓ Permutation - ORDER MATTERS8 ✓ Combination - ORDER DOESN'T MATTER9 ✓ always10 ✓ (symmetry property)11 ✓ Binomial coefficient appears in expansion12 13 Probability ✓ for any event A14 ✓ 15 ✓ For independent events: 16 ✓ Conditional probability: 17 ✓ Bayes' Theorem: 18 Boolean Algebra ✓ 0 represents FALSE, 1 represents TRUE ✓ AND (∧) is true only when both are true ✓ OR (∨) is false only when both are false ✓ NOT (') inverts the value ✓ De Morgan's Laws apply to Boolean expressions too Database Applications ✓ UNION combines rows from two queries (removes duplicates) ✓ UNION ALL combines rows (keeps duplicates) ✓ INTERSECT returns common rows ✓ EXCEPT/MINUS returns rows in first but not second ✓ Foreign keys maintain referential integrity using set relationships Programming Applications ✓ Python sets are unordered and contain unique elements ✓ HashSet in Java: O(1) average, unordered ✓ TreeSet in Java: O(log n), sorted ✓ Set operations are efficient for membership testing ✓ Use sets to remove duplicates from lists Graph Theory ✓ Graph G = (V, E) where V = vertices, E = edges
REFERENCES Textbooks 1. 1 2. 2 3. 3 4. 4 Online Resources 1. 5 2. 6 3. 7 Database and SQL References 1. 8 2. 9 Programming References 1. 10 2. 11 Machine Learning References 1. 12 2. 13 Logic and Formal Methods 1. 14 2. 15 Graph Theory 1. 16 2. 17 Combinatorics 1. 18 2. 19 Probability and Statistics 1. 20 Recommended Study Order Start with Rosen's Discrete Mathematics for comprehensive foundation1. Use Lipschutz's Schaum's Outline for quick reference and practice2. Supplement with Khan Academy videos for visual learning3. Practice with Brilliant.org interactive problems4. Study database applications with Elmasri & Navathe5. Learn programming implementations with Goodrich et al.6. Explore advanced topics with specialized textbooks7. Online Platforms for Practice LeetCode: Coding problems involving set theory HackerRank: Discrete mathematics challenges CodeSignal: Algorithm and data structure problems Codeforces: Competitive programming with set theory Project Euler: Mathematical problem-solving Academic Journals Journal of Discrete Mathematics Discrete Applied Mathematics Combinatorica IEEE Transactions on Information Theory Conferences International Conference on Discrete Mathematics and Theoretical Computer Science ACM Symposium on Discrete Algorithms European Conference on Combinatorics, Graph Theory and Applications Acknowledgments This eBook synthesizes knowledge from the above sources and incorporates best practices in mathematical education. Special emphasis has been placed on practical applications relevant to MCA, BCA, and computer science students. About This eBook Target Audience: MCA, BCA, B.Tech (CSE/IT) students Difficulty Level: Beginner to Intermediate Prerequisites: Basic mathematics knowledge Estimated Study Time: 40-50 hours Last Updated: 2026 How to Use This eBook Read chapters sequentially for comprehensive understanding1. Work through solved examples for each concept2. Practice with end-of-chapter questions3. Use the formula sheet for quick reference4. Review key points before exams5. Refer to references for deeper study6. Apply concepts in programming and database projects7. Feedback and Suggestions For improvements, corrections, or suggestions, please refer to the official website or contact the educational institution providing this material. License This eBook is provided for educational purposes. Please respect intellectual property rights and cite appropriately when using content from this material.
Chapter 2: Set Operations CHAPTER 2 CORE OPERATIONS 2.1 Union of Sets The union of two sets A and B is the set of all elements that belong to A, or B, or both. It is denoted by A ∪ B. 📘 Formula — Union: A ∪ B = {x | x ∈ A or x ∈ B} Explanation of Symbols: A, B — any two sets ∪ — union operator (read: "cup" or "union") x — a generic element ∈ — "belongs to" or "is an element of" or — logical OR (inclusive) Intuition: Think of union as "combining everything from both sets, without repeating any element." In SQL, this corresponds to the UNION operator. Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A ∪ B = {1, 2, 3, 4, 5}. Note that 3 appears only once. 2.2 Intersection of Sets The intersection of two sets A and B is the set of all elements that belong to both A and B. It is denoted by A ∩ B. 📘 Formula — Intersection: A ∩ B = {x | x ∈ A and x ∈ B} Explanation of Symbols: ∩ — intersection operator (read: "cap" or "intersection") and — logical AND (both conditions must be true) Intuition: Intersection captures what the two sets have in common. In SQL, this corresponds to INTERSECT. Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A ∩ B = {3}. 2.3 Complement of a Set The complement of set A, denoted A' or Aᶜ or Ā, is the set of all elements in the universal set U that are not in A. 📘 Formula — Complement: A' = {x | x ∈ U and x ∉ A} Key Properties: A ∪ A' = U (everything is either in A or not in A) A ∩ A' = ∅ (nothing can be both in A and not in A) (A')' = A (double complement returns the original set) ∅' = U and U' = ∅ 2.4 Difference and Symmetric Difference Set Difference (A − B) Elements in A that are not in B. A − B = {x | x ∈ A and x ∉ B} Example: A = {1,2,3,4}, B = {3,4,5} → A − B = {1,2} ⚠ Note: A − B ≠ B − A (not commutative) Symmetric Difference (A ⊕ B) Elements in A or B, but not in both. A ⊕ B = (A − B) ∪ (B − A) Also: A ⊕ B = (A ∪ B) − (A ∩ B) Example: A = {1,2,3}, B = {3,4,5} → A ⊕ B = {1,2,4,5} 2.5 Solved Problems 🟢 Beginner: Union and Intersection Problem: Let A = {2, 4, 6, 8} and B = {4, 6, 9, 10}. Find A ∪ B and A ∩ B. Given: A = {2, 4, 6, 8}, B = {4, 6, 9, 10} Required: A ∪ B and A ∩ B Step 1 — Union: Combine all elements, remove duplicates. A ∪ B = {2, 4, 6, 8, 9, 10} Step 2 — Intersection: Find common elements. A ∩ B = {4, 6} Final Answer: A ∪ B = {2, 4, 6, 8, 9, 10}, A ∩ B = {4, 6} 🟡 Intermediate: Set Difference Problem: Let U = {1, 2, …, 10}, A = {2, 4, 6, 8, 10}, B = {1, 3, 5, 7, 9}. Find A − B, B − A, and A'. Given: U = {1..10}, A = evens, B = odds Step 1 — A − B: Elements in A not in B = {2, 4, 6, 8, 10} (no overlap) Step 2 — B − A: Elements in B not in A = {1, 3, 5, 7, 9} Step 3 — A': Elements in U not in A = {1, 3, 5, 7, 9} = B Final Answer: A − B = A, B − A = B, A' = B 🔴 Advanced: Symmetric Difference with Three Sets Problem: Let A = {1,2,3,4}, B = {3,4,5,6}, C = {5,6,7,8}. Find (A ⊕ B) ⊕ C. Step 1 — A ⊕ B: (A−B) ∪ (B−A) = {1,2} ∪ {5,6} = {1,2,5,6} Step 2 — (A ⊕ B) ⊕ C: {1,2,5,6} ⊕ {5,6,7,8} = {1,2,7,8} Final Answer: (A ⊕ B) ⊕ C = {1, 2, 7, 8} Verification: Elements appearing in an odd number of sets: 1(A), 2(A), 7(C), 8(C) ✓ 2.6 Quick Revision — Chapter 2 Operation Symbol Formula SQL Equivalent Union ∪ {x | x∈A or x∈B} UNION Intersection ∩ {x | x∈A and x∈B} INTERSECT Complement A' {x | x∈U and x∉A} EXCEPT Difference − {x | x∈A and x∉B} EXCEPT Symmetric Diff. ⊕ (A−B)∪(B−A) (A UNION B) EXCEPT (A INTERSECT B)
Chapter 3: Venn Diagrams and Set Laws CHAPTER 3 VISUAL REPRESENTATION 3.1 What Are Venn Diagrams? A Venn diagram is a graphical representation of sets using closed curves (usually circles) inside a rectangle that represents the universal set U. Each circle represents a set, and the overlapping regions represent intersections. Only A A − B (elements only in A) Intersection A ∩ B (elements in both) Only B B − A (elements only in B) Outside Both U 6 (elements in neither) The diagram above shows the four fundamental regions of a two-set Venn diagram: elements only in A, only in B, in both A and B (intersection), and in neither (complement of A ∪ B). 3.2 Venn Diagrams for Three Sets For three sets A, B, and C, the Venn diagram has 8 distinct regions (2³ = 8), representing all possible combinations of membership. 3.3 Laws of Set Algebra Set algebra follows laws analogous to arithmetic. These laws are essential for simplifying set expressions and are frequently tested in university examinations. Law Union Form Intersection Form Identity A ∪ ∅ = A A ∩ U = A Domination A ∪ U = U A ∩ ∅ = ∅ Idempotent A ∪ A = A A ∩ A = A Complement A ∪ A' = U A ∩ A' = ∅ Commutative A ∪ B = B ∪ A A ∩ B = B ∩ A Associative A ∪ (B ∪ C) = (A ∪ B) ∪ C A ∩ (B ∩ C) = (A ∩ B) ∩ C Distributive A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) De Morgan's I (A ∪ B)' = A' ∩ B' — De Morgan's II — (A ∩ B)' = A' ∪ B' Absorption A ∪ (A ∩ B) = A A ∩ (A ∪ B) = A 🎯 Exam Point: De Morgan's Laws are among the most frequently asked in university exams. Remember: "The complement of a union is the intersection of complements" and vice versa. The operator flips and each set is complemented. 3.4 De Morgan's Laws — Detailed Explanation De Morgan's First Law De Morgan's Second Law