This document is the B.Tech Semester III Theory Examination (2019–20) question paper for Discrete Structures & Theory of Logic (KCS303) under Dr. A.P.J. Abdul Kalam Technical University (AKTU).
The uploaded file contains two pages and is neatly divided into three sections — SECTION A, SECTION B, and SECTION C.
The exam carries 100 marks and the duration is 3 hours.
The paper evaluates the student’s understanding of functions, relations, groups, lattices, logic, propositional equivalence, binary trees, generating functions, ring theory, recurrence relations, and algebraic structures.
SECTION A — Short Questions (10 × 2 = 20 Marks)
(Visible on Page 1)
Section A contains ten brief questions, each worth 2 marks, covering foundational concepts of discrete mathematics.
Topics include:
Types of functions
Counting symmetric and reflexive relations on a set of n elements
Binary operation on integers and identity element of a group
Proving that cyclic groups are abelian
Lattices: proving that a 5-element lattice is a Boolean algebra
Writing contrapositive of a compound proposition
Logical equivalence: proving (p→q)∧(¬q→¬p)(p → q) ∧ (¬q → ¬p)(p→q)∧(¬q→¬p)
Showing there is no graph with 5 vertices of degree 1, 3, 4, 2, 3
Finding the generating function for a sequence
Determining whether a set forms a ring or not
Each question is arranged clearly in the table on Page 1.
SECTION B — Descriptive Questions (Attempt Any 3 × 10 = 30 Marks)
(Located at the bottom of Page 1)
Students must attempt any three of the five 10-mark questions.
Topics include:
Solving a recurrence relation
Characteristics of a lattice
Poset (Partially Ordered Set) explanation with examples
Propositional logic equivalence: proving
- (p∨q)∧(p∨r)≡p∨(q∧r)(p \lor q) \land (p \lor r) \equiv p \lor (q \land r)(p∨q)∧(p∨r)≡p∨(q∧r)
Constructing a Hasse diagram and proving properties of relations
These questions require explanation, proofs, and detailed reasoning.
SECTION C — Advanced/Applied Questions (5 × 10 = 50 Marks)
(Shown clearly on Page 2)
Section C contains five numbered groups, each containing two alternatives (a or b). Students must answer one from each group.
Q3 — Number Theory & Relations
Find numbers between 1 to 500 not divisible by 2, 3, 5, or 7
OR
Discuss “divides” relation on positive integers:
Is it transitive?
Reflexive?
Symmetric?
Q4 — Ring Theory
What is a Ring? Explain elementary properties with example
OR
Prove/disprove: intersection of two normal subgroups is also normal
Q5 — Lattice Theory
Given a distributive lattice, prove b≤cb ≤ cb≤c
OR
Obtain PDNF and PCNF of (p→r)∧(q↔p)(p → r) ∧ (q ↔ p)(p→r)∧(q↔p)
Q6 — Generating Functions
Construction of generating function
OR
Solve recurrence relations using generating functions
Q7 — Hasse Diagram / Algebra
Draw Hasse diagram for a given poset
OR
Use algebraic methods to test properties of relations
These questions cover advanced logical reasoning, algebraic structures, posets, rings, lattices, and generating functions.
OVERALL SUMMARY OF THE DOCUMENT
This Discrete Structures & Theory of Logic (KCS303) question paper thoroughly evaluates:
Functions & relations
Group theory
Boolean algebra & lattices
Propositional and predicate logic
Logical equivalence and contrapositive
Hasse diagrams & posets
Recurrence relations
Generating functions
Ring theory
Graph theory basics
Algebraic structures
Basic counting & number theory
The structure strictly follows the AKTU pattern:
SECTION A: Short conceptual recall
SECTION B: Descriptive proofs/theory
SECTION C: Advanced algebraic + logical problems
The uploaded document is clean, complete, and spans two pages with clear formatting.
