Discrete Structures & Theory of Logic dstl (KCS303) syllabus Aktu
UNIT 1: Set Theory, Relations, Natural Numbers
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 counterexample, Proof by contradiction.
UNIT 2: Algebraic Structures:
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 3: Lattices:
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, Logicgates, Digital circuits and Boolean algebra.
UNIT 4: Propositional Logic, Predicate Logic:
Propositional Logic:Proposition, well formed formula, Truth tables, Tautology, Satisfiability,
Contradiction, Algebra of proposition, Theory of Inference. Predicate Logic: First order predicate, well formed formula of predicate, quantifiers, Inference
theory of predicate logic.
UNIT 5: Trees, Graphs, Combinatorics
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
Post a Comment