Associativity

x 1 (x 2 x 3) = (x 1 x 2)x 3;

x 1 Ú (x 2 Ú x 3) = (x 1 Ú x 2) Ú x 3.

Commutativity

x 1 x 2 = x 2 x 1

x 1 Ú x 2 = x 2 Ú x 1

Distributivity of conjunction relative to disjunction

x 1 (x 2 Ú x 3) = x 1 x 2 Ú x 1 x 3.

Distributivity of a disjunction relative to a conjunction

x 1 Ú(x 2 × x 3) = (x 1 Úx 2) × (x 1 Úx 3). *

Idempotency (tautology)

Twice no

Properties of constants

x & 1 = x; (laws of universal set)

x & 0 = 0; (null set laws)

De Morgan's rules (laws)

Law of contradiction (complementarity)

Law of exclusion of the third (complementarity)

The proofs of all these formulas are trivial. One option is to construct truth tables of the left and right sides and compare them.

Gluing rules

The gluing rule for elementary conjunctions follows from the distributive law, the law of complementarity and the law of the universal set: the disjunction of two adjacent conjunctions can be replaced by one elementary conjunction, which is a common part of the original conjunctions .

The gluing rule for elementary sums follows from the distribution law of the second kind, the law of complementarity and the law of the zero set: the conjunction of two adjacent disjunctions can be replaced by one elementary disjunction, which is a common part of the original disjunctions .

Takeover rule

The absorption rule for the sum of two elementary products follows from the distribution law of the first kind and the laws of the universal set: the disjunction of two elementary conjunctions, one of which is an integral part of the other, can be replaced by a conjunction having a smaller number of operands .

The absorption rule for the product of elementary sums follows from the distribution law of the second kind and the laws of the zero set: the conjunction of two elementary disjunctions, one of which is a component of the other, can be replaced by an elementary disjunction that has a smaller number of operands.

Deployment Rule

This rule defines the opposite action to gluing.

The rule for expanding an elementary product into a logical sum of elementary products of higher rank (in the limit up to r = n, i.e. up to the constituents of unity, as will be discussed below) follows from the laws of the universal set, the distribution law of the first kind and is carried out in three stages:

In the expanded elementary product of rank r, n-r units are introduced as factors, where n is the rank of the constituents of the unit;

Each unit is replaced by the logical sum of a variable not present in the original elementary product and its negation: x i v `x i = 1;

All brackets are expanded based on the distribution law of the first kind, which leads to the expansion of the original elementary product of rank r into the logical sum 2 n-r constituents of unity.

The elementary product expansion rule is used to minimize functions of logic algebra (FAL).

The rule for expanding an elementary sum of rank r to the product of elementary sums of rank n (constituent of zero) follows the laws of the null set (6) and the distribution law of the second kind (14) and is carried out in three stages:

In the expanded sum of rank r, n-r zeros are introduced as terms;

Each zero is represented as a logical product of some variable not present in the original sum and its negation: x i·` x i = 0;

The resulting expression is transformed on the basis of the distribution law of the second kind (14) in such a way that the original sum of rank r turns into a logical product of 2 n-r constituents of zero.

16. The concept of a complete system. Examples of complete systems (with proof)

Definition. A set of functions of the algebra of logic A is called a complete system (in P2) if any function of the algebra of logic can be expressed by a formula over A.

System of functions A=( f 1, f 1,…, f m), which is complete, is called basis.

A minimal basis is a basis for which the removal of at least one function f 1, forming this basis, transforms the system of functions (f 1 , f 1 ,…, f m) incomplete.

Theorem. The system A = (∨, &, ) is complete.

Proof. If a logical algebra function f is not identically zero, then f is expressed in the form of a perfect disjunctive normal form, which includes only disjunction, conjunction and negation. If f ≡ 0, then f = x & x. The theorem has been proven.

Lemma. If system A is complete, and any function of system A can be expressed by a formula over some other system B, then B is also a complete system.

Proof. Let's consider an arbitrary logical algebra function f (x 1 , ..., x n) and two systems of functions: A = (g 1 , g 2 , ...) and B = (h 1 , h 2 , ...). Due to the fact that the system A is complete, the function f can be expressed as a formula over it:

f (x 1 , …, x n) = ℑ

where g i = ℜ i

that is, the function f is represented as

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

in other words, it can be represented by a formula over B. In this way, going through all the functions of the algebra of logic, we find that the system B is also complete. The lemma is proven.

Theorem. The following systems are complete in P2:

4) (&, ⊕ , 1)Zhegalkin basis.

Proof.

1) It is known (Theorem 3) that the system A = (&, V, ) is complete. Let us show that the system B = ( V, . Indeed, from de Morgan’s law (x& y) = (x ∨ y) we obtain that x & y = (x ∨ y), that is, the conjunction is expressed through disjunction and negation, and all functions of system A are expressed by formulas over system B. According to the lemma, system B is complete.

2) Similar to point 1: (x ∨ y) = x & y ⇔ x ∨ y =(x & y) and from Lemma 2 the truth of the statement in point 2 follows.

3) x | y=(x&y), x | x = x ; x & y = (x | y) = (x | y) | (x | y) and according to Lemma 2 the system is complete.

4) x = x ⊕1 and according to Lemma 2 the system is complete.

The theorem has been proven.

17.Zhegalkin algebra. Properties of operations and completeness

The set of Boolean functions defined in the Zhegalkin basis S4=(⊕,&,1) is called Zhegalkin algebra.

Basic properties.

1. commutativity

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. associativity

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. distributivity

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. properties of constants

5. h⊕h=0 h&h=h
Statement. All other Boolean functions can be expressed through the operations of Zhegalkin algebra:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18. Zhegalkin polynomial. Methods of construction. Example.

Zhegalkin polynomial (polynomial modulo 2) from n variables x 1 ,x 2 ... x n is called an expression of the form:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

where the constants C k can take values 0 or 1.

If the Zhegalkin polynomial does not contain products of individual variables, then it is called linear (linear function).

For example, f=x⊕yz⊕xyz and f 1 =1⊕x⊕y⊕z are polynomials, the second being a linear function.

Theorem. Each Boolean function is represented in the form of a Zhegalkin polynomial in a unique way.

Let us present the main methods for constructing Zhegalkin polynomials from a given function.

1. Method of undetermined coefficients. Let P(x 1 ,x 2 ... x n) be the desired Zhegalkin polynomial that implements the given function f(x 1 ,x 2 ... x n). Let's write it in the form

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Let's find the coefficients C k. To do this, we sequentially assign the variables x 1 , x 2 ... x n values from each row of the truth table. As a result, we obtain a system of 2 n equations with 2 n unknowns, which has a unique solution. Having solved it, we find the coefficients of the polynomial P(X 1 ,X 2 ... X n).

2. A method based on transforming formulas over a set of connectives (,&). Build some formula F over the set of connectives (,&) that realizes the given function f(X 1 ,X 2 ... X n). Then replace subformulas of the form A with A⊕1 everywhere, open the brackets using the distributive law (see property 3), and then apply properties 4 and 5.

Example. Construct the Zhegalkin polynomial of the function f(X,Y)=X→Y

Solution.
1. (method of undetermined coefficients). Let us write the required polynomial in the form:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Using the truth table of the implication, we find that

f(0,0)=P(0,0)=C 0 =1

f(0,1)=P(0,1)=C 0 ⊕C 2 =1

f(1,0)=P(1,0)=C 0 ⊕C 1 =0

f(1,1)=P(1,1)=C 0 ⊕C 1 ⊕C 2 ⊕C 12 =1

From where we consistently find, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Therefore: x→y=1⊕X⊕XY.

2. (Formula conversion method.). We have: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Note that the advantage of Zhegalkin algebra (compared to other algebras) is the arithmetization of logic, which makes it possible to perform transformations of Boolean functions quite simply. Its disadvantage compared to Boolean algebra is the cumbersomeness of the formulas.

Related information.

Absorption theorem written in two forms - disjunctive and

conjunctive, respectively:

A + AB = A (16)

A(A + B)=A (17)

Let's prove the first theorem. Let's take the letter A out of brackets:

A + AB= A(1 + B)

According to Theorem (3) 1 + B = 1, therefore

A(1 + B) = A 1 = A

To prove the second theorem, let's open the brackets:

A(A + B) = A A + AB = A + AB

The result is an expression that has just been proven.

Let us consider several examples of the application of the absorption theorem for

simplification of Boolean formulas.

Gluing theorem also has two forms - disjunctive and

conjunctive:

Let's prove the first theorem:

since according to Theorems (5) and (4)

To prove the second theorem, let’s open the brackets:

According to Theorem (6) it follows:

According to the absorption theorem (16) A+AB = A

The absorption theorem, like the gluing theorem, is used when simplifying

Boolean formulas, for example:

De Morgan's theorem connects all three basic operations of Boolean algebra

Disjunction, conjunction and inversion:

The first theorem reads like this: the inversion of a conjunction is a disjunction

inversions. Second: the inversion of a disjunction is a conjunction of inversions. Morgan's theorems can be proven using truth tables for the left and right sides.

De Morgan's theorem applies to more variables:

Lecture 5

Inverting complex expressions

De Morgan's theorem applies not only to individual conjunctions

or disjunctions, but also to more complex expressions.

Let's find the inversion of the expression AB + CD , presented as a disjunction of conjunctions. We will consider inversion complete if negative signs appear only above the variables. Let us introduce the following notation: AB = X;

CD = Y Then

Let us find and substitute into expression (22):

Thus:

Consider the expression presented in conjunctive form:

(A + B)(C + D)

Let us find its inversion in the form

Let us introduce the following notation: A + B = X; C + D =Y, Then

Let's find and substitute them into the expression

Thus:

When inverting complex expressions, you can use the following rule. To find the inversion, it is necessary to replace the conjunction signs with disjunction signs, and the disjunction signs with conjunction signs and put inversions over each variable:

