Информатика 18 задание способ решения.

Задание 18 Каталог заданий. Логические высказывания

1. Задание 18 № 701. Для какого имени ложно высказывание:

(Первая буква имени гласная → Четвертая буква имени согласная).

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Пояснение.

Импликация ложна тогда и только тогда, когда посылка истинна, а следствие ложно. В нашем случае - если первая буква имени гласная и четвертая буква гласная. Этому условию удовлетворяет имя Антон.

Примечание.

Тот же результат следует из следующих преобразований: ¬ (A → B) = ¬ (¬ A ∨ B) = A ∧ (¬ B).

Правильный ответ указан под номером 3.

2. Задание 18 № 8666. На числовой прямой даны два отрезка: P = и Q = . Укажите наибольшую возможную длину промежутка A, для которого формула

(¬ (x A) → (x P)) → ((x A) → (x Q))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Пояснение.

Преобразуем данное выражение:

(¬ ( x A ) → ( x P )) → (( x A ) → ( x Q ))

((x A) ∨ (x P)) → ((x не A) ∨ (x Q))

¬(( x принадл A ) ∨ ( x принадл P )) ∨ (( x не принадл A ) ∨ ( x принадл Q ))

( x не принадл A ) ∧ ( x не принадл P ) ∨ ( x принадл A ) ∨ ( x не принадл Q )

( x не принадл A ) ∨ ( x принадл Q )

Таким образом, либо x должен принадлежать Q, либо не принадлежать A. Это значит, что для достижения истинности для всех x, необходимо, чтобы A полностью содержался в Q. Тогда максимум, каким он сможет стать, это всем Q, то есть длиной 15.

3. Задание 18 № 9170. На числовой прямой даны два отрезка: P = и Q = .

Укажите наибольшую возможную длину отрезка A, для которого формула

((x A) → ¬(x P)) → ((x A) → (x Q))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х .

Пояснение.

Преобразуем данное выражение.

(( x € A ) → ¬( x принадл P )) → (( x принадл A ) → ( x принадл Q ))

(( x не принадл A ) ∨ ( x не принадл P )) → (( x не принадл A ) ∨ ( x принадл Q ))

¬((x не принадл A) ∨ (x не принадл P)) ∨ ((x не принадл A) ∨ (x принадл Q))

Верно, что A ∧ B ∨ ¬A = ¬A ∨ B. Применим это здесь, получим:

(x принадл P) ∨ (x не принадл A) ∨ (x принадл Q)

То есть либо точка должна принадлежать Q, либо принадлежать P, либо не принадлежать А. Это значит, что А может покрывать все точки, которые покрывают P и Q. То есть A = P Q = = . |A| = 48 - 10 = 38.

4. Задание 18 № 9202. Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение

((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

истинно (т. е. принимает значение 1) при любом значении переменной х.

5. Задание 18 № 9310. Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {5, 10, 15, 20, 25, 30, 35, 40, 45, 50}.

Известно, что выражение

((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве A.

6. Задание 18 № 9321. Обозначим через ДЕЛ ( n, m ) утверждение «натуральное число n делится без остатка на натуральное число m ». Для какого наибольшего натурального числа А формула

¬ ДЕЛ ( x, А ) → (¬ ДЕЛ ( x , 21) ∧ ¬ ДЕЛ ( x , 35))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x )?

(Задание М. В. Кузнецовой)

7. Задание 18 № 9768. Обозначим через m & n m и n 2 & 0101 2 = 0100 2 А формула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х )?

8. Задание 18 № 9804. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула

x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x )?

9. Задание 18 № 723. Для какого имени истинно высказывание:

Третья буква гласная → ¬ (Первая буква согласная \/ В слове 4 гласных буквы)?

1) Римма

2) Анатолий

3) Светлана

4) Дмитрий

Пояснение.

Применим преобразование импликации:

Третья буква Согласная ∨ (Первая буква Гласная ∧ В слове НЕ 4 гласных буквы)

