MAT2612/202/1/2018

Tutorial letter 202/1/2018

Introduction to Discrete Mathematics

MAT2612

Semester 1

Department of Mathematical Sciences

This tutorial letter contains solutions for assignment 02.

BARCODE

university
Define tomorrow. of south africa
 ONLY FOR SEMESTER 1 STUDENTS
ASSIGNMENT 02
Unique Nr.: 810493
Chapters 5 and 6
Fixed closing date: 4 April 2018

Only certain questions will be marked.

1. Suppose A = {a, b, c, d, e} and R is the relation on A defined by

R = {(a, a) , (b, c) , (c, d) , (d, a) , (e, b)} .

State with reasons, whether the relation is

(a) a function from A to A;

(b) an everywhere defined function;
(c) an onto function;
(d) a one-to-one function. (4)

Solution:

(a) Since we don’t have (x, y) and (x, z) in R for y 6= z, R is a function from A to A. Informally,
no element of the domain maps to more than one element of the range.
(b) Since, for each x ∈ A there exists a y ∈ A such that (x, y) ∈ R, R is everywhere defined.
Informally, every element of A maps to something.
(c) R is not onto since there is no x ∈ A such that (x, e) ∈ R. Informally, not every element
of A is reached.
(d) Since we have (a, a) and (d, a) in R and a 6= d, the function is not−to−one. Informally,
different elements of the domain map to the same element of the range.

2. Let f : R2 → R2 be the function defined by f (x, y) = (x + y, x − y) .

(a) Show that f is one-to-one. (3)

(b) Find f −1 . Show that (f −1 ◦ f ) (x, y) = (x, y) . (6)

2
 MAT2612/202/1/2018

Solution:

(a) In order to show that f is one−to−one we must show that

f (x, y) = f (x0 , y 0 ) ⇒ (x, y) = (x0 , y 0 ) .

Now

f (x, y) = f (x0 , y 0 )
⇒ (x + y, x − y) = (x0 + y 0 , x0 − y 0 )
⇒ x+y = x0 + y 0 (1)
and x − y = x0 − y 0 (2)

By adding (1) and (2) we get

2x = 2x0 , i.e. x = x0
and by subtracting (2) from (1) we get

2y = 2y 0 , i.e. y = y 0 .

Hence (x, y) = (x0 , y 0 ) , and thus f is one−to−one.

(b) We note that
(a, b) = f (x, y) ⇔ f −1 (a, b) = (x, y) .
Thus in order to find f −1 we need to write x and y in terms of a and b.
Now
(a, b) = f (x, y)
⇔ (a, b) = (x + y, x − y)
⇔ x+y =a
and x − y =b

⇔ 2x =a+b
and 2y =a−b

⇔ x = a+b
2
and y = a−b2
 
a+b a−b
Hence (x, y) = f −1 (a, b) = , .
2 2
Thus f −1 can be defined by
 
−1 x+y x−y
f (x, y) = , (changing variables)
2 2

3
 Thus
(f −1 ◦ f ) (x, y) = f −1 (f (x, y))

= f −1 (x + y, x − y)
 
x + y + (x − y) x + y − (x − y)
= ,
2 2
 
2x 2y
= ,
2 2

= (x, y) .

3. Suppose A has 4 elements and B has 3 elements.

(a) How many everywhere defined functions are there from A to B? (3)
(b) How many everywhere defined onto functions are there from A to B? (3)
(c) How many everywhere defined functions are there from B to A? (3)
(d) How many everywhere defined onto functions are there from B to A? (3)

Solution:
Let A = {a1 , a2 , a3 , a4 } and B = {b1 , b2 , b3 } .

(a) Suppose f is an everywhere defined function from A to B. We can define

f (a1 ) to be any of b1 , b2 or b3 ; thus there are 3 options for f (a1 )

The same holds for f (a2 ) , f (a3 ) and f (a4 ) . Hence by the product rule there are

3 × 3 × 3 × 3, i.e. 34

everywhere defined functions from A to B.

(b) Think of a function from A to B as a word of length 4 over {b1 , b2 , b3 } For example,
b1 , b2 , b3 , b2 is the function
f (a1 ) = b1
f (a2 ) = b2
f (a3 ) = b3
f (a4 ) = b2
Thus the word give the sequence of function values. Since each of the elements in {b1 , b2 , b3 }
must appear in the word (f must be onto), 3 of the 4 positions in the 4 letter word are
taken by 3 different elements. There is thus 1 remaining space. Thus one of the elements
b1 , b2 and b3 will occur twice. Choose which element occurs twice - there are 3 choices for
this. The remaining two elements appear only once. After choosing which element occurs