The concept of a Boolean function

IN in general, function (lat. functio - execution, compliance,

mapping) is a certain rule (law), according to which each element of the set X, representing the range of values of the independent variable X, a specific element of the set is assigned F,

which refers to the range of values of the dependent variable f . In the case of Boolean functions X = F = (0,1). The rule by which a function is specified can be any Boolean formula, for example:

Symbol f here denotes a function that is, like the arguments of A, B, C, binary variable.

Arguments are independent variables, they can take any value - either 0 or 1. The function f - dependent variable. Its meaning is completely determined by the values of the variables and the logical connections between them.

The main feature of a function: in order to determine its value, in general it is necessary to know the values of all the arguments on which it depends. For example, the above function depends on three arguments A, V, S. If we take A = 1, we get

i.e., a new expression is obtained that is neither equal to zero nor

unit. Let it now IN= 1. Then

i.e., in this case, it is not known what the function is equal to, zero or one.

Let us finally accept WITH= 0. Then we get: f = 0. Thus, if in the original expression we take A = 1, IN= 1, WITH = 0, then the function will take the zero value: f = 0.

Let's consider concept of a set of variable values .

If all the arguments on which a function depends are assigned some values, then we speak of a set of argument values that can be

just call it a set. A set of argument values is a sequence of zeros and ones, for example 110, where the first digit corresponds to the first argument, the second to the second, and the third to the third. Obviously, it is necessary to agree in advance what the first, second or, say, fifth argument is. To do this, it is convenient to use the alphabetical arrangement of letters.

For example, if

then according to the Latin alphabet the first is the argument R, second -

Q, third - X, fourth - U. Then, based on the set of argument values, it is easy

find the value of the function. Let, for example, be given the set 1001. According to it

records i.e. on set 1001 the given function is equal to one.

Note again that the set of argument values is a collection

zeros and ones. Binary numbers are also sets of zeros and ones.

This raises the question: can sets not be considered binary?

numbers? It is possible, and in many cases it is very convenient, especially if the binary

Convert the number to the decimal system. For example, if

A = 0, B = 1, C = 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

i.e., the given set is number 6 in the decimal system.

If you need to find the values of the arguments using the decimal number, then

We proceed in the reverse order: first we convert the decimal number to binary, then we add as many zeros to the left so that the total number of digits equals the number of arguments, after which we find the values of the arguments.

Let, for example, you need to find the values of the arguments A, B, C, D, E, F by dialing with number 23. We convert the number 23 to the binary system using the method

dividing by two:

As a result, we get 23 10 = 10111 2. This number is five digits, but in total

There are six arguments, therefore, you need to write one zero on the left:

23 10 = 010111 2. From here we find:

A = 0, B = 1, C = 0, D = 1, E = 1, F = 1.

How many sets are there in total if the number is known? P arguments? Obviously, there are as many n-bit binary numbers as there are, i.e. 2 n

Lecture 6

Specifying a Boolean Function

We already know one way. It is analytical, that is, in the form of a mathematical expression using binary variables and logical operations. In addition to this, there are other methods, the most important of which is the tabular one. The table lists all possible sets of argument values and specifies the value of the function for each set. Such a table is called a correspondence (truth) table.

Using the function as an example

Let's find out how to build a correspondence table for it.

The function depends on three arguments A, B, C. Therefore, in the table

We provide three columns for arguments A, B, C and one column for the values of function f. To the left of Column A it is useful to place another column. In it we will write down decimal numbers that correspond to sets if they are considered as three-digit binary numbers. This decimal

the column is introduced for the convenience of working with the table, therefore, in principle,

it can be neglected.

Let's fill out the table. In the line with the LLC number it is written:

A = B = C = 0.

Let's determine the value of the function on this set:

In column f we write zero in the line with the dial 000.

Next set: 001, i.e. e. A = B = 0, C = 1. Find the value of the function

on this set:

On set 001 the function is 1, therefore in column f in row c

Number 001 is used to write one.

Similarly, we calculate the values of the functions on all other sets and

fill out the entire table.

De Morgan's laws are logical rules established by the Scottish mathematician Augustus de Morgan, connecting pairs of logical operations using logical negation.

Augustus de Morgan noted that in classical logic the following relations are valid:

not (A and B) = (not A) or (not B)

not (A or B) = (not A) and (not B)

In a more familiar form for us, these relationships can be written in the following form:

De Morgan's laws can be formulated as follows:

I de Morgan's law: The negation of the disjunction of two simple statements is equivalent to the conjunction of the negations of these statements.

II de Morgan's law: The negation of the conjunction of two simple statements is equivalent to the disjunction of the negations of these statements.

Let's consider the application of De Morgan's laws using specific examples.

Example 1. Transform the formula so that there are no negations of complex statements.

Let's use De Morgan's first law and get:

We apply De Morgan’s second law to the negation of the conjunction of simple statements B and C, and we obtain:

Thus:

As a result, we received an equivalent statement in which there are no negations of compound statements, and all negations relate only to simple statements.

