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.
Author(s): Gerard O'Regan
Series: Texts in Computer Science
Edition: 2
Publisher: Springer
Year: 2021
Language: English
Pages: 473
Tags: discrete mathematics; sets; relations; functions; number theory; induction; recursion; sequences; series; permutations; combinations; quadratic equations; monoids; groups; rings; integral domains; fields; vector spaces; automata theory; matrices; graph theory; cryptography; coding theory; language theory; computability; decidability;
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
