Synetic College Logo
Unit 1 of 4 · M.Sc IT Sem 3

Unit 1: Sets, relations, rings and Boolean algebra

Discrete Structures & Optimization notes · PTU syllabus (PGCA1917)

5 min read13 topics10 exam questions
On this page
  1. Unit summary
  2. Combination of sets
  3. Laws of set algebra
  4. Ordered pairs and proofs of set identities
  5. Relations
  6. Equivalence relations and partitions
  7. Partial order relations
  8. Hashing functions
  9. Rings and subrings
  10. Ring morphisms, ideals and quotient rings
  11. Integral domains, Euclidean domains and fields
  12. Boolean algebra
  13. Applications: logic implications and gates
  14. Karnaugh maps
  15. Key terms
  16. Quick revision
  17. Important questions

Unit summary

Discrete mathematics is the mathematics of computing. This unit covers combinations of sets, ordered pairs and proofs of set identities, relations, hashing functions, equivalence and partial order relations, rings, subrings, morphisms, ideals and quotient rings, Euclidean and integral domains and fields, and Boolean algebra with its applications to logic, gates and Karnaugh maps.

After this unit you can

  • Prove set identities and work with ordered pairs and relations
  • Identify equivalence and partial order relations and hashing functions
  • Define rings, subrings, ideals, integral domains and fields
  • Apply Boolean algebra to logic gates and Karnaugh maps

PTU syllabus topics

  • Combination of sets
  • ordered pairs
  • proofs of set identities
  • relations
  • hashing functions
  • equivalence and partial order relations
  • rings
  • subrings
  • morphisms
  • ideals and quotient rings
  • Euclidean domains
  • integral domains and fields
  • Boolean algebra and its applications (logic implications, logic gates, Karnaugh maps)
ComparisonProperties of relations
Definition
Example on integers

Reflexive

a R a for every a

Equals, ≤

Symmetric

a R b means b R a

Equals, 'is a sibling of'

Antisymmetric

a R b and b R a means a = b

≤

Transitive

a R b and b R c means a R c

<, ≤, equals

1

Topic 1

Combination of sets

Key termsSet operations at a glance
Union A ∪ B
Elements in A or B or both
Intersection A ∩ B
Elements common to A and B
Difference A − B
Elements in A but not in B
Symmetric difference A Δ B
Elements in exactly one of A and B: (A − B) ∪ (B − A)
Complement A'
Elements of U not in A: U − A

Take U = {1, 2, 3, 4, 5, 6, 7, 8}, A = {1, 2, 3, 4} and B = {3, 4, 5, 6}.

OperationResult
A ∪ B{1, 2, 3, 4, 5, 6}
A ∩ B{3, 4}
A − B{1, 2}
B − A{5, 6}
A Δ B{1, 2, 5, 6}
A'{5, 6, 7, 8}

Useful laws to remember:

  • Commutative: A ∪ B = B ∪ A and A ∩ B = B ∩ A
  • De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'
  • Counting formula: n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

Example

In a class of 60, 35 study Hindi, 30 study English and 15 study both. Students studying at least one language = 35 + 30 − 15 = 50.

2

Topic 2

Laws of set algebra

Key formulasLaws of sets

  • 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

    (A ∪ B)′ = A′ ∩ B′; (A ∩ B)′ = A′ ∪ B′

  • Identity

    A ∪ ∅ = A; A ∩ U = A

  • Complement

    A ∪ A′ = U; A ∩ A′ = ∅

  • Principle of duality: any law remains true if ∪ and ∩ are interchanged and U and ∅ are interchanged.
Key formulasCounting

  • Two sets

    n(A ∪ B) = n(A) + n(B) − n(A ∩ B)

  • Three sets

    n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C)

Example

Of 100 students, 60 study C and 50 study Python; 30 study both. Students studying at least one = 60 + 50 − 30 = 80; neither = 20.

3

Topic 3

Ordered pairs and proofs of set identities

  • Ordered pair (a, b): order matters — (a, b) = (c, d) only if a = c and b = d. The Cartesian product A × B = {(a, b) : a ∈ A, b ∈ B}; if n(A) = m and n(B) = n then n(A × B) = mn.
ProcessProving a set identity by element chasing
  1. 1Take an arbitrary x in the left side
  2. 2Use definitions to show x is in the right side (left ⊆ right)
  3. 3Take an arbitrary x in the right side
  4. 4Show it is in the left side (right ⊆ left)
  5. 5Conclude the sets are equal