You can check the validity of the solution using truth tables. To do this, we will compile truth tables for the original statement:

and for the statement obtained as a result of transformations performed using De Morgan's laws:

Table 1.

			B/\C	A\/B/\C

As we see from the tables, the original logical statement and the logical statement obtained using De Morgan's laws are equivalent. This is evidenced by the fact that in the truth tables we received the same sets of values.

Chapter 8 examined such types of objects of non-numerical nature as fuzzy and random sets. The purpose of this application is to study more deeply the properties of fuzzy sets and to show that the theory of fuzzy sets in a certain sense reduces to the theory of random sets. To achieve this goal, a chain of theorems is formulated and proven.

In what follows, it is assumed that all fuzzy sets under consideration are subsets of the same set Y.

P2-1. De Morgan's laws for fuzzy sets

As is known, the following identities of the algebra of sets are called Morgan’s laws

Theorem 1.For fuzzy sets the following identities hold:

(3)

The proof of Theorem 1 consists of directly checking the validity of relations (2) and (3) by calculating the values of the membership functions of the fuzzy sets involved in these relations based on the definitions given in Chapter 8.

Let us call identities (2) and (3) De Morgan's laws for fuzzy sets. Unlike the classical case of relations (1), they consist of four identities, one pair of which relates to the operations of union and intersection, and the second to the operations of product and sum. Like relation (1) in set algebra, de Morgan’s laws in fuzzy set algebra allow one to transform expressions and formulas that include negation operations.

P2-2. Distributive law for fuzzy sets

Some properties of set operations do not hold for fuzzy sets. Yes, except when A- a “crisp” set (i.e. the membership function takes only the values 0 and 1).

Is the distributive law true for fuzzy sets? The literature sometimes vaguely states that “not always.” Let's be completely clear.

Theorem 2.For any fuzzy sets A, B and C

At the same time equality

fair if and only if, for all

Proof. Fix an arbitrary element. To shorten the notation, we denote To prove identity (4), it is necessary to show that

Consider different orderings of three numbers a, b, c. Let first Then the left side of relation (6) is and the right side, i.e. equality (6) is true.

Let Then in relation (6) on the left is and on the right, i.e. relation (6) is again an equality.

If then in relation (6) on the left is and on the right, i.e. both parts match again.

Three remaining number orderings a, b, c there is no need to disassemble, since in relation (6) the numbers b And c enter symmetrically. Identity (4) is proven.

The second statement of Theorem 2 follows from the fact that, in accordance with the definitions of operations on fuzzy sets (see Chapter 8)

These two expressions coincide if and only if, when, what was required to be proved.

Definition 1.The carrier of a fuzzy set A is the set of all points , for which

Corollary of Theorem 2.If the carriers of the fuzzy sets B and C coincide with Y, then equality (5) holds if and only if A is a “crisp” (i.e., ordinary, classical, not fuzzy) set.

Proof. By condition in front of everyone. Then from Theorem 2 it follows that those. or , which means that A- clear set.

P2-3. Fuzzy sets as projections of random sets

From the very beginning of modern fuzzy theory in the 1960s, discussions began about its relationship with probability theory. The fact is that the membership function of a fuzzy set resembles a probability distribution. The only difference is that the sum of the probabilities over all possible values of a random variable (or the integral, if the set of possible values is uncountable) is always equal to 1, and the sum S values of the membership function (in the continuous case - the integral of the membership function) can be any non-negative number. There is a temptation to normalize the membership function, i.e. divide all its values by S(at S 0) to reduce it to a probability distribution (or probability density). However, fuzziness specialists rightly object to such a “primitive” reduction, since it is carried out separately for each fuzziness (fuzzy set), and the definitions of ordinary operations on fuzzy sets cannot be consistent with it. The last statement means the following. Let the membership functions of fuzzy sets be transformed in the indicated way sets A And IN. How are the membership functions transformed? Install this impossible in principle. The last statement becomes completely clear after considering several examples of pairs of fuzzy sets with the same sums of values of membership functions, but different results of set-theoretic operations on them, and the sums of values of the corresponding membership functions for these results of set-theoretic operations, for example, for intersections of sets are also different.

In works on fuzzy sets, it is quite often stated that the theory of fuzzyness is an independent branch of applied mathematics and is not related to probability theory (see, for example, a review of the literature in monographs). Authors who compared fuzzy theory and probability theory usually emphasized the difference between these areas of theoretical and applied research. Usually axiomatics are compared and application areas are compared. It should be immediately noted that the arguments for the second type of comparisons do not have evidentiary force, since there are different opinions regarding the limits of applicability of even such a long-established scientific field as probabilistic statistical methods. Let us recall that the result of the reasoning of one of the most famous French mathematicians, Henri Lebesgue, regarding the limits of applicability of arithmetic is as follows: “Arithmetic is applicable when it is applicable” (see his monograph).

