Задание 15. Алгебра логики. Преобразование и анализ логических выражений. ЕГЭ 2026 по информатике
Средний процент выполнения: 48%
Ответом к заданию 15 по информатике может быть цифра (число) или слово.
Алгоритм решения задания 15:
- Определи логические переменные и операции в выражении.
- Установи порядок выполнения операций (НЕ → И → ИЛИ).
- Если нужно, построй таблицу истинности для переменных.
- Последовательно вычисли значения подвыражений.
- Примени законы логики для упрощения (если требуется).
- Определи итоговое значение логического выражения.
- Запиши ответ в требуемом формате.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Для какого наименьшего целого неотрицательного числа А логическое выражение
(282 475 249 ≠ y + 6·x) ∨ (A > x) ∧ (A > y)
истинно (т.е. принимает значение 1) при любых целых положительных х и у?
Решение
Учтём приоритет операций: ∧ выполняется раньше ∨, поэтому формула читается как:
(282 475 249 ≠ y + 6·x) ∨ ((A > x) ∧ (A > y))
Формула ложна тогда и только тогда, когда оба операнда дизъюнкции равны 0:
- y + 6·x = 282 475 249
- (A > x) ∧ (A > y) = 0, то есть A ≤ x или A ≤ y
Для тождественной истинности необходимо, чтобы таких пар (x, y) не существовало. Значит для всех целых положительных решений уравнения y + 6·x = 282 475 249 должно выполняться A > x И A > y.
Заметим, что 282 475 249 = 710.
Из уравнения y = 282 475 249 − 6·x при x ≥ 1, y ≥ 1:
- x ≥ 1, y ≥ 1 → 1 ≤ x ≤ 47 079 208
- Максимальное x = 47 079 208 (при y = 1)
- Максимальное y = 282 475 243 (при x = 1)
Нам нужно A > x и A > y одновременно для всех решений. Самое жёсткое ограничение даёт пара (x=1, y=282 475 243): необходимо A > 282 475 243.
Проверим A = 282 475 244: для всех решений x ≤ 47 079 208 < A ✓ и y ≤ 282 475 243 < A ✓.
Задача 2
На числовой прямой даны два отрезка: B = [30; 65] и C = [50; 90]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
¬(x ∈ A) → ((x ∈ B) ≡ (x ∈ C))
истинно (т.е. принимает значение 1) при любом значении переменной x.
Решение
Формула ¬(x ∈ A) → ((x ∈ B) ≡ (x ∈ C)) ложна при: x ∉ A и (x ∈ B) ≡ (x ∈ C) = 0.
Эквиваленция ложна, когда x принадлежит ровно одному из отрезков B или C, то есть x ∈ B△C (симметрическая разность):
- B \ C = [30; 49] — принадлежит B, но не C
- C \ B = [66; 90] — принадлежит C, но не B
Для тождественной истинности необходимо и достаточно: B△C ⊆ A.
B△C = [30; 49] ∪ [66; 90]. Наименьший отрезок, покрывающий это объединение — [30; 90], его длина = 90 − 30 = 60.
Задача 3
Найдите наименьшее целое неотрицательное A, при котором выражение истинно для любых целых положительных x и y:
(59049 ≠ 3x + y) ∨ (A > x) ∧ (A > y)
Решение
Приводим выражение к удобному виду
С учётом приоритетов операций:
Q = (A > x) ∧ (A > y)
Нужно: P ∨ Q истинно при всех x, y
Когда возникает проблема?
Опасный случай — когда:
и при этом A ≤ x или A ≤ y
Максимизируем «опасное» значение
Выразим:
Чтобы «сломать» выражение, выгодно сделать одно число как можно больше.
Максимизируем y → берём минимальное x:
Выбираем минимальное A
Для этой пары нужно:
Минимальное целое:
Проверка
P = ложь, но A > y ⇒ Q = истина
⇒ всё выражение истинно
Для остальных пар значения меньше ⇒ тем более выполняется
Задача 4
Для какого наименьшего целого неотрицательного числа A логическое выражение
(342876 ≠ 7x + 2y) ∨ (A > x) ∧ (A > y)
истинно (т.е. принимает значение 1) при любых целых положительных x и y?
Решение
def f(x, y, A):
return (342876 != 7 * x + 2 * y) or ((A > x) and (A > y))
for A in range(500000):
fl = True
for x in range(1, 100000):
y = (342876 - 7 * x) // 2
if f(x, y, A) == 0:
fl = False
break
if fl:
print(A)
break
Задача 5
Элементами множества A являются натуральные числа. Известно, что выражение
(x ∈ {2, 4, 8, 12, 15}) → (¬(x ∈ {3, 6, 8, 15}) ∨ (x ∈ A))
истинно (т. е. принимает значение 1) при любом значении переменной x. Определите наименьшее возможное значение произведения элементов множества A.
Решение
a = set()
def f(x):
return (x in {2, 4, 8, 12, 15}) <= (not(x in {3, 6, 8, 15}) or x in a)
for x in range(1, 1000):
if f(x) == 0:
a.add(x)
result = 1
for x in a:
result *= x
print(result)
Задача 6
На числовой оси даны два отрезка: X = [10; 93] и Y = [4; 72].
Укажите наименьшую возможную длину такого отрезка Z, для которого логическое выражение:
(x ∈ Y) → ((x ∈ X) ∧ ¬(x ∈ Z) → ¬(x ∈ Y)) тождественно истинно (то есть принимает значение 1 при любом действительном значении переменной x).
Решение
Сначала упростим логическое выражение:
1. Исходное выражение:
(x ∈ Y) → ((x ∈ X) ∧ ¬(x ∈ Z) → ¬(x ∈ Y))
2. Применим закон импликации: A → B = ¬A ∨ B. Получим:
¬(x ∈ Y) ∨ ((x ∈ X) ∧ ¬(x ∈ Z) → ¬(x ∈ Y))
3. Упростим вторую часть выражения:
(x ∈ X) ∧ ¬(x ∈ Z) → ¬(x ∈ Y)
Применяя закон импликации снова, получаем:
¬((x ∈ X) ∧ ¬(x ∈ Z)) ∨ ¬(x ∈ Y)
Используем закон де Моргана:
¬(x ∈ X) ∨ (x ∈ Z) ∨ ¬(x ∈ Y)
Объединим все части:
¬(x ∈ Y) ∨ (¬(x ∈ X) ∨ (x ∈ Z) ∨ ¬(x ∈ Y))
Избавимся от лишних скобок и применим закон повторения:
¬(x ∈ Y) ∨ ¬(x ∈ X) ∨ (x ∈ Z)
¬(x ∈ Y) ∨ ¬(x ∈ X) покрывает все числа, не входящие в Y или в X, то есть все, кроме пересечения отрезков X и Y. Покрыты все числа до 10 и от 72.
Таким образом, чтобы гарантировать истинность выражения, необходимо, чтобы отрезок Z покрывал отрезок от 10 до 72.
Итоговая минимальная длина отрезка: 62.
Задача 7
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула
(¬ДЕЛ(x, A) → (ДЕЛ(x, 27) → ¬ДЕЛ(x, 89))) ∧ (A > 300)
тождественно истинна (то есть принимает значение 1) при любом натуральном значении переменной x?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 5000):
fl = True
for x in range(1, 5000):
F = ((not DEL(x, A)) <= ((DEL(x, 27)) <= (not DEL(x, 89)))) and (A > 300)
if not F:
fl = False
break
if fl:
print(A)
Первое значение будет наименьшим.
Задача 8
Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула
¬ДЕЛ(x, A) → (¬ДЕЛ(x, 6) ∧ ¬ДЕЛ(x, 15))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 5000):
fl = True
for x in range(1, 5000):
F = (not DEL(x, A)) <= (not DEL(x, 6) and not DEL(x, 15))
if not F:
fl = False
break
if fl:
print(A)
Последнее значение будет наибольшим.
Задача 9
Элементами множеств A, P и Q являются натуральные числа, причём:
- P = {1, 2, 3, 11, 17, 21, 30, 81, 501}
- Q = {1, 3, 55, 501, 700}
Известно, что выражение
((x ∈ A) → (x ∈ P)) ∧ (¬(x ∈ Q) → ¬(x ∈ A)) истинно (то есть принимает значение 1 при любом значении переменной x). Определите наибольшую сумму элементов множества A.
Решение
Упростим выражение
((x ∈ A) → (x ∈ P)) ∧ (¬(x ∈ Q) → ¬(x ∈ A))
Избавимся от импликации в первой и второй скобке:
(¬(x ∈ A) V (x ∈ P)) ∧ ((x ∈ Q) V ¬(x ∈ A))
Вынесем ¬(x ∈ A) за скобки:
¬(x ∈ A) V ((x ∈ P) ∧ (x ∈ Q))
Вторая скобка истинна для всех общих элементов множества P и Q. Для покрытия всех оставшихся натуральных чисел с помощью ¬(x ∈ A), элементы множества А должны содержать только общие элементы множества P и Q.
Элементы P, которые входят в Q:
- 1
- 3
- 501
Таким образом, множество A может содержать следующие элементы:
A = {1, 3, 501}
Наибольшая сумма элементов множества A равна: 505.
Задача 10
Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A > 1 формула
¬ДЕЛ(x, A) → (ДЕЛ(x, 3) → ¬ДЕЛ(x, 5))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(2, 5000):
fl = True
for x in range(1, 5000):
F = (not DEL(x, A)) <= ((DEL(x, 3)) <= (not DEL(x, 5)))
if not F:
fl = False
break
if fl:
print(A)
Первое значение будет наименьшим.
Задача 11
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Найдите наибольшее натуральное число A, для которого формула
¬(ДЕЛ(396, A) → ¬ДЕЛ(180, A))
истинна.
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 500):
F = not(DEL(396, A) <= (not(DEL(180, A))))
if F:
print(A)
Последнее значение будет наибольшим.
Задача 12
Обозначим через m & n поразрядную конъюнкцию неотрицательных чисел m и n. Так, например, 13 & 11 = 11012 & 10112 = 10012 = 9.
Для какого наименьшего целого числа A формула
x & 56 ≠ 0 → (x & A = 0 → x & 35 ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?
Решение
Мы можем использовать алгоритм для нахождения всех целых A, при которых данное выражение будет истинным для любых неотрицательных целых x и y.
for A in range(1, 101):
fl = True #А - подходит?
for x in range(0, 101):
F = (x & 56 != 0) <= ((x & A == 0) <= (x & 35 != 0))
if not F:
fl = False
break
if fl:
print(A)
Запустив данный код, мы находим все возможные целые числа A, которые делают выражение истинным для всех положительных целых x и y.
Первое из них будет наименьшим.
Задача 13
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Найдите наибольшее натуральное число A, для которого формула
¬(ДЕЛ(120, A) → ¬ДЕЛ(168, A))
истинна.
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 500):
F = not(DEL(120, A) <= (not(DEL(168, A))))
if F:
print(A)
Последнее значение будет наибольшим.
Задача 14
Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула
ДЕЛ(x, A) → (¬ДЕЛ(x, 35) ∨ ДЕЛ(x, 49))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 5000):
fl = True
for x in range(1, 5000):
F = (DEL(x, A)) <= (not DEL(x, 35) or DEL(x, 49))
if not F:
fl = False
break
if fl:
print(A)
break
Первое значение будет наименьшим.
Задача 15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула
(ДЕЛ(x, A) → ¬(ДЕЛ(x, 24) → ¬ДЕЛ(x, 74))) ∧ (A > 500)
тождественно истинна (то есть принимает значение 1) при любом натуральном значении переменной x?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 5000):
fl = True
for x in range(1, 5000):
F = ((DEL(x, A)) <= (not((DEL(x, 24)) <= (not(DEL(x, 74)))))) and (A > 500)
if not F:
fl = False
break
if fl:
print(A)
Первое значение будет наименьшим.
Задача 16
Обозначим через m & n поразрядную конъюнкцию неотрицательных чисел m и n. Так, например, 13 & 11 = 11012 & 10112 = 10012 = 9.
Для какого наибольшего целого числа A формула
x & A ≠ 0 → (x & 14 = 0 → x & 17 ≠ 0)
тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?
Решение
Мы можем использовать алгоритм для нахождения всех целых A, при которых данное выражение будет истинным для любых неотрицательных целых x и y.
for A in range(1, 101):
fl = True #А - подходит?
for x in range(0, 101):
F = (x & A != 0) <= ((x & 14 == 0) <= (x & 17 != 0))
if not F:
fl = False
break
if fl:
print(A)
Запустив данный код, мы находим все возможные целые числа A, которые делают выражение истинным для всех положительных целых x и y.
Последнее из них будет наибольшим.
Задача 17
На числовой оси даны два отрезка: X = [12; 93] и Y = [54; 150].
Укажите наименьшую возможную длину такого отрезка Z, для которого логическое выражение:
(x ∈ Y) → (¬(x ∈ X) ∧ ¬(x ∈ Z) → ¬(x ∈ Y)) тождественно истинно (то есть принимает значение 1 при любом действительном значении переменной x).
Решение
Упростим выражение, раскрыв все импликации, получим:
¬(x ∈ Y) V (¬(¬(x ∈ X) ∧ ¬(x ∈ Z)) V ¬(x ∈ Y))
Применим закон Де Моргана:
¬(x ∈ Y) V ((x ∈ X) V (x ∈ Z) V ¬(x ∈ Y))
Уберём лишние скобки и применим закон повторения:
¬(x ∈ Y) V (x ∈ X) V (x ∈ Z)
Отрезок X = [12; 93] и отрезок Y = [54; 150] пересекаются в точке 54. Это значит, что для значений x, находящихся в диапазоне от 12 до 93, выражение будет истинным.
Чтобы исключить значения из отрезка Y, которые не попадают в диапазон отрезка X, необходимо, чтобы отрезок Z начинался с точки, которая находится после точки пересечения, то есть с точки 93.
Таким образом, минимальная длина отрезка Z должна составлять:
Z = [93; 150].
Следовательно, наименьшая длина отрезка Z:
L(Z) = 150 - 93 = 57.
Задача 18
Обозначим через ДЕЛ (n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула
ДЕЛ(x, A) → (ДЕЛ(x, 6) ∨ ДЕЛ(x, 15))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Решение
Напишем код для нахождения всех возможных подходящих А:
def DEL(n, m):
return n % m == 0
for A in range(1, 5000):
fl = True
for x in range(1, 5000):
F = (DEL(x, A)) <= (DEL(x, 6) or DEL(x, 15))
if not F:
fl = False
break
if fl:
print(A)
break
Первое значение будет наименьшим.
Задача 19
Для какого наименьшего целого числа A выражение
((x − 15 < A) ∧ (17 − y < A)) ∨ (x · (y + 2) > 65)
тождественно истинно, то есть принимает значение 1 при любых целых положительных x и y?
Решение
Мы можем использовать алгоритм для нахождения наименьшего целого числа A, при котором данное выражение будет истинным для любых положительных целых x и y.
for A in range(1, 101):
fl = True #А - подходит?
for x in range(1, 101):
for y in range(1, 101):
F = ((x - 15 < A) and (17 - y < A)) or (x * (y + 2) > 65)
if not F:
fl = False
break
if not fl:
break
if fl:
print(A)
break
Запустив данный код, мы находим наименьшее целое число A, которое делает выражение истинным для всех положительных целых x и y.
Задача 20
Для какого наименьшего целого числа A выражение:
((x − 30 < A) ∧ (15 − y < A)) ∨ (x · (y + 3) > 60)
тождественно истинно, то есть принимает значение 1 при любых целых положительных x и y?
Решение
Мы можем использовать алгоритм для нахождения наименьшего целого числа A, при котором данное выражение будет истинным для любых положительных целых x и y.
for A in range(1, 101):
fl = True #А - подходит?
for x in range(1, 101):
for y in range(1, 101):
F = ((x - 30 < A) and (15 - y < A)) or (x * (y+3) >= 60)
if not F:
fl = False
break
if not fl:
break
if fl:
print(A)
break
Запустив данный код, мы находим наименьшее целое число A, которое делает выражение истинным для всех положительных целых x и y.
Рекомендуемые курсы подготовки
- 🔥 Изучишь одни из самых фундаментальных тем информатики
- 🔥 Научишься решать 6 задач формата ЕГЭ руками
- 🔥 Начнёшь свой путь в проге
- 🔥 Учёба на Турбо: познакомишься с преподавателями и личным кабинетом
Что тебя ждет?
- 8 вебинаров (1 веб в неделю по 1 часу)
- Тестовые Д/З после каждого занятия
- Конспекты и скрипты к урокам
- Доступ к личному кабинету
- Возможность отрабатывать задания ЕГЭ в любое время
- Чат с единомышленниками
- Поддержка препа 24/7
на бесплатном курсе Турбо ЕГЭ
