To solve this problem we will need to make several logical conclusions, so “watch your hands.”
- They want us to find the minimum non-negative integer A for which the expression is always true.
- What is the expression as a whole? There's something there implication there's something in parentheses.
- Let's recall the truth table for implication:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1 - This means that there are three possible ways for this to be true. Considering all three of these options means killing yourself and not living. Let's think about whether we can go "by contradiction".
- Let's instead of looking for A, let's try to find x for which this expression is false.
- That is, let’s take some number A (we don’t know what it is yet, just some). If we suddenly find an x for which the entire statement is false, then the chosen A is bad (because the condition requires that the expression always be true)!
- This way we can get some restrictions on the number A.
- So, let's go backwards and remember when an implication is false? When the first part is true and the second part is false.
- Means
\((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\) - What does it mean that \((x\&25\neq 0) = 1\) ? This means that indeed \(\mathrm(x)\&25\neq 0\) .
- Let's convert 25 to binary. We get: 11001 2 .
- What restrictions does this place on x? Since it is not equal to zero, it means that with a bitwise conjunction the result must be one somewhere. But where could she be? Only where 25 already has a unit!
- This means that the number x in at least one cross must contain a unit: XX**X.
- Great, now let's look at the second factor: \((\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
- This expression also represents an implication. Moreover, it is just as false.
- This means that its first part must be true, and the second must be false.
- Means
\((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\) - What does it mean that \(\mathrm(x)\&17=0\) ? The fact that in all places where there are ones in 17, there must be zeros in x (otherwise the result will not be 0).
- Let's convert 17 to binary: 10001 2 . This means that in x the last place from the end and the 5th place from the end must contain zeros.
- But stop, in point 13 we got that at the last OR by 4 from the end OR 5 from the end should be one.
- Since, according to line 19, there cannot be a unit at the last or 5th place from the end, which means it must be in 4th place from the end.
- That is, if we want that at our x the entire expression was false, there must be a unit at the 4th place from the end: XX...XX1XXX 2.
- Great, now consider the last condition: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). What does this mean?
- This means that it is not true that \(\mathrm(x)\&\mathrm(A)\neq 0\).
- That is, in fact, \(\mathrm(x)\&\mathrm(A)=0\) .
- What do we know about x? That there is a unit at the 4th place from the end. In all other respects, x can be almost anything.
- If we want the original expression in the problem statement to always be true, then we shouldn't find x, which would satisfy all conditions. Indeed, if we found such x, it would turn out that the original expression is not always true, which contradicts the conditions of the problem.
- This means that this very last condition simply must not be met.
- How can it not be fulfilled? If only we are 100% sure that with a bitwise conjunction there will be a unit left somewhere.
- And this is possible: if in A there is also a unit in the 4th place from the end, then as a result of the bitwise conjunction there will be a unit in the 4th place from the end.
- What is the smallest possible binary number with a 1 at the 4th end? Obviously, 1000 2. So this number will be the answer.
- All that remains is to convert it to decimal: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)
Answer: the minimum possible A that satisfies the conditions, equals 8.
Evgeny Smirnov
IT expert, computer science teacher
Solution #2
A slightly shorter approach can be suggested. Let's denote our statement as F = (A->(B->C)), where A is the statement “X&25 is not equal to 0”, B = “X&17=0” and C = “X&A is not equal to 0”.
Let's expand on the implications, using the well-known law X->Y = not(X) OR Y, we get F = A -> (not(B) OR C) = not(A) OR not(B) OR C. We also write down the binary values of the constants 25 and 17:
Our expression is a logical OR of three statements:
1) not (A) - this means X&25 = 0 (bits 0,3,4 of X are all 0)
2) not (B) - means X&17 is not equal to 0 (bits 0 and 4 of X at least one is equal to 1)
3) C - knows X&A is not equal to 0 (bits specified by mask A, at least 1 is equal to 1)
X is an arbitrary number. All its bits are independent. Therefore, it is possible to demand the fulfillment of some condition on the bits of an arbitrary number only in one single case - when we are talking about the same mask (set of bits). We can notice that the binary mask 17 is almost the same as 25, only bit number 3 is missing. Now, if we were to supplement 17 with bit number 3, then the expression (not (B) OR C) would turn into not (not A ), i.e. in A = (X&25 is not equal to 0). In another way: let's say A=8 (bit 3=1). Then the requirement (not (B) B or C) is equivalent to the requirement: (At least one of bits 4,0 is equal to 1) OR (bit 3 is equal to 1) = (at least one of bits 0,3,4 is not equal to 1) - those. inversion not(A) = A = (X&25 is not equal to 0).
As a result, we noticed that if A = 8, then our expression takes the form F = not (A) OR A, which, according to the law of excluded middle, is always identically true. For other, smaller values of A, independence from the value of X cannot be obtained, because The masks come out different. Well, if there are ones in the most significant bits of A, nothing changes in bits above 4, because in the remaining masks we have zeros. It turns out that only when A = 8 does the formula turn into a tautology for an arbitrary X.
Dmitry Lisin
Task 18 Catalog of tasks. Logical statements
1. Task 18 No. 701. For which name is the statement false:
(The first letter of the name is a vowel→ The fourth letter of the name is a consonant).
1) ELENA
2) VADIM
3) ANTON
4) FEDOR
Explanation.
An implication is false if and only if the premise is true and the consequent is false. In our case - if the first letter of the name is a vowel and the fourth letter is a vowel. The name Anton satisfies this condition.
Note.
The same result follows from the following transformations: ¬ (A→ B) = ¬ (¬ A∨ B) = A∧ (¬B).
The correct answer is listed at number 3.
2. Task 18 No. 8666. There are two segments on the number line: P = and Q = . Indicate the largest possible length of the interval A for which the formula
(¬(xA)→ (xP))→ ((xA)→ (xQ))
is identically true, that is, it takes the value 1 for any value of the variable x.
Explanation.
Let's transform this expression:
(¬ ( xA) → ( x P)) → (( x A) → ( xQ))
((xA)∨ (x P))→ ((x Not A)∨ (x Q))
¬(( xbelongedA) ∨ ( xbelongedP)) ∨ (( x didn't belongA) ∨ ( x belongedQ))
( xdidn't belongA) ∧ ( xdidn't belongP) ∨ ( x belongedA) ∨ ( x didn't belongQ)
( xdidn't belongA) ∨ ( x belongedQ)
Thus, either x must belong to Q or not belong to A. This means that to achieve truth for all x, A must be completely contained in Q. Then the maximum it can become is all Q, that is, length 15 .
3. Task 18 No. 9170. There are two segments on the number line: P = and Q = .
Indicate the greatest possible length of segment A for which the formula
((xA)→ ¬(xP))→ ((xA)→ (xQ))
identically true, that is, it takes the value 1 for any value of the variableX .
Explanation.
Let's transform this expression.
(( x€ A) → ¬( xbelongedP)) → (( x belongedA) → ( x belongedQ))
(( xdidn't belongA) ∨ ( xdidn't belongP)) → (( x didn't belongA) ∨ ( x belongedQ))
¬((x did not belong to A)∨ (xdid not belong to P))∨ ((xdid not belong to A)∨ (xbelonged to Q))
It is true that A∧ B∨ ¬A = ¬A∨ B. Applying this here, we get:
(x belongs to P)∨ (xdid not belong to A)∨ (x belongs to Q)
That is, either a point must belong to Q, or belong to P, or not belong to A. This means that A can cover all points that cover P and Q. That is, A = P Q = = . |A| = 48 - 10 = 38.
4. Task 18 No. 9202. The elements of the sets A, P, Q are natural numbers, with P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18 , 21, 24, 27, 30).
It is known that the expression
((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))
true (i.e. takes the value 1) for any value of the variable x.
5. Task 18 No. 9310. The elements of the sets A, P, Q are natural numbers, with P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30 , 35, 40, 45, 50).
It is known that the expression
((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))
true (i.e. takes the value 1) for any value of the variable x.
Determine the largest possible number of elements in set A.
6. Task 18 No. 9321. Let us denote byDEL ( n, m ) the statement “a natural number n is divisible by a natural number without a remainderm " For what is the largest natural numberA formula
¬ DEL ( x, A ) → (¬ DEL ( x , 21) ∧ ¬ DEL ( x , 35))
is identically true (that is, takes the value 1 for any natural value of the variablex )?
(Assignment from M.V. Kuznetsova)
7. Task 18 No. 9768. Let us denote by m & n m And n 2 & 0101 2 = 0100 2 A formula
x & 29 ≠ 0 → (x & 12 = 0 → x & A ≠ 0)
is identically true (that is, takes the value 1 for any non-negative integer value of the variable X )?
8. Task 18 No. 9804. Let us denote by m & n bitwise conjunction of non-negative integers m And n . So, for example, 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. For what is the smallest non-negative integer A formula
x & 29 ≠ 0 → (x & 17 = 0 → x & A ≠ 0)
is identically true (i.e., takes the value 1 for any non-negative integer value of the variable x )?
9. Task 18 No. 723. For which name is the statement true:
Third letter vowel→ ¬ (The first letter is a consonant \/ There are 4 vowels in the word)?
1) Rimma
2) Anatoly
3) Svetlana
4) Dmitry
Explanation.
Let's apply the implication transformation:
Third letter consonant∨ (First letter Vowel∧ The word does NOT have 4 vowels)
A disjunction is true when at least one statement is true. Therefore, only option 1 is suitable.
10. Task 18 No. 4581. Which of the given names satisfies the logical condition:
(the first letter is a consonant→ the last letter is a consonant) /\ (the first letter is a vowel→ is the last letter a vowel)?
If there are several such words, indicate the longest one.
1) ANNA
2) BELLA
3) ANTON
4) BORIS
Explanation.
Logical And is true only if both statements are true.(1)
An implication is false only if the truth implies a lie.(2)
Option 1 suits all conditions.
Option 2 is not suitable due to condition (2).
Option 3 is not suitable due to condition (2).
Option 4 suits all conditions.
The longest word must be specified, hence the answer is 4.
Tasks for independent solution
1. Task 18 No. 711. Which of the given country names satisfies the following logical condition: ((last letter consonant) \/ (first letter consonant))→ (the name contains the letter "p")?
1) Brazil
2) Mexico
3) Argentina
4) Cuba
2. Task 18 No. 709. Which of the given names satisfies the logical condition:
(First letter is vowel)∧ ((Fourth letter consonant)∨ (The word has four letters))?
1) Sergey
2) Vadim
3) Anton
4) Ilya
№3
№4 
№5. Task 18 No. 736. Which of the given names satisfies the logical condition
First letter is vowel∧ The fourth letter is a consonant∨ Are there four letters in the word?
1) Sergey
2) Vadim
3) Anton
4) Ilya
Belova T.V.
how to teach how to solve task 18 of the Unified State Exam in computer science
municipal budgetary educational institution "Lyceum",
Arzamas, ya. bellova. tatyana@ yandex. ru
Before starting to solve tasks 18 “Checking the truth of a logical expression” of the examination paper in computer science, you need to explain (or remember) to students what the concept of “union” and “intersection” of several sets is. And since task 18 is related to the definition of segments, it is best to explain these concepts on segments. But it is necessary to connect these concepts with the concepts of logical algebra - “conjunction” and “disjunction”, and, of course, “inversion”. I'll give you an example. First, let's consider the inversion of a segment, or, more simply, the negation of a segment.
The segment P= is given. Find the segments that will be the inverse of the segment P=. Consider the coordinate line (Fig. 1):
rice. 1
On the straight line we mark the segment P (blue area), then it is clear that the intervals not P will be intervals and (green area) - Fig. 1. Paying attention to the fact that points 6 and 15 will not be included in the inversion of the segment.
Let's consider another example: two segments P= and Q= are given (the same notations are given as in the Unified State Examination task, so that students immediately get used to the notations). Find a segment that will denote the conjunction (union) and disjunction (intersection) of these segments
We draw segments on the coordinate line (Fig. 2):
rice. 2
First, we mark the areas on the coordinate line, which represent the segments P (blue) and Q (yellow). Then we determine which part of the coordinate line will serve as the conjunction of these two segments. Here we remember that conjunction is a logical operation that combines two simple statements into a complex one using the logical connective “and”, and the complex statement will acquire the meaning “true” if and only if both original simple statements are true. Thus, we find that we need to find regions where both the segment P and the segment Q exist, and there is only one such region - the segment (red). We will study all the straight segments in more detail so that students can more clearly and understand the material, so:
Now let’s look at the disjunction of these segments in a similar way. Let us again turn to the definition of this logical operation - “disjunction is a logical operation that, in accordance with two or more logical statements, puts a new one, which is true if and only if at least one of the input initial statements is true.” That is, in other words, we need to find intervals on the coordinate line where there is at least one of our original segments, this desired interval will be green (Fig. 2). We will also analyze each of the intervals and show that this is indeed the case:
Combining the found intervals, we obtain that the required segment, denoting the disjunction of the original segments, is the segment - green (Fig. 2).
After analyzing this example, you can let students try to find various combinations of logical operations - disjunction, conjunction and negation. For example, given two segments P=[-4,10] and Q=. Find a segment that will denote the following logical operations: , , (you can come up with various other combinations of these logical operations).
rice. 3
rice. 4
rice. 5
When all the examples are analyzed, students will not have any difficulties understanding and solving task No. 18 from the exam paper of the unified state exam in computer science.
Here are examples of solutions to several tasks:
There are two segments on the number line: P = and Q =. Choose a segment A such that the formula
(x A) → ((x P) → (x Q)) is identically true, that is, it takes the value 1 for any value of the variable X. Possible answers:
1) 2) 3) 4)
Solution (Fig. 6): to simplify the understanding of the expression, let’s denote individual statements with letters - A:x A,P:x P,Q:x Q. Thus, we obtain the following expression taking into account the replacement: → ( P→ )=1. The equality of expression 1 means that whatever the value of the variable X we didn’t take it, our logical expression takes the value 1, that is, on the entire number line. Let's remember some logical laws and equalities and transform our expression: =1. As a result, we find that we need to construct a disjunction of three segments, two of which are known to us. We will build them (Fig. 7). To begin with, as in all the above examples, we must construct the inversions of the segments P (orange) and Q (red). Then from the entire expression we can determine the disjunction intervals =1 (green areas in Fig. 7). Thus, we find that we have a “free” part on the coordinate line - . This part is straight and must overlap the desired segment A.
It is known that the expression
((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))
true (that is, takes the value 1) for any value of the variable x. Determine the largest possible number of elements in set A.
Solution.
Let us introduce the following notation:
(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ · ; ∨ ≡ +.
Then, applying the implication transformation, we obtain:
(¬A + P) · (¬Q + ¬A) ⇔ ¬A · ¬Q + ¬Q · P + ¬A + ¬A · P ⇔
⇔ ¬A · (¬Q + P + 1) + ¬Q · P ⇔ ¬A + ¬Q · P.
It is required that ¬A + ¬Q · P = 1. The expression ¬Q · P is true when x ∈ (2, 4, 8, 10, 14, 16, 20). Then ¬A must be true when x ∈ (1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...).
Therefore, the maximum number of elements in the set A will be if A includes all the elements of the set ¬Q · P, there are seven such elements.
Answer: 7.
Answer: 7
The elements of set A are natural numbers. It is known that the expression
(x (2, 4, 6, 8, 10, 12)) → (((x (3, 6, 9, 12, 15)) ∧ ¬(x A)) → ¬(x (2, 4, 6 , 8, 10, 12)))
Solution.
Let us introduce the following notation:
(x ∈ (2, 4, 6, 8, 10, 12)) ≡ P; (x ∈ (3, 6, 9, 12, 15)) ≡ Q; (x ∈ A) ≡ A.
Transforming, we get:
P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬A) ∨ ¬P) = ¬P ∨ ¬Q ∨ A.
Logical OR is true if at least one statement is true. The expression ¬P ∨ ¬Q is true for all values of x except values 6 and 12. Therefore, the interval A must contain points 6 and 12. That is, the minimum set of points in the interval A ≡ (6, 12). The sum of the elements of set A is 18.
Answer: 18.
Answer: 18
The elements of the sets A, P, Q are natural numbers, with P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18 , 21, 24, 27, 30).
It is known that the expression
true (i.e. takes the value 1) for any value of the variable x. Determine the smallest possible value of the sum of the elements of set A.
Solution.
Let's simplify:
¬(x P) ∨ ¬(x Q) give 0 only when the number lies in both sets. This means that for the whole expression to be true, we need to put all the numbers lying in P and Q into A. Such numbers are 6, 12, 18. Their sum is 36.
Answer: 36.
Answer: 36
Source: Training work in COMPUTER SCIENCE, grade 11 January 18, 2017 Option IN10304
The elements of the sets A, P, Q are natural numbers, with P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18 , 21, 24, 27, 30).
It is known that the expression ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))
true (i.e. takes the value 1) for any value of the variable x.
Determine the largest possible number of elements in set A.
Solution.
Let's transform this expression:
((x A) → (x P)) ∨ ((x Q) → (x A))
((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))
(x A) ∨ (x P) ∨ (x Q)
Thus, an element must either be included in P or Q, or not be included in A. Thus, A can only contain elements from P and Q. And in total there are 17 non-repeating elements in these two sets.
Answer: 17
The elements of the sets A, P, Q are natural numbers, and P = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21), Q = (3, 6, 9, 12, 15 , 18, 21, 24, 27, 30). It is known that the expression
((x P) → (x A)) ∨ (¬(x A) → ¬(x Q))
true (i.e. takes the value 1) for any value of the variable x. Determine the smallest possible value of the sum of the elements of set A.
Solution.
Let us reveal two implications. We get:
(¬(x P) ∨ (x A)) ∨ ((x A) ∨ ¬(x Q))
Let's simplify:
(¬(x P) ∨ (x A) ∨ ¬(x Q))
¬(x P) ∨ ¬(x Q) give 0 only when the number lies in both sets. This means that for the entire expression to be true, you need to put all the numbers in P and Q into A. These numbers are 3, 9, 15 and 21. Their sum is 48.
Answer: 48.
Answer: 48
Source: Training work in COMPUTER SCIENCE, grade 11 January 18, 2017 Option IN10303
And the expression
(y + 2x 30) ∨ (y > 20)
X and y?
Solution.
Note that for this expression to be identically true, the expression (y + 2x Answer: 81.
Answer: 81
Source: Unified State Examination - 2018. Early wave. Option 1., Unified State Examination - 2018. Early wave. Option 2.
A segment A is given on the number line. It is known that the formula
((x ∈ A) → (x 2 ≤ 100)) ∧ ((x 2 ≤ 64) → (x ∈ A))
is identically true for any real x. What is the shortest length of segment A?
Solution.
Expanding the implication according to the rule A → B = ¬A + B, replacing the logical sum with a set, and the logical product with a system of relations, we determine the values of the parameter A, at which the system of aggregates
will have solutions for any real numbers.
For the solutions of the system to be all real numbers, it is necessary and sufficient that the solutions to each of the collections are all real numbers.
The solutions to the inequality are all numbers from the interval [−10; 10]. For the collection to hold for all real numbers, the numbers x, not lying on the specified segment, must belong to the segment A. Consequently, the segment A must not go beyond the boundaries of the segment [−10; 10].
Similarly, the solutions to the inequality are the numbers from the rays and For the collection to hold for all real numbers, the numbers x, not lying on the indicated rays, must lie on the segment A. Consequently, the segment A must contain the segment [−8; 8].
Thus, the shortest length of segment A can be equal to 8 + 8 = 16.
Answer: 16.
Answer: 16
A expression
(y + 2x ≠ 48) ∨ (A x) ∨ ( x y)
is identically true, that is, takes the value 1 for any non-negative integers x And y?
Solution.
A x And y, let us consider in what cases the conditions ( y + 2x≠ 48) and ( x y) are false.
y = 48 − 2x) and (x ≥ y). This x in the range from 16 to 24 and y in the range from 0 to 16. Note that in order for the expression to be suitable for any x And y, required to take x= 16 and y= 16. Then A A will equal 15.
Answer: 15.
Answer: 15
Source: Unified State Exam in Computer Science 05/28/2018. The main wave, A. Imaev’s version - “Kotolis”.
For what is the largest non-negative integer A expression
(y + 2x ≠ 48) ∨ (A x) ∨ ( A y)
is identically true, that is, takes the value 1 for any non-negative integers x And y?
Solution.
To find the largest non-negative integer A, at which the expression will be x And y, let us consider in which cases the condition ( y + 2x≠ 48) is false.
Thus, we find all solutions when ( y = 48 − 2x). This x in the range from 0 to 24 and y in the range from 48 to 0. Note that in order for the expression to be suitable for any x And y, required to take x= 16 and y= 16. Then A A will equal 15.
Answer: 15.
Answer: 15
Source: Demo version of the Unified State Exam 2019 in computer science.
For what is the smallest non-negative integer A expression
(2x + 3y > 30) ∨ (x + y ≤ A)
is identically true for any non-negative integers x And y?
Solution.
A, in which the expression will be identically true for any non-negative integers x And yy + 2x> 30) false.
y + 2x≤ 30). This x in the range from 0 to 15 and y in the range from 10 to 0. Note that in order for the expression to be suitable for any x And y, required to take x= 15 and y= 0. Then 15 + 0 ≤ A. Therefore, the smallest non-negative integer A will be equal to 15.
Answer: 15.
Answer: 15
For what is the largest non-negative integer A expression
(2x + 3y x+ y ≥ A)
is identically true for any non-negative integers x And y?
Solution.
To find the largest non-negative integer A, in which the expression will be identically true for any non-negative integers x And y, let us consider in what cases condition (3 y + 2x Thus, we find all solutions when (3 y + 2x≥ 30). This x more than 15 and y greater than 10. Note that in order for the expression to be suitable for any x And y, required to take x= 0 and y= 10. Then 0 + 10 ≤ A. Therefore, the largest non-negative integer A will equal 10.
Answer: 10.
Answer: 10
For what is the smallest non-negative integer A expression
(3x + 4y ≠ 70) ∨ (A > x) ∨ (A > y)
is identically true for any non-negative integers x And y?
Solution.
To find the smallest non-negative integer A, in which the expression will be identically true for any non-negative integers x And y, let us consider in what cases condition (3 x + 4y≠ 70) is false.
Thus, we find all solutions when (3 x + 4y= 70). This x in the range from 2 to 22 and y in the range from 16 to 1. Note that in order for the expression to be suitable for any x And y, required to take x= 10 and y= 10. Then A> 10. Therefore, the smallest non-negative integer A will equal 11.
