Discrete Math. For students of technical specialties

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: x1≤xx2 if and only if φ (x1) ≤yφ (x2), 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 ∑= (φ1, φ2,…φ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 (n1,n2,…,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: ∀x1,x2,…,xn ∈ X φ (x1,x2,…,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 (x1,…,xn) ∈ Xi ⇒ ∀ j φjXi (x1,…,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 d1,d2,…,dn are any elements from D, then the element d1,d2,…,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-1: B → A is also an isomorphism.

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

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

denote B1:= f (a1) …,bn:= f (a wherein a1 = f-1 (b1) …,an=f-1 ()

Then: f-1 (ψ (b1,…,bn)) =f-1 (ψ (f (a1),…,f (an))) =f-1 (f (φ (a1,…,an))) =φ (a1,…,an) =φ (f-1 (b1),…,f-1 (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: ∃ e1,e2 ∀a: a o e1=e1 o a= a & a o e2=e2 o a= a. Then: e1 o e2=e1 & e1 o e2 =e2 ⇒ e1=e2

THEOREM IS PROVEN.

A group is a monoid in which: ∀ a ∈ M ∃ a-1 ∈ M | a o a-1 = a-1 o a=e. The element a-1 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: ⊗:M2→M is the multiplication and ⊕:M2→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-1 | a-1⊗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= be a field with the addition operation +, the operation of multiplication., the additive unit 0 and the multiplicative unit 1. Let 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 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; i1,i2,…,in)

we will set the line (i1,i2,…,in).

A permutation is called cyclic (or a cycle) if some number j1 is translated by it into j2, j2 – by j3, etc., jk-1 is translated into jk, jk – by j1, and all the others the numbers remain in place. Such a cycle is denoted by (j1,j2,…,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 π1 and π2 consists in their sequential application. For example, if: π1= (1,2,3,4;2,4,3,1) π2= (1,2,3,4;1,4,3,2)

then: π1π2= (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;i1,i2,…,in)

is the substitution: ( i1,i2,…,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 b1 cycles of length 1, b2 cycles of length 2, etc., bn cycles of length n, then they say that the substitution is of the type: b1,b2,…,bn For example, wildcard: π1= (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 f1 and f2 from NM are called equivalent (f1 ~ f2) if: ∃π | f1 (πx) = f2 (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:E2n → E2

where E2n = {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:E2n → E2}

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 x2 Is an inconsequential variable. The variablevalue of functions x2 does not affect the, i.e. the value of the function does not significantly depend on the variable x2. f1=x1,f2= ¬ x1

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= (f1,f2,…,fn), ∀ i: fi ∈ Pn

Formula over F: Ф [F] = fi (t1,t2,…,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. F1=F2:=func (F1) =f&func (F2) =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 (E2, ¬, ∨, ∧) 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. ∀Г (Ф1 (…x…) =Ф2 (…x…)) Ф1 (…x…) {Г\\x} =Ф2 (…х…) {Г\\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=Г2⇒ Ф (…Г…) {Г1\Г} =Ф (…Г…) {Г2\Г}

1.22. Algebra of Boolean functions

Define the conjunction, disjunction and negation functions: ∧, ∨: Pn2 → 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.