Methods for solving systems of logical equations. Logics. Logic functions. Solving equations

26.09.2019

Methods for solving systems logical equations

Kirgizova E.V., Nemkova A.E.

Lesosibirsk Pedagogical Institute –

branch of Siberian Federal University, Russia

The ability to think consistently, reason convincingly, build hypotheses, and refute negative conclusions does not come on its own; this skill is developed by the science of logic. Logic is a science that studies methods for establishing the truth or falsity of some statements on the basis of the truth or falsity of other statements.

Mastering the basics of this science is impossible without solving logical problems. Testing the development of skills to apply one's knowledge in a new situation is carried out through passing. In particular, this is the ability to decide logic problems. Tasks B15 in the Unified State Examination are tasks of increased complexity, since they contain systems of logical equations. You can select various ways solving systems of logical equations. This is reduction to one equation, construction of a truth table, decomposition, sequential solution of equations, etc.

Task:Solve a system of logical equations:

Let's consider reduction method to one equation . This method involves transforming logical equations so that their right-hand sides are equal to the truth value (that is, 1). To do this, use the logical negation operation. Then, if the equations contain complex logical operations, we replace them with basic ones: “AND”, “OR”, “NOT”. The next step is to combine the equations into one, equivalent to the system, using the logical operation “AND”. After this, you should transform the resulting equation based on the laws of logical algebra and obtain a specific solution to the system.

Solution 1:Apply inversion to both sides of the first equation:

Let’s imagine the implication through the basic operations “OR” and “NOT”:

Since the left sides of the equations are equal to 1, we can combine them using the “AND” operation into one equation that is equivalent to the original system:

We open the first bracket according to De Morgan's law and transform the result obtained:

The resulting equation has one solution: A= 0, B =0 and C =1.

The next method is constructing truth tables . Since logical quantities have only two values, you can simply go through all the options and find among them those for which a given system of equations is satisfied. That is, we build one common truth table for all equations of the system and find a line with the required values.

Solution 2:Let's create a truth table for the system:








0	0	1	1	0	1

The line for which the task conditions are met is highlighted in bold. So A =0, B =0 and C =1.

Way decomposition . The idea is to fix the value of one of the variables (set it equal to 0 or 1) and thereby simplify the equations. Then you can fix the value of the second variable, and so on.

Solution 3: Let A = 0, then:

From the first equation we get B =0, and from the second – C=1. Solution of the system: A = 0, B = 0 and C = 1.

You can also use the method sequential solution of equations , at each step adding one variable to the set under consideration. To do this, it is necessary to transform the equations so that the variables are entered in alphabetical order. Next, we build a decision tree, sequentially adding variables to it.

The first equation of the system depends only on A and B, and the second equation on A and C. Variable A can take 2 values 0 and 1:

From the first equation it follows that , so when A = 0 and we get B = 0, and for A = 1 we have B = 1. So, the first equation has two solutions with respect to the variables A and B.

Let us depict the second equation, from which we determine the values of C for each option. When A =1, the implication cannot be false, that is, the second branch of the tree has no solution. At A= 0 we get the only solution C= 1 :

Thus, we obtained the solution to the system: A = 0, B = 0 and C = 1.

In the Unified State Exam in computer science, it is very often necessary to determine the number of solutions to a system of logical equations, without finding the solutions themselves; there are also certain methods for this. The main way to find the number of solutions to a system of logical equations is replacing variables. First, you need to simplify each of the equations as much as possible based on the laws of logical algebra, and then replace the complex parts of the equations with new variables and determine the number of solutions new system. Next, return to the replacement and determine the number of solutions for it.

Task:How many solutions does the equation have ( A → B ) + (C → D ) = 1? Where A, B, C, D are logical variables.

Solution:Let's introduce new variables: X = A → B and Y = C → D . Taking into account new variable equation will be written in the form: X + Y = 1.

The disjunction is true in three cases: (0;1), (1;0) and (1;1), while X and Y is an implication, that is, it is true in three cases and false in one. Therefore, the case (0;1) will correspond to three possible combinations of parameters. Case (1;1) – will correspond to nine possible combinations of parameters of the original equation. This means that the total possible solutions given equation 3+9=15.

The next way to determine the number of solutions to a system of logical equations is binary tree. Let's look at this method using an example.

