Topic

No. of hours

Lecture

Tutorial/Practical

1.Mathematical Logic: Statements, Connectives, Statement Variables and Formulas, Tautologies, Equivalences and Implications, Disjunctive and Conjunctive Normal Forms, Inference Theory in Statement Logic, Indirect Proofs, Automatic Deduction due to Hao Wang, First Order Predicate Logic, Inference Theory in Predicate Logic, Prenex Normal Form, Herbrand's Theorem, Resolution Priciple.

9

3

-

2. Relations and Functions: Boolean Matrices, Join, Meet and Boolean Product, Directed Graphs, Matrix and Digraph representations of Relations, Paths and Connectivity, Transitive Closures, Warshall's Algorithm, Growth of Functions Recursive Functions.

9

3

-

3. Lattices and Boolean Algebra: Partially Ordered Sets, Lattices, Modular and Distributive Lattices, Complements, Boolean Algebra, Stone Representation Theorem for Finite Boolean Algebras, Boolean Functions, Free Boolean Algebras, Relationship with Statement Logic.

9

3

-

4. Combinatorics: Permutations and Combinations, Permutations and Combinations with repetitions Ordered and Unordered Partitions, Sterling Numbers of First and Second Kind, Partition Functions, Linear Recurrence Relations(Difference Equations), Solution by Characteristic Roots, Generating Functions.

9

3

-

5. Graphs and Trees: Graphs, Eulerian and Hamiltonian Graphs, Graph Colourings, Trees, Tree Searching, Minimal Spanning Trees, Prim's and Kruskal's Algorithms.

6

21

-