OBJECTIVE: To develop logical thinking and introduce Basic Concepts.
1. SETS AND FUNCTIONS [10]
Sets, Subsets, Properties, De Morgan’s Law, Cartesian Product, Properties, Relation, Equivalence. Relation, Posets, Totally Ordered Sets, Well Ordered Sets, Transitive Closure of relations, Transitive and Reflexive closure of relation, Matrix representations of relations.
Function: Inductive, Subjective and Bijective function, Theorems related to function. Left and Right inverse of functions, Inverse of a function, Recursive Definitions, Recursive solution to problems. Math Inductions (Simple and strong) — Related Problems — Combinatorics.
2. GRAPHS [10]
Definition of a Simple Graph, Multigraph, Degree, Incidence, Fundamental theorems on degree, Paths, Walks, Trails, Cycles, Connectedness connected components and results, Isomorphism of graphs, complements of a graph and related results.
Matrix representation of graphs Adjacency and Incidence Matrices, Properties — Trees Equivalent properties of trees, Subgraphs, Spanning subgraphs, Spanning trees, Minimal Spanning tree Algorithms. Euler graph, Eulerian cycle graph and Eulerian path graph, Hamiltonian directed graphs, Directed paths strongly connectedness in directed graphs
3 MATHEMATICAL LOGIC [10]
Proposition Simple and compound Logical connectives, Truth Tables Tautology Contradiction Natural deduction rules Proofs in prepositional Calculus Resolution in prepositional logic Resolution Principle Problem Solving
Predicate Calculus: Quantifiers, Predicates, Functions, First order Languages, terms and well formed formulas scope of quantifiers Binding Substitution Rules of deduction in predicate logic resolution in predicate logic.
4 REGULAR GRAMMARS & FINITE AUTOMATA [10]
Alphabets Strings Languages grammars, Chomsky’s Hierarchy of grammars, language derived from a grammar Regular grammars regular expressions, equivalence Finite state Automata Deterministic and non deterministic, equivalence of the two Minimization of automata, Equivalence of Regular Languages and Finite state Automata Non regular languages
5. CONTEXT FREE GRAMMARS AND PDAS [10]
Context free grammars Chomsky s normal form and Griebach s normal form for context free grammars. Pushdown automata, acceptance by empty stack and final state, equivalence of the two,
Equivalence of CFL’s and PDA’s. Non-context free languages.
TEXT BOOKS
1. Arthur Gill, “Applied Algebra for Computer Science”, 1976, PHI
2. Narsingh Deo, “ Graph theory and application to Engineering and computer Science”,1986, PHI
3. Joshi K.D,” Foundations of Discrete Mathematics”, 1989, New Age International Ltd.
4. Gyorgy E. Revesz, “ Introduction to Formal Languages”, International Student Edition”,1986, Mcgraw Hill.
REFERENCES
1. Liu CL, “Elements of Discrete Mathematics”, 1985, McGraw Hill.
2. Seymour Lipschutz, “ Discrete Mathematics”, 1976, McGraw Hill.
3. J.P.Tremblay & R,Manohar, “Discrete Mathematical Structures”,1997, McGraw Hill International Edition.
