Solution of the equation 1. Go to the prefix form of writing the equation, replacing the symbols of negations with ¬ 2. Construct the title of a truth table of a special type 3. Fill in the rows of the truth table for all combinations of A and B, substituting 0 or 1 instead of X. 4. Generate a truth table for X = F (A,B) 5. Using the truth table, determine the type of function X, if necessary, using the methods of constructing SCNF and SDNF, which will be discussed below.
Construction of a truth table of a special form ¬((A+B)·(X A·B))=¬(B+¬(X A))
Truth table X=F(A, B) ABX Corresponds to the negation of implication B in A ANSWER:
Combinational circuits of logical devices Basic elements (GOST): 1 A B Disjunction A B Equivalence & A B Conjunction M2 A B XOR
Combinational circuits of logic devices Basic elements (GOST): 1 A B Implication & A B Schaeffer element & A B Coimplication 1 A B Webb element
Example circuit F 1 & 1 & & 1M2 B A
Solving circuits 1 Option - converting a circuit into a complex logical expression and then simplifying it according to the laws of logic. Option 2 – construction of a truth table and then, if necessary, construction through SKNF or SDNF (see below). Let's consider the second option, as it is simpler and more understandable.
Construction of the truth table AB A + B + · B B · A + A B A + · ·
Truth table F(A, B) ABX Corresponds to the negation of the implication B in A ANSWER:
SDNF and SKNF (definitions) An elementary conjunction is a conjunction of several variables, taken with or without negation, and among the variables there may be identical ones. An elementary disjunction is called a disjunction of several variables, taken with or without negation, and among the variables there may be identical ones. Any disjunction of elementary conjunctions Let's call it a disjunctive normal form (DNF) Let's call any conjunction of elementary disjunctions a conjunctive normal form (DNF)
SDNF and SCNF (definitions) A perfect disjunctive normal form (PDNF) is called a DNF in which there are no identical elementary conjunctions and all conjunctions consist of the same set of variables, in which each variable appears only once (possibly with negation). A perfect conjunctive normal form (PCNF) is a CNF in which there are no identical elementary disjunctions and all disjunctions consist of the same set of variables, in which each variable appears only once (possibly with negation).
Algorithm for obtaining SDNF from the truth table 1. Mark the rows of the truth table in the last column of which there are 1. 2. Write down for each marked row the conjunction of all variables as follows: if the value of a variable in a given row is 1, then include this variable itself in the conjunction, if equals 0, then its negation. 3. Link all the resulting conjunctions into a disjunction. Algorithm for obtaining SCNF from the truth table 1. Mark the rows of the truth table in the last column of which there are 0. 2. Write out for each marked row the disjunction of all variables as follows: if the value of a variable in a given row is 0, then include this variable itself in the conjunction, if equals 1, then its negation. 3. Link all the resulting disjunctions into a conjunction.
Example of constructing SKNF XY F(X,Y) Mark zeros 2. Disjunctions: X + Y 3. Conjunction: (X + Y) · (X + Y)
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
Solving systems of logical equations using tabular methods by transforming logical expressions.This technique is based on the use of truth tables and is designed for students who know how to convert logical expressions. If students are not fluent in these methods, they can be used without transformations. (We will use transformations). To master this method of solution, it is imperative to know the properties of basic logical operations: conjunction, disjunction, inversion, implication and equivalence.
Algorithm for solving systems of equations using this method:
Transform the logical equation and simplify it.
Determine the sequence of solving equations in the system, since in most cases there is a sequential solution of equations from top to bottom (as they are located in the system), but there are options when it is more convenient and easier to start solving from bottom to top.
Build a table of variables where you can set the initial values of the first variable (or the last).
Consistently write down the possible options for the following variable when everyone meaning of the first.
After solving the previous equation, moving on to the next one, be sure to pay attention to what variables are used in the previous and subsequent equations, since the values of the variables obtained when solving the previous equations are passed on as options for the following equations.
Pay attention to the resulting quantities of the solution when moving to the next variable, because a pattern in the increase in decisions can be identified.
Example 1.
¬ X1 ˅ X2=1
¬ X2 ˅ X3=1
¬ X3 ˅ X4=1
¬ X9 ˅ X10=1
Let's start with X1 and see what values this variable can take: 0 and 1.
Then we will consider each of these values and see what X2 can be.
Answer: 11 solutions
Example 2.
( X1X2)˅(¬X1˄¬X2) ˅( X1↔ X3)=1
( X2˄X3)˅(¬X2˄¬X3) ˅( X2↔ X4)=1
(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0
Let's transform using the formula (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B
We get:
( X1↔ X2) ˅ (X1↔ X3) =1
( X2↔ X3) ˅ (X2↔ X4) =1
( X8↔ X9 (X8↔ X10) =0
For X1 =0 - 8 solutions
Let's take X1=1 and see what value X2 can take. Now for each X2 we will consider what values X3 can take, etc.
For X1=1 – 8 solutions
Total 8+8=16 solutions
Answer. 16 solutions
Example 3 .
¬ ( X1↔ X2) ˄ ( X1X3) ˄ (¬X1˅¬X3 )=0
¬ ( X2↔ X3) ˄ (X2 ˅X4) ˄ (¬X2˅¬X4)=0
….
¬ ( X8↔ X9 (X8X10) ˄ (¬X8˅¬X10)=0
After transformations (A˅ B) ˄(¬ A ˅¬ B)= ¬( A ↔ B)
we get:
¬ ( X1↔ X2) ˄ ¬ (X1↔ X3)=0
¬ ( X2↔ X3) ˄ ¬ (X2↔ X4)=0
…..
¬ ( X8↔ X9) ˄ ¬ (X8↔ X10)=0
Let's take X1=0 and see what value X2 can take. Now for each X2 we will consider what values X3 can take, etc.
We got 10 solutions for X1=0
Let's do the same for X1=1. We also get 10 solutions
Total:10+10=20
Answer: 20 solutions.
Example 4.
(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1
(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1
….
(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0
Let's convert using formulas. (A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B. We get:
(X1↔ X2) ˅ (X2↔ X3)=1
(X2↔ X3) ˅ (X3↔ X4)=1
(X3↔ X4) ˅ (X4↔ X5)=1
(X4↔ X5) ˅ (X5↔ X6)=1
(X5↔ X6) ˅ (X6↔ X7)=1
(X6↔ X7) ˅ (X7↔ X8)=1
(X7↔ X8) ˅ (X8↔ X9)=1
(X8↔ X9) ˅ (X9↔ X10)=0
Let's start from the end, because in the last equation the variables are determined uniquely.
Let X10=0, then X9=1, X8=0, X7=0, X6=0, and the following variables can take different values. We will consider each.
Total 21 solutions for X10=0
Now consider for X10=1. We also get 21 solutions
Total:21+21=42
Answer: 42 solutions
Example 5.
( X1X2) ˅ (¬X1 ˄ ¬X2) ˅ (¬X3 ˄X4 (X3 ˄ ¬X4)=1
( X3 ˄X4) ˅ (¬X3 ˄ ¬X4) ˅ (¬X5X6) ˅ (X5˄¬X6)=1
( X5X6) ˅ (¬X5˄¬X6) ˅ (¬X7˄X8 (X7˄¬X8)=1
( X7˄X8) ˅ (¬X7˄¬X8) ˅ (¬ X9X10 (X9˄¬X10) =1
Let's transform according to the formulas:(¬ A ˄ B) ˅ ( A ˄ ¬ B)= A↔ ¬ B
( A˄ B)˅ (¬ A ˄ ¬ B)= A↔ B
( X1↔ X2) ˅ (X3 ↔ ¬X4)=1
( X3↔ X4 (X5 ↔ ¬X6)=1
( X5↔ X6) ˅ (X7 ↔ ¬X8)=1
( X7↔ X8 (X9 ↔ ¬X10)=1
Let's consider what values X1 and X2 can take: (0,0), (0,1), (1,0), (1,1).
Let's consider each option and see what values X3, X4 can take.
Starting from X7, X8, we will immediately write down the number of solutions, since it is immediately clear that when the values are the same (1,1) and (0,0), then the following variables have 4 solutions, and when they are different (0,1) and (1 ,0) – 2 solutions.
Total: 80+80+32=192
Answer: 192 solutions
Example 6.
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Let's take X1=0 and see what value X2 can take. Now for each X2 we will consider what values X3 can take, etc.
We see a certain pattern: The number of subsequent solutions is equal to the sum of the previous two.
The same for X1=1 we get 89 solutions
Total: 89+89=178 solutions
Answer: 178 solutions
Let's solve it one more way
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Let's introduce the replacement:
T 1 =(X1↔X2)
T 2 =(X2↔X3)
T 3 =(X3↔X4)
T 4 =(X4↔X5)
T 5 =(X5↔X6)
T 6 =(X6↔X7)
T 7 =(X7↔X8)
T 8 =(X8↔X9)
T 9 =(X9↔X10)
We get:
T1T2=1
T2 ˅T3=1
T3˅T4=1
T4T5=1
T5T6=1
T6˅T7=1
T7˅T8=1
T8T9=1
T9T10=1
Let's takeT1=1 and use the properties of disjunction:
BUT Let us remember that
T 1 =(X1↔X2)
T 2 =(X2↔X3), etc.
Let's use the equivalence property and make sure, looking at the table, that
When T = 1, then two solutions are obtained. And when =0 there is one solution.
Therefore, we can count the number of ones and multiply them by 2+ the number of zeros. Counting, also using a pattern.
It turns out that the number of ones = the previous total number of solutions T, and the number of zeros is equal to the previous number of ones
So. We'll get it. Since one gives two solutions, then 34 * 2 = 68 solutions from one + 21 solutions from 0.
Total 89 solutions for T=1. In a similar way we obtain 89 solutions for T=0
Total 89+89=178
Answer: 178 solutions
Example 7.
(X1 ↔ X2) ˅ (X3↔ X4) ˄ ¬(X1 ↔ X2) ˅ ¬(X3↔ X4)=1
(X3 ↔ X4 (X5↔ X6) ˄ ¬(X3 ↔ X4) ˅ ¬(X5↔ X6)=1
(X5 ↔ X6) ˅ (X7↔ X8) ˄ ¬(X5 ↔ X6) ˅ ¬(X7↔ X8)=1
(X7 ↔ X8 (X9↔ X10) ˄ ¬(X7 ↔ X8) ˅ ¬(X9↔ X10)=1
Let's introduce the replacement:
T1=(X1 ↔ X2)
T2=(X3↔ X4)
T3=(X5↔ X6)
T4=(X7 ↔ X8)
T5=(X9↔ X10)
We get:
(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1
(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1
(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1
(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1
Let's consider what Ts can be:
T1
T2
T3
T4
T5
Total
0
1
0
1
0
32
1
0
1
0
1
32
T K ≠T K+1 I T K =T K+2
We get: 2 5 =32 for T
Total: 32+32=64
Answer: 64 solutions.
Municipal budgetary educational institution
"Secondary school No. 18"
urban district of the city of Salavat of the Republic of Bashkortostan
Systems of logical equations
in Unified State Examination problems in computer science
The section “Fundamentals of Algebra of Logic” in the Unified State Examination tasks is considered one of the most difficult and difficult to solve. 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 KIM specification, this block includes four tasks of different difficulty levels.
| № 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 graduates (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: construct a truth table, through reasoning and the application of 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). Find the total number of 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 us 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)
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 the development of students’ cognitive interest, promote the development of memory, attention, and 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. Checking 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.