## Discrete Structures & Theory of Logic

UNIT I

Set Theory: Introduction, Combination of sets, Multisets, Ordered pairs. Proofs of some general identities on sets. Relations: Definition, Operations on relations, Properties of relations, Composite Relations, Equality of relations, Recursive definition of relation, Order of relations. Functions: Definition, Classification of functions, Operations on functions, Recursively defined functions. Growth of Functions Natural Numbers: Introduction, Mathematical Induction, Variants of Induction, Induction with Nonzero Base cases. Proof Methods, Proof by counter – example, Proof by contradiction.

UNIT II
Algebraic Structures: Definition, Groups, Subgroups and order, Cyclic Groups, Cosets, Lagrange’s theorem, Normal Subgroups, Permutation and Symmetric groups, Group
Homomorphisms, Definition and elementary properties of Rings and Fields.

UNIT III
Lattices: Definition, Properties of lattices – Bounded, Complemented, Modular and Complete lattice. Boolean Algebra: Introduction, Axioms and Theorems of Boolean algebra, Algebraic manipulation of Boolean expressions. Simplification of Boolean Functions, Karnaugh maps, Logic gates, Digital circuits and Boolean algebra.

UNIT IV
Propositional Logic: Proposition, well formed formula, Truth tables, Tautology, Satisfiability, Contradiction, Algebra of proposition, Theory of Inference. (8)
Predicate Logic: First order predicate, well formed formula of predicate, quantifiers, Inference theory of predicate logic.

UNIT V
Trees: Definition, Binary tree, Binary tree traversal, Binary search tree. Graphs: Definition and terminology, Representation of graphs, Multigraphs, Bipartite graphs,
Planar graphs, Isomorphism and Homeomorphism of graphs, Euler and Hamiltonian paths, Graph coloring, Recurrence Relation & Generating function: Recursive definition of functions, Recursive algorithms, Method of solving recurrences. Combinatorics: Introduction, Counting Techniques, Pigeonhole Principle