Дизъюнкция истинна, когда истинно хотя бы одно высказывание. Следовательно, подходит только вариант 1.

10. Задание 18 № 4581. Какое из приведённых имён удовлетворяет логическому условию:

(первая буква согласная → последняя буква согласная) /\ (первая буква гласная → последняя буква гласная)?

Если таких слов несколько, укажите самое длинное из них.

1) АННА

2) БЕЛЛА

3) АНТОН

4) БОРИС

Пояснение.

Логическое И истинно только тогда, когда истинны оба утверждения.(1)

Импликация ложна только тогда,когда из истины следует ложь.(2)

Вариант 1 подходит по всем условиям.

Вариант 2 не подходит из за условия (2).

Вариант 3 не подходит из за условия (2).

Вариант 4 подходит по всем условиям.

Необходимо указать самое длинное из слов, следовательно, ответ 4.

Задания для самостоятельного решения

1. Задание 18 № 711. Какое из приведенных названий стран удовлетворяет следующему логическому условию: ((последняя буква согласная) \/ (первая буква согласная)) → (название содержит букву «п») ?

1) Бразилия

2) Мексика

3) Аргентина

4) Куба

2. Задание 18 № 709. Какое из приведённых имен удовлетворяет логическому условию:

(Первая буква гласная) ∧ ((Четвёртая буква согласная) ∨ (B слове четыре буквы))?

1) Сергей

2) Вадим

3) Антон

4) Илья

№3

№4

№5. Задание 18 № 736. Какое из приведённых имен удовлетворяет логическому условию

Первая буква гласная ∧ Четвёртая буква согласная ∨ В слове четыре буквы?

1) Сергей

2) Вадим

3) Антон

4) Илья

Белова Т.В.
как научить решать задание 18 егэ по информатике

муниципальное бюджетное общеобразовательное учреждение «Лицей»,

г. Арзамас, ya . bellova . tatyana @ yandex . ru

Перед тем как приступать к решению заданий 18 «Проверка истинности логического выражения» экзаменационной работы по информатике, нужно объяснить (или вспомнить) учащимся, что такое понятие «объединение» и «пересечение» нескольких множеств. И так как задание 18 связано с определением отрезков, то и лучше всего эти понятия объяснять на отрезках. Но связать необходимо эти понятия с понятиями алгебры логики – «конъюнкция» и «дизъюнкция», ну и, конечно же, «инверсия». Приведу это все на примере. Для начала рассмотрим инверсию отрезка, или, проще говоря, отрицание отрезка.

Дан отрезок P=. Найти отрезки, которые будут инверсией отрезка P=. Рассмотрим координатную прямую (рис. 1):

рис. 1

На прямой отмечаем отрезок P (синяя область), тогда понятно, что промежутки не P будут промежутки и (зеленая область) – рис. 1. Обращая внимание, что точки 6 и 15 в инверсию отрезка входить не будут.

Рассмотрим еще пример: даны два отрезка P= и Q={приведены те же обозначения, что и в задании ЕГЭ, чтобы учащиеся сразу привыкали к обозначениям}. Найти отрезок, который будет обозначать конъюнкцию (объединение) и дизъюнкцию (пересечение) этих отрезков

Рисуем отрезки на координатной прямой (рис. 2):

рис. 2

Сначала отмечаем области на координатной прямой, которые обозначают отрезки P (синий цвет) и Q (желтый цвет). Затем определяем, какая часть координатной прямой будет служить конъюнкцией этих двух отрезков. Здесь вспоминаем, что конъюнкция – это логическая операция, которая объединяем два простых высказывания в сложное с помощью логической связки «и», и сложное высказывание будет приобретать значение «истина» тогда и только тогда, когда истины оба исходных простых высказывания. Таким образом, получаем, что нужно найти области, где и отрезок P и отрезок Q имеют место, а такая область только одна – отрезок (красный цвет). Более подробно исследуем все отрезки прямой, чтобы учащимся было нагляднее и понятнее воспринимать материал, итак:

