Printed Page: 1 of 2

PAPER ID-31 1571

Subject Code: BCS303
Roll No:
2lelalslo2 S3o
s o o1
BTECH
(SEM III) THEORY EXAMINATION 2023-24
DISCRETE STRUCTURES & THEORY OF LOGIC
TIME: 3HRS
[Link]: 70
Note: 1. Attempt all Sections. If require any missing data; then choose suitably.
SECTION A
1. Attempt all questions in brief. 2 x7=14
Qno. Question Marks

a. Determine the greatest lower bound and least upper bound of the set (2, 2 1
3, 6}, if they exist, in the Poset (D24, /).
o. Express power set of each of these sets.
1) {0,{ 0}}
2) {a,{a}}
C.
Investigate whether thefunction f(x) =x²-1 is injective or not for 2
f: R>R.
d. Express E(x, y, z) xy+ y'z into its compiete sum-of-products form. 2
e Construct inverse of the following statement "If I wake up early 2 3
in the morning, then I will be healthy."
f. Show that identity element is unique in a group. 2 4
Compare Euler circuit and Hamiltonian circuit. 2
SECTION B

2. Attempt any three of the [Link]: Marks CO

Ono. Question
Construct the Hasse Diagram for (P(S), S) whereP(S) is a powei
Lattice
set defined on set S={a, b, ¢}. Determine whether it is a
or not. 2
7
6. -Solve the following Boolean functions using K-map:
(i) F(A,B,C,D) = (m0,ml,m2,m4,m5, m6,m8,m9,m12,m13,mn14)
(ü) F(A,B,C,D) = (0,2,5,7,8,10,13,15) 7 3
Show the validity of the following argument:
hypotheses: "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. Ifwe take a
canoe trip, then
we will be home by sunset.
conclusion: "We willbe home by sunset. 7 4
multiplication be
LetG= {1, -1, i,- i} with the binaty operation
determine whether G is
an algebraic structure, wherei-1 then then determine the
Group,
an Abelian group. Also if G is cyclic
generatorof G.
hole principle. Describe generalized form of Pigeon hole 7 5
e. Explain Pigeon that at least 7 of them
[Link]
principle. If6 colors are to paint 37
willbe of same color.
 Irinted Page: 2 of 2
Subject Code: BCS303
PAPER ID-311571
Roll No:
BTECH
(SEM III) THEORY EXAMINATION 2023-24
DISCRETE STRUCTURES & THEORY OF LOGIC
TIME: 3HRS [Link]: 70

SECTION C
3. Attempt any one part of the following: 7x1 = 7
O no. Qucstion Marks CO

Let R bc a binary relation on the sct of all strings of 0 and 1such that R 1
= {(a,b): a and b have same number of 0's}. Show that whether R is
reflexive, symmctric, transitive ora partial order relation.
b Show that (D42, ) is latticc. Compare the distributive and
complemented lattice with example.
4. Attempt any one part of the following: 7x1 =7
Qno. Qucstion Marks CO
a.
Solvethe following Bqolean function using K-map: 7 2
F(A,B,C)1,2,5,7) ahd D(0,4,6) using SOP.
b. Iff: R>R,g:R’R and h: R>R defined by f(x) 3x+2, g(x) =7x-5 7
and h(x)= /x. Compute the following composition functions.
)(fogoh)(x) (i) (gog)(x) (ii) (goh)(x)
5 Attempt an one part of the following: 7x1=7
no. Question Marks Co
a. Test tac validity of the follr vingargument.
"If there was a ball game, then traveling was difficult. If they arrived on
time, then traveling was not ificult. They arrived on time. Therefore,
There was io all game."
. Describe and Quantifiers with example. "There is someone who got7 3
an A in the course" convert this sentence into predicate logic using
quantifiers. Prove the following argument. All man are mortal. Socrates
is a man. Therefore, Socrates is mortal.

