O'Regan G. Guide to Discrete Mathematics: An Accessible Introduction to the History, Theory, Logic and Applications

Springer, 2016. — 378 p. — (Texts in Computer Science). — ISBN 3-319-44560-X, 978-3-319-44560-1, 978-3-319-44561-8.The objective of this book is to give the reader a flavor of discrete mathematics and its applications to the computing field. The goal is provide a broad and accessible guide to the fundamentals of discrete mathematics, and to show how it may be applied to various areas in computing such as cryptography, coding theory, formal methods, language theory, computability, artificial intelligence, theory of databases, and software reliability. The emphasis is on both theory and applications, rather than on the study of mathematics for its own sake.
There are many existing books on discrete mathematics, and while many of these provide more in-depth coverage on selected topics, this book is different in that it aims to provide a broad and accessible guide to the reader, and to show the rich applications of discrete mathematics in a wide number of areas in the computing field.
Each chapter of this book could potentially be a book in its own right, and so there are limits to the depth of coverage for each chapter. However, the author hopes that this book will motivate and stimulate the reader, and encourage further study of the more advanced texts.Mathematics in CivilizationThe Babylonians
The Egyptians
The Greeks
The Romans
Islamic Influence
Chinese and Indian Mathematics
Review QuestionsSets, Relations and FunctionsSet Theory
Set Theoretical Operations
Properties of Set Theoretical Operations
Russell’s Paradox
Computer Representation of Sets
Relations.
Reflexive, Symmetric and Transitive Relations
Composition of Relations
Binary Relations
Applications of Relations
Functions
Application of Functions
Review QuestionsNumber TheoryElementary Number Theory
Prime Number Theory
Algorithms
Greatest Common Divisors (GCD)
Least Common Multiple (LCM)
Euclid’s Algorithm
Distribution of Primes
Theory of Congruences
Binary System and Computer Representation of Numbers
Review QuestionsMathematical Induction and RecursionStrong Induction
Recursion
Structural Induction
Review QuestionsSequences, Series, and Permutations and CombinationsSequences and Series
Arithmetic and Geometric Sequences
Arithmetic and Geometric Series
Simple and Compound Interest
Time Value of Money and Annuities
Permutations and Combinations
Review QuestionsAlgebraSimple and Simultaneous Equations
Quadratic Equations
Indices and Logarithms
Horner’s Method for Polynomials
Abstract Algebra
Monoids and Groups
Rings
Fields
Vector Spaces
Review QuestionsAutomata TheoryFinite-State Machines
Pushdown Automata
Turing Machines
Hybrid Automata
Review QuestionsMatrix TheoryTwo X Two Matrices
Matrix Operations
Determinants
Eigen Vectors and Values
Gaussian Elimination
Business Applications of Matrices
Review QuestionsGraph TheoryUndirected Graphs
Hamiltonian Paths
Trees
Binary Trees
Graph Algorithms
Graph Colouring and Four-Colour Problem
Review QuestionsCryptographyBreaking the Enigma Codes
Cryptographic Systems
Symmetric Key Systems
Public Key Systems
RSA Public Key Cryptosystem
Digital Signatures
Review QuestionsCoding TheoryMathematical Foundations
Simple Channel Code
Block Codes
Error Detection and Correction
Linear Block Codes
Parity Check Matrix
Binary Hamming Code
Binary Parity-Check Code
Miscellaneous Codes in Use
Review QuestionsLanguage Theory and SemanticsAlphabets and Words
Grammars
Backus Naur Form
Parse Trees and Derivations
Programming Language Semantics
Axiomatic Semantics
Operational Semantics
Denotational Semantics
Lambda Calculus
Lattices and Order
Partially Ordered Sets
Lattices
Complete Partial Orders
Recursion
Review QuestionsComputability and DecidabilityLogicism and Formalism
Decidability
Computability
Computational Complexity
Review QuestionsA Short History of LogicSyllogistic Logic
Paradoxes and Fallacies
Stoic Logic
Boole’s Symbolic Logic
Switching Circuits and Boolean Algebra
Application of Symbolic Logic to Digital Computing
Frege
Review QuestionsPropositional and Predicate LogicPropositional Logic
Truth Tables
Properties of Propositional Calculus
Proof in Propositional Calculus
Semantic Tableaux in Propositional Logic
Natural Deduction
Sketch of Formalization of Propositional Calculus
Applications of Propositional Calculus
Limitations of Propositional Calculus
Predicate Calculus
Sketch of Formalization of Predicate Calculus
Interpretation and Valuation Functions
Properties of Predicate Calculus
Applications of Predicate Calculus
Semantic Tableaux in Predicate Calculus
Review QuestionsAdvanced Topics in LogicFuzzy Logic
Temporal Logic
Intuitionist Logic
Undefined Values
Logic of Partial Functions
Parnas Logic
Dijkstra and Undefinedness
Logic and AI
Review QuestionsThe Nature of Theorem ProvingEarly Automation of Proof
Interactive Theorem Provers
A Selection of Theorem Provers
Review QuestionsSoftware Engineering MathematicsWhat is Software Engineering?
Early Software Engineering Mathematics
Mathematics in Software Engineering
Software Inspections and Testing
Process Maturity Models
Review QuestionsSoftware Reliability and DependabilitySoftware Reliability
Software Reliability and Defects
Cleanroom Methodology
Software Reliability Models
Dependability
Computer Security
System Availability
Safety-Critical Systems
Review QuestionsFormal MethodsDefinition 20.1 (Formal Specification)
Why Should We Use Formal Methods?
Comment 20.1 (Missile Safety)
Applications of Formal Methods
Tools for Formal Methods
Approaches to Formal Methods
Model-Oriented Approach
Axiomatic Approach
Comment 20.2 (Axiomatic Approach)
Proof and Formal Methods
The Future of Formal Methods
The Vienna Development Method
VDM♣, the Irish School of VDM
The Z Specification Language
The B Method
Predicate Transformers and Weakest Preconditions
The Process Calculi
The Parnas Way
Usability of Formal Methods
Why are Formal Methods difficult?
Characteristics of a Usable Formal Method
Review QuestionsZ Formal Specification LanguageSets
Relations
Functions
Sequences
Bags
Schemas and Schema Composition
Reification and Decomposition
Proof in Z
Review QuestionsStatisticsBasic Statistics
Abuse of Statistics
Statistical Sampling and Data Collection
Frequency Distribution and Charts
Statistical Measures
Arithmetic Mean
Mode
Median
Variance and Standard Deviation
Correlation and Regression
Regression
Statistical Inference and Hypothesis Testing
Review QuestionsProbability TheoryBasic Probability Theory
Laws of Probability
Bayes’ Formula
Random Variables
Binomial and Poisson Distributions
The Normal Distribution
Unit Normal Distribution
Confidence Intervals and Tests of Significance
The Central Limit Theorem
Bayesianism
Queueing Theory
Review QuestionsOperations ResearchLinear Programming
Linear Programming Example
General Formulation of LP Problem
Cost–Volume–Profit Analysis
Game Theory
Review QuestionsBasic Financial MathematicsSimple Interest
Computing Future and Present Values
Computing Future Value
Computing Present Values
Compound Interest
Present Value Under Compound Interest
Equivalent Values
Basic Mathematics of Annuities
Loans and Mortgages
Review Questions