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 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 methodology 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 COMPUTER 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.
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, the complete tree of 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.
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 denoted by 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 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 given system of equalities is satisfied. As an answer, you need to indicate the number of such sets.
Solution:
Let's make a change of variables:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
The system can be written as a single equation:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Equivalence is true only if both operands are equal. 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 using the method of visual determination of 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 this 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
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.
Lesson topic: Solving Logic Equations
Educational – studying methods for solving logical equations, developing skills in solving logical equations and constructing a logical expression using a truth table;Developmental - create conditions for development cognitive interest students, promote the development of memory, attention, logical thinking;
Educational : promote the ability to listen to the opinions of others, nurturing the will and perseverance to achieve final results.
Lesson type: combined lesson
Equipment: computer, multimedia projector, presentation 6.
During the classes
Repetition and updating of basic knowledge. Examination homework(10 minutes)
In previous lessons, we became acquainted with the basic laws of logical algebra and learned to use these laws to simplify logical expressions.
Let's check our homework on simplifying logical expressions:
1. Which of the following words satisfies the logical condition:
(first letter consonant→second letter 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 following notation:
A – first letter consonant
B – second letter consonant
S – last letter vowel
D – penultimate vowel letter
Let's make an expression:
Let's make a table:
2. Indicate which logical expression is equivalent to the expression
Let's simplify the recording of the original expression and the proposed options:
3. Given a fragment of the truth table of expression F:
Which expression matches F?
Let us determine the values of these expressions for the specified values of the arguments:
Introduction to 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 is “Solving Logical Equations.” After studying this topic, you will learn the basic ways of solving logical equations, gain the skills to solve these equations by using the language of logical algebra and the ability to compose a logical expression using a truth table.
1. Solve a logic 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 the fact that K=1, L=1, M=0, N=1.
Solution:
Let's transform the expression(¬K M) → (¬L M N)
An 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: drawing up a truth table
3 way: construction of a 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 obtain the disjunction of 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:
Let's take into account the same conjunctions:
As a result, we obtain an SDNF containing 9 conjunctions. Therefore, the truth table for this function has the value 1 in 9 rows 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
Let's take into account the same conjunctions:
As a result, we obtain an SDNF containing 5 conjunctions. Therefore, the truth table for this function has the value 1 on 5 rows of 2 4 =16 sets of variable values.
Constructing a logical expression using a truth table:
for each row of the truth table containing 1, we compose a product of arguments, and variables equal to 0 are included in the product with negation, and variables equal to 1 are included without negation. The desired expression F will be composed of the sum of the resulting products. Then, if possible, this expression should be simplified.
Example: a truth table of an expression is given. Construct a logical expression.
Solution:3. Homework (5 minutes)
Solve the equation:
How many solutions does the equation have (indicate only the number in your answer)?
Using a given truth table, construct a logical expression and
simplify it.
