Discrete Math. For students of technical specialties

Discrete Math

For students of technical specialties

Ivan Treshchev

Assistnt Anastasiya Sergeevna Vatolina

© Ivan Treshchev, 2020

ISBN 978-5-4498-7601-0

Created with Ridero smart publishing system

Introduction

The tutorial is devoted to the consideration of theoretical issues in the framework of the course «Discrete Mathematics». The basic theoretical information on finite mathematics for students in the study of relevant courses, the principles of constructing mathematical models and methods for their analysis are presented. The manual can be useful not only to students of technical specialties and specialties associated with the design of information systems and the development of software modules, but also to students of humanitarian specialties. The sections discussed in the manual fully reflect the necessary material.

The main focus of the manual is on the set-theoretic approach. The basic information on combinatorics, coding theory and mathematical modeling, graph theory is presented. Many theses are illustrated clearly.

1. PLURALITY

1.1. Definitions and examples

The concept of set is one of the fundamental concepts of mathematics. The set is known, at least, that it consists of elements.

By the set S we mean any collection of defined and distinguishable objects, conceivable as a whole. These objects are called elements of the set S. As examples of the sets, one can cite: the set of students present at the lecture, the set of even numbers, etc. Usually, sets are indicated in capital letters of the Latin alphabet: A, B, C, …; and the elements of sets are in lower case: a, b, c,…

If the object x is an element of the set M, then they say that x belongs to M: x∈M. Otherwise, they say that x does not belong to M: x∉M.

A set A is called a subset of B if every element of A is an element of B. If A is a subset of B and B is not a subset of A, then they say that A is a strict (proper) subset of B. In the first case, denote: A⊆B, in the second: A⊂B.

Note that the symbol ∈ defines the relationship between some element and the set, and the symbol ⊆ defines the relationship between the sets, one of which is a subset of the other. So, it is not true that 1∈ {{1}, {2}}, or that {1} ⊆ {{1}, {2}}; it is true that {1} ∈ {{1}, {2}} and {{1}} ⊆ {{1}, {2}}. This example illustrates the difference between membership and inclusion.

For arbitrary sets X, Y, Z the following relations are true:

– X⊆X;

– if X⊆Y, Y⊆Z, then X⊆Z;

– if X⊆Y, Y⊆X, then X = Y.

A set containing no elements is called empty, denoted as: ∅. It is a subset of any set. The set U is called universal, that is, all the sets under consideration are its subset.

We consider two definitions of equality of sets.

– The sets A and B are considered equal if they consist of the same elements, then they write: A = B and A ≠ B – otherwise.

– The sets A and B are considered equal if: A⊂B, B⊂A.

The power of a finite set A is the number of its elements. The power sets are denoted by | A |. Note that | ∅ | = 0, | {∅} | = 1. Sets are called equipotent if their powers coincide.

The degree-set (boolean) of A is the set 2A (the alternative notation is P (A)) of all its subsets.

Theorem. If the set A contains n elements, then the set P (A) contains 2n elements. In this regard, the notation of the set-degree of the set A in the form 2A is also used.

Proof 1: by induction. Base: if | M | = 0, then M = ∅ and 2∅ = {∅}. Therefore: | 2∅ | = | {∅} | = 1 = 20 = 2| ∅ |. Induction transition: let ∀ M | M | 2M | = 2| M |

Consider: M = {a1, …, ak}, | M | = k. Put: M1 = {X⊂2M ┤ | ak∈X} and M2 = {X⊂2M ┤ | ak∉X}.

We have: 2M = M1∪M2 and M1∩M2 = ∅.

By the induction hypothesis: | M1 | = 2k-1, | M2 | = 2k-1.

Therefore: | 2M | = | M1 | + | M2 | = 2k-1 +2k-1 = 2 * 2k-1 = 2k = 2 | M |

THEOREM IS PROVEN

Proof 2: Suppose there is some set {a1, a2 … an}. To each subset of this set we associate a sequence consisting of zeros and ones, where 0 – means that the n-th element is not, and 1 – means that it is.

We get:

00 … 00

00 … 01

00 … 11

…

11 … 11

Obviously, there are only 2n such sequences.

