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 = 2⁰ = 2| ∅ |. Induction transition: let ∀ M | M | <k⇒ | 2M | = 2| M |

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

We have: 2M = M₁∪M₂ and M₁∩M₂ = ∅.

By the induction hypothesis: | M₁ | = 2k-1, | M₂ | = 2k-1.

Therefore: | 2M | = | M₁ | + | M₂ | = 2k-1 +2k-1 = 2 * 2k-1 = 2k = 2 | M |

THEOREM IS PROVEN

Proof 2: Suppose there is some set {a₁, a₂ … 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 = {a₁, a₂,…,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): a₀=0,a₁=1,a₂=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) = X²A (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) – X²A (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 x₁,…,xn are denoted by (x₁,…,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 R₁ ∪ R₂: R₁ ∪ R₂= {(x,y) | (x,y) ∈ R₁ or (x,y) ∈ R₂}

– Intersection R₁ ⋂ R₂: R₁ ⋂ R₂= {(x,y) | (x,y) ∈ R₁ and (x,y) ∉ R₂}

– Difference R₁/R₂: R₁/R₂= {(x,y) | (x,y) ∈ R₁ and (x,y) ∉ R₂}

– Addition R: R=U/R, where U=M₁×M₂ (or U=M²)

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

Compound ratio (composition) R1 ∝ R2. Let the sets M₁, M₂ and M₃ and the relationship R₁M₁M₂ and R₂M₂M₃. The composite relation acts from M₁ to M₂ by means of R₁, and then from M₂ to M₃ by R₂, i.e. (a,b) R1 ∝ R2, if there is such an M₂ that (a,c) R₁ and (a,c) R₂.

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, c₁, c₂, … ck, b, between whose adjacent elementsis fulfilled R. In other words, ARC₁, with₁RC₂, …, withkRb.

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

Example: (x, ≤₁), (y, ≤₂) 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: ∀x₁,x₂,y: {x₁fyx₂fy⇒x₁=x₂},

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 <y, and there is no element usuch that x <u <y. In the general case, if x <y, then either y covers x, or there exist elements x1, x2, …, xi, xi +1, …, xnsuch that x = x1 <x2 <… <xi <xi +1 <… <xn = y, where xi +1 covers xi for all i.

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=p²q.

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 [a₁] × [a₂] × … × [am] linearly ordered sets.

Proof: we define an isomorphism as follows (by mapping into an m-dimensional cube): p₁β1*p₂β2*…*pmβm→ (β₁,β₂,β₃,…,βm),

THEOREM IS PROVED.

1.11. Theorem

Two partially ordered sets X and Y Isomorphismare called isomorphic if there exists a bijection φ:X → Y that preserves a partial order relation. Otherwise: x₁≤xx2 if and only if φ (x₁) ≤yφ (x₂), where ≤x is the partial order relation on the set X, and ≤y is the partial order relation on the set Y.

Statement: every partially ordered set X is isomorphic to some system of subsets of the set X partially ordered by the inclusion relation.

1.12. Algebraic structure

Everywhere defined (total function) φ: MnM→ called n-ary (n-place) operation on M.The set M together with the set of operations ∑= (φ₁, φ₂,…φm), φi: Mn→M, where ni is the arity of the operation φi, is called an algebraic structure, a universal algebra, or simply an algebra.

The set M is called the support or basis of algebra. The arity vector of operations (n₁,n₂,…,nm) is called the type of algebra. The set ∑ is called a signature.

A subset X of the set M (X ⊂ M) is said to be closed under the operation φif: ∀x₁,x₂,…,xn ∈ X φ (x₁,x₂,…,xn) ∈ X, (1.12.1)

If the set X is closed ∀ φ ∈ ∑, then X is called the support of another algebra: (X, ∑x) – and the set X together with the set of operations is called a subalgebra.

Theorem 1 (formulation 1): a nonempty intersection of subalgebras is also a subalgebra.

Proof: let (Xi, ∑ Xi) be the subalgebra (M; ∑). Then: ∀ i,j φiXi (x₁,…,xn) ∈ Xi ⇒ ∀ j φjXi (x₁,…,xn) ∈ ⋂ Xi, (1.12.2)

THEOREM IS PROVED.

Theorem 1 (formulation 2): the intersection of any system of subalgebras of the algebra G, if it is not empty, will be a subalgebra of this algebra.

Proof: indeed, if G takes a system of subalgebras Ai, i ∈ I, with non-empty intersection D and if ω ∈ Ωn, n≥1 and d₁,d₂,…,dn are any elements from D, then the element d₁,d₂,…,dnω contained in each of the subalgebras ai, and therefore is contained in D. On the other hand, in each of the subalgebras Ai, and therefore also in D, there are elements marked in G by all nullary operations from Ω. It follows that if M is a nonempty subset of the algebra G, then in G there exists a minimal among the subalgebras containing the whole set M, namely, the intersection of all such subalgebras. One of them is the algebraitself G.

THEOREM IS PROVEN.

The closure of the set X ⊂ M with respect to the signature ∑ (denoted by |X|∑) is the set of all elements (including the elementsthemselves X) that can be obtained from Xusing the operations from ∑. If the signature is implied, it can be omitted.

1.13. Theory

CategoryCategory Cis a pair (Obc, Homc (A,B)):

– set objects Obc;

– for each pair of objects A, B from the set of objects, a lot of morphisms (or arrows) are given Homc (A,B), and each morphism corresponds to unique A and B;

– for a pair of morphisms f ∈ Hom (A,B), g ∈ Hom (B,C) a composition is defined f o g ∈ Hom (A,C);

– for each object A, an identical morphism is given idA ∈ Hom (A,A);

moreover, two axioms are fulfilled: the

– composition operation is associative;

– identity morphism acts f o idA = idB o f = f trivially.

If φ o f = f o φ – then the morphism is called a homomorphism. A homomorphism, which is an injection, is called a monomorphism. A homomorphism that is surjection is called an epimorphism. A homomorphism, which is a bijection, is called an isomorphism.

If the supports of the algebra coincide, then the homomorphism is called an endomorphism, and the isomorphism is called an automorphism.

The most important role in category theory is played by the concept of a monoid (semigroup with unity). The monoid M can be described as a set M with two functions: μM × M → Mη,:1 → M, such that the following diagrams are commutative:

here 1 in the expression 1 × μ is the identical function M × M, and 1 in the expression 1 × M is a one-point set 1 = {0}, while λ ∧ ρ are bijections. The commutativity of the diagrams means that the following products coincide: μ o (1 × μ) = μ o (μ × 1), μ o (η × 1) = λ, μ o (1 × η) = ρ, (1.13.1)

Theorem: let two algebras be given: A= (A,∑A) and B= (B,∑B), then if f: A → B is an isomorphism, then f⁻¹: B → A is also an isomorphism.

Proof: consider an arbitrary operation φ from signature A and the corresponding operation ψ from signature B.

We have: f (φ (a₁,…,an)) =ψ (f (a₁),…,f (an)), in addition, f is a bijection.

denote B₁:= f (a₁) …,bn:= f (a wherein a₁ = f⁻¹ (b₁) …,an=f-1 ()

Then: f⁻¹ (ψ (b₁,…,bn)) =f⁻¹ (ψ (f (a₁),…,f (an))) =f⁻¹ (f (φ (a₁,…,an))) =φ (a₁,…,an) =φ (f⁻¹ (b₁),…,f⁻¹ (bn))

THEOREM IS PROVED.

If f: A → B is an isomorphism, then the algebras A and B are called isomorphic and are denoted as follows A~fB:

The isomorphism relation on the set of algebras of the same type is equivalent:

– reflexivity: A~fA, f:=I;

– symmetry: A~fB ⇒B~f-1A;

– transitivity: A~fB & B~gG⇒A~f o gG

1.14. Algebras with one operation (semigroups)

Semigroup – algebra with one associative operation: M= (M,o), (aob) oc=ao (boc),

Monoid is a semigroup with unit: ∃ e ∈ M| ∀x: e o x=x o e=x.

Theorem: the unit is the only one.

Proof: let: ∃ e₁,e₂ ∀a: a o e₁=e₁ o a= a & a o e₂=e₂ o a= a. Then: e1 o e₂=e1 & e1 o e2 =e₂ ⇒ e₁=e₂

THEOREM IS PROVEN.

A group is a monoid in which: ∀ a ∈ M ∃ a⁻¹ ∈ M | a o a-1 = a-1 o a=e. The element a⁻¹ is called the inverse. It is sometimes referred to as a».

Theorem: if thein the monoid for the element x opposite exists, then it is unique, that is, if x’*x=x*x’=e=x’«*x=x*x», then x’=x».

Proof: indeed, from the relations x*x»=e and x’*x=e it follows that: x’=x’*e=x’* (x*x») = (x’*x) *x»=e*x»=x».

THEOREM IS PROVEN.

Theorem: in the group the equationuniquely resolved a o x=b is.

Proof: let: a o x=b ⇒ a-1 o (aox) = a-1 o b ⇒ (a-1 o a) ox = a-1 o b ⇒ e o x = a-1 o b ⇒ x= a-1 o b.

THEOREM IS PROVEN.

A commutative group, that is, a group in which a o b = b o a is called Abelian. The following notation is used in abelian groups: a group operation is denoted by + or ⊕ the inverse of a: -a, the unit of the group denotes 0 and is called zero.

1.15. Algebra with two operations two operations

Let be given on a set: ⊗:M²→M is the multiplication and ⊕:M²→M is the addition. A ring is a set M with two binary operations ⊕ and ⊗, in which:

– addition is associative: (a ⊕ b) ⊕ c= a ⊕ (b ⊕ c)

– there is an addition unit: ∃0∈M∀aa⊕0=0⊕a=a

– there is an inverse addition element: ∀a∃-a,a⊕-a=0

– addition is commutative, that is, a ring is an Abelian addition group: a⊕b=b⊕a

– multiplication is associative, that is, a ring is a semigroup of multiplication: a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c the

– multiplication is distributive left and right: a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c), (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c) The ring is called commutative, if the multiplication is commutative: a ⊗ b = b ⊗ a. A commutative ring is called a unit ring if there is a unit of multiplication: ∃1∈Ma⊗1=1⊗a=a; that is, a ring with a unit is a monoid of multiplication.

1.16. Vector spaces

A field is a set M with two binary operations ⊕⊗ andsuch that:

– (a ⊕ b) ⊕ c= a ⊕ (b ⊕ c) – addition is associative;

– ∃0∈Ma⊕0=0⊕a=a – there is zero;

– ∀a∃-a | a⊕ (-a) =0 – there is an inverse element in addition;

– a ⊕ b = b ⊕ a – addition is commutative (field is an Abelian group by addition);

– a ⊗ (b ⊗ c) = (a ⊗ b) ⊗ c – multiplication is associative;

– ∃1∈M|a⊗1=1⊗a=a – there is a unit;

– ∀a ≠ 0∃a⁻¹ | a⁻¹⊗a=1 – there is an inverse element for multiplication;

– a ⊗ b = b ⊗ a – multiplication is commutative (field is an Abelian group by multiplication);

– a ⊗ (b ⊕ c) = (a ⊗ b) ⊕ (a ⊗ c) – Multiplication is distributive with respect to addition.

Let F= <F;+,.> be a field with the addition operation +, the operation of multiplication., the additive unit 0 and the multiplicative unit 1. Let V= <V;+,.> be some Abelian group with the operation + and the unit 0. If there exists an operation F × V → V (the sign of this operation is omitted) such that for any a,b ∈ F and for any x,y ∈ V the following relations hold: (a+b) →x=a→x⊕b→x;a (→x+→y) =a→x⊕a→y; (a*b) →x=a (b→x);1→x+x, then V is called the vector space over the field F, the elements of F are called scalar, the elements of V are called vectors, and the undefined operation F × V → V is called the multiplication of the vector by the scalar.

The unit of the group V is called →0 (zero-vector).

Theorem: ∀x∈V:0*→x=→0, ∀a∈F:a*→0=→0

Proof: (1—1) →x=1*→x-1*→x=→x-→x=→0

a (→0-→0) =a*→0-a*→0=→0-→0=→0

THEOREM IS PROVED.

1.17. Modular arithmetic

It is said that the number a is comparable modulo n with the number b (a=b (mod n)) if a and b divided by n give the same remainder: a=b (mod n) ⇔ a mod n=b mod n.

The comparability relation is reflexive, symmetric and transitive and is an equivalence relation. Equivalence classes with respect to comparability are called residues modulo n. The set of residues modulo n is denoted by zn. Over the residue modulo n, the operationsdefined +n, *n are: a+nb = (a+b) mod n, a*nb = (a*b) mod n,

It is easy to see that (zn, +n) is an Abelian group, and (zn, +n,*n) is a commutative semiring.

Numbers a and b are called coprime if their greatest common divisor is 1.

Let n – a positive integer, n ∈ N. φ (n) is the number of natural numbers 0 <a ≤ n coprime to n. n=10,d= {1,3,7,9}, φ (10) =4,

Function φ (n) is named after Euler. Assuming zn* ⊂ zn is the set of numbers coprime to n, we obtain that the Euler function φ (n) = |zn*|.

Let a natural number nbe presented, represented as its canonical decomposition into simple factors pi: n=k ∏ i=1= piai

Then the Euler function can be calculated by the formula: φ (n) =k ∏ i=1= piai-1 (pi-1)

It is assumed that φ (1) =1.

The Euler function can also be represented as the so-called Euler product: φ (n) =n ∏ p|n= (1- (1/p))

where p is a prime number and runs through all the values involved in the expansion of n into prime factors.

Euler’s theorem (ageneralization of Fermat’s small theorem): ∀a∈zn*,aφ (n) =1 (mod n)

1.18. Commutative semiring

A nonempty set S with the binary operationsdefined on it + and certain is called a commutative semiring if the following axioms hold.

– (S, +) is a commutative semigroup with neutral element 0, i.e.: ∀a,b∈S:a+b=b+a; ∀a,b,c∈S: (a+b) +c=a+ (b+c); ∃0∈S, ∀a∈S,0+a=a+0=a

– (S, *) is a commutative semigroup with neutral element 1, i.e.: ∀a,b∈S: ab=ba; ∀a,b,c∈S: (ab) c=a (bc); ∃1∈S, ∀a∈S,1a=a1=a

– Multiplication is distributive with respect to addition: ∀a,b,c∈S: a (b +c) =ab+ac, (a+b) c=ac+bc

– ∀a∈S:0a=a0=0

To construct the classical semiring of quotients, one can use the following method.

Consider a pair of non-negative integers (a,b),b ≠ 0.

We assume that the pairs (a, b) and (c, d) are equivalent, if ad = bc, we obtain a partition of the set of pairs into equivalence classes. Then we introduce operations on classes that turn the set of classes of equivalent pairs into a half-field that contains a semiring of non-negative numbers.

Weelement n ∈ S call anmultiplicatively reducible if ∀ a,b ∈ S from the equality an = bn that a = b. Denote by R the set of all multiplicatively reducible elements.

Statement: a multiplicatively reducible element is not a zero divisor.

Proof: Let s be a zero divisor, i.e. as = 0 for some a ≠ 0. Then as = 0s, but a ≠ 0 ⇒ is reducible not multiplicatively.

APPROVED PROVEN.

Let S – commutative semiring contractibly by elements of (s,r) ∈ S × R. Consider the set of ordered pairs of We introduce the relation ~ on S × R: (a,b) ~ (c,d) ⇔ ad=bc for all a,c ∈ S and b,d ∈ R.

Adoption: attitude ~ is an equivalence relation on S.

We show that ~ is an equivalence relation. To do this, it is necessary to show reflectivity, symmetry and transitivity.

Reflectivity: due to the commutativity of the semiring S: ab=ba ⇒ (a,b) ~ (a,b);

Symmetry: (a,b) ~ (c,d) ⇔ ad=bc ⇔ cb=da ⇔ (c,d) ~ (a,b);

Transitivity: (a,b) ~ (c,d) ⇔ ad=bc | × f ⇒ adf=bcf ⇒ afd=bcf

(c,d) ~ (e,f) ⇔ cf=de | × b ⇒ cfb=deb ⇒ bcf=bed

Consequently: afd=bed ⇒af =be ⇔ (a,b) ~ (e,f)

Thus, the ratio ~ is an equivalence relation on S.

APPROVED PROVEN

The semiring S is divided into equivalence classes; in each class are those elements that are in relation ~.

Denote by [a, b] the equivalence class of the pair (a, b). We introduce operations on the set Qcl (S) of all equivalence classes: [a,b] + [c,d] = [ad+bc, bd]

[a,b] * [c,d] = [ac, bd]

bd ∈ R since for n ∈ R,m ∈ R,a,b ∈ S, nma=nmb from here, since n ∈ R We obtain ma = mb, and since m ∈ R, then a = b, hence mn∈ R.

We show the correctness of the operations introduced.

Let: (a,b) ~ (a’,b’), (c,d) ~ (c’,d’)

Then (ad+bc) b’d’=adb’d’+bcb’d’=ab’dd’+cd’bb’=ab’dd’+c’dbb’=a’d’bd+c’d’bd= (a’d’+b’c’) bd ⇒ (ad+bc, bd) ~ (a’d’+b’c’,b’d’), (1.18.5)

acb’d’=ab’cd’=ba’dc’=bda’c’=a’c’bd ⇒ (ac, bd) ~ (a’c’, b’d’), (1.13.1)

Theorem: (Qcl (S),+,*) is a commutative semiring with 1,S ⊆ Qcl (S).

Evidence: to prove that the set Qcl (S) of all equivalence classes is a commutative semiring with 1, we need to show the closedness of operations on it.

– Addition. ∀ a,c,e ∈ S and ∀ b,d,f ∈ R: [a,b] + [c,d] = [ad+bc, bd] = [cb+da, db] = [c,d] + [a,b]; ([a,b] + [c,d]) + [e,f] = [ad+bc, bd] + [e,f] = [(ad+bc) f+bde, bdf] = [adf+bcf+bde, bdf]; [a,b] + ([c,d] + [e,f]) = [ab] + [cf+ de, df] = [adf+b (cf+de), bdf] = [adf+bdf+bde, bdf].

Since the right-hand sides are equal, the left-hand sides are also equal: ([a,b] + [c,d]) + [e,f] = [a,b] + ([c,d] + [e,f])

We show that ∀ n,n’ ∈ R: [0,n] = [0,n’]. Since 0n’ = n0 ⇔ (0,n) ~ (0,n’) ⇒ [0,n] = [0,n’]. The class [0, n] is neutral in +: [a,b] + [0,n] = [an, bn]

From the equality anb=bna ⇒ (an, bn) ~ (a,b) then [an, bn] = [a,b].

∀ n ∈ R [0,n] is a separate class playing thein Qcl (S) role of zero.

– Multiplication. ∀ a,c,e ∈ S and ∀ b,d,f ∈ R: [a,b] * [c,d] = [ac, bd] = [ca, db] = [c,d] * [a,b]; ([a,b] * [c,d]) * [e,f] = [ac, bd] * [e,f] = [ace, bdf]; [a,b] * ([c,d] * [e,f]) = [a,b] * [ce, df] = [ace, bdf].

From the equality of the right-hand sides it follows that: ([a,b] * [c,d]) * [e,f] = [a,b] * ([c,d] * [e,f])

Let us show that for ∀ n,n’ ∈ R [n,n] = [n’,n’]. Let nn’=nn’ ⇔ (n,n) ~ (n’,n’) ⇒ [n,n] = [n’,n’].

The class [n, n] is neutral in multiplication (a unit of a half ring), because [a,b] * [n.n] = [an, bn] = [a,b], since from the equality anb=bna ⇒ (an, bn) ~ (a,b); then [an, bn] = [a,b].

Multiplication is distributive with respect to addition: ([a,b] + [c,d]) * [e,f] = [ad+bc, bd] * [e,f] = (ade+bce, bdf]; [a,b] * [e,f] + [c,d] * [e,f] = [ae, bf] + [ce, df] = [aedf + bfce, bfdf] = [(ade + bce) f, (bfd) f] = [ade + bce, bfd] * [f,f] = [ade + bce, bfd]

Consequently, the right-hand distribution law holds:-hand distribution law is ([a,b] + [c,d]) * [e,f] = [a,b] * [e,f] + [c,d] * [e,f]

The leftproved in the same way.

THEOREM IS PROVEN

1.19. Group

Substitution on the set is the map of Zn = {1,2,…,n} into itself. Substitution: π = (1,2,…,n; i₁,i₂,…,in)

we will set the line (i₁,i₂,…,in).

A permutation is called cyclic (or a cycle) if some number j1 is translated by it into j₂, j₂ – by j₃, etc., jk-1 is translated into jk, jk – by j₁, and all the others the numbers remain in place. Such a cycle is denoted by (j₁,j₂,…,jk). The number k is called the cycle length. Arbitrary substitution can be represented as a product of cycles. For example: (1,2,3,4,5;2,1,4,5,3) = (1,2) (3,4,5)

A cycle of length 2 is called transposition.

Theorem: any substitution is representable as a product (i.e., sequential execution) of transpositions.

A substitution that can be represented as the product of an even (odd) number of transpositions is called even (respectively, odd).

Theorem: permutations on the set Zn form a group with respect to the product operation.

Proof: the operation of the product of permutations π₁ and π₂ consists in their sequential application. For example, if: π₁= (1,2,3,4;2,4,3,1) π₂= (1,2,3,4;1,4,3,2)

then: π₁π₂= (1,2,3,4;4,2,3,1)

The product operation has, as is easily verified, the associativity property: π (στ) = (πσ) τ The identity element of the group is the identity substitution: The (1,2,…,n;1,2,…,n)

substitution inverse to: (1,2,…,n;i₁,i₂,…,in)

is the substitution: ( i₁,i₂,…,in;1,2,…,n)

THEOREM IS PROVED.

Group permutations on the set Zn called symmetric group nth power, denoted by Sn.The number of elements of the symmetric group nth power is equal to n!.

If the substitution on the set Nn is represented as the product of b₁ cycles of length 1, b₂ cycles of length 2, etc., bn cycles of length n, then they say that the substitution is of the type: b₁,b₂,…,bn For example, wildcard: π₁= (1,2,3,4;2,4,3,1)

has a type (1,0,1,0).

Let M and N be finite sets, and G and H be permutation groups onrespectively M and N,. Degreesgroup HG consists of all possible pairs of (π; σ),where the π ∈ G, σ ∈ H and acts on a plurality NM of all functions f:M → N.

Moreover, by definition (π;σ) f (x) =σf (π (x)) for all x ∈ M and f ∈ N M.

Functions f₁ and f₂ from NM are called equivalent (f₁ ~ f₂) if: ∃π | f₁ (πx) = f₂ (x) for all x ∈ M

1.20. Boolean functions

A Boolean function (either a logical function or a function of a logic algebra or a switching function) of n variables is a mapping: f:E₂n → E₂

where E₂n = {0,1} Is a Boolean set.

Elements of the Boolean sets 1 and 0 are usually interpreted as logical values of «true» and «false», although in the general case they are considered as formal symbols that do not carry a certain meaning. A non-negative integer n is called the arity or locality of the function; in the case n = 0, the Boolean function turns into a Boolean constant. Elements of the Cartesian product are called Boolean vectors.

The set of all possible Boolean functions: Pn= {f|f:E₂n → E₂}

Each Boolean function of arity n is completely determined by setting its values on its domain of definition, that is, on all Boolean vectors of length n. It is easy to calculate the number of all Boolean functions of n variables.

Theorem:| Pn|=22n

Proof: Indeed, the number of functions from ak-element setAto anm-element setBis equal tomk (this fact is proved in the section on combinatorics). In our case, B = {0, 1}, andA = Bn. Thenm = 2 andk = |Bn| = 2n. This implies the statement of the theorem.

THEOREM IS PROVEN

Any Boolean function can be set by the truth table.

The truth table of Boolean functions Table 1.2

An example of the truth of Boolean functions Table 1.3

For these functions, x1 is essential and x₂ Is an inconsequential variable. The variablevalue of functions x₂ does not affect the, i.e. the value of the function does not significantly depend on the variable x₂. f₁=x₁,f₂= ¬ x₁

Boolean functions are equal if one of the other is obtained by introducing or deleting non-essential variables.

1.20.1. Boolean functions of one variable

Boolean functions of one variable Table 1.4

1.20.2. Boolean functions of two variables of

Boolean functions of two variables Table 1.5

F= (f₁,f₂,…,fn), ∀ i: fi ∈ Pn

Formula over F: Ф [F] = fi (t₁,t₂,…,tm), fi ∈ F, ti – variable or formula. The set F is called a basis. The function fi is called an external (main) operation; ti is the subformula.

1.21. Equivalent formulas

Formulas are called equivalent if they implement the same function. In other words, two logical formulas are called equivalent if, for any values of their logical variables that are the same for both functions, these formulas take the same values. F₁=F₂:=func (F₁) =f&func (F₂) =f

Equivalent formulas serve to express some logical operations through others, simplify formulas or, more precisely, replace some logical formulas with others that are equivalent, but simpler. In reasoning one can replace complex statements with simpler ones equivalent to them.

A formula is called identically true or a tautology if it implements an identity unit.

A formula is called identically false if it implements an identity zero.

Statement: the equivalence relation of formulas is equivalence.

Key equivalence Table 1.6

«Allequivalence can be checked by the relevant construction of the truth table STI.

The set (E₂, ¬, ∨, ∧) is called a binary Boolean algebra. In other words, 2 constants are defined on it: 1 and 0, and the operations of negation, conjunction and disjunction.

Substitution rule: if in the equivalent formulas instead of the same variable x we substitute the same formula, then we get equivalent formulas. ∀Г (Ф₁ (…x…) =Ф₂ (…x…)) Ф₁ (…x…) {Г\\x} =Ф₂ (…х…) {Г\\x}

In this case, the sign \\ we have designated the replacement of all occurrences of a variable with a formula. The condition for replacing all occurrences is essential.

Replacement rule: if in some formula we replace some subformula (we use the \ sign to replace) with an equivalent one, we get an equivalent formula. Ф (…Г…) ∨ Г₁=Г₂⇒ Ф (…Г…) {Г₁\Г} =Ф (…Г…) {Г₂\Г}

1.22. Algebra of Boolean functions

Define the conjunction, disjunction and negation functions: ∧, ∨: Pn² → Pn; ¬: Pn → Pn

They are operations on the set of Boolean functions. The algebraic structure (Pn, ∨, ∧, ¬) is called the algebra of Boolean functions. The algebra of Boolean functions is a Boolean algebra. All axioms of Boolean algebra are satisfied in the algebra of Boolean functions.

Ф is the set of formulas equivalent to given ones; we denote K= {Ф} Ф is the equivalence class with respect to equivalence.

An algebra of the class of formulas (K, ¬, ∨, ∧) is called the Lindenbaum-Tarski algebra. This algebra is isomorphic to the algebra of Boolean functions and is a Boolean algebra.

1.23. The principle of duality

In Boolean algebras, there are dual statements; they are either true or false at the same time. Namely, if in a formula that is true in some Boolean algebra, change all conjunctions to disjunctions, 0 to 1, ≤ to ≥ and vice versa, then we get a formula that is also true in this Boolean algebra. f (x₁,x₂,…,xn) ∈ Pn

f (x₁,x₂,…,xn) = f (x₁,x₂,…,xn) is the dual function f.

Theorem: duality is foreign-valued: (f*) *=f

Proof: f* = f (x₁,x₂,…,xn)

(f*) *=f (x₁,x₂,…,xn) def= f (x₁,x₂,…,xn)

THEOREM IS PROVED.

A function is called self-dual if f*=f.

Theorem: let φ (x₁,x₂,…,xn) be realized by the formula:

f (f₁ (x₁,x₂,…,xn),…,fn (x₁,x₂,…,xn))

then the formula :

f* (f₁* (x₁,x₂,…,xn),…,fn* (x₁,x₂,…,xn))

implements the function:

φ (x₁,x₂,…,xn)

Proof: φ* (x₁,…,xn) =φ (x₁,…,xn) =φ (x₁,…,xn) =f (f₁ (x₁,…,xn),…,fn (x₁,…,xn)) =f (f₁ (x₁,…,xn),…,fn (x₁,…,xn)) = f (f₁* (x₁,…,xn),…,fn* (x₁,…,xn)) =f* (f₁* (x₁,…,xn),…,fn* (x₁,…,xn))

THEOREM IS PROVEN.

Corollary: Ф₁=Ф₂⇒ Ф₁*=Ф₂*.

Further, proving a theorem, by the principle of duality we immediately get a dual theorem: x1 ∨ x₂= x₁ ∧ x₂

x₁ ∧ x₂= x₁ ∨ x₂

By normal form we mean a syntactically unique way of writing a formula. We introduce a special kind of entry: xy=x ≡ y, if x = y, xy=1, if x ≠ y, xy=0

The decomposition theorem of a Boolean function can be represented as a disjunctive conjunction of conjunction: f (x₁,x₂,…,xm, xm+1,…,xn) =||= δ1, δ2,…,δmx₁δ ∧ x₂δ ∧…∧ xmδm ∧ f (δ₁, δ₂,…,δm, xm+1,…,xm)

where disjunctions are taken over all possible δ.

Proof: in order to prove that a given formula implements a function, it is enough to take an arbitrary set of argument values, calculate the values of formulas on this set and, if it turns out to be equal to the value of the function, then the formula really implements the function:

(δ1, δ2,…,δmx₁δ ∧ …∧ xmδm ∧ f (δ₁,…,δm, xm+1,…,xn)) (a₁,a₂,…,an) =δ1, δ2,…,δma₁δ1 ∧ …∧ amδm ∧ f (δ₁,…,δm, am+1,…,an) = aa1 ∧ a₂a2 ∧ …∧ amam∧ f (a₁,a₂,…,an) = f (a₁,a₂,…,an)

THEOREM IS PROVED.

1.24. Perfect normal forms

All algebraic terms of a formula include all variables. It is said that a certain class of formulas K has a normal form if there is another class of formulas K», which are called normal forms, such that any formula of the class K has a unique equivalent formula from the class K»: ∃K! ∀Ф∈K∃!Г∈K»∨Ф=Г

1.24.1. Perfect Disjunctive Normal Form

Representation of a Boolean function in the form (a disjunction is a union sign):

f (x₁,x₂,…,xn) =δ1, δ2,…,δmx₁δ1 ∧ x₂δ2 ∧ …∧ xnδn

is called a perfect disjunctive normal form (SDNF).

Theorem: ∀f ∈Pn ∨ {0} ∃ the only representation in the form of SDNF.

Proof: we use the decomposition theorem for a Boolean function:

f (x₁,x₂,…,xn) =δ1, δ2,…,δnx₁δ1 ∧ …∧ xnδn ∧ f (δ₁,…,δn)) =f (δ1, δ2,…,δn) =1x₁δ ∧ …∧ xnδn ∧ f (δ₁,…,δn)) =f (δ1, δ2,…,δn) =1x₁δ ∧ …∧ xnδn

