Mathematical Foundation of Computer Science

dharm

• 1 Discrete Theory, Relations and Functions Acknowledgements .............................................................................................................ix
  
  
  • 1.1 Introduction.........................................................................................................................
  
  
  • 1.2 Elementary Theory of Sets
  
  
  • 1.3 Set Rules & Sets Combinations..........................................................................................
    
    
    • 1.3.1 Rule of Equality......................................................................................................
    
    
    • 1.3.2 Study of Sets Combinations...................................................................................
    
    
    • 1.3.3 Power Set................................................................................................................
    
    
    • 1.3.4 Multisets.................................................................................................................
    
    
    • 1.3.5 Ordered Sets...........................................................................................................
    
    
    • 1.3.6 Cartesian Products.................................................................................................
    
    
    
    
  
  
  • 1.4 Relations
    
    
    • 1.4.1 Binary Relation......................................................................................................
    
    
    • 1.4.2 Equivalence Relation...........................................................................................
    
    
    • 1.4.3 Pictorial Representation of Relations.................................................................
    
    
    • 1.4.4 Composite Relation..............................................................................................
    
    
    • 1.4.5 Ordering Relation.................................................................................................
    
    
    
    
  
  
  • 1.5 Functions
    
    
    • 1.5.1 Classification of Functions...................................................................................
    
    
    • 1.5.2 Composition of Functions....................................................................................
    
    
    • 1.5.3 Inverse Functions.................................................................................................
    
    
    • 1.5.4 Recursively Defined Functions............................................................................
    
    
    
    
  
  
  • 11.6 Mathematical Induction & Piano’s Axioms.....................................................................
  
  
  
  


• 2 Discrete Numeric Functions and Generating Functions
  
  
  • 2.1 Introduction.......................................................................................................................
  
  
  • 2.2 Properties of Numeric Functions.....................................................................................
    
    
    • 2.2.1 Addition of Numeric Functions...........................................................................
    
    
    • 2.2.2 Multiplication of Numeric Functions..................................................................
    
    
    • 2.2.3 Multiplication with Scalar Factor to Numeric Function...................................
    
    
    • 2.2.4 Quotient of Numeric Functions...........................................................................
    
    
    • 2.2.5 Modulus of Numeric Function.............................................................................
    
    
    • 2.2.6 SI an and S–I an....................................................................................................... d:\N-com\TITLE.pm5 xi
    
    
    • 2.2.7 Accumulated Sum of Numeric Functions...........................................................
    
    
    • 2.2.8 Forward Difference & Backward Difference......................................................
    
    
    • 2.2.9 Convolution of Numeric Functions.....................................................................
    
    
    
    
  
  
  • 2.3 Asymptotic Behavior (Performance) of Numeric Functions...........................................
    
    
    • 2.3.1 Big—Oh (O) Notation...........................................................................................
    
    
    • 2.3.2 Omega (Ω) Notation.............................................................................................
    
    
    • 2.3.3 Theta (θ) Notation................................................................................................
    
    
    
    
  
  
  • 2.4 Generating Functions.......................................................................................................
  
  
  • 2.5 Application of Generating Function to Solve Combinatorial Problems.........................
  
  
  
  


• 3 Recurrence Relations with Constant Coefficients
  
  
  • 3.1 Introduction.......................................................................................................................
    
    
    • (Linear Recurrence Relation with Constant Coefficients LRRCC)................................ 3.2 Recurrence Relation for Discrete Numeric Functions
    
    
    
    
  
  
  • 3.3 Finding the Solution of LRRCC........................................................................................
    
    
    • 3.3.1 Method of Finding Homogenous Solution..........................................................
    
    
    • 3.3.2 Method of Finding Particular Solution...............................................................
    
    
    
    
  
  
  • 3.4 Alternate Method Finding Solution of LRRCC by Generating Function......................
  
  
  • 3.5 Common Recurrences from Algorithms...........................................................................
  
  
  • 3.6 Method for Solving Recurrences.......................................................................................
    
    
    • 3.6.1 Iteration Method..................................................................................................
    
    
    • 3.6.2 Master Theorem...................................................................................................
    
    
    • 3.6.3 Substitution Method............................................................................................
    
    
    
    
  
  
  • 3.7 Matrix Multiplication........................................................................................................
  
  
  
  


