Задание 15. Истинность логического выражения

В условии стоят импликации, отрицания скобок, иногда эквивалентность. Разбирать такую запись как есть тяжело: приходится держать в уме, при каких значениях ложна каждая вложенная операция, и на третьем уровне вложенности человек теряет то посылку, то отрицание.

Поэтому сначала выражение переписывают так, чтобы в нём остались только ¬, ∧ и ∨. Часто встречающиеся замены:

После замен скобки дизъюнкций раскрываются, а одинаковые слагаемые склеиваются: ¬p ∨ ¬p – это просто ¬p. От выражения задания 15 при этом зачастую остаётся одна дизъюнкция из трёх слагаемых, и ровно в одном из них сидит A. Дальше её нужно проанализировать.

Дизъюнкция истинна, когда истинно хотя бы одно слагаемое. Значит:

выражение истинно при всех x тогда и только тогда, когда там, где ложны все слагаемые без A, слагаемое с A истинно.

Отсюда весь порядок работы:

1. Упростить – убрать импликации и эквивалентности, раскрыть отрицания скобок.
2. Найти опасное множество – те x (или пары x, y), на которых ложны все слагаемые, кроме того, где стоит A. Это отрезок, набор кратных или область на плоскости – всегда что-то, что рисуется.
3. Потребовать, чтобы слагаемое с A накрыло это множество целиком, и взять крайнее A – то, которое спросили.

Задача из банка тренажёра.

На числовой прямой даны два отрезка: P = [15; 40] и Q = [21; 63]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение

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

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

Шаг 1. Сократим запись: пусть p – это «x ∈ P», q – это «x ∈ Q», a – это «x ∈ A». Условие принимает вид

p → ((q ∧ ¬a) → ¬p)

Шаг 2. По правилу a → b = ¬a ∨ b вместо внутренней импликации (q ∧ ¬a) → ¬p пишем ¬(q ∧ ¬a) ∨ ¬p. Отрицание скобки раскрываем по Де Моргану, не забыв сменить союз: ¬(q ∧ ¬a) = ¬q ∨ a. Внутри осталось

¬q ∨ a ∨ ¬p

Шаг 3. Тем же правилом снимаем внешнюю импликацию: вместо p → (¬q ∨ a ∨ ¬p) пишем

¬p ∨ ¬q ∨ a ∨ ¬p

Два одинаковых слагаемых ¬p склеиваются в одно, и от всего условия остаётся

¬p ∨ ¬q ∨ a

то есть «x вне P, или x вне Q, или x внутри A».

Шаг 4. Первые два слагаемых ложны там, где x лежит и в P, и в Q, – то есть на пересечении P ∩ Q. Значит на всём пересечении обязано быть истинно третье слагаемое: отрезок A накрывает P ∩ Q целиком.

Подсвечена та самая область, где выражение может оказаться ложным: пересечение – от большего левого конца до меньшего правого, то есть от 21 до 40.

Шаг 5. Меньше, чем P ∩ Q, отрезок A быть не может, а больше – незачем: спросили наименьшую длину. Значит A = [21; 40].

Шаг 6. Длина отрезка – разность концов: $40 - 21 = 19$.

Ответ: 19.

Это задание 15 демонстрационного варианта ЕГЭ-2027 (ФИПИ).

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m»; пусть на числовой прямой дан отрезок B = [70; 90].

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

ДЕЛ(x, A) ∨ ((x ∈ B) → ¬ДЕЛ(x, 22))

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

Шаг 1. Сократим запись: d – это «ДЕЛ(x, A)», b – это «x ∈ B», m – это «ДЕЛ(x, 22)». Условие принимает вид

d ∨ (b → ¬m)

Шаг 2. Импликация здесь одна, и она уходит сразу: b → ¬m = ¬b ∨ ¬m. Скобки внутри дизъюнкции не нужны, так что всё условие – это

d ∨ ¬b ∨ ¬m

то есть «x делится на A, или x вне отрезка [70; 90], или x не делится на 22».

Шаг 3. Второе и третье слагаемые ложны там, где x лежит в [70; 90] и делится на 22. Таких x немного – достаточно перебрать кратные 22 около отрезка: $22 \cdot 3 = 66$ – левее, $22 \cdot 4 = 88$ – внутри, $22 \cdot 5 = 110$ – правее. Опасное множество состоит из одного числа: x = 88.

Точками на оси отмечены кратные 22. Внутрь отрезка B попала ровно одна – она и подсвечена.

Шаг 4. На нём обязано быть истинно первое слагаемое: ДЕЛ(88, A) = 1, то есть A – делитель числа 88.

Шаг 5. Наибольший делитель числа 88 – само число 88.

Ответ: 88.

Совпадение ответа с опасным x – случайность, а не правило. Опасных чисел бывает несколько. Стоит сделать отрезок пошире, B = [60; 90], и внутрь попадут сразу и 66, и 88: тогда A обязан делить оба, то есть делить их НОД, равный 22, и ответом станет 22, а не 88.