When comparing various axiomatics of fuzzy theory and probability theory, it is easy to see that the lists of axioms differ. From this, however, it does not at all follow that a connection cannot be established between these theories, such as the well-known reduction of Euclidean geometry on the plane to arithmetic (more precisely, to the theory of the number system - see, for example, the monograph). Let us recall that these two axiomatics - Euclidean geometry and arithmetic - at first glance are very different.

One can understand the desire of enthusiasts of the new direction to emphasize the fundamental novelty of their scientific apparatus.

However, it is equally important to establish connections between the new approach and previously known ones.

As it turns out, the theory of fuzzy sets is closely related to the theory of random sets. Back in 1974, it was shown in the work that fuzzy sets can naturally be considered as “projections” of random sets. Let's consider this method of reducing the theory of fuzzy sets to the theory of random sets.Definition 2. - Let

(7)

a random subset of a finite set Y. A fuzzy set B defined on Y is called a projection A and is denoted Proj A if

Obviously, every random set A can be correlated using formula (7) with a fuzzy set B = Proj A. It turns out the opposite is also true.

Theorem 3. For any fuzzy subset B of a finite set Y, there is a random subset A of Y such that B = Proj A.

Proof. It is enough to set the distribution of the random set A. Let U 1- carrier IN(see definition 1 above). Without loss of generality we can assume that at some m and elements U 1 numbered in such an order that

Let us introduce sets

For all other subsets X sets U let's put P(A=X)=0. Since the element y t included in the set Y(1), Y(2),…, Y(t) and is not included in sets Y(t+1),…, Y(m), That From the above formulas it follows that

If then, obviously, Theorem 3 is proven.

The distribution of a random set with independent elements, as follows from the considerations in Chapter 8, is completely determined by its projection. For a finite random set of general form this is not the case. To clarify the above, we need the following theorem. Theorem 4. For a random subset A of a set Y from a finite numbers of elements sets of numbers And

Proof. are expressed one through the other.

The second set is expressed in terms of the first as follows:

The elements of the first set can be expressed through the second using the formula of inclusions and exclusions from formal logic, according to which In this formula in the first sum at runs through all elements of the set Y\X, in the second sum the summation variables And at 1 at 2

do not coincide and also run through this set, etc. A reference to the inclusion and exclusion formula completes the proof of Theorem 4. In accordance with Theorem 4, a random set A can be characterized not only by a distribution, but also by a set of numbers There are no other relations of the equality type in this set. This set includes numbers; therefore, fixing the projection of a random set is equivalent to fixing k = Card(Y) parameters from A(2k-1)

parameters specifying the distribution of a random set

in general.. The following theorem will be useful. Theorem 5, If

Proj A = B

That

Let us find out how operations on random sets relate to operations on their projections. By virtue of De Morgan's laws (Theorem 1) and Theorem 5, it is sufficient to consider the operation of intersection of random sets.

Theorem 6. If random subsets A 1 and A 2 of a finite set y are independent, then the fuzzy set is a work fuzzy sets Proj A 1 and Proj A 2 .

Proof. It must be shown that for any

According to the formula for the probability of covering a point with a random set (Chapter 8)

As is known, the distribution of the intersection of random sets can be expressed in terms of their joint distribution as follows:

From relations (9) and (10) it follows that the covering probability for the intersection of random sets can be represented as a double sum

Note now that the right-hand side of formula (11) can be rewritten as follows:

(12)

Indeed, formula (11) differs from formula (12) only in that it groups terms in which the intersection of the summation variables takes a constant value. Using the definition of independence of random sets and the rule for multiplying sums, we obtain that from (11) and (12) the equality follows

To complete the proof of Theorem 6, it is enough to once again refer to the formula for the probability of covering a point with a random set (Chapter 8).

Definition 3. The support of a random set C is the collection of all those elements for which

Theorem 7.Equality

true if and only if the intersection of the supports of the random sets numbers of elements sets of numbers empty.

Proof. It is necessary to find out the conditions under which

Then equality (13) reduces to the condition

It is clear that relation (14) is satisfied if and only if p 2 p 3=0 for all i.e. there is not a single element such that at the same time And , and this is equivalent to the emptiness of the intersection of the supports of random sets and . Theorem 7 is proven.

P2-5. Reduction of the sequence of operations on fuzzy sets

to a sequence of operations on random sets

Above we obtained some connections between fuzzy and random sets. It is worth noting that the study of these connections in the work (this work was carried out in 1974 and reported at the seminar “Multidimensional statistical analysis and probabilistic modeling of real processes” on December 18, 1974 - see) began with the introduction of random sets for the purpose of development and generalization apparatus of fuzzy sets L. Zadeh. The fact is that the mathematical apparatus of fuzzy sets does not allow one to adequately take into account various options for the dependence between concepts (objects) modeled with its help; it is not flexible enough. Thus, to describe the “common part” of two fuzzy sets there are only two operations - product and intersection. If the first of them is applied, then it is actually assumed that the sets behave as projections of independent random sets (see Theorem 6 above). The operation of intersection also imposes well-defined restrictions on the type of dependence between sets (see Theorem 7 above), and in this case even necessary and sufficient conditions have been found. It is desirable to have broader capabilities for modeling dependencies between sets (concepts, objects). The use of the mathematical apparatus of random sets provides such opportunities.

