Discrete StructureUnit 312 min read

Set Theory & Fuzzy Sets: Definitions, Operations, and Applications

Unit 3 of Discrete Structure covers fundamental concepts of set theory (operations, relations, power sets) and fuzzy sets (membership functions, operations, and real-world applications), with emphasis on problem-solving techniques and proofs.

Padhai · Based on the official syllabus and past papers
Updated 25 Sept 2026

TAKEAWAYS:

Understand set operations (union, intersection, complement, Cartesian product) and their Venn diagram representations for visualizing relationships.
Master subset, power set, and universal set definitions, including proper subsets and cardinality calculations.
Learn fuzzy set theory (Lozzi’s membership functions, operations like union/intersection with min/max, and complement rules).
Apply set theory to solve real-world problems (e.g., database queries, network routing, and algorithm correctness).
Recognize equivalence relations and partitions derived from sets, crucial for graph theory and number theory.
Prepare for exam questions on proofs, recursive definitions, and problem-solving using set theory concepts.

1. Introduction to Set Theory

1.1 Basic Definitions

A set is a well-defined collection of distinct objects, called elements or members.

Notation: $A = {a, b, c}$ or $x \in A$ (read as "x belongs to A").
Empty set: $\emptyset$ or ${}$ (contains no elements).
Singleton set: ${a}$ (contains one element).
Finite vs. Infinite Sets:
- Finite: $A = {1, 2, 3}$ (countable elements).
- Infinite: $N = {1, 2, 3, \dots}$ (uncountable elements).

1.2 Subsets and Power Sets

Subset ( $\subseteq$ ): Every element of $A$ is in $B$ .
- $A \subseteq B$ if $\forall x (x \in A ⟹ x \in B)$ .
- Proper subset ( $\subset$ ): $A \subset B$ if $A \subseteq B$ but $A \neq = B$ .
Power Set ( $P (A)$ ): The set of all subsets of $A$ .
- If $∣ A ∣ = n$ , then $∣ P (A) ∣ = 2^{n}$ .
- Example:
  - $A = {1, 2}$
  - $P (A) = {\emptyset, {1}, {2}, {1, 2}}$ .

1.3 Universal Set and Complement

Universal Set ( $U$ ): Contains all elements under consideration.
Complement ( $A^{c}$ or $U ∖ A$ ): Elements in $U$ but not in $A$ .
- $A^{c} = {x \in U ∣ x \in / A}$ .

2. Set Operations

2.1 Union ( $A \cup B$ )

Combines all elements from $A$ and $B$ .
$A \cup B = {x ∣ x \in A or x \in B}$ .
Example:
- $A = {1, 2}$ , $B = {2, 3}$
- $A \cup B = {1, 2, 3}$ .

2.2 Intersection ( $A \cap B$ )

Contains only elements common to both $A$ and $B$ .
$A \cap B = {x ∣ x \in A and x \in B}$ .
Example:
- $A = {1, 2}$ , $B = {2, 3}$
- $A \cap B = {2}$ .

2.3 Difference ( $A ∖ B$ )

Elements in $A$ but not in $B$ .
$A ∖ B = {x ∣ x \in A and x \in / B}$ .
Example:
- $A = {1, 2}$ , $B = {2, 3}$
- $A ∖ B = {1}$ .

2.4 Symmetric Difference ( $A Δ B$ )

Elements in either $A$ or $B$ but not in both.
$A Δ B = (A ∖ B) \cup (B ∖ A)$ .
Example:
- $A = {1, 2}$ , $B = {2, 3}$
- $A Δ B = {1, 3}$ .

2.5 Cartesian Product ( $A \times B$ )

Ordered pairs where the first element is from $A$ and the second from $B$ .
$A \times B = {(a, b) ∣ a \in A and b \in B}$ .
Example:
- $A = {1, 2}$ , $B = {x, y}$
- $A \times B = {(1, x), (1, y), (2, x), (2, y)}$ .

3. Venn Diagrams and Set Identities

3.1 Venn Diagram Representation

Venn diagrams visually represent set operations:

       __________
      /           \
     /             \
____/               \____
|       A           |
|       \           /
|        \         /
|________ \_______/
      \     /
       \   /
        \ /
         B

Union ( $A \cup B$ ): Entire area covered by both circles.
Intersection ( $A \cap B$ ): Overlapping area.
Complement ( $A^{c}$ ): Area outside circle $A$ .