Второй подвид задач на делимость.

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

ДЕЛ(x, 21) → (¬ДЕЛ(x, A) → ¬ДЕЛ(x, 77))

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

1. Сокращаем и убираем импликации. Пусть t – это «ДЕЛ(x, 21)», a – «ДЕЛ(x, A)», s – «ДЕЛ(x, 77)»; условие – это t → (¬a → ¬s). Внутренняя импликация даёт ¬(¬a) ∨ ¬s, двойное отрицание снимается: a ∨ ¬s. Внешняя даёт ¬t ∨ (a ∨ ¬s), и скобки в дизъюнкции лишние. Остаётся ¬t ∨ a ∨ ¬s – «x не делится на 21, или x делится на A, или x не делится на 77».
2. Опасны те x, где ложны первое и третье слагаемые: x делится и на 21, и на 77. Это в точности кратные их НОК.
3. Считаем НОК. $21 = 3 \cdot 7$, $77 = 7 \cdot 11$; общий множитель 7 берётся один раз, поэтому НОК равен $3 \cdot 7 \cdot 11 = 231$.
4. На каждом кратном 231 обязано быть истинно второе слагаемое – значит A делит 231, иначе найдётся кратное 231, не делящееся на A. Наибольший делитель числа 231 – само 231.

Ответ: 231.

Третий жанр номера – переменных две, x и y, и все три слагаемых выражения – неравенства. Приём тот же, меняется только арифметика.

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

(x + y ≤ 27) ∨ (y ≤ x − 1) ∨ (y ≥ A)

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

Шаг 1. Упрощать нечего – условие уже дизъюнкция из трёх слагаемых, и A сидит в третьем. Так что сразу ищем опасное множество: пары, на которых ложны первые два слагаемых. Отрицания дают x + y ≥ 28 и y ≥ x. Переход «¬(x + y ≤ 27) – это x + y ≥ 28» и «¬(y ≤ x − 1) – это y ≥ x» законен ровно потому, что x и y целые: у вещественных вышло бы x + y > 27 и y > x − 1.

Шаг 2. Рисуем это множество: каждое из двух неравенств отрезает полуплоскость, а вместе они дают клин.

Шаг 3. Ищем самое маленькое y, при котором опасная пара вообще возможна. Из y ≥ x следует x + y ≤ 2y, а нужно x + y ≥ 28 – значит 2y ≥ 28, то есть y ≥ 14. Меньше не бывает, а 14 бывает: пара (14, 14) оба первых условия выполняет – это нижний угол клина.

Закрашенная область – все пары, на которых первые два слагаемых ложны. Ниже неё опасных пар нет вовсе, и это видно без вычислений: у клина есть самая нижняя точка.

Шаг 4. На всём клине обязано быть истинно третье слагаемое, y ≥ A. Прямая y = A – это его граница: выше неё и на ней слагаемое истинно, ниже – ложно. Значит клин целиком должен лежать не ниже этой прямой, а его самая нижняя точка – 14. Отсюда A ≤ 14, и наибольшее подходящее A равно 14.

Серым закрашена область, где слагаемое y ≥ A ложно при A = 15; пунктир по её верхней границе отрезал угол клина, и на паре (14, 14) ложны все три слагаемых сразу – выражение обращается в ноль. Сплошная прямая на единицу ниже – та же граница при A = 14: клин лежит на ней и выше, ни одна пара не проваливается.

Ответ: 14.

1. Считают длину отрезка числом целых точек. У [21; 40] длина 19, а точек 20. В задачах на отрезки x – любое вещественное число, целые тут ни при чём.
2. Бросаются разбирать исходную запись. Вложенные импликации приходится держать в голове целиком, и на третьем уровне теряется то посылка, то отрицание. Замена a → b на ¬a ∨ b заметно упрощает анализ.
3. Раскрывают отрицание скобки, не меняя союз. ¬(a ∧ b) – это ¬a ∨ ¬b, а не ¬a ∧ ¬b; ¬(a ∨ b) – это ¬a ∧ ¬b.
4. Найдя опасный x, пишут в ответ его самого. В демоверсии повезло: 88 оказалось и опасным числом, и ответом. А в примере с B = [60; 90] опасных чисел два – 66 и 88, и ответ равен их НОД, то есть 22.
5. Отвечают не на тот вопрос. Спросили наименьшую длину – написали правый конец отрезка; спросили наибольшее A – нашли наименьшее. Перечитайте последнюю строку условия перед тем, как записать ответ.
6. Не проверяют границу подстановкой. В жанре с двумя переменными почти вся ошибка – промах на единицу. Единственная надёжная страховка: убедиться, что при найденном A опасных пар нет, а при следующем уже есть. Для примера с неравенствами: при A = 14 у каждой пары клина y ≥ 14, третье слагаемое истинно; при A = 15 угол (14, 14) его уже не выполняет, и все три слагаемых обращаются в ноль разом.