BTECH (SEM III) THEORY EXAMINATION 2023–24
TIME: 3 Hours | MAX MARKS: 70
This examination assesses a student’s conceptual and analytical understanding of discrete mathematics, logic, Boolean algebra, algebraic structures, relations, lattices, and graph theory—fundamental building blocks of computer science.
The paper is divided into three structured sections, covering definitions, problem-solving, and higher-order reasoning.
SECTION A – Short Answer Questions (14 Marks)
Seven questions × 2 marks each
This section tests foundational knowledge, definitions, and direct application of concepts.
Topics Covered:
1. Greatest Lower Bound (GLB) & Least Upper Bound (LUB) in Posets
Find GLB and LUB of {2,3,6} in the poset (D24, ÷). Tests understanding of divisibility relations.
2. Power Set Construction
Generate P(S) for sets containing elements and sets as members:
• {Ø, {Ø}}
• {a, {a}}
3. Injectivity of f(x) = x² – 1
Determine whether function from ℝ→ℝ is one-to-one.
4. Boolean Expression Conversion
Expand E(x,y,z) = xy + y' z into full Sum of Products form.
5. Logical Inverse of Conditional Statement
Find inverse of: "If I wake up early, I will be healthy."
6. Uniqueness of Identity Element in a Group
Prove identity in a group is unique.
7. Euler Circuit vs Hamiltonian Circuit
Differentiate both graph traversal concepts.
This section tests precision and clarity in basic discrete concepts.
SECTION B – Analytical & Problem-Solving Questions (21 Marks)
Attempt any three × 7 marks
These questions evaluate reasoning, construction of diagrams, proofs, and simplification techniques.
1. Hasse Diagram & Lattice Identification
Construct Hasse diagram for P(S) where S={a,b,c}.
Check if it forms a Lattice (every pair must have meet & join).
2. Boolean Simplification Through K-Map
Simplify two 4-variable Boolean functions:
(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)
Minimization logic & grouping required.
3. Predicate Logic Validity of the Given Argument
Apply rules of inference to prove validity:
Not sunny → cold → no swimming → canoe trip → home by sunset.
4. Group Theory – Complex Numbers under Multiplication
Given G={1,-1,i,-i}:
Check if it is Abelian
Check if G is cyclic
Find generator(s)
5. Pigeonhole Principle & Generalized PHP
State both forms and prove:
• If 37 homes are painted using 6 colors → at least 7 share the same color.
This section checks deeper conceptual understanding and ability to logically justify results.
SECTION C – Long Descriptive / Higher Order Questions (35 Marks)
One question from each part × 7 marks
3. Relations & Lattices
Option A – Equivalence / Order Properties
For relation R on strings where strings share same count of zeros:
Check if R is reflexive, symmetric, transitive, antisymmetric.
Determine whether R forms a partial order.
Option B – Lattice Properties
Show that (D42, ÷) forms a lattice.
Compare distributive vs complemented lattices with examples.
4. Boolean Algebra & Function Composition
Option A – K-Map Simplification (3-variable)
Solve F(A,B,C)=Σ(1,2,5,7) with don’t-cares D(0,4,6) using SOP.
Option B – Composition of Real Functions
Given f(x)=3x²+2, g(x)=7x−5, h(x)=1/x
Compute:
(i) (f ∘ g ∘ h)(x)
(ii) (g ∘ g)(x)
(iii) (g ∘ h)(x)
5. Logical Arguments & Quantifiers
Option A – Validity of Argument
Show argument validity:
• Ball game → difficult travel
• On-time arrival → travel not difficult
• They arrived on time → No ball game
Option B – Quantifiers & Predicate Logic
Explain ∀ and ∃ with examples.
Formalize: “There is someone who got an A in the course.”
Prove classic syllogism:
• All men are mortal
• Socrates is a man
→ Socrates is mortal
6. Algebraic Structures & Groups
Option A – Algebraic Structure Hierarchy
Explain:
Algebraic structure → Semigroup → Monoid → Group
Show relationships and examples.
Option B – Modulo Multiplicative Group
For G={1,2,3,4,5,6} under multiplication mod 7:
Construct table
Find inverses of 2, 3, 6
Find orders & subgroups generated
Is G cyclic?
7. Graph Theory
Option A – Bipartite vs Complete Graph
Differentiate with examples.
Draw K₃,₄ and K₅
Explain why both graphs are non-planar (via Kuratowski’s theorem).
Option B – Edge Condition for Planarity
Show K₃,₃ satisfies |E| ≤ 3|V| – 6 but is still non-planar.
Purpose of This Examination
This exam ensures students can:
Understand and apply discrete structures in computing
Simplify Boolean functions using K-Maps
Use propositional & predicate logic for proof construction
Work with algebraic structures (groups, lattices, posets)
Analyze graphs, circuits, and planarity
Build a strong mathematical foundation for algorithms, automata, cryptography & databases
It tests mathematical reasoning, logical thinking, and problem-solving—core skills for computer science.
