Logics. Logic functions. Solving equations. Solving logical equations in mathematics

26.09.2019

Solving systems of logical equations by changing variables

The method of substitution of variables is used if some variables are included in the equations only in the form of a specific expression, and nothing else. Then this expression can be denoted by a new variable.

Example 1.

How many different sets of values of the logical variables x1, x2, x3, x4, x5, x6, x7, x8 are there that satisfy all the conditions listed below?

(x1 → x2) → (x3→ x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

The answer does not need to list all the different sets of values of the variables x1, x2, x3, x4, x5, x6, x7, x8, for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Then we can write the system in the form of a single equation:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. The conjunction is 1 (true) when each operand takes the value 1. That is each of the implications must be true, and this is true for all values except (1 → 0). Those. in the table of values of variables y1, y2, y3, y4, one should not be to the left of zero:

Those. the conditions are satisfied for 5 sets y1-y4.

Because y1 = x1 → x2, then the value y1 = 0 is achieved on a single set x1, x2: (1, 0), and the value y1 = 1 – on three sets x1, x2: (0,0) , (0,1), (1.1). Likewise for y2, y3, y4.

Since each set (x1,x2) for the variable y1 is combined with each set (x3,x4) for the variable y2, etc., the numbers of sets of the variables x are multiplied:

				Number of sets per x1…x8

Let's add up the number of sets: 1 + 3 + 9 + 27 + 81 = 121.

Answer: 121

Example 2.

How many different sets of values of the logical variables x1, x2, ... x9, y1, y2, ... y9 are there that satisfy all the conditions listed below?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

In response no need list all the different sets of values of the variables x1, x2, ... x9, y1, y2, ... y9 for which the given system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

Let's make a change of variables:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

The system can be written as a single equation:

(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)

Equivalence is true only if both operands are equal. There are two sets of solutions to this equation:

z1	z2	z3	z4	z5	z6	z7	z8	z9
0	1	0	1	0	1	0	1	0
1	0	1	0	1	0	1	0	1

Because zi = (xi ≡ yi), then the value zi = 0 corresponds to two sets (xi,yi): (0,1) and (1,0), and the value zi = 1 corresponds to two sets (xi,yi): (0 ,0) and (1,1).

Then the first set z1, z2,…, z9 corresponds to 2 9 sets (x1,y1), (x2,y2),…, (x9,y9).

The same number corresponds to the second set z1, z2,…, z9. Then there are a total of 2 9 +2 9 = 1024 sets.

Answer: 1024

Solving systems of logical equations by visually determining recursion.

This method is used if the system of equations is quite simple and the order of increasing the number of sets when adding variables is obvious.

Example 3.

How many different solutions does the system of equations have?

¬x9 ∨ x10 = 1,

where x1, x2, … x10 are logical variables?

The answer does not need to list all the different sets of values x1, x2, ... x10 for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

Let's solve the first equation. A disjunction is equal to 1 if at least one of its operands is equal to 1. That is the solutions are the sets:

For x1=0, there are two values of x2 (0 and 1), and for x1=1 there is only one value of x2 (1), such that the set (x1,x2) is a solution to the equation. There are 3 sets in total.

Let's add the variable x3 and consider the second equation. It is similar to the first one, which means that for x2=0 there are two values of x3 (0 and 1), and for x2=1 there is only one value x3 (1), such that the set (x2,x3) is a solution to the equation. There are 4 sets in total.

It is easy to see that when adding another variable, one set is added. Those. recursive formula for the number of sets of (i+1) variables:

N i +1 = N i + 1. Then for ten variables we get 11 sets.

Answer: 11

Solving systems of logical equations of various types

Example 4.

How many different sets of values of the logical variables x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4 are there that satisfy all the conditions listed below?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

In response no need list all the different sets of values of the variables x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4 for which 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.

Let's look at the first equation. A conjunction is true (equal to 1) only if all its operands are true (equal to 1). The implication is 1 on all tuples except (1,0). This means that the solution to the first equation will be the following sets x1, x2, x3, x4, in which 1 is not located to the left of 0 (5 sets):

Similarly, the solutions to the second and third equations will be absolutely the same sets y1,…,y4 and z1,…, z4.

Now let's analyze the fourth equation of the system: x 4 ∧ y 4 ∧ z 4 = 0. The solution will be all sets x4, y4, z4 in which at least one of the variables is equal to 0.

Those. for x4 = 0, all possible sets (y4, z4) are suitable, and for x4 = 1, sets (y4, z4) are suitable, in which there is at least one zero: (0, 0), (0,1) , (1, 0).

				Number of sets

The total number of sets is 25 + 4*9 = 25 + 36 = 61.

Answer: 61

Solving systems of logical equations by constructing recurrent formulas

The method of constructing recurrent formulas is used when solving complex systems in which the order of increasing the number of sets is not obvious, and constructing a tree is impossible due to volumes.

Example 5.

How many different sets of values of the logical variables x1, x2, ... x7, y1, y2, ... y7 are there that satisfy all the conditions listed below?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

The answer does not need to list all the different sets of values of the variables x1, x2, ..., x7, y1, y2, ..., y7 for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution:

Note that the first six equations of the system are identical and differ only in the set of variables. Let's look at the first equation. Its solution will be the following sets of variables:

Let's denote:

number of tuples (0,0) on variables (x1,y1) through A 1,

number of tuples (0,1) on variables (x1,y1) through B 1,

number of tuples (1,0) on variables (x1,y1) through C 1,

the number of tuples (1,1) on the variables (x1,y1) through D 1 .

number of tuples (0,0) on variables (x2,y2) through A 2 ,

number of tuples (0,1) on variables (x2,y2) through B 2,

number of tuples (1,0) on variables (x2,y2) through C 2,

the number of tuples (1,1) on the variables (x2,y2) through D 2 .

From the decision tree we see that

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

Note that the set (0,0) on the variables (x2,y2) is obtained from the sets (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. A 2 =B 1 +C 1 +D 1.

The set (0,1) on the variables (x2,y2) is obtained from the sets (0,1), (1,0) and (1,1) on the variables (x1,y1). Those. B 2 =B 1 +C 1 +D 1.

Arguing similarly, we note that C 2 =B 1 +C 1 +D 1. D2 = D1.

Thus, we obtain recurrent formulas:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i +B i + C i + D i

Let's make a table

Sets	Designation.	Formula	Number of sets
Sets	Designation.	Formula	i=1	i=2	i=3	i=4	i=5	i=6	i=7
(0,0)	A i	A i+1 =B i +C i +D i	0	3	7	15	31	63	127
(0,1)	B i	B i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,0)	C i	C i+1 =B i +C i +D i	1	3	7	15	31	63	127
(1,1)	D i	D i+1 =D i	1	1	1	1	1	1	1

The last equation (x7 ∨ y7) = 1 is satisfied by all sets except those in which x7=0 and y7=0. In our table the number of such sets is A 7.

Then the total number of sets is B 7 + C 7 + D 7 = 127+127+1 = 255

Answer: 255

How to solve some problems in sections A and B of the computer science exam

Lesson #3. Logics. Logic functions. Solving equations

A large number of Unified State Exam problems are devoted to propositional logic. 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
Distributive law regarding disjunction and conjunction:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negation of negation:
¬(¬a) ≡ a
Consistency:
a ^ ¬а ≡ false
Exclusive third:
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
Replacement of implication
a → b ≡ ¬a ˅ b
Replacement 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 specified by a truth table. Such a table contains 2n sets of variables, for each of which the value of a function on this set is specified. This method is good when the number of variables is relatively small. Already for n > 5 the representation becomes poorly visible.

Another way is to define the function by some formula using known fairly simple functions. A 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 demonstrating how implication and identity are expressed through negation, conjunction and disjunction.

In fact, a system of two functions – negation and conjunction or negation and disjunction – is also complete. From De Morgan's laws follow ideas that allow one to express a conjunction through negation and disjunction and, accordingly, to express a disjunction through negation and conjunction:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoxically, a system consisting of just one function is complete. There are two binary functions - anticonjunction and antidisjunction, called the Peirce arrow and the Schaeffer stroke, representing a hollow system.

The basic functions of programming languages usually include identity, negation, conjunction and disjunction. IN Unified State Examination problems Along with these functions, implication is often found.

Let's look at a few simple tasks related to logical functions.

Problem 15:

A fragment of the truth table is given. Which of the three functions given corresponds to this fragment?

X 1	X 2	X 3	X 4	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)

