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