Syllabus - Discrete Mathematics (CB101)

Computer Science and Business System

Discrete Mathematics (CB101)

I Semester

Unit I

Boolean algebra

Introduction of Boolean algebra, truth table, basic logic gate, basic postulates of Boolean algebra, principle of duality, canonical form, Karnaugh map.

Unit II

Abstract algebra

Set, relation, group, ring, field.

Unit III

Combinatorics

Basic counting, balls and bins problems, generating functions, recurrence relations. Proof techniques, principle of mathematical induction, pigeonhole principle.

Unit IV

Graph Theory

Graphs and digraphs, complement, isomorphism, connectedness and reachability,adjacency matrix, Eulerian paths and circuits in graphs and digraphs, Hamiltonian paths and circuits in graphs and tournaments, trees; Planar graphs, Euler’s formula, dual of a planer graph, independence number and clique number, chromatic number, statement of Four-color theorem.

Unit V

Logic

Propositional calculus - propositions and connectives, syntax; Semantics - truthassignments and truth tables, validity and satisfiability, tautology; Adequate set of connectives; Equivalence and normal forms; Compactness and resolution; Formal reducibility - natural deduction system and axiom system; Soundness and completeness.

Practicals

Reference Books

  • Topics in Algebra, I. N. Herstein, John Wiley and Sons.

  • Digital Logic & Computer Design, M. Morris Mano, Pearson.

  • Elements of Discrete Mathematics, (Second Edition) C. L. LiuMcGraw Hill, New Delhi.

  • Graph Theory with Applications, J. A. Bondy and U. S. R. Murty, Macmillan Press, London.

  • Mathematical Logic for Computer Science,L. Zhongwan, World Scientific, Singapore.