Теперь аналогичным образом разберемся с дизъюнкцией этих отрезков. Опять же обратимся к определению этой логической операции – «дизъюнкцией называется логическая операция, которая в соответствии двум и более логическим высказываниям ставит новое, которое истинно тогда и только тогда, когда истинно хотя бы одно из входящих исходных высказываний». То есть другими словами, нам надо найти на координатной прямой такие промежутки, где есть хотя бы один из исходных наших отрезков, этот искомый промежуток будет – зеленый цвет (рис. 2). Также разберем каждый из промежутков и покажем, что это действительно так:

Объединяя найденные промежутки, получаем что искомый отрезок, обозначающий дизъюнкцию исходных отрезков – это отрезок – зеленый цвет (рис. 2).

После разбора данного примера, можно дать учащимся попробовать найти различные сочетания логических операций – дизъюнкции, конъюнкции и отрицания. Например, даны два отрезка P=[-4,10] и Q=. Найти отрезок, который будет обозначать следующие логические операции: , , (можно придумать и другие различные сочетания этих логических операций).

рис. 3

рис. 4

рис. 5

Когда разобраны все примеры, то у учащихся не возникнет трудностей с пониманием и решением задания №18 из экзаменационной работы единого государственного экзамена по информатике.

Приведем примеры решений нескольких заданий:

На числовой прямой даны два отрезка: P = и Q =. Выберите такой отрезок A, что формула

(x  A ) → ((x  P ) → (x  Q )) тождественно истинна, то есть принимает значение 1 при любом значении переменной х . Возможные варианты ответов:

1) 2) 3) 4)

Решение (рис. 6): чтобы упростить понимание выражения, обозначим отдельные высказывания буквами - A : x  А, P : x  P, Q : x  Q. Таким образом, получаем следующее выражение с учетом замены: → ( P → )=1. Равенство выражения 1 говорит о том, что какое бы значение переменной х мы не взяли, наше логическое выражение принимает значение 1, то есть на всей числовой прямой. Вспомним некоторые логические законы и равенства и преобразуем наше выражение: =1. В итоге получаем, что нам надо построить дизъюнкцию трех отрезков, два из которых нам известны. Их то мы и построим (рис. 7). Для начала, как и во всех выше приведенных примерах, мы должны построить инверсии отрезков P (оранжевый цвет) и Q (красный цвет). Затем из всего выражения мы можем определить промежутки дизъюнкции =1 (зеленые области рис. 7). Таким образом получаем, что у нас на координатной прямой есть «свободная» часть - . Эту часть прямой и должен перекрыть искомый отрезок А .

Для решения этой задачи нам потребуется сделать несколько логических умозаключений, поэтому "следите за руками".

1. От нас хотят, чтобы мы нашли минимальное целое неотрицательное А, при котором выражение всегда истинно.
2. Что из себя представляет выражение в целом? Что-то там импликация что-то там в скобках.
3. Давайте вспомним таблицу истинности для импликации:
   1 => 1 = 1
   1 => 0 = 0
   0 => 1 = 1
   0 => 0 = 1
