(SEM III) THEORY EXAMINATION 2019-20 DISCRETE STRUCTURES & THEORY OF LOGIC

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.