# 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

Module 1-Notes

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 2-Notes

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

Module 3-Notes

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 4-Notes

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

Module 5-Notes

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.

Module 6-Notes

### Series Questions

R program to generate Hasse Diagram from Olympic medal tally

Infinities-PBS Video

Ted Talk: Magic of Fibonacci numbers

Origin of the term "coset"

Product of Poset - (Similar diagrams are obtained for Lattice and Boolean Algebra)

Abstract Algebra: Theory and Applications - (Book with Sage examples)

Cantors Dioganilization

Logic study guide