4. Значит, возможно три варианта, когда это будет истинно. Рассматривать все эти три варианта — это убиться и не жить. Давайте подумаем, можем ли мы пойти "от противного ".
5. Давайте вместо того, чтобы искать А, попробуем найти x, при котором это выражение ложно.
6. То есть, возьмём некоторое число А (пока не знаем какое, просто какое-то). Если вдруг мы найдём такое x, при котором всё высказывание ложно, значит, выбранное А — плохое (потому что в условии требуется, чтобы всегда выражение было истинным)!
7. Таким образом мы сможем получить какие-то ограничение на число А.
8. Итак, давайте пойдём от противного и вспомним, когда импликация бывает ложной? Когда первая часть истинна, а вторая — ложна.
9. Значит
   \((\mathrm{x}\&25\neq 0)= 1 \\ (\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
10. Что означает, что \((x\&25\neq 0) = 1\) ? Это означает, что действительно \(\mathrm{x}\&25\neq 0\) .
11. Давайте переведём 25 в двоичную. Получим: 11001 2 .
12. Какие ограничения это накладывает на x? Раз не равно нулю, значит, при поразрядной конъюнкции должна где-то получиться единица. Но где она может быть? Только там, где в 25 уже есть единица!
13. Значит, в числе x хотя бы в одном кресте должна быть единица: XX**X.
14. Отлично, теперь рассмотрим второй множитель: \((\mathrm{x}\&17=0\Rightarrow \mathrm{x}\&\mathrm{A}\neq 0) = 0\)
15. Это выражение из себя также представляет импликацию. При этом оно так же ложно.
16. Значит, его первая часть обязана быть истинной, а вторая — ложной.
17. Значит
    \((\mathrm{x}\&17=0) = 1 \\ ((\mathrm{x}\&\mathrm{A}\neq 0) = 0) = 0\)
18. Что означает, что \(\mathrm{x}\&17=0\) ? То, что на всех местах, где в 17 стоят единицы, в x должны стоять нули (иначе в результате не получится 0).
19. Переведём 17 в двоичную: 10001 2 . Значит, в x на последнем с конца и на 5 с конца месте должны стоять нули.
20. Но стоп, мы же в пункте 13 получили, что на последнем ИЛИ на 4 с конца ИЛИ на 5 с конца должна быть единица.
21. Раз согласно строке 19 на последнем или 5 с конца местах единицы быть не может, значит, она обязана быть на 4 с конца месте.
22. То есть, если мы хотим, что при нашем x всё выражение было ложным, на 4 с конца месте обязана стоять единица: XX...XX1XXX 2 .
23. Отлично, рассмотрим теперь последнее условие: \((\mathrm{x}\&\mathrm{A}\neq 0) = 0\) . Что это означает?
24. Это означает, что неверно, что \(\mathrm{x}\&\mathrm{A}\neq 0\) .
25. То есть, на самом деле, \(\mathrm{x}\&\mathrm{A}=0\) .
26. Что мы знаем про x? Что на 4 с конца месте там единица. Во всём остальном x может быть практически любым.
27. Если мы хотим, чтобы исходное выражение в условии задачи было всегда истинным, то мы не должны найти х, который бы удовлетворял всем условиям. Ведь, действительно, если бы мы нашли такой x, получилось бы, что исходное выражение не всегда истинно, что противоречит условию задачи.
28. Значит, вот это самое последнее условие просто обязано не выполняться.
29. А как оно может не выполняться? Если только мы будем уверены на 100%, что при поразрядной конъюнкции где-то останется единица.
30. И это возможно: если в А тоже на 4 месте с конца будет единица, то в результате поразрядной конъюнкции на 4 с конца месте останется единица.
31. Какое минимально возможное двоичное число имеет единицу на 4 с конца месте? Очевидно, что 1000 2 . Значит, это число и будет ответом.
32. Осталось только перевести его в десятичную: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Ответ: минимально возможное A, удовлетворяющее условиям, равно 8 .

Евгений Смирнов

Эксперт в IT, учитель информатики

Решение №2

Можно предложить несколько более короткий подход. Обозначим наше высказывание как F = (A->(B->C)), где А - это высказывание "Х&25 не равно 0", В= "Х&17=0" и C="X&A не равно 0".

Раскроем импликации, пользуясь известным законом X->Y = не(Х) ИЛИ Y, получим F = A -> (не(В) ИЛИ C) = не(А) ИЛИ не(B) ИЛИ С. Распишем также двоичные значения констант 25 и 17:

Наше выражение - логическое ИЛИ от трёх высказываний:

1) не(А) - это значит, X&25 = 0 (биты 0,3,4 числа Х все равны 0)

2) не(B) - значит, X&17 не равно 0 (биты 0 и 4 числа Х хотя бы один равен 1)

