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

Discrete Structure Question Paper

Discrete Structure

Course:Bachelor Of Computer Science (It Telecommunication)

Institution: Kabarak University question papers

Exam Year:2010

Page 1 of 6
KABARAK UNIVERSITY
UNIVERSITY EXAMINATIONS
2010/2011 ACADEMIC YEAR
FOR THE DEGREE OF BACHELOR OF COMPUTER
SCIENCE
COURSE CODE: COMP 122
COURSE TITLE: DISCRETE STRUCTURE
STREAM: Y1S2
DAY: WEDNESDAY
TIME: 9.00 – 11.00 A.M
DATE: 08/12/2010
INSTRUCTIONS:
NOTE: - PART-A is compulsory, have30 marks and from PART-B ,you can attempt any two
question. Each question has 20 marks.
PLEASE TURNOVER
Page 2 of 6
PART-A
QUESTION 1
a) Rewrite the following statements using set notation:
i) the element 1 is not a member of A
ii) A is a subset of C
iii) F contains all the elements of G. (3Marks )
b) List the elements of the following sets; here N= {1, 2, 3 ……}.
i) A = { x: x ÎN, 3<x<10}
ii) B = { x: x ÎN, x is even, x<11}
iii) C = { x: x ÎN, 4+x = 3}
iv) A = { x: x ÎN, x2 + 1 = 10}
v) B = { x: x ÎN, x is odd, -5 < x < 5} (5Marks )
c) Let A = { x: 3x = 6}.Explain does A = 2? (2Marks)
d) Which of these sets are equal: {r,s,t}, {t,s,r}, {s,r,t}, {t,r,s}? (2Marks)
e) Consider the sets:
{4,2}, {x: x2 -6x + 8=0}, {x: xÎN, x is even, 1<x<5}.
Which of them are equal to B = {2,4}? (2Marks)
f) Construct logic networks for the following Boolean expressions, using AND gates, OR gates,
and inverters.
( x + y)z (2Marks )
g) Explain the difference between AÍB and AÌB. (2Marks)
h) Show that A = {2,3,4,5} is not a subset of B= {x: xÎN, x is even}. (2Marks)
i) Suppose A = {x,y,z}. Find A2 (2Marks)
j) A group consists of nine men and six women. Find the number ‘M’ of committees of six that
can be selected from the class. (2Marks)
k) Verify that the proposition pÚ (p Ù q) is not tautology. (2Marks)
l) Determine the power set P (A) of A= {1, 3, 5} (4Marks)
Page 3 of 6
PART B
Question 2
a) List five elements of each of the following sets.
(i) {nÎN : n is divisible by 5}
(ii) {1/n : n Î P}
(iii) {n ÎN : n+1 is prime} (3Marks )
b) Suppose that A= {1,2,3,4}, B= {2,3,4,5,6,7}, C= {3,4}, D= {4,5,6}and E= {3}
1. Which of the five sets can equal X if XÍA and XÍB?
2. Which of the five sets can equal to X if XËD and XÍC?
3. Find the smallest set M which contains all five sets.
4. Find the largest set N which is a subset of all the five set. (4Marks)
c) Let A = {n Î N: n £ 20}.determine the following sets, i.e., list their elements if they are
nonempty, and write f if they are empty.
i. {n Î A : 4/n}
ii. {n Î A : max {n,4} = 4} (2Marks )
d) Draw a Venn diagram of sets X, Y, Z where XÍY, sets X and Z are disjoint, but Y and Z have
elements in common. (2Marks)
e) Suppose A= {1,2,3,4}, B={2,4,6,8}, and C={3,4,5,6}.Prove that:
(AÈB)ÈC = AÈ(BÈC) (4Marks )
f) Determine which of the following sets are finite.
(i) A={Months in a year}
(ii) B= {days in march}
(iii) C={+ve integers less than 1} (3Marks )
g) Let R be the relation on A={x,y,z,p} defined by:
R = {(x,x),(x,y),(y,x),(y,p),(z,z),(z,p),(p,x),(p,y),(p,z)} and
S = {(x,x),(y,p),(z,z),(z,p),(p,y)}
Find the composition Ro S from the relations (2Marks)
Page 4 of 6
Question 3
a) Suppose U={1,2,3,……..8,9},A= {1,2,3,4}, B={2,4,6,8}, and C={3,4,5,6}.
Find
i. A
c
ii. B
c
iii. A\B
iv. B\B (4Marks )
b) The two directed graphs that follow have relations r and s . Draw the graphs associated with
the relations r Ès and r Çs
1 1
2 3 2 3
(4Marks )
c) Prove the commutative laws: (i) AÈB=BÈA and (ii) AÇB=BÇA
(2Marks)
d) Prove x + y = x + ( x . y + x.y ) (2Marks )
e) Prove that x Å y = y Å x (2Marks)
f) Translate each of the following statements in to a Venn diagram.
(i) all students are lazy
(ii) Some students are lazy. (2Marks )
g) Given A = ? ?
?
?
? ?
?
?
-
-
4 3
1 2
and B = ? ?
?
?
? ?
?
? -
5 4
2 1
. Find (AB)T (2Marks )
h) Find the number of distinct permutations that can be formed from all the letters of each word
“THREE” (2Marks)
Question 4
a) Find the number of elements in the finite set:
(i) A={4,6,8,10}
(ii) B={x: x3 = 9}
(iii) C={x: x2< x + 3} (3Marks )
Page 5 of 6
b) One hundred students were asked whether they had taken courses in any of the three areas,
sociology, anthropology, and history. The result was:
40 had taken sociology
30 had taken anthropology
19 had taken history
18 had taken sociology and anthropology
9 had taken sociology and history
5 had taken history and anthropology and
4 had taken all courses.
(i) Draw a Venn diagram that will show the results of the survey. (5Marks)
(ii) Determine the number k of students who had taken classes in exactly (1) one of the areas, and
(2) two of the areas. (2Marks)
c) Find the adjacency matrix and adjacency relation for the graph in figure.
1
2 3 (3Marks)
d)Let R be the relation from A = {1, 2, 3, 4} to B = {x, y, z} defined by
R = {(1, y), (1, z), (3, y),(4, x),(4, z)}
Determine the domain and range of R (2Marks)
e) Let R be the relation on A = {1, 2,3,4,5} described by the directed graph in the fig. write R as a
set of ordered pairs. (2Marks)
1 2 3
4 5
f) Consider a relation S from X = {1,2,3} to Y = {a,b,c,d} whose matrix representation is
a b c d
M =
3
2
1
? ? ?
?
?
? ? ?
?
?
1 0 1 1
0 1 1 0
0 0 1 1
(3Marks)
Page 6 of 6
Question 5
a) Describe the “ arrow diagram” of a relation R from a finite set A to a finite set B. Illustrate
using the relation R from set A ={1,2,3,4} to set B = {x,y,z}defined by
R = {(1,y),(1,z),(3,y),(4,x),(4,z)} (2Marks )
b) Consider the following three relations on the set A= {1,2,3}:
R= {(1,1),(1,2),(1,3),(3,3)}
S = {(1,1),(1,2),(2,1),(2,2),(3,3)}
T = AXA
(i) Determine which of the relations are reflective.
(ii) Determine which of the relations are symmetric.
(iii) Determine which of the relations are transitive. (3Marks)
c) Functions f: A®B, g: B®C
Find the composition function h o g (3Marks)
? ? ?
?
?
? ? ?
?
?
c
b
a
? ? ?
?
?
? ? ?
?
?
z
y
x
? ? ?
?
?
? ? ?
?
?
t
s
r
A f B g C
d) Prove the associative law: (p Ù q) Ù r ºp Ù (q Ù r) (4Marks )
e) Use a K-map to find the prime implicants and minimal form for each of the following complete
sum-of-products Boolean expressions.
E1=x.y.z + x.y. z + x. y .z + x .y.z + x . y .z (3Marks)
f) Design a three-input minimal AND-OR circuit L that will have the following truth table:
T= [A=00001111, B= 00110011, C= 01010101, L= 11001101
(3Marks)
g) A student is to answer eight out of ten questions on an exam. Find the number m of ways that
the student can choose the eight questions. (2Marks)

Discrete Structure Question Paper

More Question Papers

Popular Exams