Course‎ > ‎

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

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


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

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

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

Module 5

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.


Links

R program to generate Hasse Diagram from Olympic medal tally

Infinities-PBS Video

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

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


Assignment Questions




Questions
[Series 1] [Answer Key]
[Series 2 ] [Answer Key]
Ċ
Jestin Joy,
Oct 17, 2016, 2:47 AM
Ċ
first.pdf
(112k)
Jestin Joy,
Sep 3, 2016, 6:28 AM
Ċ
Jestin Joy,
Sep 3, 2016, 6:28 AM
Ċ
mod1.pdf
(238k)
Jestin Joy,
Oct 20, 2016, 9:59 PM
Ċ
mod2.pdf
(195k)
Jestin Joy,
Nov 24, 2016, 9:36 PM
Ċ
Jestin Joy,
Oct 8, 2016, 6:37 AM
Ċ
Jestin Joy,
Oct 20, 2016, 9:53 PM
Ċ
Jestin Joy,
Jul 10, 2017, 11:49 PM
Ċ
mod6.pdf
(163k)
Jestin Joy,
Nov 24, 2016, 9:19 PM
Ċ
second.pdf
(115k)
Jestin Joy,
Oct 22, 2016, 7:45 PM
Ċ
Jestin Joy,
Oct 22, 2016, 7:45 PM
Comments