Solving logical equations in mathematics. Methods for solving systems of logical equations System of Boolean equations

Solving systems of logical equations by changing variables

The change of variables method is used if some variables are included in the equations only in the form of a specific expression, and nothing else. Then this expression can be denoted by a new variable.

Example 1

How many different sets of values ​​of logical variables x1, x2, x3, x4, x5, x6, x7, x8 are there that satisfy all of the following conditions?

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

The answer does not need to list all the different sets of values ​​of the variables x1, x2, x3, x4, x5, x6, x7, x8, under which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Then the system can be written as a single equation:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. The conjunction is 1 (true) when each operand evaluates to 1. That is, each of the implications must be true, and this is true for all values ​​except (1 → 0). Those. in the table of values ​​of variables y1, y2, y3, y4, the unit must not be to the left of zero:

Those. conditions are met for 5 sets y1-y4.

Because y1 = x1 → x2, then the value y1 = 0 is achieved on a single set x1, x2: (1, 0), and the value y1 = 1 is achieved on three sets x1, x2: (0,0) , (0,1), (1.1). Similarly for y2, y3, y4.

Since each set (x1,x2) for variable y1 is combined with each set (x3,x4) for variable y2, and so on, the numbers of sets of variables x are multiplied:

Let's add the number of sets: 1 + 3 + 9 + 27 + 81 = 121.

Answer: 121

Example 2

How many different sets of values ​​of boolean variables x1, x2, ... x9, y1, y2, ... y9 are there that satisfy all of the following conditions?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

In response no need list all different sets of values ​​of the variables x1, x2, ... x9, y1, y2, ... y9, under which the given system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

Let's make a change of variables:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

The system can be written as a single equation:

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)

Equivalence is true only if both operands are equal. The solutions to this equation will be two sets:

Because zi = (xi ≡ yi), then the value zi = 0 corresponds to two sets (xi,yi): (0,1) and (1,0), and the value zi = 1 corresponds to two sets (xi,yi): (0 ,0) and (1,1).

Then the first set z1, z2,…, z9 corresponds to 2 9 sets (x1,y1), (x2,y2),…, (x9,y9).

The same number corresponds to the second set z1, z2,…, z9. Then there are 2 9 +2 9 = 1024 sets in total.

Answer: 1024

Solving systems of logical equations by visual definition of recursion.

This method is used if the system of equations is simple enough and the order of increasing the number of sets when adding variables is obvious.

Example 3

How many different solutions does the system of equations have

¬x9 ∨ x10 = 1,

where x1, x2, ... x10 are boolean variables?

The answer does not need to enumerate all the different sets of values ​​x1, x2, ... x10 for which the given system of equalities holds. As an answer, you need to indicate the number of such sets.

Solution:

Let's solve the first equation. A disjunction is equal to 1 if at least one of its operands is equal to 1. That is, the solutions are the sets:

For x1=0, there are two x2 values ​​(0 and 1), and for x1=1, there is only one x2 value (1), such that the set (x1,x2) is the solution to the equation. Only 3 sets.

Let's add the variable x3 and consider the second equation. It is similar to the first one, which means that for x2=0 there are two values ​​of x3 (0 and 1), and for x2=1 there is only one value of x3 (1), such that the set (x2,x3) is a solution to the equation. There are 4 sets in total.

It is easy to see that when adding another variable, one set is added. Those. recursive formula for the number of sets on (i+1) variables:

N i +1 = N i + 1. Then for ten variables we get 11 sets.

Answer: 11

Solving systems of logical equations of various types

Example 4

How many different sets of values ​​of boolean variables x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 are there that satisfy all of the following conditions?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

In response no need list all different sets of values ​​of the variables x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , under which the given system of equalities is satisfied.

As an answer, you need to indicate the number of such sets.

Solution:

Note that the three equations of the system are the same on different independent sets of variables.

Consider the first equation. A conjunction is true (equal to 1) only if all of its operands are true (equal to 1). The implication is 1 on all sets except (1,0). This means that the solution to the first equation will be such sets x1, x2, x3, x4, in which 1 is not to the left of 0 (5 sets):

Similarly, the solutions of the second and third equations will be exactly the same sets of y1,…,y4 and z1,…,z4.

Now let's analyze the fourth equation of the system: x 4 ∧ y 4 ∧ z 4 = 0. The solution will be all sets x4, y4, z4 in which at least one of the variables is equal to 0.

Those. for x4 = 0, all possible sets (y4, z4) are suitable, and for x4 = 1, sets (y4, z4) that contain at least one zero are suitable: (0, 0), (0,1) , (1, 0).

