D12609
D12609
FIRST SEMESTER
(CBCSSUG) DEGREE
EXAMINATION, NOVEMBER 2021
B.C.A.
BCA 1C 02 DISCRETE MATHEMATICS
(2021 Admissions)
Time: Two Hours Maximum 60 Marks
Section A
(Short Answer Type Questions)
Answer at least eight questions.
Each question carries 3 marks.
All questions can be attended.
Overall Ceiling 24.
1. Define contradiction.
2. Define dual of proposition. Write the dual of (P∧Q)vT
3. Show that -P ∧ P is a tautology.
4. Explain universal quantifier.
5.Define transitive relation. Show whether the relation R = (<1, 2>, <2, 3>, <1, 3>, <2, 1>} is transitive.
6. Define Boolean algebra.
7. Define minterm.
8. Define partially ordered set.
9. Define subgraph of a graph with an example.
10. Define Euler Graph.
11. Define isolated vertex of a graph. Give an example.
12. Define an m-ary tree.
(8 × 3 = 24 marks)
Section B (Short Answer Essay Questions)
Answer at least five questions.
Each question carries 5 marks.
All questions can be attended.
Overall Ceiling 25.
13. Prove distributive law in logic using truth table.
14. Show that P-> (Q-> R) ⇔ (P A Q) -> R using laws of logic.
15. Let X = {1, 2, 3, 4} If R = {<x, y>/x> y, x & y € X}.
(a) Write the elements of R and its matrix.
(b) Draw the digraph represents the relation.
16. Define equivalence class. Also write the equivalence classes modulo 3 generated by the elements of Z.
17. Show that the < P(X), ⊆> is a a partially ordered set, where X is any set and P(X) is the power set of A.
18. Define isomorphism between two graphs. Show that the following graphs are isomorphic.
19. Show that in complete binary tree the total number of edges is given by 2(ni - 1). Where ni is the number of terminal nodes.
(5 × 5 = 25 marks)
Section C (Essay Type Questions)
Answer any one question.
The question carries 11 marks.
20. Explain relation on a set. Also explain different types of relation on a set. Give examples for each
relation.
21. (a) Explain Travelling Salesman Problem.
(b) Explain Breadth-first search algorithm for spanning tree.
(1 x 11 = 11 marks)
നിങ്ങൾക്ക് ഉപകാരപ്പെട്ടെങ്കിൽ നിങ്ങളുടെ കൂട്ടുകാർക്ക് കൂടി ഷെയർ ചെയ്യുക
Share This