3.2 Important Set Identities

Identity	Description
$A \cup A = A$	Idempotent law
$A \cap A = A$	Idempotent law
$A \cup \emptyset = A$	Identity law
$A \cap U = A$	Identity law
$A \cup A^{c} = U$	Complement law
$A \cap A^{c} = \emptyset$	Complement law
$(A \cup B)^{c} = A^{c} \cap B^{c}$	De Morgan’s law
$(A \cap B)^{c} = A^{c} \cup B^{c}$	De Morgan’s law
$A ∖ B = A \cap B^{c}$	Difference as intersection with complement

4. Applications of Set Theory

4.1 Database Queries

SQL WHERE clauses use set operations:
```
SELECT * FROM Students WHERE age > 20 AND grade = 'A';
```
- This retrieves students in $age > 20 \cap grade =^{'} A^{'}$ .

4.2 Network Routing

Subnet masking uses set operations to determine IP addresses in a subnet.

4.3 Algorithm Correctness

Recursive algorithms (e.g., factorial) rely on set theory for termination proofs.
- Example: Prove $n!$ is correct for all $n \geq 0$ using mathematical induction.

5. Fuzzy Set Theory

5.1 Introduction to Fuzzy Sets

Crisp Sets: Elements are either fully in ( $μ (x) = 1$ ) or fully out ( $μ (x) = 0$ ).
Fuzzy Sets: Elements have degrees of membership ( $0 \leq μ (x) \leq 1$ ).
- Defined by a membership function $μ_{A} : U \to [0, 1]$ .

5.2 Membership Function

Example: Let $U = {1, 2, 3, 4, 5}$ and define a fuzzy set $A = "small numbers"$ .
- $μ_{A} (1) = 1.0$ , $μ_{A} (2) = 0.8$ , $μ_{A} (3) = 0.4$ , $μ_{A} (4) = 0.1$ , $μ_{A} (5) = 0.0$ .
- Represented as $A = {(1, 1.0), (2, 0.8), (3, 0.4), (4, 0.1), (5, 0.0)}$ .

5.3 Fuzzy Set Operations

Operation	Definition	Example
Union ( $A \cup B$ )	$μ_{A \cup B} (x) = max (μ_{A} (x), μ_{B} (x))$	$μ_{A \cup B} (2) = max (0.8, 0.5) = 0.8$
Intersection ( $A \cap B$ )	$μ_{A \cap B} (x) = min (μ_{A} (x), μ_{B} (x))$	$μ_{A \cap B} (2) = min (0.8, 0.5) = 0.5$
Complement ( $A^{c}$ )	$μ_{A^{c}} (x) = 1 - μ_{A} (x)$	$μ_{A^{c}} (2) = 1 - 0.8 = 0.2$

5.4 Applications of Fuzzy Sets

Medical Diagnosis: "High fever" can be a fuzzy set with degrees of membership.
Control Systems: Fuzzy logic in washing machines (e.g., "dirty" vs. "clean").
Decision Making: Ranking candidates based on fuzzy criteria (e.g., "qualified").

6. Problem-Solving with Set Theory

6.1 Example 1: Computer Representation of Sets

Question: Given $U = {1, 2, \dots, 10}$ , represent the set of numbers multiple of 3 not exceeding 6. Solution:

Multiples of 3 in $U$ : ${3, 6, 9}$ .
Numbers not exceeding 6: ${3, 6}$ .
Computer representation (using bitmask for $U$ ):
- $U$ has 10 elements → 10-bit string.
- ${3, 6}$ corresponds to bits at positions 3 and 6 (1-based index):
```
0100100000 (binary) = 136 (decimal)
```
- Answer: The set is represented as 136 in binary.

6.2 Example 2: Proving Correctness of Recursive Algorithms

Question: Prove the correctness of the recursive factorial function using induction. Solution:

Base Case ( $n = 0$ ):
- $0! = 1$ (by definition).
- Recursive call: $fact (0) = 1$ . ✔️

Inductive Step:

Assume $fact (k) = k!$ holds for some $k \geq 0$ .

Show

fact (k + 1) = (k + 1)!

fact(k+1) = (k+1) * fact(k) [by definition]
          = (k+1) * k! [by inductive hypothesis]
          = (k+1)! ✔️

