Computer science how to solve equations with logical variables. Solving logical equations
Systems solution logical equations change of variables method
The change of variables method 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 logical variables x1, x2, x3, x4, x5, x6, x7, x8 are there that satisfy all of the following conditions?
(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, under 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 the system can be written as a single equation:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. The conjunction is 1 (true) when each operand evaluates to 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, the unit must not be to the left of zero:
Those. conditions are met 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 is achieved on three sets x1, x2: (0,0) , (0,1), (1.1). Similarly for y2, y3, y4.
Since each set (x1,x2) for variable y1 is combined with each set (x3,x4) for variable y2, and so on, the numbers of sets of variables x are multiplied:
Number of sets per x1…x8 |
||||
Let's add the number of sets: 1 + 3 + 9 + 27 + 81 = 121.
Answer: 121
Example 2
How many different sets of values of boolean variables x1, x2, ... x9, y1, y2, ... y9 are there that satisfy all of the following conditions?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
In response no need list all different sets of values of the variables x1, x2, ... x9, y1, y2, ... y9, under 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. The solutions to this equation will be two sets:
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 2 9 +2 9 = 1024 sets in total.
Answer: 1024
Solving systems of logical equations by visual definition of recursion.
This method is used if the system of equations is simple enough 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 boolean variables?
The answer does not need to enumerate all the different sets of values x1, x2, ... x10 for which the given system of equalities holds. 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 x2 values (0 and 1), and for x1=1, there is only one x2 value (1), such that the set (x1,x2) is the solution to the equation. Only 3 sets.
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 of 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 on (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 boolean variables x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 are there that satisfy all of the following conditions?
(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 different sets of values of the variables x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 , under 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.
Consider the first equation. A conjunction is true (equal to 1) only if all of its operands are true (equal to 1). The implication is 1 on all sets except (1,0). This means that the solution to the first equation will be such sets x1, x2, x3, x4, in which 1 is not to the left of 0 (5 sets):
Similarly, the solutions of the second and third equations will be exactly the same sets of 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) that contain at least one zero are suitable: (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 to solve complex systems in which the order of increasing the number of sets is not obvious, and building a tree is impossible due to volumes.
Example 5
How many different sets of values of boolean variables x1, x2, ... x7, y1, y2, ... y7 are there that satisfy all of the following conditions?
(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, under which the given system of equalities holds. As an answer, you need to indicate the number of such sets.
Solution:
Note that the first six equations of the system are the same and differ only in the set of variables. Consider the first equation. Its solution will be the following sets of variables:
Denote:
number of sets (0,0) on variables (x1,y1) through A 1 ,
number of sets (0,1) on variables (x1,y1) through B 1 ,
number of sets (1,0) on variables (x1,y1) via C 1 ,
number of sets (1,1) on variables (x1,y1) via D 1 .
number of sets (0,0) on variables (x2,y2) through A 2 ,
number of sets (0,1) on variables (x2,y2) via B 2 ,
number of sets (1,0) on variables (x2,y2) via C 2 ,
number of sets (1,1) on variables (x2,y2) via D 2 .
From the decision tree, we see that
A 1 =0, B 1 =1, C 1 =1, D 1 =1.
Note that the tuple (0,0) on the variables (x2,y2) is obtained from the tuples (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. A 2 \u003d 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 \u003d B 1 + C 1 + D 1.
Arguing similarly, we note that C 2 \u003d B 1 + C 1 + D 1. D2 = D1.
Thus, we obtain recursive 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 | Symbol. | Formula |
Number of sets |
||||||
i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
(0,0) | Ai | Ai+1 =Bi +Ci +Di | 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
At the end of the year, it turned out that only one of the three assumptions was true. Which departments made a profit at the end of the year?
Solution. Let us write the assumptions from the condition of the problem in the form of logical statements: “Receiving profit by division B is not necessary condition for getting
profits by unit A ":F 1 (A , B , C ) = A → B
“Receiving a profit by at least one department B and C is not sufficient for making a profit by department A”: F 2 (A , B , C ) = (B + C ) → A
"Divisions A and B will not profit at the same time": F 3 (A , B , C ) = A B
It is known from the condition that only one of the three assumptions is true. This means that we must find which of the following three logical expressions is not identically false:
1) F 1F 2F 3
2) F 1F 2F 3
3) F 1F 2F 3
1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0
2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C
3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0
Consequently, at the end of the year, the second assumption turned out to be true, and the first and third were false.
A=0 |
|||||||||
F1 F2 F3 = A B C= 1 |
|||||||||
if and only if B = 0 . |
|||||||||
C=1 |
Therefore, that division C will receive a profit, but divisions A and B will not receive a profit.
Solving logical equations
In the texts of the state centralized testing there is a task (A8), in which it is proposed to find the root of a logical equation. Let's look at how to solve such tasks with an example.
Find the root of the logical equation: (A + B )(X AB ) = B + X → A .
The first solution is to build a truth table. Let's build the truth tables of the right and left sides of the equation and see for what X , the values in the last columns of these tables will match.
F1 (A, B, X) = (A+ B)(X AB)
A+B | (A+B)(X AB) | F 1 (A ,B ,X ) |
|||||
F2 (A, B, X) = B + X → A
X→A | F 2 (A ,B ,X ) |
|||||||||
X→A | X→A |
|||||||||
Let's compare the obtained truth tables and select those rows in which the values F 1 (A , B , X ) and F 2 (A , B , X ) match.
F 1 (A ,B ,X ) | F 2 (A ,B ,X ) |
|||
We rewrite only the selected rows, leaving only the argument columns. Let's look at the variable X as a function of A and B .
It is obvious that X = B → A .
The second solution is to replace the equal sign in the equation with an equivalent sign, and then simplify the resulting logical equation.
To facilitate further work, we first simplify the right and left sides of the logical equation and find their negations:
F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B
F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B
F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A
Let's replace the equal sign in our logical equation with an equivalence sign:
F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +
+ (X A B+ X A B+ X A B) (B+ X A) =
= (X A B+ X B+ X A B) + (X A B+ X A B) =
Let's regroup the logical terms of this expression, taking the factors X and X out of the bracket.
X(A B) + X(B+ AB) = X(A B) + X(B+ A) =
Denote T = A B , then
X T+ X T= X↔ T.
Therefore, for a logical equation to have a solution: X = A B = B + A = B → A .
Logical elements of the computer. Construction of functional diagrams
Mathematical logic with the development of CT turned out to be in close relationship with the issues of design and programming computer science. The algebra of logic found wide application initially in the development of relay-contact schemes. The first fundamental research that drew the attention of engineers involved in the design of computers to the possibility of analyzing electrical circuits using Boolean algebra was published in December 1938 by the American Claude Shannon's article "Symbolic Analysis of Relay-Contact Circuits". After this article, the design of computers was not complete without the use of Boolean algebra.
Logic element is a circuit that implements the logical operations of disjunction, conjunction and inversion. Consider the implementation of logical elements through electrical relay-contact circuits, familiar to you from the school physics course.
Serial connection of contacts
Parallel connection of contacts
Let's make a table of dependences of the state of the circuits on all possible states of the contacts. Let's introduce the notation: 1 - the contact is closed, there is a current in the circuit; 0 - the contact is open, there is no current in the circuit.
Circuit status with | Circuit status with parallel |
||
serial connection | connection |
||
As you can see, a circuit with a serial connection corresponds to the logical operation of the conjunction, since the current in the circuit appears only when contacts A and B are closed simultaneously. A circuit with parallel connection corresponds to the logical operation disjunction, since there is no current in the circuit only at the moment when both contacts are open.
The logical operation of inversion is implemented through the contact circuit of an electromagnetic relay, the principle of which is studied in a school physics course. Contact x is open when x is closed and vice versa.
The use of relay-contact elements for constructing logic circuits of computers has not justified itself due to low reliability, large dimensions, high power consumption and low speed. The advent of electronic devices (vacuum and semiconductor) made it possible to build logic elements with a speed of 1 million switching per second and more. Logic elements on semiconductors operate in key mode, similar to an electromagnetic relay. The whole theory stated for contact circuits is transferred to semiconductor elements. Logical elements on semiconductors are characterized not by the state of the contacts, but by the presence of signals at the input and output.
Consider the logical elements that implement the basic logical operations:
Inverter - implements the operation of negation or inversion. At | |||||||||||||
inverter has one input and one output. The output signal appears | |||||||||||||
when it is not present at the input, and vice versa. | |||||||||||||
Conjunctor - | |||||||||||||
X1 X2 ... Xn | implements the conjunction operation. | At the conjunctor |
|||||||||||
one exit and at least two entrances. Signal on |
|||||||||||||
output appears if and only if |
|||||||||||||
all inputs are signaled. | |||||||||||||
X2 + ... Xn |
|||||||||||||
Disjunctor - implements the disjunction operation. At | |||||||||||||
disjunctor one output and at least two | |||||||||||||
The output signal does not appear if and only if, | |||||||||||||
when all inputs are not signaled. |
Build | functional |
||
F(X, Y, Z) = X(Y + Z) | |||
X+Z |
|||
diagram corresponding to the function:
& F(X, Y, Z)
Solving problems using the conjunctive-normal
and disjunctive-normal forms
AT In logical problem books, there are often standard problems where you need to write down a function that implements ladder diagram, simplify it and build a truth table for this function. How to solve the reverse problem? Given an arbitrary truth table, you need to build a functional or relay-contact circuit. We will deal with this issue today.
Any function of the algebra of logic can be represented by a combination of three operations: conjunction, disjunction and inversion. Let's see how it's done. To do this, we write down several definitions.
A minterm is a function formed by the conjunction of a certain number of variables or their negations. Minterm takes the value 1 for the only of all possible sets
arguments, and value 0 for all others. Example: x 1 x 2 x 3 x 4 .
Maksterm is a function formed by the disjunction of a certain number of variables or their negations. Maxterm takes the value 0 in one of the possible sets, and 1 in all others.
Example: x 1 + x 2 + x 3 .
Function in disjunctive normal form(DNF) is the logical sum of minterms.
Example: x 1x 2+ x 1x 2+ x 1x 2x 3.
Conjunctive normal form(CNF) is a logical product of elementary disjunctions (maxterms).
Example: (x 1+ x 2+ x 3) (x 1+ x 2) .
Perfect disjunctive normal form is called a DNF, each minterm of which contains all the variables or their negations.
Example: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3
Perfect conjunctive normal form is called CNF, in each maxterm of which there are all variables or their negations.
Example: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)
Recording a logical function in a table
Any logical function can be expressed as SDNF or SKNF. As an example, consider the function f presented in the table.
f(x1 , x2 , x3 ) | ||||||||
The functions G0, G1, G4, G5, G7 are minterms (see the definition). Each of these functions is the product of three variables or their inverses and takes the value 1 in only one situation. It can be seen that in order to get 1 in the value of the function f, one minterm is needed. Therefore, the number of minterms that make up the SDNF of this function is equal to the number of ones in the value of the function: f= G0+G1+G4+G5+G7. Thus, the SDNF has the form:
f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.
Similarly, one can construct a SKNF. The number of factors is equal to the number of zeros in the function values:
f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .
Thus, any logical function given in the form of a table can be written as a formula.
Algorithm for constructing SDNF according to the truth table
The truth table of some function is given. In order to build an SDNF, you need to perform the following sequence of steps:
1. Select all rows in the table where the function takes the value 1.
2. Each such line is assigned a conjunction of all arguments or their inversions (minterm). In this case, the argument that takes the value 0 enters the minterm with negation, and the value 1 enters the minterm without negation.
3. Finally, we form a disjunction of all obtained minterms. The number of minterms must match the number of units of the logical function.
Algorithm for constructing SKNF according to the truth table
The truth table of some function is given. To build a SKNF, you must perform the following sequence of steps:
1. Select all table rows where the function takes the value 0.
2. Each such line is assigned a disjunction of all arguments or their inversions (maxterm). In this case, the argument that takes the value 1 is included in the maxterm with negation, and the value 1 is included without negation.
3. Finally, we form a conjunction of all obtained maxterms. The number of maxterms must match the number of zeros of the logical function.
If we agree from two forms (SDNF or SKNF) to give preference to the one that contains fewer letters, then SDNF is preferable if there are fewer ones among the values of the truth table function, SKNF - if there are fewer zeros.
Example. The truth table of a logical function of three variables is given. Construct a logical formula that implements this function.
F(A, B, C) |
|||
We select those rows in the given truth table in which the value of the function is equal to 0.
F(A, B, C) = (A+ B+ C) (A+ B+ C)
Let's check the derived function by compiling a truth table.
Comparing the initial and final truth table, we can conclude that the logical function is built correctly.
Problem solving
1. Three teachers select tasks for the Olympiad. There are several tasks to choose from. For each task, each of the teachers expresses his opinion: easy (0) or difficult (1) task. A task is included in the Olympiad task if at least two teachers marked it as difficult, but if all three teachers consider it difficult, then such a task is not included in the Olympiad task as too difficult. Make a logical diagram of a device that will output 1 if the problem is included in the Olympiad task, and 0 if it is not included.
Let's build a truth table of the desired function. We have three input variables (three teachers). Therefore, the desired function will be a function of three variables.
Analyzing the condition of the problem, we obtain the following truth table:
We build SDNF. F(A, B, C) = ABC + ABC + ABC
Now we build the logic circuit of this function.
B & 1F(A,B,C)
2. City Olympiad in base rate informatics, 2007.Build an electrical circuit diagram for the entrance of a three-story house so that a switch on any floor can turn on or off the light in the whole house.
So, we have three switches with which we must turn the light on and off. Each switch has two states: high (0) and low (1). Suppose that if all three switches are in position 0, the light in the entrance is off. Then, when you move any of the three switches to position 1, the light in the entrance should light up. Obviously, when you move any other switch to position 1, the light in the entrance will turn off. If the third switch is moved to position 1, the light in the entrance will turn on. We build a truth table.
Then, F(A, B, C) = ABC+ ABC+ ABC+ ABC.
3. Change condition | logic function values | F(A, B, C) = C→ | A+B | ||||||||
simultaneous change of arguments B and C is equal to: | |||||||||||
A→(B C) | (B C) → A |
||||||||||
A(B C) |
|||||||||||
4) (B C) → A | A→(B C) |
Note. To successfully solve this problem, remember the following logical formulas:
x → y= x+ y x y= x y+ x y
x ↔ y= x y + x y
We are given a logical function of three variables F 1 (A , B , C ) = C → A + B = C + A B .
Let's change the variables B and C at the same time: F 2 (A , B , C ) = F 1 (A , B , C ) = C + A B . Let's build the truth tables of these two functions:
Let's analyze the resulting table. Of the eight rows of the table, only in two (2nd and 3rd) the function does not change its value. Note that in these lines variable A does not reverse its value, while variables B and C do.
We build SKNF functions according to these lines:
F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .
A+ (B↔ C) = A+ B C= (B C) → A
Therefore, the required answer is 4.
4. Condition for changing the value of a logical function F (A , B , C ) = C + AB while changing arguments A and B is equal to:
1) C+ (A B) | ||||||||||||||||||||||||||||||||||
C + (A B) | C(A B) |
|||||||||||||||||||||||||||||||||
4) C(A B) | ||||||||||||||||||||||||||||||||||
C → (A B) | ||||||||||||||||||||||||||||||||||
F 1 (A ,B ,C )= | ||||||||||||||||||||||||||||||||||
C+AB | ||||||||||||||||||||||||||||||||||
F 2 (A ,B ,C )= F 1 ( | C )=A | |||||||||||||||||||||||||||||||||
We build a truth table. | ||||||||||||||||||||||||||||||||||
Let's analyze the resulting table. Of the eight rows of the table, only in two (1st and 7th) the function changes its value. Note that in these lines, variable C does not change its value, while variables A and B do.
We build SDNF functions according to these lines:
F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)
Therefore, the required answer is 2.
References
1. Shapiro S.I. Solving logic and game problems(logical and psychological studies). - M.: Radio and communication, 1984. - 152 p.
2. Sholomov L.A. Fundamentals of the theory of discrete logic and computing devices. – M.: Science. Ch. ed. physical - mat. lit., 1980. - 400 p.
3. Pukhalsky G.I., Novoseltseva T.Ya. Design of discrete devices on integrated circuits.: A Handbook. - M .: Radio and communication, 1990.
Let be a logical function of n variables. The logical equation is:
The constant C has the value 1 or 0.
The logical equation can have from 0 to various solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table on which the function F takes the value true (1). The remaining sets are solutions of the equation for C, zero. We can always consider only equations of the form:
Indeed, let the equation be given:
In this case, you can go to the equivalent equation:
Consider a system of k logical equations:
The solution of the system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to the system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions:
If the number of variables is small, for example, less than 5, then it is not difficult to construct a truth table for the function , which allows you to say how many solutions the system has and what are the sets that give solutions.
In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, which is different from enumeration, which allows solving such problems.
In the problems proposed in the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from enumeration of all variants of a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique solution to this problem is as follows. We are not interested in all sets, but only those on which the function has the value 1. Instead of building a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies the set on which the function has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.
What is a binary decision tree and how it is built, I will explain with examples of several tasks.
Problem 18
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy a system of two equations?
Answer: The system has 36 different solutions.
Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation depending on 5 variables - . The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents a conjunction of logical functions. The converse statement is also true - the conjunction of conditions can be considered as a system of equations.
Let's build a decision tree for the implication () - the first term of the conjunction, which can be considered as the first equation. Here is what the graphic image of this tree looks like
The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable . Two branches of this level reflect the possible values of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values of the variable for which the equation takes the value true. Since the equation defines an implication, the branch on which it has a value of 1 requires that it has a value of 1 on that branch. The branch on which it has a value of 0 generates two branches with values equal to 0 and 1. The constructed tree defines three solutions, on where the implication takes the value 1. On each branch, the corresponding set of values of the variables is written out, which gives a solution to the equation.
These sets are: ((1, 1), (0, 1), (0, 0))
Let's continue building the decision tree by adding the following equation, the following implication. The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable already has values in the tree, then on all branches where the variable has a value of 1, the variable will also have a value of 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable has the value 0 will give a branch into two branches, where the variable will get the values 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:
has 6 solutions. Here is what the complete decision tree for this equation looks like:
The second equation of our system is similar to the first:
The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution can be combined with each variable solution, the total number of solutions is 36.
Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.
Problem 19
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.
It follows from the equation that when it has the value 1 (one such solution exists), then it has the value 1. Thus, there is one set on which and have the values 1. When equal to 0, it can have any value, both 0 and and 1. Therefore, each set with equal to 0, and there are 5 such sets, corresponds to all 6 sets with variables Y. Therefore, the total number of solutions is 31.
Problem 20
Solution: Remembering the basic equivalence, we write our equation as:
The cyclic chain of implications means that the variables are identical, so our equation is equivalent to:
This equation has two solutions when all are either 1 or 0.
Problem 21
How many solutions does the equation have:
Solution: Just as in Problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:
Let's build a decision tree for this equation:
Problem 22
How many solutions does the following system of equations have?
Lesson topic: Solving logical equations
Educational - learning how to solve logical equations, the formation of skills and abilities for solving logical equations and building a logical expression according to the truth table;Educational - create conditions for development cognitive interest students, to promote the development of memory, attention, logical thinking;
Educational : contribute to the education of the ability to listen to the opinions of others, education of will and perseverance to achieve the final results.
Lesson type: combined lesson
Equipment: computer, multimedia projector, presentation 6.
During the classes
Repetition and updating of basic knowledge. Examination homework(10 minutes)
In the previous lessons, we got acquainted with the basic laws of the algebra of logic, learned how to use these laws to simplify logical expressions.
Let's check the homework on simplifying logical expressions:
1. Which of the following words satisfies the logical condition:
(first consonant → second consonant)٨ (last letter vowel → penultimate letter vowel)? If there are several such words, indicate the smallest of them.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Let us introduce the notation:
A is the first letter of a consonant
B is the second letter of a consonant
S is the last vowel
D - penultimate vowel
Let's make an expression:
Let's make a table:
2. Indicate which logical expression is equivalent to the expression
Let's simplify the writing of the original expression and the proposed options:
3. A fragment of the truth table of the expression F is given:
What expression corresponds to F?Let's determine the values of these expressions for the specified values of the arguments:
Familiarization with the topic of the lesson, presentation of new material (30 minutes)
We continue to study the basics of logic and the topic of our today's lesson "Solving logical equations." After studying this topic, you will learn the basic ways to solve logical equations, get the skills to solve these equations by using the language of logic algebra and the ability to compose a logical expression on the truth table.
1. Solve the logical equation
(¬K M) → (¬L M N)=0
Write your answer as a string of four characters: the values of the variables K, L, M, and N (in that order). So, for example, line 1101 corresponds to K=1, L=1, M=0, N=1.
Solution:
Let's transform the expression(¬K M) → (¬L M N)
The expression is false when both terms are false. The second term is equal to 0 if M=0, N=0, L=1. In the first term, K = 0, since M = 0, and
.
Answer: 0100
2. How many solutions does the equation have (indicate only the number in your answer)?
Solution: transform the expression
(A+B)*(C+D)=1
A+B=1 and C+D=1
Method 2: compiling a truth table
3 way: construction of SDNF - a perfect disjunctive normal form for a function - a disjunction of complete regular elementary conjunctions.Let's transform the original expression, open the brackets in order to get the disjunction of the conjunctions:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Let's supplement the conjunctions to complete conjunctions (the product of all arguments), open the brackets:
Consider the same conjunctions:
As a result, we obtain an SDNF containing 9 conjunctions. Therefore, the truth table for this function has a value of 1 on 9 rows out of 2 4 =16 sets of variable values.
3. How many solutions does the equation have (indicate only the number in your answer)?
Let's simplify the expression:
,
3 way: construction of SDNF
Consider the same conjunctions:
As a result, we get an SDNF containing 5 conjunctions. Therefore, the truth table for this function has a value of 1 on 5 rows of 2 4 =16 sets of variable values.
Building a logical expression according to the truth table:
for each row of the truth table containing 1, we compose the product of the arguments, and the variables equal to 0 are included in the product with negation, and the variables equal to 1 - without negation. The desired expression F will be composed of the sum of the products obtained. Then, if possible, this expression should be simplified.
Example: the truth table of an expression is given. Build a logical expression.
Solution:3. Homework (5 minutes)
Solve the equation:
How many solutions does the equation have (answer only the number)?
According to the given truth table, make a logical expression and
simplify it.
How to Solve Some Problems in Sections A and B of the Computer Science Exam
Lesson number 3. Logics. Logic functions. Solving Equations
A large number of USE tasks are devoted to the logic of propositions. To solve most of them, it is enough to know the basic laws of propositional logic, knowledge of the truth tables of logical functions of one and two variables. I will give the basic laws of propositional logic.
- Commutativity of disjunction and conjunction:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - The distributive law regarding disjunction and conjunction:
a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Negative negation:
¬(¬a) ≡ a - Consistency:
a ^ ¬a ≡ false - Exclusive third:
a ˅ ¬a ≡ true - De Morgan's laws:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Simplification:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ true ≡ a
a ˄ false ≡ false - Absorption:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Replacing the implication
a → b ≡ ¬a ˅ b - Change of identity
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Representation of logical functions
Any logical function of n variables - F(x 1 , x 2 , ... x n) can be defined by a truth table. Such a table contains 2 n sets of variables, for each of which the value of the function on this set is specified. This method is good when the number of variables is relatively small. Even for n > 5, the representation becomes poorly visible.
Another way is to define the function by some formula, using the known enough simple functions. The system of functions (f 1 , f 2 , … f k ) is called complete if any logical function can be expressed by a formula containing only functions f i .
The system of functions (¬, ˄, ˅) is complete. Laws 9 and 10 are examples of how implication and identity are expressed through negation, conjunction, and disjunction.
In fact, the system of two functions is also complete - negation and conjunction or negation and disjunction. Representations follow from De Morgan's laws that allow expressing a conjunction through negation and disjunction and, accordingly, expressing a disjunction through negation and conjunction:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoxically, a system consisting of only one function is complete. There are two binary functions - anticonjunction and antidisjunction, called Pierce's arrow and Schaeffer's stroke, representing a hollow system.
The basic functions of programming languages usually include identity, negation, conjunction and disjunction. In the tasks of the exam, along with these functions, there is often an implication.
Let's look at a few simple tasks related to logical functions.
Task 15:
A fragment of the truth table is given. Which of the three given functions corresponds to this fragment?
x1 | x2 | x3 | x4 | F |
1 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Feature number 3.
To solve the problem, you need to know the truth tables of basic functions and keep in mind the priorities of operations. Let me remind you that conjunction (logical multiplication) has a higher priority and is performed before disjunction (logical addition). When calculating, it is easy to see that the functions with numbers 1 and 2 on the third set have the value 1 and for this reason do not correspond to the fragment.
Task 16:
Which of the following numbers satisfies the condition:
(digits, starting with the most significant digit, go in descending order) → (number - even) ˄ (lowest digit - even) ˄ (highest digit - odd)
If there are several such numbers, indicate the largest.
- 13579
- 97531
- 24678
- 15386
The condition is satisfied by the number 4.
The first two numbers do not satisfy the condition for the reason that the lowest digit is odd. A conjunction of conditions is false if one of the terms of the conjunction is false. For the third number, the condition for the highest digit is not met. For the fourth number, the conditions imposed on the minor and major digits of the number are met. The first term of the conjunction is also true, since an implication is true if its premise is false, which is the case here.
Problem 17: Two witnesses testified as follows:
First Witness: If A is guilty, then B is certainly guilty, and C is innocent.
Second witness: Two are guilty. And one of the remaining ones is definitely guilty and guilty, but I can’t say exactly who.
What conclusions about the guilt of A, B, and C can be drawn from the evidence?
Answer: It follows from the testimony that A and B are guilty, but C is innocent.
Solution: Of course, the answer can be given based on common sense. But let's look at how this can be done strictly and formally.
The first thing to do is to formalize the statements. Let's introduce three Boolean variables, A, B, and C, each of which is true (1) if the corresponding suspect is guilty. Then the testimony of the first witness is given by the formula:
A → (B ˄ ¬C)
The testimony of the second witness is given by the formula:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
The testimonies of both witnesses are assumed to be true and represent the conjunction of the corresponding formulas.
Let's build a truth table for these readings:
A | B | C | F1 | F2 | F 1 F 2 |
0 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 0 | 0 | 0 |
Total witness's testimonies are true only in one case, leading to an unequivocal answer - A and B are guilty, and C is innocent.
It also follows from the analysis of this table that the testimony of the second witness is more informative. Only two things follow from the truth of his testimony. possible options A and B are guilty and C is innocent, or A and C are guilty and B is innocent. The testimony of the first witness is less informative - there are 5 different options that correspond to his testimony. Together, the testimonies of both witnesses give an unequivocal answer about the guilt of the suspects.
Logic equations and systems of equations
Let F(x 1 , x 2 , …x n) be a logical function of n variables. The logical equation is:
F(x 1, x 2, ... x n) \u003d C,
The constant C has the value 1 or 0.
A logical equation can have from 0 to 2n different solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table on which the function F takes the value true (1). The remaining sets are solutions of the equation for C equal to zero. We can always consider only equations of the form:
F(x 1 , x 2 , …x n) = 1
Indeed, let the equation be given:
F(x 1 , x 2 , …x n) = 0
In this case, you can go to the equivalent equation:
¬F(x 1 , x 2 , …x n) = 1
Consider a system of k logical equations:
F 1 (x 1, x 2, ... x n) \u003d 1
F 2 (x 1, x 2, ... x n) \u003d 1
F k (x 1 , x 2 , …x n) = 1
The solution of the system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to the system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions F:
Ф = F 1 ˄ F 2 ˄ … F k
If the number of variables is small, for example, less than 5, then it is not difficult to build a truth table for the function Ф, which allows you to say how many solutions the system has and what are the sets that give solutions.
In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, other than enumeration, that allows solving such problems.
In the problems proposed in the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from enumeration of all variants of a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique for solving this problem is as follows. We are not interested in all sets, but only those on which the function Ф has the value 1. Instead of constructing a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies a set on which the function Ф has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.
What is a binary decision tree and how it is built, I will explain with examples of several tasks.
Problem 18
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy a system of two equations?
Answer: The system has 36 different solutions.
Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation, depending on 5 variables – x 1 , x 2 , …x 5 . The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents a conjunction of logical functions. The converse statement is also true - the conjunction of conditions can be considered as a system of equations.
Let's build a decision tree for the implication (x1→ x2), the first term of the conjunction, which can be considered as the first equation. Here is what the graphic representation of this tree looks like:
The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable X 1 . Two branches of this level reflect the possible values of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values of the variable X 2 for which the equation takes the value true. Since the equation defines an implication, the branch on which X 1 has the value 1 requires that X 2 has the value 1 on that branch. The branch on which X 1 has the value 0 generates two branches with X 2 values equal to 0 and 1 The constructed tree specifies three solutions, on which the implication X 1 → X 2 takes the value 1. On each branch, the corresponding set of values of the variables is written out, which gives the solution to the equation.
These sets are: ((1, 1), (0, 1), (0, 0))
Let's continue building the decision tree by adding the following equation, the following implication X 2 → X 3 . The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable X 2 already has values in the tree, then on all branches where the variable X 2 has the value 1, the variable X 3 will also have the value 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable X 2 has the value 0 will give a branch into two branches, where the variable X 3 will get the values 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
has 6 solutions. Here is what the complete decision tree for this equation looks like:
The second equation of our system is similar to the first:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution X i can be combined with each variable solution Y j , the total number of solutions is 36.
Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.
Problem 19
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.
From the equation X 1 → Y 1 it follows that when X 1 has the value 1 (one such solution exists), then Y 1 has the value 1. Thus, there is one set on which X 1 and Y 1 have the values 1. With X 1 equal to 0, Y 1 can have any value, both 0 and 1. Therefore, each set with X 1 equal to 0, and there are 5 such sets, corresponds to all 6 sets with Y variables. Therefore, the total number of solutions is 31 .
Problem 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Solution: Remembering the basic equivalence, we write our equation as:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
The cyclic chain of implications means that the variables are identical, so our equation is equivalent to:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
This equation has two solutions when all X i are either 1 or 0.
Problem 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Solution: Just as in Problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Let's build a decision tree for this equation:
Problem 22
How many solutions does the following system of equations have?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
Answer: 64
Solution: Let's go from 10 variables to 5 variables by introducing the following change of variables:
Y 1 = (X 1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);
Then the first equation will take the form:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
The equation can be simplified by writing it as:
(Y 1 ≡ Y 2) = 0
Passing to the traditional form, we write the system after simplifications in the form:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
The decision tree for this system is simple and consists of two branches with alternating variable values:
Returning to the original X variables, note that each value of the Y variable corresponds to 2 values of the X variables, so each solution in the Y variables generates 2 5 solutions in the X variables. Two branches generate 2 * 2 5 solutions, so the total number of solutions is 64.
As you can see, each task for solving a system of equations requires its own approach. A common trick is to perform equivalent transformations to simplify the equations. A common technique is the construction of decision trees. The applied approach partially resembles the construction of a truth table with the peculiarity that not all sets of possible values of variables are constructed, but only those on which the function takes the value 1 (true). Often in the proposed problems there is no need to build a complete decision tree, since already at the initial stage it is possible to establish the regularity of the appearance of new branches at each next level, as was done, for example, in problem 18.
In general, problems for finding solutions to a system of logical equations are good mathematical exercises.
If the problem is difficult to solve manually, then you can entrust the solution of the problem to the computer by writing an appropriate program for solving equations and systems of equations.
It is easy to write such a program. Such a program will easily cope with all the tasks offered in the exam.
Oddly enough, but the task of finding solutions to systems of logical equations is also difficult for a computer, it turns out that a computer has its limits. The computer can easily cope with tasks where the number of variables is 20-30, but it will start to think for a long time on larger tasks. The point is that the function 2 n that specifies the number of sets is an exponent that grows rapidly with n. So fast that the usual Personal Computer for a day will not cope with the task, which has 40 variables.
C# program for solving logical equations
Writing a program to solve logical equations is useful for many reasons, not least because it can be used to check the correctness of own decision USE test problems. Another reason is that such a program is an excellent example of a programming problem that meets the requirements for category C problems in the USE.
The idea of constructing a program is simple - it is based on a complete enumeration of all possible sets of variable values. Since the number of variables n is known for a given logical equation or system of equations, the number of sets is also known - 2 n , which need to be sorted out. Using the basic functions of the C# language - negation, disjunction, conjunction and identity, it is easy to write a program that, for a given set of variables, calculates the value of a logical function corresponding to a logical equation or system of equations.
In such a program, you need to build a cycle by the number of sets, in the body of the cycle, by the set number, form the set itself, calculate the value of the function on this set, and if this value is equal to 1, then the set gives a solution to the equation.
The only difficulty that arises in the implementation of the program is related to the task of forming the set of variable values itself by the set number. The beauty of this task is that this seemingly difficult task, in fact, comes down to a simple task that has already arisen repeatedly. Indeed, it is enough to understand that the set of values of variables corresponding to the number i, consisting of zeros and ones, represents the binary representation of the number i. So that difficult task obtaining a set of values of variables by the number of the set is reduced to the well-known problem of converting a number into a binary system.
This is how the C# function that solves our problem looks like:
///
/// program for counting the number of solutions
/// logical equation (system of equations)
///
///
/// logical function - method,
/// whose signature is set by the DF delegate
///
/// number of variables
///
static int SolveEquations(DF fun, int n)
bool set = new bool[n];
int m = (int)Math.Pow(2, n); //number of sets
int p = 0, q = 0, k = 0;
//Full enumeration by the number of sets
for (int i = 0; i< m; i++)
//Formation of the next set — set,
//given by the binary representation of the number i
for (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Calculate function value on set
To understand the program, I hope that the explanations of the idea of the program and the comments in its text will suffice. I will dwell only on the explanation of the heading of the above function. The SolveEquations function has two input parameters. The fun parameter specifies a logical function corresponding to the equation or system of equations being solved. The n parameter specifies a number function variables fun. As a result, the SolveEquations function returns the number of solutions of the logical function, that is, the number of sets on which the function evaluates to true.
For schoolchildren, it is customary when for some function F(x) the input parameter x is a variable of arithmetic, string or boolean type. In our case, a more powerful design is used. The SolveEquations function refers to higher-order functions - functions of type F(f), whose parameters can be not only simple variables, but also functions.
The class of functions that can be passed as a parameter to the SolveEquations function is defined as follows:
delegate bool DF(bool vars);
This class includes all functions that are passed as a parameter a set of values of boolean variables specified by the vars array. The result is a Boolean value representing the value of the function on this set.
In conclusion, I will give a program in which the SolveEquations function is used to solve several systems of logical equations. The SolveEquations function is part of the following ProgramCommon class:
class ProgramCommon
delegate bool DF(bool vars);
static void Main(string args)
Console.WriteLine("Function And Solutions - " +
SolveEquations(FunAnd, 2));
Console.WriteLine("Function has 51 solutions - " +
SolveEquations(Fun51, 5));
Console.WriteLine("Function has 53 solutions - " +
SolveEquations(Fun53, 10));
static bool FunAnd(bool vars)
return vars && vars;
static bool Fun51(bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
static bool Fun53(bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Here is what the results of the solution for this program look like:
10 tasks for independent work
- Which of the three functions are equivalent:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄ Y
- A fragment of the truth table is given:
x1 | x2 | x3 | x4 | F |
1 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 0 |
Which of the three functions corresponds to this fragment:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- The jury consists of three people. The decision is made if the chairman of the jury votes for it, supported by at least one of the jury members. Otherwise, no decision is made. Build a logical function that formalizes the decision making process.
- X wins over Y if four coin tosses come up heads three times. Define a boolean function describing payoff X.
- Words in a sentence are numbered starting from one. A sentence is considered well-formed if the following rules are met:
- If an even numbered word ends in a vowel, then next word, if it exists, must begin with a vowel.
- If an odd numbered word ends in a consonant, then the next word, if it exists, must start with a consonant and end with a vowel.
Which of the following sentences are correct: - Mom washed Masha with soap.
- The leader is always a model.
- The truth is good, but happiness is better.
- How many solutions does the equation have:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - List all solutions of the equation:
(a → b) → c = 0 - How many solutions does the following system of equations have:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - How many solutions does the equation have:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Answers to tasks:
- The functions b and c are equivalent.
- The fragment corresponds to function b.
- Let the boolean variable P take the value 1 when the chairman of the jury votes "for" the decision. Variables M 1 and M 2 represent the opinion of the jury members. Boolean function, specifying the adoption of a positive decision can be written as follows:
P ˄ (M 1 ˅ M 2) - Let the boolean variable P i take on the value 1 when the i-th coin toss comes up heads. The logical function that defines the payoff X can be written as follows:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Offer b.
- The equation has 3 solutions: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)