DISCRETE MATHEMATICS:

Question 1

(a) Use truth tables to determine if the given compound proposition is a tautology.

(b) Determine if the compound propositions and are logically equivalent.

(c) Use quantifiers to rewrite the given statements. If the statement is true, provide a short
proof. If the statement is false, provide a counterexample.

For every real , for some real ,

Solution:

1. (a)

T T T T T T T T
T T F T F F F T
T F T F T F T T
T F F F T F F T
F T T T T T T T
F T F T F F T T
F F T T T T T T
F F F T T T T T
So tautology.

(b)

T T T F F F
T F F T T T
F T F T F T
F F T F T F
So logically equivalent.

(c)

False. is a counterexample.
Question 2

(a) Test the validity of the following argument.

When I play cricket I am sore.

(b) Use mathematical induction to prove that

for .

Solution(a) Let p : I play cricket , q: I am sore, r: I use a hot bath.

T T T T T F
T T F T F T
T F T F T F
T F F F T T
F T T T T F
F T F T F T
F F T T T F
F F F T T T
(b) When So true for .

Assume true for

When

So true for . Hence true by induction.

(a) Use mathematical induction to prove that is a multiple of 3 for .

(b) (i) Write down the first four terms of the recurrence relation

(ii) Solve the recurrence relation given in part (i).

(a) When which is a multiple of 3. So true for .

Assume true for i.e. is a multiple of 3.

When

So true for . Hence true by induction.

(b) (i)

(ii) The auxiliary equation is

So

to solve to get .

So
Question 4

(a) Consider the relation on

(i) reflexive,
(ii) symmetric,
(iii) transitive
(iv) an equivalence relation.

You should justify your answers.

(b) There are 9 lecturers in the mathematics department and 11 lecturers in the computer
science department. A committee is to be selected to develop a discrete mathematics
course. The committee should consist of three lecturers from the mathematics department
and four lecturers from the computer science department. In how many ways can the
committee be selected?

(c) How many permutations of the letters ABCDEFGH contain the word CAB?

Solution:

4. (a) (i) Yes.

(ii) Yes.

(iii) No.

(iv) No. R is not transitive.

(b) Number of ways .

(c) Number of ways .

(d) Number of ways

(a) Find the output of the given combinatorial circuit.

(b) Construct a circuit from inverters, AND gates, and OR gates to produce the output

Solution:

5. (a)

(b)

(c) Convert the hexadecimal number to

(i) binary
(ii) octal

Solution: (i)

(ii)