Discrete Structure (BIT153HS)
Set theory, functions, mathematical reasoning and counting techniques, propositional and predicate logic, binary relations and directed graphs, graph theory and trees, partially ordered sets and lattices, algebraic structures, and finite automata, languages, and grammars.
Unit 1: Set Theory and Matrices3 hrs
- Sets, elements, set-builder notation, empty set, universal set, and power sets
- Set operations: union, intersection, set difference, symmetric difference, and complement
- Venn diagrams, set identities, algebraic laws of sets, and principle of duality
- Computer representation of sets using bit strings and bitwise Boolean operations
- Matrices: matrix addition, scalar multiplication, matrix multiplication, and transpose
- Zero-one matrices (Boolean matrices): join (OR), meet (AND), and Boolean product (circle dot) of zero-one matrices
Unit 2: Functions and Counting7 hrs
- Functions: domain, codomain, range, image, and preimage
- Classification of functions: Injection (one-to-one), Surjection (onto), and Bijection (one-to-one correspondence)
- Inverse functions, composition of functions, and associativity of composition
- Special functions: Floor function, ceiling function, and factorial function
- Basic counting principles: The Sum Rule, The Product Rule, The Subtraction Rule (Inclusion-Exclusion), and The Division Rule
- The Pigeonhole Principle: Classical form, generalized pigeonhole principle, and elegant combinatorial applications
- Permutations (ordered arrangements) and Combinations (unordered selections) without and with repetition
- Binomial theorem, Pascal's triangle, and algebraic identities involving binomial coefficients
Unit 3: Logic and Proofs6 hrs
- Propositional logic: propositions, truth values, and logical connectives (conjunction, disjunction, negation, implication, biconditional)
- Truth tables for compound propositions, converse, contrapositive, and inverse of conditional statements
- Propositional equivalences: Tautology, contradiction, contingency, logical equivalence, and De Morgan's laws for logic
- Predicates and quantifiers: Propositional functions, universal quantifier (forall), and existential quantifier (exists)
- Nested quantifiers, negation of quantified statements, and scope of quantifiers
- Rules of inference for propositional logic: Modus Ponens, Modus Tollens, Hypothetical Syllogism, Disjunctive Syllogism, and Resolution
- Methods of mathematical proof: Direct proof, proof by contraposition, proof by contradiction, and counterexamples
- The Principle of Mathematical Induction, basis step, inductive step, and strong induction with well-ordering principle
Unit 4: Relations and Digraphs8 hrs
- Binary relations: Definition, relations from set A to set B, and relations on a set A
- Properties of relations: Reflexive, irreflexive, symmetric, antisymmetric, and transitive relations
- Combining relations: Union, intersection, difference, and composition of relations
- Representation of relations: Matrix of a relation (zero-one matrix) and Directed Graphs (digraphs)
- Closures of relations: Reflexive closure, symmetric closure, and transitive closure
- Paths in directed graphs and connection to transitive closure
- Warshall's algorithm for computing transitive closures with time complexity analysis
- Equivalence relations, equivalence classes, congruence modulo m, and partitions of sets
Unit 5: Graph Theory and Trees8 hrs
- Graphs and graph models: Simple graphs, multigraphs, pseudographs, directed and undirected graphs
- Graph terminology: Degrees of vertices, Handshaking Lemma (sum of degrees = 2E), isolated and pendant vertices
- Special simple graphs: Complete graphs (K_n), Cycles (C_n), Wheels (W_n), Bipartite graphs, and Complete Bipartite graphs (K_{m,n})
- Representations of graphs: Adjacency matrices, incidence matrices, and adjacency lists
- Graph isomorphism and invariant properties
- Connectivity: Paths, cycles, connected components, cut-vertices, and cut-edges (bridges)
- Euler paths and Euler circuits: Euler's Theorem (all even degree vertices) and Fleury's algorithm
- Hamilton paths and Hamilton circuits: Dirac's theorem, Ore's theorem, and Traveling Salesperson Problem (TSP)
- Planar graphs, Euler's formula for planar graphs (V - E + R = 2), Kuratowski's theorem, and graph coloring (chromatic number)
- Trees: Definition, properties, rooted trees, m-ary trees, and binary trees
- Tree traversal algorithms: Preorder, Inorder, and Postorder traversals
- Spanning trees: Depth-First Search (DFS) and Breadth-First Search (BFS) spanning trees
- Minimum Spanning Trees (MST): Kruskal's greedy algorithm and Prim's algorithm with worked examples
Unit 6: Order Relations and Structures6 hrs
- Partially ordered sets (Posets): Definition (reflexive, antisymmetric, transitive) and formal notation (S, <=)
- Comparability and incomparability of poset elements, and totally ordered sets (chains)
- Hasse diagrams: Construction rules, removing reflexive loops and transitive edges
- Extremal elements in posets: Maximal elements, minimal elements, greatest element (maximum), and least element (minimum)
- Upper bounds, lower bounds, Least Upper Bound (LUB / Supremum / Join), and Greatest Lower Bound (GLB / Infimum / Meet)
- Well-ordered sets and the well-ordering theorem
- Lattices: Definition as posets where every pair has a unique LUB and GLB, and algebraic definition with meet and join operations
- Properties of lattices: Idempotent, commutative, associative, absorption, and modular laws
- Special lattices: Sublattices, bounded lattices, distributive lattices, and complemented lattices
- Boolean algebra as a complemented distributive lattice and isomorphism with switching circuits
Unit 7: Automata, Languages and Grammars7 hrs
- Formal languages: Alphabets, strings, string length, concatenation, prefix, suffix, and empty string
- Operations on languages: Union, intersection, concatenation, and Kleene star closure
- Phrase-structure grammars: Terminal symbols, non-terminals, start symbol, and production rules
- Chomsky hierarchy of grammars: Type 0 (Unrestricted), Type 1 (Context-sensitive), Type 2 (Context-free), Type 3 (Regular)
- Derivations, derivation trees (parse trees), and sentential forms
- Finite State Machines (FSM): State diagrams, state transition tables, and machines with output (Moore and Mealy machines)
- Deterministic Finite Automata (DFA): Formal 5-tuple definition (Q, Sigma, delta, q_0, F), language accepted by DFA, and string tracing
- Non-Deterministic Finite Automata (NFA): Definition, lambda/epsilon-transitions, and language acceptance
- Equivalence of DFA and NFA: The Subset Construction (powerset construction) algorithm to convert NFA to DFA
- Regular expressions, correspondence with regular languages, and Arden's theorem
- Pumping Lemma for regular languages: Statement, proof methodology, and application to prove languages non-regular
Reference books
- Kenneth H. Rosen, Discrete Mathematics and Its Applications (8th ed.), McGraw-Hill.
- Bernard Kolman, Robert C. Busby, and Sharon Cutler Ross, Discrete Mathematical Structures (6th ed.), Pearson.
- C.L. Liu and D.P. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach (4th ed.), McGraw-Hill.
- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (3rd ed.), Pearson.
- Peter Linz, An Introduction to Formal Languages and Automata (6th ed.), Jones & Bartlett Learning.