CS 201 Discrete Computational Structures Full Note

Discrete Computational Structures-DCS CS201

Full Note

Content:-

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

Click Here