DISCRETE MATHEMATICS QUESTIONS

Unit –Wise Descriptive Questions

Unit-1

1.   Determine the Principal Disjunctive Normal Form(PDNF) of the formula

                      P→{(P→Q) Λ¬ (¬QV¬P)}

2.   Prove the logical equivalences for the given formula:

              (¬PΛ(¬QΛR))V(QΛR)V(PΛR) ÛR

3.   Construct the truth table for the following formula

                (PΛQ) V (¬PVQ) V (PV¬Q) V (¬PV¬Q)

4.   Obtain Conjunctive Normal Form (CNF) of the formula

       [Q V (P Λ R)] Λ ¬ ((P VR) ΛQ)

5.   Prove the following logical equivalences without using truth tables:

               (p®q) Λ[¬q Λ (r V ¬q)] Û¬(qVp)

6.      Show that RVS is logically valid from the following premises.

                CÚD, (CÚD) →¬H, ¬H→ (AÙ¬B) and (AÙ¬B) →RÚS.

7.   Obtain the PCNF and PDNF of the formula (¬P→Q)  (QP).

8.   Determine whether the conclusion C logically follows from the premises H₁ and H₂:

i)                    H₁= P®Q,  H₂ = ¬(P ΛQ),  C = ¬P  

ii)                  H₁= ¬P,  H₂ = PQ,  C = ¬(P ΛQ)

9.   Verify the principal of duality for the following logical equivalence:

[¬(PÙQ) → ¬PÚ(¬PÚQ)] Û (¬PÚQ)

10. Let p,q and r be propositions having truth values 0 and 1 respectively. Find the truth values of the following:

           i) (p V q) V r      ii) (p Λ q) Λ r     iii) (p Λq) ®r

          iv) p®(q Λ r)       v) p Λ (r®q)      vi) p®(q®¬ r)

11. Identify the Principal Disjunctive Normal Form(PDNF) of the

                   P→{(P→Q) Λ¬ (¬QV¬P)}

12. Show that SVR is tautologically implied by

              (PVQ),  (P →R), (Q→S)

Unit-2:

1.   Let A={a,b,c,d} and R be a relation on A that has the matrix

                      

Draw the digraph of R and list the in-degree and out-degree of all

vertices.

2.Let A={1,2,3,4} and R={(1,1),(1,2),(2,1),(2,2),(3,4),(4,3),(3,3),(4,4)} be relation on A. Verify whether R is an equivalence relation.

3. Explain about following properties on relations with examples:

i) Reflexive     ii) Transitive       iii) Symmetric  

4. Let A={1, 2, 3, 4, 6, 12}. On A, define the relation R by aRb if and only if a divides b. Prove that R is a partial order relation on A. Draw the Hasse diagram for this relation.

5. If A={1,2,3,4} and R,S are relations on A defined by R={(1,2), (1,3), (2,4), (4,4)}   S={(1,1), (1,2), (1,3), (1,4), (2,3), (2,4)} find  RoS, SoR,R²,S² and write down their matrices.

6. From set A={1,2,3,4} & R={(1,1),(1,2),(2,2),(2,4),(1,3),(3,3),(3,4),(1,4),(4,4)} Verify that R is a partial order on A. also write down the Hasse diagram for R.

7. Let A= {1,2,3,4} and R be the relation on A defined by xRy if and only if “x divides y”. Then find relation R, Digraph of R and Matrix of R. and also find in-degree and out-degree of each node in digraph.

8. Assume A={1,2,3,4} and f and g be functions from A to A given by f={(1,4),(2,1),(3,2),(4,3)} and g={(1,2),(2,3),(3,4),(4,1)}. Prove that f and g are inverse of each other

9. Consider the functions f and g defined by f(x)=x³ and g(x)=x²+1, for all   x ∈R. Find g o f, f o g, f² and g².

10. For A={a, b, c, d, e}, the Hasse diagram for the poset(A,R) is shown below, determine the relation matrix  and  Digraph for R  

                             

11.If A={1,2,3,4} and R is a relation on A defined by R={(1,2), (1,3),(2,4), (3,2), (3,3), (3,4)}, find  M(R) , M(R²), M(R³). Verify that M(R²) = [M(R)]² and M(R³)=[M(R)]³.

12. If U={1,2,3,4,5,6,7,8,9}, A={1,2,4,6,8} and B={2,4,5,9} then compute the following

   i) A1     ii) A¹ U B¹      iii) (A∩B)¹     iv) AΔB

Unit-3

1.   Check whether the graph is Eulerian graph or not. Explain.

           

