ADCA / MCA (II Yr)
Term-End Examination
December, 2001
CS07: Discrete Mathematics
Time: 3 hours
Maximum Marks: 75
Note : Question No. 1 is compulsory. Answer any three questions from the rest.
1.
a. A = {1,2,4,5}, B = {a,b,c,f} and C = {a,5} are three given sets.
Compute (AUC) - (AUC) X B
Where 'U', '-', '?' and 'x' are well-known set-theoretic operations. (4)
b. Construct truth table for the following formula: (4)
7(PV7Q) <=> (P => Q)
c. Obtain the equivalent disjunctive normal form of the formula: 7R ∧ (P ⇔ R) (4)
d. Define the following concepts giving one example of each (4)
1.1-1 Onto function
2. Anti-symmetric relation on a set
3. Union of two fuzzy sets
4. Partial Order Relation
e. Define the following concepts from Graph theory, with an example for each:
1. Spanning subgraph of a graph
2. Eccentricity of a vertex of a graph
3. A full binary tree
4. A Hamiltonian Path in a graph
f. Draw a Hasse diagram for the relation {P{a,b,c} ⊇, where P {a,b,c}denotes the power set of {a,b,c} and '⊇' denotes the relation of containment in sets. (3)
g. A graph G has the following adjacency matrix. Check whether it is connected.
0 0 1 0
A(G) = 0 0 0 1
0 1 0 0
0 0 1 1
h. Define the following concepts with one example for each:
i. Bounded lattice
ii. Distributive lattice
iii. min-term in a Boolean Algebra
iv. 2's complement of a binary number
2.
a. Determine the validity of the conclusion (represented by 'C:') from the given set of premises (4)
P -> ~Q, P ∨ R, ~R ∨ ~S, S with conclusion C: ~Q
b. Show that theset {7, →} of operators is a complete set of operators.
c. Find equivalent form in Predicate/Propositional Calculus of the following statements:
i. Nine plus ten equal nineteen.
ii. Some patients like all doctors.
iii. Any integer is either positive or negative.
iv. Every integer is also a real number.
3.
a. Draw the graph having the following matrix as its adjacency matrix:
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
6.
a. Using either Breadth First Search Algorithm or Dijkstra's algorithm, find the shortest path from s to t in the following weighted path: (6)
