**DCS NOTES S3 CS**

## 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

## 0 comments