Formulas and laws of logic

In an introductory lesson on the basics of mathematical logic, we got acquainted with the basic concepts of this section of mathematics, and now the topic is being naturally continued. In addition to new theoretical, or rather not even theoretical, but general educational material, practical tasks await us, and therefore if you entered this page from a search engine and / or are poorly guided in the material, then please follow the above link and start with the previous article. In addition, for practice we need 5 truth tables logical operations which i highly recommend rewrite by hand.

DO NOT remember, DO NOT print, namely, to comprehend again and rewrite on paper with your own hand - so that they are before your eyes:

- the table is NOT;
- table I;
- OR table;
- implication table;
- equivalence table.

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 the first, and in the other - the one hundred and first. Therefore, we will use "natural" names. We continue:

In fact, you are already familiar with the concept of a logical formula. I'll give you a standard, but rather witty definition: formulas algebras of statements 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. Insofar as - formulas, then - also a formula; since and are formulas, then - also a formula, etc. Any elementary statement (again as defined) may appear in the formula more than once.

Formula not there is, for example, a record - and here there is an obvious analogy with "algebraic rubbish", from which it is not clear whether numbers should be added or multiplied.

The logical formula can be viewed as logical function... Let's write down the same conjunction in functional form:

In this case, elementary statements also play the role of arguments (independent variables), which in classical logic can take 2 values: true or Lying... In what follows, for convenience, I will sometimes refer to simple statements variables.

The table describing the logical formula (function) is called, as already announced, truth table... Please - familiar picture:

The principle of forming the truth table is as follows: "at the input" you need to list all possible combinations truths and lies that 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).

I must say that the "exit" here turned out "in one step", but in the general case the logical formula is more complicated. And in such "difficult cases" you need to observe order of execution of logical operations:

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

So, for example, the notation implies that first you 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 for every fireman: and this two different formulas! (both formally and substantively)

Let's compose 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 misunderstandings, we agree to list combinations strictly in that order (which I actually use de facto 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, we deny the "pe" column - we turn the ones into zeros, and the zeros into ones:

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

The truth table is built. Now let's remember the good old implication:

… Attentively, attentively… we look at the final columns…. In propositional algebra such formulas are called tantamount to or identical:

(the three horizontal bars are the identity icon)

In the first 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 interested can put a 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 formulas of variables (elementary statements)... It is also said that "Formulas are equivalent if their truth tables match" but I don't really like this phrase.

Exercise 1

Draw up a truth table for the formula and make sure that the identity you know is true.

Let's repeat the order of solving the problem once again:

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

2) Implications are "weaker" than conjunction, but they are located in parentheses. We fill in the column, while it is convenient to use the following applied reasoning: "If zero follows from one, then we put zero, in all other cases - one"... Next, we fill in the column for the implication, and at the same time, Attention!- columns and should be analyzed "from right to left"!

3) And at the final stage, fill in the final column. And here it is convenient to reason like this: "If there are two units in the columns, then we put one, in all other cases - zero".

Finally, we check the truth table equivalents .

Basic equivalences of propositional algebra

We have just met two of them, but, of course, the matter 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 a conjunction and commutativity of a disjunction

Commutativity Is permutability:

Rules familiar from the 1st grade: "The product (sum) does not change from the permutation of the factors (terms)"... But for all the seeming elementarity 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 (permutation of vectors entails a sign change).

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 the substantive point of view, but indistinguishable from the point of view 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 a school way" - a combination property:

Distributive properties

Please note that in the second case it will be incorrect to talk about "opening brackets", in a certain sense here is "fiction" - after all, they can be removed altogether: since 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 "usual" algebra. And in fact:

The law of idempotency

What to do, Latin ...

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

And then there are several similar identities:

... hmm, something I even got hung up on ... so you can wake up with a doctor of philosophy tomorrow =)

The law of double negation