Task:How many different solutions does the system of logical equations have:

The given system of equations is equivalent to the equation:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x m -1 → x m) = 1.

Let's assume thatx 1 – is true, then from the first equation we obtain thatx 2 also true, from the second -x 3 =1, and so on until x m= 1. So the set (1; 1; …; 1) of m units is the solution of the system. Let it nowx 1 =0, then from the first equation we havex 2 =0 or x 2 =1.

When x 2 true, we obtain that the remaining variables are also true, that is, the set (0; 1; ...; 1) is a solution to the system. Atx 2 =0 we get that x 3 =0 or x 3 =, and so on. Continuing to the last variable, we find that the solutions to the equation are the following sets of variables ( m +1 solution, in each solution m variable values):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

This approach is well illustrated by constructing a binary tree. The number of possible solutions is the number of different branches of the constructed tree. It is easy to see that it is equal m +1.

Variables	Tree	Number of solutions
x 1
x 2
x 3

In case of difficulties in reasoning and building a decision tree, you can search for a solution using truth tables, for one or two equations.

Let's rewrite the system of equations in the form:

And let’s create a truth table separately for one equation:

x 1	x 2	(x 1 → x 2)

Let's create a truth table for two equations:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Next, you can see that one equation is true in the following three cases: (0; 0), (0; 1), (1; 1). A system of two equations is true in four cases (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). In this case, it is immediately clear that there is a solution consisting of only zeros and more m solutions in which one unit is added at a time, starting with last position until all possible places are filled. It can be assumed that general solution will have the same form, but for this approach to become a solution, proof is required that the assumption is true.

To summarize all of the above, I would like to draw your attention to the fact that not all of the methods discussed are universal. When solving each system of logical equations, one should take into account its features, on the basis of which the solution method should be chosen.

Literature:

1. Logical problems / O.B. Bogomolov – 2nd ed. – M.: BINOM. Laboratory of Knowledge, 2006. – 271 p.: ill.

2. Polyakov K.Yu. Systems of logical equations / Educational and methodological newspaper for computer science teachers: Informatics No. 14, 2011.

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, where J, K, L, M, N are logical variables?

Explanation.

The expression (N ∨ ¬N) is true for any N, therefore

J ∧ ¬K ∧ L ∧ ¬M = 0.

Let's apply negation to both sides of the logical equation and use De Morgan's law ¬ (A ∧ B) = ¬ A ∨ ¬ B. We get ¬J ∨ K ∨ ¬L ∨ M = 1.

A logical sum is equal to 1 if at least one of its constituent statements is equal to 1. Therefore, the resulting equation is satisfied by any combination of logical variables except the case when all quantities included in the equation are equal to 0. Each of the 4 variables can be equal to either 1 or 0, therefore all possible combinations are 2·2·2·2 = 16. Therefore, the equation has 16 −1 = 15 solutions.

It remains to note that the 15 solutions found correspond to any of the two possible values of the logical variable N, so the original equation has 30 solutions.

Answer: 30

How many different solutions does the equation have?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (M → J) = 1

where J, K, L, M, N are logical variables?

The answer does not need to list all the different sets of values of J, K, L, M and N for which this equality holds. As an answer, you need to indicate the number of such sets.

Explanation.

We use the formulas A → B = ¬A ∨ B and ¬(A ∨ B) = ¬A ∧ ¬B

Let's consider the first subformula:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Let's consider the second subformula

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Let's consider the third subformula

1) M → J = 1 therefore,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Let's combine:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 hence 4 solutions.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Let's combine:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L hence 4 solutions.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Answer: 4 + 4 = 8.

Answer: 8

How many different solutions does the equation have?

((K ∨ L) → (L ∧ M ∧ N)) = 0

where K, L, M, N are logical variables? The Answer does not need to list all the different sets of values of K, L, M and N for which this equality holds. As an Answer you need to indicate the number of such sets.

Explanation.

Let's rewrite the equation using simpler notation for operations:

((K + L) → (L M N)) = 0

1) from the truth table of the “implication” operation (see the first problem) it follows that this equality is true if and only if at the same time

K + L = 1 and L M N = 0

2) from the first equation it follows that at least one of the variables, K or L, is equal to 1 (or both together); so let's consider three cases

