Methods for solving logical equations. Logics. Logic functions. Solving Equations

Let be a logical function of n variables. The logical equation is:

The constant C has the value 1 or 0.

The logical equation can have from 0 to various solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table on which the function F takes the value true (1). The remaining sets are solutions of the equation for C, zero. We can always consider only equations of the form:

Indeed, let the equation be given:

In this case, you can go to the equivalent equation:

Consider a system of k logical equations:

The solution of the system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to the system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions:

If the number of variables is small, for example, less than 5, then it is not difficult to construct a truth table for the function , which allows you to say how many solutions the system has and what are the sets that give solutions.

In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, which is different from enumeration, which allows solving such problems.

In the problems proposed in the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from enumeration of all variants of a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique solution to this problem is as follows. We are not interested in all sets, but only those on which the function has the value 1. Instead of building a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies the set on which the function has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.

What is a binary decision tree and how it is built, I will explain with examples of several tasks.

Problem 18

How many different sets of values ​​of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy a system of two equations?

Answer: The system has 36 different solutions.

Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation depending on 5 variables - . The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents a conjunction of logical functions. The converse statement is also true - the conjunction of conditions can be considered as a system of equations.

Let's build a decision tree for the implication () - the first term of the conjunction, which can be considered as the first equation. Here is what the graphic image of this tree looks like

The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable . Two branches of this level reflect the possible values ​​of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values ​​of the variable for which the equation takes the value true. Since the equation defines an implication, the branch on which it has a value of 1 requires that it has a value of 1 on that branch. The branch on which it has a value of 0 generates two branches with values ​​equal to 0 and 1. The constructed tree defines three solutions, on where the implication takes the value 1. On each branch, the corresponding set of values ​​of the variables is written out, which gives a solution to the equation.

These sets are: ((1, 1), (0, 1), (0, 0))

Let's continue building the decision tree by adding the following equation, the following implication. The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable already has values ​​in the tree, then on all branches where the variable has a value of 1, the variable will also have a value of 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable has the value 0 will give a branch into two branches, where the variable will get the values ​​0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:

has 6 solutions. Here is what the complete decision tree for this equation looks like:

The second equation of our system is similar to the first:

The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution can be combined with each variable solution, the total number of solutions is 36.

Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.

Problem 19

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?

This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.

It follows from the equation that when it has the value 1 (one such solution exists), then it has the value 1. Thus, there is one set on which and have the values ​​1. When equal to 0, it can have any value, both 0 and and 1. Therefore, each set with equal to 0, and there are 5 such sets, corresponds to all 6 sets with variables Y. Therefore, the total number of solutions is 31.

Problem 20

Solution: Remembering the basic equivalence, we write our equation as:

The cyclic chain of implications means that the variables are identical, so our equation is equivalent to:

This equation has two solutions when all are either 1 or 0.

Problem 21

How many solutions does the equation have:

Solution: Just as in Problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:

Let's build a decision tree for this equation:

Problem 22

How many solutions does the following system of equations have?

This material contains a presentation that presents methods for solving logical equations and systems of logical equations in task B15 (No. 23, 2015) of the Unified State Examination in Informatics. It is known that this task is one of the most difficult among the tasks of the exam. The presentation can be useful when conducting lessons on the topic "Logic" in specialized classes, as well as in preparation for passing the exam.

Download:

Preview:

To use the preview of presentations, create a Google account (account) and sign in: https://accounts.google.com

Slides captions:

Solution of task B15 (system of logical equations) Vishnevskaya M.P., MAOU "Gymnasium No. 3" November 18, 2013, Saratov

Task B15 is one of the most difficult in the exam in computer science !!! Skills are checked: to transform expressions containing logical variables; describe in natural language the set of values ​​of logical variables for which a given set of logical variables is true; count the number of binary sets that satisfy the given conditions. The most difficult, because there are no formal rules on how to do this, guesswork is required.

What not to do without!

What not to do without!

Conventions conjunction: A /\ B , A  B , AB , А &B, A and B disjunction: A \ / B , A + B , A | B , A or B negation:  A , A, not A equivalent: A  B, A  B, A  B XOR: A  B , A xor B

