MASTER OF COMPUTER APPLICATION (Two Year Course) MCA Ist Year 2020-21
KCA104 : Discrete Mathematics
Course Outcome ( CO) Bloom’s Knowledge Level (KL)
At the end of course , the student will be able to
Use mathematical and logical notation to define and formally reason about basic
CO 1 K1, K2
discrete structures such as Sets, Relations and Functions
Apply mathematical arguments using logical connectives and quantifiers to check the
CO 2 K2,K3
validity of an argument through truth tables and propositional and predicate logic
CO 3 Identify and prove properties of Algebraic Structures like Groups, Rings and Fields K3, K4
CO 4 Formulate and solve recurrences and recursive functions K3, K4
CO 5 Apply the concept of combinatorics to solve basic problems in discrete mathematics K1, K3
DETAILED SYLLABUS 3-0-0
Unit Topic Proposed
Lecture
I Set Theory: Introduction, Size of sets and Cardinals, Venn diagrams, Combination of 08
sets, Multisets, Ordered pairs and Set Identities.
Relation: Definition, Operations on relations, Composite relations, Properties of
relations, Equality of relations, Partial order relation.
Functions: Definition, Classification of functions, Operations on functions,
Recursively defined functions.
II Posets, Hasse Diagram and Lattices: Introduction, Partial ordered sets, Combination 08
of Partial ordered sets, Hasse diagram, Introduction of lattices, Properties of lattices –
Bounded, Complemented, Modular and Complete lattice.
Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Boolean
functions. Simplification of Boolean functions, Karnaugh maps, Logic gates.
III Propositional: Propositions, Truth tables, Tautology, Contradiction, Algebra of 08
Propositions, Theory of Inference and Natural Detection.
Predicate Logic: Theory of Predicates, First order predicate, Predicate formulas,
Quantifiers, Inference theory of predicate logic.
IV Algebraic Structures:Introduction to algebraic Structures and properties. Types of 08
algebraic structures: Semi group, Monoid, Group, Abelian group and Properties of
group. Subgroup, Cyclic group, Cosets, Permutation groups, Homomorphism and
Isomorphism of groups.
Rings and Fields: Definition and elementary properties of Rings and Fields.
V Natural Numbers: Introduction, Piano’s axioms, Mathematical Induction, Strong 08
Induction and Induction with Nonzero Base cases.
Recurrence Relation & Generating functions: Introduction and properties of
Generating Functions. Simple Recurrence relation with constant coefficients and
Linear recurrence relation without constant coefficients. Methods of solving
recurrences.
Combinatorics: Introduction, Counting techniques and Pigeonhole principle,
Polya’s Counting theorem.
Suggested Readings:
1. Kenneth H. Rosen, "Discrete Mathematics and Its Applications", McGraw Hill, 2006.
2. B. Kolman, R.C Busby and S.C Ross, "Discrete Mathematics Structures", Prentice Hall ,2004.
3. R.P Girimaldi, "Discrete and Combinatorial Mathematics", Addison Wesley, 2004.
4. Y.N. Singh, "Discrete Mathematical Structures", Wiley- India, First edition, 2010.
5. Swapankumar Sarkar, "A Textbook of Discrete Mathematics”, S. Chand & Company PVT. LTD.V.
6. Krishnamurthy, "Combinatorics Theory & Application", East-West Press Pvt. Ltd., New Delhi.
7. Liptschutz, Seymour, "Discrete Mathematics", McGraw Hill.
8. J.P. Trembely&R.Manohar, "Discrete Mathematical Structure with application to Computer Science",
McGraw Hill.
AICTE Model Curriculum based Evaluation Scheme & Syllabus (I & II) 2020-21 Page 8