THEOREM IS PROVED.

Theorem: every Boolean function can be expressed in terms of disjunction, conjunction and negation: ∀f ∈Pn∃Ф {¬, ∨, ∧} |funcФ=f

Proof:0=x ∧ x. In other cases, see the theorem above.

THEOREM IS PROVEN.

1.24.2. Perfect conjunctive normal forms

Theorem: every Boolean function can be represented in the form:

f (x₁,…,xn) =f (δ1, …,δ2) =1x₁δ ∨ … ∨ xnδn

Proof: by the duality principle from the SDNF theorem, it can be argued that every Boolean function has an SKNF.

Q.E.D.

1.25. Closed classes of Boolean functions

Let F be the set of Boolean functions: F= {f₁,f₂,…,fn},∀ifi∈ Pn

The closure of the set F is the set of Boolean functions realized by formulas over F: [F] = {f∈ Pn | f=func Ф [F]}

We introduce a special type of classes of Boolean functions.

– T₀= {f|f (0,0,…,0) =0} – a class of functions that preserves 0;

– T₁= {f|f (1,1,…,1) =1} – a class of functions that preserves 1;

– T*= {f|f =f*} is the class of self-dual functions;

– T≤= {f|α≤β⇒f (α) ≤f (β),α= (α₁,α₂,…,αn),β= (β₁,β₂,…,βn) ∀iai, bi∈ E₂,α≤β ⇔ ∀iai ≤ bi is the class of monotonic functions;

– TL= {f|f=x₀+C₁x₁+C₂x₂+…+Cnxn} is the class of linear functions.

Theorem: classes: T₀,T₁,T*,T≤,TL – closed.

Proof: in order to prove that some class is closed, it is enough to prove that if a function is implemented as a formula over this class, then it belongs to this class. The proof of the isolation of classes 4 and 5 is provided to readers as an exercise.

It can be proved that an arbitrary formula has this property by induction on the structure of formulas. The basis of each such induction is obvious. Functions from F are realized as trivial formulas over F. Thus, only inductive transitions need to be proved.

f₀,f₁,…,fn ∈ T₀, Ф= f₀ (f₁ (x₁,…,xn),…, fn (x₁,…,xn)) = f₀ (0,…,0) =0 ⇒ Ф ∈ T₀

f₀,f₁,…,fn ∈ T₁,, Ф= f₀ (f₁ (x₁,…,xn),…, fn (x₁,…,xn)) = f₀ (1,…,1) =1 ⇒ Ф ∈ T₁

f₀,f₁,…,fn ∈ T*,, Ф*= f₀* (f₁* (x₁,…,xn),…, fn* (x₁,…,xn)) = f₀ (f₁ (x₁,…,xn),…, fn (x₁,…,xn)) ⇒ Ф* ∈ T*,,

Q.E.D.

1.26. Completeness of a system of Boolean functions

As already mentioned, a Booleanis an arbitrary n-function place function f (x₁,x₂,…,xn), where xi ∈ {0,1}. The complete system of Boolean functions is denoted by E and has the following form: f₁ (x₁,x₂,…,xk1) f₂ (x₁,x₂,…,xk2) … fe (x₁,x₂,…,xke)

A system of functions Eis called complete if any of its Boolean functions can be expressed using f₁, f₂, … fe through superposition.

A superposition is a function f*, which is obtained from a function f using the following transformations:

– change of variable: f (x₁,x₂, xj, …,xn) f* = f (x₁,x₂, xj-1,y, xj+1, …,xn);

– substitution instead of xj of some function from the system.

f* = fi (x₁,x₂, xj-1, fe (x₁,x₂,…,xke),xj+1, …,xki)

Example: system of functions {¬, ∪, ⋂} =E1 is always complete, because each function of this system can be represented as SDNF, therefore, SDNF is a superposition through which any of the functions of the system can be expressed.

Example: the system of functions {¬, ∪} =E2 is also complete, since the missing function ∩ can be expressed in terms of the other two by the de Morgan rule and double negation:

x1 ⋂ x₂= ¬ (¬ x1 ∪ ¬ x₂)

Example: prove the completeness of the system: X → Y,0.

For clarity, this system can be written as follows: {→,0}. That is, we are given a system consisting of a Boolean function (implication) and a constant 0. With their help we can express the negation operation, for this we substitute the constant 0 instead of one of the variables:

X → 0= ¬ X ∪ 0 = ¬ X

Therefore, this system is complete.

Consider alternative definitions.

The set of Boolean functions of B= {f 1, f₂,fm,…,…} is called a full system if any Boolean function can be implemented by the formula above B.

Theorem (on completeness): let two systems of functions frombe given P₂: B₁= {f₁,f₂,…} and B₂= {g₁,g₂,…}. Then, if the system B₁ is complete and each of its functions can be realized by a formula over B₂, then the system B2 is also complete.

Proof: let h be an arbitrary function from P₂. We show that it can be realized by the formula over B₂.

Due to the completeness of B₁ h is realized by the formula over B₁, i.e. h= [ff₁,f₂,…]. In addition, by condition f₁,f₂,… are realized by formulas over B₂, i.e. fi=Фi [g₁,g₂,…]. Therefore, in the formula Ф we can exclude the occurrence of symbols of functions f₁,f₂,…, replacing them with the corresponding formulas: Ф [Ф₁ [g₁,g₂,…], Ф₂ [g₁,g₂,…],…], (1.26.5)

The resulting expression defines a formula over B₂that implements h.

THEOREM IS PROVEN

Example: the system {x,x ∧ y} is complete. Indeed, consider the systems B₁= {x,x ∧ y, x ∨ y} and B₂= {x,x ∧ y}. The system B₁ is complete and, since x ∨ y= x ∧ y, then each function of this system is expressed by a formula over B₂. Thus, the conditions of the completeness theorem are satisfied and, therefore, the system B₂= {x,x ∧ y} is a complete system.

Example: the system {x|y} is complete. Indeed, consider the systems B₁= {x,x ∧ y} and B₂= {x|y}. We have: x|y= x ∨ y =xy. Therefore:

x|x=xx=x and xy=x|y= (y) | (x|y), (1.26.6)

Thus, each function of the system B₁ is realized by a formula over B₂. In addition, system B₁ is complete. Therefore, the conditions of the completeness theorem are fulfilled and, therefore, B₂= {x|y} is a complete system.

2. COMBINATORY

2.1. The basic principles of combinatorics

Theorem (principle of multiplication): if some action can be performed in k stages, and the number of possible ways of i-thstage is equal to ni (i=1,2,…,k),then the total number Nk of all possible ways of performing said action is calculated according to the formula:

Nk=n₁*n₂*…*nk=∏i=1kni, (2.1.1)

Proof: we use induction on the number of stages. If k = 1 then, obviously, N₁ = n₁ and, therefore, formula (2.1.1) is valid for k = 1.

Further, let k = 2. Then, since each of the n₁ methods for implementing the first stage can take place with each of the n₂ methods for implementing the second stage, then N₂=n₁*n₂, i.e. formula (2.1.1) is also valid for k = 2.

Now suppose that formula (2.1.1) is valid for k = m – 1, i.e. the formula holds:

Nm-1=∏i=1m-1ni, (2.1.2)

Then, if k = m then, considering the first m – 1 stages as the first stage with the total number of implementation methods defined by the formula (2.1.2), and applying a result similar to the second step of induction, we obtain:

Nm=Nm-1*nm=∏i=1mni,

i.e. formula (2.1.1) is also valid for k = m.

THEOREM IS PROVEN.

Theorem: the number of elements of the Cartesian product is equal to the product of the numbers of the elements of the set participating in this Cartesian product:

|X×Y|=|X|*|Y|

Proof: Consider an action consisting of 2 stages. The first stage is the choice of the 1st element of an ordered pair. The second stage – the choice of the 2nd element of an ordered pair.

Then the 1st stage can be completed in |X| steps, the 2nd stage in |Y| steps. By the principle of multiplication,

THEOREM IS PROVED.

Theorem: the number of all possible functions from M to N, where the number of elements |M|=n, the number of elements |N|=m, is mn.

Proof: the first element from the set M can be mapped to m elements, the second element from the set M can be mapped to m elements, the third n etc. We get: m*m*…*m=∏i=1nmi=mn, where ∀i mi = m.

THEOREM IS PROVEN.

Theorem (addition principle): if object a can be obtained in n ways, object b – in m ways, then object «a or b» can be obtained in n + m – k ways, where k is the number of repeated methods. Set theoretic wording. If A ⋂ B ≠ ∅,then| ∪ || || || AB=A+B-A ⋂ |

Lemma: If A ⋂ B=∅,then |A ⋂ B|= 0,then |A ∪ |=|A|+|B|B.

Proof of the lemma: let A and B be finite sets such that A ⋂ B=∅, |A|=m, |B|=n. If the element a ∈ A can be selected in m ways, and the element b ∈ B – n ways, then the elementselected in x ∈ A ∪ B can be m + n ways. Let X₁,X₂,…,Xk be pairwise disjoint sets, Xi ⋂ Xj =∅, where i ≠ j. Then, obviously, the equality holds:

| ∪i=1kXi|= ∑i=1k|Xi|

The lemma is proved.

Proof of the principle: if we consider the union of two sets A and B, then we will not change anything if we consider a union of this kind:

A ∪ B=A ∪ (B\A)

It can be opened:

A ∪ B=A ∪ (B ⋂ A)

Now the number of union elements is:

|A ∪ B|=|A ∪ (B\A) |

Next we consider A ⋂ (B\A), which is equal to ∅. Accordingly, you can open the difference of the sets:

A ⋂ B ⋂ A= ∅ ⋂ B= ∅

We have the intersection of two sets, it is empty and there are the number of elements combining these sets. We use the lemma. We get:

|A ∪ B|=|A| + |B\A|

Further we consider the set B, it is:

B= (A ⋂ B) ∪ (B\A)

Moreover, if we take the intersection of these sets, we get:

(A ⋂ B) ⋂ (B\A) = ∅

Once again we return to the lemma and get: |B|= |A ⋂ B| ∪ |B\A|. Let us express from here: |B\A|, |B\A|= |B| – |A ⋂ B|

Substitute it in: |A ∪ B| =|A ∪ (B\A) | and get: |A ∪ B| =|A| + |B| – |A ⋂ B|

PRINCIPLE PROVED.

2.2. Placements

A placement with repetitions is the function f: {x₁,x₂,…,xm} → {y₁,y₂,…,yn}. Elements xi are called objects, and yj – drawers.

Placements with repetitions – combinatorial compounds made up of n elements of m. Moreover, each of the n elements may be contained as many times as desired or absent altogether.

Theorem: the number of all arrangements with repetitions is equal to the number of sequences {a₁,a₂,…,am} of numbers 1 ≤ ai ≤ n and, therefore, it is equal to nm.

Non-repetitive placements are combinatorial compounds made up of n elements of m each. In this case, two compounds are considered different if they either differ from each other by at least one element, or consist of the same elements, but located in different order.

Theorem: the number of placements without repetition is:

Anm= ((n!) / (nm)!)

Proof: the first item can be placed in n ways, the second – (n – 1), ⋅⋅⋅, mth– (n – m +1). We get: Anm=n (n-1) … (n-m+1) = ((n!) / (nm)!)

THEOREM IS PROVEN.

2.3. Combinations

Of a combination of elements of the set X is a subset of a finite set A ⊆ X. If |A|=k,|X|=n, then the subset A is called a combination of n in k, denoted by: Cnk. For example, combinations of the three colors of a seven-color rainbow will be described by subsets of three elements.

The combination can be interpreted as the placement of indistinguishable objects. Combinations are a k-element subset of a given set.

Theorem: the number of combinations of n over k is equal to:

Cnk= ((n!) / (k! (nk)!))

Proof 1: from the formulas: Akn=Ckn*k! and Ank= ((n!) / ((nk)!) – we get the necessary formula.

THEOREM IS PROVEN.

Proof 2: we consider an action consisting of two stages.

Stage I: n₁=Cnk-1

Stage II: n₂= (n-k+1) / (k), Cnk=Cnk-1* ((n-k+1) / (k))

Using this formula, we get: Cnk= ((n!) / (k! (nk)!))

THEOREM IS PROVEN.

Property 1: Cnk= Cn-1k-1+ Cn-2k-1 +…+Ck-1k-1

Proof (by induction): for n = 1, the induction basis holds.

For n = n +1: Cn+1k=Cnk-1+Cnk

Cn+1k=Cnk-1+Cn-1k-1+Cn-2k-1 +…+Ck-1k-1

((n+1)!) / (k! (n+1-k)!) = (n!) / ((k-1)! ((n-k+1)!)) + (n!) / (k! (n-k)!)

(n!* (n+1)!) / ((k-1)!*k (n-k)!* (n-k+1)) = (n!) / ((k-1)! (n-k)!* (n-k+1)) + (n!) / ((k-1)!*k (n-k)!)

(n+1) / (k (n-k+1)) = (1) / (n-k+1) + (1) / (k)

(n+1) / (k (n-k+1)) = (k+n-k+1) / (k* (n-k+1))

1 = 1 (true). Thus, the statement is true for any n.

PROPERTY PROVED

Proof (combinatorial):

Cnk=Cn-1k-1+Cn-2k-1 +…+Ckk-1+ CK-1k-1

Cn+1k=Cnk-1+Cnk

Cn-1k=Cn-1k-1+Cn-1k

Cn-1k=Cn-2k-1+Cn-2k

Cn-2k=Cn-3k-1+Cn-3k

…

Ck+1k=Ckk-1+Ckk

PROPERTY PROVED.

Property 2: Cnk=Cn-1k+Cn-1k-1

Proof:

((n-1)!) / (k! (n-1-k)!) + ((n-1)!) / ((k-1)! ((n-1-k+1)!)) = ((n-1)!) / (k! (n-1-k)!) + ((n-1)!) / ((n-1)! (n-k)!)) = ((n-1)! (n-k)) / (k! (n-k)!) + ((n-1)!k) / (k! (n-k)!) = ((n-1)! (n-k+k)) / (k! (n-k)!) + (n!) / (k! (n-k)!)

PROPERTY IS PROVED.

Property 3: Blaise Pascal suggested to consider and illustrate the properties associated with binomial coefficients, consider the Pascal triangle.

Fig. 2.1 – Pascal Triangle

Theorem:∑k=0n Cnk=2n

Proof (combinatorial): on the left side of the equality is the number of all possible subsets of the set – by the Boolean theorem this number is 2n.

THEOREM IS PROVEN

Proof (by induction):

– For k = 0: ∑k=0⁰ C₀k=C₀⁰=1=2⁰ the ⇒ equality is true.

– Assume that the equality holds for k = n, we prove the equality for k = n +1, i.e. we prove the equality: ∑k=0n+1 Cn+1k=2n+1=2* ∑k=0nCnk, or: Cn+1⁰+Cn+1¹+Cn+1²+Cn+1³+…+Cn+1n-1+Cn+1n+Cn+1n+1=2 (Cn⁰+Cn¹+Cn²+Cnn-2+Cnn-1+Cnn), (2.3.1)

To prove equality (2.3.1), we use: Cn+1k=Cnk-1+Cnk, (2.3.2)

Let us prove this equality: (n! (N+1)) / (k! (nk)! (n-k+1)) = (n!k) / (k! (nk)! (n-k+1)) + (n!) / (k! (nk)!)

(n+1) / (n-k+1) = (k) / (n-k+1) +1 ⇔ (n+1) / (n-k+1) = (n+1) / (n-k+1) the ⇒ equality (2.3.2) is proved. We return to the proof of (2.3.1): using equality (2.3.2) we obtain that: Cn+1¹=Cn⁰+Cn¹;Cn+1²=Cn¹+Cn²

…

Cn+1n-1=Cnn-2+Cnn-1;Cn+1n=Cnn-1+Cnn

i.e. equality (2.3.1) takes the form: Cn+1⁰+Cn+1n+1=Cn⁰+Cnn;1+1=1+1⇒

THEOREM IS PROVED.

Property 4: Cmn=Cmmn is the symmetry of the Pascal triangle.

Proof: (m!) / (n! (m-n)!) = (m!) / ((m-n)! (m-m+n)!)

PROPERTY PROVED.

Property 5: CniCim=CnmCnmim

Proof: (n!) / (i! (n-i)!) * (i!) / (m! (i-m)!) = (n!) / (m! (n-m)!) * ((n-m)!) / ((i-m)! (n-m-i+m)!)

PROPERTY PROVED.

Suppose there are objects of n different kinds, and from them are made up sets containing k elements. Such samples are called repeat combinations. Their number is denoted by Cnk.

Theorem: The number of combinations with repetitions can be calculated by the formula: Cmn=Cn+m-1n= ((n+m-1)!) / (n! (m-1)!), (2.3.3)

Example (cake problem): let it be required in the store to buy 7 cakes. The store has cakes of one of the types: eclairs, sand, puff, Napoleon. How many choices?

With each purchase we put in correspondence a sequence consisting of seven units and three delimiters 0. A total of 4 types of cakes, then zeros – 3.

Option table Table 2.1

Summarize the previous problem. The number of purchase options is equal to the number of permutations of n type I elements (units (cakes)) and m type II objects (zeros (delimiters)). Thus, rearranging by all means n units and (m – 1) zeros, we get the desired number:

P (n,m-1) = ((n+m-1)!) / (n! (m-1)!) =Cmn

The solution to the generalized purchase problem is a proof of (2.3.3).

2.4. Number of permutations

Letbe given n₁ elements of the first type, n₂ – the second type, …, nk – thek-th type, total n elements. Ways to place them in n different places are called repetitive permutations. Their number is denoted by:

Pn (n₁,n₂,…,nk)

Theorem: the number of permutations without repetition is:

Pn (k₁,k₂,…,km) = (n!) / (k₁!k₂!…,km!)

Proof: a subset of A₁ can be chosen Cnk1 in ways. A subset of A₂ is selected from the remaining (n – k₁) elements, it can be selected in Cn-k1k2 ways. A subset of A₃ – Cn-k1-k2k3 ways, etc. Select a subset Am defined by previous subsets. From here we get: P(k1,k2,…,km)=Cnk1Cn-k1k2…Cn-k1-… -km-2km-1= (n!) / (k₁! (n-k₁)!) * ((n-k₁)!) / (k₂! (n-k₁-k₂)!) … ((n-k₁-… -km-2)!) / (km-1! (n-k₁-… -km-2-km-1)!)

Since n-k₁-… -km-1= km, then after reducing the fraction we get the desired equality.

THEOREM IS PROVEN.

The number of one-to-one functions, or the number of permutations of n objects, is denoted by P (n).

Theorem: the number of permutations of elements is n! or n elements can be rearranged n! way, i.e. P (n) =n!

Proof: we can put the first item in one of n positions, the second in (n – 1), etc., the last item can only be put in one place, and this is the definition of n!:

P (n) =Ann=n* (n-1) *…* (n-n+1) =n* (n-1) *…*1=n!, (2.4.4)

THEOREM IS PROVED.

Comment. Fair recurrence formula: P (n) =n*Pn-1

2.5. Inclusion and exclusion formula (main theorem)

The formulas and algorithms given in the previous sections give methods for calculating combinatorial numbers for some common combinatorial configurations. Practical tasks are not always directly reduced to known combinatorial configurations. In this case, various methods are used to reduce some combinatorial configurations to others.

Consider the principle of inclusion and exclusion.

The rule (principle) of inclusion / exclusion allows you to calculate the power of the union of sets if their powers and powers of all intersections are known.

Theorem:|i=1nAi|=∑i=1n|Ai|-∑I≤i1≤i2≤n|Ai1 ⋂ Ai2 |+…+ (-1) k+1∑I≤i1≤…≤i2≤n|Ai1 ⋂ Ai2 ⋂…⋂ Aik |+ …+ (-1) n+1|Ai1 ⋂ Ai2 ⋂…⋂ Ain |

Proof: by induction, for n = 1, the statement is obvious.

For n = 2, we obtain the addition theorem, i.e. if A ⋂ B=∅,then|∪|| || ||AB=A+B-A⋂|

Let it be true for n – 1, we prove for n. Note that the relation holds: (i=1n-1Ai) ⋂ An= i=1n-1 (Ai ⋂ An)

and for (n – 1) it holds.

Let us prove for n: |i=1nAi|=| (i=1n-1Ai) ∪ An|=|i=1n-1Ai|+|An|-| (i=1n-1Ai) ⋂ An|= ∑i=1n-1|Ai|-∑I≤i <j≤n-1|Ai ⋂ Aj|+…+ (-1) n|A1 ⋂ A2 ⋂…⋂ An-1 |+|An|-∑I≤i≤n-1|Ai ⋂ An|+ ∑I≤i <j≤n-1 |Ai ⋂ Aj⋂ An|+…=∑i=1n-1|Ai|-∑I≤i <j≤n-1|Ai ⋂ Aj|+…+ (-1) n+1|A1 ⋂ A2 ⋂…⋂ An|

Therefore, the statement is true for n sets.

Q.E.D.

Formulation using Euler-Venn diagrams: 3 setsare marked on the diagram A, B, C:

Fig. 2.2 – Illustration to the inclusion-exclusion formula

Then the area of the union A ∪ B ∪ C is equal to the sum of the areas A, B, C minus the twice-covered areas A ⋂ B,A ⋂ C,B ⋂ C, but with the addition of the three-times covered area A ⋂ B ⋂ C: S (A ∪ B ∪ C) =S (A) +S (B) +S (C) -S (A⋂B) -S (A⋂C) -S (B⋂C) +S (A⋂B⋂C)

In a similar way, it is generalized to the union of n sets.

2.5.1. A special case of the theorem on inclusions and exceptions

In some cases, the number of objects that have a certain set of properties depends only on the number of these properties. Then the formula for counting the number of objects that do not have any of the selected properties is simplified.

For arbitrary n we have: N (n) =n! -Cn¹*N (1) +Cn²*N (2) -…+ (-1) nN (n)

In the general case, when rearranging n objects, the number of arrangements in which no object is located on in its place: N (n) =n! -Cn¹* (n-1)! +Cn²* (n-2)! -…+ (-1) n0!=Dn

The resulting value of Dn is sometimes called a complete disorder formula or sub-factor. The subfactorial Dn can also be represented as follows: Dn=n! [1- (1) / (1!) + (1) / (2!) – (1) / (3!) +…+ (-1) n/ (n!)]

where the expression in […] tends to e⁻¹ with an unlimited increase in n.

A subfactorial has properties similar to those of a regular factorial. For example:

– n!= (N-1) [(n-1)!+ (N-2)!] – for a regular factorial;

– Dn= (n-1) [Dn-1+Dn-2] – for the sub-factorial.

Subfactorials are calculated by the formula: Dn=nDn-1+ (-1) n

2.5.2. Caravan

Problem Let us consider a problem in which a solution can be obtained using the main combinatorics theorem.

Task: 9 camels go in a bargain. How many combinations of camel rearrangements exist, in which no camel follows the one he followed earlier?

We distinguish the forbidden pairs: (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7),

(7, 8), (8, 9) To solve, we apply the main theorem of combinatorics.

To do this, we define what an object is and what properties are. By objects we mean various arrangements of camels. In total there will be N = 9!. By properties we mean the presence of a certain pair

in the permutation. Thus, the number of properties is 8. Then the number of permutations that do not have any of the 8 properties: N (8) =9! -C₈¹*8!+C₈²*7! -C₈³*6!+C₈⁴*5! -C₈⁵*4!+C₈⁶*3! -C₈⁷*2!+C₈⁸*1!=142729=D₉=D₈

In the general case, for n camels, we have: Dn+Dn-1

2.5.3. Problem about disturbances

Set we denote all permutations by S, and the list of properties will consist of properties pi: property pi is the property of this or that substitution to leave elementin place i. It is clear that disorder is just such a permutation that does not have any properties from P= {p₁,…,pn}. Following the inclusion-exclusion formula, we get: N=M-∑i=1nS(pi)+∑i,jS(pipj)-…+(-1)k∑pi1,pi2,…pik,S(pi1,pi2,…pik)+…+(-1)nS(p1,p2,…pn) =n! -Cn¹ (n-1)!+Cn² (n-2)! -…+ (-1) kCnk (n-k)!+…+ (-1) n=n! (1—1+ (1) / (2!) – (1) / (3!) +…+ (-1) k/ (k!) +…+ (-1) n/ (n!)) ≈ (n!) / (e).

2.6. The concept of a lattice, a distributive lattice

A lattice is a partially ordered set in which each two-element subset has both an exact upper (sup) and an exact lower (inf) face. This implies the existence of these faces for any nonempty finite subsets.

Any two elements in such a partially ordered set must be comparable: ∀a,b must be either a ≤ b ∨ b ≤ a.

Precision (smallest) of the upper edge (boundary) or supremum subset X ordered set (or class) M, is the smallest element M, which is equal to or more than all of the elements of X.In other words, the supremum is the smallest of all the upper faces.

More ∈ formally: SX= {yM | ∈ ≤

the set of upper bounds of X, that is, elements of M, equal to or greater than any element X.

s=sup sup X ⇔ ∈ s Sx ∧ ∀y ∈ Sx: s ≤ y)

H=sup sup (a,b) = ∧ – the exact upper face of the two elements.

Precision (maximum) of the bottom face (boundary) orinfimum subset X of an ordered set (or class) M, is called the largest element M, which is equal to or less than all of the elements of X.In other words, the infimum is the largest of all the lower faces.

L=inf inf (a,b) = ∨ – the exact lower bound of the two elements.

Theorem: if the lower (upper) face exists, then it is unique.

Proof: x=inf inf (a,b) ∧ y =inf inf (a,b) ⇒ y≤x ∧ x≤y ⇒ x=y

THEOREM IS PROVED.

A lattice is called distributive if sup and inf are distributive:

a∪ (b⋂c) = (a∪b) ⋂ (a∪c),a⋂ (b∪c) = (a⋂b) ∪ (a⋂c), (2.6.4)

Lemma: the set of natural numbers N⁺ is a lattice with respect to operations ≤,max, min.

Proof: by definition, a lattice is a partially ordered set. Let us show that the set of natural numbers is a partially ordered set. Moreover, a linearly ordered set.

Consider the relation ≤. This is a relation of order because it is:

– Reflective:∀a ∈ N,a ≤ a

– Transitive: ∀a,b,c ∈ N,a ≤ b ⋂ b ≤ c ⇒ a ≤ c

– Antisymmetric: ∀a,b ∈ N,a ≤ b ⋂ b ≤ a ⇒ a = b

In addition, there are many natural numbers linearly ordered, because: ∀a,b ∈ N,a ≤ b ⋂ b ≤ a)