Variable substitution method How many different sets of values ​​of boolean variables x1, x2, ..., x9, x10 exist that satisfy all of the following conditions: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ ​​(¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ ​​(¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ ​​(¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ ​​(¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 The answer does not need to list all the different sets x1, x2, …, x9, x10 under which the given system of equalities is satisfied. As an answer, you must indicate the number of such sets (demo version 2012)

Solution Step 1. Simplify by changing variables t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 After simplification: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬t4 \/ ¬ t5) =1 Consider one of the equations: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Obviously, it =1 only if one of the variables is 0 and the other is 1. We use the formula to express the XOR operation in terms of conjunction and disjunction: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Step2. Analysis of the system .To. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), then each value tk corresponds to two pairs of values ​​x2k-1 and x2k , for example: tk =0 corresponds to two pairs - (0,1) and (1, 0) , and tk =1 are the pairs (0,0) and (1,1).

Step3. Counting the number of solutions. Each t has 2 solutions, the number of t is 5. Thus for variables t there are 2 5 = 32 solutions. But each t corresponds to a pair of solutions x, i.e. the original system has 2*32 = 64 solutions. Answer: 64

Partial solution elimination method How many different sets of values ​​of logical variables x1, x2, …, x5, y1,y2,…, y5 exist that satisfy all the following conditions: (x1→ x2)∧(x2→ x3)∧(x3→ x4 )∧(x4→ x5) =1; (y1→ y2)∧(y2→ y3)∧(y3→ y4) ∧(y4→ y5) =1; y5→ x5 =1. The answer does not need to list all the different sets x1, x2, ..., x5, y 1, y2, ..., y5, under which this system of equalities is satisfied. As an answer, you must indicate the number of such sets.

Solution. Step 1. Sequential solution of equations x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 each of the implications is true. The implication is false only in one case, when 1  0, in all other cases (0  0, 0  1, 1  1) the operation returns 1. Let's write this in the form of a table:

Step 1. Sequential solution of equations Т.о. 6 sets of solutions for х1,х2,х3,х4,х5 are received: (00000), (00001), (00011), (00111), (01111), (11111). Arguing similarly, we conclude that for y1, y2, y3, y4, y5 there is the same set of solutions. Because these equations are independent, i.e. there are no common variables in them, then the solution to this system of equations (without taking into account the third equation) will be 6 * 6 = 36 pairs of “xes” and “yes”. Consider the third equation: y5→ x5 =1 Pairs are the solution: 0 0 0 1 1 1 Pair is not a solution: 1 0

Let's compare the obtained solutions. Where y5 =1, x5=0 do not fit. there are 5 such pairs. The number of solutions of the system: 36-5= 31. Answer: 31 It took combinatorics!!!

Dynamic programming method How many different solutions does the logical equation x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1 have, where x 1, x 2, ..., x 6 are logical 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 Step1. Analysis of the condition On the left side of the equation, implication operations are sequentially written, the priority is the same. Rewrite: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 NB! Each next variable does not depend on the previous one, but on the result of the previous implication!

Step2. Revealing the pattern Consider the first implication, X 1 → X 2. Truth table: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 From one 0 we got 2 ones, and from 1 we got one 0 and one 1. Only one 0 and three 1, this is the result of the first operation.

Step2. Revealing a pattern Connecting x 3 to the result of the first operation, we get: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Out of two 0s - two 1s, out of each 1 (there are 3) one each 0 and 1 (3 + 3)

Step 3. Derivation of the formula you can make formulas for calculating the number of zeros N i and the number of ones E i for an equation with i variables: ,

Step 4. Filling in the table Let's fill in the table for i = 6 from left to right, calculating the number of zeros and ones using the above formulas; the table shows how the next column is built according to the previous one: : number of variables 1 2 3 4 5 6 Number of zeros N i 1 1 3 5 11 21 Number of ones E i 1 2*1+1= 3 2*1+3= 5 11 21 43 Answer: 43

Method using simplifications of logical expressions How many different solutions does the equation have ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 where J , K, L, M, N are logical variables? The answer does not need to list all the different sets of values ​​J , K, L, M and N for which this equality holds. As an answer, you need to indicate the number of such sets.

Solution Note that J → K = ¬ J  K We introduce a change of variables: J → K=A, M  N  L =B We rewrite the equation taking into account the change: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Obviously, A  B for the same values ​​of A and B 6. Consider the last implication M → J =1 This is possible if: M= J=0 M=0, J=1 M=J=1

Solution A  B , then With M=J=0 we get 1 + K=0. There are no solutions. With M=0, J=1 we get 0 + K=0, K=0, and N and L - any, 4 solutions: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Solution 10. With M=J=1 we get 0+K=1 *N * L , or K=N*L, 4 solutions: 11. Total has 4+4=8 solutions Answer: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Sources of information: O.B. Bogomolova, D.Yu. Usenkov. B15: new tasks and new solution // Informatics, No. 6, 2012, p. 35 – 39. K.Yu. Polyakov. Logical Equations // Informatics, No. 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/b15/, [Electronic resource]. http://kpolyakov.narod.ru/school/ege.htm, [Electronic resource].

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.