(SEM III) THEORY EXAMINATION 2023-24 DISCRETE STRUCTURES & THEORY OF LOGIC

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.