Discrete Structure : End Semester Examination ( 3rd Sem )

Discrete Structure

End Semester Examination, 2021-22
B. Tech - Semester : 03
Time : 03 hrs. - Max. Marks : 100

Instructions:

1. All questions are Compulsory
2. Assume missing data suitably, if any.

Section : A ( 10 x 4 = 40 Marks )

All questions are compulsory

1. Given set A = { 1,2,3,4 } and B = { x,y,z }. Let R be the following relation from A to B, R = { (1,y), (1,z), (3,y), (4,x), (4,z) }
   a. Determine the matrix of the relation.
   b. Find inverse R^-1 of R.
   c. Determine the domain and Range of R.
2. Let f: R->R ang g: R->R, where R is the set of real numbers. Find fog and gof, where f(x) = x²-4 and g(x) = x+4. State where these functions are injective, surjective and bijective.
3. Construct the truth table for each of the following compound statement.
   i. (p <--> q) V (~p <--> r) 
   ii. (~p<-->q) <--> (p <-->r)
4. Use mathematical induction to show that
   1+2+2²+...+2ⁿ = 2ⁿ⁺¹ - 1, for all non-negative integers n.
5. Verify absorption law with the help of truth table.
6. Explain Ring and Field with suitable example.
   
7. Using the law of Boolean algebra prove that
   ( A+B )( A+C ) = A+BC
8. Apply DeMorgan's theorems to each of the following expressions.
   a. ( A+B+C)D 
   b. ABC+DEF
   
9. Define and explain the following :
   i) Binary search tree, ii) Bipartite graphs.
10. Find the all Least Upper Bounds (LUB) and all Greatest Upper Bounds (GUB) of 
    i) {c,d,e}, ii) {a,b} for the given figure.
    
    
    
    
    

Section : B ( 3 x 6 = 18 Marks )

All questions are compulsory

1. State which of the following propositional statement is Tautology/ Contingency/ Contrdiction.
   i. ( P^Q ) -> ( QvR )
   ii. ( p->(QvR)) -> ((P^Q)->R))
   iii. ((P->Q) ^ (Q->R) ^ R)) -> (~P)
   
   OR
   Write the converse, Inverse and contrapositive of the following:
   i. "If P is Cube then P is 3D."
   ii. If the flood destroy my house then my insurance company will pay me.
2. Define the following terms with an example.
   i. Graph, ii. Self loop, iii. Regular graph
   
   OR
   Find the In order, Pre Order and Post Order of Binary tree.
   
   
   
   
   
3. Consider the Poset A = ({1,2,3,4,6,9,12,18,36}, | ). Draw the Hasse diagram and find the GLB & LUB of the sets {6,18} & {4,6,9}. ( | denotes divide relation i.e. a|b is a divides b).
   

   OR

   Discuss Poset. Show that "less than or equal to" relation on a set of real number is partial ordering.

Section : C ( 3 x 10 = 30 Marks )

All questions are compulsory

1. Given the In Order and Post Order traversal of a tree T:
   In Order : BEHFACDGI
   Post order : HFEABIGDC. Determine the tree T and its pre order.
   
   OR
   Define complemented lattice. Determine whether the poset shown in figure-1 and figure-2 is complemented lattice or not.
   
   
   
   
   
2. Convert each of the following Boolean expressions to sop form:
   i. AB+B(CD+EF) , ii. (A+B)(B+C+D)
   

   OR

   Minimize the following Boolean function
   F(A, B, C, D) = Σm(0,1,2,5,7,8,9,10,13,15)
3. Discuss the pigeon hole principle. Show that among all 80 students in our class, 7 or more are born in the same month.
   

   OR

   Solve the recurrence relation Fn=10F_n-1-25F_n-2, where F0 = 3 and F1 = 17.

Section : D ( 1 x 12 = 12 Marks )

All questions are compulsory

1. Define isomorphism. Determine whether the following pair of graphs are isomorphic.
   
   
   
   OR
   

   Find the Hamiltonian path and Hamiltonian cycle, if it exists. Also identify the Euler's circuit.
   
   

   

   
   
   
   

*******************