U.G. DEGREE EXAMINATION, NOVEMBER 2017
Information Technology
Allied: DISCRETE MATHEMATICS
(CBCS 2011 onwards)
Time 3 Hours Maximum 75 Marks
Part A (10 x 2 20)
Answer all questions.
1. What is compound statement? And give an example.
2. Show that the statement P^7P is a contradiction.
3. Define Conjunctive Normal Form of a statement.
4. Write the inference rules of hypothetical syllogism and
disjunction syllogism.
5. What is simple graph? And give an example.
6. Define circuit with an example.
7. What is meant by minimum spanning tree?
8. Define cut vertices with an example.
9. Define binary relation from one set to another and give
an example.
10. What is partial ordering? And give an example.
Sub. Code
1BITSA1/
1BIT1A1
AFC-10504
2
ws1
Part B x 5 25)
Answer all questions, choosing either or

Define conditional and biconditional statement.

12. Explain degree of a vertex with example.
Or
Explain isomorphism of two graphs with an
example.
14. Write Prim's Algorithm to find the minimum
spanning tree of a graph.
Or
Explain Hamiltonian graph with suitable example.
15. Draw the Hasse diagram for relation on
15}.
Or
State and prove isotonic property of lattices.
AFC-10504
3
ws1
Part C x 10 30)
Answer any three questions.
16. Explain the following term:
Negation Conjunction
17. Obtain the principal Conjunctive Normal Form of
V
18. Explain bipartite graph with suitable example.
19. Explain Dijkstra's Algorithm to find the shortest path
between a specified vertex to another specified vertex in a
graph.
20. Write the properties of Boolean Algebra.
————————