The purpose of reducing fuzzy sets to random ones is to see behind any construction of fuzzy sets a construction of random sets that determines the properties of the first, in the same way as we see a random variable with a probability distribution density. In this section we present results on reducing the algebra of fuzzy sets to the algebra of random sets.

Definition 4.Probability space { W, G, P)we call it divisible if for any measurable set X G and any positive number, smaller than P(X), we can specify a measurable set such that

Example. Let be the unit cube of a finite-dimensional linear space, G is the sigma algebra of Borel sets, and P- Lebesgue measure. Then { W, G, P)- divisible probability space.

Thus, divisible probability space is not exotic. An ordinary cube is an example of such a space.

The proof of the statement formulated in the example is carried out using standard mathematical techniques, based on the fact that a measurable set can be approximated as accurately as desired by open sets, the latter being represented as a sum of no more than a countable number of open balls, and for balls the divisibility is checked directly (from a ball X a body of volume separated by a corresponding plane).

Theorem 8.Let a random set A be given on a divisible probability space (W, G, P) with values in the set of all subsets of the set Y from a finite number of elements, and a fuzzy set D on Y. Then there are random sets C 1, C 2, C 3, C 4 on the same probability space such that

where B = Proj A.

Proof. Due to the validity of De Morgan's laws for fuzzy (see Theorem 1 above) and for random sets, as well as Theorem 5 above (on negations), it is sufficient to prove the existence of random sets C 1 And C 2 .

Consider the probability distribution in the set of all subsets of the set U, corresponding to the random set WITH such that Proj C = D(it exists by virtue of Theorem 3). Let's build a random set C 2 We exclude the element only for of the same set Y such that

and, in addition, the results of set-theoretic operations are related by similar relations

where the sign means that at the place in question there is a symbol of the intersection of random sets, if in the definition of B m there is an intersection symbol or a symbol of the product of fuzzy sets, and, accordingly, a symbol of the union of random sets, if in B m there is a union symbol or a symbol of the sum of fuzzy sets.

Formulas and laws of logic

During the introductory lesson on basics of mathematical logic, we became acquainted with the basic concepts of this branch of mathematics, and now the topic is receiving a natural continuation. In addition to new theoretical, or rather not even theoretical - but general educational material, practical tasks await us, and therefore if you came to this page from a search engine and/or are poorly versed in the material, then please follow the above link and start from the previous article. In addition, for practice we will need 5 truth tables logical operations which I highly recommend rewrite by hand.

DO NOT remember, DO NOT print it out, but rather comprehend it again and copy it onto paper with your own hand - so that they are before your eyes:

– table NOT;
– table I;
– OR table;
– implication table;
– table of equivalence.

It is very important. In principle, it would be convenient to number them "Table 1", "Table 2", etc., but I have repeatedly emphasized the flaw of this approach - as they say, in one source the table will be first, and in another - one hundred and first. Therefore, we will use “natural” names. Let's continue:

In fact, you are already familiar with the concept of a logical formula. I’ll give you a standard, but quite witty definition: formulas propositional algebras are called:

1) any elementary (simple) statements;

2) if and are formulas, then formulas are also expressions of the form
.

There are no other formulas.

In particular, a formula is any logical operation, such as logical multiplication. Pay attention to the second point - it allows recursive way to “create” an arbitrarily long formula. Because the - formulas, then - also a formula; since and are formulas, then – also a formula, etc. Any elementary statement (again according to definition) can be included in the formula more than once.

Formula Not is, for example, a notation - and here there is an obvious analogy with “algebraic garbage”, from which it is not clear whether numbers need to be added or multiplied.

The logical formula can be thought of as logical function. Let us write the same conjunction in functional form:

Elementary statements in this case also play the role of arguments (independent variables), which in classical logic can take on 2 meanings: true or lie. Below, for convenience, I will sometimes call simple statements variables.

A table describing a logical formula (function) is called, as already stated, truth table. Please – a familiar picture:

The principle of forming a truth table is as follows: “at the input” you need to list all possible combinations truths and lies, which can take elementary statements (arguments). In this case, the formula includes two statements, and it is easy to find out that there are four such combinations. “At the output” we get the corresponding logical values of the entire formula (function).

It must be said that the “exit” here turned out to be “in one step,” but in the general case the logical formula is more complex. And in such “difficult cases” you need to comply order of execution of logical operations:

– negation is performed first;
– secondly – conjunction;
– then – disjunction;
– then implication;
– and finally, equivalence has the lowest priority.

So, for example, the entry implies that you first need to perform logical multiplication, and then logical addition: . Just like in “ordinary” algebra – “first we multiply, and then we add.”

The order of actions can be changed in the usual way - with brackets:
– here, first of all, the disjunction is performed and only then a “stronger” operation.

Probably everyone understands, but just in case, fireman: and this two different formulas! (both formally and substantively)