3) C - знаит, X&A не равно 0 (биты, задаваемые маской A, хотя бы 1 равен 1)

Х - произвольное число. Все его биты независимы. Поэтому требовать выполнения какого-то условия на биты произвольного числа можно только в одном единственном случае - когда речь идёт об одной и той же маске (наборе битов). Мы можем заметить, что двоичная маска 17 - почти то же самое, что и 25, только не хватает бита номер 3. Вот если бы дополнить 17 битом номер 3, то выражение (не(В) ИЛИ С) превратилось бы в не(неА), т.е. в А = (X&25 не равно 0). По-другому: допустим, А=8 (бит 3=1). Тогда требование (не(В) B или С) равносильно требованию: (Хотя бы один из битов 4,0 равен 1) ИЛИ (бит 3 равен 1) = (хотя бы один из битов 0,3,4 не равен 1) - т.е. инверсия не(А) = А = (Х&25 не равно 0).

В итоге мы заметили, что если А=8, то наше выражение принимает вид F = не(А) ИЛИ А, что, по закону исключённого третьего, всегда тождественно истинно. При других, меньших, значениях А независимость от значения Х получить не удаётся, т.к. маски выходят разные. Ну, а при наличии в старших битах А единиц в битах выше 4 ничего не меняется, т.к. в остальных масках у нас нули. Получается, что только при А=8 формула превращается в тавтологию для произвольного Х.

Дмитрий Лисин

Известно, что выражение

((x ∈ A) → (x ∈ P)) ∧ ((x ∈ Q) → ¬(x ∈ A))

истинно (то есть принимает значение 1) при любом значении переменной х. Определите наибольшее возможное количество элементов в множестве A.

Решение.

Введем обозначения:

(x ∈ P) ≡ P; (x ∈ Q) ≡ Q; (x ∈ A) ≡ A; ∧ ≡ · ; ∨ ≡ +.

Тогда, применив преобразование импликации, получаем:

(¬A + P) · (¬Q + ¬A) ⇔ ¬A · ¬Q + ¬Q · P + ¬A + ¬A · P ⇔

⇔ ¬A · (¬Q + P + 1) + ¬Q · P ⇔ ¬A + ¬Q · P.

Требуется чтобы ¬A + ¬Q · P = 1. Выражение ¬Q · P истинно когда x ∈ {2, 4, 8, 10, 14, 16, 20}. Тогда ¬A должно быть истинным когда x ∈ {1, 3, 5, 6, 7, 9, 11, 12, 13, 15, 17, 18, 19, 21, 22, 23,...}.

Следовательно, максимальное количество элементов в множестве A будет, если A включает в себя все элементы множества ¬Q · P, таких элементов семь.

Ответ: 7.

Ответ: 7

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

Решение.

Введем обозначения:

(x ∈ {2, 4, 6, 8, 10, 12}) ≡ P; (x ∈ {3, 6, 9, 12, 15}) ≡ Q; (x ∈ A) ≡ A.

Преобразовав, получаем:

P → ((Q ∧ ¬A) → ¬P) = P → (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ (¬(Q ∧ ¬А) ∨ ¬P) = ¬P ∨ ¬Q ∨ А.

Логическое ИЛИ истинно, если истинно хотя бы одно утверждение. Выражение ¬P ∨ ¬Q истинно при всех значениях x, кроме значений 6 и 12. Следовательно, промежуток А должны содержать точки 6 и 12. То есть минимальный набор точек в промежутке А ≡ {6, 12}. Сумма элементов множества А равна 18.

Ответ: 18.

Ответ: 18

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение.

Упростим:

¬(x ∈ P) ∨ ¬(x ∈ Q) дают 0 только, когда число лежит в обоих множествах. Значит, чтобы все выражение было истинно нам нужно все числа лежащие в P и Q занести в А. Такие числа 6, 12, 18. Их сумма 36.

Ответ: 36.

Ответ: 36

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Элементами множеств А, P, Q являются натуральные числа, причём P = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}.

