Subject Code: CS2L001	Name: Discrete Structures	L-T-P: 3-1-0	Credit: 4
Pre-requisite(s): None
Set Theory: Paradoxes in set theory; inductive definition of sets and proof by induction; Peono postulates; Relations; representation of relations by graphs; properties of relations; equivalence relations and partitions; Partial orderings; Posets; Linear and well-ordered sets;Size of a set: Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schroeder-Bernstein theorem; Functions: injection and surjections; composition of functions; inverse functions; special functions; Algebraic structures and morphisms: Algebraic structures with one and two binary operations: semigroups, monoids, groups, rings, lattices, Boolean Algebra; Propositional logic: Syntax, semantics, validity of formulas, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments; soundness and completeness; Proof techniques: Proof by Induction, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency; First order Logic: Brief introduction; Basics of soundness and completeness; Introduction to graphs: Graphs and their basic properties - degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees. Text Books: Kenneth H. Rosen : Discrete Mathematics and Its Applications, Kenneth H. Rosen, McGraw Hill, 6th edition, 2007 J.P.Tremblay & R. Manohar, Discrete Mathematical Structure with Applications to Computer Science, Tata McGraw Hill, 2008. Reference Books: Norman L. Biggs, Discrete Mathematics, Oxford University Press, 2nd edition, 2002. Liu and Mahapatra, Elements of Discrete Mathematics, Tata McGraw Hill, 3rd edition, 2008.

Subject Code: CS2L001

Name: Discrete Structures

L-T-P: 3-1-0

Credit: 4

Pre-requisite(s): None

Set Theory: Paradoxes in set theory; inductive definition of sets and proof by induction;
Peono postulates; Relations; representation of relations by graphs; properties of relations; equivalence relations and partitions; Partial orderings; Posets; Linear and well-ordered sets;Size of a set: Finite and infinite sets, countable and uncountable sets, Cantor's diagonal argument and the power set theorem, Schroeder-Bernstein theorem; Functions: injection and surjections; composition of functions; inverse functions; special functions; Algebraic structures and morphisms: Algebraic structures with one and two binary operations: semigroups, monoids, groups, rings, lattices, Boolean Algebra; Propositional logic: Syntax, semantics, validity of formulas, satisfiable and unsatisfiable formulas, encoding and examining the validity of some logical arguments; soundness and completeness; Proof techniques: Proof by Induction, proof by contradiction, contrapositive proofs, proof of necessity and sufficiency; First order Logic: Brief introduction; Basics of soundness and completeness; Introduction to graphs: Graphs and their basic properties - degree, path, cycle, subgraphs, isomorphism, Eulerian and Hamiltonian walks, graph coloring, planar graphs, trees.

Text Books:

Kenneth H. Rosen : Discrete Mathematics and Its Applications, Kenneth H. Rosen, McGraw Hill, 6th edition, 2007
J.P.Tremblay & R. Manohar, Discrete Mathematical Structure with Applications to Computer Science, Tata McGraw Hill, 2008.

Reference Books:

Norman L. Biggs, Discrete Mathematics, Oxford University Press, 2nd edition, 2002.
Liu and Mahapatra, Elements of Discrete Mathematics, Tata McGraw Hill, 3rd edition, 2008.