M131: Discrete Mathematics
Q–1:
[2+3 Marks]
a)
Find
a proposition using only
and the
connective ˅ with the following truth table:
and the
connective ˅ with the following truth table:|
p
|
q
|
?
|
|
F
|
F
|
F
|
|
F
|
T
|
T
|
|
T
|
F
|
T
|
|
T
|
T
|
F
|
Answer:
b)
Using
the truth table, determine whether or not the proposition
is a tautology.
Answer:
Q−2: [5×1
marks] Determine whether each of the
following is TRUE or FALSE:
a) (1 > 2 or 1 + 2 = 4) if (1 + 1 = 2
and 1 > 2).
b) (124 mod 6 = 4) → (5 | 16).
c) 
, domain is the
set of integers.
, domain is the
set of integers.
d) 
, domain is the
set of integers.
, domain is the
set of integers.
e) 
.
.
Answer:
|
a)
|
b)
|
c)
|
d)
|
e)
|
|
|
|
|
|
|
Q−3: [3+2
marks]
a)
Let
A = {a, b, c} and B = {1, 2, 3, 4}.
Determine whether each of the following is TRUE or FALSE:
i.
.
.
ii. 
.
.
iii. 
.
.
iv. 
.
.
v.
.
.
vi. 
.
.
Answer:
|
i.
|
ii.
|
iii.
|
iv.
|
v.
|
vi.
|
|
|
|
|
|
|
|
b) Show that
.
.
Answer:
Q−4: [3+2 marks]
a) Consider the decimal number a =
137.
i.
Find in set builder
notation the set of all positive integers b such that
b ≡ a (mod 5).
ii.
Is the number a
prime? Explain.
iii.
Convert the number a
to binary and octal numbers.
Answer:
b)
Find the hexadecimal
representation of the expansion
.
.
Answer:
Q−5: [2+3 marks]
a) Find the smallest positive integer a
in the encryption function
f (x)
= (ax + 7) mod 26, 0 ≤ x ≤ 25,
such that the function encodes the letter “H” by “C”.
Answer:
b) Decrypt the message “QHHG KHOS” taking
into consideration that you are using the encryption function
f (x)
= (x + 3) mod 26, 0 ≤ x ≤ 25.
Answer:
Q−6: [2+3 marks] Let R1 = {(x, y): |x
- y| ≤ 1} and R2 = {(x, y): 2x + y
≤ 6} be relations on the set A = {1, 2, 3, 4}.
a)
List the elements of R1
and R2.
Answer:
b)
Find 
and 
.
and .
Answer:
Q−7: [3+2 marks]
a)
Find the transitive
closure of R = {(a, a), (b, a), (b, c), (c, a),
(c, c), (c, d), (d, a), (d, c)} on the set {a,
b, c, d}.
Answer:
b)
Find
the smallest equivalence relation on {1, 2, 3} that contains (1, 2) and (2, 3).
Answer:
Q−8: [2+3 marks]
a)
Let R = {(1, 1),
(1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 3), (4, 4), (5, 5),
(6, 6)} be an equivalence relation on A = {1, 2, 3, 4, 5, 6}. Find the
equivalence classes for the partition of A given by R.
Answer:
b)
Let R be the
partial order relation defined on A = {2, 3, 4, 5, 6, 8, 10, 40}, where xRy
means x | y.
i.
Draw the Hasse diagram
for R.
ii.
Find the upper and lower
bounds of {4, 8}.
Answer:
