Printed Pages:03 Sub Code: KCS -303

Paper Id: 233534 Roll No.

B. TECH.
(SEM-III) THEORY EXAMINATION 2022-23
DISCRETE STRUCTURES & THEORY OF LOGIC

Time: 3 Hours Total Marks: 100

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

SECTION A

1. Attempt all questions in brief. 2 x 10 = 20

(a) Identify whether ⎾x+y⏋=⎾x⏋+⎾y⏋, ⩝x,y ∈R, where ⎾x⏋is a ceiling
function
(b) Find the Maximal elements and minimal elements form the following Hasse’s
diagram

(c) Define what is Big-O notation with respect of growth of functions.

(d) Find the composite mapping gof if
f: RR is given by f(x) = ex and g: RR is given by g(x) = sinx
(e) Draw an adjacency matrix for the following graph

(f) Let A = { Φ, b}, then calculate A  P(A), where P(A) is a power set of A.
(g) Draw the Hasse’s diagram of the POSET (L, ) , where
L = {S0, S1, S2, S3, S4, S5, S6, S7}, where the sets are given by
S0 = {a,b,c,d,e,f}, S1 = {a,b,c,d,e} , S2 = {a,b,c,e,f},
S3 = {a,b,c,e}, S4 = {a,b,c} , S5 = {a,b} , S6 = {a,c} , S7 = {a}
(h) Describe Planar graph and express Euler’s formula for planar graph.
(i) Define normal subgroup.
(j) Identify whether (p Λ q) → (p V q) is tautology or contradiction with using
Truth table.

SECTION B
2. Attempt any three of the following: 10x3=30
(a) Identify whether the each of the following relations defined on the set X =
{1,2,3,4} are reflexive, symmetric, transitive and/or antisymmetric?

(i) R1 = { (1,1), (1,2), (2,1) }

(ii) R2 = { (1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4) }

(iii) R3 = { (2,1), (3,1), (3,2), (4,1), (4,2), (4,3) }
(b) Let a function is defined as f: R-{3}→ R-{1}, f(x) = (x-1)/(x-3) ,
then show that f is a bijective function and also compute the inverse of f.
Where R is a set of real numbers.
(c) (i) Express Converse, Inverse and Contrapositive of the following statement
“If x+5=8 then x=3”
(ii) Show that the statements P↔Q and (P ⋀ Q) V(⏋P ⋀ ⏋Q) are equivalent
(d) Express the following
(i) Euler graph and Hamiltonian graph
(ii) Chromatic number of a graph
(iii) Walk and path
(iv) Bipartite graph
(e) Solve the following recurrence relation by using generating function.
an + 5an-1 + 6an-2= 42. 4n , where a0 = 1 and a1 = -2

SECTION C
3. Attempt any one part of the following: 10x1=10
(a) Let G = {1,-1, 𝑖, 𝑖} with the operation of ordinary multiplication on G be an
algebraic structure, where 𝑖=√-1.
(i) Determine whether G is abelian.
(ii) Determine the order of each element in G.
(iii) Determine whether G is a cyclic group, if G is a cyclic group, then
determine the generator/generators of the group G.
(iv) Determine a subgroup of the group G.

(b) Let (G,*) and G’,*’) be any two groups and let e and e’ be their respective
identities. If f is a homomorphism of G into G’, then prove that
(i) f(e) = e’
(ii) f(x-1) = [f(x)]-1 , ⩝ x ∈G

4. Attempt any one part of the following: 10x1=10

(a) Use generating function to find the number of ways Rs 23 can by paid by using
4 coins of Rs 5, 6 coins of Rs 2 and 4 coins of Rs 1.
(b) Using Pigeonhole principle find the minimum number n of integers to be
selected from S={1,2,3,4,5,6,7,8,9} so that
(i) the sum of two of the integers is even
(ii) the difference of two of the n integers is 5

5. Attempt any one part of the following: 10x1=10

(a) Define complemented lattice and then show that in a distributive lattice, if an
element has a complement then this complement is unique.
(b) Solve the following Boolean functions using K-map:
(i) F(A,B,C,D) = ∑( m0, m1, m2, m4, m5, m6, m8, m9, m12, m13, m14 )
 (ii) F(A,B,C,D)=∑(0,2,5,7,8,10,13,15)

6. Attempt any one part of the following: 10x1=10

(a) Prove the validity of the following argument.
If Mary runs for office, She will be elected. If Mary attends the meeting, she will
run for office. Either Mary will attend the meeting or she will go to India. But Mary
cannot go to India.
“Thus Mary will be elected”.
(b) Convert the following two statements in quantified expressions of predicate logic
(i) For every number there is a number greater than that number.
(ii) Sum of every two integer is an integer.
(iii) Not Every man is perfect.
(iv) There is no student in the class who knows Spanish and German

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

