Syllabus
Course Title: Discrete Mathematics
Course code: BC23-103
LTP: 3-1-0
Credit: 4
Unit 1
Boolean algebra: Introduction of Boolean algebra, truth table, basic logic gate, basic postulates of Boolean algebra, principle of duality, canonical form, Karnaugh map.
Unit 2
Abstract algebra: Set, relation, group, ring, field.
Unit 3
Combinatorics: Basic counting, balls and bins problems, generating functions, recurrence relations. Proof techniques, principle of mathematical induction, pigeonhole principle.
Unit 4
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 5
Logic: Propositional calculus - propositions and connectives, syntax; Semantics - truth assignments 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.