Let's create a truth table for the formula. This formula includes two elementary statements and “at the input” we need to list all possible combinations of ones and zeros. To avoid confusion and discrepancies, we will agree to list the combinations strictly in that order (which I actually de facto use from the very beginning):

The formula includes two logical operations, and according to their priority, first of all you need to perform negation statements. Well, let’s deny the “pe” column – we turn ones into zeros, and zeros into ones:

In the second step, we look at the columns and apply to them OR operation. Looking ahead a little, I will say that the disjunction is commutative (and are the same thing), and therefore the columns can be analyzed in the usual order - from left to right. When performing logical addition, it is convenient to use the following applied reasoning: “If there are two zeros, we put a zero, if there is at least one one, we put a one.”:

The truth table has been constructed. Now let’s remember the good old implication:

...carefully, carefully... looking at the total columns.... In propositional algebra such formulas are called equivalent or identical:

(three horizontal lines are an identity icon)

In the 1st part of the lesson, I promised to express the implication through basic logical operations, and the fulfillment of the promise was not long in coming! Those who wish can put meaningful meaning into the implication (for example, “If it’s raining, it’s damp outside”) and independently analyze the equivalent statement.

Let's formulate general definition: the two formulas are called equivalent (identical), if they take the same values for any set of values included in these variable formulas (elementary statements). It is also said that “formulas are equivalent if their truth tables coincide”, but I don't really like this phrase.

Exercise 1

Create a truth table for the formula and make sure that the identity you are familiar with is correct.

Let us repeat the order of solving the problem once again:

1) Since the formula includes two variables, there will be a total of 4 possible sets of zeros and ones. We write them down in the order specified above.

2) Implications are “weaker” than conjunctions, but they are placed in parentheses. We fill out the column, and it is convenient to use the following applied reasoning: “if a zero follows from one, then we put zero, in all other cases - one”. Next, fill in the column for implication, and at the same time, attention!– columns should be analyzed “from right to left”!

3) And at the final stage, fill in the final column. And here it is convenient to think like this: “if there are two units in the columns, then we put one, in all other cases – zero”.

And finally, we check the truth table equivalence .

Basic equivalences of propositional algebra

We have just met two of them, but the matter, of course, is not limited to them. There are quite a few identities and I will list the most important and most famous of them:

Commutativity of conjunction and commutativity of disjunction

Commutativity- this is commutability:

Rules familiar from 1st grade: “The product (sum) does not change by rearranging the factors (addends)”. But despite all the seeming elementaryness of this property, it is not always true; in particular, it is non-commutative matrix multiplication (in general, they cannot be rearranged), A vector product of vectors– anticommutative (rearrangement of vectors entails a change of sign).

And, besides, here I again want to emphasize the formalism of mathematical logic. So, for example, the phrases “The student passed the exam and drank” And “The student drank and passed the exam” different from a content point of view, but indistinguishable from the standpoint of formal truth. ...Each of us knows such students, and for ethical reasons we will not voice specific names =)

Associativity of logical multiplication and addition

Or, if “in school style” – a coordinating property:

Distributive properties

Please note that in the 2nd case it will be incorrect to talk about “opening the parentheses”; in a certain sense, this is a “fiction” - after all, they can be removed altogether: , because multiplication is a stronger operation.

And again, these seemingly “banal” properties are not fulfilled in all algebraic systems, and, moreover, require proof (which we will talk about very soon). By the way, the second distributive law is not valid even in our “ordinary” algebra. And in fact:

Law of Idempotency

What to do, Latin...

Just some principle of a healthy psyche: “I and I are me”, “I or I are also me” =)

And here are several similar identities:

...hmm, I’m kind of stuck... so I might wake up with a PhD tomorrow =)

Law of double negation

Well, here an example with the Russian language suggests itself - everyone knows perfectly well that two particles “not” mean “yes”. And in order to enhance the emotional connotation of denial, three “nots” are often used:
– even with a tiny piece of evidence it worked!

Laws of absorption

- “Was there a boy?” =)

In the right identity, the parentheses can be omitted.

De Morgan's laws

Let's assume that the strict teacher (whose name you also know :)) gives an exam if - The student answered the 1st question numbers of elements sets of numbers – The student answered the 2nd question. Then a statement saying that Student Not passed the exam, will be equivalent to the statement – Student Not answered the 1st question or to the 2nd question.

As noted above, equivalences are subject to proof, which is usually carried out using truth tables. In fact, we have already proved the equivalences expressing implication and equivalence, and now it is time to consolidate the technique for solving this problem.

Let's prove the identity. Since it includes a single statement, there are only two possible options at the input: one or zero. Next, we assign a single column and apply to them rule I:

As a result, the output is a formula, the truth of which coincides with the truth of the statement. Equivalence has been proven.

Yes, this proof is primitive (and some will say “stupid”), but a typical mathematics teacher will shake his soul for him. Therefore, even such simple things should not be treated with disdain.

Now let us verify, for example, the validity of de Morgan's law.

First, let's create a truth table for the left side. Since the disjunction is in parentheses, we perform it first, after which we negate the column:

