Discrete Computational Structures-DCS CS201
MODULE - 1
Review of elementary set theory :
Algebra of sets – Ordered pairs and Cartesian products –Countable and Uncountable sets
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
Injective, Surjective and Bijective functions - Inverse of a function- Composition
MODULE - 2
Review of Permutations and combinations, Principle of inclusion exclusion, Pigeon Hole Principle,
Introduction- Linear recurrence relations with constant coefficients– Homogeneous solutions – Particular solutions – Total solutions
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
Propositions – Logical connectives – Truth tables
Tautologies and contradictions – Contra positive – Logical equivalences and implications
Rules of inference: Validity of arguments.
MODULE - 6
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.
Mathematical induction and its variants – Proof by Contradiction – Proof by Counter Example – Proof by Contra positive.
Download Full Note