**Declaration of No Repetition of Previous Exam Questions**

Herewith, I declare that the exam for the course M131 of this semester has no repeated questions from previous exams. I also declare that all the exam questions cover all the course material and reflect what has been covered in the continuous assessment. Also, I declare that I did not solicit the opinions of other tutors regarding preparation of this exam and have ensured adequate security of the exam.

Name: Mohamed Sayed

Signed by: Mohamed Sayed

Date: 20/10/2012

**Faculty Of Computer Studies**

M131

**Discrete Mathematics**

**F I N A L E X A M I N A T I O N**

**Fall / 2012 – 2013**

--/01/2013

2 Hours / Time Allowed: / 4 /

**Number of Exam Pages (including this cover sheet):**

FORM A

Keys

Instructions:

**Part 1: MULTIPLE CHOICE QUESTIONS**

**You may solve all questions. Each question is worth 2 marks. Your grade in this part is that of the best 5 questions, giving a total of 10 possible marks. **

Q–1: The negation of is

a)

b)

c)

d)

e) None of the above

Q–2: The quotient and remainder when 77 is divided by 6 is

a) q = 11, r = 11

b) q = 12, r = 5

c) q = 13, r = −1

d) q = 14, r = −7

e) None of the above

Q–3: Assume that R is a relation on {1, 2, 3, 4} defined as follows: *a R b if and only if a + b is an odd number, then R* =

a) {(1,2), (1,4), (2,3), (3,4)}

b) {((2,1), (4,1), (3,2), (4,3)}

c) {(1,2), (3,4)}

d) {(1,2), (2,1), (1,4), (4,1), (2,3), (3,2), (3,4),(4,3)}

e) None of the above

Q–4: A minimal element of the Poset ({2, 4, 5, 10, 20, 25}, |) is

a) 4

b) 5

c) 10

d) 20

e) None of the above

Q–5: The number of rows in the adjacency matrix of the complete graph K6 is

a) 6

b) 7

c) 21

d) 36

e) None of the above

Q–6: The number of vertices in a full binary tree with 50 internal nodes is

a) 99

b) 101

c) 51

d) 49

e) None of the above

**Part 2: ESSAY QUESTIONS**

**Each question is worth 10 marks. You should answer only FOUR out of the five questions, giving a total of 40 possible marks. If you answer all five questions, your tutor will only mark the first four in the order presented.**

Q–1:

**a) [5×1 Marks]** Determine the truth value of each of the following statements:

i. If 0.5 is an integer, then 1 + 0.5 = 3.

T

ii. Cats can fly whenever 5 > 2.

F

iii. , domain is the set of real numbers.

F

iv. , domain is the set of integers.

F

v. 123 27 (mod 4).

T

**b) [3+2 Marks]** Establish whether each of the following propositions is a tautology, contradiction or contingency:

i. (p®q) ˅ (p® Øq), by using truth table.

p q / p®q / Øq / p® Øq / (p®q) ˅ (p® Øq)F F / T / T / T / T

F T / T / F / T / T

T F / F / T / T / T

T T / T / F / F / T

Tautology.

ii. Ø (p® (q®p)), by using law of logic.

Ø (*p® (q®p)) ≡ Ø ( Øp ˅ (Øq ˅ p)) ≡ Ø ((Øp ˅ p) ˅ Øq*)

≡ Ø (T ˅ Øq) ≡ ØT = F.

Contradiction.

Q–2:

**a) [5×1 Marks] **Let *P(x) be the statement "x is happy" and Q(x) be the statement "x* is under 20", where the universe of discourse for x is the set of students. Express each of the following in English:

i. P(Ali) ˄ Q(Ali).

Ali is happy and under 20

ii. Q(Ahmed) → P(Ahmed).

If Ahmed is under 20, then he is happy

iii. .

Some students are unhappy

iv. .

There is a student who is happy and over 20

v. .

Not all students are either unhappy or under 20.

**b) [3+2 Marks] **If *A = {x: x is an integer and 1≤ x ≤11}, B = {x | x is an even integer} and C* = {2, 3, 5, 6}.

i. Find (A Ç B) – C.

(A Ç B) – C = {4, 8, 10}

ii. How many members does the power set P(C) have? The Cartesian product A×C have?

|P(A)| = 16

|A×C| = 24

## Q–3:

**a) [5×1 Marks] **Consider the integers a = 825 and b = 1638.

i. Find the prime factorizations of a and b.

a = 3×52×11 & b = 2×32×7×13

ii. Are a and b relatively prime? Explain.

No, as 3 | a and 3 | b

iii. Find GCD(a, b) and LCM(a, b).

GCD(a, b) = 3

LCM(a, b) = 2×32×52×7×11×13 = 450450

iv. Convert a to a binary number.

a = (1100111001)2

v. Convert a to a hexadecimal number.

a = (339)16

**b) [1+2+2 Marks] **Let

i. Calculate B ˄ C.

B ˄ C =

ii. Calculate B ⊙ A.

B ⊙ A =

iii. List the elements of the relation R on the set {1, 2, 3} represented by the matrix A.

R = {(1, 1), (1, 3), (2, 2), (2, 3), (3, 1)}

## Q–4:

## a) [5×1 Marks] Let R1 = {(x, y): x = y − 1} and R2 = {(x, y): x < y} be relations on the set A = {1, 2, 3, 4}.

i. List the elements of R1 and R2.

R1 = {(1, 2), (2, 3), (3, 4)}

R2 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

ii. Find R2○ R1.

R2○ R1 = {(1, 3), (1, 4), (2, 4)}

iii. Find the matrix representation of R2.

iv. Find the symmetric closure of R1.

{(1, 2), (2, 3), (3, 4), (2, 1), (3, 2), (4, 3)}

v. Find the transitive closure of R2.

{(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}

**b) [5 Marks] **Show that the relation on the set of integers

R = {(a, b) | a – b is an even integer}

is an equivalence relation.

Reflexive: *a – a = 0; even integer, so (a, a) in R for all a*.

Symmetric: If (*a, b) in R, then a – b = 2n for some integer n, thus b – a = –2n and hence b – a* is an even integer, then (b, a) in R for all a, b.

Transitive: If (*a, b) and (b, c) in R, so a – b = 2n and b – c = 2m for some integers n , m. Now a – c = (a – b) + (b – c) = 2(n + m); even integer, hence (a, c) in R for all a, b, c*.

## Q–5:

a) [3+2 Marks] Let be the adjacency matrix of a graph G = (E, V), E = {a, b, c, d}.

i. Draw G.

ii. Find the incidence matrix of G.

b) [3+1+1 Marks] Consider the binary search tree that results when the following integers are inserted in the order given: 50, 90, 40, 45, 80, 60, 65, 30.

i. Draw the tree.

ii. Is it a full binary tree? Find its height.

It is not a full binary tree. Its height is 4.

iii. Show the inorder traversal of that tree.

30, 40, 45, 50, 60, 65, 80, 90