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

Second Edition. — Springer, 2021. — 459 p. — (Texts in Computer Science). — ISBN 9783030815875, 3030815870.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.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