(SEM III) THEORY EXAMINATION 2020-21 DISCRET STRUCTURE THEORY OF LOGIC

This document is the B.Tech Semester III Theory Examination Question Paper for the subject KCS303 – Discrete Structure & Theory of Logic, conducted by Dr. A.P.J. Abdul Kalam Technical University (AKTU) for the academic year 2020–2021. The exam duration is 3 hours, and the total marks allotted are 100. The paper follows the official AKTU pattern and is divided into multiple structured sections designed to test conceptual understanding, logical reasoning, mathematical proof skills, graph theory concepts, Boolean algebra, and functional analysis.

Section A – Short Answer Questions (10 Questions × 2 Marks = 20 Marks)

This section includes ten short questions, each worth 2 marks, covering core definitions and fundamental concepts from functions, relations, algebraic structures, logic, lattices, binary trees, and graph theory.
Examples include:

Checking injectivity of a function

Counting reflexive and symmetric relations on a set

Defining a group and a ring

Drawing a Hasse diagram for a divisibility relation

Writing negation of statements

Expressing English statements symbolically

Explaining complete graph and regular graph

Proving maximum vertices in a binary tree of height h

These questions test basic understanding and theoretical clarity. 

Section B – Attempt Any Three (Each 10 Marks)

This section evaluates analytical and problem-solving skills.
Questions touch upon:

Composition of functions (fogoh, gog, goh, hogof)

Lagrange’s theorem (statement and proof)

Proving distributive inequalities in lattices

Logical argument validation

Euler’s formula for planar graphs (n – e + r = 2)

This section requires step-by-step reasoning, proofs, and detailed explanations. 

Section C – Mathematical Induction & Number Problems (Attempt One, 10 Marks)

This section focuses on mathematical induction and number theory.
Students must either:

Prove expressions divisible by 17 using induction
or

Find the numbers between 100 and 1000 divisible by 3, 5, or 7

These questions test logical reasoning and number system understanding. 

Section D – Group Theory (One Question, 10 Marks)

This section covers group theory concepts including normal subgroups and inverse properties.
Students must prove group identities such as:

(a⁻¹)⁻¹ = a

(ab)⁻¹ = b⁻¹ a⁻¹

or prove the definition of a normal subgroup.
This tests abstract algebra understanding. 

Section E – Boolean Algebra Simplification (One Question, 10 Marks)

Students must simplify Boolean expressions using Boolean algebra or express Boolean functions using minterms.
One question also requires drawing the corresponding logic circuit.
This section measures digital logic competency. 

Section F – Propositional Logic & Predicate Logic (One Question, 10 Marks)

This includes:

Identifying whether a compound statement is a tautology, contradiction, or contingency

Translating English statements into symbolic logic

Examples include statements about positivity of sums, universal love, admiration, and parental roles.
This tests symbolic logic and reasoning. 

Section G – Trees & Recurrence Relations (One Question, 10 Marks)

Students may either:

Construct a binary tree from given inorder & preorder traversal and find postorder traversal
or

Solve a recurrence relation

This section tests knowledge of data structures and discrete mathematics. 

Overall Description

This AKTU question paper offers a well-structured and comprehensive evaluation of Discrete Structure & Theory of Logic, covering:

Functions & relations

Group theory & lattices

Logical equivalences & proofs

Boolean algebra & circuits

Graph theory & planar graphs

Recurrence relations

Tree construction

Mathematical induction

The paper reflects the breadth of discrete mathematics crucial for computer science students, testing both theoretical knowledge and analytical depth.