**KTU B.Tech s3 Model questions for Discrete computational structures**

**MODEL QUESTION PAPER by ktubtechquestions.com**

**THIRD SEMESTER B.TECH DEGREE EXAMINATION DECEMBER 2016**

**CS201 Discrete computational structures**

**Time:** **3 Hrs Marks: 100**

__PART A__

( Answer All Questions Each carries **3 Marks **)

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

__PART B__

( Answer **any TWO**, Each carries **9 Marks **)

**(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)**

**( 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)**

**(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)**

__PART C__

( Answer All Questions Each Carries **3 Marks** )

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

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

- Simplify the following Boolean expression

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

__PART D__

( Answer **any TWO**, Each carries **9 Marks **)

**(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)**

- 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)**

__PART E__

( Answer **any FOUR**, Each carries **10 Marks **)

- (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)**

- 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)**

- (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) **

**(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)**

- 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**

**Discrete computational structures**