To prove that the set N is a lattice, it remains to show that for any two-element subset X ⊂ N there are exact upper and lower faces. This follows from linear ordering. X= {a,b}

Supposeb a ≤ b. Then: in fX=a, supX=b

Similarly, we can reason for another case.

APPROVED PROVEN

2.7. The principle of mathematical induction

Formulation: suppose that it is required to establish the validity of an infinite sequence of statements numbered by natural numbers: P (1),P (2),…,P (n),P (n+1).

Assume that:

– It is established thatP (1) is true (this statement is called the base of induction).

– For anyn, it is proved that ifP (n) is true, thenis trueP (n +1) (this statement is called the induction transition).

Then all the statements of our sequence are true.

Proof:

– induction basis. Let P (1) be true, i.e.holds P (k) for some k ∈ N⁺.

– inductive step. If (P + k) – true, then ∀n ∈ N+ P (n) – true.

We prove that the method of mathematical induction can be applied using the method of proof by contradiction. Suppose that for some numbers in the natural series the method of mathematical induction is incorrect.

Let them form the set N» ⊆ N⁺. N⁺ is a lattice with respect to the operations ≤,max, min (by the lemma proved in Section 2.6); therefore, N», as its subset, is also a lattice ⇒ ∃m | ∀k ∈ N»(m,k) =m.