Function number 3.

To solve the problem, you need to know the truth tables of basic functions and remember the priorities of operations. Let me remind you that conjunction (logical multiplication) has a higher priority and is executed earlier than disjunction (logical addition). During calculations, it is easy to notice that functions with numbers 1 and 2 in the third set have the value 1 and for this reason do not correspond to the fragment.

Problem 16:

Which of the given numbers satisfies the condition:

(digits, starting from the most significant digit, are in descending order) → (number - even) ˄ (low digit - even) ˄ (high digit - odd)

If there are several such numbers, indicate the largest.

13579
97531
24678
15386

The condition is satisfied by the number 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 low and high digits of the number are met. The first term of the conjunction is also true, since the implication is true if its premise is false, which is the case in this case.

Problem 17: Two witnesses gave the following testimony:

First witness: If A is guilty, then B is even more 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 who exactly.

What conclusions about the guilt of A, B and C can be drawn from the testimony?

Answer: From the testimony it follows that A and B are guilty, and 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 logical variables - A, B and C, each of which has the value 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 testimony of both witnesses is assumed to be true and represents the conjunction of the corresponding formulas.

Let's build a truth table for these readings:

A	B	C	F 1	F 2	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

The summary evidence is true in only one case, leading to a clear answer - A and B are guilty, and C is innocent.

From the analysis of this table it also follows 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 various options, corresponding to his testimony. Together, the testimony of both witnesses gives a clear answer about the guilt of the suspects.

Logical equations and systems of equations

Let F(x 1, x 2, …x n) be a logical function of n variables. The logical equation looks like:

F(x 1, x 2, …x n) = C,

The constant C has the value 1 or 0.

A logical equation can have from 0 to 2 n 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:

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, we 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) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1 , x 2 , …x n) = 1

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 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 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 USE problems on finding 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 - 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 the conjunction of logical functions. The converse is also true: a 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. 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 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 is true. Since the equation specifies an implication, a branch on which X 1 has the value 1 requires that on that branch X 2 has the value 1. A branch on which X 1 has the value 0 produces two branches with the values of X 2 equal to 0 and 1 The constructed tree defines three solutions, on which the implication X 1 → X 2 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 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 a value of 1, the variable X 3 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. The single branch where the variable X 2 has the value 0 will branch into two branches where the variable X 3 will receive the values 0 and 1. Thus, each addition of a new equation, given its specifics, adds one solution. Original first equation:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
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:

(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 every solution for the variables X i can be combined with every solution for the variables Y j , 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?

(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 variables X and Y.

From the equation X 1 → Y 1 it follows that when X 1 has the value 1 (one such solution exists), then Y 1 also has the value 1. Thus, there is one set on which X 1 and Y 1 have the values 1. When 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 equivalences, 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 the equation:

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 move from cyclic implications to identities, 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 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Answer: 64

Solution: Let's move from 10 variables to 5 variables by introducing the following change of variables:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (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

Moving on 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 for each value in the Y variable there are 2 values in the X variables, so each solution in the Y variables generates 2 5 solutions in the X variables. The two branches generate 2 * 2 5 solutions, so the total number of solutions is 64.

As you can see, each problem of solving a system of equations requires its own approach. A common technique is to perform equivalent transformations to simplify equations. A common technique is to construct decision trees. The approach used is partially reminiscent of constructing 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 initial stage it is possible to establish a pattern of the appearance of new branches at each subsequent level, as was done, for example, in problem 18.

In general, problems involving 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 to the computer by writing an appropriate program for solving equations and systems of equations.

It is not difficult to write such a program. Such a program will easily cope with all the tasks offered in the Unified State Exam.

Oddly enough, the task of finding solutions to systems of logical equations is difficult for a computer, and it turns out that a computer has its limits. A computer can quite easily cope with tasks where the number of variables is 20-30, but it will begin to think about problems for a long time larger size. The fact is that the function 2 n, which specifies the number of sets, is an exponential that grows rapidly as n increases. So fast that an ordinary personal computer cannot cope with a task that has 40 variables in a day.

Program in C# language for solving logical equations

Writing a program for solving logical equations is useful for many reasons, if only because you can use it to check the correctness of your own solution to Unified State Exam test problems. Another reason is that such a program is an excellent example of a programming task that meets the requirements for category C tasks in the Unified State Examination.

The idea of building a program is simple - it is based on a complete search of all possible sets of variable values. Since for a given logical equation or system of equations the number of variables n is known, then the number of sets is also known - 2 n which need to be sorted out. Using basic functions C# language - negation, disjunction, conjunction and identity, it is not difficult 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 loop based on the number of sets, in the body of the loop, using the number of the set, form the set itself, calculate the value of the function on this set, and if this value is 1, then the set gives a solution to the equation.

The only difficulty that arises when implementing the program is related to the task of generating the set of variable values itself based on the set number. The beauty of this problem is that this seemingly difficult task actually comes down to a simple problem that has already arisen many times. Indeed, it is enough to understand that the set of variable values corresponding to the number i, consisting of zeros and ones, represents the binary representation of the number i. So difficult task obtaining a set of variable values by set number comes down to the well-known problem of converting a number to the binary system.

This is what a function in C# looks like that solves our problem:

///

/// program for counting the number of solutions

/// logical equation (system of equations)

///

/// logical function - method,

/// whose signature is specified by the DF delegate

///

/// number of variables

/// number of solutions

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;

//Complete search by number of sets

for (int i = 0; i< m; i++)

//Formation of the next set - set,

//specified by the binary representation of the number i

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Calculate the value of the function on the set

To understand the program, I hope the explanations of the program's idea and comments in its text are sufficient. I will only focus on explaining the title of the given 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 the number function variables fun. As a result, the SolveEquations function returns the number of solutions of the logical function, that is, the number of those sets on which the function evaluates to true.

It is common for schoolchildren when some function F(x) has an input parameter x that is a variable of arithmetic, string or logical 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 specified as follows:

delegate bool DF(bool vars);

This class owns all functions that are passed as a parameter a set of values of logical variables specified by the vars array. The result is a Boolean value representing the value of the function on this set.

Finally, here is a program that uses the SolveEquations function to solve several systems of logical equations. The SolveEquations function is part of the ProgramCommon class below:

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine("And Functions - " +

SolveEquations(FunAnd, 2));

Console.WriteLine("The Function has 51 solutions - " +

SolveEquations(Fun51, 5));

Console.WriteLine("The Function has 53 solutions - " +

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

f = f && (!vars || vars);

static bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Here's what the solution results for this program look like:

10 tasks for independent work

Which of the three functions are equivalent:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Given is a fragment of the truth table:

X 1	X 2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Which of the three functions does this fragment correspond to:

(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. Construct a logical function that formalizes the decision-making process.
X wins over Y if four coin tosses result in heads three times. Define a logical function that describes the payoff of X.
Words in a sentence are numbered starting from one. A sentence is considered correctly constructed if the following rules are met:
1. If an even-numbered word ends with a vowel, then next word, if it exists, must begin with a vowel.
2. If an odd-numbered word ends with a consonant, then the next word, if it exists, must begin with a consonant and end with a vowel.
  Which of the following sentences are correctly constructed:
3. Mom washed Masha with soap.
4. A leader is always a model.
5. Truth is good, but happiness is better.
How many solutions does the equation have:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
List all solutions to 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 problems:

The functions b and c are equivalent.
The fragment corresponds to function b.
Let the logical variable P take the value 1 when the chairman of the jury votes “for” the decision. Variables M 1 and M 2 represent the opinions of the jury members. The logical function that specifies making a positive decision can be written as follows:
P ˄ (M 1 ˅ M 2)
Let the logical variable P i take the value 1 when the i-th coin toss lands on heads. The logical function that specifies 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))
Sentence b.
The equation has 3 solutions: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Methods for solving systems of logical equations

You can solve a system of logical equations, for example, using a truth table (if the number of variables is not too large) or using a decision tree, having first simplified each equation.

1. Variable replacement method.

Introducing new variables allows you to simplify the system of equations, reducing the number of unknowns.New variables must be independent of each other. After solving the simplified system, we must return to the original variables.

Let's consider the application of this method using a specific example.

Example.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Solution:

Let's introduce new variables: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Attention! Each of the variables x1, x2, ..., x10 must be included in only one of the new variables A, B, C, D, E, i.e. the new variables are independent of each other).

Then the system of equations will look like this:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Let's build a decision tree for the resulting system:

Consider the equation A=0, i.e. (X1≡ X2)=0. It has 2 roots:

		X1 ≡ X2

From the same table it can be seen that the equation A=1 also has 2 roots. Let's arrange the number of roots on the decision tree:

To find the number of solutions of one branch, you need to multiply the number of solutions at each level. The left branch has 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 solutions; the right branch also has 32 solutions. Those. the whole system has 32+32=64 solutions.

Answer: 64.

2. Method of reasoning.

The difficulty of solving systems of logical equations lies in the cumbersomeness of a complete decision tree. The reasoning method allows you not to build the entire tree, but to understand how many branches it will have. Let's look at this method using specific examples.

Example 1. How many different sets of values of the logical variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all the conditions listed below?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

The answer does not need to list all the different sets of values of the variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 for which this system of equalities is satisfied. As an answer, you need to indicate the number of such sets.

Solution :

The first and second equations contain independent variables that are related by the third condition. Let's build a solution tree for the first and second equations.

To represent a solution tree for a system of the first and second equations, each branch of the first tree must be continued with a tree for variables at . The tree constructed in this way will contain 36 branches. Some of these branches do not satisfy the third equation of the system. Let's mark the number of branches of the tree on the first tree"y" , which satisfy the third equation:

Let us explain: to satisfy the third condition, when x1=0 there must be y1=1, i.e. all branches of the tree"X" , where x1=0 can be continued with only one branch from the tree"y" . And only for one branch of the tree"X" (right) all branches of the tree fit"y". Thus, the complete tree of the entire system contains 11 branches. Each branch represents one solution to the original system of equations. This means that the entire system has 11 solutions.

Answer: 11.

Example 2. How many different solutions does the system of equations have?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

where x1, x2, …, x10 are logical variables? The answer does not need to list all the different sets of variable values for which this equality holds. As an answer, you need to indicate the number of such sets.

Solution : Let's simplify the system. Let's build a truth table for part of the first equation:

X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

Pay attention to the last column, it matches the result of the action X1 ≡ X10.

X1 ≡ X10

After simplification we get:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Consider the last equation:(X1 ≡ X10) = 0, i.e. x1 should not coincide with x10. For the first equation to be equal to 1, the equality must be true(X1 ≡ X2)=1, i.e. x1 must match x2.

Let's build a solution tree for the first equation:

Consider the second equation: for x10=1 and for x2=0 the bracketmust be equal to 1 (i.e. x2 coincides with x3); for x10=0 and for x2=1 bracket(X2 ≡ X10)=0, which means the bracket (X2 ≡ X3) should be equal to 1 (i.e. x2 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: 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.

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:

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 USE problems on finding 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 is no general method other than enumeration that 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 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 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 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 no new branches appear. A single branch where the variable has a value of 0 will branch into two branches where the variable will receive 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's 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.

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?

You can select various ways solving systems of logical equations. This is reduction to one equation, construction of a truth table and decomposition.

Task: Solve a system of logical equations:

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

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

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

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

The disjunction is true in three cases: (0;1), (1;0) and (1;1), while X and Y are implications, that is, it is true in three cases and false in one. Therefore, the case (0;1) will correspond to three possible combinations of parameters. Case (1;1) – will correspond to nine possible combinations of parameters of the original equation. 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 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)*