Task 18 in computer science
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 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 elements of the set ¬Q · P, there are seven such elements.
Answer: 7.
Answer: 7
The elements of the 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 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.
The logical OR is true if at least one of the statements is true. The expression ¬P ∨ ¬Q is true for all values of x, except for the 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, and 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 in P and Q in A. Such numbers are 6, 12, 18. Their sum is 36.
Answer: 36.
Answer: 36
Source: Training work on INFORMATICS Grade 11 January 18, 2017 Option IN10304
The elements of the sets A, P, Q are natural numbers, and 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 included in A. Thus, only elements from P and Q can be in A. And 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's explore 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 whole expression to be true, you need to put all the numbers in P and Q into A. Such numbers are 3, 9, 15 and 21. Their sum is 48.
Answer: 48.
Answer: 48
Source: Training work on INFORMATICS Grade 11 January 18, 2017 Option IN10303
And the expression
(y + 2x 30) ∨ (y > 20)
x and y?
Solution.
Note that for the identical truth of this expression, the expression (y + 2x Answer: 81.
Answer: 81
Source: USE - 2018. Early wave. Option 1., USE - 2018. Early wave. Option 2.
A segment A is given on the number line. It is known that the formula
((x ∈ A) → (x2 ≤ 100)) ∧ ((x2 ≤ 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, under which the system of collections
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 of each of the collections are all real numbers.
The solutions of the inequality are all numbers from the interval [−10; 10]. In order for the collection to hold for all real numbers, the numbers x, which do not lie on the specified segment, must belong to the segment A. Therefore, the segment A must not go beyond the segment [−10; 10].
Similarly, the solutions of the inequality are the numbers from the rays and In order for the set to hold for all real numbers, the numbers x, not lying on the indicated rays, must lie on the segment A. Therefore, the segment A must contain the segment [−8; 8].
Thus, the smallest length of segment A can be equal to 8 + 8 = 16.
Answer: 16.
Answer: 16
A expression
(y + 2x ≠ 48) ∨ (A x) ∨ ( x y)
identically true, that is, it takes the value 1 for any non-negative integers x And y?
Solution.
A x And y, consider in which cases the conditions ( y + 2x≠ 48) and ( x y) are false.
y = 48 − 2x) and (x ≥ y). This x between 16 and 24 y in the range from 0 to 16. Note that in order for the expression to be suitable for any x And y, it is required to take x= 16 and y= 16. Then A A will equal 15.
Answer: 15.
Answer: 15
Source: USE in Informatics 05/28/2018. The main wave, A. Imaev's variant - "Kotolis".
What is the largest non-negative integer A expression
(y + 2x ≠ 48) ∨ (A x) ∨ ( A y)
identically true, that is, it 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, consider in which cases the condition ( y + 2x≠ 48) is false.
Thus, we find all solutions when ( y = 48 − 2x). This x between 0 and 24 y in the range from 48 to 0. Note that in order for the expression to be suitable for any x And y, it is required to take x= 16 and y= 16. Then A A will equal 15.
Answer: 15.
Answer: 15
Source: Demo version of the USE-2019 in informatics.
What is the smallest non-negative integer A expression
(2x + 3y > 30) ∨ (x + y ≤ A)
identically true for any non-negative integers x And y?
Solution.
A, under which the expression will be identically true for any integer non-negative x And yy + 2x> 30) is false.
y + 2x≤ 30). This x ranging 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, it is required to take x= 15 and y= 0. Then 15 + 0 ≤ A. Therefore, the smallest integer non-negative number A will equal 15.
Answer: 15.
Answer: 15
What is the largest non-negative integer A expression
(2x + 3y x + y ≥ A)
identically true for any non-negative integers x And y?
Solution.
To find the largest non-negative integer A, under which the expression will be identically true for any integer non-negative x And y, consider in which cases the condition (3 y + 2x Thus, we find all solutions when (3 y + 2x≥ 30). This x over 15 and y greater than 10. Note that in order for the expression to be suitable for any x And y, it is 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
What is the smallest non-negative integer A expression
(3x + 4y ≠ 70) ∨ (A > x) ∨ (A > y)
identically true for any non-negative integers x And y?
Solution.
To find the smallest integer non-negative number A, under which the expression will be identically true for any integer non-negative x And y, consider in which cases the condition (3 x + 4y≠ 70) is false.
Thus, we find all solutions when (3 x + 4y= 70). This x between 2 and 22 y in the range from 16 to 1. Note that in order for the expression to be suitable for any x And y, it is required to take x= 10 and y= 10. Then A> 10. Therefore, the smallest non-negative integer A will equal 11.
Task 18 Job directory. 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.
The implication is false if and only if the premise is true and the consequence 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 number 3.
2. Task 18 No. 8666. Two segments are given on the number line: P = and Q = . Specify 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))
¬(( xownedA) ∨ ( xownedP)) ∨ (( x not ownedA) ∨ ( x ownedQ))
( xnot ownedA) ∧ ( xnot ownedP) ∨ ( x ownedA) ∨ ( x not ownedQ)
( xnot ownedA) ∨ ( x ownedQ)
Thus, either x must belong to Q or not belong to A. This means that in order to achieve true for all x, it is necessary that A is completely contained in Q. Then the maximum that it can become is the whole of Q, that is, of length 15 .
3. Task 18 No. 9170. Two segments are given on the number line: P = and Q = .
Specify the largest possible length of the segment A, for which the formula
((xA)→ ¬(xP))→ ((xA)→ (xQ))
is identically true, that is, it takes the value 1 for any value of the variableX .
Explanation.
Let's transform this expression.
(( x€ A) → ¬( xownedP)) → (( x ownedA) → ( x ownedQ))
(( xnot ownedA) ∨ ( xnot ownedP)) → (( x not ownedA) ∨ ( x ownedQ))
¬((x does not belong to A)∨ (xdoes not belong to P))∨ ((xdoes not belong to A)∨ (xbelongs to Q))
It is true that A∧ B∨ ¬A = ¬A∨ B. Applying this here, we get:
(x belongs to P)∨ (xdoes not belong to A)∨ (x belongs to Q)
That is, either the 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, and 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, and 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. Denote byDEL ( n, m ) the statement “a natural number n is divisible without a remainder by a natural numberm ". For what is the largest natural numberA formula
¬ DEL ( x, A ) → (¬ DEL ( x , 21) ∧ ¬ DEL ( x , 35))
is identically true (that is, it takes the value 1 for any natural value of the variablex )?
(Assignment to M. V. Kuznetsova)
7. Task 18 No. 9768. 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 on the value 1 for any non-negative integer value of the variable X )?
8. Task 18 No. 9804. 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:
The third letter is a 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 NOT has 4 vowels)
A disjunction is true when at least one of the statements is true. Therefore, only option 1 is suitable.
10. Task 18 No. 4581. Which of the following names satisfies the logical condition:
(first letter consonant→ the last letter is a consonant) /\ (the first letter is a vowel→ the last letter is a vowel)
If there are several such words, indicate the longest of them.
1) ANNA
2) BELLA
3) ANTON
4) BORIS
Explanation.
A logical AND is only true if both statements are true.(1)
An implication is false only when a false follows from the truth.(2)
Option 1 is suitable for all conditions.
Option 2 is not suitable due to condition (2).
Option 3 is not suitable due to condition (2).
Option 4 is suitable for all conditions.
You must specify the longest of the words, hence the answer is 4.
Tasks for independent solution
1. Task 18 No. 711. Which of the following country names satisfies the following logical condition: ((last consonant) \/ (first consonant))→ (the name contains the letter "p")?
1) Brazil
2) Mexico
3) Argentina
4) Cuba
2. Task 18 No. 709. Which of the following names satisfies the logical condition:
(First letter is a vowel)∧ ((Fourth letter consonant)∨ (There are four letters in the word))?
1) Sergey
2) Vadim
3) Anton
4) Ilya
№3
№4 
№5. Task 18 No. 736. Which of the given names satisfies the logical condition
The first letter is a vowel∧ fourth consonant∨ Does the word have four letters?
1) Sergey
2) Vadim
3) Anton
4) Ilya
Belova T.V.
how to teach to solve task 18 exam in computer science
Municipal budgetary educational institution "Lyceum",
Arzamas, ya. bellova. tatyana@ yandex. en
Before proceeding with the solution of tasks 18 "Checking the truth of a logical expression" of the examination paper in computer science, it is necessary to explain (or remember) to students what the concept of "union" and "intersection" of several sets is. And since task 18 is connected with the definition of segments, it is best to explain these concepts in segments. But it is necessary to connect these concepts with the concepts of the algebra of logic - "conjunction" and "disjunction", and, of course, "inversion". I'll give you all this with an example. To begin with, 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 inversion 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 gaps not P will be gaps and (green area) - fig. 1. Paying attention that points 6 and 15 will not be included in the inversion of the segment.
Consider another example: two segments P= and Q= are given (the same designations are given as in the USE task, so that students immediately get used to the designations). 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 indicate 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 recall 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 value “true” if and only if both original simple statements are true. Thus, we get that we need to find areas where both the segment P and the segment Q take place, and there is only one such region - the segment (red color). We will examine in more detail all the segments of the straight line, so that students can perceive the material more clearly and understandably, so:
Now, in a similar way, we will deal with the disjunction of these segments. Again, let us turn to the definition of this logical operation - “a disjunction is a logical operation that, in accordance with two or more logical statements, puts a new one that 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 such gaps on the coordinate line where there is at least one of our original segments, this desired gap will be green (Fig. 2). We will also analyze each of the intervals and show that this is indeed the case:
Combining the found gaps, we get that the desired segment, denoting the disjunction of the original segments, is a 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 think of other different combinations of these logical operations).
rice. 3
rice. 4
rice. 5
When all the examples have been analyzed, students will not have difficulty understanding and solving task No. 18 from the examination paper of the unified state exam in computer science.
Here are examples of solutions to several tasks:
Two segments are given 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, we denote individual statements by 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 says that whatever value of the variable X we did not take, our logical expression takes the value 1, that is, on the entire number line. Let's recall some logical laws and equalities and transform our expression: =1. As a result, we get 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 build 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 get that we have a “free” part on the coordinate line -. This part is straight and should overlap the desired segment A.
To solve this problem, we need to make some 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? something there implication something in brackets.
- Let's recall the truth table for the implication:
1 => 1 = 1
1 => 0 = 0
0 => 1 = 1
0 => 0 = 1 - So, there are three possibilities when this will be true. To consider all these three options is to kill yourself and not live. Let's think about whether we can go "from the opposite".
- 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 yet what, just some). If suddenly we find such an x for which the whole statement is false, then the chosen A is bad (because the condition requires that the expression is always true)!
- Thus, we can get some kind of restriction on the number A.
- So, let's go from the opposite and remember when the 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 impose on x? Since it is not equal to zero, it means that with a bitwise conjunction, a unit must be obtained somewhere. But where could she be? Only where there is already a unit in 25!
- This means that in the number x at least one cross must contain a unit: XX**X.
- Ok, now consider the second multiplier: \((\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
- This expression is also an implication. However, it is just as false.
- Hence, 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 \(\mathrm(x)\&17=0\) mean? 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, at the last place from the end and at the 5th place from the end, there must be zeros.
- But stop, we got in paragraph 13 that on the last OR 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 5 from the end places, so it must be 4th place from the end.
- That is, if we want the whole expression to be false with our x, then the 4th place from the end must be one: XX...XX1XXX 2 .
- Ok, now let's look at 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 at 4 from the end of the place there is a unit. In all other respects, x can be almost anything.
- If we want the original expression in the problem statement to be always true, then we should not be found x that satisfies all conditions. After all, indeed, if we found such x, it would turn out that the original expression is not always true, which contradicts the condition of the problem.
- This means that this very last condition simply must not be fulfilled.
- How can it not be done? If only we are 100% sure that with a bitwise conjunction, a unit will remain 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 a bitwise conjunction, a unit will remain in the 4th place from the end.
- What is the smallest possible binary number that has a 1 times 4 from the end of the place? Obviously 1000 2 . So this number will be the answer.
- It remains only 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 smallest possible A that satisfies the conditions, equals 8.
Evgeny Smirnov
Expert in IT, 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 us expand 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 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) - so 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 set 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 it comes to 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 17 were supplemented 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 1) OR (bit 3 is 1) = (at least one of bits 0,3,4 is not 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 the excluded middle, is always identically true. For other, smaller values of A, independence from the value of X cannot be obtained, since the masks are different. Well, if there are ones in the high bits of A in bits above 4, nothing changes, because in the rest of the masks we have zeros. It turns out that only when A=8 does the formula turn into a tautology for arbitrary X.
Dmitry Lisin