4
 MAT2612/202/1/2018

twice you must arrange 4 objects of which 2 are of the same type and the other 2 different.
We can arrange these 4 objects in
4!
ways.
2!
See Theorem 5 and Example 10 in Section 3.2 of KBR. Hence in total there are
4!
3· different words,
2!
4!
i.e 3. everywhere defined onto functions.
2!
(c) Using reasoning similar to that in (a) it follows that there are
4 × 4 × 4 = 43
different everywhere defined functions from B to A.
(d) Suppose f is an everywhere defined onto function from B to A.
Since the number of elements of B is less than the number of elements of A and f is onto, it
follows that one of the elements of B must map onto two elements in A. Hence f cannot be
a function, which is a contradiction. Thus there are no everywhere defined onto functions
from B to A.

4. Use the definition of O (f ) to show that each of the following is O (n2 ) .

(a) 5n2 + 4n + 2 (4)

n
(b) lg n (4)

Solution:

(a) We must find constants c and k ∈ Z+ such that

|5n2 + 4n + 2| ≤ c |n2 | for all n ≥ k,
i.e. 5n2 + 4n + 2 ≤ cn2 for all n ≥ k.
Now
5n2 + 4n + 2 ≤ 5n2 + 4n2 + 2n2 for n ≥ 1
= 11n2 for all n ≥ 1.
Hence |5n2 + 4n + 2| ≤ c |n2 | for all n ≥ k, where c = 11 and k = 1. Hence 5n2 + 4n + 2
is O (n2 ) .
(b) Consider the graphs of y = x and y = lg x. You will note that x ≥ lg x for all x > 0.
We must find constants c and k ∈ Z+ such that
|lg nn | ≤ c |n2 | for all n≥k
i.e. lg nn ≤ cn2 for all n ≥ k.
Now
lg nn = n lg n
≤ n · n for n ≥ 1
= n2 for n ≥ 1.
Hence |lg nn | ≤ c |n2 | for all n ≥ k, where c = 1 and k = 1. Hence lg nn is O (n2 ) .

5
 5. Let A = {1, 2, 3, 4, 5, 6, 7, 8} . Compute the product (composition)

(1, 4, 8) ◦ (2, 3, 5, 8) ◦ (1, 7)

and write it in the form  

1 2 3 4 5 6 7 8
.

(3)
Solution:
(1, 4, 8) ◦ (2, 3, 5, 8) ◦ (1, 7)
     
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
= ◦ ◦
4 2 3 8 5 6 7 1 1 3 5 4 8 6 7 2 7 2 3 4 5 6 1 8
   
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
= ◦
4 2 3 8 5 6 7 1 7 3 5 4 8 6 1 2
 
1 2 3 4 5 6 7 8
= .
7 3 5 8 1 6 4 2

[Remember f ◦ g ◦ h (x) = f (g (h (x))) , so begin working from right to left.]

Short method:
Begin with the permutation on the right and work towards the left:
1 maps to 7 (right permutation), then 7 maps to 7 (middle permutation) and then 7 maps to 7
(left permutation). Thus 1 maps to 7. Using a short hand notation we write:

1 → 7 → 7 → 7; hence 1 → 7.

Thus we have
2 → 2 → 3 → 3; hence 2→3
3 → 3 → 5 → 5; hence 3→5
4 → 4 → 4 → 8; hence 4→8
5 → 5 → 8 → 1; hence 5→1
6 → 6 → 6 → 6; hence 6→6
7 → 1 → 1 → 4; hence 7→4
8 → 8 → 2 → 2; hence 8→2

Thus the composition is given by

 
1 2 3 4 5 6 7 8
.
7 3 5 8 1 6 4 2

6. Let    
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
p= and q = .
6 1 4 3 5 8 2 7 4 3 2 1 8 7 6 5

(a) Write p as a function, e.g. p (1) = 6, p (2) = . . . (2)

6
 MAT2612/202/1/2018

(b) Write p as a product of disjoint cycles. (2)

(c) Write p as a product of transpositions. (2)
(d) Is p an even or odd permutation? (2)
(e) Compute p ◦ p and p ◦ q. (4)
(f) Compute p−1 . (2)
(g) Determine the period of p, that is, the smallest positive integer k such that
 
k 1 2 3 4 5 6 7 8
p = .
1 2 3 4 5 6 7 8