The total number of sets is 25 + 4*9 = 25 + 36 = 61.

Answer: 61

Solving systems of logical equations by constructing recurrent formulas

The method of constructing recurrent formulas is used to solve complex systems in which the order of increasing the number of sets is not obvious, and building a tree is impossible due to volumes.

Example 5

How many different sets of values ​​of boolean variables x1, x2, ... x7, y1, y2, ... y7 are there that satisfy all of the following conditions?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

The answer does not need to list all the different sets of values ​​of the variables x1, x2, ..., x7, y1, y2, ..., y7, under which the given system of equalities holds. As an answer, you need to indicate the number of such sets.

Solution:

Note that the first six equations of the system are the same and differ only in the set of variables. Consider the first equation. Its solution will be the following sets of variables:

Denote:

number of sets (0,0) on variables (x1,y1) through A 1 ,

number of sets (0,1) on variables (x1,y1) through B 1 ,

number of sets (1,0) on variables (x1,y1) via C 1 ,

number of sets (1,1) on variables (x1,y1) via D 1 .

number of sets (0,0) on variables (x2,y2) through A 2 ,

number of sets (0,1) on variables (x2,y2) via B 2 ,

number of sets (1,0) on variables (x2,y2) via C 2 ,

number of sets (1,1) on variables (x2,y2) via D 2 .

From the decision tree, we see that

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