– If m = 1, then a contradiction with (a) the condition.

– If m ≠ 1, then (m – 1) is not natural.

P (m – 1 +1) is true (by condition (b)); therefore, P (m) is true (a contradiction to condition (b)).

PRINCIPLE PROVED

2.8. The Cantor diagonal method

If each element of the set X corresponds to a single element from the set Y, then it is said that a one-to-one correspondence is established between these sets.

Consider 2 infinite sets: the

– set of natural numbers 1, 2, 3, 4, 5, …, n, …;

– the set of even positive integers 2, 4, 6, …, 2n, … (this is a subset of the first set).

Since a series of even numbers can be numbered using natural numbers, a one-to-one correspondence can be established between these two sets. If a one-to-one correspondence cannot be established between a set and its certain subset, then the set is finite.

A set equivalent to a set of natural numbers is called countable. In other words, a countable set can be established one-to-one correspondence with a set of natural numbers.

Theorem: the set of real numbers of the interval [0, 1] is uncountable.

Proof (by diagonalization method): each number is represented as an infinite decimal fraction: 0. a₁ a₂ a₃… consisting of digits and not having a period of 9. Suppose that some countable set (of all or only some) of real numbersalying on the interval [0, 1]. Then they can be arranged as a list of lines:

0. a₁₁ a₁₂ a₁₃ a₁₄…

