DISCRETE COMPUTATIONAL STRUCTURES
Class Notes
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
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
Algebraic systems (contd...):- Groups, definition and elementary properties, subgroups, Homomorphism and somorphism, Generators - Cyclic Groups, Cosets and Lagrange’s Theorem Algebraic systems with two binary operations- rings, fields-sub rings, ring homomorphism
Lattices and Boolean algebra :- Lattices –Sublattices – Complete lattices – Bounded Lattices - Complemented Lattices – Distributive Lattices – Lattice Homomorphisms. Boolean algebra – sub algebra, direct product and homomorphisms
Propositional Logic:-Propositions – Logical connectives – Truth tables, Tautologies and contradictions – Contra positive – Logical equivalences and implications Rules of inference: Validity of arguments.
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.
Assignment Questions
Series Questions
[Series 1] [Answer Key]
[Series 2 ] [Answer Key]
[Series 2-2017 ] [Answer Key-2017]
Useful Links
R program to generate Hasse Diagram from Olympic medal tally
Ted Talk: Magic of Fibonacci numbers
Product of Poset - (Similar diagrams are obtained for Lattice and Boolean Algebra)
Abstract Algebra: Theory and Applications - (Book with Sage examples)