MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

UNIT-I

Mathematical Logic: Statements and notations, Connectives, Well formed formulas, Truth Tables, tautology, equivalence implication, Normal forms, Quantifiers, universal quantifiers

UNIT-II

Predicates: Predicative logic, Free & Bound variables, Rules of inference, Consistency, proof of contradiction, Automatic Theorem Proving.

UNIT-III

Relations: Properties of Binary Relations, equivalence, transitive closure, compatibility and partial ordering relations, Lattices, Hasse diagram. Functions: Inverse Function, Composition of functions, recursive Functions, Lattice and its Properties.

UNIT-IV

Algebraic structures: Algebraic systems Examples and general properties, Semi groups and monads, groups sub groups homomorphism, Isomorphism.

UNIT-V

Elementary Combinatory: Basis of counting, Enumerating Combinations & Permutations, with repetitions, Constrained repetitions, Binomial Coefficients, Binomial Multinomial theorems, the principles of Inclusion – Exclusion. Pigeon hole principles and its application

UNIT-VI

Recurrence Relation: Generating Functions and Sequences Calculating Coefficient of generating function, Recurrence relations, Solving recurrence relation by substitution and Generating functions. Characteristics roots, solution of In homogeneous Recurrence Relation.

UNIT-VII

Graph Theory: Representation of Graph, DFS, BFS, Spanning Trees, planar Graphs

UNIT-VIII

Graph Theory and Applications, Basic Concepts Isomorphism and Sub graphs, Multi graphs and Euler circuits, Hamiltonian graphs, Chromatic Numbers

TEXT BOOKS:

1. Elements of Discrete Mathematics- A computer Oriented Approach-   C L Liu, D P Mohapatra. Third Edition, Tata McGraw Hill.
2. Discrete Mathematics for Computer Scientists & Mathematicians, J.L. Mott, A. Kandel, T.P. Baker, PHI.

REFERENCES:

1. Discrete and Combinational Mathematics- An Applied Introduction-5th Edition – Ralph. P.Grimaldi.Pearson Education
2. Discrete Mathematics and its Applications, Kenneth H. Rosen, Fifth Edition.TMH.
3. Discrete Mathematical structures Theory and application-Malik & Sen, Cengage.
4. Discrete Mathematics with Applications, Thomas Koshy, Elsevier
5.  Logic and Discrete Mathematics, Grass Man & Trembley, Pearson Education.