3) if K = 1 and L = 0, then the second equality is satisfied for any M and N; since there are 4 combinations of two Boolean variables (00, 01, 10 and 11), we have 4 different solutions

4) if K = 1 and L = 1, then the second equality holds for M · N = 0; there are 3 such combinations (00, 01 and 10), we have 3 more solutions

5) if K = 0, then L = 1 (from the first equation); in this case, the second equality is satisfied when M · N = 0; there are 3 such combinations (00, 01 and 10), we have 3 more solutions

6) in total we get 4 + 3 + 3 = 10 solutions.

Answer: 10

How many different solutions does the equation have?

(K ∧ L) ∨ (M ∧ N) = 1

Explanation.

The expression is true in three cases, when (K ∧ L) and (M ∧ N) are equal to 01, 11, 10, respectively.

1) "01" K ∧ L = 0; M ∧ N = 1, => M, N are equal to 1, and K and L are anything except simultaneously 1. Therefore, there are 3 solutions.

2) "11" K ∧ L = 1; M ∧ N = 1. => 1 solution.

3) "10" K ∧ L = 1; M ∧ N = 0. => 3 solutions.

Answer: 7.

Answer: 7

How many different solutions does the equation have?

(X ∧ Y ∨ Z) → (Z ∨ P) = 0

where X, Y, Z, P are logical variables? The answer does not need to list all the different sets of values for which this equality holds. As an answer, you only need to indicate the number of such sets.

Explanation.

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Logical OR is false only in one case: when both expressions are false.

Hence,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Therefore, there is only one solution to the equation.

Answer: 1

How many different solutions does the equation have?

(K ∨ L) ∧ (M ∨ N) = 1

where K, L, M, N are logical variables? The answer does not need to list all the different sets of values of K, L, M and N for which this equality holds. As an answer, you only need to indicate the number of such sets.

Explanation.

Logical And is true only in one case: when all expressions are true.

K ∨ L = 1, M ∨ N = 1.

Each equation gives 3 solutions.

Consider the equation A ∧ B = 1 if both A and B accept true values in three cases each, then in total the equation has 9 solutions.

Therefore the answer is 9.

Answer: 9

How many different solutions does the equation have?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

where A, B, C, D are logical variables?

The answer does not need to list all the different sets of values A, B, C, D for which this equality holds. As an answer, you need to indicate the number of such sets.

Explanation.

Logical "OR" is true when at least one of the statements is true.

(D ∧ ¬D)= 0 for any D.

Hence,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, which gives us 3 possible solutions for each D.

(D ∧ ¬ D)= 0 for any D, which gives us two solutions (for D = 1, D = 0).

Therefore: total solutions 2*3 = 6.

Total 6 solutions.

Answer: 6

How many different solutions does the equation have?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

Explanation.

Let's apply negation to both sides of the equation:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Logical OR is true in three cases.

Option 1.

K ∧ L ∧ M = 1, then K, L, M = 1, and ¬L ∧ M ∧ N = 0. N is arbitrary, that is, 2 solutions.

Option 2.

¬L ∧ M ∧ N = 1, then N, M = 1; L = 0, K any, that is, 2 solutions.

Therefore the answer is 4.

Answer: 4

A, B and C are integers for which the statement is true

¬ (A = B) ∧ ((A > B)→(B > C)) ∧ ((B > A)→(C > B)).

What is B equal to if A = 45 and C = 43?

Explanation.

1) ¬(A = B); (A > B)→(B > C); (B > A)→(C > B);

2) these simple statements are connected by the operation ∧ (AND, conjunction), that is, they must be executed simultaneously;

3) from ¬(A = B)=1 it immediately follows that A B;

4) suppose that A > B, then from the second condition we obtain 1→(B > C)=1; this expression can be true if and only if B > C = 1;

5) therefore we have A > B > C, only the number 44 corresponds to this condition;

6) just in case, let’s also check option A 0 →(B > C)=1;

this expression is true for any B; Now we look at the third condition and we get

this expression can be true if and only if C > B, and here we have a contradiction, because there is no such number B for which C > B > A.

Answer: 44.

Answer: 44

Construct a truth table for a logical function

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

