Download AKTU B-Tech 3rd Sem 2018-2019 Discrete Structures And Theory Of Logic Rcs 301 Question Paper

Firstranker's choice

www.FirstRanker.com

Paper Id: 110301

--- Content provided by FirstRanker.com ---

www.FirstRanker.com

Roll No.

Time: 3 Hours

B. TECH.

(SEM III) THEORY EXAMINATION 2018-19

--- Content provided by‌ FirstRanker.com ---

DISCRETE STRUCTURES AND THEORY OF LOGIC

Total Marks: 70

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

2. Any special paper specific instruction.

SECTION A

--- Content provided by‌ FirstRanker.com ---

1. Attempt all questions in brief. 2 x 7 = 14

1. Find the power set of each of these sets, where a and b are distinct elements.
   1. {a}
   2. {a, b}
   3. {0, {0}}
   4. {a, {a}}

   --- Content provided by‍ FirstRanker.com ---

2. Define Ring and Field.
3. Draw the Hasse diagram for D30.
4. What are the contrapositive, converse, and the inverse of the conditional statement "The home team wins whenever it is raining?"
5. How many bit strings of length eight either start with a '1' bit or end with the two bits '00'?

--- Content provided by⁠ FirstRanker.com ---

6. Define Injective, surjective and bijective function.
7. Show that (p V q) and p^q are logically equivalent.

SECTION B

Attempt any three of the following:

2. A total of 1232 student have taken a course in Spanish, 879 have taken a course in French, and 114 have taken a course in Russian. Further, 103 have taken courses in both Spanish and French, 23 have taken courses in both Spanish and Russian, and 14 have taken courses in both French and Russian. If 2092 students have taken at least one of Spanish, French, and Russian, how many students have taken a course in all three languages?

--- Content provided by FirstRanker.com ---

3. (i) Let H be a subgroup of a finite group G. Prove that order of H is a divisor of order of G.
   (ii) Prove that every group of prime order is cyclic.
4. Define a lattice. For any a, b, c, d in a lattice (A, =) if a = b and c = d then show that a = b and c = d then show that a = b and c = d.
5. Show that ((p?q)^~(~p^ (~qv~r))) v (~p^~q) v (~p vr) is a tautology without using truth table.
6. Define a Binary Tree. A binary tree has 11 nodes. It's in order and preorder traversals node sequences are:
   

   --- Content provided by‌ FirstRanker.com ---

   Preorder: A BDHIEJKCFG
   In-order: HDIBJEKAFCG
   Draw the tree.

www.FirstRanker.com

SECTION C

--- Content provided by‍ FirstRanker.com ---

Attempt any one part of the following: 7x1=7

3. (a) Prove that if n is a positive integer, then 133 divides 11ⁿ⁺¹ + 12^2n-1
   (b) Let n be a positive integer and S a set of strings. Suppose that R_n is the relation on S such that s R_n t if and only if s = t, or both s and t have at least n characters and the first n characters of s and t are the same. That is, a string of fewer than n characters is related only to itself; a string s with at least n characters is related to a string t if and only if t has at least n characters and t begins with the n characters at the start of s.
   What is the equivalence class of the string 0111 with respect to the equivalence relation R.

Attempt any one part of the following: 7x1=7

--- Content provided by‍ FirstRanker.com ---

4. (a) Let G= {1, -1, i, -i} with the binary operation multiplication be an algebraic structure, where i=v-1. Determine whether G is an Abelian or not.
   (b) What is meant by a ring? Give examples of both commutative and non-commutative rings.

Attempt any one part of the following: 7x1=7

5. (a) Show that the inclusion relation is a partial ordering on the power set of a set S. Draw the Hasse diagram for inclusion on the set P (S), where S = {a, b, c, d}. Also Determine whether (P(S), =) is a lattice.
   (b) Find the sum-of-products and Product of sum expansion of the Boolean function F (x, y, z) = (x + y) z'.

--- Content provided by⁠ FirstRanker.com ---

Attempt any one part of the following: 7x1=7

6. (a) What is a tautology, contradiction and contingency? Show that (pVq) ? (pV r)?(q V r) is a tautology, contradiction or contingency.
   (b) Show that the premises "It is not sunny this afternoon and it is colder than yesterday," "We will go swimming only if it is sunny," "If we do not go swimming, then we will take a canoe trip," and "If we take a canoe trip, then we will be home by sunset" lead to the conclusion "We will be home by sunset."

Attempt any one part of the following: 7x1=7

7. (a) What are different ways to represent a graph. Define Euler circuit and Euler graph. Give necessary and sufficient conditions for Euler circuits and paths.
   

   --- Content provided by‍ FirstRanker.com ---

   (b) Suppose that a valid codeword is an n-digit number in decimal notation containing an even number of 0's. Let a_n denote the number of valid codewords of length n satisfying the recurrence relation a_n = 8a_n-1 + 10^n-1 and the initial condition a₁ = 9. Use generating functions to find an explicit formula for a_n.