## MATH - I (Discrete), BCA Question Paper

• Sunday, September 30, 2012

punjabtechnicaluniversity.blogspot.in

Total No. of Questions : 13]                                                         [Total No. of Pages : 03
Paper ID [A0208]
BCA (203) (Old) / (S05) (Sem. - 2nd)
B.Sc. IT (202) (New)
C

Time : 03 Hours                                                                              Maximum Marks : 75
Instruction to Candidates:
1) Section - A is Compulsory.
2) Attempt any Nine questions from Section - B.

Section - A
Q1)                                                                                          (15 x 2 = 30)
a) Define inverse relation with example.
b) Define into and onto functions.
c) Prove A B = B A.
d) Draw venn diagram for the symmetrical difference of sets A and B.
e) Define partition of a set with example.
f) Form conjuction of p and q for the following:
p : Ram is healthy, q : He has blue eyes.
g) If p : It is cold, q : It is raining, write the simple verbal sentence which describe (i) p q (ii) p~ q.
h) Define logical equivalence.
i) Prove that proposition p~ p is tautology.
j) Define Biconditional statement.
k) Define undirected graph with example.
l) Edge of a graph that joins a node to itself is called? And Edges joins node by more than one edges are called?
m) Define Null graph with example.
n) Does there exist a 4 - regular graph on 6-vertices, if so construct a graph.
o) Prove V (G1 G2) = V(G1) V (G2) with example.

Section - B
(9 x 5 = 45)
Q2) Let R = {(1, 2), (2, 3), (3, 1)} and A = {1, 2, 3}. Find Reflexive, symmetric, and transitive closure of R using composition of relation R.
Q3) If f : A B and g : B C be functions, then prove
(a) If f and g are injections, then gof : A C is an injection.
(b) If f and g are surjections then so is gof.
Q4) Prove that A – (B C) = (A – B) (A – C).
Q5) Show that set of real numbers in [0, 1] is uncountable set.
Q6) A man has 7 relatives, 4 of them are ladies, and 3 are gentlemen, his wife has 7 relatives and 3 of them are ladies and 4 are gentlemen. In how many ways can they invite a dinner party of 3 ladies and 3 gentlemen so that there are 3 man’s relatives and 3 of wife relatives.
Q7) Using truth table show that ~ ( p q) (~ p) (~ q).
Q8) Consider the following:
p : It is cold day, q : the temperature is 50°C
write the simple sentences meaning of the following:
(a) ~ p (b) p q (c) ~ ( p q) (d) ~ p~ q (e) ~ (~ p~ q)

Q9) Prove that following propositions are tautology.
(a) ~ ( pq) q (b) p( p q)
Q10)Show that two graphs shown in figure are isomorphic.
Q11)Prove a non-empty connected graph G is Eulerian if and only if its all vertices
are of even degree.
Q12)Define graph coloring and chromatic number with two examples of each.
Q13)Prove a simple graph G has a spanning tree if and only if G is connected.