MATH - I (Discrete), BCA Question Paper

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) ~ ( p∧ q) ∨ 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.