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 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 the tasks of the exam, along with these functions, there is often an implication.
Consider a few simple tasks associated with 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 build a truth table for the function Ф, which allows you to say how many solutions the system has and what are the sets that give solutions.
In some tasks of the Unified State Examination on finding solutions to a system of logical equations, the number of variables reaches the value of 10. Then building a truth table becomes an almost unsolvable task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general way, 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 has two levels equation variables. The first level describes the first variable X 1 . Two branches of this level reflect the possible values of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values of the variable X 2 for which the equation takes the value true. Since the equation defines an implication, the branch on which X 1 has the value 1 requires that X 2 has the value 1 on that branch. The branch on which X 1 has the value 0 generates two branches with X 2 values equal to 0 and 1 The constructed tree specifies three solutions, on which the implication X 1 → X 2 takes the value 1. On each branch, the corresponding set of values of the variables is written out, which gives the solution to the equation.
These sets are: ((1, 1), (0, 1), (0, 0))
Let's continue building the decision tree by adding the following equation, the following implication X 2 → X 3 . The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable X 2 already has values in the tree, then on all branches where the variable X 2 has the value 1, the variable X 3 will also have the value 1. For such branches, the construction of the tree continues to the next level, but no new branches appear. The only branch where the variable X 2 has the value 0 will give a branch into two branches, where the variable X 3 will get the values 0 and 1. Thus, each addition of a new equation, given its specificity, adds one solution. Original first equation:
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
has 6 solutions. Here is what the complete decision tree for this equation looks like:
The second equation of our system is similar to the first:
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
The only difference is that the equation uses Y variables. This equation also has 6 solutions. Since each variable solution X i can be combined with each variable solution Y j , the total number of solutions is 36.
Note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves, written out on each branch of the tree.
Problem 19
How many different sets of values of boolean variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy all of the following conditions?
(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1
This task is a modification of the previous task. The difference is that another equation is added that relates the X and Y variables.
From the equation X 1 → Y 1 it follows that when X 1 has the value 1 (one such solution exists), then Y 1 has the value 1. Thus, there is one set on which X 1 and Y 1 have the values 1. With X 1 equal to 0, Y 1 can have any value, both 0 and 1. Therefore, each set with X 1 equal to 0, and there are 5 such sets, corresponds to all 6 sets with Y variables. Therefore, the total number of solutions is 31 .
Problem 20
(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1
Solution: Remembering the basic equivalence, we write our equation as:
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1
The cyclic chain of implications means that the variables are identical, so our equation is equivalent to:
X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1
This equation has two solutions when all X i are either 1 or 0.
Problem 21
(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1
Solution: Just as in Problem 20, we pass from cyclic implications to identities by rewriting the equation in the form:
(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1
Let's build a decision tree for this equation: 
Problem 22
How many solutions does the following system of equations have?
((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X4)) = 0
((X 3 ≡X 4) ˄ (X5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X5 ≡X 6)) = 0
((X5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X5 ≡X 6) ˄ ¬(X 7 ≡X8)) = 0
((X 7 ≡X 8) ˄ (X9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X9 ≡X10)) = 0
Answer: 64
Solution: Let's go from 10 variables to 5 variables by introducing the following change of variables:
Y 1 = (X 1 ≡ X 2); Y 2 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);
Then the first equation will take the form:
(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0
The equation can be simplified by writing it as:
(Y 1 ≡ Y 2) = 0
Turning to 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. General reception 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 on initial stage it is possible to establish a regularity in the appearance of new branches at each next level, as was done, for example, in problem 18.
In general, problems for finding solutions to a system of logical equations are good mathematical exercises.
If the problem is difficult to solve manually, then you can entrust the solution of the problem to the computer by writing an appropriate program for solving equations and systems of equations.
It is easy to write such a program. Such a program will easily cope with all the tasks offered in the exam.
Oddly enough, but the task of finding solutions to systems of logical equations is also difficult for a computer, it turns out that a computer has its limits. The computer can easily cope with tasks where the number of variables is 20-30, but it will start to think for a long time on larger tasks. The point is that the function 2 n that specifies the number of sets is an exponent that grows rapidly with n. So fast that a normal personal computer can't handle a task with 40 variables in a day.
C# program for solving logical equations
It is useful to write a program for solving logical equations 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 , which need to be sorted out. Using the basic functions of the C# language - negation, disjunction, conjunction and identity, it is easy to write a program that, for a given set of variables, calculates the value of a logical function corresponding to a logical equation or system of equations.
In such a program, you need to build a cycle by the number of sets, in the body of the cycle, by the set number, form the set itself, calculate the value of the function on this set, and if this value is equal to 1, then the set gives a solution to the equation.
The only difficulty that arises in the implementation of the program is related to the task of forming the set of variable values itself by the set number. The beauty of this task is that this seemingly difficult task, in fact, reduces to a simple problem 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 a number function variables fun. As a result, the SolveEquations function returns the number of solutions of the logical function, that is, the number of sets on which the function evaluates to true.
For schoolchildren, it is customary when for some function F(x) the input parameter x is an arithmetic, string or boolean type. In our case, a more powerful design is used. The SolveEquations function refers to functions higher order– 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)
Solution of the equation 1. Switch to the prefix form of the equation, replacing the notation of negations with ¬ 2. Build the header of a special type of truth table 3. Fill in the lines of the truth table for all combinations of A and B, substituting 0 or 1 instead of X. 4. Form a truth table for X = F (A, B) 5. According to the truth table, determine the type of function X, if necessary, using the methods for constructing SKNF and SDNF, which will be discussed below.
Construction of a special type of truth table ¬((A+B) (X A B))=¬(B+¬(X A))
Truth table X=F(A, B) ABX Corresponds to the negation of the implication B in A ANSWER:
Combination circuits of logical devices Basic elements (GOST): 1 A B Disjunction A B Equivalence & A B Conjunction M2 A B XOR
Combination circuits of logical devices Basic elements (GOST): 1 A B Implication & A B Schaeffer element & A B Coimplication 1 A B Webb element
Schematic example F 1 & 1 & & 1M2 B A
Scheme solution 1 Option - converting the scheme into a complex logical expression and then simplifying it according to the laws of logic. Option 2 - building a truth table and then, if necessary, building through SKNF or SDNF (see below). Consider the second option, as simpler and more understandable.
Construction of the truth table AB A + B + · B B · A + A B A + · ·
Truth table F(A, B) ABX Corresponds to the negation of the implication B in A ANSWER:
SDNF and SKNF (definitions) An elementary conjunction is a conjunction of several variables, taken with or without negation, and among the variables there may be the same Elementary disjunction is a disjunction of several variables, taken with or without negation, and among the variables there may be the same Any disjunction of elementary conjunctions we will call the disjunctive normal form (DNF) Any conjunction of elementary disjunctions will be called the conjunctive normal form (DNF)
PDNF and CKNF (definitions) A perfect disjunctive normal form (PDNF) is called a DNF in which there are no identical elementary conjunctions and all conjunctions consist of the same set of variables, in which each variable occurs only once (possibly with a negation). A perfect conjunctive normal form (PCNF) is called a CNF in which there are no identical elementary disjunctions and all disjunctions consist of the same set of variables, in which each variable occurs only once (possibly with a negation).
Algorithm for obtaining SDNF according to the truth table 1. Mark the rows of the truth table in the last column of which are 1. 2. Write out for each marked row the conjunction of all variables as follows: if the value of the variable in this row is 1, then include this variable itself in the conjunction, if equals 0, then its negation. 3. Connect all the resulting conjunctions into a disjunction. Algorithm for obtaining SKNF according to the truth table 1. Mark the rows of the truth table in the last column of which are 0. 2. Write out for each marked row the disjunction of all variables as follows: if the value of the variable in this row is 0, then include this variable itself in the conjunction, if equals 1, then its negation. 3. Connect all the resulting disjunctions into a conjunction.
Example of constructing CKNF XY F(X,Y) Mark zeros 2. Disjunctions: X + Y 3. Conjunctions: (X + Y) (X + Y)
UDC 004.023
Semenov Sergey Maksimovich
Vladivostok State University economy and service Russia. Vladivostok
On one method for solving systems of logical equations
A method for determining the number of solutions to a system of logical equations is considered. The method is based on the construction of a decision tree and the determination of recurrence relations for level N. The application of the developed method provides a constructive approach to solving the B15 USE problem.
Key words and phrases: systems of logical equations, decision tree, recurrence relations, B15, USE.
In practice, systems of logical equations are useful in the design of digital logic devices. One of the tasks of the Unified State Examination in Informatics is devoted to solving systems of logical equations. Unfortunately, various known methods for solving this problem do not allow one to form any one approach to solving this problem. As a result, solving the problem causes great difficulties for graduates. We propose a method for solving systems of logical equations, which allows the graduate to follow a well-defined algorithm. The idea of this method is presented in . We have applied and developed this idea (building a decision tree), almost without using truth tables for the entire tree. When solving various problems, it turned out that the number of solutions to many systems of logical equations is subject to recurrent relations, such as Fibonacci numbers, etc.
Systems of logical equations. We will adhere to the following notation: disjunction (+), conjunction ( ), exclusive OR (©), implication (->■), equivalence (=), negation (-■). In the figures, the dark circle denotes 1 and the light circle denotes 0. Fl is the number of solutions for X1 equal to 1. Fo is the number of solutions for X1 equal to 0. N is the number of variables in the system of equations. F(N) = F1(N) + F0(N) is the total number of solutions.
Task 1. You need to find the number of solutions to the system of equations (, test number 2)
First we set X1 = 1. Then for the first equation the values of X2 and X3 can be arbitrary. Thus, the tree is built up to the third level. Further, taking into account X2 and Xs, we choose X4. After that, the algorithm is repeated for each triple of variables (Fig. 1). Beginning with fourth level you can see that Fl(4)=Fl(3)+Fl(1), Fl(5)=Fl(4)+Fl(2). Thus, we get Fl(N) = Fl(N-1) + Fl(N-3) (1)
Rice. 1. Task 1
Equation (1) implies:
Bx(8) = 16 + 7 = 23,
Fl(9) = 23 + 11 = 34.
To build a tree from scratch, you can use the lower branch from Fig. 1. It is easy to see that it repeats the main tree, but with a shift to the right by 2, that is
So, F(9) = Fl(9) + Fo(9) = 34 + 16 = 50.
When building a decision tree, you can visually establish recurrence relationships to determine the number of decisions at the N level.
The principle of mathematical induction says: let there be a sequence of statements Fl, F2, F3 and let the first statement Fl be true. We can prove that the validity of FN implies that FN+l is true. Then all statements in this sequence are true.
Consider Fig. 2 for task 1.
d2 >3 x5 xb x7
Rice. 2. Decision tree analysis
Figure 2 highlights figures that have a common vertex (combinations of variable values) for the first five equations of the system. There are three variables involved in each equation, so the shapes are made up of the values of the three variables (three levels of the tree). In order to identify the figures, it would be possible to introduce notation. However, we will proceed as follows: each figure will be assigned the number of its constituent circles (variable values). Then we obtain the following equations for the sequence:
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
From Equation 4, it can be seen that the shapes for Equation N are composed of Equation N-1 shapes and Equation N-3 shapes. It is important that there are no other figures and cannot be for of this type equations, that is, the transition from one equation to another is carried out by increasing the number of figures from a limited set according to strictly defined rules. This fact is the main one in order to assert by induction that for the equation N + 1 the set of figures will consist of the figures of the equation N and the figures of the equation N-2.
Another way to identify figures is to determine the number of variable values at the last level for a given equation, that is, we need to go from the equation number to the tree level number, since we need to determine the number of solutions for the system of equations, Then for the constructed tree we get the sequence: 1, 2, 4 , 5, 7, 11, 16. For this sequence, the formula is valid: FN = FN-1 + FN-3.
In accordance with our reasoning, this formula will be true for N + 1, and by induction for any N.
The given method of proof can be used for any systems of this type. In practice, it is sufficient to determine the recurrence relation for level N, since it is based on a limited set of figures and methods for their transformations when moving from an equation corresponding to level N to an equation corresponding to level N + 1.
Task 2. It is necessary to find the number of solutions to the system of equations (, 4.16)
(X1=X2) + (X1 = X3) = 1 (X2=X3) + (X2 = X4) = 1 (X3=X4) + (X3 = X5) = 1 (X4=X5) + (X4 = X6) \u003d 1 (X5 \u003d X6) + (X5 \u003d X7) \u003d 1
XI X2 X3 >:1 X5 Xb X7
Rice. 3. Task 2
To obtain the number of solutions to task 2, it was possible not to build the decision tree completely (Fig. 3), since it is obvious that Fl(N) = N. Similarly, Fo(N) = N. Total F(7) = 7 + 7 = 14.
Task 3. You need to find the number of solutions to the system of equations (, test number 1)
(X1 ^ X2) ■ (X2 ^ X3) ■ (X3 ^ X4) ■ (X4 ^ X5) = 1
(Yl ^ Y2) ■ (Y2 ^ Yz) ■ (Yz ^ Y4) ■ (Y4 ^ Y5) = 1
(Yl ^ X1) ■ (Y2 ^ X2) ■ (Y3 ^ X3) ■ (Y4 ^ X4) ■ (Y5 ^ X5) = 1
Figure 4 shows the decision trees for X and Y and the corresponding truth tables.
Rice. 4. Task 3
From the first two equations, since X and Y are independent, it follows that the total number of solutions F(5) = 6 * 6 = 36. In order to take into account the third equation, it is necessary for each variable Y to calculate how many sets from table X do not satisfy equation. The implication Yi ^ Xi = 0 if Yi = 1 and Xi = 0. In other words, for Yl = 1, the third equation does not satisfy all rows from the table X, where X1 = 0. The number of such rows is 5. For Y2 = 1 such lines - 4, etc. The total number of rows that do not satisfy the third equation is 5 + 4 + 3 + 2 + 1 = 15.
Thus, the total number of feasible solutions is 36 - 15 = 21. Task 4. It is necessary to find the number of solutions to the system of equations (, 4.17.a)
(X1=X2) + (X1=X3)=(X2=X3)+(X2=X4)=(X4=X5)+(X4=X6)=(X5=X6)+(X5=X7)=(Xb \u003d X7) + (Xb \u003d X8) \u003d (X5 \u003d X6) \u003d 0
Rice. 5. Task 4
For this example, it is difficult to determine the final formula F(N), it is easier to build a decision tree to the end (or at least to X6). Figure 5 shows the constructed decision tree. As a result, we get F(8) = Fl(8) + Fo(8) = 5 + 5 = 10.
Task 5. It is necessary to find the number of solutions to the system of equations (, 4.17.b)
(X1=X2) + (X1 = X3) = 1 (X2=X3) + (X2 = X4) = 1 (X3 = X4) + (X3 = X5) = 1 (X4=X5) + (X4 = X6) =1 (X5 = X6) + (X5 = X7) = 1 (X6 = X8) = 1
For this example, as well as for the previous one, it is easier to build a decision tree to the end (Fig. 6). As a result, we get F(8) = Fl(8) + Fo(8) = 7 + 7 = 14.
Task 6. You need to find the number of solutions to the system of equations ([!]> 4.17.c)
(X!8 "X2) + (X2EXz) \u003d 1 (X2fXz) + (Xs \u003d X4) \u003d 1 (Xs8 "X4) + (X4 \u003d X5) \u003d 1 (X4 © X5) + (X5 \u003d Xb) \u003d 1 (X5fXb) + (Xb = X7) = 1 (Xb © X7) + (X7 = X8) = 1 The decision tree is shown in fig. 7.
XI X2 X3 X4 X5 X6 X7 X8 XI X2 X3 X4 X5 X6 X7 X8
Rice. 6. Task 5 Fig. 7. Task 6
For this system of equations, it was not possible to build a complete decision tree, since already from the third - fourth step it is clear that F1(N) = N. It is easy to see that Fo(N) can be obtained from a tree starting at the second level from zero. Then Fo(N) = N. So, F(8) = Fl(8) + Fo(8) = 8 + 8 = 16.
Task 7. You need to find the number of solutions to the system of equations
(X4EX5) + (X4 © X6) = 1 (X5 © Xb) + (X5 © X7) = 1
Note that if X! = X2 = 1, then the first equation is satisfied for Xz = 0. Let us first construct a tree for Xl = X2 = 1 (Fig. 8). Then the number of solutions Fl(N) = Fll(N) + Flo(N).
XI X2 X3 X4 X5 X6 X7 X8
Rice. 8. Task 7
Figure 8 shows that the number of solutions is F11(N) = F11(N-1) + F11(N-2). In other words, the number of solutions is described by Fibonacci numbers. The second branch of the tree for F10 can be omitted, since it is obtained from Fig. 1 starting from the second level. Then F10(N) = F11(N+1). Finally, we obtain that Fll(8) = 13 and Flo(8) = Fll(9) = 13 + 8 = 21. Then Fl(8) = Fll(8) + Flo(8) = 13 + 21 = 34.
In order to obtain F0(N), it is also not necessary to build a decision tree, since it is obtained from Fig. 1 starting from the third level. Then Fo(N) = Fll(N+2). Hence we obtain that Fo(8) = Fll(10) = Fll(9) + Fll(8) = 21 + 13 = 34. Thus, the total number of solutions F(8)= F1(8) + F0(8) = s4 + s4 = 68.
Task 8. It is necessary to find the number of solutions to the system of equations ([h], Task 2)
(X1 + X2) ^ (X3 + X4) = 1 (X3 + X4) ^ (X5 + X6) = 1 (X5 + X6) ^ (X7 + X8) = 1 (X7 + X8) ^ (X9 + X10) = 1
Let's make a substitution (X1 + X2) = Yl, etc. and get a system of equations:
^ ^ Y2 = 1 Y2 ^ Yg = 1 Yg ^ Y4 = 1 Y4 ^ Y5 = 1
The decision tree and truth table for this system are exactly the same as the tree and table shown in Fig. 4. Taking into account the substitution, we note that the expression (X1 + X2) is equal to one in three cases (except for the case when both variables are equal to zero).
Since the Y variables are independent, for the first row of the truth table shown in Fig. 4, the number of different combinations is 35, for the second row it is 34, and so on. The total number of different combinations is 35 + 34 + 33 + 32 + 31 + 30 = 364.
Task 9. It is necessary to find the number of solutions to the system of equations (, Task 4)
(^ ^ b) ■ (-X ^ X3) ■ No ^ X) ■ (-X ^ K3) = 1 No ^ Y2) ■ (Y1 ^ Y3) ■ (-G1 ^ Y4) ■ (Y1 ^ Y5) = 1 (-X + Y 1) ■ (-X + Y5) = 1
For X and Y we have the following decision trees
Rice. 9. Task 8
Given the third equation, we get the following four sets of combinations:
A - C: 4 * 4 = 16 ((-£1 + Y 1) ■ (-X + Y5) = (0 + 1) ■ (0 + 1) = 1) B - C: 4 * 4 = 16 ( (-X + Y 1) ■ (-X + Y5) = (1 + 1) ■ (1 + 1) = 1) A - D: = 0 (0 + 0) ■ (-X + Y5) = 0) B - D: 4 * 4 = 16 (1 + 0) ■ (1 + Y5) = 1) There are 48 sets of solutions in total.
Task 10. It is necessary to find the number of solutions to the system of equations (^1 = b) + (Xz = X)) ■ = b) + -fz = X4)) =1 ((Xz = X4) + (X5 = X6)) ■ ( -(X = X) + -(X = X6)) =1 ((X5 = X6) + ^7 = X")) ■ (-(X = X6) + -(^7 = X8)) =1
((X7 = X8) + (X9 = Xlo)) ■ (-^7 = X8) + = Xlo)) =1
(X5 = X) = Yz (X7 = X8) = Y4 (X9 = X10) = Y5
(Y^2) ■ (-b + ^)=1
(Y2+Yz) ■ № + -Тз)=1
(Yz+Y4) ■ № + ^)=1
(Y4+Y5) ■ (^4 + ^)=1
Figure 10 shows a decision tree
U1 U2 UZ U4 U5
Rice. 10. Task 10
Task 11. You need to find the number of solutions to the system of equations (, Example 2)
X1 + X2 \u003d 1 -X2 + Xs \u003d 1
Figure 11 shows a decision tree. We limited ourselves to four levels instead of ten, since it is obvious that F1(N) = 1 and F0(N) = N. Then P(N) = P1(N) + BoC) = 1 + N. ) = 1 + 10 = 11.
Rice. 11. Task 11
Task 12. You need to find the number of solutions to the system of equations (, Example h)
(X1 = X2) + (X2 = Xs) = 1
(X1 = X3) + (X3 = X4) (X1 = X4) + (X4 = X5) (X1 = X5) + (X5 = X6) (X1 = X6) + (X6 = X7) (X1 = X7) + (X7 = X8) (X1 = X) + (X8 = X9) (X1 = X9) + (X9 = X10) (X1 = X10) = 0
Rice. 12. Task 12
Having built a decision tree from "1" (we restrict ourselves to five levels), we note that Fl(N) = N. Moreover, the values of Xn consist of N-1 values of "0" and one value of "1". However, the last equation in our system forbids the value "1" for X10. Therefore, the number of solutions Fl(10) = 10 - 1. It is easy to see that the decision tree from "0" will be symmetrical (there will be ones instead of zeros). Therefore F0 = 10 - 1. Finally
F(N) = 2 x 9 = 18.
Task 13. You need to find the number of solutions to the system of equations (, Example 4)
- (X1 = X2) + (X3 = X4) = 1
- (X3 = X4) + (X5 = X) = 1
- (X = X) + (X7 = X) = 1
- (X7 = X8) + (X9 = X10) = 1
Let's replace:
(X1 = X2) = Yl
(X5 \u003d X) \u003d Yz
(X7 = X8) = Y4
(X9 = X10) = Y5
Let us rewrite the system of equations taking into account the replacement:
Task 11 shows that F(5) = 5 + 1 = 6. The truth table is shown in fig. 13.
U1 U2 UZ U4 U5
Rice. 13. Task 13
Considering the substitution, we note that the expression ^ = X2) is equal to one (or zero) in two cases (when the values of the variables coincide). Taking into account the independence of variables for each row of the table, we obtain that the number of solution sets is 25 = 32. The total number of solution sets is 6 * 32 = 192.
Task 14. You need to find the number of solutions to the system of equations (, Task 1)
((X = b) ■ (X3 = X4)) + (4X1 = b) ■ - (X = X)) = 0 ((X3 = X4) ■ (X5 = X6)) + (4X3 = X4) ■ - (X=X6))=0
((X5 = X) ■ (X7 = X8)) + (-(X = X6) ■ 4X7 = X8)) =0 ((X7 = X8) ■ (X9 = X',)) + (-(^7 = X8) ■ ^9 = Xlo)) =0
b) = Yl (X = ^4) = Y2
(X5 = X6) = Yz ^7 = X8) = Y4 ^9 = Xlo) = Y5
Let us rewrite the system of equations taking into account the replacement:
(UL) + (-U" ■ -U2) \u003d 0
(Y2 Yz) + (-Y2 ■ -Y3) \u003d 0 (Y3-Y4) + (-Y3 ■ -Y4) \u003d 0 (Y4-Y5) + (-Y4 ■ -Y5) \u003d 0
(Y2 = Yz) = 0 (Uz = Y4) = 0 (Y4 = Y5) = 0
Figure 14 shows a decision tree
U1 U2 UZ U4 U5
Rice. 14. Task 14
Considering the substitution, we note that the expression (X1 = X2) is equal to one (or zero) in two cases (when the values of the variables are the same). Taking into account the independence of variables for each tree, we obtain that the number of decision sets is 25 = z2. The total number of solution sets is 64.
Task 15. You need to find the number of solutions to the system of equations (, Task 2)
(X4 X5) + (-X4 -X5) + (X4 = X) = 1
(X5 X) + (-X -X6) + (X5 = X7) = 1
(X X7) + (-X -X7) + (X = X8) = 1
(X7 X) + (-X7 -X8) + (X7 = X9) = 1
(X8 X9) + (-X -X9) + (X8 = X10) = 1
(X1 = X2) + (X1 = Xs) = 1
(X = X3) + (X2 = X4) = 1
(Xs = X4) + (Xs = X5) = 1
(X4 = X5) + (X4 = X) = 1
(X5 = X6) + (X5 = X7) = 1
(X = X7) + (X6 = X8) = 1
(X7 = X8) + (X7 = X9) = 1
(X = X9) + (X8 = X10) = 1
But this system repeats the system from Task 5, only without the constraint condition and for N = 10. Then the number of solutions is F(N) = F1(N) + F0(N) = N + N. For N = 10 we get F(N )= 20.
Task 16. You need to find the number of solutions to the system of equations (, Task 3)
(X1 X2) + (-X1 -X2) + (X1 \u003d Xs) \u003d 1
(X2 Xs) + (-X -Xs) + (X2 \u003d X4) \u003d 1
(Xs X4) + (-Xs -X4) + (Xs = X5) = 1
(X4 X5) + (-X -X5) + (X4 = Xb) = 1
(X5 Xb) + (-X -Xb) + (X5 \u003d X7) \u003d 1
(Xb X7) + (-Xb -X7) + (Xb \u003d X8) \u003d 1
(X7 X8) + (-X7 -X8) + (X7 = X9) = 1
(X8 X9) + (-X8 -X9) + (X8 = X10) = 0
This system of equations, as in the previous task, can be rewritten as:
(XI = X2) + (XI = Xs) = 1 (X = Xs) + (X2 = X) = 1 (Xs = X) + (Xs = X5) = 1 (X = X5) + (X4 = Xb) = 1 (X5 = Xb) + (X5 = X7) = 1 (Xb = X7) + (Xb = X8) = 1 (X = X8) + (X7 = X9) = 1 (X = X9) + (X8 = Xxc) = 0
It is easy to check from the last equation that after N = 8 the number of solutions stops increasing. Then F(10) = F(8) = 8 + 8 = 16.
Task 17. You need to find the number of solutions to the system of equations (, Task 4)
(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 -Xs) = 1
(X2 Xs) + (-X2 -Xs) + (Xs X) + (-Xs ■ -X4) = 1
(Xz X) + (-Xz -X4) + (X4 X5) + (-X4 -X5) = 1
(X4 X) + (-X -X5) + (X5 Xb) + (-X5 -Xb) = 1
(X5 Xb) + (-X -Xb) + (Xb X7) + (-Xb ■ -X7) = 1
(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 -X8) = 1
(X7 X) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1
(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 1
Note that the system of equations can be rewritten as:
(X = X2) + (X = X3) = 1 (X = X3) + (X = X) = 1 (X3 = X4) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X5 = Xb) + (Xb = X7) = 1
(Xb = X7) + (X7 = X) = 1 (X7 = X8) + (X8 = X9) = 1 (Xv = X 9) + (X9 = X10) = 1
In Figure 15, the tree has been built up to the fifth level and it can be seen that the number of solutions is described by Fibonacci numbers, that is, Fl(N) = Fl(N-1) + Fl(N-2). Then Fl(10) = 89. It is easy to check that for F0(N) the tree is symmetric. Therefore Fo(10) = 89. B(10) = p1(10) + Po(10) = 89 + 89 = 178.
Rice. 15. Task 17
Task 18. You need to find the number of solutions to the system of equations (, Task 5)
(X1 X2) + (-X1 -X2) + (X2 Xs) + (-X2 ■ -Xs) = 1
(X2 Xs) + (-X -Xs) + (Xs X4) + (-Xs -X4) = 1
(Xs X4) + (-Xs -X4) + (X4 X5) + (-X4 ■ -X5) = 1
(X4 X5) + (-X4 -X5) + (X Xb) + (-X5 ■ -Xb) = 1
(X5 Xb) + (-X5 -Xb) + (Xb X7) + (-Xb ■ -X7) = 1
(Xb X7) + (-Xb -X7) + (X7 X8) + (-X7 ■ -X8) = 1
(X7 X8) + (-X7 -X8) + (X8 X9) + (-X8 -X9) = 1
(X8 X9) + (-X8 -X9) + (X9 X10) + (-X9 ■ -X10) = 0
Note that the system of equations can be rewritten as:
(X=X2) + (X2=X3) = 1 (X2=X3) + (X3=X4) = 1
(Xz = X) + (X4 = X5) = 1 (X = X5) + (X5 = Xb) = 1 (X = Xb) + (Xb = X7) = 1 (Xb = X7) + (X7 = X8) = 1 (X7 = X8) + (X8 = X9) = 1 (X8 = X 9) + (X = X10) = 0
Task 18 is similar to task 17, however, the last equation leads to the fact that starting from the seventh level, the number of solutions does not increase. As a result, F(10) = Fl(10) + Fo(10) = Fl(7) + Fo(7) = 21 + 21 = 42.
Task 19. You need to find the number of solutions to the system of equations (, Task b)
(X = X2) + (X = X10) = 1 (X = X3) + (X2 = X10) = 1 (X3 = X4) + (X = X10) = 1 (X = X5) + (X = X10) = 1 (X = Xb) + (X5 = X10) = 1 (Xb = X7) + (Xb = X10) = 1 (X7 = X) + (X = X10) = 1 (X8 = X9) + (X = X10) = 1 (X9 = X10) + (X9 = X10) = 1 (X = X10) = 0
- - - -*- - - -*-O
Rice. 1b. Task 19
The decision trees for obtaining F1(N) and F0(N) are shown in fig. 1b. However, the equation (X9 = X10) = 1 cannot be fulfilled. Therefore, the system of equations has no solutions.
Task 20. You need to find the number of solutions to the system of equations (, Task 7)
(X ^ X2) + (X ^ X3) = 1 (X2 ^ X3) + (X2 * X4) = 1 (X3 ^ X4) + (X3 ^ X5) = 1 (X ^ X5) + (X4 ^ Xb) = 1 (X5 ^ Xb) + (X5 ^ X7) = 1 (Xb ^ X7) + (Xb ^ X8) = 1
(X7^Xs) + (X7^X9) = 1 (Xs^X9) + (Xs^X10) = 1
Figure 17 shows a decision tree from "1".
Rice. 17. Task 20 18. Task 20
Instead of ten levels, we limited ourselves to five, since the task is similar to task 17. However, from "0" the tree will look different (Fig. 18).
Note that F0(N) = Fx(N+1) - 1. Then Fx(10) = 89, and F0(10) = Fx(11) - 1 = 144 - 1. So, F(10) = F1 (10) + F0(10) = 89 + 143 = 232.
In conclusion, we present a program in basic VBA, with which you can solve systems of logical equations. The program may be needed when compiling new systems of equations. Figure 19 shows a program that solves the system of equations from task 7.
In the program shown in Fig. 19, the array m and the variable c contain the values of the variables that satisfy the system of equations from task 7. The program gives the answer 68. The program uses the fact that the number of different sets of values n of logical variables is 2n. To get all the sets, you need to loop from 0 to 2n-1. The loop variable is converted to the binary system at each step, the result is written to the m array, and then the conditions from the system of equations are checked. To solve another system of equations, it is enough to change the dimension of the array m, change the value of the variable vg (equal to the dimension), and change the test conditions.
Dim m(S) As Integer, k As Integer, j. As Integer. _ j As Integer. N As Integer, vg As Integer Dim with As String vg=S j-0
For 1 To 2 ■""■ vg "Loop through ^ from 1 to 2n. where n=,.g For k = 1 To vg
N = ).- 1: Binary
Do "^Tiils N > 0 "Translate e binary system m(k) = N Mod 2 K = N ■ 2 k=k+ ! loop
Ifim(l) O m(2) Or m(l)0- ni(3)) And_ "Equation conditions (m(2) c= "" "The variable c at each step will contain the solution of the system For k= 1 Then vg c = c - Foimat(m(k)j Next k j-j-1 End If Next I. Ms^Eox i "Number of solutions VvVvVlVvVvv- -1 i Rice. 19. Program for task 7 1. Krylov S.S. USE 2014. Informatics. Thematic test tasks / S.S. Krylov, D.M. Ushakov. - M.: Publishing house "Exam". - 245 p. 2. Website of K.Yu. Polyakov. Access mode: http://kpolyakov.namd.-ru/download/inf-2011-14.pdf 3. Methodological certified course of the company "1C" "Preparation for the Unified State Examination in Informatics. Module 1". - M.: Publishing house "1C". - 218 p. 4. Successfully pass the exam in computer science. Access mode: http://infoegehelp.ru/index.php?Itemid=77&id=103&option=com_con- Lesson topic:
Solving logical equations
Educational -
create conditions for the development of cognitive interest of students, promote the development of memory, attention, logical thinking; Educational
: contribute to the education of the ability to listen to the opinions of others, education of will and perseverance to achieve the final results. Lesson type:
combined lesson
Equipment:
computer, multimedia projector, presentation 6. During the classes Repetition and updating of basic knowledge.
Checking homework (10 minutes)
In the previous lessons, we got acquainted with the basic laws of the algebra of logic, learned how to use these laws to simplify logical expressions. Let's check the homework on simplifying logical expressions: 1. Which of the following words satisfies the logical condition:
(first consonant → second consonant)٨
(last letter vowel → penultimate letter vowel)? If there are several such words, indicate the smallest of them. 1) ANNA 2) MARIA 3) OLEG 4) STEPAN Let us introduce the notation: A is the first letter of a consonant B is the second letter of a consonant S is the last vowel D - penultimate vowel Let's make an expression: Let's make a table: 2. Indicate which logical expression is equivalent to the expression
Let's simplify the writing of the original expression and the proposed options: 3. A fragment of the truth table of the expression F is given:
Let's determine the values of these expressions for the specified values of the arguments: Familiarization with the topic of the lesson, presentation of new material
(30 minutes)
We continue to study the basics of logic and the topic of our today's lesson "Solving logical equations." After studying this topic, you will learn the basic ways to solve logical equations, get the skills to solve these equations by using the language of logic algebra and the ability to compose a logical expression on the truth table. 1. Solve the logical equation (¬K
M) → (¬L
M
N)=0 Write your answer as a string of four characters: the values of the variables K, L, M, and N (in that order). So, for example, line 1101 corresponds to K=1, L=1, M=0, N=1. Solution: Let's transform the expression(¬K
M) → (¬L
M
N)
The expression is false when both terms are false. The second term is equal to 0 if M=0, N=0, L=1. In the first term, K = 0, since M = 0, and Answer: 0100 2. How many solutions does the equation have (indicate only the number in your answer)? Solution: transform the expression (A+B)*(C+D)=1 A+B=1 and C+D=1 Method 2: compiling a truth table Let's transform the original expression, open the brackets in order to get the disjunction of the conjunctions: (A+B)*(C+D)=A*C+B*C+A*D+B*D= Let's supplement the conjunctions to complete conjunctions (the product of all arguments), open the brackets: As a result, we obtain an SDNF containing 9 conjunctions. Therefore, the truth table for this function has a value of 1 on 9 rows out of 2 4 =16 sets of variable values. 3. How many solutions does the equation have (indicate only the number in your answer)? Let's simplify the expression: 3 way: construction of SDNF Consider the same conjunctions: As a result, we get an SDNF containing 5 conjunctions. Therefore, the truth table for this function has a value of 1 on 5 rows of 2 4 =16 sets of variable values. Building a logical expression according to the truth table: for each row of the truth table containing 1, we compose the product of the arguments, and the variables equal to 0 are included in the product with negation, and the variables equal to 1 - without negation. The desired expression F will be composed of the sum of the products obtained. Then, if possible, this expression should be simplified. Example: the truth table of an expression is given. Build a logical expression. 3. Homework (5 minutes)
Solve the equation: How many solutions does the equation have (answer only the number)? According to the given truth table, make a logical expression and simplify it. Municipal budgetary educational institution "Secondary school No. 18" urban district of the city of Salavat of the Republic of Bashkortostan Systems of logical equations
in the tasks of the exam in informatics
The section "Fundamentals of Algebra of Logic" in the tasks of the exam is considered one of the most difficult and poorly solved. The average percentage of completing tasks on this topic is the lowest and is 43.2. Course section Average percentage of completion by groups of tasks Coding information and measuring its quantity information modeling Number systems Fundamentals of Algebra of Logic Algorithmization and programming Fundamentals of information and communication technologies Based on the specification of KIM 2018, this block includes four tasks of different levels of complexity. № tasks Checked content elements Task difficulty level Ability to build truth tables and logic circuits Ability to search for information on the Internet Knowledge of basic concepts and laws mathematical logic Ability to build and transform logical expressions Task 23 is a high level of difficulty, therefore it has the lowest percentage of completion. Among the trained graduates (81-100 points) 49.8% completed the task, the averagely prepared (61-80 points) cope by 13.7%, the remaining group of students does not complete this task. The success of solving a system of logical equations depends on the knowledge of the laws of logic and on the precise application of methods for solving the system. Consider the solution of a system of logical equations by the mapping method. (23.154 Polyakov K.Yu.) How many different solutions does the system of equations have? ((x1
y1
)
(x2
y2
))
(x1
x2
)
(y1
y2
) =1
((x2
y2
)
(x3
y3
))
(x2
x3
)
(y2
y3
) =1
((x7
y7
)
(x8
y8
))
(x7
x8
)
(y7
y8
) =1
Where x1
,
x2
,…,
x8,
at1
,y2
,…,y8
- 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. All equations included in the system are of the same type, and four variables are included in each equation. Knowing x1 and y1, we can find all possible values of x2 and y2 that satisfy the first equation. Arguing in a similar way, from the known x2 and y2 we can find x3, y3 that satisfies the second equation. That is, knowing the pair (x1 , y1) and determining the value of the pair (x2 , y2) , we will find the pair (x3 , y3 ), which in turn will lead to the pair (x4 , y4 ) and so on. Let's find all solutions of the first equation. This can be done in two ways: to build a truth table, through reasoning and applying the laws of logic. Truth table: x 1
y 1 x2
y2 (x 1
y1)
(x 2
y2) (x 1
x2) (y 1
y2) (x 1
x2)
(y 1
y2) Building a truth table is laborious and time inefficient, so we use the second method - logical reasoning. The product is 1 if and only if each factor is 1. (x1
y1
)
(x2
y2
))=1
(x1
x2
) =1
(y1
y2
) =1
Consider the first equation. Following is equal to 1, when 0 0, 0 1, 1 1, then (x1 y1)=0 at (01), (10), then the pair (x2
y2
)
can be any (00), (01), (10), (11), and for (x1 y1)=1, i.e. (00) and (11) the pair (x2 y2)=1 takes the same values (00) and (11). We exclude from this solution those pairs for which the second and third equations are false, that is, x1=1, x2=0, y1=1, y2=0. (x1
,
y1
)
(x2
,
y2
)
Total number of pairs 1+1+1+22= 25
2)
(23.160 Polyakov K.Yu.) How many different solutions does a system of logical equations have (x
1
(x
2
y
2
))
(y
1
y
2
)
=
1
(x
2
(x
3
y
3
))
(y
2
y
3
)
=
1
...
(
x
6
(
x
7
y
7
))
(
y
6
y
7
)
=
1
x
7
y
7
=
1
Solution. 1) The equations are of the same type, so by the method of reasoning we will find all possible pairs (x1,y1), (x2,y2) of the first equation. (x1
(x2
y2
))=1
(y1
y2
)
= 1
The solution of the second equation are pairs (00), (01), (11). Let's find solutions to the first equation. If x1=0, then x2 , y2 - any, if x1=1, then x2 , y2 takes the value (11). Let's make connections between pairs (x1 , y1) and (x2 , y2). (x1
,
y1
)
(x2
,
y2
)
Let's make a table to calculate the number of pairs at each stage. 0
Taking into account the solutions of the last equation x
7
y
7
=
1,
we eliminate the pair (10). Find the total number of solutions 1+7+0+34=42 3)(23.180)
How many different solutions does the system of logical equations have (x1
x2
)
(x3
x4
) = 1
(x3
x4
)
(x5
x6
)
= 1
(x5
x6
)
(x7
x8
) = 1
(x7
x8
)
(x9
x10
)
= 1
x1
x3
x5
x7
x9
= 1
Solution. 1) The equations are of the same type, so by the method of reasoning we will find all possible pairs (x1,x2), (x3,x4) of the first equation. (x1
x2
)
(x3
x4
) = 1
We exclude from the solution the pairs that give 0 (1 0) in the following, these are the pairs (01, 00, 11) and (10). Compose links between pairs (x1,x2), (x3,x4)
.
Consider the same conjunctions:
,
