Verify Account

SYLLABUS

Unit-I

Statements and Notation, Connectives: Negation, Conjunction, Disjunction, Conditional and Bi-conditional, Statement Formulas and Truth Tables. Well-formed Formulas, Tautologies, Equivalence of Formulas, Duality Law, Tautological Implications. Normal Forms: Disjunctive Normal Forms, Conjunctive Normal Forms, Principal Disjunctive Normal Forms (PDNF), Principal Conjunctive Normal Forms (PCNF), Ordering and Uniqueness of Normal Forms. The Theory of Inference for the Statement Calculus: Rules of Inference, Consistency of Premises and Indirect Method of Proof. The Predicate Calculus, Inference Theory of the Predicate Calculus.

UNIT-II

Set Theory: Basic Concepts of Set Theory, Representation of Discrete Structures, Relations and Ordering, Functions, Recursion. Lattices and Boolean algebra: Lattices as Partially Ordered Sets, Boolean Algebra, Boolean Functions, Representation and Minimization of Boolean Functions. Algebraic Structures: Algebraic Systems: Examples and General Properties, Semi Groups and Monoids, Groups.

UNIT-III

Elementary Combinatorics: Basics of Counting, Combinations and Permutations, Enumeration of Combinations and Permutations, Enumerating Combinations and Permutations with Repetitions, Enumerating Permutations and Combinations with Constrained Repetitions, Binomial Coefficients, The Binomial and Multinomial Theorems, The Principle of Inclusion and Exclusion.

UNIT-IV

Recurrence Relations: Generating Functions of Sequences, Calculating Coefficients of Generating Functions, Recurrence Relations, Solving Recurrence Relations by Substitution and Generating Functions, The method of Characteristic Roots, Solution of Inhomogeneous Recurrence Relations.

UNIT-V

Graphs: Basic Concepts, Isomorphism and Sub Graphs, Trees and their Properties, Spanning Trees, Directed Trees, Binary Trees, Planar Graphs, Euler’s Formula, Multigraphs and Euler Circuits, Hamiltonian Graphs, Chromatics Number, The Four-Color Problem.