Solving logical equations. Solve Logic Equation

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

Lesson #3. Logics. Logic functions. Solving equations

A large number of Unified State Exam problems are devoted to propositional logic. To solve most of them, it is enough to know the basic laws of propositional logic, knowledge of the truth tables of logical functions of one and two variables. I will give the basic laws of propositional logic.

1. Commutativity of disjunction and conjunction:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Distributive law regarding disjunction and conjunction:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negation of negation:
   ¬(¬a) ≡ a
4. Consistency:
   a ^ ¬a ≡ false
5. Exclusive third:
   a ˅ ¬а ≡ true
6. De Morgan's laws:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Simplification:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Absorption:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Replacement of implication
   a → b ≡ ¬a ˅ b
10. Replacement of identity
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Representation of logical functions

Any logical function of n variables - F(x 1, x 2, ... x n) can be specified by a truth table. Such a table contains 2n sets of variables, for each of which the value of a function on this set is specified. This method is good when the number of variables is relatively small. Already for n > 5 the representation becomes poorly visible.

Another way is to define the function by some formula using known fairly simple functions. A system of functions (f 1, f 2, ... f k) is called complete if any logical function can be expressed by a formula containing only functions f i.

The system of functions (¬, ˄, ˅) is complete. Laws 9 and 10 are examples demonstrating how implication and identity are expressed through negation, conjunction and disjunction.

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

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

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

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

Let's look at a few simple problems involving logical functions.

Problem 15:

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

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Function number 3.

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

Problem 16:

Which of the given numbers satisfies the condition:

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

If there are several such numbers, indicate the largest.

1. 13579
2. 97531
3. 24678
4. 15386

The condition is satisfied by the number number 4.

The first two numbers do not satisfy the condition for the reason that the lowest digit is odd. A conjunction of conditions is false if one of the terms of the conjunction is false. For the third number, the condition for the highest digit is not met. For the fourth number, the conditions imposed on the low and high digits of the number are met. The first term of the conjunction is also true, since the implication is true if its premise is false, which is the case here.

Problem 17: Two witnesses gave the following testimony:

First witness: If A is guilty, then B is even more guilty, and C is innocent.

Second witness: Two are guilty. And one of the remaining ones is definitely guilty and guilty, but I can’t say who exactly.

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

Answer: From the testimony it follows that A and B are guilty, and C is innocent.

Solution: Of course, the answer can be given based on common sense. But let's look at how this can be done strictly and formally.

The first thing to do is to formalize the statements. Let's introduce three logical variables - A, B and C, each of which has the value true (1) if the corresponding suspect is guilty. Then the testimony of the first witness is given by the formula:

A → (B ˄ ¬C)

The testimony of the second witness is given by the formula:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

The testimony of both witnesses is assumed to be true and represents the conjunction of the corresponding formulas.

Let's build a truth table for these readings:

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

From the analysis of this table it also follows that the testimony of the second witness is more informative. From the truth of his testimony, only two possible options follow - A and B are guilty, and C is innocent, or A and C are guilty, and B is innocent. The testimony of the first witness is less informative - there are 5 different options corresponding to his testimony. Together, the testimony of both witnesses gives a clear answer about the guilt of the suspects.

Logical equations and systems of equations

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

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

The constant C has the value 1 or 0.

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

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

Indeed, let the equation be given:

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

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

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

Consider a system of k logical equations:

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

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

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

The solution to a system is a set of variables on which all equations of the system are satisfied. In terms of logical functions, to obtain a solution to a system of logical equations, one should find a set on which the logical function Ф is true, representing the conjunction of the original functions F:

Ф = F 1 ˄ F 2 ˄ … F k

If the number of variables is small, for example, less than 5, then it is not difficult to construct a truth table for the function Ф, which allows us to say how many solutions the system has and what are the sets that provide solutions.

In some USE problems on finding solutions to a system of logical equations, the number of variables reaches 10. Then constructing a truth table becomes an almost impossible task. Solving the problem requires a different approach. For an arbitrary system of equations, there is no general method other than enumeration that allows solving such problems.

In the problems proposed on the exam, the solution is usually based on taking into account the specifics of the system of equations. I repeat, apart from trying out all the options for a set of variables, there is no general way to solve the problem. The solution must be built based on the specifics of the system. It is often useful to carry out a preliminary simplification of a system of equations using known laws of logic. Another useful technique for solving this problem is as follows. We are not interested in all sets, but only those on which the function Ф has the value 1. Instead of building a complete truth table, we will build its analogue - a binary decision tree. Each branch of this tree corresponds to one solution and specifies a set on which the function Ф has the value 1. The number of branches in the decision tree coincides with the number of solutions to the system of equations.

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