THEOREM IS PROVEN

For example, there is some set A = {1, 2, 3}. Consider the set of all its subsets. Obviously, there are only 2n such representations, in this case n = 3.

1.2. Ways to Define Sets

The sets are set:

by listing the elements: M = {a1, a2,…,ak}, i.e., a list of its elements;

characteristic predicate: M = {x|P (x)} – a description of the characteristic properties that its elements must possess;

generative procedure: M = {x|x=f}, which describes a method for obtaining elements of a set from already obtained elements or other objects. In this case, the elements of the set are all objects that can be constructed using such a procedure. For example, the set of all integers that are powers of two.

When defining sets by enumeration, the notation of elements is usually enclosed in curly brackets and separated by commas. By enumeration, only finite sets can be specified (the number of elements in the set is finite, otherwise the set is called infinite). A characteristic predicate is a condition expressed in the form of a logical statement or procedure that returns a logical value. If the condition is satisfied for a given element, then it belongs to the set being defined, otherwise it does not. A generating procedure is a procedure that, when launched, generates some objects that are elements of a defined set. Infinite sets are given by a characteristic predicate or generating procedure.

Examples:

M = {1, 2, 3, 4}. – enumeration of elements of the set.

M = {m| m ∈ N and ≤ 10} – is a characteristic predicate.

Tribonacci numbers are specified by the conditions (generative procedure): a0=0,a1=1,a2=2,an=an—1+ an—2+ an—3, for n> 3

1.3. Set Operations

Operations on sets are considered to obtain new sets from existing ones.

The union of the sets A and B is the set consisting of all those elements that belong to at least one of the sets A, B (Fig. 1.1): A ∪ B = {x | x ∈ A ∨ x ∈ B}.

The intersection of sets A and B is the set consisting of all those and only those elements that belong simultaneously to both the set A and the set B (Fig. & 1.2): A ⋂ B = {x | x ∈ A ∧ x ∈ B}.

The difference between the sets A and B is the set of all those and only those elements A that are not contained in B (Fig. 1.3): A\B = {x | x ∈ A and x ∉ B},

The symmetric difference of sets A and B is the set of elements of these sets that belong either to the set A or to the set B, but do not belong to their intersection (Fig. & 1. 4): A+B= {x | x ∈ A, or x ∈ B, x ∉ A⋂ B},

Absolute complement (negation) of the set A is the set of all those elements that do not belong to the set A (Fig. & 1. 5): ̅A=U\A,

1.4. Set Operations Properties

For arbitrary sets A, B, and C, the following relations are true.

Commutativity of the union: A ∪ B = B ∪ A,

Commutativity of the intersection: A ⋂ B = B ⋂ A,

Associativity of the union: A ∪ (B ∪ С) = (A ∪ B) ∪ С,

Associativity of the intersection: A ⋂ (B ⋂ С) = (A ⋂ B) ⋂ С,

Distribution of the union with respect to the intersection: A ∪ (B ⋂ С) = (A ∪ B) ⋂ (А ∪ С),

Distribution of intersection with respect to the union: A ⋂ (B ∪ С) = (A ⋂ B) ∪ (А ⋂ С),

Laws of action with empty and universal sets: A ∪ ∅ = A, A ∪ A = U, A ∪ U = U, A ⋂ U = A, A ⋂ A = ∅, A ⋂ ∅ = ∅

The law of idempotency of the union: A ∪ A = A,

The law of idempotency of the intersection: A ⋂ A = A,

De Morgan’s laws: A ∪ B = A ⋂ B, A ⋂ B = A ∪ B,

Laws of absorption: A ∪ (A ⋂ B) = A, A ⋂ (A ∪ B) = A,

Gluing laws: (A ⋂ B) ∪ (A ⋂ B) = A, (A ∪ B) ⋂ (A ∪ B) = A,

Poretsky Laws: A ∪ (A ⋂ B) = A ∪ B, A ⋂ (A ∪ B) = A ⋂ B,

Double Supplement Law A=A,

1.5. Euler-Venn Diagrams

The illustrations below are called Euler-Venn diagrams, they can be used to illustrate the equalities sets expressed through given sets, as well as receive new equalities.