0. a₂₁ a₂₂ a₂₃ a₂₄…

0. a₃₁ a₃₂ a₃₃ a₃₄…

…

Consider the sequence of numbers: b₁≠a₁₁,b₂≠a₂₂,b₃≠a₃₃,…,not equal to 9. Then the number 0. b₁ b₂ b3is… not in the list, although it is in the interval on the segment [0, 1]. This means that all real numbers from this segment cannot be enumerated using natural numbers. Thus, no countable set of real numbers lying on the segment [0, 1] does not exhaust this segment.

THEOREM IS PROVEN.

2.9. The principle of transfinite induction

Transfinite induction is a method of proof that generalizes mathematical induction to the case of an uncountable number of parameter values.

Transfinite induction is based on the following statement.

Statement: let a completely ordered setbe given A. P (x),x ∈ A is a statement. Suppose that for each element of the set A, since P (y) is true for all y <x, it follows that p (x) is true. Then the statement P (x) is true for any x.

Mathematical induction is a special case of transfinite induction. Indeed, let M be the set of natural numbers. Then the statement of transfinite induction turns into the following: if for any positive integer n the truth of statements P (1), P (2), …, P (n – 1) implies the truth of statement P (n), then all statements P (n) Moreover, the induction base, that is, P (1), turns out to be a trivial special case for n = 1.

