Annexure- 18
Roll No.
KIET Group of Institutions
CT Examination (2023-2024) ODD Semester
Department: Information Technology Course: B.Tech
Year: 2023-24 Semester: 3rd
Subject Name: Discrete Structure and Theory of Logics Subject Code: BCS303
Duration: 2 Hrs Max. Marks: 60
Note: Attempt all the questions of each section
Section-A (2X10=20)
Q. 1 Competitive
Exam# CO BL/ KC*
a Define Partition of a set with example. 1 1F
b Show that (A-B) = A ∩ B’ 2 3P
c Let A = {1, 2, 3, 4, 6, 8, 9, 12, 18, 24} be ordered by the relation ‘a divides b’. Draw the Hasse diagram. 1 1P
d 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) (3,3,) (3,6) (4,4) (5,1) (5,5) (6,2) (6,3) 1 1P
(6,6)} be the relation defined on set A. Identify Equivalence classes induced by R.
e Let A= ({1,2,3,4…………10},/). Identify the Supremum and Infimum for B={2,7}, C={1,2,3}, D={10, 6}. and 1 1P
E={2,7,9}.
f Let R be a relation on set A with cardinality n. Identify number of reflexive and symmetric relation on set A. 1 1C
g Express power set of each of these sets. GATE 2018 1 2C
1) {Ø,{ Ø}}
2) {a,{a}}
h Explain union and intersection of multiset and identify for A= [1,1,4,2,2,3], and B= [1,2,2,6,3,3]. 1 2C/P
i Explain power set with example. GATE 2007 1 2C
j Define Absorption law and Involution Law with equation. 2 1F
Section-B (5X4=20)
Out of 250 candidates who failed in an examination, it was revealed that 128 failed in maths, 87 in physics, and
134 in aggregate. 31 failed in maths and in physics, 54 failed in maths and in aggregate, 30 failed in aggregate
Q. 2 and physics.
1 3C/P
a. Calculate number of students failed in all subjects.
b. Calculate number of student failed in maths but not physics.
OR
In the Poset P shown in fig. Calculate upper bound, LUB, lower bound and GLB for A= {b, c} and B= {d, f}. NET 2010
Let R={(1,1),(2,2),(2,3),(3,2),(4,2),(4,4)} defined on A ={1,2,3,4}. Determine transitive closure of R using
Warshall’s algorithm.
Q. 3 1 3F/P
OR
Let R be relation given by on set A= {1,2,3,4,5} R= {(1,1), (1,4), (1,5), (2,3), (2,5), (3,1), (3,2), (3,3), (4,2),
(4,3), (5,3)}. Determine reflexive, and transitive closure of R.
Let us assume that R be a relation on the set of ordered pairs of positive integers such that ((a, b), (c, d))∈ R if
and only if ad=bc. Show that the R is an equivalence relation.
Q. 4 1 3C/P
OR
Show that for any sets A, B, and C:
a) (A – (A ∩ B)) = A – B.
b) (A – (B ∩ C)) = (A – B) ᴜ (A – C)
Illustrate isomorphic and homomorphic lattice with example.
Q. 5 OR 1 3C
Construct the Hasse Diagram for (P(S), ⊆) where P(S) is a power set defined on set S={a,b,c}.Determine
whether it is a Lattice or not?
Section-C (10X2=20)
Minimize the following Boolean expression using K-Map. GATE 2014
1) F(A,B,C,D)=(0,1,3,5,7,8,9,11,13,15) using POS.
Q. 6 2) F(A, B, C, D) = (0,1,2,5,7,8,9,10,13,15) using SOP.
2 4P
OR
Minimize the following Boolean expression using K-Map.
1) F(A,B,C,D)=(0,2,4,5,6,7,8,10,13,15) using SOP
2) F(A,B,C)=(0,1,2,4,5,6) using POS
Let L1 be the divisor D6 and L2 be the lattice (P(S), ⊆) where P(S) is a power set defined on set S={a,b}. Show
that the two lattices L1 and L2 are isomorphic. Determine whether (D36, /) is a complemented lattice.
Q. 7 OR 1 3C/P
Show that (D42, /) is lattice. Compare the distributive and complemented lattice with example.
● CO -Course Outcome generally refer to traits, knowledge, skill set that a student attains after completing the course successfully.
● Bloom’s Level (BL) - Bloom’s taxonomy framework is planning and designing of assessment of student’s learning.
● *Knowledge Categories (KCs): F-Factual, C-Conceptual, P-Procedural, M-Metacognitive
● #Reference to Competitive Exams (GATE, GPAT, CAT, GRE, TOFEL, NET, etc. )
