Discrete Structures & Theory of Logic

Unit I

Set Theory, Relations, POSET & Lattices: Introduction, Combination of Sets. Relations — Definition, Operations, Properties, Composite Relations, Equality, Recursive Definition, Order of Relations. POSET & Lattices: Hasse Diagram, POSET, Definition & Properties of Lattices — Bounded, Complemented, Distributed, Modular and Complete Lattice.

Unit II

Functions & Boolean Algebra: Functions — Definition, Classification, Operations, Growth of Functions. Boolean Algebra — Axioms and Theorems, Algebraic Manipulation of Boolean Expressions, Simplification of Boolean Functions, Karnaugh Maps.

Unit III

Theory of Logics: Proposition, Truth Tables, Tautology, Satisfiability, Contradiction, Algebra of Propositions, Theory of Inference. Predicate Logic: First Order Predicate, Well-Formed Formula, Quantifiers, Inference Theory of Predicate Logic.

Unit IV

Algebraic Structures: Definition, Groups, Subgroups and Order, Cyclic Groups, Cosets, Lagrange's Theorem, Normal Subgroups, Permutation and Symmetric Groups, Group Homomorphisms, Rings and Fields — Definition and Elementary Properties.

Unit V

Graphs & Combinatorics: Graphs — Definition and Terminology, Representation, Multigraphs, Bipartite Graphs, Planar Graphs, Isomorphism and Homeomorphism, Euler and Hamiltonian Paths, Graph Coloring. Combinatorics: Counting Techniques, Pigeonhole Principle.