Well, here an example with the Russian language already suggests itself - everyone knows perfectly well that two particles "do not" mean "yes". And in order to enhance the emotional coloring of denial, three "not" are often used:
- even with a tiny proof it worked!

Absorption laws

- "Was there a boy?" =)

In the right identity, the parentheses can be omitted.

De Morgan's laws

Suppose the strict Teacher (whose name you also know :)) puts an exam if - Student answered 1st question and – The student answered the 2nd question... Then the statement stating that Student not passed the exam, will be equivalent to the statement - Student not answered the 1st question or on the 2nd question.

As noted above, equivalences are subject to proof, which is carried out in a standard way 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 us prove the identity. Since it contains a single statement, only two options are possible "at the input": one or zero. Next, we assign a single column and apply to them rule AND:

As a result, "at the exit" a formula is obtained, the truth of which coincides with the truth of the statement. Equivalence has been proven.

Yes, this proof is primitive (and someone will say that "stupid"), but a typical teacher of matology will shake his heart out for him. Therefore, even such simple things should not be taken lightly.

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

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

Next, let's make a truth table for the right side. Here, too, everything is transparent - first of all we carry out more "strong" negations, then we apply to the columns rule AND:

The results coincide, so the identity is proved.

Any equivalence can be represented as identically to the true formula... It means that FOR ANY original set of zeros and ones"At the exit" is strictly one. And there is a very simple explanation for this: since the truth tables and coincide, then, of course, they are equivalent. Let us combine, for example, by an equivalent the left and right sides of the just proved de Morgan's identity:

Or, if more compact:

Assignment 2

Prove the following equivalences:

b)

A short solution at the end of the tutorial. We are not lazy! Try not only to compile truth tables, but also clearly formulate conclusions. As I noted recently, neglecting simple things can get very, very expensive!

We continue to get acquainted with the laws of logic!

Yes, that's right - we are already working with them with might and main:

True at is called identically to the true formula or the law of logic.

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

The formula that takes on the value Lie at any set of values ​​of the variables included in it is called identically false formula or contradiction.

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

The proof is trivial:

"At the exit", only zeros are received, therefore, the formula is valid identical false.

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

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

The law of the excluded third

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

Draw up a truth plate on your own and make sure that it is identically true formula.

The law of contraposition

This law was actively discussed when we discussed the essence of necessary condition, remember: “If it’s damp during the rain, then it follows that if it’s dry outside, then it certainly didn’t rain.”.

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, opposite reverse:

And again, back to our informative examples: for statements - number is divisible by 4, - number is divisible by 2 fair straight and opposite theorems but false reverse and opposite reverse theorems. For the "adult" formulation of the Pythagorean theorem, all 4 "directions" are true.

Syllogism law

Also classics 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 definitely a plant =) ... although, if you think about it, then maybe with an informal one, too = )

Let's compose 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 execute the 3rd implication, but it is more convenient with it (and permissible!) figure it out a little later;

2) apply to columns rule AND;

3) now we are doing;

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 comments:
, as required to prove.

Assignment 3

Find out whether the following formula will be a law of logic:

A short solution at the end of the tutorial. Yes, and I almost forgot - let's agree to list the initial sets of zeros and ones in exactly the same order as in the proof of the law of the syllogism. Of course, the lines can be rearranged, but this will greatly complicate the comparison with my solution.

Converting Boolean 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 you come across a fragment in a logical formula, then, according to the law of idempotency, you can (and should) write it simply instead of it. If you see, then by the law of absorption, simplify the entry to. Etc.

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

, where are any (however difficult) formulas.

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

Next, we apply the "complex" de Morgan's law to the bracket, while, due to the priority of operations, it is the law where :

The brackets can be removed as inside there is a "stronger" conjunction:

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

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

Speak out loud the logical chain "with an oak, tree, plant", and you will understand that the meaning of the law has not changed at all from the rearrangement of the implications. Perhaps the wording has become more original.