(3)
(h) Find a permutation h such that
 
1 2 3 4 5 6 7 8
p◦h= .
7 3 4 6 5 8 1 2

(4)

Solution:

(a) p (1) =6
p (2) =1
p (3) =4
p (4) =3
p (5) =5
p (6) =8
p (7) =2
p (8) =7

(b) We start at 1. It goes to 6 which goes to 8 which goes to 7 which goes to 2 which goes back to
1. So we have the cycle (1, 6, 8, 7, 2) . We then consider 3. It goes to 4 which goes back to 3.
Thus we have the cycle (3, 4) . Finally 5 maps onto itself. Thus

p = (1, 6, 8, 7, 2) ◦ (3, 4) ◦ (5) .

(c) We have
p = (1, 2) ◦ (1, 7) ◦ (1, 8) ◦ (1, 6) ◦ (3, 4) .

Note the order of the “decompostion” and the fact that (5) is not a transposition.

(d) Since we wrote p as the product of 5 transpositions and 5 is odd, p is odd.

7
    
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
(e) p ◦ p = ◦
6 1 4 3 5 8 2 7 6 1 4 3 5 8 2 7
 
1 2 3 4 5 6 7 8
= .
8 6 3 4 5 7 1 2
   
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
p◦q = ◦
6 1 4 3 5 8 2 7 4 3 2 1 8 7 6 5
 
1 2 3 4 5 6 7 8
= .
3 4 1 6 7 2 8 5

(f) Since
p = {(1, 6) , (2, 1) , (3, 4) , (4, 3) , (5, 5) , (6, 8) , (7, 2) , (8, 7)}

we have
p−1 = {(6, 1) , (1, 2) , (4, 3) , (3, 4) , (5, 5) , (8, 6) , (2, 7) , (7, 8)}
= {(1, 2) , (2, 7) , (3, 4) , (4, 3) , (5, 5) , (6, 1) , (7, 8) , (8, 6)} .

Hence  
−1 1 2 3 4 5 6 7 8
p = .
2 7 4 3 5 1 8 6

(g) We have
p = (1, 6, 8, 7, 2) ◦ (3, 4) ◦ (5) .

We note that each element in the cycle (1, 6, 8, 7, 2) maps to itself every 5 steps, e.g. 1 − 6 − 8 −
7 − 2 − 1. Also each element in (3, 4) maps to itself every 2 steps. Hence every element in

(1, 6, 8, 7, 2) ◦ (3, 4) ◦ (5)

maps to itself every LCM (5, 2) steps, i.e. every 10 steps.

Hence the period is k = 10.

(h) Let p ◦ h = r. We want h, so we compose both sides on the left with p−1 as follows:

p−1 ◦ (p ◦ h) = p−1 ◦ r
p−1 ◦ p ◦ h = p−1 ◦ r


i.e.
i.e. h = p−1 ◦ r since p−1 ◦ p = Id .

Thus    
1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
h = ◦
2 7 4 3 5 1 8 6 7 3 4 6 5 8 1 2
 
1 2 3 4 5 6 7 8
= .
8 4 3 1 5 6 2 7

8
 MAT2612/202/1/2018

7. (a) Let A = {a, b, c, d, e, f, g} . Write the following permutation as the product of disjoint
cycles.  
a b c d e f g
g d b a c f e
(2)
(b) Determine whether the following permutation is even or odd.
 
1 2 3 4 5 6 7 8
4 2 1 6 5 8 7 3
(4)

Solution:

(a) We start at a. It goes to g which goes to e which goes to c which go b which goes to d
which goes back to a. Thus we have the cycle (a, g, e, c, b, d). Finally f maps onto itself.
Thus the permutation is equal to (a, g, e, c, b, d) ◦ (f ).
(b)  
1 2 3 4 5 6 7 8
p =
4 2 1 6 5 8 7 3

= (1, 4, 6, 8, 3) ◦ (2) ◦ (5) ◦ (7) (product of disjoint cycles)

= (1, 3) ◦ (1, 8) ◦ (1, 6) ◦ (1, 4) (product of transpositions)

Since p is the composition of an even number of transpositions, it is an even permutation.

8. (a) Draw the Hasse diagram of the lattice D56 . (5)

(b) What are ∨ and ∧ here? (2)
(c) Is D56 a complemented lattice? Explain. (3)
(d) Is D56 a Boolean algebra? Explain. (2)

Solution:

(a) D56 = {1, 2, 4, 7, 8, 14, 28, 56}