(a) Prove that the set of residues F={0,1,2,3,4} modulo 5 is a field w.r.t. addition and
multiplication of residue classes modulo 5. i.e. (F, +5, X5) is a field.
(b) Define Boolean algebra. Show that a’.[(b’+c)’+ b.c] + [(a+b’)’.c] = a’.b using
rules of Boolean Algebra. Where a’ is the complement of an element a.
 Printed Page: 1 of 2
Subject Code: KCS303
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM III) THEORY EXAMINATION 2021-22
DISCRETE STRUCTURES & THEORY OF LOGIC

Time: 3 Hours Total Marks: 100

Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2x10 = 20
Qno. Question Marks CO
a. Let A = {1,2,3,4,5,6} be the set and R = {(1,1) (1,5) (2,2) (2,3) (2,6) (3,2) 2 1
(3,3,) (3,6) (4,4) (5,1) (5,5) (6,2) (6,3) (6,6)} be the relation defined on set
A.
Find Equivalence classes induced by R.
b. Solve Ackerman Function A (2,1). 2 1
c. State and justify “Every cyclic group is an abelian group”. 2 2
d. State Ring and Field with example. 2 2
e. Differentiate complemented lattice and distributed lattice. 2 3
f. State De Morgan’s law and Absorption Law. 2 3
g. Translate the conditional statement “If it rains, then I will stay at home” into 2 4
contrapositive, converse and inverse statement.

1
h. State Universal Modus Ponens and Universal Modus Tollens laws. 2 4

13
0
i. Explain Euler’s formula. Determine number of regions if a planar graph has 2 5
29

30 vertices of degree 3 each.

2.
2_

j. Explain pigeonhole principle with example. 2 5

24
SECTION B
2P

5.
.5
2. Attempt any three of the following: 3x10 =30
P2

17
Qno. Question Marks CO
Q

|1

a. Justify that for any sets A, B, and C: 10 1

i) (A – (A ∩ B)) = A – B ii) (A – (B ∩ C)) = (A – B) ᴜ (A – C)
4

b. Explain Cyclic group. Let H be a subgroup of a finite group G. Justify the 10 2

:3

statement “the order of H is a divisor of the order of G”.

27

c. Solve E(x,y,z,t) = ∑ (0,2,6,8,10,12,14,15) using K-map. 10 3

:

d. Construct the truth table for the following statements: 10 4

13

i) (P→Q’)→P’ ii) P↔(P’˅Q’).

2

e. Solve the recurrence relation using generating function. 10 5

02

an+2- 5an+1 +6an =2, with a0=3 and a1=7.

-2

SECTION C
ar

3. Attempt any one part of the following: 1x10 =10

M

Qno. Question Marks CO

1-

a. State Principle of Duality. Let A denote the set of real numbers and a 10 1
|3

relation R is defined on A such that (a,b)R(c,d) if and only if a2 + b2 = c2 +

d2. Justify that R is an equivalence relation.
b. i) Let R = {(1,2) (2,3) (3,1)} defined on A = {1,2,3}. Find the transitive 10 1
closure of R using Warshall’s algorithm.
ii) Justify that “If f: A→B and g: B→C be one-to-one onto functions, then
gof is also one to one onto and (gof)-1= f -1o g -1”.

1|Page
QP22P2_290 | 31-Mar-2022 13:27:34 | 117.55.242.131
 Printed Page: 2 of 2
Subject Code: KCS303
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

BTECH
(SEM III) THEORY EXAMINATION 2021-22
DISCRETE STRUCTURES & THEORY OF LOGIC

4. Attempt any one part of the following: 1x10 =10

Qno. Question Marks CO
a. Define the binary operation * on Z by x*y=x + y + 1 for all x,y belongs to 10 2
set of integers. Verify that (Z,*) is abelian group? Discuss the properties of
abelian group.
b. i) Justify that “The intersection of any two subgroup of a group (G,*) is 10 2
again a subgroup of (G,*)”.
ii) Justify that “If a,b are the arbitrary elements of a group G then (ab)2 =
a2b2 if and only if G is abelian.
5. Attempt any one part of the following: 1x10 =10
Qno. Question Marks CO
a. Define Modular Lattice. Justify that if ‘a’ and ‘b’ are the elements in a 10 3
bounded distributive lattice and if ‘a’ has complement a′. then
I) a ˅ (a′˄ b)=a˅ b II ) a˄ (a′˅ b)=a˄ b
b. i) Justify that (D36,\) is lattice. 10 3
ii) Let L1 be the lattice defined as D6 and L2 be the lattice (P(S), ≤), where