Problem 18

How many different sets of values ​​of the logical variables x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 are there that satisfy the system of two equations?

Answer: The system has 36 different solutions.

Solution: The system of equations includes two equations. Let's find the number of solutions for the first equation, depending on 5 variables - x 1, x 2, ...x 5. The first equation can in turn be considered as a system of 5 equations. As has been shown, the system of equations actually represents the conjunction of logical functions. The converse is also true: a conjunction of conditions can be considered as a system of equations.

Let's build a decision tree for the implication (x1→ x2) - the first term of the conjunction, which can be considered as the first equation. This is what a graphical representation of this tree looks like:

The tree consists of two levels according to the number of variables in the equation. The first level describes the first variable X 1 . Two branches of this level reflect the possible values ​​of this variable - 1 and 0. At the second level, the branches of the tree reflect only those possible values ​​of the variable X 2 for which the equation is true. Since the equation specifies an implication, a branch on which X 1 has the value 1 requires that on that branch X 2 has the value 1. A branch on which X 1 has the value 0 produces two branches with the values ​​of X 2 equal to 0 and 1 The constructed tree defines three solutions, on which the implication X 1 → X 2 takes the value 1. On each branch, a corresponding set of variable values ​​is written out, giving a solution to the equation.

These sets are: ((1, 1), (0, 1), (0, 0))

Let's continue building the decision tree by adding the following equation, the following implication X 2 → X 3 . The specificity of our system of equations is that each new equation of the system uses one variable from the previous equation, adding one new variable. Since the variable X 2 already has values ​​in the tree, then on all branches where the variable X 2 has a value of 1, the variable X 3 will also have a value of 1. For such branches, the construction of the tree continues to the next level, but new branches do not appear. The single branch where the variable X 2 has the value 0 will branch into two branches where the variable X 3 will receive the values ​​0 and 1. Thus, each addition of a new equation, given its specifics, adds one solution. Original first equation:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
has 6 solutions. Here's 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 solution for the variables X i can be combined with each solution for the variables Y j , the total number of solutions is 36.

Please note that the constructed decision tree gives not only the number of solutions (according to the number of branches), but also the solutions themselves written on each branch of the tree.

Problem 19

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

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

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

From the equation X 1 → Y 1 it follows that when X 1 has the value 1 (one such solution exists), then Y 1 also has the value 1. Thus, there is one set on which X 1 and Y 1 have the values ​​1. When X 1 equal to 0, Y 1 can have any value, both 0 and 1. Therefore, each set with X 1 equal to 0, and there are 5 such sets, corresponds to all 6 sets with Y variables. Therefore, the total number of solutions is 31 .

Problem 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Solution: Remembering the basic equivalences, we write our equation as:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

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

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

This equation has two solutions when all X i are either 1 or 0.

Problem 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Solution: Just as in problem 20, we move from cyclic implications to identities, rewriting the equation in the form:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Let's build a decision tree for this equation:

Problem 22

How many solutions does the following system of equations have?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

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

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

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

Answer: 64

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

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Then the first equation will take the form:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

The equation can be simplified by writing it as:

(Y 1 ≡ Y 2) = 0

Moving on to the traditional form, we write the system after simplifications in the form:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

The decision tree for this system is simple and consists of two branches with alternating variable values:

Returning to the original X variables, note that for each value in the Y variable there are 2 values ​​in the X variables, so each solution in the Y variables generates 2 5 solutions in the X variables. The two branches generate 2 * 2 5 solutions, so the total number of solutions is 64.

As you can see, each problem of solving a system of equations requires its own approach. A common technique is to perform equivalent transformations to simplify equations. A common technique is to construct decision trees. The approach used is partially reminiscent of constructing a truth table with the peculiarity that not all sets of possible values ​​of variables are constructed, but only those on which the function takes the value 1 (true). Often in the proposed problems there is no need to build a complete decision tree, since already at the initial stage it is possible to establish the pattern of the appearance of new branches at each subsequent level, as was done, for example, in problem 18.

In general, problems involving finding solutions to a system of logical equations are good mathematical exercises.

If the problem is difficult to solve manually, then you can entrust the solution to the computer by writing an appropriate program for solving equations and systems of equations.

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

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

Program in C# language for solving logical equations

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

