Discrete Mathematics (CB101)-Computer Science and Business System (I Semester) | RGPV
-
Syllabus
-
Syllabus - Discrete Mathematics (CB101)
-
Unit I - Boolean algebra
-
Introduction of Boolean algebra
-
Truth table and basic logic gate
-
Basic postulates of Boolean algebra
-
Principle of duality
-
Canonical form and Karnaugh map
-
Unit II - Abstract algebra
-
Set and relation
-
Group, ring, field
-
Unit III - Combinatorics
-
Basic counting and balls and bins problems
-
Generating functions and recurrence relations
-
Proof techniques and 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 - 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