Известно, что выражение ((x A) → (x P)) ∨ (¬(x Q) → ¬(x A))

истинно (т. е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве A.

Решение.

Преобразуем данное выражение:

((x A) → (x P)) ∨ ((x Q) → (x A))

((x A) ∨ (x P)) ∨ ((x Q) ∨ (x A))

(x A) ∨ (x P) ∨ (x Q)

Таким образом элемент должен либо входить в P или Q, либо не входить в А. Таким образом в А могут быть лишь элементы из P и Q. И всего в этих двух множествах 17 неповторяющихся элементов.

Ответ: 17

Элементами множеств А, P, Q являются натуральные числа, причём P = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение

((x ∈ P) → (x ∈ A)) ∨ (¬(x ∈ A) → ¬(x ∈ Q))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение.

Раскроем две импликации. Получим:

(¬(x ∈ P) ∨ (x ∈ A)) ∨ ((x ∈ A) ∨ ¬(x ∈ Q))

Упростим:

(¬(x ∈ P) ∨ (x ∈ A) ∨ ¬(x ∈ Q))

¬(x ∈ P) ∨ ¬(x ∈ Q) дают 0, только когда число лежит в обоих множествах. Значит, чтобы все выражение было истинно, нужно все числа, лежащие в P и Q, занести в А. Такие числа 3, 9, 15 и 21. Их сумма 48.

Ответ: 48.

Ответ: 48

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10303

А выражение

(y + 2x 30) ∨ (y > 20)

X и y?

Решение.

Заметим, что для тождественной истинности данного выражения выражение (y + 2x Ответ: 81.

Ответ: 81

Источник: ЕГЭ - 2018. До­сроч­ная волна. Вариант 1., ЕГЭ - 2018. До­сроч­ная волна. Вариант 2.

На числовой прямой задан отрезок A. Известно, что формула

((x ∈ A ) → (x 2 ≤ 100)) ∧ ((x 2 ≤ 64) → (x ∈ A ))

тождественно истинна при любом вещественном x . Какую наименьшую длину может иметь отрезок A?

Решение.

Раскрывая импликацию по правилу A → B = ¬A + B, заменяя логическую сумму совокупностью, а логическое произведение системой соотношений, определим значения параметра А , при котором система совокупностей

будет иметь решения для любых вещественных чисел.

Чтобы решениями системы были все вещественные числа, необходимо и достаточно, чтобы решениями каждой из совокупностей были все вещественные числа.

Решениями неравенства являются все числа из отрезка [−10; 10]. Чтобы совокупность выполнялась для всех вещественных чисел, числа x , не лежащие на указанном отрезке, должны принадлежать отрезку A. Следовательно, отрезок A не должен выходить за пределы отрезка [−10; 10].

Аналогично, решениями неравенства являются числа из лучей и Чтобы совокупность выполнялась для всех вещественных чисел, числа x , не лежащие на указанных лучах, должны лежать на отрезке A. Следовательно, отрезок A должен содержать в себе отрезок [−8; 8].

Тем самым, наименьшая длина отрезка A может быть равна 8 + 8 = 16.

Ответ: 16.

Ответ: 16

A выражение

(y + 2x ≠ 48) ∨ (A x) ∨ (x y)

тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y ?

Решение.

A x и y , рассмотрим, в каких случаях условия (y + 2x ≠ 48) и (x y) ложны.

y = 48 − 2x ) и (x ≥ y). Это x в промежутке от 16 до 24 и y в промежутке от 0 до 16. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 16 и y = 16. Тогда A A будет равняться 15.

Ответ: 15.

Ответ: 15

Источник: ЕГЭ по информатике 28.05.2018. Основная волна, вариант А. Имаева - «Котолис».

Для какого наибольшего целого неотрицательного числа A выражение

(y + 2x ≠ 48) ∨ (A x) ∨ (A y)

тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y ?

Решение.

Чтобы найти наибольшее целое неотрицательное число A , при котором выражение будет x и y , рассмотрим, в каких случаях условие (y + 2x ≠ 48) ложно.

Таким образом, находим все решения, когда (y = 48 − 2x ). Это x в промежутке от 0 до 24 и y в промежутке от 48 до 0. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 16 и y = 16. Тогда A A будет равняться 15.

Ответ: 15.

Ответ: 15

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ-2019 по информатике.

Для какого наименьшего целого неотрицательного числа A выражение

(2x + 3y > 30) ∨ (x + y ≤ A )

тождественно истинно при любых целых неотрицательных x и y ?

Решение.

A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y y + 2x > 30) ложно.