Example

Prove A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). If x ∈ A ∩ (B ∪ C) then x ∈ A and (x ∈ B or x ∈ C), so x ∈ A ∩ B or x ∈ A ∩ C. The converse follows the same steps backwards. Hence the sets are equal.

  • Identities can also be proved with membership tables (like truth tables) or by algebra of sets using known laws.
4

Topic 4

Relations

  • Cartesian product: A × B = {(a, b) : a ∈ A, b ∈ B}. A relation from A to B is a subset of A × B.
ClassificationTypes of relations on a set A
Relations

  • Reflexive

    (a, a) ∈ R for every a

  • Symmetric

    (a, b) ∈ R implies (b, a) ∈ R

  • Antisymmetric

    (a, b) and (b, a) in R imply a = b

  • Transitive

    (a, b) and (b, c) in R imply (a, c) ∈ R

  • Equivalence

    Reflexive, symmetric and transitive

  • Partial order

    Reflexive, antisymmetric and transitive

Example

"Is congruent modulo 3" on integers is an equivalence relation; "divides" on positive integers is a partial order.

5

Topic 5

Equivalence relations and partitions

  • A relation R on A is an equivalence relation if it is reflexive, symmetric and transitive. Each element's equivalence class [a] = {x : x R a}; the classes form a partition of A.

Example

Congruence modulo 3 on integers: a R b if 3 divides (a − b). Classes [0] = {…, −3, 0, 3, 6, …}, [1] and [2] partition Z.

6

Topic 6

Partial order relations

  • A relation is a partial order if it is reflexive, antisymmetric and transitive; (A, ≤) is a poset. If every two elements are comparable it is a total (linear) order.
Key termsPoset concepts
Hasse diagram
Drawing of a poset without loops and transitive edges, smaller elements lower
Maximal and minimal elements
Nothing above or below them
Greatest and least elements
Above or below every element
Upper bound and least upper bound (join)
Supremum
Lattice
Poset in which every pair has a join and a meet

Example

Divisibility on {1, 2, 3, 6, 12}: 1 is least, 12 greatest; the Hasse diagram has 1 at the bottom, 2 and 3 above it, 6 above both and 12 at the top.

7

Topic 7

Hashing functions

  • A hash function h maps keys from a large set to addresses in a table of size m — a function from keys to {0, 1, …, m − 1}. Collisions occur because many keys map to one address (pigeonhole principle).
Key formulasHash functions

  • Division method

    h(k) = k mod m, with m a prime not close to a power of 2

  • Mid-square method

    Square k and take middle digits

  • Folding method

    Split k into parts and add them

  • Multiplication method

    h(k) = floor(m × fractional part of kA), 0 < A < 1

Example

m = 11: h(1234) = 1234 mod 11 = 2; h(5678) = 5678 mod 11 = 2 — a collision, resolved by probing or chaining.

8

Topic 8

Rings and subrings

  • A ring (R, +, ·) is a set with two operations such that (R, +) is an abelian group, multiplication is associative (closed), and multiplication distributes over addition.
Key termsTypes of rings
Commutative ring
ab = ba for all a, b
Ring with unity
Has a multiplicative identity 1
Subring
Subset that is itself a ring under the same operations (closed under subtraction and multiplication)
Zero divisors
Non-zero a, b with ab = 0 — e.g., 2 × 3 = 0 in Z6

Example

(Z, +, ×) is a commutative ring with unity; even integers 2Z form a subring without unity; Zn (integers modulo n) is a finite commutative ring.

9

Topic 9

Ring morphisms, ideals and quotient rings

  • A ring homomorphism f: R → S satisfies f(a + b) = f(a) + f(b) and f(ab) = f(a)f(b); its kernel {a : f(a) = 0} is an ideal. A bijective homomorphism is an isomorphism.
  • An ideal I of R is a subring such that ra and ar lie in I for every r in R and a in I — e.g., nZ in Z.
  • The quotient ring R/I has cosets a + I as elements with (a + I) + (b + I) = (a + b) + I and (a + I)(b + I) = ab + I. Z/nZ is isomorphic to Zn.
10

Topic 10

Integral domains, Euclidean domains and fields

ComparisonSpecial rings
Definition
Examples

Integral domain

Commutative ring with unity and no zero divisors

Z, Zp for prime p

Euclidean domain

