UNIQUE SERIES AKTU Syllabus
BCS303BCS303H

Discrete Structures & Theory of Logic

L-T-P2-1-0 Credits3 Session2023-24 TypeTheory
Appears in 13 semesters · 13 branches

B.Tech Computer Science & Engineering · Sem 3 (Core, code BCS303) · B.Tech Information Technology · Sem 3 (Core, code BCS303) · B.Tech Artificial Intelligence & Machine Learning · Sem 3 (Core, code BCS303) · B.Tech Artificial Intelligence & Data Science · Sem 3 (Core, code BCS303) · B.Tech CSE (Artificial Intelligence) · Sem 3 (Core, code BCS303) · B.Tech CSE (AI & ML) · Sem 3 (Core, code BCS303) · B.Tech CSE (Data Science) · Sem 3 (Core, code BCS303) · B.Tech CSE (Cyber Security) · Sem 3 (Core, code BCS303) · B.Tech CSE (Internet of Things) · Sem 3 (Core, code BCS303) · B.Tech Computer Science & Design · Sem 3 (Core, code BCS303) · B.Tech Computer Science (Hindi) · Sem 3 (Core, code BCS303H) · B.Tech Computer Science & Business Systems · Sem 3 (Core, code BCS303) · B.Tech Electronics & Computer Engineering · Sem 3 (Core, code BCS303)

Download PDF

Syllabus

5 units · 40 lecture hours
Unit1

Unit 1: Set Theory& Relations

8 hrs

Introduction, Combination of sets. Relations: Definition, Operations on relations, Properties of relations, Composite Relations, Equality of relations, Recursive definition of relation, Order of relations. POSET & Lattices: Hasse Diagram, POSET, Definition & Properties of lattices – Bounded, Complemented, Distributed, Modular and Complete lattice.

Unit2

Unit 2: Functions

8 hrs

Definition, Classification of functions, Operations on functions. Growth of Functions. Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Algebraic manipulation of Boolean expressions. Simplification of Boolean Functions, Karnaugh maps.

Unit3

Unit 3: Theory of Logics

8 hrs

Proposition, Truth tables, Tautology, Satisfiability, Contradiction, Algebra of proposition, Theory of Inference. Predicate Logic: First order predicate, well-formed formula of predicate, quantifiers, Inference theory of predicate logic.

Unit4

Unit 4: Algebraic Structures

8 hrs

Definition, Groups, Subgroups and order, Cyclic Groups, Cosets, Lagrange's theorem, Normal Subgroups, Permutation and Symmetric groups, Group Homomorphisms, Definition and elementary properties of Rings and Fields.

Unit5

Unit 5: Graphs

8 hrs

Definition and terminology, Representation of graphs, Multigraphs, Bipartite graphs, Planar graphs, Isomorphism and Homeomorphism of graphs, Euler and Hamiltonian paths, Graph coloring. Combinatorics: Introduction, Counting Techniques, Pigeonhole Principle

Course Outcomes (COs)5 outcomes

After completion of the course student will be able to:

  1. CO1Acquire Knowledge of sets and relations for solving the problems of POSET and lattices.K3, K4
  2. CO2Apply fundamental concepts of functions and Boolean algebra for solving the problems of logical abilities.K1, K2
  3. CO3Employ the rules of propositions and predicate logic to solve the complex and logical problems.K3
  4. CO4Explore the concepts of group theory and their applications for solving the advance technological problems.K1, K4
  5. CO5Illustrate the principles and concepts of graph theory for solving problems related to computer science.K2, K6

Text books

  1. Koshy, Discrete Structures, Elsevier Pub. 2008 Kenneth H. Rosen, Discrete Mathematics and Its Applications, 6/e, McGraw-Hill, 2006.
  2. B. Kolman, R.C. Busby, and S.C. Ross, Discrete Mathematical Structures, 5/e, Prentice Hall, 2004.
  3. E.R. Scheinerman, Mathematics: A Discrete Introduction, Brooks/Cole, 2000.
  4. R.P. Grimaldi, Discrete and Combinatorial Mathematics, 5/e, Addison Wesley, 2004
  5. Liptschutz, Seymour, “ Discrete Mathematics”, McGraw Hill.
  6. Trembley, J.P & R. Manohar, “Discrete Mathematical Structure with Application to Computer Science”, McGraw Hill. 4. Deo,
  7. Narsingh, “Graph Theory With application to Engineering and Computer.Science.”, PHI.
  8. Krishnamurthy, V., “Combinatorics Theory & Application”, East-West Press Pvt. Ltd., New Delhi

Official AKTU syllabus

This subject is on page 7 of the original AKTU PDF.

Official AKTU syllabus PDF ↗