y + 2x ≤ 30). Это x в промежутке от 0 до 15 и y в промежутке от 10 до 0. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 15 и y = 0. Тогда 15 + 0 ≤ A . Следовательно, наименьшее целое неотрицательное число A будет равняться 15.

Ответ: 15.

Ответ: 15

Для какого наибольшего целого неотрицательного числа A выражение

(2x + 3y x + y ≥ A )

тождественно истинно при любых целых неотрицательных x и y ?

Решение.

Чтобы найти наибольшее целое неотрицательное число A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y , рассмотрим, в каких случаях условие (3y + 2x Таким образом, находим все решения, когда (3y + 2x ≥ 30). Это x больше 15 и y больше 10. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 0 и y = 10. Тогда 0 + 10 ≤ A . Следовательно, наибольшее целое неотрицательное число A будет равняться 10.

Ответ: 10.

Ответ: 10

Для какого наименьшего целого неотрицательного числа A выражение

(3x + 4y ≠ 70) ∨ (A > x ) ∨ (A > y )

тождественно истинно при любых целых неотрицательных x и y ?

Решение.

Чтобы найти наименьшее целое неотрицательное число A , при котором выражение будет тождественно истинно при любых целых неотрицательных x и y , рассмотрим, в каких случаях условие (3x + 4y ≠ 70) ложно.

Таким образом, находим все решения, когда (3x + 4y = 70). Это x в промежутке от 2 до 22 и y в промежутке от 16 до 1. Заметим, что для того, чтобы выражение подходило для любых x и y , требуется взять x = 10 и y = 10. Тогда A > 10. Следовательно, наименьшее целое неотрицательное число A будет равняться 11.

1. Пример из демонстрационного варианта

(первая буква согласная → вторая буква согласная) / (предпоследняя буква гласная → последняя буква гласная)

1) КРИСТИНА 2) МАКСИМ 3) СТЕПАН 4) МАРИЯ

Набросок решения Импликация a → b равносильна выражению ¬a / b.

Первая импликация верна для слов КРИСТИНА и СТЕПАН. Из этих слов вторая импликация верна только для слова КРИСТИНА.

Ответ: 1. КРИСТИНА

2.Еще два примера

Пример 1 (открытый сегмент банка ФИПИ)

Какое из приведённых имён удовлетворяет логическому условию:

(первая буква согласная → первая буква гласная) / (последняя буква гласная → последняя буква согласная)

1. ИРИНА 2. МАКСИМ 3. АРТЁМ 4. МАРИЯ

Набросок решения . Импликация a → b равносильна выражению ¬a / b. Это выражение истинно если или выражение a ложно, или оба выражения a и b истинны. Поскольку в нашем случае ни в одной из импликаций оба выражения одновременно истинными быть не могут, то должны быть ложными утверждения «первая буква согласная» и «последняя буква гласная», то есть нам нужно слово, у которого первая буква гласная, а последняя - согласная.

Ответ: 3. АРТЁМ.

Пример 2. Для какого из указанных значений числа X истинно высказывание

(X < 4)→(X >15)

1) 1 2) 2 3) 3 4) 4

Решение. Никакое число не может быть одновременно меньше 4 и больше 15. Поэтому импликация истинна только, если посылка X < 4 ложна.

Ответ 4.

