Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications

Description

This stimulating textbook presents a broad and accessible guide to the fundamentals of discrete mathematics, highlighting how the techniques may be applied to various exciting areas in computing. The text is designed to motivate and inspire the reader, encouraging further study in this important skill.   Features: This book provides an introduction to the building blocks of discrete mathematics, including sets, relations and functions; describes the basics of number theory, the techniques of induction and recursion, and the applications of mathematical sequences, series, permutations, and combinations; presents the essentials of algebra; explains the fundamentals of automata theory, matrices, graph theory, cryptography, coding theory, language theory, and the concepts of computability and decidability; reviews the history of logic, discussing propositional and predicate logic, as well as advanced topics such as the nature of theorem proving; examines the field of software engineering, including software reliability and dependability and describes formal methods; investigates probability and statistics and presents an overview of operations research and financial mathematics. Preface Overview Organization and Features Audience Contents 1 Mathematics in Civilization 1.1 Introduction 1.2 The Babylonians 1.3 The Egyptians 1.4 The Greeks 1.5 The Romans 1.6 Islamic Influence 1.7 Chinese and Indian Mathematics 1.8 Review Questions 1.9 Summary References 2 Sets, Relations and Functions 2.1 Introduction 2.2 Set Theory 2.2.1 Set Theoretical Operations 2.2.2 Properties of Set Theoretical Operations 2.2.3 Russell’s Paradox 2.2.4 Computer Representation of Sets 2.3 Relations 2.3.1 Reflexive, Symmetric and Transitive Relations 2.3.2 Composition of Relations 2.3.3 Binary Relations 2.3.4 Applications of Relations 2.4 Functions 2.5 Application of Functions 2.6 Review Questions 2.7 Summary References 3 Number Theory 3.1 Introduction 3.2 Elementary Number Theory 3.3 Prime Number Theory 3.3.1 Algorithms 3.3.2 Greatest Common Divisors (GCD) 3.3.3 Least Common Multiple (LCM) 3.3.4 Euclid’s Algorithm 3.3.5 Distribution of Primes 3.4 Theory of Congruences 3.5 Binary System and Computer Representation of Numbers 3.6 Review Questions 3.7 Summary References 4 Mathematical Induction and Recursion 4.1 Introduction 4.2 Strong Induction 4.3 Recursion 4.4 Structural Induction 4.5 Review Questions 4.6 Summary Reference 5 Sequences, Series, and Permutations and Combinations 5.1 Introduction 5.2 Sequences and Series 5.3 Arithmetic and Geometric Sequences 5.4 Arithmetic and Geometric Series 5.5 Simple and Compound Interest 5.6 Time Value of Money and Annuities 5.7 Permutations and Combinations 5.8 Review Questions 5.9 Summary 6 Algebra 6.1 Introduction 6.2 Simple and Simultaneous Equations 6.3 Quadratic Equations 6.4 Indices and Logarithms 6.5 Horner’s Method for Polynomials 6.6 Abstract Algebra 6.6.1 Monoids and Groups 6.6.2 Rings 6.6.3 Fields 6.6.4 Vector Spaces 6.7 Review Questions 6.8 Summary Reference 7 Automata Theory 7.1 Introduction 7.2 Finite-State Machines 7.3 Pushdown Automata 7.4 Turing Machines 7.5 Hybrid Automata 7.6 Review Questions 7.7 Summary Reference 8 Matrix Theory 8.1 Introduction 8.2 Two × Two Matrices 8.3 Matrix Operations 8.4 Determinants 8.5 Eigen Vectors and Values 8.6 Gaussian Elimination 8.7 Business Applications of Matrices 8.8 Review Questions 8.9 Summary References 9 Graph Theory 9.1 Introduction 9.2 Undirected Graphs 9.2.1 Hamiltonian Paths 9.3 Trees 9.3.1 Binary Trees 9.4 Graph Algorithms 9.5 Graph Colouring and Four-Colour Problem 9.6 Review Questions 9.7 Summary References 10 Cryptography 10.1 Introduction 10.2 Breaking the Enigma Codes 10.3 Cryptographic Systems 10.4 Symmetric Key Systems 10.5 Public Key Systems 10.5.1 RSA Public Key Cryptosystem 10.5.2 Digital Signatures 10.6 Review Questions 10.7 Summary References 11 Coding Theory 11.1 Introduction 11.2 Mathematical Foundations 11.3 Simple Channel Code 11.4 Block Codes 11.4.1 Error Detection and Correction 11.5 Linear Block Codes 11.5.1 Parity Check Matrix 11.5.2 Binary Hamming Code 11.5.3 Binary Parity-Check Code 11.6 Miscellaneous Codes in Use 11.7 Review Questions 11.8 Summary References 12 Language Theory and Semantics 12.1 Introduction 12.2 Alphabets and Words 12.3 Grammars 12.3.1 Backus Naur Form 12.3.2 Parse Trees and Derivations 12.4 Programming Language Semantics 12.4.1 Axiomatic Semantics 12.4.2 Operational Semantics 12.4.3 Denotational Semantics 12.5 Lambda Calculus 12.6 Lattices and Order 12.6.1 Partially Ordered Sets 12.6.2 Lattices 12.6.3 Complete Partial Orders 12.6.4 Recursion 12.7 Review Questions 12.8 Summary References 13 Computability and Decidability 13.1 Introduction 13.2 Logicism and Formalism 13.3 Decidability 13.4 Computability 13.5 Computational Complexity 13.6 Review Questions 13.7 Summary References 14 A Short History of Logic 14.1 Introduction 14.2 Syllogistic Logic 14.3 Paradoxes and Fallacies 14.4 Stoic Logic 14.5 Boole’s Symbolic Logic 14.5.1 Switching Circuits and Boolean Algebra 14.6 Application of Symbolic Logic to Digital Computing 14.7 Frege 14.8 Review Questions 14.9 Summary References 15 Propositional and Predicate Logic 15.1 Introduction 15.2 Propositional Logic 15.2.1 Truth Tables 15.2.2 Properties of Propositional Calculus 15.2.3 Proof in Propositional Calculus 15.2.4 Semantic Tableaux in Propositional Logic 15.2.5 Natural Deduction 15.2.6 Sketch of Formalization of Propositional Calculus 15.2.7 Applications of Propositional Calculus 15.2.8 Limitations of Propositional Calculus 15.3 Predicate Calculus 15.3.1 Sketch of Formalization of Predicate Calculus 15.3.2 Interpretation and Valuation Functions 15.3.3 Properties of Predicate Calculus 15.3.4 Applications of Predicate Calculus 15.3.5 Semantic Tableaux in Predicate Calculus 15.4 Review Questions 15.5 Summary References 16 Advanced Topics in Logic 16.1 Introduction 16.2 Fuzzy Logic 16.3 Temporal Logic 16.4 Intuitionist Logic 16.5 Undefined Values 16.5.1 Logic of Partial Functions 16.5.2 Parnas Logic 16.5.3 Dijkstra and Undefinedness 16.6 Logic and AI 16.7 Review Questions 16.8 Summary References 17 The Nature of Theorem Proving 17.1 Introduction 17.2 Early Automation of Proof 17.3 Interactive Theorem Provers 17.4 A Selection of Theorem Provers 17.5 Review Questions 17.6 Summary References 18 Software Engineering Mathematics 18.1 Introduction 18.2 What is Software Engineering? 18.3 Early Software Engineering Mathematics 18.4 Mathematics in Software Engineering 18.5 Software Inspections and Testing 18.6 Process Maturity Models 18.7 Review Questions 18.8 Summary References 19 Software Reliability and Dependability 19.1 Introduction 19.2 Software Reliability 19.2.1 Software Reliability and Defects 19.2.2 Cleanroom Methodology 19.2.3 Software Reliability Models 19.3 Dependability 19.4 Computer Security 19.5 System Availability 19.6 Safety-Critical Systems 19.7 Review Questions 19.8 Summary References 20 Formal Methods 20.1 Introduction 20.1.1 Definition 20.1 (Formal Specification) 20.2 Why Should We Use Formal Methods? 20.2.1 Comment 20.1 (Missile Safety) 20.3 Applications of Formal Methods 20.4 Tools for Formal Methods 20.5 Approaches to Formal Methods 20.5.1 Model-Oriented Approach 20.5.2 Axiomatic Approach 20.5.3 Comment 20.2 (Axiomatic Approach) 20.6 Proof and Formal Methods 20.7 The Future of Formal Methods 20.8 The Vienna Development Method 20.9 VDM♣, the Irish School of VDM 20.10 The Z Specification Language 20.11 The B Method 20.12 Predicate Transformers and Weakest Preconditions 20.13 The Process Calculi 20.14 The Parnas Way 20.15 Usability of Formal Methods 20.15.1 Why are Formal Methods difficult? 20.15.2 Characteristics of a Usable Formal Method 20.16 Review Questions 20.17 Summary 21 Z Formal Specification Language 21.1 Introduction 21.2 Sets 21.3 Relations 21.4 Functions 21.5 Sequences 21.6 Bags 21.7 Schemas and Schema Composition 21.8 Reification and Decomposition 21.9 Proof in Z 21.10 Review Questions 21.11 Summary Reference 22 Statistics 22.1 Introduction 22.2 Basic Statistics 22.2.1 Abuse of Statistics 22.2.2 Statistical Sampling and Data Collection 22.3 Frequency Distribution and Charts 22.4 Statistical Measures 22.4.1 Arithmetic Mean 22.4.2 Mode 22.4.3 Median 22.5 Variance and Standard Deviation 22.6 Correlation and Regression 22.6.1 Regression 22.7 Statistical Inference and Hypothesis Testing 22.8 Review Questions 22.9 Summary References 23 Probability Theory 23.1 Introduction 23.2 Basic Probability Theory 23.2.1 Laws of Probability 23.2.2 Bayes’ Formula 23.3 Random Variables 23.4 Binomial and Poisson Distributions 23.5 The Normal Distribution 23.5.1 Unit Normal Distribution 23.5.2 Confidence Intervals and Tests of Significance 23.5.3 The Central Limit Theorem 23.6 Bayesianism 23.7 Queueing Theory 23.8 Review Questions 23.9 Summary References 24 Operations Research 24.1 Introduction 24.2 Linear Programming 24.2.1 Linear Programming Example 24.2.2 General Formulation of LP Problem 24.3 Cost–Volume–Profit Analysis 24.4 Game Theory 24.5 Review Questions 24.6 Summary References 25 Basic Financial Mathematics 25.1 Introduction 25.2 Simple Interest 25.2.1 Computing Future and Present Values 25.2.2 Computing Future Value 25.2.3 Computing Present Values 25.3 Compound Interest 25.3.1 Present Value Under Compound Interest 25.3.2 Equivalent Values 25.4 Basic Mathematics of Annuities 25.5 Loans and Mortgages 25.6 Review Questions 25.7 Summary Glossary Index