Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2018-2019 Discrete Structures And Theory Of Logic Rcs 301 Question Paper
Paperld=IIl1EEll RollNo-1 1T1 14 I 1 l I 1
B. TECH.
(SEM III) THEORY EXAMINATION 2018-19
DISCRETE STRUCTURES AND THEORY OF LOGIC
T ime: 3 Hours T otal Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper speci?c instruction.
SECTION A
I. Attempt all questions in brief. 2 x 7 = 14
a. F ind the power set of each of these sets, where a and b are distinct elements.
i) {3} ii) {21, 13} iii.) {0, {6}} W) {3, {3}}
b. De?ne Ring and F ield.
Draw the Hasse diagram for D30
no
What are the contrapositive; converse, and the inverse of the conditional
statement ?The home team wins whenever it is raining?
c How many bit strings of length eight either stanmth a 1 bit or end With the
two bits ?00 '-?
, De?ne lnjective surjective and b1jecti1?e ?111ction.
g. Show that (p V q) and p A q am ically equivalent.
SEI?TION B
2. Attempt any three of the folfowmg N 1 7 x 3? ? 21
a. A total 01 1232 SW1 have taken a course 111 Spanish 879 have taken a course
in French, and 114? have taken a course in Russian.1111?1h_er. 10.3 have taken
courses in b12111; Spanish and French 23 have taken c0111$es in both Spanish and
Russian, and 14 have taken courses in both Frgrich and Russian 1f 2092
students have taken at least one of Spanish. French, and Russian, how many
students have taken a course in all three language?
h. (i) Let H be a subgroup of a ?nite group G Prove that order of H is a divisor
of order of G
(11) Prove that every group 01 prif?e order 15 cyclic.
C. De?ne a lattice. For anya. 11.1; d in a1attice (A, S) if a Sb and c S d then
showthata v csb v dahdfa A c S b A d.
(1. Show that((pvq) A~ (~p A (~q v~r))) v (~p A~q) v ( p vr) is atautology
without using truth table
e. De?ne a Binary Tree. A binary tIee has 11 nodes. It?s in order and preorder
traversals node sequences are:
Preorder:ABDHIEJKCFG
In-order: HDlBJEKAFCG
Draw the tree.
SECTION C
3. Attempt any one part of the following: 7 x 1 = 7
(a)
(b)
Prove that ifn is a positive integer, then 133 divides ll"+1 + 121?".
Let n be a positive integer and S a set of strings. Suppose that R. is the relation
on S such that s Ru t if and only if s = t, or both 5 and t have at least 11 characters
and the ?rst 11 characters of s and t are the same. That is, a string of fewer than
11 characters is related only to itself; a string 5 with at least 11 characters is
related to a string t if and only if t has at least 11 characters and t begins with the
11 characters at the start of 5.
What 1s the equivalence class of the stung 0111 with respect to the equivalence
relation R,
4. Attempt any one part of the following: 7 x l = 7
(a)
(b)
5. Attempt any one part of the following:
Let G = {1, -l, i, -i} with the binary operation multiplication be an algebraic
structure, where i =\/?_1?. Determine whether G is an Abelian or not.
What is meant by a ring? Give examples"?uf both commutative and non-
commutative rings ? ?
7XI=7w
(a) Show that the inclusion relation??: a partial ordering on the power set o?} set
S. Draw the Hasse diagram for ixiclusion on the set P (S) where S * { " 3b,;
d} Also Determine whether?? (S), 9') IS a lattice. , ' _
(b) Find the sum- ?)f-pm?tfefs and Product of sum expansmnwof the Boolean
function F (x y, z) a(x + y) 2 $9?
6. Attempt any one part Of the following: ~ _.?- E, ' 7 x l =
(a) What IS a tautology, contradiction and contingeneV'VS'l'tow that (p V q) A t p V
r)?-> (q V r) [S a tautology. contradiction 0r contingency
(b) Show that the premises ?It is not sumftyft'l'fis a?emoon and it is colder than
7. Attempt am one part of the {o?owingz
(a)
(b)
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?: ead'to the conclusion ?We will be home by
sunset." '
7xl=7
What axe different ways to represent a graph De?ne Euler circuit and Euler
graph Give necessary and suf?cient conditions for Euler circuits and paths.
Suppose that a valid codeword is an n-digit number in decimal notation
containing an even number of 0?s. Let 3:. denote the number of valid codewords
of length n satisfying the recurrence relation 3.. = 83.11 + 10?"1 and the initial
condition a1 = 9. Use generating functions to find an explicit formula for an.
This post was last modified on 29 January 2020