QUESTION 1 (20 Marks)

a)  Let that p and r are false and that q and s are true, find the truth value of following

proposition.

i.     (s → (p ∧ ¬r)) ∧ ((p → (r ∨ q)) ∧ s)

(1 Mark)

ii.     ((p ∧ ¬q) → (q ∧ r)) → (s ∨ ¬q)

(1 Mark)

iii.     (p → q) ∧ (q → r)

(1 Mark)

b)  Use Logical Equivalence Theorem to verify the logical equivalences below.

~(p ↔ q) ≡ (p ↔ ~q)

(9 Marks)

c)  Use the valid arguments forms to deduce the conclusion from the given situation, giving a reason for each step.

You are about to leave for class in the morning and found that you left your book. You know the following statements are true:

1.  If I was reading my book in the kitchen, then it should be on the kitchen table.

2.  If my book is on the kitchen table, then I saw it at breakfast.

3.  I did not see my book at breakfast.

4.  I was reading my book in the living room or I was reading my book in the kitchen.

5.  If I was reading my book in the living room then my book is on coffee table.

Where is the book?

(8 Marks)

QUESTION 2 (20 marks)

a)  Use the method of direct proof to prove the following statements.

i.     Prove that if n is a positive integer, then n mod 10 is the digit in the ones place in the decimal representation for n .

(3 Marks)

ii.     Prove that if A ∩ B = A ∩ C and A U B = A U C, then B = C for all sets A, B and

.

(3 Marks)

b)  Use the method of proof by contradiction to prove the following statements.

i.     For all integer x , 3x + 2 is not divisible by 3.

(3 Marks)

ii.     The negative of any irrational number is irrational.

(3 Marks)

c)  Find counterexample to show that the statements are false.

i.     There exist three integers x, y, z , all greater than 1 and no two equal for which

y            z

(2 Marks)

ii.     If a, b, and d are integers where d > 0, and a mod d = b mod d , then a = b .

(2 Marks)

iii.     For all real numbers r and s , ⌊r − s⌋ = ⌊r⌋ − ⌊s⌋ .

(2 Marks)

iv.     The sum of any two irrational numbers is irrational.

(2 Marks)

QUESTION 3 (20 Marks)

a)  Prove the following statement by using induction method.

For any real number X except 1, and any integer n ≥ 0,  ∑0 X i  =  .

(7 Marks)

b)  Let the sum of the first two terms of a geometric series is 7 and the sum of the first six terms is 91. Show that the common ratio r satisfies r 2  = 3.

(3 Marks)

c)  Use iteration method to guess an explicit formula for the recurrence relation below. bn  = 3bn−1  + 1 for all integers n ≥ 2 where initial condition, b1  = 1.

(4 Marks)

d)  Let B = {0, 1,2,3,4} and consider the following partition of B: {0,3,4}, {1}, {2} . Find the relation R induced by this partition.

(6 Marks)

QUESTION 4 (20 Marks)

a)  Prove the Inclusion-Exclusion Principle for two sets.

(5 Marks)

b)  By using principle in (a),

i.     Find how many integers from 1 through 1000 are multiples of 4 or multiples of

6.

(3 Marks)

ii.     Find how many integers from 1 through 1000 are neither multiples of 4 nor multiples of 6.

(2 Marks)

c)  Write down the quadratic expression 3y2  + 5y − 2 in the form (ay − b)(y + c) .Hence find the coefficient of the term in y9  in the expansion of (3y2  + 5y − 2)5 .

(7 Marks)

d)  Consider the identity  +  where P, Q  ∈ Ζ . Hence find the value of P and Q .

(3 Marks)

QUESTION 5 (20 Marks)

a)  A probability experiment has four possible outcomes: p1, p2, p3, p4 . The outcome p1  is four times as likely as each of the three remaining outcomes. Find the probability of

p1 .

(2 Marks)

b)  Given any set of four integers, must there be two that have the same remainder when divided by 3? Justify your answer.

(3 Marks)

c)  Student A  and  Student  B  take  a  final  examination  in  Discrete  Structures.  The probability that Student A passes is 0.75, and the probability that Student B passes is 0.8. Let the events “Student A passes the final examination” and “Student B passes the final examination” are independent. Find,

i.     probability that Student A does not pass

(1 Mark)

ii.     probability that both pass

(2 Marks)

iii.     probability that both fail

(2 Marks)

d)  Describe  how  minimum  spanning  trees  being  applied  on  one  of  the  following applications:

1.  Telecommunication network

2.  Transportation network

3.  Computer network

4.  Water supply network