See Example 3 of Section 6.3 and the section on Hasse Diagrams in Section 6.1 of KBR.

9
 (b) 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)) .
(c) 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 complement if

x∧y = O (the least element)

x∨y = I (the greatest element).

Consider, for example, x = 2. The element y for which

x ∧ y = 1 is y = 1 or y = 7.

But 2 ∨ 1 = 2 and 2 ∨ 7 = 14.

Hence no y is a complement for 2. Thus D56 is not a complemented lattice.
(d) D56 is not a Boolean algebra since it is not a complemented lattice. Also note, that
although D56 has 8 = 23 elements it is not a Boolean algebra since D56 is not isomorphic
to B3 .

9. Draw the Hasse diagram of the poset represented by the following matrix. (Call the elements
a, b, c, d, e.)  
1 1 1 1 1
 0 1 1 1 0 
 
 0 0 1 0 1 .
 
 0 0 0 1 0 
0 0 0 0 1

(4)

Solution:

It is not surprising if you were unable to do this question using the matrix above which was
given in Tutorial Letter 101, since the matrix above does not represent a poset. Why is this
so? The matrix above does not represent a transitive relation. Suppose MR denotes the
matrix in the question. Then
     
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 0 1 1 1 0   0 1 1 1 0   0 1 1 1 1 
     
MR2 = MR MR =   0 0 1 0 1   0 0 1 0 1  =  0 0 1 0 1 .
    
 0 0 0 1 0   0 0 0 1 0   0 0 0 1 0 
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1

Then MR2 has a one in the 2nd row 5th column which is not in MR . Hence R is not transitive.

10
 MAT2612/202/1/2018

Consider, for example, (A, R) , where A = {a, b, c, d, e} and

 
1 1 1 1 1
 0 1 1 1 1 
 
MR =  0 0 1 0 1 

 0 0 0 1 0 
0 0 0 0 1

Then (A, R) is a poset and

R = {(a, a) , (a, b) , (a, c) , (a, d) , (a, e) , (b, b) , (b, c) , (b, d) , (b, e) , (c, c) , (c, e) , (d, d) , (e, e)} .

The Hasse diagram in this case is

10. Draw the Hasse diagram of a partially ordered set (poset) satisfying the following:

(a) The poset contains 3 elements a, b, c and {a, b} has a least upper bound but no greatest
lower bound. (3)
(b) The poset contains 4 elements a, b, c, d and {a, b} has exactly two lower bounds but no
greatest lower bound. (3)
(c) The poset contains 4 elements a, b, c, d and {a, b} has exactly two upper bounds and a least
upper bound. (3)

Solution:

The following are examples of Hasse diagrams:

(a)

(b)

11
 (c)

11. Consider the poset H represented by the following Hasse diagram.

(a) Give each of the following. If any do not exist, explain why.
(i) All minimal elements of H. (2)
(ii) The least element of H. (1)
(iii) All maximal elements of H. (2)
(iv) The greatest element of H. (1)
(v) All upper bounds of {f, g}. (2)
(vi) The least upper bound of {f, g}. (1)
(vii) All lower bounds of {a, b}. (2)
(viii) The greatest lower bound of {a, b}. (1)
(ix) All lower bounds of {c, d, e} . (2)
(x) The greatest lower bound of {c, d, e} . (1)
(xi) Any two elements which are complements of each other. (2)
(b) Give complete reasons for answers to the following:
(i) Is H a lattice? (3)
(ii) Is H a Boolean algebra? (3)

Solution:

(a) (i) A minimal element is one that has no path downwards. The minimal element is h.

12
 MAT2612/202/1/2018

(ii) The least element, if it exist, is the element with paths upwards to all others. In
this case the least element is h.
(iii) A maximal element is one that has no path upwards. The maximal elements are

a and b.

