23 Task on computer science. Your formula for success

14.10.2020

Interactive simulator 23 EGE demo 2017

for impediting complete solution, placed at the very end of this page.

There were questions, doubts or comments appeared, write ...

And the second with a condition deployed specifically for underscore seeming complexity I. huge difference , as number of equations and their content .

Demonstration option EGE 2015 Informatics and ICT task 23.

In response, you do not need to list all different sets of variable values \u200b\u200bx1, x2, ... x8, y1, y2, ... y8, for which this system equalities. In the quality of the answer, you need to specify the number of such sets.

And I just stay, despite this very seeming complexity of this task, show. How its solution is easily reduced to solving such a first.

Take the first equation (x1 | x2) & ((x1 & x2) → x3) & (¬x1 | y1) \u003d 1 and with the help of a truth table we find all its solutions. After that it remains to highlight (delete) all rows having 0 in the final column

Analyzing the table, we build pairs of pairs x 1x 2 to x 2x 3, noting that the first pair with values \u200b\u200b01 is displayed in the second with the value 10 twice (for meaningy 1 \u003d 1 andy 1 \u003d 0 From here and double red arrow, the display is built for pairs with values \u200b\u200b01-11)

According to this figure, we build the rules of the display, for which we find the number of solutions for the first six equations for which it is enough to fill out the following table

From where we find that the first six equations have only 53 solutions.

And we still have to deal with the remaining "added" two equations
(x7 | x8) & (¬x7 | y7) \u003d 1
(¬x8 | y8) \u003d 1
Let us dwell on the first of them and, without going into deep reasoning, fill the truth table for it, where the number 1 denotes the conditionally the first bracket, and the two - the second and the lid - their work, respectively.

The table shows that the pair x7x8

