Home » ModelQuestions » KTU B.TECH S3 MODEL QUESTIONS CS201 Discrete computational structures

KTU B.TECH S3 MODEL QUESTIONS CS201 Discrete computational structures

KTU B.Tech s3 Model questions for Discrete  computational structures

MODEL QUESTION PAPER by ktubtechquestions.com


CS201 Discrete  computational structures

Time: 3 Hrs                                                                                                      Marks: 100


( Answer All Questions Each carries 3 Marks )


  1. Differentiate between a partition and Covering of a Set with an example.
  2. Give an example of an equivalence relation.
  3. State Principle of inclusion exclusion.
  4. 51 numbers are chosen from the integers between 1 and 100 inclusively .Prove that 2 of the chosen integers are consecutive


( Answer any TWO, Each carries 9 Marks )


  1. (a) For any two sets A and B Show that A – (A∩B) = A – B. (4 marks)

         (b)  Let R and S be two relations on a set of positive integers I.

R={ <x, 2x>/ xεI} S= { <x, 7x>/ xεI}   Find RoS, RoR, RoRoR, RoSoR. (5 marks)


  1. ( a) Explain Pigeon Hole Principle with example. (4 marks)

( b) Five friends run a race everyday for 4 months (excluding Feb). If no race ends in        a tie, show that there                      are at least 2 races with identical outcomes. (5 marks)

  1. (a) Let a0=1, a1= 2, a2 = 3. an= an-1+ an-2+ an-3 for n ≥ 3 Prove that an ≤ 3n

(5 marks)

         (b) Draw the Hasse Diagram of (P(A), ≤) where ≤ represents A ⊆ B and A ={ a, b, c } (5 marks)



( Answer All Questions Each Carries 3 Marks )

  1. Let (A,.) be a Group. Show that .
  2. List out the properties of a ring.

     10  Prove that the Zero element and Unit element of a Boolean algebra B are unique

  1. Simplify the following Boolean expression

                 (a ⋀ b ) ⋁c) ⋀ (a ⋁ b ) ⋀c)

       PART D

( Answer any TWO, Each carries 9 Marks )

  1. (a) Prove that in a distributive Lattice, if b ⋀ c = 0, then b≤ c. (5 marks)


(b) Show that a ⋁ b is the least upper bound of a and b in (A, ≤). Show that a ⋀ b is the greatest lower bound of                   a and b in (A, ≤).(4 marks)

  1. Let (H, .) be a subgroup of a Group (G, .) . Let N ={x/xε G, xHx-1 = H}. Show that (N, .) is a subgroup of (G, .).(9 marks)

     14 State and prove Lagrange’s Theorem. (9 marks)



( Answer any FOUR, Each carries 10 Marks )


  1. (a)Write the given formula to an equivalent form and which contains the connectives ⏋ and ⋀ only. ⏋ (P⇆ (Q→(R⋁P))) (3 marks)

        (b) Show that the following implication is a tautology without constructing the truth table

             ((P⋁⏋P) →Q) → ((P⋁⏋P)→R) ⇒ (Q→R) (3 marks)

       (c) Show that ( ⏋P⋀ ( ⏋Q⋀R)) ⋁ (Q⋀R) ⋁ (P⋀R) ⇔ R without constructing the truth table. (4 marks)


  1. Show that (x) (P(x) ⋁ Q(x)) ⇒ (x)P(x) ⋁ (∃x)Q(x) using Indirect method of Proof. (10 Marks)

    17 Discuss Indirect method of Proof. Show that the following premises are inconsistent.

(i) If Jack misses many classes through illness, then he fails high school.

(ii) If Jack fails high School, then he is uneducated.

(iii) If Jack reads a lot of books, then he is not uneducated.

(iv) Jack misses many classes through illness and reads a lot of books. (10 marks)

  1. (a) Show that

(i) (∃x) (F(x) ⋀ S(x)) → (y) (M(y) → W(y))

(ii) (∃y) (M(y) ⋀⏋W(y)) the conclusion (x)(F(x) →⏋S(x)) follows. (10 marks)

  1. (a) Show that S⋁R is tautologically implied by (P⋁Q) ⋀ (P→R) ⋀ (Q→S) (5 marks)

(b) Show the following implication using rules of inferences

           P→ (Q→R),Q→ (R→S) ⇒ P→ (Q→S) (5 marks)

  1. Give two translations of each of the following, one using a universal quantifier, and one using an existential quantifier.

(i)            All men are human

(ii)           No women like John

(iii)          [John likes some women

(iv)         Some woman likes John

(v)          Only women like John.

(vi)         Everyone is a man or a woman.

(vii)        Some humans are not men.

(viii)       If someone is a woman, she likes John. (10 marks)


©® ktubtechquestions.com

 Click here to download KTU B.Tech s3 Model questions Discrete  computational structures

12,182 total views, 5 views today


Check Also


KTU B.Tech S4 model Questions for Probability distributions, Transforms and Numerical Methods

KTU B.Tech S4 model Questions for Probability distributions, Transforms, and Numerical Methods ...


KTU B.Tech S4 ModelQuestions Fluid Mechanics-II

KTU B.Tech S4 Model Questions FLUID MECHANICS II KTU B.Tech S4 model ...