Get premium membership and access revision papers, questions with answers as well as video lessons.

Sce 207: Discrete Mathematics Question Paper

Sce 207: Discrete Mathematics

Course:Bachelor Of Information Technology

Institution: Kenyatta University question papers

Exam Year:2008

DATE: Thursday, 19th June, 2008
TIME: 8.00 a.m. – 10.00 a.m.
------------------------------------------------------------------------------------------------------------
INSTRUCTIONS:
Answer question ONE and any other TWO.
QUESTION 1
a)
If n??? = 37, ?
n ?
A
,
19
?
?
n B??23 and n? c
c
A ? B ? = 12, find ?
n A ? B?.

(4 marks)
b)
Simplify ?S ?T ?U ? c
S ?T ?U ?
c
S ?T ?

(4 marks)
c)
Let A?? ,
a ?
b and B?? ,
a ,
c d?.

Find B X A

(4 marks)
d)
Verify that the proposition ?p?q??~?p?q?is contradiction
(5 marks)
e)
Show that ~ ?p?q?? p ? p

(5 marks)
f)
Find a counter example for each statement where the universe

??? ,
3 ,
5 ,
7 ?
9 .

i)
? ,
x x?3?7

(2 marks)

ii)
,
x
? xis prim .
e

(2 marks)

2.
Find the adjacency matrix of the graph

(4 marks)

QUESTION 2
a)
In a class of 80 students, 50 students know English, 55 know French and 46 know
German language. 37 students know English and French, 28 students know
French and German, 25 students know English and German, 7 students know
none of the languages. Find out.
i)
How many students know all the 3 languages
ii)
How many students know exactly 2 languages
iii)
How many students know only one language.
(6 marks)
b)
Given the Venn diagram

Shade the following sets

i)
Ac ? ?B ? C?

2

ii)
c
c
C ?B ? A

iii)
A ?B?C?

iv)
Ac ??C B?

(8 marks)
c)
For the sets A and B, define A? B??A?B???A?B?.

Show that

i)
A? B? B? A

ii)
A? B ?Ac
?
n B?
iv)
What is A?? ?
(6 marks)

QUESTION 3
a)
i)
Show that p??q?r?and ?p?q???p?r? are logically equivalent
ii)
Show that ~q is logically implied by ~ ?p?q?? .
p
(7 marks)
b)
Simplify the following expressions:
??~ p? ~ q?? ~ r?? ??p ? q??r?

i)

?~?p ? q ? r???~ p? ~ q? ~ r?

ii)
??p ? q?? ~ p?? q

(7 marks)
c)
Test the validity of the following argument

If two sides of a triangle are equal, then the opposite angles are equal.

Two sides of a triangle are not equal

Conclusion: The opposite angles are not equal.

(6 marks)

3
QUESTION 4
a)
Find the adjacency and the incidence matrix of the graph

b)
The diagram below shows 3 vertices L, M and N and edges a, b, c, d, e and
regions I, II, III, and IV.

i)
Copy and complete the incidence matrices for the network shown:
? I II III IV ?
L ?
?
? 1 ?
0
? ?
X ? M ?
?
? ?
?
?
N ??
?
?
?? ?
?
? ?

? a b c d e ?
I ?
?
? 1 1 0 ? ??
II

?
?
Y ?

III ? ? ? ? ? ? ?
? ? ? ? ? ??
IV ?
?
? ? ? ? ? ??

4
? a b c d e ?
L ?
?
? 1 1 1 ? 0?

Z ? M ?
?
? ? ? ? ?
N ??
?
?
?? ? ? ? ??
ii)
Determine the matrix XY
iii)
If Z – XY = A, determine A.
c)
Compute the shortest distance and path from a to z in the graph

QUESTION 5
a)
Let D?? ,
1 ,
2 ,
3 ,
4 ,
5 ?
6 be ordered as shown below. Consider the subset
E ?? ,
2 ,
3 ?
4 of D.

5
i)
Find the upper bounds of E
ii)
Find the lower bounds of E
iii)
Does sup (e) exist? Does inf (E) exist?
iv)
Is D a lattice.
(7 marks)
b)
Consider the group G = ? ,
1 ,
2 ,
3 ,
4 ,
5 ?
6 under multiplication modulo 7.
i)
Find the multiplication table for G.
ii)
Find 2-1, 3-1, 6-1.
iii)
Find the orders and subgroups generated by 2 and 3.
iv)
Is G cyclic?
(7 marks)
c)
Consider the ring Z10= ? ,
1
,
0
,
2
,
? ?
9 of integers modulo 10.
i)
find –3, -8 and 3-1
ii)
Find the units of Z10
iii)
Can Z10 be a field? Give reasons.
(6 marks)

Sce 207: Discrete Mathematics Question Paper

More Question Papers

Popular Exams