Skip to main content
main-content
Top

About this book

This practically-oriented textbook presents an accessible introduction to discrete mathematics through a substantial collection of classroom-tested exercises. Each chapter opens with concise coverage of the theory underlying the topic, reviewing the basic concepts and establishing the terminology, as well as providing the key formulae and instructions on their use. This is then followed by a detailed account of the most common problems in the area, before the reader is invited to practice solving such problems for themselves through a varied series of questions and assignments.

Topics and features: provides an extensive set of exercises and examples of varying levels of complexity, suitable for both laboratory practical training and self-study; offers detailed solutions to many problems, applying commonly-used methods and computational schemes; introduces the fundamentals of mathematical logic, the theory of algorithms, Boolean algebra, graph theory, sets, relations, functions, and combinatorics; presents more advanced material on the design and analysis of algorithms, including asymptotic analysis, and parallel algorithms; includes reference lists of trigonometric and finite summation formulae in an appendix, together with basic rules for differential and integral calculus.

This hands-on study guide is designed to address the core needs of undergraduate students training in computer science, informatics, and electronic engineering, emphasizing the skills required to develop and implement an algorithm in a specific programming language.

Table of Contents

Chapter 1. Fundamentals of Mathematical Logic

The chapter gives an idea of mathematical logic, a science that studies mathematical proofs. Subjects of mathematical logic are mathematical proofs, methods and means for their construction.
The simplest division of mathematical logic is the propositional logic. Proposition is a statement that has a value of truth; i.e., it can be true or false. The respective values of truth will be denoted by T or F.
Compound proposition can be built out of atomic propositions using logical operations and brackets. The most common logical operations are:  and (conjunction or logical multiplication), or (disjunction or logical addition), if ... then (logical consequence or implication, this operation is also denoted as “\(\Rightarrow \)”), not (negation).
Statements about properties of variable x are called predicates and denoted: P(x), Q(x), ... Truth domain of a predicate is a collection of all x, for which the given predicate becomes a true proposition. The predicate properties are studied by predicate logic.
For construction of compound logical expressions we use quantifiers: \(\forall \) (for all)—universal quantifier—and \(\exists \) (exists)—existential quantifier. Quantifier is a logical operation that by predicate P(x) constructs a proposition that characterizes the truth domain P(x).
In this chapter, the main proof methods are described:
1.
forward reasoning;
 
2.
backward reasoning;
 
3.
method “by contradiction”.
 
Examples are considered to illustrate a powerful method for proving the truth of statements with respect to all natural numbers, the method of mathematical induction.
Sergei Kurgalin, Sergei Borzunov

Chapter 2. Set Theory

One of the fundamental concepts of mathematics is the notion of a set. A set is a collection of objects which we conceive as a whole. These objects are called elements of a set. The belonging of some element a to the set A can be denoted as follows: \(a\in A\). This record reads as follows: “a is an element of the set A” or “element a belongs to the set A.” If a does not belong to A, then we write \(a\notin A\).:
There are several ways to denote which elements belong to a set; the most common are the following:
(1) enumerating the elements \(A=\{a_1,a_2,\dots , a_n\}\). The elements of the set A are enclosed in braces and separated by commas.
(2) using the characteristic predicate \(A=\{x:P(x)\}\).
The characteristic predicate is a statement, allowing one to establish the fact that the object x belongs to the set A. If for some x the predicate P(x) takes a true value, then \(x\in A\); otherwise \(x\notin A\).
Some widely used sets have specific notations:
\(\mathbb {N}=\{1,2,3,\ldots \}\) is the set of natural numbers;
\(\mathbb {Z}=\{0,\pm 1,\pm 2,\pm 3,\ldots \}\) is the set of integers; :
\(\mathbb {Q}=\left\{ p/q:p, q\text { are integers},\;q\ne 0\right\} \) is the set of rational numbers.
A set of real numbers is denoted by \(\mathbb {R}=(-\infty ,+\infty )\) and of complex numbers by \(\mathbb {C}\).
Sergei Kurgalin, Sergei Borzunov

Chapter 3. Relations and Functions

Binary relation between the elements of the sets A and B is the subset R of the direct product \(A\times B\). It is said that R is the relation on A if \(A=B\). If R is some binary relation, then instead of notation \((x, y)\in R\) designation \(x\;R\;y\) is often used.
Let \(A=\{x_1, x_2, \dots , x_n\}\), \(B=\{y_1, y_2, \dots , y_m\}\). Logical matrix of the relation R on \(A\times B\) is defined as matrix M of size \(n\cdot m\), whose elements \(M_{ij}=\text {T}\), if \((x_i, y_j)\in R\), and \(M_{ij}=\text {F}\), if \((x_i, y_j)\notin R\).
A binary relationship between elements of finite sets can be represented by a listing of ordered pairs, using suitable predicates, as well as in the form of a logical matrix or a directed graph (digraph, see chapter “Graphs”). If at least one of the sets A or B is not finite, the relation \(R\subseteq A\times B\) can be specified with the help of predicates.
In this chapter, the equivalence relations of partial and linear order are considered. An important special case of relations are functions. Function from a set A to a set B is a binary relation, for which each element from A is associated with the only element from the set B.
An idea of the types of functions is given:
1.
injection;
 
2.
surjection;
 
3.
bijection.
 
The Pigeonhole Principle is formulated.
Sergei Kurgalin, Sergei Borzunov

Chapter 4. Combinatorics

Combinatorics solves the problems of counting the number of various configurations (e.g., permutations), formed by the elements of finite sets, on which various restrictions can be imposed. The number of configurations formed by the elements of the set is counted in accordance with the sum rule and the product rule.
The sum rule states that if \(A_1\), \(A_2\), ..., \(A_k\) are independent events, and there exists \(n_1\) of possible outcomes of the event \(A_1, n_2\) possible outcomes of the event \(A_2\), ..., \(n_k\) possible outcomes of the event \(A_k\), then the possible number of outcomes of the event “\(A_1~\mathbf{{or}}~A_2~\mathbf{{or}}\dots \mathbf{{or}}~A_k\)” is equal to the sum \(n_1+n_2+\cdots +n_k\).
The product rule states that if we have a sequence of k events with \(n_1\) possible outcomes of the first one, \(n_2\)—of the second one, and so on, up to \(n_k\) possible outcomes of the last one, then the total number of outcomes of the sequence of k events is equal to the product \(n_1\cdot n_2\cdot \cdots \cdot n_k\).
\(\left( n, k\right) \)-Sample or sample of volume k out of n elements is any set of elements \(x_1,x_2,\ldots , x_k\) out of the set A of cardinality n. And if the sequence of elements is of the essence, then the sample is called ordered, otherwise—unordered. An ordered \(\left( n, k\right) \)-sample with repeated elements is called \(\left( n, k\right) \)-permutation with repetitions, and without repeated elements \(\left( n, k\right) \)-permutation without repetitions.
The Newton’s binomial and polynomial expansion are considered.
Sergei Kurgalin, Sergei Borzunov

Chapter 5. Graphs

Graph is a pair \(G=\left( V,\;E\right) \), where V is a set of vertices (nodes), and E is a set of edges (arcs), connecting some pairs of vertices (nodes). A graph is said to be simple if it contains no loops (edges beginning and ending at the same vertex) and multiple edges (several edges are called multiple if they connect the same pair of vertices), and the sets V and E are finite. The figure where the graph vertices are shown as points, and edges are shown as segments or arcs, is called a diagram of a graph.
Two vertices u and v of a graph are adjacent is they are connected by an edge \({r=uv}\). In this case, it is said that the vertices u and v are endpoints of the edge r. If the vertex v is the endpoint of the edge r, then v and r are incident.
Directed graph or digraph is a pair \(D=(V, E)\), where V is a finite set of vertices, and E is a relation on V. Elements of the set E are called directed edges or arcs. An arc that connects a pair (uv) of vertices u and v of the digraph D is denoted by uv. A simple digraph contains no loops (i.e., acrs of the form uu) or multiple arcs.
Sergei Kurgalin, Sergei Borzunov

Chapter 6. Boolean Algebra

Boolean algebra is a set \(\mathbb {B}=\{0,1\}\) with defined on it operations of disjunction (\(\vee \)), conjunction (\(\wedge \)) and negation (\(\overline{ {a}}\)). Boolean variable p can take the values 0 or 1 (and only them), \(p\in \mathbb {B}\).
Boolean expression is formed by Boolean variables with the help of operations \(\vee \), \(\wedge \), \(\overline{ {a}}\) and brackets. The expression of the form \(x_1\wedge x_2\) is sometimes written in the form \(x_1\) &   \(x_2\) or simply \(x_1 x_2\).
The tuple \(\mathbf {x}=(x_1,x_2,\dots , x_n)\), where \(x_i\in \{0,1\}\), \(1\leqslant i\leqslant n\), is referred to the Boolean tuple (vector). The tuple elements are components or coordinates. The function \(f:\mathbb {B}^n\rightarrow \mathbb {B}\), where \(f(x_1,\dots , x_n)\) is Boolean expression, is called Boolean function.
The most important classes of Boolean functions are considered:
  • Functions that preserve constants 0 and 1.
  • Self-dual functions.
  • Linear functions.
  • Monotone functions.
For practical applications, an important task consists in reducing the Boolean function written in disjunctive normal form. One of the methods to solve this problem was developed by Karnaugh.
The methods of Boolean algebra are used for creation and analysis of combinational circuits, that allow understanding the structure and the logic of digital devices’ operation, including computers. Combinational circuits consist of electronic devices (called gates) with a finite number of inputs and outputs, and each input and output can have only two values of the signal.
Sergei Kurgalin, Sergei Borzunov

Chapter 7. Complex Numbers

Complex number z is an ordered pair of real numbers (ab), where \(a, b\in \mathbb {R}\). The first number a is called the real part of the complex number \(z=(a, b)\) and is denoted by symbol \(\mathrm {Re}\, z\), while the second number of the pair b is called the imaginary part z and is denoted by \(\mathrm {Im}\, z\).
A complex number of the form (a, 0), where the imaginary part is zero, is identified with the real number a, i.e., \((a, 0)\equiv a\). This allows considering the set of all real numbers \(\mathbb {R}\) as s subset of set of complex numbers \(\mathbb {C}\).
Two complex numbers \(z_1 = (a_1,b_1)\) and \(z_2 = (a_2,b_2)\) are considered equal if and only if their
real and imaginary parts are pairwise equal: \(z_1=z_2\Leftrightarrow a_1=a_2\), \(b_1=b_2\).
On the set \(\mathbb {C}\) the operations of addition and multiplication of complex numbers are defined. Sum of the complex numbers \(z_1 = (a_1,b_1)\) and \(z_2 = (a_2,b_2)\) is the complex number z, equal to \(z_1+z_2 = {(a_1+a_2,b_1+b_2)}\). Product of the numbers \(z_1 = (a_1,b_1)\) and \(z_2 = (a_2,b_2)\) is such a complex number \(z=(a, b)\), that \(a=a_1 a_2-b_1 b_2\), \(b=a_1 b_2+a_2 b_1\).
Fundamental theorem of algebra states that any polynomial of a zero degree with complex coefficients has a complex root. This is why an arbitrary polynomial with real (or complex) coefficients always has some root \(z\in \mathbb {C}\).
Sergei Kurgalin, Sergei Borzunov

Chapter 8. Recurrence Relations

Recurrence relation is the method of specifying the function f(n), \(n\in \mathbb {N}\), for which:
1.
values of the function f(n) for some subset
$$\begin{aligned} N_m=\{1,2,\dots , m\}\subset \mathbb {N} \end{aligned}$$
are specified in an explicit form:
$$\begin{aligned} f(1)=a_1, \; f(2)=a_2,\; \dots , \; f(m)=a_m; \end{aligned}$$
 
2.
values of the function for the arguments \(k\in \mathbb {N}\setminus N_m\) are expressed by the values f(i), where \(i=1,2,\dots , k-1\), in accordance with a specified rule.
 
The function constructed in this way is called recursive or recursively defined, and it is the solution of the recurrence relation. The set of values of the function f(n) is also referred to as the recursive sequence.
Let the recursive sequence \(\{a_n\}\) be defined. The sequence \(\{a_n\}\) is called the finite history sequence, if each subsequent term of the sequence explicitly depends on some fixed number of previous terms. If \(a_n\) depends on all \(a_i\), \(1\leqslant i\leqslant n-1\), then it is referred to as the full history sequence.
When analyzing algorithms, one quite often has to study the recursively defined sequences. The main methods for analyzing the recurrence relations are considered:
1.
method of substitution;
 
2.
method based on the solution of a characteristic equation;
 
3.
method of generating functions.
 
Sergei Kurgalin, Sergei Borzunov

Chapter 9. Concept of an Algorithm. Correctness of Algorithms

Algorithm is an exact prescription determining the computation process, leading from the varying source data to the sough result (data is the ordered set of characters). In other words, an algorithm describes the certain computation procedure, with the help of which the computation problem is solved. As a rule, an algorithm is used for solving some class of problems, rather than one certain problem.
Concept of an algorithm belongs to the basic, fundamental notions of mathematics. Many researchers use different wordings for the definition of an algorithm. However, all wordings explicitly or implicitly mean the following algorithm properties.
1.
Discreteness. An algorithm shall represent a problem-solving process as a consecutive execution of separate steps. Execution of each step of an algorithm requires some time, and each operation is performed only in full and cannot be performed partially.
 
2.
Elementary character of steps. The method of executing each command should be known and simple enough.
 
3.
Determinateness. Each subsequent step of the algorithm operation is uniquely defined. The result should be the same for the same source data.
 
4.
Directedness. It should be known, what is to be considered as the algorithm operation result.
 
5.
Mass character. There should be a possibility to apply the algorithm to all collections of source data from a certain predetermined set.
 
As an example, the Warshall algorithm, which is used for calculating the reachability matrix of a specified directed graph D(V, E), is considered.
Sergei Kurgalin, Sergei Borzunov

Chapter 10. Turing Machine

In order to formalize the concept of an algorithm, Turing suggested a mathematical model of a computing machine. Turing machine is an abstract-computing device consisting of a tape, a reading and printing head and a control device.
Let us consider some elements of a Turing machine in more detail.
1. Tape is divided into similar cells and is supposed to be unlimited on both sides. In other words, the number of cells in each certain moment of time is finite, but when necessary their number can be increased.
2. Reading and writing head moves along the tape and at each moment of time observes one cell of the tape. At this moment, the head reads the content of this cell and writes into it some symbol from the alphabet \(\Sigma \).
3. Control device at each moment of time is in some state \(q_i\); the set of all states \(Q=\{q_0, q_1, \dots , q_n\}\), \(n\geqslant 1\), is called the internal alphabet. Among all \(q_i\), \({0\leqslant i\leqslant n}\), initial and final states are distinguished. It is usually assumed that there exists one initial state, \(q_1\), and one final state, \(q_0\).
The Turing machine is not the only way to formalize the concept of an algorithm. Similar approaches are known, leading to equivalent results, among which we should mention the Post machine and the Markov normal algorithm.
Sergei Kurgalin, Sergei Borzunov

Chapter 11. Asymptotic Analysis

An important task of algorithm analysis is the estimation of the number of operations executed by the algorithm over a certain class of input data. The exact value of the number of elementary operations does not play any considerable role here, since it depends on the software implementation of the algorithm, the computer’s architecture, and other factors. This is why the algorithm’s performance indicator is the growth rate of this value with the growth of the input data volume.
For analysis of the algorithm’s efficiency, it is necessary to estimate the operation time of the computer that solves the set problem, as well as the volume of memory used. The estimate of the computation system operation time is usually obtained by calculating the elementary operations performed during calculations (such operations are referred to as basic). In a supposition that one elementary operation is executed within a strictly defined period of time, the function f(n), defined as the number of operations when calculating over the input data of size n, is called a time-complexity function.
Universal method of estimating the growth rate of functions, based on the Master Theorem, is given.
Sergei Kurgalin, Sergei Borzunov

Chapter 12. Basic Algorithms

The chapter is devoted to the methods of analysis of basic algorithms that are important for computer applications of discrete mathematics. The following algorithms are considered in detail:
1.
search algorithms (sequential, binary, Fibonaccian, interpolation search),
 
2.
sorting algorithms (insertion, bubble, shaker, selection, Shellsort, quicksort),
 
3.
algorithms for determining order statistics.
 
An idea of recursive algorithms is given.
In chapters “Concept of an Algorithm,” “Correctness of Algorithms,” and “Basic Algorithms” fragments of code are set in order to demonstrate the applicability of the studied methods in programming practice. Headings of some problems in chapter “Basic Algorithms” are in semi-bold; the above-mentioned problems are recommended to do in a computer lab.
Sergei Kurgalin, Sergei Borzunov

Chapter 13. Parallel Algorithms

A separate chapter is dedicated to parallel algorithms. Multiprocessor computing systems are extensively used at present for solving tasks on mathematical and computer modeling, management of database and complex software packages, etc. Furthermore, the majority of modern computing systems backup parallel computations on a hardware level. From this perspective, questions connected with construction and analysis of parallel algorithms are becoming increasingly relevant.
It should be pointed out that in many cases developing an effective parallel algorithm of solution of some task requires attraction of new ideas and methods comparing to creating sequential algorithms. These are, for instance, practically important problems of searching a target element in data structures, evaluation of an algebraic expression, etc. Theoretical part of this chapter takes a relatively bigger place in comparison with other chapters, as it deals with more complex issues of applied aspects of parallel programming, rather difficult when first studied. This chapter requires good command of methods of problem solution described in the previous chapters.
Sergei Kurgalin, Sergei Borzunov
Additional information