• 4 Algebraic Structure
  
  
  • 4.1 Introduction.......................................................................................................................
  
  
  • 4.2 Groups
  
  
  • 4.3 Semi Subgroup...................................................................................................................
  
  
  • 4.4 Complexes..........................................................................................................................
  
  
  • 4.5 Product Semi Groups........................................................................................................
  
  
  • 4.6 Permutation Groups..........................................................................................................
  
  
  • 4.7 Order of a Group................................................................................................................
  
  
  • 4.8 Subgroups..........................................................................................................................
  
  
  • 4.9 Cyclic Groups.....................................................................................................................
  
  
  • 4.10 Cosets.................................................................................................................................
  
  
  • 4.11 Group Mapping..................................................................................................................
  
  
  • 4.12 Rings...................................................................................................................................
  
  
  • 4.13 Fields..................................................................................................................................
  
  
  
  


• 5 Propositional Logic
  
  
  • 5.1 Introduction to Logic.......................................................................................................
  
  
  • 5.2 Symbolization of Statements..........................................................................................
  
  
  • 5.3 Equivalence of Formula.................................................................................................. d:\N-com\TITLE.pm5 xii
  
  
  • 5.4 Propositional Logic..........................................................................................................
    
    
    • 5.4.1 Well Formed Formula........................................................................................
    
    
    • 5.4.2 Immediate Subformula......................................................................................
    
    
    • 5.4.3 Subformula
    
    
    • 5.4.4 Formation Tree of a Formula............................................................................
    
    
    • 5.4.5 Truth Table.........................................................................................................
    
    
    
    
  
  
  • 5.5 Tautology.........................................................................................................................
  
  
  • 5.6 Theory of Inference.........................................................................................................
    
    
    • 5.6.1 Validity by Truth Table......................................................................................
    
    
    • 5.6.2 Natural Deduction Method................................................................................
    
    
    • 5.6.3 Analytical Tableaux Method (ATM)..................................................................
    
    
    
    
  
  
  • 5.7 Predicate Logic................................................................................................................
    
    
    • 5.7.1 Symbolization of Statements using Predicate..................................................
    
    
    • 5.7.2 Variables and Quantifiers..................................................................................
    
    
    • 5.7.3 Free and Bound Variables.................................................................................
    
    
    
    
  
  
  • 5.8 Inference Theory of Predicate Logic...............................................................................
  
  
  
  


• 6 Lattice Theory
  
  
  • 6.1 Introduction.....................................................................................................................
  
  
  • 6.2 Partial Ordered Set
  
  
  • 6.3 Representation of a Poset (Hasse Diagram)..................................................................
  
  
  • 6.4 Lattices
    
    
    • 6.4.1 Properties of Lattices.........................................................................................
    
    
    • 6.4.2 Lattices and Algebraic Systems........................................................................
    
    
    • 6.4.3 Classes of Lattices..............................................................................................
    
    
    • 6.4.4 Product of Lattices.............................................................................................
    
    
    • 6.4.5 Lattice Homomorphism.....................................................................................
    
    
    
    
  
  
  
  


• 7 Introduction to Languages and Finite Automata
  
  
  • 7.1 Basic Concepts of Automata Theory..............................................................................
    
    
    • 7.1.1 Alphabets............................................................................................................
    
    
    • 7.1.2 Strings.................................................................................................................
    
    
    • 7.1.3 Power of Σ
    
    
    • 7.1.4 Languages
    
    
    
    
  
  
  • 7.2 Deterministic Finite State Automata (DFA).................................................................
    
    
    • 7.2.1 Definition
    
    
    • 7.2.2 Representation of a DFA
    
    
    • 7.2.3 δ-head
    
    
    • 7.2.4 Language of a DFA
    
    
    
    
  
  
  • 7.3 Nondeterministic Finite State Automata (NFA)...........................................................
    
    
    • 7.3.1 Definition
    
    
    • 7.3.2 Representation
    
    
    • 7.3.3 δ-head
      
      
      • 7.3.4 Properties of δ-head............................................................................................ d:\N-com\TITLE.pm5 xiii
      
      
      • 7.3.5 Language of an NFA
      
      
      
      
    
    
    
    
  
  
  
  


• 8 Equivalence of NFA and DFA
  
  
  • 8.1 Relationship between NFA & DFA................................................................................
  
  
  • 8.2 Method of Conversion from NFA to DFA......................................................................
  
  
  • 8.3 Finite Automata with ∈-moves.......................................................................................
    
    
    • 8.3.1 NFA with ∈-moves.............................................................................................
    
    
    • 8.3.2 δ∈-head
    
    
    • 8.3.3 Language of NFA with ∈-moves........................................................................
    
    
    • 8.3.4 Method of Conversion from NFA with ∈-moves to NFA.................................
    
    
    • 8.3.5 Equivalence of NFA with ∈-moves to DFA.......................................................
    
    
    
    
  
  
  
  