6. Attempt any onepartofthe following: 7x1=7

Q no. Question Marks CO
Describe Algebraic structure, semigroup, monoid and group. Also 7 4
explain the relationship among them.
b. Consider group G= {1, 2, 3,4, 5, 6} under multiplication modulo 7. 7 4
(a)Construct the multiplication table of G.
(b)Compute 2-1, 3-!, 6-!
(c) Compute the orders and subgroups generated by 2 and 3.
(d) Is G
cyclic?
7. Attempt any one part of the following: 7x1=7
Q no. Question Marks Co
a. Compare bipartite and complete graph with example. Draw K3,4 and Ks.7
Explain why these two graphs are not planar.
b. Show that K33 satisfies in equality |E| < 3 |V| - 6, but it is non- 7
planar.(V-No. of Vertices,E=No. of Edges, R-No. of Regions)
 NITRA TECHNICAL CAMPUS (802), GHAZIABAD

RollNo. 2aodalsalooo
B. Tech -CSE/TT/AI&ML
(SEM III) 1st Sessional, Odd Semcster, Oct, 2023
Discrete Structures & Theory of Logic
BCS 303

Time: 01:30 hrs Total Marks:20

Note: () Attempt all sections as directed.
(2) Be precise in your answer.
Section A
1. Attempt all parts. 5X1=5

(a) What is the cardinality of the set?

(b) Define various types of functions.
(c) lf a set has n elements, how many relations are there from A to A?
(d) Define Composition of Relations with example.
(e) Define Boolean Algebra.
Section B

2. Attempt any four parts. 4 X2.5=10

(a) Write down the properties of Equivalence relation.
(b) Defne Growth of functions.
(c) Define Axioms of Boolean Algebra.
(d) Let f: R ’R, g: R ’R, where R is the set of real numbers be given by f(x) =x
2and g(x)=x+4find fog and gof. State whether these functions are bijective or not.
(e) Let a¬B, Prove that
(i) a +a = a (i) a.a=a

Section C
3. Attempt any one parts. 1x5=5

(a) 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 bcth French and Russian) If 2092 students have iaken at least
one of Spanish, French, and Russian,how many students have taken a course in all
three languages?
(b) IfX= (1,2,3), Y=(p.) and Z=(a, b) and the functions fand gare define as
fX’Y be f= {(1, p), (2, p), (3, )}, g: Y Zbe g= ((p.@,(9, b)} then find fog
and gof.
 NITRA TECHNICAL CAMPUS (802), GHAZIABAD

RollNo.

B. Tech -CSE/AI&ML
(SEM III) 1st Sessional, Odd Semester, Oct, 2024
Discrete Structures & Theory of Logic
BCS 303

Time: 0l:30 hrs Total Marks: 20

Note: (1) Attempt all sections as directed.

(2) Be precise in your answer.
Section A
5X 1=5
1. Attempt all parts.
(2)Find the power set of A = {0, (1,2), 3}
b) Define various types of functions.
fe) State De Morgan's Law.
(d) What is an inverse relation?
(e) What are the basic operations in Boolean Algebra?
Section B
2. Attempt any four parts. 4 X2.5=10
(ay Writedown the properties of Equivalence relation.
Ab) What is a reflexive closure, symmetric closure, and transitive closure?
(c) Define Axioms of Boolean algehra.
(d) Draw the graph for the relation R= {(1, 2),(2,3),(1,3)}.
(e) Explain the application of set theory.

Section C
3. Attempt any one parts. 1X5=5

(a) Let A={0, 1, 2, 3,... and R= l(x. y) :xy=3k, kis an integer) ie., xRy if 'x-y' is
divisible by 3, then prove that Ris an equivalence relation.
(b) Simplify the following Boolean function using a4-variable K-map:
F(A,B,C,D)= m(1,3,7,11,15) Here, the Boolean function is expressed as the sum of
minterms, where m(i) represents a miaterm with index i.

a.