Skip to main content
main-content
Top

About this book

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: 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; examines the field of software engineering, describing formal methods; investigates probability and statistics.

Table of Contents

Chapter 1. Mathematics in Civilization

Abstract
Chapter 2 considers the contributions of early civilisations to the computing field, including the achievements of the Babylonians, Egyptians, Greeks, and Romans and the Islamic world. The Babylonian civilization flourished in Mesopotamia (in modern Iraq) from about 2000 B.C., until about 300 B.C., and they made important contributions to mathematics. The Egyptian Civilization developed along the Nile from about 4000 B.C., and their knowledge of mathematics allowed them to construct the pyramids at Giza as well as other impressive monuments. The Greek s made major contributions to western civilization including mathematics, logic and philosophy. The Golden Age of Islamic civilization was from 750 A.D. to 1250 A.D., and enlightened caliphs recognized the value of knowledge, and sponsored scholars to come to Baghdad to gather and translate the existing world knowledge into Arabic.
Gerard O’Regan

Chapter 2. Sets, Relations and Functions

Abstract
This chapter provides an introduction to fundamental building blocks in mathematics such as sets, relations and functions. Sets are collections of well-defined objects; relations indicate relationships between members of two sets A and B; and functions are a special type of relation where there is exactly (or at most) one relationship for each element aA with an element in B. A set is a collection of well-defined objects that contains no duplicates. A binary relation R (A, B) where A and B are sets is a subset of the Cartesian product (A × B) of A and B. The notation aRb signifies that there is a relation between a and b and that (a, b) ∈R. A total function f: AB is a special relation such that for each element a ∈ A there is exactly one element b ∈ B. This is written as f(a) = b. A partial function differs from a total function in that the function may be undefined for one or more values of A.
Gerard O’Regan

Chapter 3. Number Theory

Abstract
Number theory is the branch of mathematics that is concerned with the mathematical properties of the natural numbers and integers. These include properties such as the parity of a number; divisibility; additive and multiplicative properties; whether a number is prime or composite; the prime factors of a number; the greatest common divisor and least common multiple of two numbers; and so on. Number theory has many applications in computing: for example, the security of the RSA public key cryptographic system relies on the infeasibility of the integer factorization problem for large numbers. There are several unsolved problems in number theory: e.g., Goldbach’s Conjecture states that every even integer greater than two is the sum of two primes.
Gerard O’Regan

Chapter 4. Mathematical Induction and Recursion

Abstract
Mathematical induction Mathematical induction is an important proof technique used in mathematics, and it is often used to establish the truth of a statement for all natural numbers. There are two parts to a proof by induction, and these are the base step and the inductive step.
Gerard O’Regan

Chapter 5. Sequences, Series and Permutations and Combinations

Abstract
The goal of this chapter is to provide an introduction to sequences and series, including arithmetic and geometric sequences, and arithmetic and geometric series. We discuss the calculation of simple and compound interest , and the concept of the time value of money, and its application to determine the present value of a payment to be made in the future. We discuss annuities, which are a series of payments made at regular intervals over a period of time, and we determine the present value of an annuity. We discuss permutations and combinations, where a permutation is an arrangement of objects in a particular order, whereas the order of the elements is unimportant for a combination.
Gerard O’Regan

Chapter 6. Algebra

Abstract
Algebra is the branch of mathematics that uses letters in the place of numbers, where the letters stand for variables or constants that are used in mathematical expressions. Algebra is the study of such mathematical symbols and the rules for manipulating them, and it is a powerful tool for problem solving in science and engineering.
Gerard O’Regan

Chapter 7. Automata Theory

Abstract
Automata Theory is the branch of computer science that is concerned with the study of abstract machines and automata. These include finite-state machines, pushdown automata, and Turing machines. Finite-state machines are abstract machines that may be in one state at a time (current state), and the input symbol causes a transition from the current state to the next state. They have limited computational power due to memory and state constraints. Pushdown automata have greater computational power, and they contain extra memory in the form of a stack from which symbols may be pushed or popped. The Turing machine is the most powerful model for computation, and this theoretical machine is equivalent to an actual computer in the sense that it can compute exactly the same set of functions. The memory of the Turing machine is a tape that consists of a potentially infinite number of one-dimensional cells.
Gerard O’Regan

Chapter 8. Matrix Theory

Abstract
A matrix is a rectangular array of numbers that consists of horizontal rows and vertical columns. A matrix with m rows and n columns is termed an m × n matrix, where m and n are its dimensions. A matrix with an equal number of rows and columns is termed a square matrix. Various operations such as the addition and multiplication of matrices are considered, and the determinant and inverse of a matrix is discussed. The application of matrices to solving a set of linear equations using Gaussian elimination is considered.
Gerard O’Regan

Chapter 9. Graph Theory

Abstract
Graph theory is a practical branch of mathematics that deals with the arrangements of certain objects known as vertices (or nodes) and the relationships between them. It has been applied to practical problems such as the modelling of computer networks; determining the shortest driving route between two cities; the link structure of a website; the travelling salesman problem; and the four-colour problem.
Gerard O’Regan

Chapter 10. Cryptography

Abstract
The field of cryptography is concerned with techniques by which information may be concealed in cipher texts and made unintelligible to all but the intended recipient. This ensures the privacy of the information sent, as any information intercepted will be meaningless to anyone other than the recipient. It employs theoretical results from number theory to convert the original message (or plaintext) into cipher text that is then transmitted over a secure channel to the intended recipient. The cipher text is meaningless to anyone other than the intended recipient, and the recipient uses a key to decrypt the received cipher text and to read the original message.
Gerard O’Regan

Chapter 11. Coding TheoryCoding Theory

Abstract
Coding theory is a practical branch of mathematics concerned with the reliable transmission of information over communication channels. It includes theory and practical algorithms for error detection and correction, and it plays an important role in modern communication systems that require reliable and efficient transmission of information. An error correcting code encodes the data by adding a certain amount of redundancy to the message. This enables the original message to be recovered if a small number of errors have occurred.
Gerard O’Regan

Chapter 12. Language Theory and Semantics

Abstract
There are two key parts to any programming language, and these are its syntax and semantics . The syntax is the grammar of the language and a program needs to be syntactically correct with respect to its grammar. The semantics of the language is deeper, and determines the meaning of what has been written by the programmer. The compiler preserves the semantics of the language, where a compiler is a program that translates a program that is written in some programming language into another form. It involves syntax analysis and parsing to check the syntactic validity of the program; semantic analysis to determine what the program should do; optimization to improve the speed and performance; and code generation in some target language.
Gerard O’Regan

Chapter 13. Computability and Decidability

Abstract
A function f is computable if there exist an algorithm that produces the value of f correctly for each possible argument of f. The computation of f for a particular argument x just involves following the instructions in the algorithm, and it produces the result f(x) in a finite number of steps if x is in the domain of f. If x is not in the domain of f then the algorithm may produce an answer saying so or it might run forever never halting. The concept of computability may be made precise in several equivalent ways such as Church’s lambda calculus, recursive function theory or by the theoretical Turing machines. Church and Turing independently showed in 1936 that mathematics is not decidable: i.e. there is no mechanical procedure (i.e. algorithm) to determine whether an arbitrary mathematical proposition is true or false, and so the only way is to determine the truth or falsity of a statement is, try to solve the problem.
Gerard O’Regan

Chapter 14. A Short History of Logic

Abstract
Logic is concerned with reasoning and with establishing the validity of arguments. It allows conclusions to be deduced from premises according to logical rules, and the logical argument establishes the truth of the conclusion provided that the premises are true. The origins of logic are with the Greeks who were interested in the nature of truth. Aristotle developed syllogistic logic, where a syllogism consists of two premises and a conclusion. The Stoics developed an early form of propositional logic, where the assertibles (propositions) have a truth value such that at any time they are either true or false. Boole’s symbolic logic and its application to digital computing are discussed, and we consider Frege’s work on predicate logic.
Gerard O’Regan

Chapter 15. Propositional and Predicate Logic

Abstract
Propositional logic is the study of propositions, where a proposition is a statement that is either true or false. Propositionallogic may be used to encode simple arguments that are expressed in natural language, and to determine their validity. The validity of an argument may be determined from truth tables, or using the inference rules such as modus ponens to establish the conclusion via deductive steps. Predicate logic allows complex facts about the world to be represented, and new facts may be determined via deductive reasoning. Predicate calculus includes predicates, variables and quantifiers, and a predicate is a characteristic or property that the subject of a statement can have. The universal quantifier is used to express a statement such as that all members of the domain of discourse have property P, and the existential quantifier states that there is at least one value of x has property P.
Gerard O’Regan

Chapter 16. Advanced Topics in Logic

Abstract
We consider some advanced topics in logic including fuzzy logic, temporal logic, intuitionist logic, undefined values, logic and AI and theorem provers. Fuzzy logic is an extension of classical logic that acts as a mathematical model for vagueness. Temporal logic is concerned with the expression of properties that have time dependencies. Brouwer and others developed intuitionist logic as the logical foundation for intuitionism, which was a controversial theory of the foundations of mathematics based on a rejection of the law of the excluded middle and an insistence on constructive existence. We discuss several approaches that have been applied to dealing with undefined values that arise with partial functions including the logic of partial functions; Dijkstra’s approach with his cand and cor operators; and Parnas’s approach which preserves a classical two-valued logic.
Gerard O’Regan

Chapter 17. Software Engineering Mathematics

Abstract
This chapter provides an introduction to the important field of software engineering. The birth of the discipline was at the Garmisch conference in Germany in the late 1960s. Mathematics plays a key role in engineering, and it may potentially assist software engineers in delivering high-quality software products that are safe to use. However, it is important to recognize that while the use of mathematics is suitable for some areas of software engineering (especially in the safety and security critical fields), less rigorous techniques (such as software inspections and testing) are sufficient in most other areas of software engineering. The extent to which mathematics should be employed remains a topic of active debate.
Gerard O’Regan

Chapter 18. Formal Methods

Abstract
This chapter discusses formal methods, which consist of a set of mathematic techniques that provide an extra level of confidence in the correctness of the software. They consist of a formal specification language, and employ a collection of tools to support the syntax checking of the specification, as well as the proof of properties of the specification. They allow questions to be asked about what the system does independently of the implementation, and they may be employed to formally state the requirements of the proposed system, and to derive a program from its mathematical specification. They may be employed to provide a rigorous proof that the implemented program satisfies its specification, and they have been applied mainly to the safety critical field.
Gerard O’Regan

Chapter 19. Z Formal Specification Language

Abstract
Chapter 19 presents the Z specification language, which is one of the most widely used formal methods. Z is a formal specification language based on Zermelo set theory. It was developed at the Programming Research Group at Oxford University in the early 1980s. Z specifications are mathematical and employ a classical two-valued logic. The use of mathematics ensures precision, and allows inconsistencies and gaps in the specification to be identified. Theorem provers may be employed to demonstrate that the software implementation meets its specification.
Gerard O’Regan

Chapter 20. Probability, Statistics and Applications

Abstract
This chapter discusses probability and statistics and includes a discussion on discrete random variables; probability distributions; sample spaces; sampling; the abuse of statistics; variance and standard deviation; hypothesis testing. Statistics is an empirical science that is concerned with the collection, organization, analysis, interpretation and presentation of data. They allow the behaviour of a population to be studied and inferences to be made about the population. Probability is a way of expressing the likelihood of a particular event occurring, and the applications of probability to the software reliability field and queuing theory are briefly discussed.
Gerard O’Regan
Additional information