2K6CS 303 : DISCRETE COMPUTATIONAL STRUCTURES

Module I: Logic (13 hours)
Prepositional Logic – Logical arguments – Consistency completeness and independence – Formal proofs – Natural deduction – Soundness, completeness and compactness theorems – Predicate logic – Completeness -Resolution – Unification algorithm
Module II: Relational structures (13 hours)
Sets relations and functions – Pigeonhole principle – Cardinals – Countable and uncountable sets – Digonalization – Equivalence relations and partitions – Partial order – Lattices and Boolean algebra
Module III: Group theory (13 hours)
Groups and subgroups – Products and quotients – Homomorphism theorems – Cosets and normal subgroups – Lagrange’s theorem – Permutation groups – Cayley’s theorem – Hamming Codes and Syndrome decoding
Module IV: Rings and fields (13 hours)
Rings, integral domains and fields – Ideals and quotient rings – Euclidean domains – Polynomial rings and division algorithm – Factorization and unique factorization – Irreducibility – Field properties and extensions – Ruler and compass constructions – Introduction to cyclic codes

Text books
1. Truss J.K., Discrete Mathematics for Computer Scientists, Addison Wesley (Modules I & II)
2. Kolman B. & Busby R.C., Discrete Mathematical Structures for Computer Science, Prentice Hall of India (Modules III & IV)
Reference books
1. Liu C.L., Elements of Discrete Mathematics, McGraw Hill
2. Grimaldi P., Discrete & Combinatorial Mathematics, Addison Wesley
3. Tremblay, J P., Manohar R – Discrete Mathematical Structures to Applications to Computer Science –
Tata McGraw-Hill