does not have solutions at 00 (which means the following: pair x7x8 with value 00 will appear in y7. With the same values \u200b\u200b0 times (i.e. not displayed)

it has two solutions at a value 01 (Y7 \u003d 0 and Y7 \u003d 1, which means the following: the number of solutions for the x7x8 pair with the value 01, displayed in y7. - doubles

it has one solution with 10 and 11 values, i.e. The number of solutions in the display with these values \u200b\u200bwill not change.

We remain, filling out the corresponding cells found values, find the number of solutions for the first seven equations

And here he is the most responsible step, therefore, in order not to perform unnecessary errors, we again resort to the construction of the truth table, but already for the eighth equation
(¬x8 | y8) \u003d 1

From the truth table we built, it can be seen that

if x8 \u003d 0, then y8 has two solutions 0 and 1 (i.e., the number of solutions when mapping double)

if x8 \u003d 1, then y8 has one solution (that is, the number of solutions when displaying is unchanged)

this means that if x8 is 0, then in the x8 map to Y8 at values \u200b\u200b00 and 10, the number of solutions doubles, and in the case when x8 is 1 in the x8 map to Y8 with values \u200b\u200b01 and 11, the number of solutions remains unchanged. This is also displayed in the final table and summing up all the values \u200b\u200bof the Y8 column. We find the desired result.

Correct answer: 61

Full decision-tip for task 23 Demovrssia EGE 2017 on computer science

Task directory.
Systems of logical equations containing the same type equations

Sorting Basic First Simple First Complicated Popularity First Next First
Touch testing for these tasks
Return to the task catalog
Printing and copying version in MS Word

Ski-so-it is a single-person-bouquet of know-Chered Lo-Childle, x2, x3, x4, x5, x6 , x7, x8 ko-rye wovel-tet-ryu-ryu-du-linen below aslo-vi-yam?

(x1≡x2) -\u003e (x2≡x3) \u003d 1

(x2≡x3) -\u003e (x3≡x4) \u003d 1

(x6≡x7) -\u003e (x7≡x8) \u003d 1

In from-ve not necessary ne-re-numbers are all once-personal on-b-rys of the signs of PE-PER -MEN, X1, X2, X3, X4, X5, X6, X7, X8 with which You are-floor-not-on Dan-Naya Si-Ste-Ma Ra-Venation. In Ka-Thieves, you need to indicate such on-bouts.

Decision.

We write the variables into the line: x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8. The implication is false only when a lie from the truth should be. The condition is not performed if another digit is present in the series after a pair of identical numbers. For example, "11101 ...", which means non-fulfillment of the second condition.

Consider combinations of variables that satisfy all conditions. We will write down the options in which all the numbers alternate, such two: 10101010 and 01010101. Now for the first option, starting from the end, we will increase the number of numbers repetitive in a row (as much as possible). We repel the resulting combinations: "1010 1011; 1010 1111; 1011 1111; 1111 1111; 1010 1000; 1010 0000; 1000 0000; 0000 0000 »There are nine such combinations, including the initial. Similar to the second option: "0101 0101; 0101 0100; 0101 0000; 0100 0000; 0000 0000; 0101 0111; 0101 1111; 0111 1111; 1111 1111 "- such combinations also nine. Note that combinations 0000 0000 and 1111 1111 are taken into account twice. Thus, we obtain 9 + 9 - 2 \u003d 16 solutions.

Answer: 16.

¬ (x 1 ≡ x 2) ∧ (x 1 ∨ x 3) ∧ (¬x 1 ∨ ¬x 3) \u003d 0

¬ (x 2 ≡ x 3) ∧ (x 2 ∨ x 4) ∧ (¬x 2 ∨ ¬x 4) \u003d 0

¬ (x 8 ≡ x 9) ∧ (x 8 ∨ x 10) ∧ (¬x 8 ∨ ¬x 10) \u003d 0

In response not necessary

Decision.

Consider the first equation.

At x 1 \u003d 1, two cases are possible: x 2 \u003d 0 and x 2 \u003d 1. In the first case x 3 \u003d 1. In the second - x 3 or 0, or 1. At x 1 \u003d 0, two cases are also possible: x 2 \u003d 0 and x 2 \u003d 1. In the first case x 3 or 0, or 1. In the second - x 3 \u003d 0. Thus, the equation has 6 solutions (see Figure).

Consider a system of two equations.

Let x 1 \u003d 1. At x 2 \u003d 0, only one case is possible: x 3 \u003d 1, the variable x 4 \u003d 0. At x 2 \u003d 1, two cases are possible: x 3 \u003d 0 and x 3 \u003d 1. In the first case x 4 \u003d 1, in the second - x 4 or 0, or 1. Total we have 4 options.

Let x 1 \u003d 0. With x 2 \u003d 1, only one case is possible: x 3 \u003d 0, the variable x 4 \u003d 1. At x 2 \u003d 0, two cases are possible: x 3 \u003d 0 and x 3 \u003d 1. In the first case x 4 or 1, or 0, in the second - x 4 \u003d 0. Total we have 4 options.

Thus, the system of two equations has 4 + 4 \u003d 8 options (see Figure).

The system of three equations will have 10 solutions, from four - 12. The system of eight equations will have 20 solutions.

Answer: 20.

Source: EGE on computer science 05/30/2013. Basic wave. Centre. Option 1.

How many different sets of values \u200b\u200bof logical variables x 1, x 2, ... x 10, which satisfy all the conditions listed below?

(x 1 ∧ ¬x 2) ∨ (¬x 1 ∧ x 2) ∨ (x 3 ∧ x 4) ∨ (¬x 3 ∧ ¬x 4) \u003d 1

(x 3 ∧ ¬x 4) ∨ (¬x 3 ∧ x 4) ∨ (x 5 ∧ x 6) ∨ (¬x 5 ∧ ¬x 6) \u003d 1

(x 7 ∧ ¬x 8) ∨ (¬x 7 ∧ x 8) ∨ (x 9 ∧ x 10) ∨ (¬x 9 ∧ ¬x 10) \u003d 1

In response not necessary List all the different sets of values \u200b\u200bof the variables x 1, x 2, ... x 10 at which this system of equalities is made. As an answer, you need to specify the number of such sets.

Decision.

The first equation has 12 solutions. The second equation is associated with the first only via variables x 3 and x 4. Based on the tree of solutions for the first equation, we drink pairs of values \u200b\u200bof the variables x 3 and x 4, which satisfy the first equation and indicate the number of such pairs of values.

number par values	x 3.	x 4.
× 4.	1	1
× 4.	0	0
× 2.	1	0
× 2.	0	1

Since equations are identical to accuracy to the indices of variables, the tree of solutions of the second equation is similar to the first. Consequently, the pair of values \u200b\u200bx 3 \u003d 1 and x 4 \u003d 1 generates two sets of variables x 3, ..., x 6, satisfying the second equation. Since among the sets of solutions of the first partition equation, four, we obtain 4 · 2 \u003d 8 sets of variables x 1, ..., x 6, satisfying the system of two equations. Correcting similarly to a pair of values \u200b\u200bx 3 \u003d 0 and x 4 \u003d 0, we obtain 8 sets of variables x 1, ..., x 6. A pair x 3 \u003d 1 and x 4 \u003d 0 generates four solutions of the second equation. Since among sets of solutions of the first equation of these steam data, we obtain 2 · 4 \u003d 8 sets of variables x 1, ..., x 6, satisfying the system of two equations. Similarly for x 3 \u003d 0 and x 4 \u003d 1 - 8 sets of solutions. A total system of two equations has 8 + 8 + 8 + 8 \u003d 32 solutions.

Conducting similar arguments for a system of three equations, we obtain 80 sets of variables x 1, ..., x 8 satisfying the system. For a system of four equations, there are 192 sets of variables x 1, ..., x 10 satisfying the system.

Answer: 192.

Source: EGE on computer science 07/08/2013. Second wave. Option 501.

the guest 17.12.2013 18:50

Recalted 3 times, it turns out that after 2 equations 34 solutions, and you have 32, we have 8 + 12 + 8 + 6, and you have 8 + 8 + 8 + 8

Peter Murzin

Give your solution completely. Write how you get 12 and 6.

Ivan Grebenshchikov 12.06.2016 20:51

In general, it is possible to solve this problem much easier. If notice (x1 ∧ ¬x2) ∨ (¬x1 ∧ x2) identically ¬ (x1 \u003d\u003d x2) and (x3 ∧ x4) ∨ (¬x3 ∧ ¬x4) identically (x3 \u003d\u003d x4), then substituting into the initial Equation, we obtain: ¬ (x1 \u003d\u003d x2) ∨ (x3 \u003d\u003d x4) \u003d 1. However, this expression can be converted and obtain (x1 \u003d\u003d x2) → (x3 \u003d\u003d x4) \u003d 1.

By converting in a similar way, all expressions are obtained:

(x1 \u003d\u003d x2) → (x3 \u003d\u003d x4) \u003d 1

(x3 \u003d\u003d x4) → (x5 \u003d\u003d x6) \u003d 1

(x7 \u003d\u003d x8) → (x9 \u003d\u003d x10) \u003d 1

Replacing (x1 \u003d\u003d x2) on A1, (x3 \u003d\u003d x4) on a3, ..., (x9 \u003d\u003d x10) on A9 We get sets of solutions for A-out:

A1 A3 A5 A7 A9

Each A-out corresponds to (regardless of the value) a pair of pairs of values \u200b\u200bof i-Togo and I + 1st X-owl \u003d\u003e (2 * 2 * 2 * 2 * 2) * 6 (since six sets of solutions for A- Its) \u003d 192

How many different sets of values \u200b\u200bof logical variables x 1, x 2, ... x 10, which satisfy all the conditions listed below?

(x 1 ∧ x 2) ∨ (¬x 1 ∧ ¬x 2) ∨ (¬x 3 ∧ x 4) ∨ (x 3 ∧ ¬x 4) \u003d 1

(x 3 ∧ x 4) ∨ (¬x 3 ∧ ¬x 4) ∨ (¬x 5 ∧ x 6) ∨ (x 5 ∧ ¬x 6) \u003d 1

(x 7 ∧ x 8) ∨ (¬x 7 ∧ ¬x 8) ∨ (¬x 9 ∧ x 10) ∨ (x 9 ∧ ¬x 10) \u003d 1

Decision.

We construct the tree solutions for the first equation.

Thus, the first equation has 12 solutions.

The second equation is associated with the first only via variables x 3 and x 4. Based on the tree of solutions for the first equation, we drink pairs of values \u200b\u200bof the variables x 3 and x 4, which satisfy the first equation and indicate the number of such pairs of values.

number par values	x 3.	x 4.
× 2.	1	1
× 2.	0	0
× 4.	1	0
× 4.	0	1

Since equations are identical to accuracy to variable indices, the tree solutions of the second equation is similar to the first (see Fig.). Consequently, the pair of values \u200b\u200bx 3 \u003d 1 and x 4 \u003d 1 generates four sets of variables x 3, ..., x 6 satisfying the second equation. Since among sets of solutions of the first partition equation, two, we obtain 4 · 2 \u003d 8 sets of variables x 1, ..., x 6, satisfying the system of two equations. Correcting similarly to a pair of values \u200b\u200bx 3 \u003d 0 and x 4 \u003d 0, we obtain 8 sets of variables x 1, ..., x 6. A pair x 3 \u003d 1 and x 4 \u003d 0 generates two solutions of the second equation. Since among sets of solutions of the first partition equation, four, we obtain 2 · 4 \u003d 8 sets of variables x 1, ..., x 6, satisfying the system of two equations. Similarly for x 3 \u003d 0 and x 4 \u003d 1 - 8 sets of solutions. A total system of two equations has 8 + 8 + 8 + 8 \u003d 32 solutions.

The third equation is connected with the second only through the variables x 5 and x 6. Tree solutions similar. Then, for the system of three equations, each pair of values \u200b\u200bx 5 and x 6 will generate the number of solutions in accordance with the tree (see Fig.): Steam (1, 0) gives 2 solutions, steam (1, 1) will generate 4 solutions, and t. d.

From the decision of the first equation, we know that the pair of values \u200b\u200bx 3, x 4 (1, 1) is found in decisions twice. Consequently, for a system of three equations, the number of solutions for the pair x 3, x 4 (1, 1) is 2 · (2 \u200b\u200b+ 4 + 4 + 2) \u003d 24 (see Fig.). Taking advantage of the table above, we calculate the number of solutions for the remaining pairs x 3, x 4:

4 · (2 \u200b\u200b+ 2) \u003d 16

2 · (2 \u200b\u200b+ 4 + 4 + 2) \u003d 24

4 · (2 \u200b\u200b+ 2) \u003d 16

Thus, for a system of three equations, we have 24 + 16 + 24 + 16 \u003d 80 sets of variables x 1, ..., x 8 satisfying the system.

For a system of four equations, there are 192 sets of variables x 1, ..., x 10 satisfying the system.

Answer: 192.

1. General

Complexity: High.

Approximate time solutions (For those who will perform part 2):5-10 minutes

Subject: Basics of logic

Substitute: Analysis of logical expressions

What is checked: Ability to analyze logical expressions. The ability to describe in the natural language the many values \u200b\u200bof logical variables in which the specified set of logical expressions is true.

How to look like a task:

For example, so.

Find the number of solutions of the system of logical equations. It is assumed that the student will describe many solutions of the system, after which it will calculate how many elements are in this set.

2. An example of a task

2.1. The task.

Task 2012-B15-1.

How many different sets of logical variables x 1, x 2, ... x 9, x 10who satisfy all the conditions listed below?

((x 1 ≡x 2) \/ (x 3 ≡x 4.)) /\ (¬( x 1 ≡x 2) \/ ¬( x 3 ≡x 4.)) =1

((x 3 ≡x 4.) \/ (x 5 ≡x 6.)) /\ (¬( x 3 ≡x 4.) \/ ¬( x 5 ≡x 6.)) =1

((x 5 ≡x 6.) \/ (x 7 ≡x 8.)) /\ (¬( x 5 ≡x 6.) \/ ¬( x 7 ≡x 8.)) =1

((x 7 ≡x 8.) \/ (x 9 ≡x 10.)) /\ (¬( x 7 ≡x 8.) \/ ¬( x 9 ≡x 10.)) =1

In response not necessary List all different sets of values x 1, x 2, ... x 9, x 10under which this system of equalities is performed. As an answer, you need to specify the number of such sets.

2.2. Sketch of solution.

The system appear logical functions from the following expressions:

(x 1 ≡x 2), (x 3 ≡x 4.), (x 5 ≡x 6.), (x 7 ≡x 8.), (x 9 ≡x 10.)

Just as this is done in solving algebraic equations, we will replace the variables:

t. 1 \u003d x 1 ≡x 2

t. 2 \u003d x 3 ≡x 4.

t 3 \u003d x 5 ≡ x 6

t 4 \u003d x 7 ≡ x 8

T 5 \u003d.x 9 ≡x 10.

General replacement formula ( k \u003d 1, 2, 3, 4, 5):

t k \u003d (x 2 K-1 ≡x 2 k)

(t 1. \/ t 2.) /\ (¬ t 1. \/ ¬ T. 2 ) =1

(t. 2 \/ t 3.) /\ (¬ t. 2 \/ ¬ T. 3 ) =1

(t. 3 \/ t 4.) /\ (¬ t. 3 \/ ¬ T. 4 ) =1

(t. 4 \/ t 5.) /\ (¬ t. 4 \/ ¬ T. 5 ) =1

The equations of the obtained system are related ( k \u003d 1, 2, 3, 4):

(t. K. \/ t k + 1) /\ (¬ t. K. \/ ¬ T. K + 1.) =1

This means that of every two variables. t. K. and t k +1. Exactly one equal to 1 and exactly one is zero, i.e. These variables have different values. Thus, the system can be easily simplified and record it like this:

¬( t 1. ≡ T. 2 ) =1

¬( t 2. ≡ T 3.) =1

¬( t 3. ≡ T 4.) =1

¬( t 4. ≡ T 5.) =1

B. Analysis of the system.

In any solution of the last system, the values \u200b\u200bof variables alternate. Therefore, such a system has exactly two solutions: 01010 and 10101 (first digit - variable value t 1, Second - value T 2.etc.).

t k \u003d.x 2 K-1 ≡x 2 K.

(here k \u003d 1, 2, 3, 4, 5), then each value t K.two pairs of variable values \u200b\u200bcorrespond to x 2 K-1and x 2 K.. For example, t k \u003d 1in two cases: { x 2 K-1 \u003dx 2 k \u003d 1)and { x 2 K-1 \u003dx 2 k \u003d 0).

2.2.2. Counting the number of solutions

Each of the two solutions of the system for variables t.corresponds to 2 5 \u003d 32 solutions of the source system. Therefore, the source system has 2 ∙ 32 \u003d 64 solutions.

The exercise. Write all solutions. It is a little tedious, but useful.

3. EXAMPLE FIPIP OPEN SEEMENT EXAMPLE

3.1. The task.

Task 2012-B15-2 (open segment, standing 3: 2011)

How many different sets of logical variables x 1, x 2, ..., x 10, which satisfy all the conditions listed below?

¬ (x 1 ≡ x 2) / \\ (x 1 \\ / x 3) / \\ (¬x 1 \\ / ¬x 3) \u003d 0

¬ (x 2 ≡ x 3) / \\ (x 2 \\ / x 4) / \\ (¬x 2 \\ / ¬x 4) \u003d 0

¬ (x 8 ≡ x 9) / \\ (x 8 \\ / x 10) / \\ (¬x 8 \\ / ¬x 10) \u003d 0

In response not necessarylist all different sets of values \u200b\u200bx 1, x 2, ..., x 10, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

3.2. Sketch of solution.

The solution consists of two stages. First, we will try to describe how all sets of variables satisfy this system are arranged. Next, we calculate the number of such sets.

2.2.1. How many solutions are arranged

A. Preliminary stage - simplify the equation.

Note that the expression (A \\ / b) / \\ (¬a \\ / ¬b) is equivalent to the fact that exactly one of the variables A and B is equal to 1, that is, equivalent to the expression ¬ (a ≡ b). Therefore, each expression (X. k \\ / x k + 2) / \\ (¬x k \\ / ¬x K + 2)where k \u003d 1, ..., 8,in our equations can be replaced by expression ¬ (x k ≡ x k + 2).

Thus, our system is equivalent to the system

¬ (x 1 ≡ x 2) / \\ ¬ (x 1 ≡ x 3) \u003d 0

¬ (x 2 ≡ x 3) / \\ ¬ (x 2 ≡ x 4) \u003d 0

Therefore, the system can be written in the following form.

¬ (x 1 ≡ x 2) → (x 1 ≡ x 3) \u003d 1

¬ (x 2 ≡ x 3) → (x 2 ≡ x 4) \u003d 1

¬ (x 8 ≡ x 9) → (x 8 ≡ x 10) \u003d 1

B. Analysis of the system.

Each equations of the obtained system has the form ( k. = 1, …, 8):

¬ (X. k ≡ x k + 1) → (X. K ≡ X. K + 2) \u003d 1

In other words, if two adjacent elements of the X k and x k + 1 set are not equal to each other, then x k \u003d x k + 2, that is, the elements X k + 1 and x k + 2 are also not equal to each other. Thus, the set satisfies the system, then and only if it possesses the following properties. At the beginning of the set, it is somewhat (maybe one) of the same values \u200b\u200b(let's call it "head" dial). Then (after the first appearance of the new number) the values \u200b\u200bin the set alternate ("tail" set).

Example Solution: 111101010101 (In this sequence, the first digit is the value of the variable x 1, the second digit is the value of the variable x 2, etc.)

Here the head of the set consists of four units, and the tail is sequence 01010101. In this example, the length of the head is equal to 4.

Important observation. For each non-empty head there is exactly one tail that makes a solution with it. Indeed, the first digit of this tail is a digit opposite to the numbers of the head. And then the numbers in the tail alternate.

3.2.2. How many solutions are arranged

In accordance with important observation, the number of solutions coincides with the number of possible heads. Obviously, there are 10 heads consisting of units (1, 11, 111, ..., 1111111111) and as many heads consisting of zeros.

Comment. As we see, the complexity of solving the problem does not depend on the number of variables and equations. If it is clear how many solutions are arranged, calculate the number of solutions for a similar system, say, with the 20th variables, is not more difficult than in the case already considered.

4. Discussion

4.1. What knowledge / skills / skills are needed by the student to solve this task

This task is one of the most difficult in the exam, if not the most difficult. To solve her, the student should be able to

Convert logical expressions (including variable replacement);

Translate a formal description, in the form of a system of logical conditions, on a normal, "human" language and

After it is found out that the sets satisfy the system, the counting of their number is relatively simple.

The most difficult to assimilate, apparently, is the second of the listed requirements - it is not formalized, from the student, as a rule, a guess is required.

Invent your approaches, use them and tell us!

4.2.1. It is worth disassembling this task only with students who are freely posted by transformations of logical expressions. We note a few useful transformations (they met in disassembled examples):

¬a \\ / b is equivalent to a → B.

(A. → b) / \\ (b → a) equivalent to A ≡ B

(¬a \\ / b) / \\ (a \\ / ¬b) is equivalent to a ≡ b

(A \\ / b) / \\ (¬a \\ / ¬b) is equivalent to ¬ (A ≡ B).

More information about transformations of logical expressions is written here [see logic01.dOC]

In addition, it is useful to work out in the implementation of substitutions in logical expressions. Note that this is done in the same way as the replacement in the equations that are found in the course of mathematics.

4.2.2. The most difficult thing is to figure out that it is a lot of solutions. In sections 5 and 6, several examples are disassembled. Other useful examples and recommendations can be found on site K.Yu. Polyakov.

4.2.3. Counting the number of solutions is a simple combinatorial task. Strong students can figure out how to count, not even possessing special knowledge. It is necessary to repeat the formula for the work of the possibilities and the formula of the sum of arithmetic progression.

4.2.4. Thus, the preparation plan can be approximately so.

1) Repeat logical transformations and elements of combinatorics.

2) to determine the tasks and practice in translating a formal description, in the form of a system of logical conditions, on a normal, "human" language.

The exact algorithm of actions, guaranteed leading to success here is not. The first goal is to understand what is a variety of system solutions. To do this, the system is useful to convert (simplify) the system using identical conversions and replace variables. Then - calculate the number of elements in a variety of solutions.

In many cases, the system consists of the same type of equations, each of which binds a small number of variables (two-three-four), despite the fact that the system can be 10 or more variables. Usually, the number of variables is not a source of complexity, it is a solution parameter. If it is impossible to solve the task in general, you can try to move all solutions for the system with a small amount of variables. It can suggest how the solution is in general form.

5. Other tasks

Task 2012-B15-3.

How many different sets of logical variables x 1, x 2, ..., x 5, which satisfy all the condition listed below?

(x 1 → x 2) / \\ (x 2 → x 3) / \\ (x 3 → x 4) / \\ (x 4 → x 5) \u003d 1

In response not necessarylist all different sets of values \u200b\u200bx 1, x 2, ..., x 5, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

Decision. Obviously, the following ratios are met:

(x 1 → x 2) \u003d 1

(x 2. → x 3) \u003d 1

(x 3. → x 4) \u003d 1

(x 4. → x 5) \u003d 1

Suppose that the set (A1, A2, A3. A4, A5) is the solution of our equation. Suppose that A4 \u003d 1. Then, from the equation

(x 4. → x 5) \u003d 1

it follows that A5 \u003d 1 (Recall: 1 → 0 false!). Suppose now that A3 \u003d 1. From condition

(x 3. → x 4) \u003d 1

it follows that A4 \u003d 1 and, it means, according to the proven, A5 \u003d 1.

Similarly, you can show (check yourself!) That if the decision is found 1, then only the units go.

Thus, solutions of the equation are sets in which zeros first go, and then - units.

It is important not to forget about "special" sets - 00000 and 11111. They are also suitable.

Thus, here are all solutions of the equation:

00000, 00001, 00011, 00111, 01111, 11111

Each solution is fully described by the number of units in it. This amount may be from 0 to 5. The number of solutions - 6.

Task 2012-B15-4

How many different sets of logical variables x 1, x 2, ..., x 5, z 1, ..., z 4, which satisfy all the condition listed below?

(x 1 → x 2) / \\ (x 2 → x 3) / \\ (x 3 → x 4) / \\ (x 4 → x 5) \u003d 1 (1)

(Z 1. → z 2) / \\ (z 2 → z 3) / \\ (z 3 → z 4) \u003d 1 (2)

In response not necessarylist all different sets of values \u200b\u200bx 1, x 2, ..., x 5, z 1, ..., z 4, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

Decision.About such systems they say that the variables in them "divided": x 1, ...,x 5. occur only in equation (1), and z 1, ...,z 4 -only in equation (2). From solving the problem 3 it follows that equation (1) satisfies 6 sets of values \u200b\u200bof the variables x 1, x 2, ..., x 5, and equation (2) - 5 sets of variable values z 1, ...,z 4.Each of these sets for { x i)may form a solution with any of the sets for { z i).Therefore, the total number of solutions is equal to 6 ∙ 5 \u003d 30.

6. Tasks for self-decisions

Task 2012-B15-T1.

How many different sets of values \u200b\u200bof logical variables x 1, x 2, ..., x 500, which satisfy all the condition listed below?

(x 1 → x 2) / \\ (x 2 → x 3) / \\ ... / \\ (x 499 → x 500) \u003d 1

In response not necessary

Task 2012-B15- T2.

How many different sets of logical variables x 1, x 2, ..., x 1000, which satisfy all the condition listed below?

(x 2. → x 1) / \\ (x 3 → x 2) / \\ ... / \\ (x 1000 → x 999) \u003d 1

In response not necessarylist all the different sets of values \u200b\u200bx 1, x 2, ..., x 1000, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

Task 2012-B15- T3.

How many different sets of logical variables x 1, x 2, ..., x 11, which satisfy all the condition listed below?

(x 1 → x 3) / \\ (x 3 → x 5) / \\ ... / \\ (x 9 → x 11) \u003d 1

(x 2. → x 4) / \\ (x 4 → x 6) / \\ ... / \\ (x 8 → x 10) \u003d 1

In response not necessarylist all different sets of values \u200b\u200bx 1, x 2, ..., x 11, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

Task 2012-B15- T4.

How many different sets of logical variables x 1, x 2, ..., x 100, which satisfy all the condition listed below?

(x 1 → x 3) / \\ (x 3 → x 5) / \\ ... / \\ (x 99 → x 101) \u003d 1

(x 2. → x 4) / \\ (x 4 → x 6) / \\ ... / \\ (x 98 → x 100) \u003d 1

In response not necessarylist all different sets of values \u200b\u200bx 1, x 2, ..., x 500, under which this system of equalities is made. As an answer, you need to specify the number of such sets.

Answers: T1. 501; T2. 1001; T3. 42; T4. 2652.

Views

Save to classmates Save Vkontakte

You may also like