Note that the tuple (0,0) on the variables (x2,y2) is obtained from the tuples (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. A 2 \u003d B 1 + C 1 + D 1.

The set (0,1) on the variables (x2,y2) is obtained from the sets (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. B 2 \u003d B 1 + C 1 + D 1.

Arguing similarly, we note that C 2 \u003d B 1 + C 1 + D 1. D2 = D1.

Thus, we obtain recursive formulas:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i + B i + C i + D i

Let's make a table

The last equation (x7 ∨ y7) = 1 is satisfied by all sets except those in which x7=0 and y7=0. In our table, the number of such sets is A 7 .

Then the total number of sets is B 7 + C 7 + D 7 = 127+127+1 = 255

Answer: 255

The use of equations is widespread in our lives. They are used in many calculations, construction of structures and even sports. Equations have been used by man since ancient times and since then their use has only increased. In mathematics, there are certain tasks that are devoted to the logic of propositions. To solve this kind of equation, you must have a certain amount of knowledge: knowledge of the laws of propositional logic, knowledge of the truth tables of logical functions of 1 or 2 variables, methods for transforming logical expressions. In addition, you need to know the following properties of logical operations: conjunctions, disjunctions, inversions, implications and equivalences.

Any logical function from \ variables - \ can be specified by a truth table.

Let's solve some logical equations:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Let's start the solution with \[X1\] and determine what values ​​\u200b\u200bthis variable can take: 0 and 1. Next, consider each of the above values ​​\u200b\u200band see what \[X2.\] can be in this case

As can be seen from the table, our logical equation has 11 solutions.

Where can I solve a logical equation online?

You can solve the equation on our website https: // site. Free online solver will allow you to solve an online equation of any complexity in seconds. All you have to do is just enter your data into the solver. You can also watch the video instruction and learn how to solve the equation on our website. And if you have any questions, you can ask them in our Vkontakte group http://vk.com/pocketteacher. Join our group, we are always happy to help you.

Ways to solve systems of logical equations

Kirgizova E.V., Nemkova A.E.

Lesosibirsk Pedagogical Institute -

branch of the Siberian Federal University, Russia

The ability to think consistently, argue conclusively, build hypotheses, refute negative conclusions, does not come by itself, this skill is developed by the science of logic. Logic is a science that studies the methods of establishing the truth or falsity of some statements on the basis of the truth or falsity of other statements.

Mastering the basics of this science is impossible without solving logical problems. Checking the formation of skills to apply their knowledge in a new situation is carried out by passing. In particular, this is the ability to solve logical problems. Tasks B15 in the exam are tasks of increased complexity, since they contain systems of logical equations. There are various ways to solve systems of logical equations. This is reduction to one equation, construction of a truth table, decomposition, sequential solution of equations, etc.

Task:Solve a system of logical equations:

Consider method of reduction to one equation . This method involves the transformation of logical equations, so that their right-hand sides are equal to the truth value (that is, 1). To do this, use the operation of logical negation. Then, if there are complex logical operations in the equations, we replace them with basic ones: “AND”, “OR”, “NOT”. The next step is to combine the equations into one, equivalent to the system, using the logical operation "AND". After that, you should make transformations of the resulting equation based on the laws of the algebra of logic and get a specific solution to the system.

Solution 1:Apply the inversion to both sides of the first equation:

Let's represent the implication through the basic operations "OR", "NOT":

Since the left sides of the equations are equal to 1, you can combine them using the “AND” operation into one equation that is equivalent to the original system:

We open the first bracket according to de Morgan's law and transform the result:

The resulting equation has one solution: A= 0 , B=0 and C=1 .

The next way is construction of truth tables . Since logical values ​​have only two values, you can simply go through all the options and find among them those for which the given system of equations is satisfied. That is, we build one common truth table for all equations of the system and find a line with the desired values.

Solution 2:Let's make a truth table for the system:

Bold is the line for which the conditions of the problem are met. So A =0 , B =0 and C =1 .

Way decomposition . The idea is to fix the value of one of the variables (put it equal to 0 or 1) and thereby simplify the equations. Then you can fix the value of the second variable, and so on.

Solution 3: Let A = 0, then:

From the first equation we get B =0, and from the second - С=1. System solution: A = 0 , B = 0 and C = 1 .

You can also use the method sequential solution of equations , adding one variable to the set under consideration at each step. To do this, it is necessary to transform the equations in such a way that the variables are entered in alphabetical order. Next, we build a decision tree, sequentially adding variables to it.

The first equation of the system depends only on A and B, and the second equation on A and C. Variable A can take 2 values ​​0 and 1:

It follows from the first equation that , so when A = 0 we get B = 0 , and for A = 1 we have B = 1 . So, the first equation has two solutions with respect to the variables A and B .

We draw the second equation, from which we determine the values ​​of C for each option. For A =1, the implication cannot be false, that is, the second branch of the tree has no solution. At A= 0 we get the only solution C= 1 :

Thus, we got the solution of the system: A = 0 , B = 0 and C = 1 .

In the USE in computer science, it is very often necessary to determine the number of solutions to a system of logical equations, without finding the solutions themselves, there are also certain methods for this. The main way to find the number of solutions to a system of logical equations is change of variables. First, it is necessary to simplify each of the equations as much as possible based on the laws of the algebra of logic, and then replace the complex parts of the equations with new variables and determine the number of solutions to the new system. Then return to the replacement and determine the number of solutions for it.

Task:How many solutions does the equation ( A → B ) + (C → D ) = 1? Where A, B, C, D are boolean variables.

Solution:Let's introduce new variables: X = A → B and Y = C → D . Taking into account the new variables, the equation can be written as: X + Y = 1.

The disjunction is true in three cases: (0;1), (1;0) and (1;1), while X and Y is an implication, that is, it is true in three cases and false in one. Therefore, the case (0;1) will correspond to three possible combinations of parameters. Case (1;1) - will correspond to nine possible combinations of the parameters of the original equation. Hence, there are 3+9=15 possible solutions of this equation.

The following way to determine the number of solutions to a system of logical equations is − binary tree. Let's consider this method with an example.

Task:How many different solutions does the system of logical equations have:

The given system of equations is equivalent to the equation:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Let's pretend thatx 1 is true, then from the first equation we get thatx 2 also true, from the second -x 3 =1, and so on until x m= 1. Hence the set (1; 1; …; 1) from m units is the solution of the system. Let nowx 1 =0, then from the first equation we havex 2 =0 or x 2 =1.

When x 2 true, we obtain that the other variables are also true, that is, the set (0; 1; ...; 1) is the solution of the system. Atx 2 =0 we get that x 3 =0 or x 3 =, and so on. Continuing to the last variable, we find that the solutions to the equation are the following sets of variables ( m +1 solution, in each solution m variable values):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

This approach is well illustrated by building a binary tree. The number of possible solutions is the number of different branches of the constructed tree. It is easy to see that it is m+1.

In case of difficulties in reasoning and building a decision tree, you can look for a solution using truth tables, for one or two equations.

We rewrite the system of equations in the form:

And let's make a truth table separately for one equation:

Let's make a truth table for two equations:

Next, you can see that one equation is true in the following three cases: (0; 0), (0; 1), (1; 1). The system of two equations is true in four cases (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). In this case, it is immediately clear that there is a solution consisting of only zeros and more m solutions in which one unit is added, starting from the last position until all possible places are filled. It can be assumed that the general solution will have the same form, but for such an approach to become a solution, proof that the assumption is true is required.

Summing up all of the above, I would like to draw attention to the fact that not all of the considered methods are universal. When solving each system of logical equations, its features should be taken into account, on the basis of which the solution method should be chosen.

Literature:

1. Logical tasks / O.B. Bogomolov - 2nd ed. – M.: BINOM. Knowledge Laboratory, 2006. - 271 p.: ill.

2. Polyakov K.Yu. Systems of logical equations / Educational and methodical newspaper for teachers of computer science: Informatics No. 14, 2011

Methods for solving systems of logical equations

You can solve a system of logical equations, for example, using a truth table (if the number of variables is not too large) or using a decision tree, after simplifying each equation.

1. Method of change of variables.

The introduction of new variables makes it possible to simplify the system of equations by reducing the number of unknowns.New variables must be independent of each other. After solving the simplified system, it is necessary to return to the original variables again.

Consider the application of this method on a specific example.

Example.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Solution:

Let's introduce new variables: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Attention! Each of their variables x1, x2, ..., x10 must be included in only one of the new variables A, B, C, D, E, i.e. the new variables are independent of each other).

Then the system of equations will look like this:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Let's build a decision tree of the resulting system:

Consider the equation A=0, i.e. (X1≡ X2)=0. It has 2 roots:

From the same table it can be seen that the equation A \u003d 1 also has 2 roots. Let's arrange the number of roots on the decision tree:

To find the number of solutions for one branch, you need to multiply the number of solutions at each level. The left branch has 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 solutions; the right branch also has 32 solutions. Those. the whole system has 32+32=64 solutions.

Answer: 64.

2. Method of reasoning.

The complexity of solving systems of logical equations lies in the bulkiness of the complete decision tree. The reasoning method allows you not to build the whole tree completely, but at the same time understand how many branches it will have. Let's consider this method on concrete examples.

Example 1 How many different sets of values ​​of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

The answer does not need to list all the different sets of values ​​of the variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 under which the given system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution :

The first and second equations contain independent variables that are related by a third condition. Let us construct a decision tree for the first and second equations.

To represent the decision tree of the system from the first and second equations, it is necessary to continue each branch of the first tree with a tree for variables at . The tree constructed in this way will contain 36 branches. Some of these branches do not satisfy the third equation of the system. Note on the first tree the number of branches of the tree"at" , which satisfy the third equation:

Let us clarify: for the fulfillment of the third condition at x1=0 there must be y1=1, i.e. all branches of the tree"X" , where x1=0 can be continued with only one branch from the tree"at" . And only for one branch of the tree"X" (right) fit all branches of the tree"at". Thus, the complete tree of the entire system contains 11 branches. Each branch represents one solution to the original system of equations. So the whole system has 11 solutions.

Answer: 11.

Example 2 How many different solutions does the system of equations have

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

where x1, x2, …, x10 are boolean variables? The answer does not need to list all the different sets of variable values ​​for which this equality holds. As an answer, you need to indicate the number of such sets.

Solution : Let's simplify the system. Let's build a truth table of the part of the first equation:

Pay attention to the last column, it matches the result of the action X1 ≡ X10.

After simplification, we get:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Consider the last equation:(X1 ≡ X10) = 0 , i.e. x1 should not be the same as x10. For the first equation to be equal to 1, the equality must hold(X1 ≡ X2)=1, i.e. x1 must match x2.

Let's build a decision tree for the first equation:

Consider the second equation: for x10=1 and for x2=0 the bracketmust be equal to 1 (i.e. x2 is the same as x3); at x10=0 and at x2=1 bracket(X2 ≡ X10)=0 , so bracket (X2 ≡ X3) must be equal to 1 (i.e. x2 is the same as x3):

Arguing in this way, we construct a decision tree for all equations:

Thus, the system of equations has only 2 solutions.

Answer: 2.

Example 3

How many different sets of values ​​of boolean variables x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 are there that satisfy all of the following conditions?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Solution:

Let's build a decision tree of the 1st equation:

Consider the second equation:

• When x1=0 : second and third brackets will be 0; for the first bracket to be equal to 1, must y1=1 , z1=1 (i.e. in this case - 1 solution)
• With x1=1 : first parenthesis will be 0; second or the third parenthesis must be equal to 1; the second bracket will be equal to 1 when y1=0 and z1=1; the third bracket will be equal to 1 for y1=1 and z1=0 (i.e. in this case - 2 solutions).

Similarly for the rest of the equations. Note the number of solutions obtained for each node of the tree:

To find out the number of solutions for each branch, we multiply the obtained numbers separately for each branch (from left to right).

1 branch: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solution

2 branch: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 solutions

3rd branch: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 solutions

4 branch: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 solutions

5 branch: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 solutions

Let's add the numbers obtained: a total of 31 solutions.

Answer: 31.

3. Regular increase in the number of roots

In some systems, the number of roots of the next equation depends on the number of roots of the previous equation.

Example 1 How many different sets of values ​​of boolean variables x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 are there that satisfy all of the following conditions?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Simplify first equation:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Then the system will take the form:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Etc.

Each following equation has 2 more roots than the previous one.

4 equation has 12 roots;

Equation 5 has 14 roots

8 equation has 20 roots.

Answer: 20 roots.

Sometimes the number of roots grows according to the law of Fibonacci numbers.

Solving a system of logical equations requires a creative approach.

Municipal budgetary educational institution

"Secondary school No. 18"

urban district of the city of Salavat of the Republic of Bashkortostan

Systems of logical equations

in the tasks of the exam in informatics

The section "Fundamentals of Algebra of Logic" in the tasks of the exam is considered one of the most difficult and poorly solved. The average percentage of completing tasks on this topic is the lowest and is 43.2.

Based on the specification of KIM 2018, this block includes four tasks of different levels of complexity.

Task 23 is a high level of difficulty, therefore it has the lowest percentage of completion. Among the trained graduates (81-100 points) 49.8% completed the task, the averagely prepared (61-80 points) cope by 13.7%, the remaining group of students does not complete this task.

The success of solving a system of logical equations depends on the knowledge of the laws of logic and on the precise application of methods for solving the system.

Consider the solution of a system of logical equations by the mapping method.

(23.154 Polyakov K.Yu.) How many different solutions does the system of equations have?

((x1  y1 )  (x2  y2 ))  (x1  x2 )  (y1  y2 ) =1

((x2  y2 )  (x3  y3 ))  (x2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

Where x1 , x2 ,…, x8, at1 ,y2 ,…,y8 - Boolean variables? The answer does not need to list all the different sets of variable values ​​for which this equality holds. As an answer, you need to indicate the number of such sets.

Solution. All equations included in the system are of the same type, and four variables are included in each equation. Knowing x1 and y1, we can find all possible values ​​of x2 and y2 that satisfy the first equation. Arguing in a similar way, from the known x2 and y2 we can find x3, y3 that satisfies the second equation. That is, knowing the pair (x1 , y1) and determining the value of the pair (x2 , y2) , we will find the pair (x3 , y3 ), which in turn will lead to the pair (x4 , y4 ) and so on.

Let's find all solutions of the first equation. This can be done in two ways: to build a truth table, through reasoning and applying the laws of logic.

Truth table:

Building a truth table is laborious and time inefficient, so we use the second method - logical reasoning. The product is 1 if and only if each factor is 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Consider the first equation. Following is equal to 1, when 0 0, 0 1, 1 1, then (x1 y1)=0 at (01), (10), then the pair (x2  y2 ) can be any (00), (01), (10), (11), and for (x1 y1)=1, i.e. (00) and (11) the pair (x2 y2)=1 takes the same values (00) and (11). We exclude from this solution those pairs for which the second and third equations are false, that is, x1=1, x2=0, y1=1, y2=0.

Total number of pairs 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) How many different solutions does a system of logical equations have

(x 1  (x 2  y 2 ))  (y 1  y 2 ) = 1

(x 2  (x 3  y 3 ))  (y 2  y 3 ) = 1

...

( x 6  ( x 7  y 7 ))  ( y 6  y 7 ) = 1

x 7  y 7 = 1

Solution. 1) The equations are of the same type, so by the method of reasoning we will find all possible pairs (x1,y1), (x2,y2) of the first equation.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

The solution of the second equation are pairs (00), (01), (11).

Let's find solutions to the first equation. If x1=0, then x2 , y2 - any, if x1=1, then x2 , y2 takes the value (11).

Let's make connections between pairs (x1 , y1) and (x2 , y2).

Let's make a table to calculate the number of pairs at each stage.

Taking into account the solutions of the last equation x 7  y 7 = 1, we eliminate the pair (10). Find the total number of solutions 1+7+0+34=42

3)(23.180) How many different solutions does the system of logical equations have

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Solution. 1) The equations are of the same type, so by the method of reasoning we will find all possible pairs (x1,x2), (x3,x4) of the first equation.

(x1  x2 )  (x3  x4 ) = 1

We exclude from the solution the pairs that give 0 (1 0) in the following, these are the pairs (01, 00, 11) and (10).

Compose links between pairs (x1,x2), (x3,x4)