The idea of ​​building a program is simple - it is based on a complete search of all possible sets of variable values. Since for a given logical equation or system of equations the number of variables n is known, then the number of sets is also known - 2 n which need to be sorted out. Using the basic functions of the C# language - negation, disjunction, conjunction and identity, it is not difficult to write a program that, for a given set of variables, calculates the value of the logical function corresponding to a logical equation or system of equations.

In such a program, you need to build a loop based on the number of sets, in the body of the loop, using the number of the set, form the set itself, calculate the value of the function on this set, and if this value is 1, then the set gives a solution to the equation.

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

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

///

///

/// logical function - method,

/// whose signature is specified by the DF delegate

///

/// number of variables

/// number of solutions

static int SolveEquations(DF fun, int n)

bool set = new bool[n];

int m = (int)Math.Pow(2, n); //number of sets

int p = 0, q = 0, k = 0;

//Complete search by number of sets

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

//Formation of the next set - set,

//specified by the binary representation of the number i

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

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

//Calculate the value of the function on the set

To understand the program, I hope the explanations of the program's idea and comments in its text are sufficient. I will only focus on explaining the title of the given function. The SolveEquations function has two input parameters. The fun parameter specifies a logical function corresponding to the equation or system of equations being solved. The n parameter specifies the number of fun variables. As a result, the SolveEquations function returns the number of solutions of the logical function, that is, the number of those sets on which the function evaluates to true.

It is common for schoolchildren when some function F(x) has an input parameter x that is a variable of arithmetic, string or logical type. In our case, a more powerful design is used. The SolveEquations function refers to higher-order functions - functions of type F(f), whose parameters can be not only simple variables, but also functions.

The class of functions that can be passed as a parameter to the SolveEquations function is specified as follows:

delegate bool DF(bool vars);

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

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

class ProgramCommon

delegate bool DF(bool vars);

static void Main(string args)

Console.WriteLine("And Functions - " +

SolveEquations(FunAnd, 2));

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

SolveEquations(Fun51, 5));

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

SolveEquations(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51(bool vars)

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

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's what the solution results for this program look like:

10 tasks for independent work

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

Which of the three functions does this fragment correspond to:

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

Answers to problems:

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

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 Unified State Examination problems in computer science

The section “Fundamentals of Algebra of Logic” in the Unified State Examination tasks is considered one of the most difficult and difficult to solve. The average percentage of tasks completed on this topic is the lowest and is 43.2.

Based on the 2018 KIM specification, this block includes four tasks of different difficulty levels.

Task 23 is high in difficulty level, therefore it has the lowest percentage of completion. Among prepared graduates (81-100 points), 49.8% completed the task; moderately prepared graduates (61-80 points) completed 13.7%; the remaining group of students did not complete this task.

The success of solving a system of logical equations depends on knowledge of the laws of logic and on the precise application of methods for solving the system.

Let's consider solving a system of logical equations using 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 - logical variables? The answer does not need to list all the different sets of variable values ​​for which this equality holds. As an answer, you need to indicate the number of such sets.

Solution. All equations included in the system are of the same type, and each equation includes four variables. Knowing x1 and y1, we can find all possible values ​​of x2 and y2 that satisfy the first equation. Reasoning 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 to the first equation. This can be done in two ways: construct a truth table, through reasoning and the application of the laws of logic.

Truth table:

Constructing a truth table is labor-intensive and time-inefficient, so we use the second method - logical reasoning. The product is equal to 1 if and only if each factor is equal to 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Let's look at the first equation. The consequence is equal to 1 when 0 0, 0 1, 1 1, which means (x1 y1)=0 for (01), (10), then the pair (x2  y2 ) can be any (00), (01), (10), (11), and when (x1 y1) = 1, that is, (00) and (11) the pair (x2 y2) = 1 takes the same values (00) and (11). Let us 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.

Total number of pairs 1+1+1+22= 25

2) (23.160 Polyakov K.Yu.) How many different solutions does the 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 using reasoning we will find all possible pairs (x1,y1), (x2,y2) of the first equation.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

The solution to the second equation is the 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).

Let's create a table to calculate the number of pairs at each stage.

Taking into account the solutions of the last equation x 7  y 7 = 1, let's exclude pair (10). Find the total number of solutions 1+7+0+34=42

3)(23.180) How many different solutions does a 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 using reasoning we will find all possible pairs (x1,x2), (x3,x4) of the first equation.

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

Let us exclude from the solution the pairs that in the sequence give 0 (1 0), these are the pairs (01, 00, 11) and (10).

Let's make connections between pairs (x1,x2), (x3,x4)