Integral domain with a division algorithm (a = qb + r with r smaller than b in a size function)

Z with absolute value; polynomials over a field

Field

Commutative ring with unity in which every non-zero element has a multiplicative inverse

Q, R, C, Zp for prime p

  • Every field is an integral domain; every finite integral domain is a field. Z6 is not an integral domain (2 × 3 = 0); Z7 is a field.
11

Topic 11

Boolean algebra

Boolean algebra works on the values 0 and 1 with three operations: AND (·), OR (+) and NOT ('). Its laws let us reduce a long expression to a shorter equivalent one.

Key termsKey laws of Boolean algebra
Identity
A + 0 = A ; A·1 = A
Null
A + 1 = 1 ; A·0 = 0
Idempotent
A + A = A ; A·A = A
Complement
A + A' = 1 ; A·A' = 0
Absorption
A + AB = A ; A(A + B) = A
De Morgan
(A + B)' = A'B' ; (AB)' = A' + B'

Example

Simplify Y = AB + AB'. Y = A(B + B') = A·1 = A.

Example

Simplify Y = A + A'B. Using A + A'B = (A + A')(A + B) = 1·(A + B), so Y = A + B.

12

Topic 12

Applications: logic implications and gates

  • Boolean algebra models propositional logic (∧, ∨, ¬ correspond to ·, +, ′), so implications and equivalences can be simplified algebraically — p → q equals p′ + q.
Key termsBoolean functions and gates
AND
x · y
OR
x + y
NOT
x′
NAND and NOR
Universal gates
XOR
x′y + xy′
Implication p → q
p′ + q

Example

Simplify F = xy + xy′ + x′y: = x(y + y′) + x′y = x + x′y = x + y — one OR gate.

13

Topic 13

Karnaugh maps

A K-map is a grid representation of a truth table in which adjacent cells differ by only one variable (Gray code order: 00, 01, 11, 10). Grouping adjacent 1s removes the variable that changes, giving the simplest SOP.

ProcessSimplifying with a K-map
  1. 1

    Draw the map

    2ⁿ cells for n variables

  2. 2

    Fill the 1s

    From the minterms

  3. 3

    Group the 1s

    In 1, 2, 4, 8 … cells, as large as possible

  4. 4

    Allow overlaps and wrap-around

    Edges are adjacent

  5. 5

    Write one term per group

    Keep only variables that don't change

  6. 6

    OR the terms together

Example

Y = Σm(0, 1, 2, 3) for two variables fills the whole map, so Y = 1. For three variables, Y = Σm(1, 3, 5, 7) forms a group of four where C = 1 throughout, so Y = C.

Exam tip

Groups must be rectangles of size 1, 2, 4 or 8. Always draw the map with Gray code labels and circle every group.

Key terms

Ordered pair
Pair of elements in which order matters
Equivalence relation
Reflexive, symmetric and transitive relation
Partial order
Reflexive, antisymmetric and transitive relation
Ring
Set with addition and multiplication satisfying ring axioms
Field
Commutative ring with unity in which non-zero elements have inverses

Quick revision

  • Set operations and laws; Cartesian products; element-chasing proofs.
  • Relations; equivalence classes and partitions; posets, Hasse diagrams, lattices.
  • Hash functions: division, mid-square, folding, multiplication.
  • Rings, subrings, zero divisors; homomorphisms, kernels, ideals, quotient rings.
  • Integral and Euclidean domains, fields; Boolean algebra; gates; K-maps.

Important exam questions

Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).

Short-answer questions

  1. Q1.If n(A) = 3 and n(B) = 4, find n(A × B).
  2. Q2.Is "less than" on integers an equivalence relation? Why?
  3. Q3.Draw the Hasse diagram of divisibility on {1, 2, 4, 8}.
  4. Q4.Compute h(2025) for the division method with m = 13.
  5. Q5.Does Z8 have zero divisors? Give one.
  6. Q6.Distinguish an integral domain and a field.

Long-answer questions

  1. Q1.Prove set identities using element chasing and laws of sets.
  2. Q2.Explain equivalence and partial order relations with examples.
  3. Q3.Explain rings, subrings, ideals and quotient rings.
  4. Q4.Explain Boolean algebra and simplify a function with a Karnaugh map.

Stuck on this unit?

Message SBS on WhatsApp for help with Discrete Structures & Optimization, or to ask about studying M.Sc IT at Synetic.

WhatsApp us