Noskin Andrey Nikolaevich,
IT-teacher
highest qualification category,
Candidate of Military Sciences, Associate Professor
GBOU Lyceum No. 1575, Moscow
Optimized mapping method for solving problem 23 from KIM Unified State Examination in computer science and ICT
One of the most difficult tasks in the Unified State Exam KIM is problem 23, in which you need to find the number of different sets of values of logical variables that satisfy the specified condition.
This task is perhaps the most difficult task of the KIM Unified State Examination in computer science and ICT. As a rule, no more than 5% of examinees cope with it (1).
Such a small percentage of students who completed this task is explained by the following:
- students may confuse (forget) the signs of logical operations;
- mathematical errors in the process of performing calculations;
- errors in reasoning when searching for a solution;
- errors in the process of simplifying logical expressions;
- teachers recommend solving this problem after completing all the work, since the likelihood of
errors are very large, and the “weight” of the task is only one primary point.
In addition, some teachers themselves have difficulty solving this type of problem and therefore try to solve simpler problems with children.
Also complicating the situation is that in this block there is a large number of various tasks and it is impossible to choose a template solution.
To correct this situation, the teaching community is finalizing the main two methods for solving problems of this type: solution using bit chains (2) and mapping method (3).
The need to refine (optimize) these methods is due to the fact that tasks are constantly changing both in structure and in the number of variables (only one type of variables X, two types of variables X and Y, three types: X, Y, Z).
The difficulty of mastering these methods for solving problems is confirmed by the fact that on the website of K.Yu. Polyakov, there are 38 analyzes of this type of problem (4). Some analyzes provide more than one type of solution to a problem.
Lately in KIM Unified State Examination in computer science there are problems with two types of variables X and Y.
I have optimized the display method and encourage my students to use the improved method.
This gives results. The percentage of my students who cope with this task varies up to 43% of those passing. As a rule, every year from 25 to 33 people from all 11th grades take the Unified State Exam in computer science.
Before the advent of tasks with two types variable method The students used mappings very successfully, but after the appearance of Y in the logical expression, I began to notice that the children’s answers no longer coincided with the tests. It turned out that they were not quite clear on how to create a table of mappings with a new type of variable. Then the thought occurred to me that for convenience, the entire expression should be reduced to one type of variable, as is convenient for children.
I will give this technique in more detail. For convenience, I will consider it using the example of the system of logical expressions given in (4).
How many different solutions does the system have? logical equations
(x 1 ^ y 1)=(¬x 2 V ¬
y 2
)
(x 2 ^ y 2)= (¬
x 3
V ¬
y 3
)
...
(x 5 ^ y 5)
= (¬
x 6
V ¬
y 6
)
Solution:
1. From the analysis of the system of logical equations we see that there are 6 variables X and 6 variables U. Since any of these variables can take only two values (0 and 1), we replace these variables with 12 variables of the same type, for example Z.
2. Now let's rewrite the system with new variables of the same type. The difficulty of the task will be to take careful notes when replacing variables.
(z 1 ^ z 2)=
(¬z 3V¬
z 4
)
(z 3 ^ z 4)=
(¬
z 5
V¬
z 6
)
...
(z 9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Let’s build a table in which we’ll go through all the options z 1 , z 2 , z 3 , z 4 , since there are four variables in the first logical equation, the table will have 16 rows (16=2 4); remove such values from the table z 4 , for which the first equation has no solution (crossed out numbers).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Analyzing the table, we build a rule for displaying pairs of variables (for example, a pair Z 1 Z 2 =00 corresponds pair Z 3 Z 4 = 11) .
5. Fill out the table by calculating the number of pairs of variables for which the system has a solution. 
6. Add up all the results: 9 + 9 + 9 + 27 = 54
7. Answer: 54.
The above optimized method for solving problem 23 from the Unified State Exam KIM allowed students to regain confidence and successfully solve this type of problem.
Literature:
1. FIPI. Guidelines for teachers, prepared on the basis of analysis typical mistakes participants of the Unified State Exam 2015 in INFORMATION SCIENCE and ICT. Access mode: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, M.A. Roitberg.Systems of logical equations: solution using bit strings. Journal of Informatics, No. 12, 2014, p. 4-12. Publishing House"First of September", Moscow.3. E.A. Mironchik, Display method. Magazine Informatics, No. 10, 2013, p. 18-26. Publishing house "First of September", Moscow.
Solving systems of logical equations by changing variables
The method of substitution of variables 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 designated as a new variable.
Example 1.
How many different sets of values of the logical variables x1, x2, x3, x4, x5, x6, x7, x8 are there that satisfy all the conditions listed below?
(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, for 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 we can write the system in the form of a single equation:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. The conjunction is 1 (true) when each operand takes the value 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 the variables y1, y2, y3, y4, one should not be to the left of zero:
Those. the conditions are satisfied 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 – on three sets x1, x2: (0,0) , (0,1), (1.1). Likewise for y2, y3, y4.
Since each set (x1,x2) for the variable y1 is combined with each set (x3,x4) for the variable y2, etc., the numbers of sets of the variables x are multiplied:
|
Number of sets per x1…x8 |
||||
Let's add up the number of sets: 1 + 3 + 9 + 27 + 81 = 121.
Answer: 121
Example 2.
How many different sets of values of the logical variables x1, x2, ... x9, y1, y2, ... y9 are there that satisfy all the conditions listed below?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
In response no need list all the different sets of values of the variables x1, x2, ... x9, y1, y2, ... y9 for which the this system equals 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. There are two sets of solutions to this equation:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
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 a total of 2 9 +2 9 = 1024 sets.
Answer: 1024
Solving systems of logical equations by visually determining recursion.
This method is used if the system of equations is quite simple 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 logical variables?
The answer does not need to list all the different sets of values x1, x2, ... x10 for which this system of equalities is satisfied. 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 values of x2 (0 and 1), and for x1=1 there is only one value of x2 (1), such that the set (x1,x2) is a solution to the equation. There are 3 sets in total.
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 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 of (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 the logical variables x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 are there that satisfy all the conditions listed below?
(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 the different sets of values of the variables x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 for 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.
Let's look at the first equation. A conjunction is true (equal to 1) only if all its operands are true (equal to 1). The implication is 1 on all tuples except (1,0). This means that the solution to the first equation will be the following sets x1, x2, x3, x4, in which 1 is not located to the left of 0 (5 sets):
Similarly, the solutions to the second and third equations will be absolutely the same sets 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) are suitable, in which there is at least one zero: (0, 0), (0,1) , (1, 0).
|
Number of sets |
||||
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 when solving complex systems in which the order of increasing the number of sets is not obvious, and constructing a tree is impossible due to volumes.
Example 5.
How many different sets of values of the logical variables x1, x2, ... x7, y1, y2, ... y7 are there that satisfy all the conditions listed below?
(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 for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.
Solution:
Note that the first six equations of the system are identical and differ only in the set of variables. Let's look at the first equation. Its solution will be the following sets of variables:
Let's denote:
number of tuples (0,0) on variables (x1,y1) through A 1,
number of tuples (0,1) on variables (x1,y1) through B 1,
number of tuples (1,0) on variables (x1,y1) through C 1,
the number of tuples (1,1) on the variables (x1,y1) through D 1 .
number of tuples (0,0) on variables (x2,y2) through A 2,
number of tuples (0,1) on variables (x2,y2) through B 2,
number of tuples (1,0) on variables (x2,y2) through C 2,
the number of tuples (1,1) on the variables (x2,y2) through D 2 .
From the decision tree we see that
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Note that the set (0,0) on the variables (x2,y2) is obtained from the sets (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. A 2 =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 =B 1 +C 1 +D 1.
Arguing similarly, we note that C 2 =B 1 +C 1 +D 1. D2 = D1.
Thus, we obtain recurrent 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
| Sets | Designation. | Formula |
Number of sets |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
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
Municipal budgetary educational institution
"Average comprehensive school No. 18"
urban district of the city of Salavat of the Republic of Bashkortostan
Systems of logical equations
in Unified State Examination problems in computer science
Section "Fundamentals of Logic Algebra" in Unified State Exam assignments considered one of the most difficult and poorly solved. The average percentage of tasks completed on this topic is the lowest and is 43.2.
| Course section | Average percentage of completion by task groups |
| Encoding information and measuring its quantity | |
| Information Modeling | |
| Number systems | |
| Fundamentals of Logic Algebra | |
| Algorithmization and programming | |
| Fundamentals of information and communication technologies |
Based on the 2018 CMM specification, this block includes four tasks different levels difficulties.
| № tasks | Verifiable content elements | Task difficulty level |
| Ability to construct truth tables and logic circuits | ||
| Ability to search for information on the Internet | ||
| Knowledge of basic concepts and laws mathematical logic | ||
| Ability to construct and transform logical expressions |
Task 23 is high in difficulty level, therefore it has the lowest percentage of completion. Among prepared graduates (81-100 points) 49.8% completed the task, moderately prepared (61-80 points) completed 13.7%, the remaining group of students did not complete this task.
The success of solving a system of logical equations depends on knowledge of the laws of logic and on the precise application of methods for solving the system.
Let's consider solving a system of logical equations using 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 - 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. All equations included in the system are of the same type, and each equation includes four variables. Knowing x1 and y1, we can find all possible values of x2 and y2 that satisfy the first equation. Reasoning 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 to the first equation. This can be done in two ways: constructing a truth table, through reasoning and applying the laws of logic.
Truth table:
| x 1 y 1 | x 2 y 2 | (x 1 y 1) (x2 y2) | (x 1 x2) | (y 1 y2) | (x 1 x2) (y 1 y2) | |||||
Constructing a truth table is labor-intensive and time-inefficient, so we use the second method - logical reasoning. The product is equal to 1 if and only if each factor is equal to 1.
(x1 y1 ) (x2 y2 ))=1
(x1 x2 ) =1
(y1 y2 ) =1
Let's look at the first equation. The consequence is equal to 1 when 0 0, 0 1, 1 1, which means (x1 y1)=0 for (01), (10), then the pair (x2 y2 ) can be any (00), (01), (10), (11), and when (x1 y1) = 1, that is, (00) and (11) the pair (x2 y2) = 1 takes the same values (00) and (11). Let us 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 the 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 using reasoning we will find all possible pairs (x1,y1), (x2,y2) of the first equation.
(x1 (x2 y2 ))=1
(y1 y2 ) = 1
The solution to the second equation is the 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 create 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, let's exclude pair (10). We find total number solutions 1+7+0+34=42
3)(23.180) How many different solutions does a 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 using reasoning we will find all possible pairs (x1,x2), (x3,x4) of the first equation.
(x1 x2 ) (x3 x4 ) = 1
Let's exclude from the solution the pairs that in the sequence give 0 (1 0), these are the pairs (01, 00, 11) and (10).
Let's make connections between pairs (x1,x2), (x3,x4)
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, having first simplified each equation.
1. Variable replacement method.
Introducing new variables allows you to simplify the system of equations, reducing the number of unknowns.New variables must be independent of each other. After solving the simplified system, we must return to the original variables.
Let's consider the application of this method using 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: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Attention! Each of the 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 for 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=1 also has 2 roots. Let's arrange the number of roots on the decision tree:
To find the number of solutions of 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 difficulty of solving systems of logical equations lies in the cumbersomeness of a complete decision tree. The reasoning method allows you not to build the entire tree, but to understand how many branches it will have. Let's look at this method using specific examples.
Example 1. How many different sets of values of the logical variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all the conditions listed below?
(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 for which this 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 the third condition. Let's build a solution tree for the first and second equations.
To represent a solution tree for a system of the first and second equations, each branch of the first tree must be continued 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. Let's mark the number of branches of the tree on the first tree"y" , which satisfy the third equation:
Let us explain: to satisfy the third condition, when 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"y" . And only for one branch of the tree"X" (right) all branches of the tree fit"y". Thus, full tree The entire system contains 11 branches. Each branch represents one solution to the original system of equations. This means that the entire 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 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 : Let's simplify the system. Let's build a truth table for 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 coincide with x10. For the first equation to be equal to 1, the equality must be true(X1 ≡ X2)=1, i.e. x1 must match x2.
Let's build a solution 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 coincides with x3); for x10=0 and for x2=1 bracket(X2 ≡ X10)=0, which means the bracket (X2 ≡ X3) should be equal to 1 (i.e. x2 coincides with x3):
Reasoning in this way, we build 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 the logical variables x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 are there that satisfy all the conditions listed below?
(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 solution tree for the 1st equation:
Consider the second equation:
- When x1=0 : the second and third brackets will be equal to 0; for the first bracket to be equal to 1, y1=1, z1=1 (i.e. in this case - 1 solution)
- When x1=1 : the first bracket will be equal to 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 when y1=1 and z1=0 (i.e. in this case - 2 solutions).
Similarly for the remaining equations. Let us note the resulting number of solutions for each tree node:
To find out the number of solutions for each branch, multiply the resulting numbers separately for each branch (from left to right).
1 branch: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solution
Branch 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 =2 solutions
3rd branch: 1 ⋅ 1 ⋅ 2 ⋅ 2 =4 solutions
4th branch: 1 ⋅ 2 ⋅ 2 ⋅ 2 =8 solutions
5th branch: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 solutions
Let's add up the resulting numbers: there are 31 solutions in total.
Answer: 31.
3. Natural 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 the logical variables x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 are there that satisfy all the conditions listed below?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
Let's 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 next equation has 2 more roots than the previous one.
4 equation has 12 roots;
Equation 5 has 14 roots
Equation 8 has 20 roots.
Answer: 20 roots.
Sometimes the number of roots grows according to the Fibonacci law.
Solving a system of logical equations requires a creative approach.
J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, where J, K, L, M, N are logical variables?
Explanation.
The expression (N ∨ ¬N) is true for any N, therefore
J ∧ ¬K ∧ L ∧ ¬M = 0.
Let's apply negation to both sides of the logical equation and use De Morgan's law ¬ (A ∧ B) = ¬ A ∨ ¬ B. We get ¬J ∨ K ∨ ¬L ∨ M = 1.
A logical sum is equal to 1 if at least one of its constituent statements is equal to 1. Therefore, the resulting equation is satisfied by any combination of logical variables except the case when all quantities included in the equation are equal to 0. Each of the 4 variables can be equal to either 1 or 0, therefore all possible combinations are 2·2·2·2 = 16. Therefore, the equation has 16 −1 = 15 solutions.
It remains to note that the 15 solutions found correspond to any of the two possible values of the logical variable N, so the original equation has 30 solutions.
Answer: 30
How many different solutions does the equation have?
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (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 of J, K, L, M and N for which this equality holds. As an answer, you need to indicate the number of such sets.
Explanation.
We use the formulas A → B = ¬A ∨ B and ¬(A ∨ B) = ¬A ∧ ¬B
Let's consider the first subformula:
(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)
Let's consider the second subformula
(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L
Let's consider the third subformula
1) M → J = 1 therefore,
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;
(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;
Let's combine:
¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 hence 4 solutions.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L
Let's combine:
K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L hence 4 solutions.
c) M = 0 J = 0.
(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.
(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.
Answer: 4 + 4 = 8.
Answer: 8
How many different solutions does the equation have?
((K ∨ L) → (L ∧ M ∧ N)) = 0
where K, L, M, N are logical variables? The Answer does not need to list all the different sets of values of K, L, M and N for which this equality holds. As an Answer you need to indicate the number of such sets.
Explanation.
Let's rewrite the equation using simpler notation for operations:
((K + L) → (L M N)) = 0
1) from the truth table of the “implication” operation (see the first problem) it follows that this equality is true if and only if at the same time
K + L = 1 and L M N = 0
2) from the first equation it follows that at least one of the variables, K or L, is equal to 1 (or both together); so let's consider three cases
3) if K = 1 and L = 0, then the second equality holds for any M and N; since there are 4 combinations of two Boolean variables (00, 01, 10 and 11), we have 4 different solutions
4) if K = 1 and L = 1, then the second equality holds for M · N = 0; there are 3 such combinations (00, 01 and 10), we have 3 more solutions
5) if K = 0, then L = 1 (from the first equation); in this case, the second equality is satisfied when M · N = 0; there are 3 such combinations (00, 01 and 10), we have 3 more solutions
6) in total we get 4 + 3 + 3 = 10 solutions.
Answer: 10
How many different solutions does the equation have?
(K ∧ L) ∨ (M ∧ N) = 1
Explanation.
The expression is true in three cases, when (K ∧ L) and (M ∧ N) are equal to 01, 11, 10, respectively.
1) "01" K ∧ L = 0; M ∧ N = 1, => M, N are equal to 1, and K and L are anything except simultaneously 1. Therefore, there are 3 solutions.
2) "11" K ∧ L = 1; M ∧ N = 1. => 1 solution.
3) "10" K ∧ L = 1; M ∧ N = 0. => 3 solutions.
Answer: 7.
Answer: 7
How many different solutions does the equation have?
(X ∧ Y ∨ Z) → (Z ∨ P) = 0
where X, Y, Z, P are logical variables? The answer does not need to list all the different sets of values for which this equality holds. As an answer, you only need to indicate the number of such sets.
Explanation.
(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>
¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;
(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;
Logical OR is false only in one case: when both expressions are false.
Hence,
(Z ∨ P) = 0 => Z = 0, P = 0.
¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>
¬X ∨ ¬Y = 0 => X = 1; Y = 1.
Therefore, there is only one solution to the equation.
Answer: 1
How many different solutions does the equation have?
(K ∨ L) ∧ (M ∨ N) = 1
where K, L, M, N are logical variables? The answer does not need to list all the different sets of values of K, L, M and N for which this equality holds. As an answer, you only need to indicate the number of such sets.
Explanation.
Logical And is true only in one case: when all expressions are true.
K ∨ L = 1, M ∨ N = 1.
Each of the equations gives 3 solutions.
Consider the equation A ∧ B = 1 if both A and B accept true values in three cases each, then in total the equation has 9 solutions.
Therefore the answer is 9.
Answer: 9
How many different solutions does the equation have?
((A → B)∧ C) ∨ (D ∧ ¬D)= 1,
where A, B, C, D are logical variables?
The answer does not need to list all the different sets of values A, B, C, D for which this equality holds. As an answer, you need to indicate the number of such sets.
Explanation.
Logical "OR" is true when at least one of the statements is true.
(D ∧ ¬D)= 0 for any D.
Hence,
(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, which gives us 3 possible solutions for each D.
(D ∧ ¬ D)= 0 for any D, which gives us two solutions (for D = 1, D = 0).
Therefore: total solutions 2*3 = 6.
Total 6 solutions.
Answer: 6
How many different solutions does the equation have?
(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0
where K, L, M, N are logical variables? The answer does not need to list all the different sets of values of K, L, M and N for which this equality holds. As an answer, you only need to indicate the number of such sets.
Explanation.
Let's apply negation to both sides of the equation:
(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1
Logical OR is true in three cases.
Option 1.
K ∧ L ∧ M = 1, then K, L, M = 1, and ¬L ∧ M ∧ N = 0. N is arbitrary, that is, 2 solutions.
Option 2.
¬L ∧ M ∧ N = 1, then N, M = 1; L = 0, K any, that is, 2 solutions.
Therefore the answer is 4.
Answer: 4
A, B and C are integers for which the statement is true
¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).
What is B equal to if A = 45 and C = 43?
Explanation.
1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);
2) these simple statements are connected by the operation ∧ (AND, conjunction), that is, they must be executed simultaneously;
3) from ¬(A = B)=1 it immediately follows that A B;
4) suppose that A > B, then from the second condition we obtain 1→(B > C)=1; this expression can be true if and only if B > C = 1;
5) therefore we have A > B > C, only the number 44 corresponds to this condition;
6) just in case, let’s also check option A 0 →(B > C)=1;
this expression is true for any B; now look at the third condition we get
this expression can be true if and only if C > B, and here we have a contradiction, because there is no such number B for which C > B > A.
Answer: 44.
Answer: 44
Construct a truth table for a logical function
X = (A ↔ B) ∨ ¬(A → (B ∨ C))
in which the column of values of argument A is the binary representation of the number 27, the column of values of argument B is the number 77, the column of values of argument C is the number 120. The number in the column is written from top to bottom from the most significant to the least significant (including the zero set). Convert the resulting binary representation of the values of function X to the decimal number system.
Explanation.
Let's write the equation using simpler notation for operations:
1) this is an expression with three variables, so there will be lines in the truth table; therefore, the binary representation of the numbers used to construct table columns A, B and C must consist of 8 digits
2) convert the numbers 27, 77 and 120 into the binary system, immediately adding up to 8 digits of zeros at the beginning of the numbers
3) it is unlikely that you will be able to immediately write the values of the X function for each combination, so it is convenient to add additional columns to the table to calculate intermediate results (see table below)
| A | IN | WITH | X|
| 0 | 0 | ||
| 0 | 1 | 1 | |
| 0 | 0 | 1 | |
| 1 | 0 | 1 | |
| 1 | 1 | 1 | |
| 0 | 1 | 0 | |
| 1 | 0 | 0 | |
| 1 | 1 | 0 |
4) fill in the table columns:
| A | IN | WITH | X | ||||
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
the value is 1 only in those lines where A = B
the value is 1 in those lines where either B or C = 1
the value is 0 only in those lines where A = 1 and B + C = 0
the value is the inverse of the previous column (0 is replaced by 1, and 1 is replaced by 0)
the result of X (last column) is the logical sum of the two columns and
5) to get the answer, write out the bits from column X from top to bottom:
6) convert this number to the decimal system:
Answer: 171
What is the largest integer X for which the statement (10 (X+1)·(X+2)) is true?
Explanation.
An equation is an operation of implication between two relations:
1) Of course, here you can apply the same method as in example 2208, but you will need to solve quadratic equations(I do not want…);
2) Note that by condition we are only interested in integers, so we can try to somehow transform the original expression, obtaining an equivalent statement ( exact values we are not interested in roots at all!);
3) Consider the inequality: obviously, it can be either a positive or a negative number;
4) It is easy to check that in the domain the statement is true for all integers , and in the domain - for all integers (in order not to get confused, it is more convenient to use non-strict inequalities, and , instead of and );
5) Therefore, for integers it can be replaced by an equivalent expression
6) the domain of truth of an expression is the union of two infinite intervals;
7) Now consider the second inequality: it is obvious that it can also be either a positive or a negative number;
8) In the domain the statement is true for all integers , and in the domain - for all integers , therefore for integers it can be replaced by an equivalent expression
9) the domain of truth of the expression is a closed interval;
10) The given expression is true everywhere, except for areas where and ;
11) Please note that the value is no longer suitable, because there and , that is, the implication gives 0;
12) When substituting 2, (10 (2+1) · (2+2)), or 0 → 0 which satisfies the condition.
So the answer is 2.
Answer: 2
What is the largest integer X for which the statement is true
(50 (X+1)·(X+1))?
Explanation.
Let's apply the implication transformation and transform the expression:
(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).
Logical OR is true when at least one logical statement is true. Having solved both inequalities and taking into account that we see that the largest integer for which at least one of them is satisfied is 7 (in the figure, the positive solution of the second inequality is shown in yellow, and the first in blue).
Answer: 7
Indicate the values of the variables K, L, M, N, at which the logical expression
(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)
false. Write the answer as a string of 4 characters: the values of the variables K, L, M and N (in that order). So, for example, line 1101 corresponds to the fact that K=1, L=1, M=0, N=1.
Explanation.
Duplicates task 3584.
Answer: 1000
(¬K ∨ M) → (¬L ∨ M ∨ N)
Explanation.
Let's apply the implication transformation:
(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0
Let's apply negation to both sides of the equation:
(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1
Let's transform:
(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1
Therefore, M = 0, N = 0, now consider (¬K ∧ L ∨ M ∧ L):
from the fact that M = 0, N = 0 it follows that M ∧ L = 0, then ¬K ∧ L = 1, that is, K = 0, L = 1.
Answer: 0100
Specify the values of the variables K, L, M, N for which the logical expression
(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)
false. 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 the fact that K=1, L=1, M=0, N=1.
Explanation.
Let's write the equation using simpler notation of operations (the condition “the expression is false” means that it is equal to logical zero):
1) from the formulation of the condition it follows that the expression must be false only for one set of variables
2) from the truth table of the operation “implication” it follows that this expression is false if and only if at the same time
3) the first equality (the logical product is equal to 1) is satisfied if and only if and ; from this it follows (the logical sum is equal to zero), which can only happen when ; Thus, we have already defined three variables
4) from the second condition, , for and we obtain .
Duplicates the task
Answer: 1000
Specify the values of the logical variables P, Q, S, T, at which the logical expression
(P ∨ ¬Q) ∨ (Q → (S ∨ T)) is false.
Write the answer as a string of four characters: the values of the variables P, Q, S, T (in that order).
Explanation.
(1) (P ∨ ¬Q) = 0
(2) (Q → (S ∨ T)) = 0
(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.
(2) (Q → (S ∨ Т)) = 0 Let us apply the implication transformation:
¬Q ∨ S ∨ T = 0 => S = 0, T = 0.
Answer: 0100
Specify the values of the variables K, L, M, N for which the logical expression
(K → M) ∨ (L ∧ K) ∨ ¬N
false. 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 the fact that K=1, L=1, M=0, N=1.
Explanation.
Logical OR is false if and only if both statements are false.
(K → M) = 0, (L ∧ K) ∨ ¬N = 0.
Let's apply the implication transformation for the first expression:
¬K ∨ M = 0 => K = 1, M = 0.
Consider the second expression:
(L ∧ K) ∨ ¬N = 0 (see the result of the first expression) => L ∨ ¬N = 0 => L = 0, N = 1.
Answer: 1001.
Answer: 1001
Specify the values of the variables K, L, M, N for which the logical expression
(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))
true. 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 the fact that K=1, L=1, M=0, N=1.
Explanation.
Logical "AND" is true if and only if both statements are true.
1) (K → M) = 1 Apply the implication transformation: ¬K ∨ M = 1
2) (K → ¬M) = 1 Apply the implication transformation: ¬K ∨ ¬M = 1
It follows that K = 0.
3) (¬K → (M ∧ ¬L ∧ N)) = 1 Apply the implication transformation: K ∨ (M ∧ ¬L ∧ N) = 1 from the fact that K = 0 we obtain:
M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.
Answer: 0011
It is known that for integers X, Y and Z the following statement is true:
(Z What is Z equal if X=25 and Y=48?
Explanation.
After substituting the numbers, we get that Z = 47.
Please note that this complex statement consists of three simple ones
1) (Z 2) these simple statements are connected by the operation ∧ (AND, conjunction), that is, they must be executed simultaneously.
3) from ¬(Z+1 24, and from ¬(Z+1 47.
4) from (Z Z Answer: 47.
Answer: 47
A, B and C are integers for which the following statement is true:
(C What is the value of C if A=45 and B=18?
Explanation.
Logical "AND" is true if and only if both statements are true.
Let's substitute the numbers into the expression:
1) (C (C 2) ¬(C+1, C ≥ 44.
3) ¬(C+1, C ≥ 17.
From 2) and 1) it follows that C
Answer: 44
¬(A = B) ∧ ((B A)) ∧ ((A 2C))
What is the value of A if C = 8 and B = 18?
Explanation.
Logical "AND" is true if and only if both statements are true.
1) ¬(A = B) = 1, that is, A ≠ 18 = 1.
2) ((B A)) Apply the implication transformation: (18 > A) ∨ (16 > A) = 1
3) (A 2C) Apply the implication transformation: (A > 18) ∨ (A > 16) = 1
From 2) and 3) it follows that (18 > A) and (A > 16), since otherwise a contradiction arises: A = 17.
Answer: 17
A, B and C are integers for which the statement is true
¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))
What is the value of B if A = 45 and C = 18?
Explanation.
Logical "AND" is true only if all statements are true.