in which the column of values of argument A is the binary representation of the number 27, the column of values of argument B is the number 77, the column of values of argument C is the number 120. The number in the column is written from top to bottom from the most significant to the least significant (including the zero set). Convert the resulting binary representation of the values of function X to the decimal number system.

Explanation.

Let's write the equation using simpler notation for operations:

1) this is an expression with three variables, so there will be lines in the truth table; therefore, the binary representation of the numbers used to construct table columns A, B and C must consist of 8 digits

2) convert the numbers 27, 77 and 120 into the binary system, immediately adding up to 8 digits of zeros at the beginning of the numbers

3) it is unlikely that you will be able to immediately write the values of the X function for each combination, so it is convenient to add additional columns to the table to calculate intermediate results (see table below)

A	IN	WITH
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) fill in the table columns:

A	IN	WITH					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

the value is 1 only in those lines where A = B

the value is 1 in those lines where either B or C = 1

the value is 0 only in those lines where A = 1 and B + C = 0

the value is the inverse of the previous column (0 is replaced by 1, and 1 is replaced by 0)

the result of X (last column) is the logical sum of the two columns and

5) to get the answer, write out the bits from column X from top to bottom:

6) convert this number to the decimal system:

Answer: 171

What is the largest integer X for which the statement (10 (X+1)·(X+2)) is true?

Explanation.

An equation is an operation of implication between two relations:

1) Of course, here you can apply the same method as in example 2208, but you will need to solve quadratic equations(I don’t want to...);

2) Note that by condition we are only interested in integers, so we can try to somehow transform the original expression, obtaining an equivalent statement ( exact values we are not interested in roots at all!);

3) Consider the inequality: obviously, it can be either a positive or a negative number;

4) It is easy to check that in the domain the statement is true for all integers , and in the domain - for all integers (in order not to get confused, it is more convenient to use non-strict inequalities, and , instead of and );

5) Therefore, for integers it can be replaced by an equivalent expression

6) the domain of truth of an expression is the union of two infinite intervals;

7) Now consider the second inequality: it is obvious that it can also be either a positive or a negative number;

8) In the domain the statement is true for all integers , and in the domain - for all integers , therefore for integers it can be replaced by an equivalent expression

9) the domain of truth of the expression is a closed interval;

10) The given expression is true everywhere, except for areas where and ;

11) Please note that the value is no longer suitable, because there and , that is, the implication gives 0;

12) When substituting 2, (10 (2+1) · (2+2)), or 0 → 0 which satisfies the condition.

So the answer is 2.

Answer: 2

What is the largest integer X for which the statement is true

(50 (X+1)·(X+1))?

Explanation.

Let's apply the implication transformation and transform the expression:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Logical OR is true when at least one logical statement is true. Having solved both inequalities and taking into account that we see that the largest integer for which at least one of them is satisfied is 7 (in the figure, the positive solution of the second inequality is shown in yellow, and the first in blue).

Answer: 7

Indicate the values of the variables K, L, M, N, at which the logical expression

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

false. Write your answer as a string of 4 characters: the values of the variables K, L, M and N (in that order). So, for example, line 1101 corresponds to the fact that K=1, L=1, M=0, N=1.

Explanation.

Duplicates task 3584.

Answer: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Explanation.

Let's apply the implication transformation:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Let's apply negation to both sides of the equation:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Let's transform:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Therefore, M = 0, N = 0, now consider (¬K ∧ L ∨ M ∧ L):

from the fact that M = 0, N = 0 it follows that M ∧ L = 0, then ¬K ∧ L = 1, that is, K = 0, L = 1.

Answer: 0100

Specify the values of the variables K, L, M, N at which the logical expression

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

false. Write your answer as a string of four characters: the values of the variables K, L, M and N (in that order). So, for example, line 1101 corresponds to the fact that K=1, L=1, M=0, N=1.

Explanation.

Let's write the equation using simpler notation of operations (the condition “the expression is false” means that it is equal to logical zero):

1) from the formulation of the condition it follows that the expression must be false only for one set of variables

2) from the truth table of the operation “implication” it follows that this expression is false if and only if at the same time

3) the first equality (the logical product is equal to 1) is satisfied if and only if and ; from this it follows (the logical sum is equal to zero), which can only happen when ; Thus, we have already defined three variables

