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 KIM Unified State Examination in Informatics 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 pedagogical 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 appearance of problems with two types of variables, students used the mapping method 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 various solutions has a system of 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 an analysis of typical mistakes made by participants in the 2015 Unified State Exam 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.
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 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 is satisfied 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 equation gives 3 solutions.
Consider the equation A ∧ B = 1, if both A and B take 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 we look at the third condition and 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 (we are not at all interested in the exact values of the roots!);
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 region, the statement is true for all integers, and in the region - 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 at 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 “implication” operation 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 ∨ Т)) = 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 at 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 at 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.
You can select various ways solving systems of logical equations. This is reduction to one equation, construction of a truth table and decomposition.
Task: Solve a system of logical equations:
Let's consider reduction method to one equation . This method involves transforming logical equations so that their right-hand sides are equal to the truth value (that is, 1). To do this, use the logical negation operation. Then, if the equations contain complex logical operations, 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 this, you should transform the resulting equation based on the laws of logical algebra and get specific solution systems.
Solution 1: Apply inversion to both sides of the first equation:
Let’s imagine the implication through the basic operations “OR” and “NOT”:
Since the left sides of the equations are equal to 1, we 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 obtained:
The resulting equation has one solution: A =0, B=0 and C=1.
The next method is constructing truth tables . Since logical quantities have only two values, you can simply go through all the options and find among them those for which a given system of equations is satisfied. That is, we are building one general table truth for all equations of the system and find the line with the required values.
Solution 2: Let's create a truth table for the system:
|
0 |
0 |
1 |
1 |
0 |
1 |
The line for which the task conditions are met is highlighted in bold. So A=0, B=0 and C=1.
Way decomposition . The idea is to fix the value of one of the variables (set 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 - C = 1. Solution of the system: A = 0, B = 0 and C = 1.
In the Unified State Exam 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 isreplacing variables. First, you need to simplify each of the equations as much as possible based on the laws of logical algebra, and then replace the complex parts of the equations with new variables and determine the number of solutions new system. Next, return to the replacement and determine the number of solutions for it.
Task: How many solutions does the equation (A →B) + (C →D) = 1 have? Where A, B, C, D are logical variables.
Solution: Let's introduce new variables: X = A →B and Y = C →D. Taking into account new variable 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 implications, 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 parameters of the original equation. So, total possible solutions of this equation 3+9=15.
The next way to determine the number of solutions to a system of logical equations is binary tree. Let's consider this method For example.
Task: How many different solutions does the system of logical equations have:
The given system of equations is equivalent to the equation:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Let's pretend that x 1 – is true, then from the first equation we obtain 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 a solution to the system. Let it 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 remaining variables are also true, that is, the set (0; 1; ...; 1) is a solution to the system. At x 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, each solution contains m values of the variables):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
This approach is well illustrated by constructing 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.
|
Tree |
Number of solutions |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
In case of difficulties in reasoning research and constructionof solutions you can search for a solution with using truth tables, for one or two equations.
Let's rewrite the system of equations in the form:
And let’s create a truth table separately for one equation:
|
x 1 |
x 2 |
(x 1 → x 2) |
Let's create a truth table for two equations:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |
Methods for solving systems of logical equations
Kirgizova E.V., Nemkova A.E.
Lesosibirsk Pedagogical Institute –
branch of Siberian Federal University, Russia
The ability to think consistently, reason convincingly, build hypotheses, and refute negative conclusions does not come on its own; this skill is developed by the science of logic. Logic is a science that studies methods for 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. Testing the development of skills to apply one's knowledge in a new situation is carried out through passing. In particular, this is the ability to decide logic problems. Tasks B15 in the Unified State Examination are tasks of increased complexity, since they contain systems of logical equations. There are various ways to solve systems of logical equations. This is reduction to one equation, construction of a truth table, decomposition, sequential solution of equations, etc.
Task:Solve a system of logical equations:
Let's consider reduction method to one equation . This method involves transforming logical equations so that their right-hand sides are equal to the truth value (that is, 1). To do this, use the logical negation operation. Then, if the equations contain complex logical operations, 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 this, you should transform the resulting equation based on the laws of logical algebra and obtain a specific solution to the system.
Solution 1:Apply inversion to both sides of the first equation:
Let’s imagine the implication through the basic operations “OR” and “NOT”:
Since the left sides of the equations are equal to 1, we 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 obtained:
The resulting equation has one solution: A= 0, B =0 and C =1.
The next method is constructing truth tables . Since logical quantities have only two values, you can simply go through all the options and find among them those for which a 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 required values.
Solution 2:Let's create a truth table for the system:
|
0 |
0 |
1 |
1 |
0 |
1 |
The line for which the task conditions are met is highlighted in bold. So A =0, B =0 and C =1.
Way decomposition . The idea is to fix the value of one of the variables (set 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 – C=1. Solution of the system: A = 0, B = 0 and C = 1.
You can also use the method sequential solution of equations , at each step adding one variable to the set under consideration. To do this, it is necessary to transform the equations so 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:
From the first equation it follows that 
, so when A = 0 and 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.
Let us depict the second equation, from which we determine the values of C for each option. When 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 obtained the solution to the system: A = 0, B = 0 and C = 1.
In the Unified State Exam 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 replacing variables. First, you need to simplify each of the equations as much as possible based on the laws of logical algebra, and then replace the complex parts of the equations with new variables and determine the number of solutions to the new system. Next, return to the replacement and determine the number of solutions for it.
Task:How many solutions does the equation have ( A → B ) + (C → D ) = 1? Where A, B, C, D are logical 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 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 parameters of the original equation. This means that the total possible solutions to this equation are 3+9=15.
The next way to determine the number of solutions to a system of logical equations is binary tree. Let's look at this method using an example.
Task:How many different solutions does the system of logical equations have:
The given system of equations is equivalent to the equation:
( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.
Let's pretend thatx 1 – is true, then from the first equation we obtain thatx 2 also true, from the second -x 3 =1, and so on until x m= 1. So the set (1; 1; …; 1) of m units is the solution of the system. Let it nowx 1 =0, then from the first equation we havex 2 =0 or x 2 =1.
When x 2 true, we obtain that the remaining variables are also true, that is, the set (0; 1; ...; 1) is a solution to 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 constructing 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 m +1.
|
Variables |
Tree |
Number of solutions |
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
In case of difficulties in reasoning and building a decision tree, you can search for a solution using truth tables, for one or two equations.
Let's rewrite the system of equations in the form:
And let’s create a truth table separately for one equation:
|
x 1 |
x 2 |
(x 1 → x 2) |
Let's create a truth table for two equations:
|
x 1 |
x 2 |
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). A 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 at a time, 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 is required that the assumption is correct.
To summarize all of the above, I would like to draw your attention to the fact that not all of the methods discussed are universal. When solving each system of logical equations, one should take into account its features, on the basis of which the solution method should be chosen.
Literature:
1. Logical problems / O.B. Bogomolov – 2nd ed. – M.: BINOM. Laboratory of Knowledge, 2006. – 271 p.: ill.
2. Polyakov K.Yu. Systems of logical equations / Educational and methodological newspaper for computer science teachers: Informatics No. 14, 2011.
The use of equations is widespread in our lives. They are used in many calculations, construction of structures and even sports. Man used equations in ancient times, and since then their use has only increased. In mathematics, there are certain problems that deal with propositional logic. To solve this kind of equation, you need to have a certain amount of knowledge: knowledge of the laws of propositional logic, knowledge of truth tables of logical functions of 1 or 2 variables, methods for converting logical expressions. In addition, you need to know the following properties of logical operations: conjunction, disjunction, inversion, implication and equivalence.
Any logical function of \variables - \can be specified by a truth table.
Let's solve several 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 this variable can take: 0 and 1. Next, we will consider each of the above values and see what \[X2.\] can be.
As can be seen from the table, our logical equation has 11 solutions.
Where can I solve a logic equation online?
You can solve the equation on our website https://site. Free online solver will allow you to solve online equations of any complexity in a matter of seconds. All you need to do is simply enter your data into the solver. You can also watch video instructions and learn how to solve the equation on our website. And if you still have questions, you can ask them in our VKontakte group http://vk.com/pocketteacher. Join our group, we are always happy to help you.