Fig. 1.1 – Intersection of sets

Fig. 1.2 – Combining sets

Fig. 1.3 – The difference of the sets

Fig. 1.4 – The symmetric difference of sets

Fig. 1.5 – Absolute complement (negation) of the set

1.6. Characteristic functions

1.6.1. Main relations

To prove complex set-theoretic identities, it is more efficient to use characteristic functions.

A characteristic function XA of the set A ⊆ U is a function defined on the set U with values on the set {0,1}: XA (x) = {1 if x ∈ A 0 if x ∉ A},

Obviously, the identity L = R will be valid if the characteristic functions of the sets L, Rare equal, i.e.. XL (x) = XR (x).

We give the characteristic functions of intersection, union, difference, absolute complement and symmetric difference, as well as an important property of the characteristic functions:

– XA ⋂ B (x) = XA (x) *XB (x)

– XA ∪ B (x) = XA (x) +XB (x) – XA (x) *XB (x)

– XA \ B (x) = XA (x) – XA (x) *XB (x)

– XA (x) = 1 – XA (x)

– XA + B (x) = XA (x) +XB (x) – 2XA (x) XB (x)

– XA (x) = X2A (x)

1.6.2. The process of evidence by the characteristic function

To prove the validity of the set-theoretic identities should express the characteristic features of its left and right sides of the characteristic features contained in them sets.

As an example, we prove the validity of one of the laws of action with an empty set: A ⋂ A = ∅.

Using the characteristic functions: XA ⋂ B (x) = XA (x) *XB (x), XA (x) = 1 – XA (x), we obtain: XA ⋂ A (x) = XA (x) *XA (x) = XA (x) * (1 – XA (x)) = XA (x) – X2A (x) =0

WHAT AND NEEDED TO BE PROVEN.

1.7. Relationships

Relationship is a mathematical structure that formally defines the properties of various objects and their relationships. Relations are usually classified by the number of objects to be linked and their own properties.

An ordered pair (x,y) is intuitively defined as a collection consisting of two elements x and yarranged in a specific order. Two pairs (x,y), (u,v) are considered equal if x=u, y=v and only if. The ordered n-th elements x1,…,xn are denoted by (x1,…,xn).

The Cartesian product of the sets X and Y is the set X × Y of all ordered pairs (x, y) such that x ∈ X, y ∈ Y.

A binary (or two-place) relation R is the set of ordered pairs, a binary relation is a subset of the Cartesian product.

If R is a relation and the pair (x, y) belongs to this relation, then along with the record (x, y) R, the notationis also used xRy. Elements x and y are called the coordinates (or components) of the ratio R.

The domain of a binary relation R is the set DR= {x ∨ ∃ y, xRy}. The range of binary relations R is the set ER= {y ∨ ∃ x, xRy}.

Let R XY be defined in accordance with the image in Figure 1.6

Fig. 1.6 – Definition of the relation R

The domain of definition of DR and the range of values of ER are defined respectively: DR= {x: (x, y) ∈ R}, ER= {y: (x, y) ∈ R}. The binary relation can be set in any of the ways job sets. In addition, relations defined on finite sets are usually specified: by a

– list (enumeration) of pairs for which this relation is satisfied;

– matrix – the binary relation corresponds to a square matrix of order n, in which the element rij, standing at the intersection of the i-th row and the j-th column, is 1 if ai and aj is the relation, or 0 if it is absent: R= rij, rij= [0, (ai, aj) ∉ R 1, (ai, aj) ∈ R]

1.7.1. Properties of binary relations

– relationship R on the set X is reflexive if for any element xX hRh performed.

– The ratio R for the set X is called anti-reflective (irreflexive) if for any element xX performed ¬ (xRx).

– The ratio R for the set X is symmetric if for all x,x from hRu should be uRh.

– The ratio R for the set X is antisymmetric if for all x, yX of hRu and that x=y.

– A relation R on a set X is called transitive if, for any x, y, z X from xRy, and xRz follows yRz.

A partial order relation R is called linear order if the condition ∀x, y ∈ X: xRy ∨ yRx is satisfied.