4) from the second condition, , for and we obtain .

Duplicates the task

Answer: 1000

Specify the values of the logical variables P, Q, S, T, at which the logical expression

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) is false.

Write the answer as a string of four characters: the values of the variables P, Q, S, T (in that order).

Explanation.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Let us apply the implication transformation:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Answer: 0100

Specify the values of the variables K, L, M, N at which the logical expression

(K → M) ∨ (L ∧ K) ∨ ¬N

false. Write your answer as a string of four characters: the values of the variables K, L, M and N (in that order). So, for example, line 1101 corresponds to the fact that K=1, L=1, M=0, N=1.

Explanation.

Logical OR is false if and only if both statements are false.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Let's apply the implication transformation for the first expression:

¬K ∨ M = 0 => K = 1, M = 0.

Consider the second expression:

(L ∧ K) ∨ ¬N = 0 (see the result of the first expression) => L ∨ ¬N = 0 => L = 0, N = 1.

Answer: 1001.

Answer: 1001

Specify the values of the variables K, L, M, N at which the logical expression

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

true. Write your answer as a string of four characters: the values of the variables K, L, M and N (in that order). So, for example, line 1101 corresponds to the fact that K=1, L=1, M=0, N=1.

Explanation.

Logical "AND" is true if and only if both statements are true.

1) (K → M) = 1 Apply the implication transformation: ¬K ∨ M = 1

2) (K → ¬M) = 1 Apply the implication transformation: ¬K ∨ ¬M = 1

It follows that K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Apply the implication transformation: K ∨ (M ∧ ¬L ∧ N) = 1 from the fact that K = 0 we obtain:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Answer: 0011

It is known that for integers X, Y and Z the following statement is true:

(Z What is Z equal if X=25 and Y=48?

Explanation.

After substituting the numbers, we get that Z = 47.

Please note that this complex statement consists of three simple ones

1) (Z 2) these simple statements are connected by the operation ∧ (AND, conjunction), that is, they must be executed simultaneously.

3) from ¬(Z+1 24, and from ¬(Z+1 47.

4) from (Z Z Answer: 47.

Answer: 47

A, B and C are integers for which the following statement is true:

(C What is the value of C if A=45 and B=18?

Explanation.

Logical "AND" is true if and only if both statements are true.

Let's substitute the numbers into the expression:

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

From 2) and 1) it follows that C

Answer: 44

¬(A = B) ∧ ((B A)) ∧ ((A 2C))

What is the value of A if C = 8 and B = 18?

Explanation.

Logical "AND" is true if and only if both statements are true.

1) ¬(A = B) = 1, that is, A ≠ 18 = 1.

2) ((B A)) Apply the implication transformation: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Apply the implication transformation: (A > 18) ∨ (A > 16) = 1

From 2) and 3) it follows that (18 > A) and (A > 16), since otherwise a contradiction arises: A = 17.

Answer: 17

A, B and C are integers for which the statement is true

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

What is the value of B if A = 45 and C = 18?

Explanation.

Logical "AND" is true only if all statements are true.

Let be a logical function of n variables. The logical equation looks like:

The constant C has the value 1 or 0.

A logical equation can have from 0 to different solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table for which the function F takes the value true (1). The remaining sets are solutions of the equation with C equal to zero. You can always consider only equations of the form:

Indeed, let the equation be given:

In this case, we can go to the equivalent equation:

Consider a system of k logical equations:

The solution to a 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 a 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 us to say how many solutions the system has and what are the sets that provide solutions.

In some Unified State Examination problems to find solutions to a system of logical equations, the number of variables reaches 10. Then constructing a truth table becomes an almost impossible task. Solving the problem requires a different approach. For an arbitrary system of equations there are no general method, different from brute force, which allows solving such problems.

In the problems proposed on the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from trying out all the options for 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 trick The 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 constructing full table truth, 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.

I will explain what a binary decision tree is and how it is built using examples of several problems.

Problem 18

How many different sets of values of the logical variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy the 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 the conjunction of logical functions. The converse statement is also true - a conjunction of conditions can be considered as a system of equations.

