Discrete Structure · Unit 3
Set Theory and Relations
Exam-focused notes for Set Theory and Relations (Discrete Structure, BIT152): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Set representation and operations
- Bit strings for set operations
- Power set
- Cartesian product
- Venn diagrams
- Relations and their representations
- Relation matrices
- Directed graphs for relations
- Equivalence relations
- Partial ordering
Set representation and operations
How do you represent set? Explain. [5]
A set is a well-defined collection of distinct objects called elements or members. Sets can be represented in several standard ways. --- All elements of the set are listed explicitly, separated by commas and enclosed in curly braces { }. Example: - Set of v...
Full solved answer →Venn diagrams
Explain how set operations can be represented using venn diagram with example.Convert the following sentences using quantifier: a.) Not all good peoples are heroes. b.) Every peoples in our country are loyal. c.) Some people hate good people.[10]
--- A Venn Diagram is a pictorial/graphical representation of sets and their relationships within a universal set U. Sets are represented as circles inside a rectangle (universal set). --- Definition: The union of sets A and B contains all elements that bel...
Full solved answer →Relation matrices
How can you represent relations using matrices? Explain with suitable example. [5]
A relation R from set A to set B can be represented using a zero-one matrix (also called a Boolean matrix or relation matrix), denoted MR. --- Let: - Set A = {a₁, a₂, ..., aₘ} with m elements (rows) - Set B = {b₁, b₂, ..., bₙ} with n elements (columns) The ...
Full solved answer →How can you represent relations using matrices? Suppose that $A = {1, 2, 3}$ and $B = {1, 2}$. Let $R$ be the relation from $A$ to $B$ containing $(a, b)$ if $a \in A$, $b \in B$, and $a > b$. What matrix representing $R$ if $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, and $b_1 = 1$ and $b_2 = 2$? [5]
A relation $R$ from a set $A$ (with $m$ elements) to a set $B$ (with $n$ elements) can be represented by an $m \times n$ zero-one (Boolean) matrix $MR = [m{ij}]$, where: $$m{ij} = \begin{cases} 1 & \text{if } (ai, bj) \in R \\ 0 & \text{if } (ai, bj) \notin...
Full solved answer →Power set
Define power set. What is the power set of the set A= {1,2, 3, 4}? [5]
- Set $A = \{1, 2, 3, 4\}$ - Number of elements: $n = 4$ --- The power set of a set $A$ is the set of all subsets of $A$, including the empty set $\emptyset$ and the set $A$ itself. It is denoted by $P(A)$ or $2^A$. Key property: If $A = n$, then the power ...
Full solved answer →Equivalence relations
Define equivalence relation with an example. [5]
A relation R on a set A is called an equivalence relation if and only if it satisfies the following three properties: For every element $a \in A$, we have $(a, a) \in R$. $$\forall a \in A, \; aRa$$ For all $a, b \in A$, if $(a, b) \in R$ then $(b, a) \in R...
Full solved answer →Define equivalence relation. How do you represent relation? [5]
A relation R on a set A is called an equivalence relation if it satisfies the following three properties simultaneously: For every element $a \in A$: $$a \mathrel{R} a$$ Every element is related to itself. For all $a, b \in A$: $$a \mathrel{R} b \implies b ...
Full solved answer →Cartesian product
Define cartesian product. Find A3 for the set A = (a, b, c). [5]
- Set $A = \{a, b, c\}$, so $A = 3$ - Required: definition of Cartesian product, and $A^3$ --- The Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of all ordered pairs $(a, b)$ such that $a \in A$ and $b \in B$: $$A \times B = \{...
Full solved answer →Bit strings for set operations
Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Use bit strings to find the union and intersection of the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9}. [5]
- Universal set: $U = \{1,2,3,4,5,6,7,8,9,10\}$ (length 10) - Set A: $\{1,2,3,4,5\}$ - Set B: $\{1,3,5,7,9\}$ Bit string convention: position $i$ = 1 if element $i \in$ set, else 0. Positions ordered $1 \to 10$. Positions: $\;1\;2\;3\;4\;5\;6\;7\;8\;9\;10$ ...
Full solved answer →Directed graphs for relations
How can we represent a relation using directed graph? Draw a directed graph of the relation R = {(1, 1), (1, 3), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (4, 1)} on the set {1, 2, 3, 4}. [5]
A relation R on a set A can be represented as a directed graph (digraph) where: - Each element of the set A is represented as a node (vertex) - For every ordered pair (a, b) ∈ R, we draw a directed edge (arrow) from node a to node b - If (a, a) ∈ R (i.e., a...
Full solved answer →Make Unit 3 stick
Practice BIT152 with flashcards & quizzes