ASSIGNMENT 04
Total Marks: 100
Memorandum
ONLY FOR YEAR MODULE
All questions will be marked.
DO NOT USE A CALCULATOR TO OBTAIN YOUR ANSWERS-WHERE APPLICABLE, LEAVE
YOUR ANSWERS IN TERMS OF FACTORIALS, n Cr AND n Pr .
Question 1: 6 Marks
Determine whether the relation R is a partial order on the set A, where A = R and aRb if and only if
a ≤ b.
Solution
We must check fro reflexivity, antisymmetry and transitivity.
Reflexive: Yes. Since a = a, we have a ≤ a and hence aRa for all a ∈ A.
Antisymmetry: Suppose aRb and bRa. Then
a ≤ b and b ≤ a.
Hence a = b. Thus R is antisymmetric.
Transitive: Suppose aRb and bRc. Then
a ≤ b and b ≤ c.
Hence, a ≤ c, i.e. aRc. Thus R is transitive.
Hence R is a partial order on A.
26
, /
Question 2: 22 Marks
(2.1) Draw a Hasse diagram of the lattice D36 . (10)
Solution
D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}. See Example 3 of Section 6.3 and the Section on Hasse diagrams
in Section 6.1 of KBR.
(2.2) What are ∨ and ∧ here? (4)
Solution
For divisibility, a ∨ b is the least number into which both a and b divide, i.e. the Least Common
Multiple of a and b (LCM(a, b)).
For divisibility, a ∧ b is the largest number that divides into both a and b, i.e. the Greatest Common
Divisor of a and b (GCD(a, b)).
(2.3) Is D36 a complemented lattice? Explain. (4)
Solution
To be a complemented lattice, all elements must have complements (some may have more than one
complement). But here, not all elements have complements. Recall the definition of a complement:
x has y as a complement if
x ∧ y = O, (the least element)
x ∨ y = I. (the greatest element)
Consider, for example, x = 2. The elements y for which
x ∧ y = 1 is y = 1 or y = 3 or y = 9.
27
Total Marks: 100
Memorandum
ONLY FOR YEAR MODULE
All questions will be marked.
DO NOT USE A CALCULATOR TO OBTAIN YOUR ANSWERS-WHERE APPLICABLE, LEAVE
YOUR ANSWERS IN TERMS OF FACTORIALS, n Cr AND n Pr .
Question 1: 6 Marks
Determine whether the relation R is a partial order on the set A, where A = R and aRb if and only if
a ≤ b.
Solution
We must check fro reflexivity, antisymmetry and transitivity.
Reflexive: Yes. Since a = a, we have a ≤ a and hence aRa for all a ∈ A.
Antisymmetry: Suppose aRb and bRa. Then
a ≤ b and b ≤ a.
Hence a = b. Thus R is antisymmetric.
Transitive: Suppose aRb and bRc. Then
a ≤ b and b ≤ c.
Hence, a ≤ c, i.e. aRc. Thus R is transitive.
Hence R is a partial order on A.
26
, /
Question 2: 22 Marks
(2.1) Draw a Hasse diagram of the lattice D36 . (10)
Solution
D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}. See Example 3 of Section 6.3 and the Section on Hasse diagrams
in Section 6.1 of KBR.
(2.2) What are ∨ and ∧ here? (4)
Solution
For divisibility, a ∨ b is the least number into which both a and b divide, i.e. the Least Common
Multiple of a and b (LCM(a, b)).
For divisibility, a ∧ b is the largest number that divides into both a and b, i.e. the Greatest Common
Divisor of a and b (GCD(a, b)).
(2.3) Is D36 a complemented lattice? Explain. (4)
Solution
To be a complemented lattice, all elements must have complements (some may have more than one
complement). But here, not all elements have complements. Recall the definition of a complement:
x has y as a complement if
x ∧ y = O, (the least element)
x ∨ y = I. (the greatest element)
Consider, for example, x = 2. The elements y for which
x ∧ y = 1 is y = 1 or y = 3 or y = 9.
27