2.10. Newton’s binomial
2.10.1. Case of two variables

Formula (Newton’s binomial). A formula for decomposing into separate terms a non-negative integer power of the sum of two variables, having the form: (a+b) n=∑k=0nCnkankbk

Proof (by induction). We have the formula: (a+b) n=∑k=0nCnianibi= Cn⁰an+ Cn¹an-1b¹+…+Cnna⁰bn

Induction base: for n = 2, the statement is obvious: (a+b) 2=C₂⁰a²b⁰+ C₂¹a¹b¹+C₂²a⁰b²=a²+2ab+b²

Induction step: suppose that the statement is true for n – 1 and show that it will be true for n. (a+b) n-1=∑i=0n-1Cn-1ian-1-ibi

(a+b) n= (a+b) n-1* (a+b) = ∑i=0n-1Cn-1ian-1-ibi* (a+b)

Which is equivalent: (Cn-1⁰an-1b⁰+Cn-1¹an-2b¹+…+Cn-1n-1a⁰bn-1) * (a+b)

And: Cn-1⁰anb⁰+Cn-1¹an-1b¹+…+Cn-1n-1a¹bn-1+Cn-1⁰an-1b¹+Cn-1¹an-2b²+…+Cn-1n-1a⁰bn

Group the terms: Cn-1⁰an+ (Cn-1⁰+Cn-1¹) an-1b¹+…+Cn-1n-1bn