Conclusion: By induction, $fact (n) = n!$ for all $n \geq 0$ .

6.3 Example 3: Symmetric Closure

Question: Find the symmetric closure of $R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 1), (3, 2)}$ on $A = {1, 2, 3}$ . Solution:

Symmetric closure adds the reverse of every pair in $R$ .
Original $R$ has $(1, 2)$ but not $(2, 1)$ . Add $(2, 1)$ .
Similarly, add $(1, 3)$ (since $(3, 1)$ exists).
Final symmetric closure: $R_{sym} = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2)}$ .

7. Common Mistakes and Clarifications

Confusing $\subseteq$ and $\subset$ :
- $A \subseteq B$ allows $A = B$ .
- $A \subset B$ requires $A \neq = B$ .
Fuzzy Set Operations:
- Union uses max, not OR.
- Intersection uses min, not AND.
Cartesian Product Order:
- $A \times B \neq = B \times A$ unless $A = B$ .
Empty Set in Operations:
- $A \cup \emptyset = A$ .
- $A \cap \emptyset = \emptyset$ .

8. Exam Tips

8.1 What to Expect in Exams

Short Questions (2-5 marks):
- Define subset, power set, fuzzy set, symmetric closure.
- Draw Venn diagrams for given operations.
- Compute Cartesian products or set differences.
Long Questions (10-15 marks):
- Prove a recursive algorithm using induction (e.g., factorial, Fibonacci).
- Find closures (reflexive, symmetric, transitive).
- Solve real-world problems (e.g., database queries, network routing).
- Compare crisp vs. fuzzy sets with examples.
Problem-Solving (15-20 marks):
- Set theory in combinatorics (e.g., counting subsets).
- Fuzzy set applications (e.g., membership functions in decision-making).

8.2 Key Formulas to Remember

Concept	Formula
Power set cardinality	$∣ P (A) ∣ = 2^{∣ A ∣}$
Union cardinality	$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣$
Fuzzy union	$μ_{A \cup B} (x) = max (μ_{A} (x), μ_{B} (x))$
Fuzzy intersection	$μ_{A \cap B} (x) = min (μ_{A} (x), μ_{B} (x))$
Fuzzy complement	$μ_{A^{c}} (x) = 1 - μ_{A} (x)$

8.3 Common Exam Pitfalls

Forgetting to include all elements in union/intersection.
Misapplying De Morgan’s laws (e.g., confusing $\cup$ and $\cap$ ).
Incorrectly computing symmetric/transitive closures.
Not verifying base cases in induction proofs.
Assuming fuzzy sets are binary (remember $0 \leq μ (x) \leq 1$ ).

8.4 Recommended Practice

Solve past exam questions (focus on proofs, closures, and fuzzy operations).
Draw Venn diagrams for all operations to visualize relationships.
Practice recursive proofs (factorial, Fibonacci, sum of first $n$ integers).
Apply set theory to real-world scenarios (e.g., database queries, network routing).
Memorize key identities (De Morgan’s, distributive laws).

9. Summary Table: Crisp vs. Fuzzy Sets

Feature	Crisp Set	Fuzzy Set
Membership	Binary ( $0$ or $1$ )	Continuous ( $[0, 1]$ )
Union	$A \cup B = {x ∣ x \in A or x \in B}$	$μ_{A \cup B} (x) = max (μ_{A} (x), μ_{B} (x))$
Intersection	$A \cap B = {x ∣ x \in A and x \in B}$	$μ_{A \cap B} (x) = min (μ_{A} (x), μ_{B} (x))$
Complement	$A^{c} = {x ∣ x \in / A}$	$μ_{A^{c}} (x) = 1 - μ_{A} (x)$
Example Application	Database records (yes/no)	Medical diagnosis (degree of fever)
Advantage	Simple, exact	Handles uncertainty, real-world ambiguity

10. Final Notes

Set theory is foundational for computer science (databases, algorithms, logic).
Fuzzy sets extend classical sets to model uncertainty, widely used in AI and control systems.
Always verify your answers with examples (e.g., small finite sets).
For exams, prioritize proofs, definitions, and problem-solving over rote memorization.

End of Notes

Based on the TU BSc CSIT syllabus for Discrete Structure (CSC165), unit 3.

Discussion

Loading…