Mathematical Foundations of Computer Science

Description

Cover Half Title Title Page Copyright Page Preface Acknowledgement Table of Contents Chapter 1: Propositional Calculus 1.1 Statements and Notations 1.1.1 Subject and Predicate 1.1.2 Notation 1.2 Connectives and Truth Tables 1.2.1 Negation of a Statement 1.2.2 Conjunction (or meet) 1.2.3 Disjunction (or join) 1.2.4 Notation 1.2.5 Draw Truth Table for ''p ↑ q" 1.2.6 Draw the Truth Table for ''p ↓ q" 1.2.7 Statement Formulas and Truth Tables 1.2.8 Implication (or Conditional Statement) 1.2.9 Biconditional (or Double Implication) 1.2.10 Construction of the Truth Table for p ⇆ q 1.2.11 Well Formed Formulas 1.2.12 The Operation ⊕ or Δ 1.3 Tautology and Contradiction 1.3.1 Tautology 1.3.2 Contradiction (or Fallacy) 1.3.3 Contingency 1.4 Equivalence of Statements/ Formulas 1.4.1 Statements/Formulas 1.4.2 Equivalent Formulas 1.5 Duality Law and Tautological Implication 1.5.1 Duality Law 1.5.2 Tautological Implications 1.5.3 Converse 1.5.4 Inverse 1.5.5 Contrapositive 1.5.6 Some Implications 1.6 Normal Forms 1.6.1 Decision Problem 1.6.2 DNF 1.6.3 How to Find DNF 1.6.4 CNF 1.6.5 Principal Disjunctive Normal Form (PDNF) 1.6.6 Black Box Method (to find PDNF) 1.6.7 Principal Conjunctive Normal Form (PCNF) 1.6.8 How to Find PCNF (by using truth table or through PDNF) 1.7 The Theory of Inference for Statement Calculus 1. 7.1 Tautology 1. 7.2 Validity using Truth Table 1.7.3 Rules of lnference 1.7.4 Some Implications 1.7.5 Some Equivalences 1.8 Consistency of Premises and Indirect Method of Proof 1.8.1 Indirect Method of Proof Exercises Chapter 2: Predicate Calculus 2.1 Predicate Logic 2.1.1 Predicate 2.1.2 2-place Predicate 2.1.3 m-place Predicate 2.1.4 Connectives 2.2 Statement Functions, Variables and Quantifiers 2.2.1 Combined Statements (or Connectives) 2.2.2 Quantifiers 2.2.3 Universal Quantifier 2.2.4 Existential Quantifier 2.2.5 The Universe of Discourse 2.3 Free and Bound Variable 2.4 Inference Theory for the Predicate Calculus 2.41 Universal Specification (US) 2.4.2 Universal Generalization (UG) 2.4.3 Existential Specification (ES) 2.4.4 Existential Generalization (EG) 2.4.5 Formulas with More than One Quantifier Exercises Chapter 3: Number Theory 3.1 Properties of Integers 31.1 Properties of Integers 3.1.2 Z (the set of lntegers) 3.2 Division Algorithm (or Division Theorem) 3.3 Greatest Common Divisor (GCD) 3.4 Euclidian Algorithm 3.5 Least Common Multiple 3.6 Testing for Prime Numbers 3.7 Fundamental Theorem of Arithmetic (or Unique Factorization Theorem) 3.8 Modular Arithmatic 3.9 Fennats Theorem 3.9.1 Corollary Exercises Chapter 4: Mathematical Induction 4.1 The Principle of Mathematical Induction 4.1.1 The Principle Exercises Chapter 5: Set Theory 5.1 Sets 5.1.1 Set 5.1.2 Sub Set 5.1.3 Equity of Sets 51.4 Powerset 5.1.5 Notations 5.2 Operations on Sets 5.2.1 Union and Intersection 5.2.2 Properties of Union and Intersection 5.2.3 Symmetric Difference 5.2.4 Set Complement 5.2.5 Cartesian Product 5.2.6 Disjoint Sets 5.2. 7 Distributive Laws 5.2.8 Properties Related to Set Operations 5.2.9 Venn Diagrams 5.3 Principle of Inclusion and Exclusion 5.3.1 Principle 5.4 Relations, Binary Operations on Relations and Properties of Binary Relations 5.4.1 Domain and Range 5.4.2 Notation 5.4.3 Some Binary Operations on Relations 5.4.4 Properties of Relations 5.4.5 Composition of Relations 5.4.6 Notation 5.5 Relation Matrix and the Graph of a Relation 5.5.1 Some Properties of Relation Matrices 5.5.2 Pictorial Representation 5.5.3 Properties of the Graph of a Relation 5.6 Partition, Covering of a Set; and Equivalence Relations 5.6.1 Equivalence Relations 5.6.2 Equivalence Class 5.7 Transitive Closure 5. 7.1 Properties of Transitive Closure 5.7.2 Representation of Closure Relations in the Form of Matrices 5.8 Compatibility Relations 5.8.1 Definition: (Maximal Compatibility Block) 5.8.2 Composition of Binary Relation 5.9 Partial Order Relations 5.9.1 Zorn's Lemma Exercises Chapter 6: Functions 6.1 Definition and Examples of Functions 6.2 Types of Functions (including Bijective Functions) 6.2.1 Observation 6.2.2 Geometric Interpretation 6.2.3 Properties 6.2.4 Some Rules on Floor and Ceiling Functions 6.3 Composition of Functions and Inverse Functions 6.3.1 Observation 6.3.2 Notation 6.3.3 Definition 6.4 Permutation Functions 6.5 Recursive Functions 6.5.1 Theorem: (Recursion Theorem) 6.5.2 Observation Exercises Chapter 7: Graph Theory - I 7.1 Basic Concepts of Graphs 7.1.1 Example (Utilities Problem) 7.1.2 Observation 7.1.3 Example: Konigsberg Bridges (or Seven Bridges) 7.1.4 Properties of Konigsberg Bridges Graph 7.2 Sub graphs 7.2.1 Observations 7.3 Matrix Representation of Graphs 73.1 Incidence Matrices 7.4 Isomorphic Graphs Exercises Chapter 8: Graph Theory - II 8.1 Paths and Circuits 81.1 Corollary 8.2 Eularian Graphs 8.2.1 Corollary 8.3 Hamiltonian Graphs 8.3.1 Some Basic Rules for Constructing Hamiltonian Paths and Cycles 8.3.2 Corollary 8.3.3 Example (City-Route Puzzle) 8.3.4 Example (The Seating Arrangement Problem) 8.3.5 Travelling - Salesman Problem 8.4 Multiple Graphs Exercises Chapter 9: Graph Theory - Ill 9.1 Planar Graphs 9.1.1 Observation 9.2 Euler's Formula 9.2.1 Corollary 9.3 Graph Colouring, Covering and Chromatic Numbers 9.3.1 The Scheduling Problem 9.3.2 Rules for Graph Coloring Exercises Chapter 10: Graph Theory - IV 10.1 Fundamental Concepts of Trees 10.1.1 Note (Formation of Components) 10.1.2 Some Properties of Trees 10.1.3 Corollary 10.2 Directed Trees 10.3 Binary Trees and Decision Trees 10.3.1 Lemma 10.4 Spanning Trees and Properties 10.5 Algorithms for Spanning Trees 10.5.1 Breadth-First Search Algorithm (BFS): (for a Spanning Tree) 10.5.2 Depth-First Search Algorithm (DFS): (for a Spanning Tree) 10.5.3 Minimal Spanning Trees 10.5.4 Kruskal Algorithm: (Finding Shortest Spanning Tree) 10.5.5 Prim's Algorithm Exercises Chapter 11: Algebraic Structures 11.1 Some Algebraic Properties 11.2 Lattice as an Algebraic System 11.2.1 Properties of Lattices 11.3 Algebraic Systems with One Binary Operation 11.4 Properties of Binary Operations 11.4.1 Result 11.5 Semi Groups and Monoids 11.5.1 Observation 11.5.2 Result 11.5.3 Observations 11.6 Homomorphism of Semi Groups and Monoids 11.6.1 Definition 11.6.2 Result 11.6.3 Observation 11.6.4 Fundamental Theorem of Homomorphism Exercises Chapter 12: Algebraic Structures (Groups and Rings) 12.1 Fundamental Concepts in Group Theory 12.1.1 Result 12.2 Subgroups 12.2.1 Notation 12.3 Cosets 12.3.1 Remark 12.3.2 Theorem (Lagranges Theorem) 12.3.3 Remark 12.4 Rings 12.4.1 The Pigeon Hole Principle Exercises Chapter 13: Permutations and Combinations 13.1 Basic Counting Principles 13.1.1 Sum Rule 13. 1.2 General Rule for Counting Event (or Sum Rule) 13.1.3 Product Rule 13.1.4 Indirect Counting 13.1.5 One to One Correspondence 13.1.6 Applications to Computer Science 13.2 Permutations 13.2.1 Fundamental Principles of Counting 13.2.2 Permutations of Distinct Things 13.2.3 Permutations with Repetitions 13.2.4 Dearrangements 13.3 Circular Permutations, Restricted Permutations 13.3.1 Circular Permutations 13.3.2 Clockwise and Anticlockwise Permutations 13.3.3 Restricted Permutations 13.4 Combinations and Restricted Combinations 13.5 The Pigeonhole Principle and its Applications 13.5.1 The Extended Pigeonhole Principle Exercises Chapter 14: Binomial Theorem 14.1 Binomial and Multinomial Coefficients 14.1.1 Pascal's Triangle 14.1.2 Properties of Binomial Coefficients or Combinatorial Identities 14.1.3 Multinomial Coefficients 14.1.4 Multinomial Theorem 14.1.5 Multinomial Theorem - An Explanation 14.1.6 How to Find Number of Solutions of the Equation 14.2 Generating Functions of Permutations and Combinations 14.2.1 The Concept "Generating Function" 14.2.2 Properties of Generating Functions with Respect to Sum and Derivative 14.3 The Principle of Inclusion - Exclusion 14.3.1 Result 14.3.2 Principle of Inclusion-Exclusion for n-sets 14.3.3 Result Exercises Chapter 15: Recurrence Relations 15.1 Generating Function of Sequences 15.1.1 Generating Functions 15.2 Partial Fractions (Definition) 15.2.1 Partial Fractions 15.3 Calculating Coefficient of Generating Functions 15.3.1 Remark 15.3.2 Some Formulas (Special Cases of Binomial Theorem) 15.3.3 Geometric Series 15.3.4 A List of Formulas 15.4 Recurrence Relations and Formation of Recurrence Relation 15.4.1 Examples of Recurrence Relations 15.4.2 Some More Examples 15.4.3 Solutions of Recurrence Relations Exercises Chapter 16: Some Methods of Solving Recurrence Relations 16.1 Solving Linear Homogeneous Recurrence Relations by Substitution Method 16.1.1 Substitution Method 16.1.2 First Order Recurrence Relation 16.2 Generating Functions and the Method of Characteristic Roots 16.2.1 The Shifting Properties of Generating Functions 16.2.2 Sketch of the Method of Generating Functions 16.2.3 The Method of Characteristic Roots 16.3 Solving Inhomogeneous Recurrence Relations 16.3.1 Method Exercises Bibliography