2. Задачи в формате ЕГЭ 2013-2014 гг.

2.1. Демо-версия 2013 г.

На числовой прямой даны два отрезка: P = и Q = .

Выберите такой отрезок A, что формула

1) 2) 3) 4)

2.2. Демо-версия 2014 г.

На числовой прямой даны два отрезка: P = и Q = . Выберите из предложенных отрезков такой отрезок A, что логическое выражение

((x ∈ P) → ¬ (x ∈ Q))→ ¬ (x ∈ А)

тождественно истинно, то есть принимает значение 1 при любом значении переменной

Варианты ответов: 1) 2) 3) 4)

Решение. Преобразуем выражение, используя . Имеем:

¬((x ∈ P) → ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

¬(¬(x ∈ P) ∨ ¬ (x ∈ Q)) ∨ (¬ (x ∈ А)) - замена импликации дизъюнкцией;

((x ∈ P) ∧ (x ∈ Q)) ∨ (¬ (x ∈ А)) - правило де Моргана и снятие двойного отрицания;

(x ∈ А) → ((x ∈ P) ∧ (x ∈ Q)) - замена дизъюнкции импликацией

Последнее выражение является тождественно истинным тогда и только тогда, когда A ⊆ P∩ Q = ∩ = (см. ). Из четырех данных отрезков этому условию удовлетворяет только отрезок - вариант №2.

Ответ: - вариант №2

3. Задачи в формате ЕГЭ 2015-2016 гг.

3.1. Задача 1.

На числовой прямой даны два отрезка: P = и Q = .

Известно, что границы отрезка A - целочисленные точки и для отрезка A, формула

((x ∈ А) → (x ∈ P)) \/ (x ∈ Q)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Какова наибольшая возможная длина отрезка A?

Правильный ответ: 10

Решение:

Преобразуем выражение – заменим импликацию дизъюнкцией. Получим:

(¬(x ∈ А)) \/ ((x ∈ P)) \/ (x ∈ Q)

Выражение ((x ∈ P)) \/ (x ∈ Q) истинно для тех только тех x, которые лежат либо в P, либо в Q, иными словами – для x ∈ R = P ∪ Q = ∪ . Выражение

(¬(x ∈ А)) \/ (x ∈ R)

тождественно истинно тогда и только тогда, когда A ∈ R. Так как A – отрезок, то A ∈ R тогда и только тогда, когда A ∈ P или A ∈ Q. Так как отрезок Q длиннее отрезка P, то наибольшая длина отрезка A достигается, когда A = Q = . Длина отрезка A в этом случае равна 30 – 20 = 10.

3.2. Задача 2.

Обозначим через m &n поразрядную конъюнкцию неотрицательных целых чисел m и n . Так, например, 14&5 = 1110 2 &0101 2 = 0100 2 = 4. Для какого наименьшего неотрицательного целого числа А формула

x &25 ≠ 0 → (x &33 ≠ 0 → x &А ≠ 0)

тождественно истинна, т.е. принимает значение 1 при любом неотрицательном целом значении переменной х ?

Правильный ответ: 57

Решение:

Преобразуем выражение – заменим импликации дизъюнкциями. Получим:

¬(x &25 ≠ 0) ∨ (¬(x &33 ≠ 0) ∨ x &А ≠ 0)

Раскроем скобки и заменим отрицания неравенств равенствами:

x &25 = 0 ∨ x &33 = 0 ∨ x &А ≠ 0 (*)

Имеем: 25 = 11001 2 и 33 = 100001 2 . Поэтому формула

x &25 = 0 ∨ x &33 = 0

ложна тогда и только тогда, когда двоичная запись числа x содержит 1 хотя бы в одном из следующих двоичных разрядов: 100000 (32), 10000 (16), 1000 (8) и 1.

Чтобы формула (*) была истинна при всех таких x необходимо и достаточно, чтобы двоичная запись числа A содержала 1 во всех этих разрядах. Наименьшее такое число – это число 32+16+8+1 = 57.