As a training, let's simplify the formula.

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

As a rule, in the first step (s) one gets rid of the equivalence and implication (if they are) and reduce the formula to three main logical operations. What can you say…. It is logical.

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

This is usually followed by "disassembly" with brackets. First the whole solution, then the comments. In order not to get "butter oil", I will use the icons of "ordinary" equality:

(2) We apply de Morgan's law to the outer brackets, where.

Absorption theorem is written in two forms - disjunctive and

conjunctive, respectively:

A + AB = A (16)

A (A + B) = A (17)

Let us prove the first theorem. Let's take out the letter A outside the 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, we expand the brackets:

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

This is the expression just 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 us prove the first theorem:

since according to theorems (5) and (4)

To prove the second theorem, we expand the brackets:

According to theorem (6), therefore:

By the absorption theorem (16) A + AB = A

The absorption theorem, like the gluing theorem, is applied to simplify

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 inverse of a conjunction is a disjunction

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

De Morgan's theorem is applicable to more variables:

Lecture 5

Inverting complex expressions

De Morgan's theorem is applicable not only to individual conjunctions

or disjunctions, but also to more complex expressions.

Find the inverse of the expression AB + CD , presented as a disjunction of conjunctions. The inversion will be considered complete if the negation signs are only above the variables. Let us introduce the notation: AB = X;

CD = Y, then

Find and substitute in expression (22):

Thus:

Consider an expression in conjunctive form:

(A + B) (C + D)

Let us find its inversion in the form

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

Find and substitute them in 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 the disjunction signs, and the disjunction signs - by the conjunction signs and put inversions over each variable:

Boolean function concept

V in the general case, a function (lat.functio - execution, compliance,

mapping) is some rule (law) according to which each element of the set X, which is the range of values ​​of the independent variable NS, a certain element of the set is associated F,

which is understood as the range of values ​​of the dependent variable f ... In the case of boolean functions X = F = (0,1). Any Boolean formula can be used as a rule for defining a function, for example:

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

Arguments are independent variables; they can take any values ​​- 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 the general case, you need to know the values ​​of all the arguments on which it depends. For example, the above function depends on three arguments A, B, C. If we take A = 1, then we get

that is, a new expression has turned out that is not equal to zero or

unit. Let now V= 1. Then

that is, in this case it is not known whether the function is equal to zero or one.

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

Consider variable value set concept .

If some values ​​are assigned to all the arguments on which the function depends, then one speaks of a set of argument values ​​that can be

just call it a set. The 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, the fifth argument is. For 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, the fourth - U. Then, by the set of values ​​of the arguments, it is easy

find the value of the function. For example, let the set 1001 be given. According to its

records, that is, on the set 1001 the given function is equal to one.

Note again that a set of argument values ​​is a collection

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

This raises the question - can the sets be considered as binary

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

convert number to 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

that is, the given set is numbered 6 in decimal.

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

we act in the reverse order: first, we convert the decimal number to binary, then add so 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, it is required to find the values ​​of the arguments A, B, C, D, E, F by the set with number 23. We translate the number 23 into the binary system using the method

division by two:

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

there are six arguments, therefore, one zero must be written 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 there are, if the number is known NS arguments? Obviously, as many as there are n-bit binary numbers, i.e. 2 n

Lecture 6

Boolean function

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

Using the function as an example

let's figure out how to build a lookup table for it.

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

we provide three columns for the arguments A, B, C and one column for the values ​​of the function f. It is useful to place another column to the left of column A. In it we will write decimal numbers that correspond to sets if we consider them 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.

We fill in the table. The line with the LLC number contains:

A = B = C = 0.

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

In column f, write zero in the line with the set 000.

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

on this set:

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

number 001, write one.

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