(iv) The greatest element, if it exists, is the element with paths downwards to all others.
In this case there is no greatest element. Note a and b are not comparable.
(v) Upper bounds of {f, g} are those elements (including f and g) which have paths down-
wards to both f and g. In this case they are e, b and a.
(vi) The least upper bound of {f, g} if it exists, is the upper bound of {f, g} which is less
than all other upper bounds. In this case it is e.
(vii) Lower bounds of {a, b} are those elements (including a and b) which have paths upwards
to both a and b. In this case they are d, e, f, g and h.
(viii) The greatest lower bound of {a, b} if it exists, is the lower bound of {a, b} which is
greater than the other lower bounds. In this case it does not exist because d and e
are not comparable.
(ix) Lower bounds of {c, d, e} are those elements (including c, d and e) which have paths
upwards to c, d and e. In this case they are f and h.
(x) The greatest lower bound of {c, d, e} if it exists, is the lower bound of {c, d, e} which
is greater than the other lower bounds. In this case it is f.
(xi) A complement of an element is defined for a poset only if the poset is a bounded lattice.
Thus, since the poset H is not a lattice (see (b)(i) below) the question does not make
sense.
(b)(i) H is not a lattice since not all pairs of elements have a LUB and GLB. For example,
{a, b} has no LUB.
(Also, according to Theorem 5 of Section 6.3 of KBR a finite lattice is bounded. Since
H has no greatest element, H cannot be a lattice.)
(ii) H is not a Boolean algebra because it is not a lattice.

12. Chapter dependencies of textbooks is a familiar partial ordering of the chapters in a text-
book. Define A < B if chapter A is a prerequisite for chapter B. Let C be the set of
chapters and let the prerequisites be given by

Chapter Prerequisites
Chapter 1 None
Chapter 2 Chapter 1
Chapter 3 Chapter 2
Chapter 4 Chapter 2
Chapter 5 Chapter 3
Chapter 6 Chapter 4
Chapter 7 Chapter 3,6

(a) Draw the Hasse diagram for the partial ordering of the chapters. (4)
(b) Give all the minimal and maximal elements of C. (3)

13
 (c) Does C have a least element or a greatest element? If so give them. (2)
(d) Suppose you want to read the entire book, one chapter a month.
(i) Which choice or choices do you have for your first and your last chapter? (3)
(ii) You want to read chapter 6 as soon as possible. After how many months can you
begin chapter 6? (2)
(iii) Do you need to read all the other chapters before you can read chapter 7? If not,
which chapter(s) can you leave out? (2)
(iv) You want to read chapters 1, 2, 3 in order and chapter 7 last. Find all possible ways
that you could read the book. (4)

Solution:

(a)

(b) Minimal element is 1.

Maximal elements are 5 and 7.
(c) C has a least element, namely 1.
There is no greatest element since 5 and 7 are maximal, but not comparable.
(d) (i) You have to read chapter 1 first as it is the least element.
You can read either chapter 5 or 7 last.
(ii) You have to read chapters 1, 2 and 4 before you can read chapter 6. You can begin
chapter 6 after 3 months.
(iii) You need not read all other chapters before you read chapter 7. You can leave chapter
5 out.
(iv) The following give the order of chapters in which you can read the book.

1, 2, 3, 5, 4, 6, 7
1, 2, 3, 4, 5, 6, 7
1, 2, 3, 4, 6, 5, 7

14
 MAT2612/202/1/2018

13. (a) Construct the truth table for the following Boolean function:

f (x, y, z) = (x ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z) .

Write it in the form:

x y z f (x, y, z)
0 0 0 ?
0 0 1 ?
0 1 0 ?
1 0 0 ?
0 1 1 ?
1 0 1 ?
1 1 0 ?
1 1 1 ?
(4)
(b) Use a Karnaugh map to simplify the Boolean expression given in (a). (4)

Solution:

(a) In completing the table we use the facts that

1 ∨ 0 = 1, 0∨0=0 and 1∨1=1

1 ∧ 0 = 0, 0∧0=0 and 1∧1=1
00 = 1 and 10 = 0.

See 8, 9 and 12 of the properties given after Example 6 in Section 6.4 of KBR.

x y z x∧y∧z x ∧ y0 ∧ z x0 ∧ y ∧ z f (x, y, z)
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 0 0 0 0 0
1 1 1 1 0 0 1
Example. Consider the fifth row of the table, where

x = 0, y = 1 and z = 1. Then
x∧y∧z = 0∧1∧1 = 0∧1=0
x ∧ y0 ∧ z = 0 ∧ 0 ∧ 1 = 0 ∧ 0 = 0
and x0 ∧ y ∧ z = 1 ∧ 1 ∧ 1 = 1 ∧ 1 = 1.

Then
(x ∧ y ∧ z) ∨ (x ∧ y 0 ∧ z) ∨ (x0 ∧ y ∧ z) = 0 ∨ 0 ∨ 1 = 1.

15
 (b)

See Figures 6.84 and 6.85 in Section 6.6 of KBR. A simplification is

f (x, y, z) = (x ∧ z) ∨ (y ∧ z) .

16