• 9 Regular Expressions
  
  
  • 9.1 Introduction to Regular Expressions.............................................................................
  
  
  • 9.2 Definition of Regular Expression...................................................................................
  
  
  • 9.3 Equivalence of Regular Expression and Finite Automata...........................................
    
    
    • 9.3.1 Construction of NFA with ∈-moves from Regular Expression........................
    
    
    • 9.3.2 Construction of DFA from Regular Expression................................................
    
    
    
    
  
  
  • 9.4 Finite Automata to Regular Expression........................................................................
    
    
    • 9.4.1 Construction of DFA from Regular Expression................................................
    
    
    
    
  
  
  • 9.5 Construction of Regular Expression from DFA.............................................................
  
  
  • 9.6 Finite Automatons with Output.....................................................................................
    
    
    • 9.6.1 Melay Automaton...............................................................................................
    
    
    • 9.6.2 Moore Automaton...............................................................................................
    
    
    
    
  
  
  • 9.7 Equivalence of Melay & Moore Automatons.................................................................
    
    
    • (From Moore Machine-to-Melay Machine)....................................................... 9.7.1 Equivalent Machine Construction
    
    
    • 9.7.2 Melay Machine-to-Moore Machine....................................................................
    
    
    
    
  
  
  
  


• 10 Regular and Nonregular Languages
  
  
  • 10.1 Introduction.....................................................................................................................
  
  
  • 10.2 Pumping Lemma for Regular Languages......................................................................
  
  
  • 10.3 Regular and Nonregular Languages Examples............................................................
  
  
  • 10.4 Properties of Regular Languages...................................................................................
  
  
  • 10.5 Decision Problems of Regular Languages......................................................................
    
    
    • 10.5.1 Emptiness Problem............................................................................................
    
    
    • 10.5.2 Finiteness Problem.............................................................................................
    
    
    • 10.5.3 Membership Problem.........................................................................................
    
    
    • 10.5.4 Equivalence Problem..........................................................................................
    
    
    • 10.5.5 Minimization Problem and Myhill Nerode Theorem (Optimizing DFA)........
    
    
    
    
  
  
  • 11 Non-Ragular Grammars d:\N-com\TITLE.pm5 xiv
    
    
    • 11.1 Introduction.....................................................................................................................
    
    
    • 11.2 Definition of the Grammar.............................................................................................
    
    
    • 11.3 Classification of Grammars—Chomesky’s Heirarchy...................................................
    
    
    • 11.4 Sentential Form...............................................................................................................
    
    
    • 11.5 Context Free Grammars (CFG) & Context Free Languages (CFL)
    
    
    • 11.6 Derivation Tree (Parse Tree)..........................................................................................
      
      
      • 11.6.1 Parse Tree Construction....................................................................................
      
      
      
      
    
    
    • 11.7 Ambiguous Grammar......................................................................................................
      
      
      • 11.7.1 Definition
      
      
      • 11.7.2 Ambiguous Context Free Language..................................................................
      
      
      
      
    
    
    • 11.8 Pushdown Automaton.....................................................................................................
    
    
    • 11.9 Simplification of Grammars...........................................................................................
    
    
    
    
  
  
  
  


• 11.10 Chomsky Normal Form...................................................................................................


• 11.11 Greibach Normal Form...................................................................................................


• 11.12 Pumping Lemma for CFLs..............................................................................................


• 11.13 Properties of Context Free Languages...........................................................................


• 11.14 Decision Problems of Context Free Languages.............................................................


• 11.15 Undecided Problems of Context Free Languages.........................................................
  
  
  • 12 Introduction to Turning Machine
    
    
    • 12.1 Introduction.....................................................................................................................
    
    
    • 12.2 Basic Features of a Turing Machine..............................................................................
      
      
      • 12.2.1 Abstract View of a Turing Machine..................................................................
      
      
      • 12.2.2 Definition of a Turing Machine.........................................................................
      
      
      • 12.2.3 Instantaneous Description of a Turing Machine..............................................
      
      
      • 12.2.4 Representation of a Turing Machine................................................................
      
      
      
      
    
    
    • 12.3 Language of a Turing Machine.......................................................................................
    
    
    • 12.4 General Problems of a Turing Machine.........................................................................
    
    
    • 12.5 Turing Machine is the Computer of Natural Functions...............................................
      
      
      • A.1 Introduction..................................................................................................................... Appendix—Boolean Algebra
      
      
      • A.2 Definition of Boolean Algebra.........................................................................................
      
      
      • A.3 Theorems of Boolean Algebra.........................................................................................
      
      
      • A.4 Boolean Functions...........................................................................................................
      
      
      • A.5 Simplification of Boolean Functions..............................................................................
      
      
      • A.6 Forms of Boolean Functions...........................................................................................
      
      
      • A.7 Simplification of Boolean Functions Using K-map.......................................................