Next, let's create a truth table for the right side. Here, too, everything is transparent - first of all, we carry out “stronger” negations, then apply them to the columns rule I:

The results coincided, thus the identity was proven.

Any equivalence can be represented in the form identical to the true formula. It means that FOR ANY initial set of zeros and ones The “output” is strictly one. And there is a very simple explanation for this: since the truth tables coincide, then, of course, they are equivalent. Let us, for example, connect the left and right sides of the just proven de Morgan identity by equivalence:

Or, more compactly:

Task 2

Prove the following equivalences:

A short solution at the end of the lesson. Let's not be lazy! Try not only to create truth tables, but also clearly formulate conclusions. As I recently noted, neglecting simple things can be very, very expensive!

Let's continue to get acquainted with the laws of logic!

Yes, that’s absolutely right – we are already working hard with them:

True at , called identical to the true formula or law of logic.

Due to the previously justified transition from equivalence to an identically true formula, all of the identities listed above represent laws of logic.

Formula that takes value Lie at any set of values of the variables included in it, called identically false formula or contradiction.

A signature example of a contradiction from the ancient Greeks:
- no statement can be true and false at the same time.

The proof is trivial:

The “output” contains only zeros, therefore the formula is really identical false.

However, any contradiction is also a law of logic, in particular:

It is impossible to cover such a vast topic in one single article, and therefore I will limit myself to just a few more laws:

Law of the excluded middle

– in classical logic, any statement is true or false and there is no third option. “To be or not to be” – that is the question.

Make a truth sign yourself and make sure that it is identically true formula.

Law of contraposition

This law was actively discussed when we discussed the essence necessary condition, we remember: “If it’s damp outside when it’s raining, then it follows that if it’s dry outside, then it definitely hasn’t rained.”.

It also follows from this law that if fair is straight theorem, then the statement, which is sometimes called opposite theorem.

If true reverse theorem, then by virtue of the law of contraposition, the theorem is also valid, the opposite of the reverse:

And again let's return to our meaningful examples: for statements – the number is divisible by 4, – the number is divisible by 2 fair straight And opposite theorems, but false reverse And the opposite of the reverse theorems. For the “adult” formulation of the Pythagorean theorem, all 4 “directions” are true.

Law of syllogism

Also a classic of the genre: “All oaks are trees, all trees are plants, therefore all oaks are plants.”.

Well, here again I would like to note the formalism of mathematical logic: if our strict Teacher thinks that a certain Student is an oak tree, then from a formal point of view this Student is certainly a plant =) ... although, if you think about it, then maybe from an informal point of view too = )

Let's create a truth table for the formula. In accordance with the priority of logical operations, we adhere to the following algorithm:

1) we carry out the implications and . Generally speaking, you can immediately perform the 3rd implication, but it is more convenient (and acceptable!) figure it out a little later;

2) apply to columns rule I;

3) now we execute;

4) and at the final step we apply the implication to the columns And .

Feel free to control the process with your index and middle fingers :))

From the last column, I think everything is clear without comment:
, which was what needed to be proven.

Task 3

Find out whether the following formula is a law of logic:

A short solution at the end of the lesson. Oh, and I almost forgot - let's agree to list the original sets of zeros and ones in exactly the same order as when proving the law of syllogism. Of course, the lines can be rearranged, but this will make it very difficult to compare with my solution.

Converting logical formulas

In addition to their “logical” purpose, equivalences are widely used to transform and simplify formulas. Roughly speaking, one part of the identity can be exchanged for another. So, for example, if in a logical formula you come across a fragment, then according to the law of idempotency, instead of it you can (and should) write simply . If you see, then according to the law of absorption, simplify the notation to. And so on.

In addition, there is one more important thing: the identities are valid not only for elementary statements, but also for arbitrary formulas. For example:

, where – any (as complex as you like) formulas.

Let us transform, for example, the complex implication (1st identity):

Next, we apply the “complex” de Morgan’s law to the bracket, and, due to the priority of operations, it is the law where :

The parentheses can be removed, because inside there is a “stronger” conjunction:

Well, with commutativity in general everything is simple - you don’t even need to designate anything... something about the law of syllogism has sunk into my soul :))

Thus, the law can be rewritten in a more intricate form:

Say out loud the logical chain “with an oak, a tree, a plant,” and you will understand that the substantive meaning of the law has not changed at all by rearranging the implications. Except that the wording has become more original.

As a workout, let's simplify the formula.

Where to begin? First of all, understand the order of actions: here the negation is applied to an entire parenthesis, which is “fastened” to the statement by a “slightly weaker” conjunction. Essentially, we have before us the logical product of two factors: . Of the two remaining operations, implication has the lowest priority, and therefore the entire formula has the following structure: .

Typically, the first step(s) is to get rid of equivalence and implication (if they are) and reduce the formula to three basic logical operations. What can I say... Logical.

(1) We use the identity . And in our case.

This is usually followed by “showdowns” with brackets. First the whole solution, then the comments. To avoid “butter and butter”, I will use “regular” equality symbols: