Unified State Examination in Informatics Logical Equations Solution Methods. Solving logic equations in mathematics
How to Solve Some Problems in Sections A and B of the Computer Science Exam
Lesson number 3. Logics. Logic functions. Solving Equations
A large number of USE tasks are devoted to the logic of propositions. To solve most of them, it is enough to know the basic laws of propositional logic, knowledge of the truth tables of logical functions of one and two variables. I will give the basic laws of propositional logic.
- Commutativity of disjunction and conjunction:
a ˅ b ≡ b ˅ a
a^b ≡ b^a - The distributive law regarding disjunction and conjunction:
a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c) - Negative negation:
¬(¬a) ≡ a - Consistency:
a ^ ¬a ≡ false - Exclusive third:
a ˅ ¬a ≡ true - De Morgan's laws:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b - Simplification:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ true ≡ a
a ˄ false ≡ false - Absorption:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a - Replacing the implication
a → b ≡ ¬a ˅ b - Change of identity
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)
Representation of logical functions
Any logical function of n variables - F(x 1 , x 2 , ... x n) can be defined by a truth table. Such a table contains 2 n sets of variables, for each of which the value of the function on this set is specified. This method is good when the number of variables is relatively small. Even for n > 5, the representation becomes poorly visible.
Another way is to define the function by some formula, using well-known fairly simple functions. The system of functions (f 1 , f 2 , … f k ) is called complete if any logical function can be expressed by a formula containing only functions f i .
The system of functions (¬, ˄, ˅) is complete. Laws 9 and 10 are examples of how implication and identity are expressed through negation, conjunction, and disjunction.
In fact, the system of two functions is also complete - negation and conjunction or negation and disjunction. Representations follow from De Morgan's laws that allow expressing a conjunction through negation and disjunction and, accordingly, expressing a disjunction through negation and conjunction:
(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)
Paradoxically, a system consisting of only one function is complete. There are two binary functions - anticonjunction and antidisjunction, called Pierce's arrow and Schaeffer's stroke, representing a hollow system.
The basic functions of programming languages usually include identity, negation, conjunction and disjunction. IN USE tasks along with these functions there is often an implication.
Let's look at a few simple tasks related to logical functions.
Task 15:
A fragment of the truth table is given. Which of the three given functions corresponds to this fragment?
| x1 | x2 | x3 | x4 | F |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
- (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
- (¬X 1 ˄ X 2) ˅ (¬X 3 ˄ X 4)
- ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)
Feature number 3.
To solve the problem, you need to know the truth tables of basic functions and keep in mind the priorities of operations. Let me remind you that conjunction (logical multiplication) has a higher priority and is performed before disjunction (logical addition). When calculating, it is easy to see that the functions with numbers 1 and 2 on the third set have the value 1 and for this reason do not correspond to the fragment.
Task 16:
Which of the following numbers satisfies the condition:
(digits, starting with the most significant digit, go in descending order) → (number - even) ˄ (lowest digit - even) ˄ (highest digit - odd)
If there are several such numbers, indicate the largest.
- 13579
- 97531
- 24678
- 15386
The condition is satisfied by the number 4.
The first two numbers do not satisfy the condition for the reason that the lowest digit is odd. A conjunction of conditions is false if one of the terms of the conjunction is false. For the third number, the condition for the highest digit is not met. For the fourth number, the conditions imposed on the minor and major digits of the number are met. The first term of the conjunction is also true, since an implication is true if its premise is false, which is the case here.
Problem 17: Two witnesses testified as follows:
First Witness: If A is guilty, then B is certainly guilty, and C is innocent.
Second witness: Two are guilty. And one of the remaining ones is definitely guilty and guilty, but I can’t say exactly who.
What conclusions about the guilt of A, B, and C can be drawn from the evidence?
Answer: It follows from the testimony that A and B are guilty, but C is innocent.
Solution: Of course, the answer can be given based on common sense. But let's look at how this can be done strictly and formally.
The first thing to do is to formalize the statements. Let's introduce three Boolean variables, A, B, and C, each of which is true (1) if the corresponding suspect is guilty. Then the testimony of the first witness is given by the formula:
A → (B ˄ ¬C)
The testimony of the second witness is given by the formula:
A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))
The testimonies of both witnesses are assumed to be true and represent the conjunction of the corresponding formulas.
Let's build a truth table for these readings:
| A | B | C | F1 | F2 | F 1 F 2 |
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
The summary evidence is true in only one case, leading to a clear answer - A and B are guilty, and C is innocent.
It also follows from the analysis of this table that the testimony of the second witness is more informative. Only two things follow from the truth of his testimony. possible options A and B are guilty and C is innocent, or A and C are guilty and B is innocent. The testimony of the first witness is less informative - there are 5 various options corresponding to his testimony. Together, the testimonies of both witnesses give an unequivocal answer about the guilt of the suspects.
Logic equations and systems of equations
Let F(x 1 , x 2 , …x n) be a logical function of n variables. The logical equation is:
F(x 1, x 2, ... x n) \u003d C,
The constant C has the value 1 or 0.
A logical equation can have from 0 to 2n different solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table on which the function F takes the value true (1). The remaining sets are solutions of the equation for C, zero. We can always consider only equations of the form:
F(x 1 , x 2 , …x n) = 1
Indeed, let the equation be given:
F(x 1 , x 2 , …x n) = 0
In this case, you can go to the equivalent equation:
¬F(x 1 , x 2 , …x n) = 1
Consider a system of k logical equations:
F 1 (x 1, x 2, ... x n) \u003d 1
F 2 (x 1, x 2, ... x n) \u003d 1
F k (x 1 , x 2 , …x n) = 1
The solution of the system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to the system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions F:
Ф = F 1 ˄ F 2 ˄ … F k
If the number of variables is small, for example, less than 5, then it is not difficult to construct a truth table for the function Ф, which allows you to say how many solutions the system has and what are the sets that give solutions.
In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, which is different from enumeration, which allows solving such problems.
In the problems proposed in the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from enumeration of all variants of a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique for solving this problem is as follows. We are not interested in all sets, but only those on which the function Ф has the value 1. Instead of constructing a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies a set on which the function Ф has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.
What is a binary decision tree and how it is built, I will explain with examples of several tasks.
Problem 18
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy a system of two equations?
Answer: The system has 36 different solutions.
Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation, depending on 5 variables – x 1 , x 2 , …x 5 . The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents a conjunction of logical functions. The converse statement is also true - the conjunction of conditions can be considered as a system of equations.
Let's build a decision tree for the implication (x1→ x2), the first term of the conjunction, which can be considered as the first equation. Here is what the graphic representation of this tree looks like:
The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable X 1 . Two branches of this level reflect the possible values of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values of the variable X 2 for which the equation takes the value true. Since the equation defines an implication, the branch on which X 1 has the value 1 requires that X 2 has the value 1 on that branch. The branch on which X 1 has the value 0 generates two branches with X 2 values equal to 0 and 1 The constructed tree defines three solutions, on which the implication X 1 → X 2 takes the value 1. On each branch, the corresponding set of variable values is written, which gives the solution to the equation.
These sets are: ((1, 1), (0, 1), (0, 0))
Let's continue building the decision tree by adding the following equation, the following implication X 2 → X 3 . The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable X 2 already has values in the tree, then on all branches where the variable X 2 has the value 1, the variable X 3 will also have the value 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable X 2 has the value 0 will give a branch into two branches, where the variable X 3 will get the values 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
has 6 solutions. Here is what the complete decision tree for this equation looks like:
The second equation of our system is similar to the first:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution X i can be combined with each variable solution Y j , the total number of solutions is 36.
Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.
Problem 19
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.
It follows from the equation X 1 → Y 1 that when X 1 has the value 1 (one such solution exists), then Y 1 has the value 1. Thus, there is one set on which X 1 and Y 1 have the values 1. 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 equivalence, we write our equation as:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
A cyclic chain of implications means that the variables are identical, so our equation is equivalent to:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
This equation has two solutions when all X i are either 1 or 0.
Problem 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Solution: Just as in problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Let's build a decision tree for this equation: 
Problem 22
How many solutions does the following system of equations have?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
Answer: 64
Solution: Let's go from 10 variables to 5 variables by introducing the following change of variables:
Y 1 = (X 1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);
Then the first equation will take the form:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
The equation can be simplified by writing it as:
(Y 1 ≡ Y 2) = 0
Passing to the traditional form, we write the system after simplifications in the form:
¬(Y 1 ≡ Y 2) = 1
¬(Y 2 ≡ Y 3) = 1
¬(Y 3 ≡ Y 4) = 1
¬(Y 4 ≡ Y 5) = 1
The decision tree for this system is simple and consists of two branches with alternating variable values:
Returning to the original X variables, note that each value of the Y variable corresponds to 2 values of the X variables, so each solution in the Y variables generates 2 5 solutions in the X variables. Two branches generate 2 * 2 5 solutions, so the total number of solutions is 64.
As you can see, each task for solving a system of equations requires its own approach. A common trick is to perform equivalent transformations to simplify the equations. A common technique is the construction of decision trees. The applied approach partially resembles the construction of a truth table with the peculiarity that not all sets of possible values of variables are constructed, but only those on which the function takes the value 1 (true). Often in the proposed problems there is no need to build a complete decision tree, since already at the initial stage it is possible to establish the regularity of the appearance of new branches at each next level, as was done, for example, in problem 18.
In general, problems for finding solutions to a system of logical equations are good mathematical exercises.
If the problem is difficult to solve manually, then you can entrust the solution of the problem to the computer by writing an appropriate program for solving equations and systems of equations.
It is easy to write such a program. Such a program will easily cope with all the tasks offered in the exam.
Oddly enough, but the task of finding solutions to systems of logical equations is also difficult for a computer, it turns out that a computer has its limits. A computer can easily cope with tasks where the number of variables is 20-30, but it will start to think for a long time on larger tasks. The point is that the function 2 n that specifies the number of sets is an exponent that grows rapidly with n. So fast that a normal personal computer can't handle a task with 40 variables in a day.
C# program for solving logical equations
Writing a program for solving logical equations is useful for many reasons, if only because it can be used to check the correctness of your own solution to the USE test problems. Another reason is that such a program is an excellent example of a programming problem that meets the requirements for category C problems in the USE.
The idea of constructing a program is simple - it is based on a complete enumeration of all possible sets of variable values. Since the number of variables n is known for a given logical equation or system of equations, the number of sets is also known - 2 n that need to be sorted out. Using the basic functions of the C# language - negation, disjunction, conjunction and identity, it is easy to write a program that, for a given set of variables, calculates the value of a logical function corresponding to a logical equation or system of equations.
In such a program, you need to build a cycle by the number of sets, in the body of the cycle, by the number of the set, form the set itself, calculate the value of the function on this set, and if this value is equal to 1, then the set gives a solution to the equation.
The only difficulty that arises in the implementation of the program is related to the task of forming the set of variable values itself by the set number. The beauty of this task is that this seemingly difficult task, in fact, comes down to a simple task that has already arisen repeatedly. Indeed, it is enough to understand that the set of values of variables corresponding to the number i, consisting of zeros and ones, represents the binary representation of the number i. So the complex task of obtaining a set of values of variables by the set number is reduced to the well-known problem of converting a number into a binary system.
This is how the C# function that solves our problem looks like:
///
/// program for counting the number of solutions
/// logical equation (system of equations)
///
///
/// logical function - method,
/// whose signature is set by the DF delegate
///
/// number of variables
///
static int SolveEquations(DF fun, int n)
bool set = new bool[n];
int m = (int)Math.Pow(2, n); //number of sets
int p = 0, q = 0, k = 0;
//Full enumeration by the number of sets
for (int i = 0; i< m; i++)
//Formation of the next set — set,
//given by the binary representation of the number i
for (int j = 0; j< n; j++)
k = (int)Math.Pow(2, j);
//Calculate function value on set
To understand the program, I hope that the explanations of the idea of the program and the comments in its text will suffice. I will dwell only on the explanation of the heading of the above function. The SolveEquations function has two input parameters. The fun parameter specifies a logical function corresponding to the equation or system of equations being solved. The n parameter specifies the number of variables in the fun function. As a result, the SolveEquations function returns the number of solutions of the logical function, that is, the number of sets on which the function evaluates to true.
For schoolchildren, it is customary when for some function F(x) the input parameter x is a variable of arithmetic, string or boolean type. In our case, a more powerful design is used. The SolveEquations function refers to higher-order functions - functions of type F(f), whose parameters can be not only simple variables, but also functions.
The class of functions that can be passed as a parameter to the SolveEquations function is defined as follows:
delegate bool DF(bool vars);
This class includes all functions that are passed as a parameter a set of values of boolean variables specified by the vars array. The result is a Boolean value representing the value of the function on this set.
In conclusion, I will give a program in which the SolveEquations function is used to solve several systems of logical equations. The SolveEquations function is part of the following ProgramCommon class:
class ProgramCommon
delegate bool DF(bool vars);
static void Main(string args)
Console.WriteLine("Function And Solutions - " +
SolveEquations(FunAnd, 2));
Console.WriteLine("Function has 51 solutions - " +
SolveEquations(Fun51, 5));
Console.WriteLine("Function has 53 solutions - " +
SolveEquations(Fun53, 10));
static bool FunAnd(bool vars)
return vars && vars;
static bool Fun51(bool vars)
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
f = f && (!vars || vars);
static bool Fun53(bool vars)
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && ((vars == vars) || (vars == vars));
f = f && (!((vars == vars) || (vars == vars)));
Here is what the results of the solution for this program look like:
10 tasks for independent work
- Which of the three functions are equivalent:
- (X → Y) ˅ ¬Y
- ¬(X ˅ ¬Y) ˄ (X → ¬Y)
- ¬X ˄ Y
- A fragment of the truth table is given:
| x1 | x2 | x3 | x4 | F |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
Which of the three functions corresponds to this fragment:
- (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
- (X 1 → X 3) ˄ X 2 ˅ X 4
- X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
- The jury consists of three people. The decision is made if the chairman of the jury votes for it, supported by at least one of the jury members. Otherwise, no decision is made. Build a logical function that formalizes the decision making process.
- X wins over Y if four coin tosses come up heads three times. Define a boolean function describing payoff X.
- Words in a sentence are numbered starting from one. A sentence is considered well-formed if the following rules are met:
- If an even numbered word ends in a vowel, then the next word, if it exists, must begin with a vowel.
- If an odd numbered word ends in a consonant, then the next word, if it exists, must start with a consonant and end with a vowel.
Which of the following sentences are correct: - Mom washed Masha with soap.
- The leader is always a model.
- The truth is good, but happiness is better.
- How many solutions does the equation have:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1 - List all solutions of the equation:
(a → b) → c = 0 - How many solutions does the following system of equations have:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1 - How many solutions does the equation have:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1
Answers to tasks:
- The functions b and c are equivalent.
- The fragment corresponds to function b.
- Let the boolean variable P take the value 1 when the chairman of the jury votes "for" the decision. Variables M 1 and M 2 represent the opinion of the jury members. The logical function that specifies the adoption of a positive decision can be written as follows:
P ˄ (M 1 ˅ M 2) - Let the boolean variable P i take on the value 1 when the i-th coin toss comes up heads. The logical function that defines the payoff X can be written as follows:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4)) - Offer b.
- The equation has 3 solutions: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a=0; b=1; c=0)
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, after simplifying each equation.
1. Method of change of variables.
The introduction of new variables makes it possible to simplify the system of equations by reducing the number of unknowns.New variables must be independent of each other. After solving the simplified system, it is necessary to return to the original variables again.
Consider the application of this method on 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: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Attention! Each of their variables x1, x2, …, x10 must be included in only one of the new variables A, B, C, D, E, i.e. 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 of 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 \u003d 1 also has 2 roots. Let's arrange the number of roots on the decision tree:
To find the number of solutions for 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 complexity of solving systems of logical equations lies in the cumbersomeness of the complete decision tree. The reasoning method allows you not to build the whole tree completely, but at the same time understand how many branches it will have. Let's consider this method on concrete examples.
Example 1 How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
x1\/y1 =1
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 under which the given 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 a third condition. Let us construct a decision tree for the first and second equations.
To represent the decision tree of the system from the first and second equations, it is necessary to continue each branch of the first tree 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. Note on the first tree the number of branches of the tree"at" , which satisfy the third equation:
Let us clarify: for the fulfillment of the third condition at 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"at" . And only for one branch of the tree"X" (right) fit all branches of the tree"at". Thus, the complete tree of the entire system contains 11 branches. Each branch represents one solution to the original system of equations. So the whole 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 boolean 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 of the 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 be the same as x10. For the first equation to be equal to 1, the equality must hold(X1 ≡ X2)=1, i.e. x1 must match x2.
Let's build a decision 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 is the same as x3); at x10=0 and at x2=1 bracket(X2 ≡ X10)=0 , so bracket (X2 ≡ X3) must be equal to 1 (i.e. x2 is the same as x3):
Arguing in this way, we construct 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 boolean variables x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 are there that satisfy all of the following conditions?
(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 decision tree of the 1st equation:
Consider the second equation:
- When x1=0 : second and third brackets will be 0; for the first bracket to be equal to 1, must y1=1 , z1=1 (i.e. in this case - 1 solution)
- With x1=1 : first parenthesis will be 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 for y1=1 and z1=0 (i.e. in this case - 2 solutions).
Similarly for the rest of the equations. Note the number of solutions obtained for each node of the tree:
To find out the number of solutions for each branch, we multiply the obtained numbers separately for each branch (from left to right).
1 branch: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 solution
2 branch: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 solutions
3rd branch: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 solutions
4 branch: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 solutions
5 branch: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 solutions
Let's add the numbers obtained: a total of 31 solutions.
Answer: 31.
3. Regular 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 boolean variables x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 are there that satisfy all of the following conditions?
¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0
¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0
¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0
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 following equation has 2 more roots than the previous one.
4 equation has 12 roots;
Equation 5 has 14 roots
8 equation has 20 roots.
Answer: 20 roots.
Sometimes the number of roots grows according to the law of Fibonacci numbers.
Solving a system of logical equations requires a creative approach.
Let be a logical function of n variables. The logical equation is:
The constant C has the value 1 or 0.
A logical equation can have from 0 to various solutions. If C is equal to 1, then the solutions are all those sets of variables from the truth table on which the function F takes the value true (1). The remaining sets are solutions of the equation for C equal to zero. We can always consider only equations of the form:
Indeed, let the equation be given:
In this case, you can go to the equivalent equation:
Consider a system of k logical equations:
The solution of the system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to the system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions:
If the number of variables is small, for example, less than 5, then it is not difficult to construct a truth table for the function , which allows you to say how many solutions the system has and what are the sets that give solutions.
In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, other than enumeration, that allows solving such problems.
In the problems proposed in the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from enumeration of all variants of a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique for solving this problem is as follows. We are not interested in all sets, but only those on which the function has the value 1. Instead of building a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies the set on which the function has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.
What is a binary decision tree and how it is built, I will explain with examples of several tasks.
Problem 18
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy a system of two equations?
Answer: The system has 36 different solutions.
Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation depending on 5 variables - . The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents a conjunction of logical functions. The converse statement is also true - the conjunction of conditions can be considered as a system of equations.
Let's build a decision tree for the implication () - the first term of the conjunction, which can be considered as the first equation. Here is what the graphic image of this tree looks like
The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable . Two branches of this level reflect the possible values of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values of the variable for which the equation takes the value true. Since the equation defines an implication, the branch on which it has a value of 1 requires that it has a value of 1 on that branch. The branch on which it has a value of 0 generates two branches with values equal to 0 and 1. The constructed tree defines three solutions, on where the implication takes the value 1. On each branch, the corresponding set of values of the variables is written out, which gives a solution to the equation.
These sets are: ((1, 1), (0, 1), (0, 0))
Let's continue building the decision tree by adding the following equation, the following implication. The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable already has values in the tree, then on all branches where the variable has a value of 1, the variable will also have a value of 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable has the value 0 will give a branch into two branches, where the variable will get the values 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:
has 6 solutions. Here is what the complete decision tree for this equation looks like:
The second equation of our system is similar to the first:
The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution can be combined with each variable solution, the total number of solutions is 36.
Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.
Problem 19
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.
It follows from the equation that when it has the value 1 (one such solution exists), then it has the value 1. Thus, there is one set on which and have the values 1. When equal to 0, it can have any value, both 0 and and 1. Therefore, each set with equal to 0, and there are 5 such sets, corresponds to all 6 sets with variables Y. Therefore, the total number of solutions is 31.
Problem 20
Solution: Remembering the basic equivalence, we write our equation as:
A cyclic chain of implications means that the variables are identical, so our equation is equivalent to:
This equation has two solutions when all are either 1 or 0.
Problem 21
How many solutions does the equation have:
Solution: Just as in problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:
Let's build a decision tree for this equation:
Problem 22
How many solutions does the following system of equations have?
The use of equations is widespread in our lives. They are used in many calculations, construction of structures and even sports. Equations have been used by man since ancient times and since then their use has only increased. In mathematics, there are certain tasks that are devoted to the logic of propositions. To solve this kind of equation, you must have a certain amount of knowledge: knowledge of the laws of propositional logic, knowledge of the truth tables of logical functions of 1 or 2 variables, methods for transforming logical expressions. In addition, you need to know the following properties of logical operations: conjunctions, disjunctions, inversions, implications and equivalences.
Any logical function from \ variables - \ can be specified by a truth table.
Let's solve some logical equations:
\[\rightharpoondown X1\vee X2=1 \]
\[\rightharpoondown X2\vee X3=1\]
\[\rightharpoondown X3\vee X4=1 \]
\[\rightharpoondown X9\vee X10=1\]
Let's start the solution with \[X1\] and determine what values \u200b\u200bthis variable can take: 0 and 1. Next, consider each of the above values \u200b\u200band see what \[X2.\] can be in this case
As can be seen from the table, our logical equation has 11 solutions.
Where can I solve a logical equation online?
You can solve the equation on our website https: // site. Free online solver will allow you to solve an online equation of any complexity in seconds. All you have to do is just enter your data into the solver. You can also watch the video instruction and learn how to solve the equation on our website. And if you have any questions, you can ask them in our Vkontakte group http://vk.com/pocketteacher. Join our group, we are always happy to help you.
Service assignment. The online calculator is designed for constructing a truth table for a logical expression.Truth table - a table containing all possible combinations of input variables and their corresponding output values.
The truth table contains 2n rows, where n is the number of input variables, and n+m are columns, where m are the output variables.
Instruction. When entering from the keyboard, use the following conventions:
For example, the logical expression abc+ab~c+a~bc must be entered like this: a*b*c+a*b=c+a=b*cTo enter data in the form of a logical diagram, use this service.
Logic function input rules
- Use the + sign instead of v (disjunction, OR).
- Before the logical function, you do not need to specify the function designation. For example, instead of F(x,y)=(x|y)=(x^y) you would simply type (x|y)=(x^y) .
- Maximum amount variables is 10 .
The design and analysis of computer logic circuits is carried out with the help of a special section of mathematics - the algebra of logic. In the algebra of logic, three main logical functions can be distinguished: "NOT" (negation), "AND" (conjunction), "OR" (disjunction).
To create any logical device, it is necessary to determine the dependence of each of the output variables on the current input variables, such a dependence is called a switching function or a function of the logic algebra.
A logic algebra function is called fully defined if all 2 n of its values are given, where n is the number of output variables.
If not all values are defined, the function is called partially defined.
A device is called logical if its state is described using a function of the algebra of logic.
The following methods are used to represent the logic algebra function:
In algebraic form, it is possible to construct a diagram of a logical device using logical elements. 
Figure 1 - Diagram of a logical device
All operations of the algebra of logic are defined truth tables values. The truth table determines the result of performing an operation for all possible x logical values of the original statements. The number of options that reflect the result of applying the operations will depend on the number of statements in the logical expression. If the number of statements in the logical expression is N, then the truth table will contain 2 N rows, since there are 2 N different combinations of possible argument values.
Operation NOT - logical negation (inversion)
The logical operation is NOT applied to a single argument, which can be either a simple or a complex logical expression. The result of the operation is NOT the following:- if the original expression is true, then the result of its negation will be false;
- if the original expression is false, then the result of its negation will be true.
not A, Ā, not A, ¬A, !A
The result of the negation operation is NOT determined by the following truth table:
| A | not A |
| 0 | 1 |
| 1 | 0 |
The result of the negation operation is true when the original statement is false, and vice versa.
Operation OR - logical addition (disjunction, union)
The logical OR operation performs the function of combining two statements, which can be either a simple or a complex logical expression. Statements that are initial for a logical operation are called arguments. The result of the OR operation is an expression that will be true if and only if at least one of the original expressions is true.Designations used: A or B, A V B, A or B, A||B.
The result of the OR operation is determined by the following truth table:
The result of the OR operation is true when A is true, or B is true, or both A and B are true, and false when both A and B are false.
Operation AND - logical multiplication (conjunction)
The logical operation AND performs the function of the intersection of two statements (arguments), which can be either a simple or a complex logical expression. The result of the AND operation is an expression that is true if and only if both of the original expressions are true.Symbols used: A and B, A Λ B, A & B, A and B.
The result of the AND operation is determined by the following truth table:
| A | B | A and B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The result of operation AND is true if and only if statements A and B are both true, and false in all other cases.
Operation "IF-THEN" - logical consequence (implication)
This operation connects two simple logical expressions, of which the first is a condition, and the second is a consequence of this condition.Applied designations:
if A, then B; A attracts B; if A then B; A → B.
Truth table:
| A | B | A→B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The result of the operation of consequence (implication) is false only when premise A is true and conclusion B (consequence) is false.
Operation "A if and only if B" (equivalence, equivalence)
Applicable designation: A ↔ B, A ~ B.Truth table:
| A | B | A↔B |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Modulo 2 addition operation (XOR, exclusive or, strict disjunction)
Notation used: A XOR B, A ⊕ B.Truth table:
| A | B | A⊕B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The result of an equivalence operation is true only if both A and B are both true or both false.
Precedence of logical operations
- Actions in brackets
- Inversion
- Conjunction (&)
- Disjunction (V), Exclusive OR (XOR), modulo 2 sum
- Implication (→)
- Equivalence (↔)
Perfect disjunctive normal form
Perfect disjunctive normal form of a formula(SDNF) is a formula equivalent to it, which is a disjunction of elementary conjunctions, which has the following properties:- Each logical term of the formula contains all the variables included in the function F(x 1 ,x 2 ,...x n).
- All logical terms of the formula are different.
- No logical term contains a variable and its negation.
- No logical term in a formula contains the same variable twice.
For each function, SDNF and SKNF are uniquely defined up to a permutation.
Perfect conjunctive normal form
Perfect conjunctive normal form of a formula (SKNF) is a formula equivalent to it, which is a conjunction of elementary disjunctions that satisfies the following properties:- All elementary disjunctions contain all variables included in the function F(x 1 ,x 2 ,...x n).
- All elementary disjunctions are distinct.
- Each elementary disjunction contains a variable once.
- No elementary disjunction contains a variable and its negation.
