Discrete Mathematics Answers

Question 1. [20 Marks]

a) Let p, q, and r be the propositions:

p = "the flag is set"

q = "I = 0"

r = "subroutine S is completed"

Translate each of the following propositions into symbols, using the letters p, q, r and logical connectives.

(i) If the flag is set, then I = 0 [2 marks]

(ii) The flag is set and I = 0 if subroutine S is not completed [2 marks]

(iii) Subroutine S is completed if and only if I = 0 and flag is set [2 marks]

b) State the converse, contrapositive, and inverse of each of these conditional statements.

(i) If it snows tonight, then I will stay at home [3 marks]

(ii) I go to the beach whenever it is a sunny summer day [3 marks]

(iii) When I stay up late, it is necessary that I sleep until noon [3 marks]

c) Explain the step-by-step procedure involved in finding the inverse of an n by n square matrix. [5 marks]

Show that the following relations are Partial order relations.

(a) R on the set of integers Z, defined by, R = {(a, b) | a ≤ b}

(b) R on the set of integers Z, defined by, R = {(a, b) | a ≥ b}

(c) R on the set of positive integers N, defined by, R = {(a, b) | a divides b} [Note: It is divisibility

relation]

(d) R on the Power set of a set S, defined by, R = {(A, B) | A is a subset of B} [Note: It is set inclu￾sion relation]

Let R = {(0, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 2), (3, 0)} be a relation on the set {0, 1, 2, 3}. Find the

(a) Reflexive closure of R

(b) Symmetric closure of R

(c) Transitive closure of R

A relation R on a set S is called asymmetric if (a, b) is in R implies that (a, b) is not in R. Which of the

relations in Q. No. 5 is asymmetric?

(I) A relation R on a set S is called irreflexive, if no element in S is related to itself, that is if for every a

in S, (a, a) is not in R. Which of the relations in Q. No. 5 is irreflexive?

Write down the relation R on the Power-set of S = {1, 2, 3, 4}, defined by, R = {(A, B) | A and B are

subsets of S and they have the same cardinality} using any one of the methods: (i) set of ordered pairs, (ii)

directed graphs, (iii) matrix notation.

Write down the relation R on the S = {1, 2, 3, 4, 5, 6} by any one of the methods: set of ordered pairs, 

directed graphs, matrix notation. R is given as follows. 

(a) R = {(a, b) | a = b }

(b) R = {(a, b) | a ≠ b}

(c) R = {(a, b) | a < b}

(d) R = {(a, b) | a ≤ b}

(e) R = {(a, b) | a > b}

(f) R = {(a, b) | a ≥ b}

(g) R = {(a, b) | a = b + 1}

(h) R = {(a, b) | a + b ≤ 3}

(i) R = {(a, b) | a divides b}

Let S = {1, 2, 3, 4, 5, 6}. How many ordered pairs are there in S × S ?

What will be the composition of two functions f ° g from R to R,

(a)

f(x) = 2x + 3, g(x) = 3x + 2

(b)

f(x) = 2x + 3, g(x) = sin (x)

(c)

f(x) = sin (x), g(x) = 2x + 3

(d)

f(x) = sin (x), g(x) = x2

(e)

f(x) = |x|, g(x) = 2x + 3