DCS CS201 Full Note

Discrete Computational Structures CS201 Full Note

DCS Syllabus

Module-1

Review of elementary set theory :

Algebra of sets – Ordered pairs and Cartesian products –Countable and Uncountable sets

Relations :-

Relations on sets –Types of relations and their properties –Relational matrix and the graph of a relation – Partitions –Equivalence relations - Partial ordering- Posets – Hasse Diagrams - Meet and Join – Infimum and Supremum

Functions :-

Injective, Surjective and Bijective functions - Inverse of a function- Composition

Module-2

Review of Permutations and combinations, Principle of inclusion exclusion, Pigeon Hole Principle,Recurrence Relations:Introduction- Linear recurrence relations with constant coefficients– Homogeneous solutions – Particular solutions –Total solutions Algebraic systems:-Semigroups and monoids - Homomorphism, Subsemigroups and submonoids

Module-3

Algebraic systems (contd...):-Groups, definition and elementary properties, subgroups,Homomorphism and Isomorphism, Generators - Cyclic Groups,Cosets and Lagrange’s Theorem Algebraic systems with two binary operations- rings, fields-sub rings, ring homomorphism

Module-4

Lattices and Boolean algebra :-Lattices –Sublattices – Complete lattices – Bounded Lattices Complemented Lattices – Distributive Lattices – Lattice Homomorphisms.Boolean algebra – sub algebra, direct product and homomorphisms

Module-5

Propositional Logic:-Propositions – Logical connectives – Truth tables Tautologies and contradictions – Contra positive – Logical equivalences and implications Rules of inference: Validity of arguments.

Module-6

Predicate Logic:-Predicates – Variables – Free and bound variables – Universal and Existential Quantifiers – Universe of discourse.Logical equivalences and implications for quantified statements– Theory of inference : Validity of arguments.Proof techniques:Mathematical induction and its variants – Proof by Contradiction– Proof by Counter Example – Proof by Contra positive.

Download Full Note