UNIT – II Mathematical Foundations
UNIT – II
Mathematical
Foundations of Computer Science
Syllabus:
Set Identities · Set Operations · Cartesian Products · Relational
Matrices · Equivalence Relations · Partial Ordering · Lattices · Functions ·
Types of Functions · Recurrence Relations · Combinatorics
Set Theory Basics
A set is a well-defined collection of distinct objects,
called the elements or members of the set.
●
Capital letters A, B, C, … denote sets.
●
Lower-case letters a, b, c, … denote elements.
●
Braces { } enclose the elements of a set.
●
x ∈ S means x
is a member of set S; x ∉ S means x
is not a member of S.
Special Sets and Notation
|
Symbol |
Meaning |
|
∅ |
Empty set — the set with no elements |
|
U |
Universal set — the set of all elements under discussion |
|
N = { 1, 2, 3, …} |
Set of natural numbers |
|
Z = {…, −2, −1, 0, 1, 2, …} |
Set of integers |
|
Z⁺ = {1, 2, 3, …} |
Set of positive integers |
|
Q = {p/q | p ∈ Z, q ∈ Z, q ≠ 0} |
Set of rational numbers |
|
R |
Set of real numbers |
|
P(A) |
Power set of A — the set of all subsets of A |
Representation of a Set
A set can be represented in two ways:
1. Roster
(Tabular) Form
The elements are listed and enclosed in braces, separated by
commas.
Example:
Vowels: V = {a, e, i, o, u}
Odd numbers less than 10: A = {1, 3, 5, 7, 9}
2.
Set-Builder Notation
The set is described by a property common to its elements: A
= {x | p(x)}.
Example:
V = {x | x is a vowel in the English alphabet} A = {x | 1 ≤ x < 10 and x is odd}
TOPIC 1. Set Identities (Laws of Set Algebra)
Set identities are algebraic laws that hold for all sets,
regardless of what their elements are. They are used to simplify or prove set
expressions — very similar to algebraic identities in ordinary algebra.
The Laws of Set Algebra
|
Identity |
Primal Form |
Dual Form |
|
Idempotent laws |
A ∪ A = A |
A ∩ A = A |
|
Identity laws |
A ∪∅= A |
A ∩ U = A |
|
Dominance laws |
A ∪ U = U |
A ∩ ∅ = ∅ |
|
Complement laws |
A ∪ Aᶜ = U |
A ∩ Aᶜ = ∅ |
|
Commutative laws |
A ∪ B = B ∪ A |
A ∩ B = B ∩ A |
|
Associative laws |
A ∪ (B∪C) = (A∪B) ∪ C |
A ∩ (B∩C) = (A∩B) ∩ C |
|
Distributive laws |
A ∪ (B∩C) = (A∪B) ∩ (A∪C) |
A ∩ (B∪C) = (A∩B) ∪ (A∩C) |
|
Absorption laws |
A ∪ (A∩B) = A |
A ∩ (A∪B) = A |
|
Involution law |
(Aᶜ)ᶜ = A |
— |
|
De Morgan's laws |
(A∪B)ᶜ = Aᶜ ∩ Bᶜ |
(A∩B)ᶜ = Aᶜ ∪ Bᶜ |
Duality Principle
The Principle of Duality states that the dual of any true
set identity is also true. To form the dual of a statement, swap the following
pairs throughout:
|
Swap |
With |
|
∪ |
∩ |
|
∩ |
∪ |
|
∅ |
U |
|
U |
∅ |
Worked Example — Simplify Using Laws
Question:
Simplify: (A ∩ B) ∪ (A ∩ Bᶜ)
(A ∩ B) ∪ (A ∩ Bᶜ) = A ∩ (B ∪ Bᶜ) [Distributive law]
= A ∩ U [Complement
law]
(A ∩ B) ∪ (A ∩ Bᶜ) = A [Identity law]
TOPIC 2. Set Operations (Set Algebra)
1. Union
The union of sets A and B is the set of all elements that
are in A, in B, or in both. Denoted A ∪ B.
A ∪ B = {
x | x ∈ A or x ∈ B }
2. Intersection
The intersection of sets A and B is the set of all elements
common to both A and B. Denoted A ∩ B.
A ∩ B = {
x | x ∈ A and x ∈ B }
Example:
A = {a, e, i, o, u}, B = {a,
b, c, d, e} ⇒ A ∩ B = {a, e}
3. Disjoint Sets
Two sets are disjoint if their intersection is the empty set
— i.e., they share no elements.
A ∩ B = ∅
Example:
A = {a, e, i, o, u}, B = {1,
2, 3, 4, 5} ⇒ A ∩ B = ∅
4. Set Difference
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 = {a, e, i, o, u}, B = {a,
b, c, d, e} ⇒ A − B = {i, o, u}
A − B ≠ B − A
(set difference is NOT commutative)
A ∩ Bᶜ = A − B
5. Set Complement
Let U be the universal set. The complement of A, written Aᶜ,
is everything in U that is not in A.
Aᶜ = { x | x ∈
U and
x ∉ A } = U – A
Example: U = {a, b, …, z}, V = {a, e, i, o, u} ⇒ Vᶜ = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}
A ∩ Aᶜ = ∅ A ∪ Aᶜ
= U
Venn Diagrams
A Venn diagram is a pictorial way to show relationships between
sets: the rectangle represents the universal set U, and circles inside it
represent individual sets.
|
Operation |
Shaded Region in the Venn
Diagram |
|
Union A ∪ B |
Everything inside circle A, circle B, or both |
|
Intersection A ∩ B |
Only the overlapping region common to A and B |
|
Disjoint A, B |
Two circles with no overlapping region at all |
|
Difference A − B |
Part of circle A that does NOT overlap with B |
|
Complement Aᶜ |
Everything inside the rectangle U, outside circle A |
TOPIC 3. Cartesian Products
The Cartesian product of two sets A and B, denoted A × B, is
the set of all ordered pairs (x, y) where the first element comes from A and
the second from B.
A × B = {
(x, y) | x ∈ A
and y ∈ B }
Worked Example
Given:
A = {a, e, i, o, u}, B = {1,
2, 3}
A × B =
{(a,1),(e,1),(i,1),(o,1),(u,1), (a,2),(e,2),(i,2),(o,2),(u,2),
(a,3),(e,3),(i,3),(o,3),(u,3)}
Important Properties
●
If |A| = m and |B| = n, then |A × B| = m × n.
●
A × B ≠ B × A in general — the Cartesian product is NOT
commutative (order of the pair matters).
●
The Cartesian product A × B is the foundation for
defining a relation: any subset of A × B is called a binary relation from A to
B.
TOPIC 4 Relational Matrices
Relations
A relation represents how elements of one set are connected
to elements of another set (e.g., employees and their salaries, students and
their roll numbers).
Definition:
When A and B are sets, any subset R of the Cartesian product A × B
is called a binary relation from A to B. If (a,b) ∈ R, we write a R b, read as
"a is related to b by R."
Domain
and Range of a Relation
|
Term |
Definition |
|
Domain, Dom(R) |
{ a ∈ A | (a,b)
∈ R for
some b ∈ B } |
|
Range, Ran(R) |
{ b ∈ B | (a,b)
∈ R for
some a ∈ A } |
Relation
on a Set
If R ∈ A × A
(i.e., from A back to itself), R is called a relation on the set A.
Example:
R on A = {1,2,3,4}, defined by (a,b) ∈ R if a ≤ b, gives R =
{(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}. Here Dom(R) =
Ran(R) = A.
Comments
Post a Comment