Instructions. When entering from the keyboard, use the following conventions:

Rules for entering a logical function

1. Instead of the v (disjunction, OR) symbol, use the + sign.
2. There is no need to specify a function designation before a logical function. For example, instead of F(x,y)=(x|y)=(x^y) you need to simply enter (x|y)=(x^y) .
3. The maximum number of variables is 10.

The design and analysis of computer logic circuits is carried out using a special branch of mathematics - logic algebra. 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 existing input variables; this dependence is called a switching function or a logic algebra function.
A logical algebra function is called completely defined if all 2n 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 logic algebra function.
The following methods are used to represent a logical algebra function:
In algebraic form, you can build a circuit of a logical device using logical elements.


Figure 1 - Logic device diagram

All operations of the algebra of logic are defined truth tables values. The truth table determines the result of an operation for everyone is possible x logical values ​​of the original statements. The number of options reflecting the result of applying operations will depend on the number of statements in the logical expression. If the number of statements in a 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)

• 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.

OR operation - logical addition (disjunction, union)

Operation AND - logical multiplication (conjunction)

Operation “IF-THEN” - logical consequence (implication)

Operation “A if and only if B” (equivalence, equivalence)

Operation “Addition modulo 2” (XOR, exclusive or, strict disjunction)

Priority of logical operations

• Actions in parentheses
• Inversion
• Conjunction (&)
• Disjunction (V), Exclusive OR (XOR), sum modulo 2
• Implication (→)
• Equivalence (↔)

Perfect disjunctive normal form

1. Each logical term of the formula contains all the variables included in the function F(x 1,x 2,...x n).
2. All logical terms of the formula are different.
3. Not a single logical term contains a variable and its negation.
4. No logical term in a formula contains the same variable twice.

Perfect conjunctive normal form

1. All elementary disjunctions contain all the variables included in the function F(x 1 ,x 2 ,...x n).
2. All elementary disjunctions are different.
3. Each elementary disjunction contains a variable once.
4. Not a single elementary disjunction contains a variable and its negation.

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

Solution.

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

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

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

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

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

Answer: 30

How many different solutions does the equation have?

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

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

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

Solution.

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

Let's consider the first subformula:

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

Let's consider the second subformula

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

Let's consider the third subformula

1) M → J = 1 therefore,

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

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

Let's combine:

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

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

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

Let's combine:

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

c) M = 0 J = 0.

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

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

Answer: 4 + 4 = 8.

Answer: 8

How many different solutions does the equation have?

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

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

Solution.

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

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

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

K + L = 1 and L M N = 0

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

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

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

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

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

Answer: 10

How many different solutions does the equation have?

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

Solution.

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

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

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

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

Answer: 7.

Answer: 7

How many different solutions does the equation have?

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

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

Solution.

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

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

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

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

Hence,

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

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

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

Therefore, there is only one solution to the equation.

Answer: 1

How many different solutions does the equation have?

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

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

Solution.

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

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

Each equation gives 3 solutions.

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

Therefore the answer is 9.

Answer: 9

How many different solutions does the equation have?

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

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

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

Solution.

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

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

Hence,

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

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

Therefore: total solutions 2*3 = 6.

Total 6 solutions.

Answer: 6

How many different solutions does the equation have?

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

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

Solution.

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

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

Logical OR is true in three cases.

Option 1.

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

Option 2.

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

Therefore the answer is 4.

Answer: 4

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

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

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

Solution.

Please note that this complex statement consists of three simple ones

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

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

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

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

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

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

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

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

Answer: 44.

Answer: 44

Construct a truth table for a logical function

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

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

Solution.

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

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

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

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

4) fill in the table columns:

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

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

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

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

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

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

6) convert this number to the decimal system:

Answer: 171

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

Solution.

An equation is an operation of implication between two relations:

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

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

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

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

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

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

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

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

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

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

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

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

So the answer is 2.

Answer: 2

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

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

Solution.

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

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

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

Answer: 7

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

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

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

Solution.

Duplicates task 3584.

Answer: 1000

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

Solution.

Let's apply the implication transformation:

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

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

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

Let's transform:

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

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

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

Answer: 0100

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

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

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

Solution.

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

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

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

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

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

Duplicates the task

Answer: 1000

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

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

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

Solution.

(1) (P ∨ ¬Q) = 0

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

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

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

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

Answer: 0100

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

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

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

Solution.

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

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

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

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

Consider the second expression:

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

Answer: 1001.

Answer: 1001

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

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

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

Solution.

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

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

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

It follows that K = 0.

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