Let's build a decision tree for implication () - the first term of the conjunction, which can be considered as the first equation. This is what a graphical 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. 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 evaluates to true. Since the equation specifies an implication, a branch on which has the value 1 requires that on this branch there be a value of 1. A branch on which has the value 0 generates two branches with values equal to 0 and 1. The constructed tree specifies three solutions, on of which the implication takes the value 1. On each branch, a corresponding set of variable values is written out, giving 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 new branches do not appear. A single branch where a variable has a value of 0 will branch into two branches where the variable will receive values of 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:

has 6 solutions. This is what it looks like full tree solutions for this equation:

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 every variable solution can be combined with every variable solution, then total number There are 36 solutions.

Please 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 on each branch of the tree.

Problem 19

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?

This task is a modification of the previous task. The difference is that another equation is added that relates the variables X and Y.

It follows from the equation that when has a value of 1 (one such solution exists), then it has a value of 1. Thus, there is one set on which and have values of 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 equivalences, we write our equation as:

The cyclic chain of implications means that the variables are identical, so our equation is equivalent to the equation:

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 move from cyclic implications to identities, 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?

There are various ways to solve systems of logical equations. This is reduction to one equation, construction of a truth table and decomposition.

Task: Solve a system of logical equations:

Solution 1: Apply inversion to both sides of the first equation:

Let’s imagine the implication through the basic operations “OR” and “NOT”:

Since the left sides of the equations are equal to 1, we can combine them using the “AND” operation into one equation that is equivalent to the original system:

We open the first bracket according to De Morgan's law and transform the result obtained:

The resulting equation has one solution: A =0, B=0 and C=1.

Solution 2: Let's create a truth table for the system:








0	0	1	1	0	1

The line for which the task conditions are met is highlighted in bold. So A=0, B=0 and C=1.

Solution 3: Let A = 0, then:

From the first equation we get B = 0, and from the second - C = 1. Solution of the system: A = 0, B = 0 and C = 1.

In the Unified State Exam in computer science, it is very often necessary to determine the number of solutions to a system of logical equations, without finding the solutions themselves; there are also certain methods for this. The main way to find the number of solutions to a system of logical equations isreplacing variables. First, you need to simplify each of the equations as much as possible based on the laws of logical algebra, and then replace the complex parts of the equations with new variables and determine the number of solutions to the new system. Next, return to the replacement and determine the number of solutions for it.

Task: How many solutions does the equation (A →B) + (C →D) = 1 have? Where A, B, C, D are logical variables.

Solution: Let's introduce new variables: X = A →B and Y = C →D. Taking into account the new variables, the equation will be written as: X + Y = 1.

The disjunction is true in three cases: (0;1), (1;0) and (1;1), while X and Y are implications, that is, it is true in three cases and false in one. Therefore, the case (0;1) will correspond to three possible combinations of parameters. Case (1;1) – will correspond to nine possible combinations of parameters of the original equation. This means that the total possible solutions to this equation are 3+9=15.

The next way to determine the number of solutions to a system of logical equations is binary tree. Let's look at this method using an example.

Task: How many different solutions does the system of logical equations have:

The given system of equations is equivalent to the equation:

(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.

Let's assume that x 1 – is true, then from the first equation we obtain that x 2 also true, from the second - x 3 =1, and so on until x m= 1. This means that the set (1; 1; …; 1) of m units is a solution to the system. Let it now x 1 =0, then from the first equation we have x 2 =0 or x 2 =1.

When x 2 true, we obtain that the remaining variables are also true, that is, the set (0; 1; ...; 1) is a solution to the system. At x 2 =0 we get that x 3 =0 or x 3 =, and so on. Continuing to the last variable, we find that the solutions to the equation are the following sets of variables (m +1 solution, each solution contains m values of the variables):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

This approach is well illustrated by constructing a binary tree. The number of possible solutions is the number of different branches of the constructed tree. It is easy to see that it is equal to m +1.

	Tree	Number of solutions
x 1
x 2
x 3
		…

In case of difficulties in reasoning research and constructionof solutions you can search for a solution with using truth tables, for one or two equations.

Let's rewrite the system of equations in the form:

And let’s create a truth table separately for one equation:

x 1	x 2	(x 1 → x 2)

Let's create a truth table for two equations:

x 1	x 2	x 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) (x 2 → x 3)*

Methods for solving systems of logical equations

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, y1 = 1 must be, 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 is the same as 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.