Using the proven earlier identity Cnk=Cn-1k+ Cn-1k-1 we get:

Cn⁰an+Cn¹an-1b¹+Cn²an-2b²+…+Cnnbn

WHAT YOU NEED TO PROVE.

2.10.2. Ordered partitions and the generalized

Newton bin recall that a partition of a set A is the family {Ai} of its pairwise disjoint subsets such that: ∪i Ai=A. Thesubsets Ai are called partition blocks. If the family takes into account the order of the subsets, then it is called an ordered partition. We say that the ordered partition (A₁,A₂,…,Am of the) set E= {e₁,e₂,…,en} is of type (k₁,k₂,…,km) if |A₁|=k₁,|A₂|=k₂,…,|Am|=km. The number of such partitions is denoted by P (k₁,k₂,…,km) or Pn (k₁,k₂,…,km), where n=k₁+k₂+…+km.

Pn (k₁,k₂,…,km) = (n!) / (k₁!k₂!…km!)

This is the number of permutations with repetitions. For the proof of this formula, see §2.4.

Theorem: (x₁+x₂+…+xm) n=n!∑k1+k2+…+km=n ((1) / (k₁!k₂!…km!)) x₁k1x₂k2…xmkm

Proof: we consider how the boxes are factors of the product: (x₁+x₂+…+xm) (x₁+x₂+…+xm) … (x₁