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.
| Course section | Average percentage of completion by groups of tasks |
| Coding information and measuring its quantity | |
| information modeling | |
| Number systems | |
| Fundamentals of Algebra of Logic | |
| Algorithmization and programming | |
| Fundamentals of information and communication technologies |
Based on the specification of KIM 2018, this block includes four tasks of different levels of complexity.
| № tasks | Checked content elements | Task difficulty level |
| Ability to build truth tables and logic circuits | ||
| Ability to search for information on the Internet | ||
| Knowledge of basic concepts and laws mathematical logic | ||
| Ability to build and transform logical expressions |
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:
| x 1 y 1 | x2 y2 | (x 1 y1) (x 2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
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.
| (x1 , y1 ) | (x2 , y2 ) |
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).
| (x1 , y1 ) | (x2 , y2 ) |
Let's make a table to calculate the number of pairs at each stage.
| 0 |
|||||||
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)
There are various ways to solve systems of logical equations. This is a reduction to one equation, the construction of a truth table and decomposition.
A 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:
|
0 |
0 |
1 |
1 |
0 |
1 |
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.
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 ischange 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.
A task: How many solutions does the equation (A → B ) + (C → D ) = 1 have? 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 will be written in the form: X + Y = 1.
The disjunction is true in three cases: (0;1), (1;0) and (1;1), while X and Y are 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.
A 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 that x 1 is true, then from the first equation we get that x 2 also true, from the second - x 3 =1, and so on until x m= 1. This means that the set (1; 1; …; 1) of m units is the solution of the system. Let now x 1 =0, then from the first equation we have x 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. At x 2 =0 we get that x 3 =0 or x 3 =, and so on. Continuing to the last variable, we get that the solutions of the equation are the following sets of variables (m + 1 solution, each solution has m values of variables):
(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 equal to m + 1.
|
Wood |
Number of decisions |
|
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
|
… |
In case of difficulties in reasoning niyah and construction deroar of solutions, you can search for a solution with 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:
|
x 1 |
x2 |
(x 1 → x 2) |
Let's make a truth table for two equations:
|
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Lesson topic: Solving logical equations
Educational - learning how to solve logical equations, the formation of skills and abilities for solving logical equations and building a logical expression according to the truth table;Educational - create conditions for the development of cognitive interest of students, promote the development of memory, attention, logical thinking;
Educational : contribute to the education of the ability to listen to the opinions of others, education of will and perseverance to achieve the final results.
Lesson type: combined lesson
Equipment: computer, multimedia projector, presentation 6.
During the classes
Repetition and updating of basic knowledge. Checking homework (10 minutes)
In the previous lessons, we got acquainted with the basic laws of the algebra of logic, learned how to use these laws to simplify logical expressions.
Let's check the homework on simplifying logical expressions:
1. Which of the following words satisfies the logical condition:
(first consonant → second consonant)٨ (last letter vowel → penultimate letter vowel)? If there are several such words, indicate the smallest of them.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Let us introduce the notation:
A is the first letter of a consonant
B is the second letter of a consonant
S is the last vowel
D - penultimate vowel
Let's make an expression:
Let's make a table:
2. Indicate which logical expression is equivalent to the expression
Let's simplify the writing of the original expression and the proposed options:
3. A fragment of the truth table of the expression F is given:
What expression corresponds to F?
Let's determine the values of these expressions for the specified values of the arguments:
Familiarization with the topic of the lesson, presentation of new material (30 minutes)
We continue to study the basics of logic and the topic of our today's lesson "Solving logical equations." After studying this topic, you will learn the basic ways to solve logical equations, get the skills to solve these equations by using the language of logic algebra and the ability to compose a logical expression on the truth table.
1. Solve the logical equation
(¬K M) → (¬L M N)=0
Write your answer as a string of four characters: the values of the variables K, L, M, and N (in that order). So, for example, line 1101 corresponds to K=1, L=1, M=0, N=1.
Solution:
Let's transform the expression(¬K M) → (¬L M N)
The expression is false when both terms are false. The second term is equal to 0 if M=0, N=0, L=1. In the first term, K = 0, since M = 0, and 
.
Answer: 0100
2. How many solutions does the equation have (indicate only the number in your answer)?
Solution: transform the expression
(A+B)*(C+D)=1
A+B=1 and C+D=1
Method 2: compiling a truth table
3 way: construction of SDNF - a perfect disjunctive normal form for a function - a disjunction of complete regular elementary conjunctions.Let's transform the original expression, open the brackets in order to get the disjunction of the conjunctions:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Let's supplement the conjunctions to complete conjunctions (the product of all arguments), open the brackets:
Consider the same conjunctions:
As a result, we obtain an SDNF containing 9 conjunctions. Therefore, the truth table for this function has a value of 1 on 9 rows out of 2 4 =16 sets of variable values.
3. How many solutions does the equation have (indicate only the number in your answer)?
Let's simplify the expression:
,
3 way: construction of SDNF
Consider the same conjunctions:
As a result, we get an SDNF containing 5 conjunctions. Therefore, the truth table for this function has a value of 1 on 5 rows of 2 4 =16 sets of variable values.
Building a logical expression according to the truth table:
for each row of the truth table containing 1, we compose the product of the arguments, and the variables equal to 0 are included in the product with negation, and the variables equal to 1 - without negation. The desired expression F will be composed of the sum of the products obtained. Then, if possible, this expression should be simplified.
Example: the truth table of an expression is given. Build a logical expression.
Solution:3. Homework (5 minutes)
Solve the equation:
How many solutions does the equation have (answer only the number)?
According to the given truth table, make a logical expression and
simplify it.
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.
A 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:
|
0 |
0 |
1 |
1 |
0 |
1 |
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.
A 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.
A 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.
|
Variables |
Wood |
Number of decisions |
|
x 1 |
|
|
|
x2 |
||
|
x 3 |
||
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:
|
x 1 |
x2 |
(x 1 → x 2) |
Let's make a truth table for two equations:
|
x 1 |
x2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
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:
X1 ≡ X2 |
||
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:
X1 ∧ X10 | ¬X1 ∧ ¬X10 | (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10) |
||
Pay attention to the last column, it matches the result of the action X1 ≡ X10.
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.