fill in the entire table.

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 a conjunction with respect to disjunction x 1 (x 2 Ú x 3) = x 1 x 2 Ú x 1 x 3. Distributivity of a disjunction with respect to a conjunction x 1 Ú (x 2 × x 3) = (x 1 Úx 2) × (x 1 Úx 3). * Idempotency (tautology) Twice no Constant properties x & 1 = x; (laws of the universal set) x & 0 = 0; (zero set laws) De Morgan's rules (laws) Contradiction (complementarity) law Third (complementarity) exclusion law The proofs of all these formulas are trivial. One option is to build truth tables for the left and right sides and compare them. Bonding rules The gluing rule for elementary conjunctions follows from the distribution law, the law of complementarity, and the law of the universal set: a disjunction of two adjacent conjunctions can be replaced by a single 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 neighboring clauses can be replaced by one elementary clause, which is the common part of the original clauses . Absorption 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: a disjunction of two elementary conjunctions, of which one is an integral part of the other, can be replaced by a conjunction with 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 an integral part of the other, can be replaced by an elementary disjunction with a smaller number of operands. Deployment rule This rule defines the reverse action of gluing. The rule for expanding an elementary product into a logical sum of elementary products of a higher rank (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 performed in three stages: In the expandable elementary product of rank r, it is introduced as factors of n-r units, where n is the rank of the constituent of one; Each unit is replaced by the logical sum of some variable that is not present in the original elementary product and its negation: x i v `x i = 1; All brackets are opened on the basis of the distribution law of the first kind, which leads to the expansion of the initial elementary product of rank r into a logical sum of 2 n-r constituents of the unit. The rule of unfolding the elementary product is used to minimize the functions of Boolean Algebra (FAL). The rule of expanding an elementary sum of rank r to the product of elementary sums of rank n (constituents of zero) follows their laws of the zero set (6) and the distribution law of the second kind (14) and is performed in three stages: In the expandable 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 initial 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 initial sum of rank r unfolds 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 Boolean functions A is called a complete system (in P2) if any Boolean function can be expressed by a formula over A. System of functions A = ( f 1, f 1, ..., f m) that 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 the function of the algebra of logic f is different from the identical 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 is proved. 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. Consider an arbitrary Boolean function f (x 1,…, x n) and two systems of functions: A = (g 1, g 2,…) and B = (h 1, h 2,…). Since 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. Going through all the functions of the Boolean algebra in this way, we obtain that the system B is also complete. The lemma is proved. Theorem. The following systems are complete in P 2: 4) (&, ⊕, 1) a Zhegalkin basis. Proof. 1) It is known (Theorem 3) that the system A = (&, V,) is complete. Let us show that the system B = (V, is complete. Indeed, from the de Morgan law (x & y) = (x ∨ y) we obtain that x & y = (x ∨ y), that is, 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) Similarly to item 1: (x ∨ y) = x & y ⇔ x ∨ y = (x & y) and Lemma 2 implies the truth of item 2. 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 is proved. 17. Zhegalkin's algebra. Operation properties and completeness The set of Boolean functions defined in the Zhegalkin basis S4 = (⊕, &, 1) is called Zhegalkin algebra. Basic properties. 1. commutability h1⊕h2 = h2⊕h1 h1 & h2 = h2 & h1 2. associativity h1⊕ (h2⊕h3) = (h1⊕h2) ⊕h3 h1 & (h2 & h3) = (h1 & h2) & h3 3. distributiveness 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 the Zhegalkin algebra: x → y = 1⊕x⊕xy x ↓ y = 1⊕x⊕y⊕xy 18. Polynom Zhegalkina. Construction methods. Example. The Zhegalkin polynomial (a polynomial modulo 2) in 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 separate variables, then it is called linear (linear function). For example, f = x⊕yz⊕xyz and f 1 = 1⊕x⊕y⊕z are polynomials, and the second is a linear function. Theorem... Each Boolean function is uniquely represented as a Zhegalkin polynomial. Here are the main methods for constructing Zhegalkin polynomials in a given function. 1. The method of undefined coefficients. Let P (x 1, x 2 ... x n) be the required Zhegalkin polynomial realizing a 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 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 get 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 (, &) realizing the given function f (X 1, X 2 ... X n). Then, everywhere substitute subformulas of the form A by A⊕1, expand 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 undefined coefficients). Let's 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 Whence we successively find, C 0 = 1, C 1 = 1, C 2 = 0, C 12 = 1 Therefore: x → y = 1⊕X⊕XY. 2. (Method of transformation of formulas.). We have: x → y = xvy = (xy) = (x (y⊕1)) ⊕1 = 1⊕x⊕xy Note that the advantage of the Zhegalkin algebra (in comparison with other algebras) lies in the arithmeticization of logic, which makes it possible to perform transformations of Boolean functions quite simply. Its disadvantage in comparison with Boolean algebra is the cumbersomeness of the formulas. Similar information. The considered operations on sets are subject to certain laws that resemble the well-known elementary laws of the algebra of numbers. This defines the name set algebra, which is often called Boolean algebra of sets, which is associated with the name of the English mathematician John Boole, who based his logical studies on the idea of ​​an analogy between algebra and logic. For arbitrary sets A, B, and C, the following identities are valid (Table 3.1): Table 3.1 1. The law of identity 2. Commutativity of a union 2 '. Intersection commutativity 3. Association associativity 3 '. Intersection associativity 4. Distributivity of a union with respect to intersection 4'. Distributiveness of intersection relative to union 5. Laws of action with empty and universal U sets (law of the excluded third) 5'. Laws of action with empty and universal U sets (law of contradiction) 6. The law of idempotency of association 6 '. The law of idempotency of intersection 7. De Morgan's law 7 '. De morgan's law 8. The law of elimination (absorption) eight'. Elimination (absorption) law 9. The law of bonding nine'. Bonding law 10. Poretsky's law ten'. Poretsky's law 11. Law of involution (double's complement) The laws of the algebra of sets with respect to the operations of intersection () and union () are subject to the duality principle: if in any law all intersection signs are replaced by union signs, and all union signs by intersection signs, the universe sign (U) is replaced by the empty set sign (Ø), and the empty sign is the sign of the universe, then we again obtain the correct identity. For example (by virtue of this principle), it follows from, etc. 3.1. Testing the Truth of Identities Using Euler-Venn Diagrams All laws of set algebra can be visualized and proved using Euler-Venn diagrams. This requires: Draw the corresponding diagram and shade all the sets on the left-hand side of the equality. Draw another diagram and do the same for the right side of the equation. This identity is true if and only if the same area is shaded on both diagrams. Remark 3.1. Two intersecting circles divide the entire universal set into four areas (see Figure 3.1) Remark 3.2. Three intersecting circles divide the entire universal set into eight regions (see Figure 3.2): Remark 3.2. When recording the conditions of various examples, the notation is often used:  - from ... follows ...;  - if and only if…. Task 3.1 ... Simplify set algebra expressions: Solution. Task 3 .2 ... Prove identities: (AB) \ B = A \ B; A (BC) = A \ (A \ B)  (A \ C). Solution. Task 3.3 ... Prove the following relations in two ways: using diagrams and using the definition of equality of sets. Solution. 2. Proof using the definition of equality of sets. By definition, the sets X and Y are equal if the following relations hold simultaneously: XY and YX. Let us first show that ... Let be NS- an arbitrary element of the set , that is NS ... It means that NSU and NS ... Hence it follows that NSA or NSV. If NSA, then NSĀ, which means ... If NSВ, then , which means ... Thus, every element of the set. ... is also an element of the set That is Now let us prove the opposite, that is, that ... Let be ... If NSĀ, then NSU and NSA, which means NSАВ. Hence it follows that ... If , then NSU and NSV. Means, NSАВ, that is ... Hence it follows that every element of the set is also an element of the set , that is . Means, , as required to prove. A (BC) = (AB)  (AC); 1. Proof by diagram: Let be NSА (ВС). Then NSA and NSВС. If NSВ, then NSАВ, which does not contradict what was said, which means that NS (АВ)  (АС). If NSС, then NSАС. Hence, NS (AB)  (AC). So, we have proved that A (BC)  (AB)  (AC. Let now NS (AB)  (AC). If NSАВ, then NSA and NSV. Hence it follows that NSA and NSВС, that is NSА (ВС). If NSАС, then NSA and NSC. Hence it follows that NSA and NSВС, that is NSА (ВС). Thus, (AB)  (AC)  A (BC). Therefore, A (BC) = (AB)  (AC). Q.E.D. In proving the sufficiency, we obtained that AB = . Obviously, C, so the relation is proved. In the proof, the most general case was considered. However, some more options are possible here when constructing diagrams. For example, the case of equality АВ = С or , the case of empty sets, and so on. Obviously, it can be difficult to take into account all the possible options. Therefore, it is believed that the proof of relations using diagrams is not always correct. 2. Proof using the definition of equality of sets. Need. Let АВС and the element NSA. Let us show that in this case an element of the set A will also be an element of the set . Consider two cases: NSB or . If NSВ, then NSАВС, that is NSС, and, as a consequence of this, . If , then ... The necessity has been proven. Let now and NSАВ. Let us show that the element NS will also be an element of the set C. If NSАВ, then NSA and NSV. Insofar as , means NSC. The sufficiency has been proven. 1. Proof by diagram: 2. Proof using the definition of equality of sets. Let AB. Consider the element NSВ (or ). Likewise: NSА (or NSĀ). That is, any element of the set is also an element of the set Ā. And this may be the case if ... Q.E.D. Task 3.4. Express the indicated areas symbolically and simplify the resulting expressions. Solution. The search area consists of two isolated parts. Let's call them the top and bottom. The multitude that they represent can be described as follows: M = ( x xA and NSB and NSC or NSC and NSA and NSB). From the definition of operations on sets, we get: M = ((AB) \ C)  (C \ A \ B). Let's write this expression using basic operations - complement, union and intersection: It is impossible to simplify this expression, since we have one occurrence of each symbol. This is the simplest form of this formula. This area can be considered as the union of the sets A \ B \ C and ABC. By definition, M = ( x xA and xB and NSC or NSA and NSB and NSC). Let's simplify: Tasks for an independent solution. 1. Simplify: 2. Prove using diagrams, laws of set algebra and definition of equality of sets: (AB) \ B = A \ B; A (BC) = A \ (A \ B)  (A \ C); АВ = АВ  А = В; A \ B =   AB = A. 3. Find out whether there is a set X satisfying for any A the equality: AX = A; (answer );

De Morgan's Laws are logical rules established by the Scottish mathematician Augustus de Morgan that connect pairs of logical operations using logical negation. Augustus de Morgan noted that in classical logic the following relations are true: 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 ratios can be written in the following form: De Morgan's laws can be formulated as follows: I de Morgan's law: The denial of a disjunction of two simple statements is tantamount to a conjunction of the negations of these statements. II de Morgan's law: The denial of the conjunction of two simple statements is tantamount to the disjunction of the negations of these statements. Let's consider the application of de Morgan's laws with specific examples. Example 1. Transform the formula so that there are no negations of complex statements. Using the first de Morgan's law, we get: to negate the conjunction of simple statements B and C we apply the second de Morgan's law, we get: , thus: . As a result, we got an equivalent statement, in which there are no denials of compound statements, and all negations refer only to simple statements. You can check the validity of the decision using truth tables. To do this, we will compose truth tables for the original statement: and for a statement obtained as a result of transformations performed with the help of de Morgan's laws: . Table 1. B / \ C A \ / B / \ C As you can 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 truth tables we received the same sets of values.