A relation R is called a strict order relation on a set Xif it is antireflexive, antisymmetric, and transitive.

Reflective, symmetric, transitive relation on a set X is an equivalence relation on the set X.

Reflexive transitive and antisymmetric ratio is called a partial order relation, or the ratio of the non-strict order on the set X.

If theon the set X relation of partial orderis given ≤, then the set X is called partially ordered. If theon the set X relation of linear orderis given ≤, then the set X is called linearly ordered. If aon a set X relation of full orderis given ≤, then the set X is said to be completely ordered.

Let R – equivalence relation on the set X.

An equivalence class generated by an element x ∈ X is a subset of the set Xconsisting of those elements y X for which xRy. It is designated as: [x] = {y ∈ X | xRy}.

A partition of a set X is a collection of pairwise disjoint subsets of Xsuch that each element of the set X belongs to one and only one of these subsets.

Examples:

1. X= {1,2,3,4,5} Partition: {{1,2}, {3,5}, {4}}.

2. The partition of many students of the institute can be a set of groups.

In other words, a partition of a set X is a family: X = ∪i ∈ IXi∀i, j Xi ⋂ Xj j =0, Xi ⊆ X is an element of the partition.

The set of equivalence classes of elements of any set of X by the equivalence relation R setis the quotient of the set X with respect R denotedand X/R.For example, a plurality of student groups of a given university is a factor in a plurality of a plurality of university students in relation to belonging to one group.

Examples:

– (x, ≤) x ≤ y (x,y) ∈ ≤ – are comparable;

– (x,y) ∉ ≤ – are not comparable.

If (x, ≤), ∀ x ∈ X ∃ a ∈ X ∨ a ≤ x then a is the smallest element. If ∃ a ∈ X ∨ ∀ x ∈ X x ≤ a, then a is the largest element.

Statement: the largest or smallest element is single.

Proof: let a and b be the largest elements in (x, ≤), then ∀ x ∈ X a ≥ x, in particular a ≥ b. Similar to b ≥ a, therefore a=b.

In a similar way, the statement for the smallest elements is proved.

APPROVED PROVEN

1.7.2. Operations on binary relations

Since relations on X are defined by subsets R ⊆ X × Y, the same operations are defined for them as on sets.

– The union R1 ∪ R2: R1 ∪ R2= {(x,y) | (x,y) ∈ R1 or (x,y) ∈ R2}

– Intersection R1 ⋂ R2: R1 ⋂ R2= {(x,y) | (x,y) ∈ R1 and (x,y) ∉ R2}

– Difference R1/R2: R1/R2= {(x,y) | (x,y) ∈ R1 and (x,y) ∉ R2}

– Addition R: R=U/R, where U=M1×M2 (or U=M2)

The inverse ratio R-1:x R-1y if and only if yRx, R-1= {(x,y) ∨ (y,x) ∈ R}.

Compound ratio (composition) R1 ∝ R2. Let the sets M1, M2 and M3 and the relationship R1M1M2 and R2M2M3. The composite relation acts from M1 to M2 by means of R1, and then from M2 to M3 by R2, i.e. (a,b) R1 ∝ R2, if there is such an M2 that (a,c) R1 and (a,c) R2.

The transitive closure of R.A transitive closure consists of such and only such pairs of elements a and b from M, that is, (a, b) R, for which in M there exists a chain of (k +2) elements M, k 0 such that a, c1, c2, … ck, b, between whose adjacent elementsis fulfilled R. In other words, ARC1, with1RC2, …, withkRb.

Two partially ordered sets are called isomorphic if there is a one-to-one correspondence between them that preserves order.

Example: (x, ≤1), (y, ≤2) x, y are isomorphic if, where ∃φ:X → Y is a bijective function that preserves order (the definition of a function and a bijective function is given below).

A binary relation is called tolerance if it is reflective and symmetrical. A binary relation is called a quasiorder if it is irreflexive, antisymmetric, and transitive (preorder).

1.8. Functions

A binary relation f is called a function if from (x. y) f and (x. z) f it follows that y=z. Since functions are binary relations, the two functions f and g are equal if they consist of the same elements. The domain of the function is denoted by Df, and the domain is Rf. They are defined in the same way as for binary relations.

If f is a function, then instead of (x. y) f they write y=f (x) and say that y is the value corresponding to the argument x, or y is the image of the element x under the mapping f. Moreover, x is called the inverse image of the element y.

The concept of «display» is also often used. Display is some function that reflects the interconnection of elements between sets. In other words, the concepts of «function» and «display» are equivalent.

Let f: XY. A function f is called injective (injection) if: ∀x1,x2,y: {x1fyx2fy⇒x1=x2},

That is, each value of the function corresponds to a single value of the argument. A function f is called surjective (surjection) if ∀ y ∃ x | xfy. A function f is called bijective (bijection) if f is both surjective and injective.

Figure 1.7 illustrates the concepts of relationship, function, injection, surjection, and bijection.

Fig. 1.7 – Relations and functions

1.9. Algebraic operations

An algebraic operation on a set M is a function φ: Mn → M, for n = 1 – unary operation, n = 2 – binary, n = 3 – triary (ternary).

It is said thaton M a binary algebraic operation is definedif, by anyany ordered pair of elements of the set M. law, a well-defined element of the same set is associated withFor functions, multiplicative and additive terminology is used.

Comparison of operations Table 1.1

Properties:

– commutativity: a+b=b+a, a*b=b*a,

– () Associativity: a+b+c=a (a*b) *c=a* (b*c),

– distributivity: (a+b) *c=a*c+b*c,

A neutral element e of the set M for a binary algebraic operation φ:M2 → M is an element: e ∈ M ∨ ∀ x ∈ M φ (x, e) = φ (e, x) = x,

Theorem: the neutral element is the only one.

Proof: suppose that in the set M there are two neutral elements e and e». Then ∀ x ∈ M the equalities hold: φ (x, e) = x and φ (e’, x) = x. Therefore, these equalities hold for x=e’ and x=e: φ (e’, e) = e’ and φ (e’, e) = e, and it follows that e=e’.

THEOREM IS PROVEN.

1.10. Hasse diagrams

If x ≤ (precedes) y and x ≠ y, then write: x <(strictly precedes) y.

It is said that an element y covers an element xif x

To illustrate the partial order on the set X, schemes are used that are called Hasse diagrams. In these diagrams, the elements of the set are represented as points on the plane. At the very bottom, the smallest element is depicted, if it exists and belongs to the set, or minimal elements, the elements covering the elements of the previous row, etc. are located higher, and if y covers x, then the points corresponding to them are connected by segments. Figure 1.8 shows the Hasse diagrams of two sets, and Figure 1.9b corresponds to a linearly ordered set.

Fig. 1.8 – Examples of Hasse diagrams

Let A = {1,2,3}. On the set 2,A = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}, we define the partial order relation «to be a subset», that is, x ≤ y if and only if when x ⊆ y. The Hasse diagram for this set is shown in Figure 1.9a.

Let X = {1,2,3,5,6,10,15,30}. On this set (divisors of 30), we define a partial order relation: x | y if and only if x divides y. The Hasse diagram for this set is shown in Figure 1.10.2b.

On a numerical set Y = {1,2,3,4,5,6,7,8} consider the relation ≤ (less than or equal to). The Hasse diagram for this set is shown in Figure 1.9c.

Fig. 1.9 – Hasse diagrams of ordered sets 2A, X, Y

A Hasse diagram is a directed graph of the form: o→o→…→o→o

Consider the set of divisors of nordered by the divisibility relation. a/b ⇔ a divisor b (Dn,1),n ≥ 1,

Let p and q be prime integers greater than 1. We construct a Hasse diagram for which n=p2q.

In the most general case, the Hasse diagram of a partially ordered set (Dn, 1) consists of edges of an n-dimensional parallelepiped, where n is the number of different prime divisors of n.

Theorem: n> 0, n=p1a1p2a2…pmam is the decomposition of the number n into the product of pairwise unequal simple factors. ∀ i,j (i≠j) ⇒ pi ≠ pj. The partially ordered set (Dn, 1) will be isomorphic to the Cartesian product of [a1] × [a2] × … × [am] linearly ordered sets.