Задание 15. Алгебра логики. Преобразование и анализ логических выражений. ЕГЭ 2026 по информатике
Средний процент выполнения: 68.7%
Ответом к заданию 15 по информатике может быть цифра (число) или слово.
Подпишись на суперполезные материалы
Задачи для практики
Задача 1
Обозначим через ДЕЛ (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
Первое значение будет наименьшим.
Задача 2
Обозначим через ДЕЛ(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)
Последнее значение будет наибольшим.
Задача 3
Обозначим через ДЕЛ(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)
Последнее значение будет наибольшим.
Задача 4
Для какого наименьшего целого числа 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.
Задача 5
Обозначим через ДЕЛ(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)
Первое значение будет наименьшим.
Задача 6
Элементами множеств A, P и Q являются натуральные числа, причём:
- P = {3, 5, 7, 8, 9, 11, 15, 28}
- Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}
Известно, что выражение:
((x ∈ A) → (x ∈ P)) ∧ (¬(x ∈ Q) → ¬(x ∈ A)) истинно при любом значении переменной 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:
- 3
- 9
- 15
Таким образом, множество A может содержать следующие элементы:
A = {3, 9, 15}
Наибольшее количество элементов множества A равно: 3.
Задача 7
Обозначим через 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.
Последнее из них будет наибольшим.
Задача 8
Для какого наименьшего целого числа 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.
Задача 9
На числовой оси даны два отрезка: 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.
Задача 10
На числовой оси даны два отрезка: 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.
Задача 11
Обозначим через ДЕЛ (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)
Первое значение будет наименьшим.
Задача 12
Обозначим через ДЕЛ (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
Первое значение будет наименьшим.
Задача 13
Обозначим через ДЕЛ(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)
Первое значение будет наименьшим.
Задача 14
Обозначим через 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.
Первое из них будет наименьшим.
Задача 15
Обозначим через ДЕЛ (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)
Последнее значение будет наибольшим.
Задача 16
Элементами множеств 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.
Задача 17
Для какого наименьшего целого неотрицательного числа А логическое выражение
(x ≥ 11) \/ (x < y) \/ (x2 + y2 < A)
тождественно истинно (т.е. принимает значение 1) при любых целых неотрицательных x и y?
Решение
for a in range(0, 1000):
flag = True
for x in range(0, 100):
for y in range(0, 100):
if ((x >= 11) or (x < y) or (x**2 + y**2 < a)) == 0:
flag = False
break
if not flag:
break
if flag:
print(a)
break
Задача 18
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 12) → ¬ДЕЛ(x, 6)) ∨ (x+𝐴 ≥ 987)
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение
Для решения этого номера избавимся от импликации:
¬ДЕЛ(x, 12) ∨ ¬ДЕЛ(x, 6) ∨ (x+𝐴 ≥ 987)
Чтобы А влияло на результат, нужно чтобы все выражения, кроме выражения с А были ложны. Тогда мы получим:
когда x делится на 12 и х делится на 6, должно выполниться (x+𝐴 ≥ 987).
х = {12, 24, 36, 48, 60, 72 и т.д.}
Возьмём наименьший х (12)
x+𝐴 ≥ 987
12+𝐴 ≥ 987
𝐴 ≥ 975
Ответ: 975
Задача 19
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 4) → ¬ДЕЛ(x, 8)) ∨ (x+𝐴 ≥ 40)
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение
Для решения этого номера избавимся от импликации:
¬ДЕЛ(x, 4) ∨ ¬ДЕЛ(x, 8) ∨ (x+𝐴 ≥ 40)
Чтобы А влияло на результат, нужно чтобы все выражения, кроме выражения с А были ложны. Тогда мы получим:
когда x делится на 4 и х делится на 8, должно выполниться (x+𝐴 ≥ 40).
х = {8, 16, 24, 32 и т.д.}
Возьмём наименьший х (8)
x+𝐴 ≥ 40
8+𝐴 ≥ 40
𝐴 ≥ 32
Ответ: 32
Задача 20
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наименьшего натурального числа А формула
(ДЕЛ(x, 7) → ¬ДЕЛ(x, 10)) ∨ (x+𝐴 ≥ 100)
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Решение
Для решения этого номера избавимся от импликации:
¬ДЕЛ(x, 7) ∨ ¬ДЕЛ(x, 10) ∨ (x+𝐴 ≥ 100)
Чтобы А влияло на результат, нужно чтобы все выражения, кроме выражения с А были ложны. Тогда мы получим:
когда x делится на 7 и х делится на 10, должно выполниться (x+𝐴 ≥ 100).
х = {70, 140 и т.д.}
Возьмём наименьший х (70)
x+𝐴 ≥ 100
70+𝐴 ≥ 100
𝐴 ≥ 30
Ответ:30
Рекомендуемые курсы подготовки
- Узнаешь всё про кодирование: что это такое и как происходит
- Познакомишься с Условием Фано: как оно примняется и почему важно
- Научишься считать колиечтсво информации и сколько под неё нужно выделить памяти
на бесплатном курсе Турбо ЕГЭ