2.   For a planar graph shown below, find the degrees of regions and verify whether the sum of these degrees is equal to twice the number of edges.

         

       

 

3.   Using Prims algorithm find a minimal spanning tree for the weighted graph given below

                         

4.       Define complete graph? Which of the following are complete graphs? Justify your answer.

	A bb
			B bb				V bb
					U bb

 

 

			C bb
	D bb
							X bb
					Y bb

 

5.   Which graph shown in following figure have Euler path? Justify your answer.

                      G1                                                                 G2

6.   Using Kruskal’s algorithm find a minimal spanning tree for the weighted graph given below.

   .

7.   Check whether the following graphs G1 and G2 are isomorphic.

              G1                                                G2

8.   Consider the graph G(V,E) in given figure:

(a)  Describe G formally.

(b)  Find the degree and parity of each vertex

(c)  Verify that sum of degrees of the vertices of a graph is equal to twice the number of edges.

 

9.   Show that the following graphs are Isomorphic

                      G1                                    G2

10.Decide which of the following graphs are Eulerian or Hamiltonian or both and write down as Euler circuit and Hamiltonian circuit whenever possible.

     

11.Using Prims algorithm find a minimal spanning tree for the weighted graph given below:

12. Define the following terms with example each:

(a)  K3    (b) planar Graph     (c) Trail    (d) 3-regular

Unit-4

1. Identify the number of integers <500 and divisible by 9 or 11or 13.

2.  In how many ways can 6 men and 6 women be seated in a row

             i) if any person may sit next to any other.

             ii) if men and women must occupy alternate seats.

3. Prove that the set G={1, -1, i, -i} is an abelian group w.r.t Multiplication. Is it cyclic?  

4.Discover the coefficient of

i) x⁴y² in the expansion of (3x+2y)⁶.

                   ii) x²y⁴z⁶ in the expansion of (2x-3y+2z)¹²

5. Identify the coefficient of

 i) x³y⁶ in the expansion of (2x-5y)⁹.

                   ii) x²y⁴z⁶ in the expansion of (5x+2y-4z)¹².

6. Find the number of distinguishable permutations of the letters in the following words:

i)STRUCTURES     ii) ENGINEERING

7. Let G={0,1,2,3,4,5}

i. Prepare composition table with respect to +₆

ii. Prove that G is an abelian group  with respect to +₆

iii. Find the inverse of 2,3 and 5

iv. Is it cyclic?

v. Find the order of elements 2 and 3

8. For Z₇ - {0}

i. Prepare composition table with respect to x₇

ii. Prove that G is an abelian group  with respect to x₆

iii. Find the inverse of all the elements set.

iv. Is it cyclic?

v. Find the order of elements 2 and 4

9. Calculate the number of integers <500 and divisible by 3 or 5 or 11.

10. Find the number of permutations of the letters of the word MASSASAUGA. In how many of these, all four A’s are together? How many of them begin with S?

 

Unit-5

1. Solve the Recurrence Relation a_n=6a_n-1-12a_n-2+8a_n-3  for n ≥3, with a₀=1, a₁=4, a₂=28

2. Determine the coefficient of

           i) x¹² in x³(1-2x)¹⁰      ii) x²⁷ in (x⁴ + x⁵  + x⁶ +……)⁵ 

3. Find the sequence generated for the following function (3+x)³

4. Solve the Recurrence Relation a_n=3a_n-1-2a_n-2  for n≥2 with a₁=5, a₂=3

5. Determine the generating function for the recurrence relation:

a_{n+1 -} a_{n =} 3ⁿ , n≥0 with a₀=1 

6. Evaluate the sequences generated by the following functions:

i)(1+3x)^-1/3       ii) 3x³+e^2x 

7. Construct the generating function for the following sequences:

i)             1,1,0,1,1,1,…..

ii)           1,-2,3,-4,….

8. Solve the Recurrence Relation a_n+a_n-1-8a_n-2-12a_n-3=0 for n≥3, with a₀=1, a₁=5, a₂=1

9. Evaluate a generating function for the recurrence relation

             a_n+1- a_n = n², n>=0 and a₀=1. Hence solve the relation

10. Determine the coefficient of

i)             X⁰ in (3X² - (2/X))¹⁵

ii)           X⁵ in (1-2X)^-7

11. Solve the Recurrence Relation of 2a_{n+3 =} a_n+2+2a_n+1-a_n, n≥0, with a₀=0, a₁=1, a₂=2.

12. Construct the sequence generated by the following function:  (1+3X)^-1/3