1
P(S) be the power set defined on set S= {a, b}. Justify that the two lattices

13
0
are isomorphic.
29

6. Attempt any one part of the following: 1x10 =10

2.
2_

24
Qno. Question Marks CO
2P

a. Use rules of inference to Justify that the three hypotheses (i) “If it does not 10 4

5.
rain or if it is not foggy, then the sailing race will be held and the lifesaving
.5
P2

demonstration will go on.” (ii) “If the sailing race is held, then the trophy
17
Q

will be awarded.” (iii) “The trophy was not awarded.” imply the conclusion
|1

(iv) “It rained.”

b. Justify that the following premises are inconsistent. (i) If Nirmala misses 10 4
4

many classes through illness then he fails high school. (ii) If Nirmala fails
:3

high school, then he is uneducated. (iii) If Nirmala reads a lot of books then
27

he is not uneducated. (iv) Nirmala misses many classes through illness and
:

reads a lot of books.

13

7. Attempt any one part of the following: 1x10 =10

2

Qno. Question Marks CO

02

a. Explain the following terms with example: 10 5

-2

i. Graph coloring and chromatic number.

ar

ii. How many edges in K7 and K3,3

M

iii. Isomorphic Graph and Hamiltonian graph.

iv. Bipartite graph.
1-

v. Handshaking theorem.
|3

b. i. Justify that “In a undirected graph the total number of odd degree 10 5
vertices is even”.
ii. Justify that “The maximum number of edges in a simple graph is
n(n-1)/2”.

2|Page
QP22P2_290 | 31-Mar-2022 13:27:34 | 117.55.242.131
 Printed Page: 1 of 2
Subject Code: KCS303
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

B TECH
(SEM-III) THEORY EXAMINATION 2020-21
DISCRETE STRUCTURE & THEORY OF LOGIC
Time: 3 Hours Total Marks: 100
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.

SECTION A

1. Attempt all questions in brief. 2 x 10 = 20

Q no. Question Marks CO
a. Check whether the function f(x) = x2 - 1 is injective or not for f : R→R. 2 CO3
b. Let R be a relation on set A with cardinality n. Write down the number of 2 CO2
reflexive and symmetric relation on set A.
c. Define group. 2 CO3
d. Define ring. 2 CO3
e. Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by the relation ‘a divides 2 CO3
b’. Find the Hasse diagram.
f. If L be a lattice, then for every a and b in L prove that a ˄ b = a if and only if 2 CO3
a ≤ b.

P
g. Write the negation of the following statement: 0Q 2 CO1
“If I wake up early in the morning, then I will be healthy.”

1
13
h. Express the following statement in symbolic form: 2 CO1
29

“All flowers are beautiful.”

2.
0E

i. Define complete and regular graph. 2 CO4

24
j. Prove that the maximum number of vertices in a binary tree of height h is 2h+1, 2 CO4
P2

5.
h ≥ 0.
_Q

.5
17
TU

SECTION B
|1
AK

2. Attempt any three of the following:

1

Q no. Question Marks CO

:4
55

a. If f : R → R, g : R → R and h : R → R defined by 10 CO3

f(x) = 3x2 +2, g(x) = 7x – 5 and h(x) = 1/x.
:
13

Compute the following composition functions

i. (fogoh)(x)
1

ii. (gog)(x)
02

iii. (goh)(x)
-2

iv. (hogof)(x)
ar

b. State and prove Lagrange theorem for group. 10 CO3

M

c. Prove that in any lattice the following distributive inequalities hold 10 CO3
9-

i. a ˄ (b ˅ c) ≥ (a ˄ b) ˅ (a ˄ c)
|1

ii. a ˅ (b ˄ c) ≤ (a ˅ b) ˄ (a ˅ c)
d. Prove the validity of the following argument 10 CO1
“If I get the job and work hard, then I will get promoted. If I get promoted,
then I will be happy. I will not be happy. Therefore, either I will not get the
job, or I will not work hard.”
e. If a connected planar graph G has n vertices, e edges and r region, then n – e 10 CO5
+ r = 2.

1|Page
AKTU_QP20E290QP | 19-Mar-2021 13:55:41 | 117.55.242.131
 Printed Page: 2 of 2
Subject Code: KCS303
0Roll No: 0 0 0 0 0 0 0 0 0 0 0 0 0

SECTION C
3. Attempt any one part of the following:
a. Prove by mathematical induction for all positive integers that 10 CO2
3.52n+1 + 23n+1 is divisible by 17.
b. Find the numbers between the 100 to1000 that are divisible by 3 or 5 or 7. 10 CO2

4. Attempt any one part of the following:

a. A subgroup H of a group G is a normal subgroup if and only if g- 10 CO3
1
hg ϵ H for every h ϵ and g ϵ G.
b. In a group (G, *) prove that 10 CO3
i. (a-1)-1 = a
ii. (ab)-1 = b-1a-1

5. Attempt any one part of the following:

a. Simplify the Boolean function 10 CO3
F (A, B, C, D) = ∑ (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11)
Also draw the logic circuit of simplified F.
b.
P
Simplify the following Boolean expressions using Boolean algebra 10 CO3
0Q

1
i. xy + x΄z +yz

13
29

ii. C(B + C)(A + B + C)

2.
iii. A + B(A + B) + A(A΄ + B)
0E

24
iv. XY + (XZ)΄ + XY΄Z(XY + Z)
P2

5.
_Q

.5
6. Attempt any one part of the following:
17
TU

a. Define tautology, contradiction and contingency? Check whether (p ˅ q) ˄ ( 10 CO1

|1

~ p ˅ r) → (q ˅ r) is a tautology, contradiction or contingency.

AK

b. Translate the following statements in symbolic form 10 CO1

:4

i. The sum of two positive integers is always positive.

55

ii. Everyone is loved by someone.

:

iii. Some people are not admired by everyone.

13

iv. If a person is female and is a parent, then this person is someone’s

mother.
1
02
-2

7. Attempt any one part of the following:

ar

a. Construct the binary tree whose inorder and preorder traversal is given below. 10 CO4
M

Also, find the postorder traversal of the tree.

9-

Inorder: d, g, b, e, i, h, j, a, c, f
|1

Preorder: a, b, d, g, e, h, i, j, c, f
b. Solve the following recurrence relation 10 CO3
an – an – 1 + 20an – 2 = 0 where a0 = – 3 , a1 = – 10

2|Page
AKTU_QP20E290QP | 19-Mar-2021 13:55:41 | 117.55.242.131
 Printed pages:2 Roll No. Sub Code: RCS 301

Paper ID:1002

B.Tech.
(SEM III) THEORY EXAMINATION 2017-18
Discrete Structures & Theory of Logic
Time: 3 Hours Total Marks: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
2. Any special paper specific instruction.

SECTION A

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

a. Define Eulerian path, circuit and graph
b. Let A=(2,4,5,7,8)=B ,aRb if and only if a+b<=12.Find relation matrix
c. Explain edge coloring and k egde coloring.
d. Define Chromatic number and Isomorphic graph.

e. Define union and intertersection of multiset and find for

A=[1,1,4,2,2,3],B=[1,2,2,6,3,3].

f. Find the contrapositive of –“If he has courage, then he will win”.

g .Define rings and write its properties.

SECTION B

2. Attempt any three of the following: 7 x 3 = 21

a. Prove by mathematical induction
3+33+333+..............33..3 = (10n+1-9n-10)/27

b. Define the following with one example:

i) Bipartite graph.

ii) Complete graph.

iii) How many edges in K7 and K3,6

iv) Planar Graph.

c. For any positive integer D36, then find whether (D36,’|’) is lattice or not?

d. Let X={1,2,3.....7} and R={(x,y) | (x-y) is divisible by 3).Is R equivalence relation

Draw the diagraph of R
e. Simplify the following Boolean function using K-map:
F(x,y,z)=∑(0,2,3,7)
 SECTION C
3. Attempt any one part of the following: 7x1=7
r
(a) Solve ar-6ar-1+8ar-2=r.4 , given a0=8, and a1=1.
(b) Show that: r → ~q, r v s, s → ~q, p → q ↔ ~p are inconsistent

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

(a) Write the properties of Group. Show that the set(1,2,3,4,5)is not group under
addition and multiplication modulo 6.

(b) Prove by mathematical induction

n4-4n2 is divisible by 3 for all n>=2.

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

(a)Explain Modular lattice, distribute lattice and bounded lattice with eg and diagram

(b) Draw the Hasse diagram of (A, ≤), where

A= {3,4,12,24,48,72} and relation ≤ be such that a ≤ b if a divides b

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

(a) Given the inorder and postorder traversal of a tree T
Inorder : HFEABIGDC Postorder : BEHFACDGI .
Determine the tree T and its Preorder.

(b) Translate the following sentences in quantified expressions

of predicate logic.

i) All students need financial aid.

ii) Some cows are not white..
iii) Suresh will get if division if and only if he gets first div.
iv) if water is hot,then shyam will swim in pool.
v) All integer are either even or odd integer.
7. Attempt any one part of the following: 7x1=7
(a) Define and Explain any two the following:
1. BFS and DFS in Trees.
2. Euler Graph
3. Adjacency matrix of a graph.
2
(b) Solve the recurrence relation: ar +4ar-1 + 4ar-2= r .