В этой статье вспомним основные понятия и законы математической логики, а также научимся решать задание №15 из ЕГЭ по информатике с помощью программирования.
Термины, которые будем использовать: таблица истинности, логическая функция, логическая операция, логическая переменная, логическое отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.
Основные понятия
- Единица в алгебре логики принимает значение «истина», а ноль — «ложь».
- Логическая функция — это функция, принимающая в качестве аргументов только единицы или нули и возвращающая одно из этих двух значений.
- Логическая операция — это простейшая логическая функция, которую используют для построения сложных выражений. Например, в математике арифметические знаки («+», «–», «*», «/») используют для составления сложных уравнений — такую же роль играют логические операции для функций.
- Логическая переменная — это переменная, принимающая значение 1 или 0, которая является аргументом логической функции.
- Таблица истинности — это таблица, заполненная 1 и 0, в каждой строке которой описана новая комбинация значений логических переменных и соответствующий ей результат логического выражения.
Таблицы истинности
Каждая логическая функция или операция имеет свою таблицу истинности, давай рассмотрим самые популярные из них:
1. Отрицание (инверсия).
Чаще всего в ЕГЭ встречается следующее обозначение: ¬A, читается «не А», но также можно встретить А.
Отрицание возвращает противоположное значение исходному, но, так как значений всего два, то единица противоположна нулю, а ноль — единице.
Обрати внимание на таблицу истинности для этой логической операции:
| А | ¬A |
|---|---|
| 1 | 0 |
| 0 | 1 |
Слева обозначается значение логической переменной (значение аргумента для функции), справа показан результат операции для текущих входных данных.
2. Логическое И (конъюнкция).
Чаще всего в ЕГЭ встречается следующее обозначение: A∩B, читается «А и Б».
Конъюнкция возвращает истину только в том случае, если обе логические переменные принимают значения единицы, в противном случае она вернёт ложь.
| A | B | A∩B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Для двух переменных количество всевозможных комбинаций равняется четырём.
3. Логическое ИЛИ (дизъюнкция).
Чаще всего в ЕГЭ встречается следующее обозначение: A∪B, читается «А или Б».
Дизъюнкция возвращает ложь только в том случае, когда обе переменные принимают значения нуля, в остальных случаях она вернёт истину.
| A | B | A∪B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Как отличить знаки конъюнкции и дизъюнкции. Над знаком ∩ (логическое И) можно поставить только одну букву И, а над знаком ∪ (логическое ИЛИ) можно разместить сразу обе.
4. Импликация (следование).
Чаще всего в ЕГЭ встречается следующее обозначение: A→B, читается «Из А следует Б» или «Если А, то Б».
Импликация вернёт ложь только тогда, когда из истины следует ложь, в остальных случаях она вернёт истину.
| A | B | A→B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Выражение A→B можно раскрыть как ¬A∪B, то есть вместо знака импликации перед первой переменной появляется отрицание, а между ними — логическое ИЛИ.
Это возможно благодаря тому, что таблица истинности для второго выражения совпадает с таблицей истинности для импликации, то есть обе функции при одинаковых входных данных вернут одинаковый результат.
Давай убедимся в этом и составим таблицу истинности в два шага: сначала выполни операцию отрицания, потом раскрой логическое ИЛИ для каждой из четырёх комбинаций: 00, 01, 10, 11. Проверь себя:
| А | B | ¬A | B | ¬A∪B |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 |
5. Эквивалентность (равносильность).
Чаще всего в ЕГЭ встречается следующее обозначение: A≡B, читается «А эквивалентно Б» или «А равносильно Б».
Эквивалентность вернёт истину тогда, когда обе переменные имеют одинаковые значения, оба ложны или оба истинны, в противном случае вернёт ложь.
| A | B | A≡B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Сопоставим логические операции в алгебре логики с их аналогами на языке Python.
| Алгебра логики | Python |
|---|---|
| ¬A или $\overline{A}$ | not A |
| ∩ | and |
| ∪ | or |
| → | <= |
| ≡ или ~ | == |
| ∈ | in |
| ∉ | not in |
| & | & |
Практикум: решение задач
Рассмотрим каждый тип задания №15, который встречался на реальном ЕГЭ:
Задание 1. Основная волна 2025
Для какого наибольшего целого неотрицательного числа А логическое выражение:
(x⋅y>А)∨(x>y)∨(11>x)
тождественно истинно (т. е. принимает значение 1) при любых целых неотрицательных x и y?
def f(x, y):
# просто переписываем нашу функцию
return (x ⋅ y > A) or (x > y) or (11 > x)
res = 0
# всегда внешний цикл перебирает А, потому что для каждого А нужно проверить множество x и y
for A in range(1000):
# если функция вернула истину для всех пар x и y — функция all вернёт истину (такое А подойдёт)
if all(f(x, y) for x in range(500) for y in range(500)):
# запоминаем наибольшее А
res = A
print(res)
Ответ: 120.
! Важно !
Если ты перебираешь до 1000, и твой ответ = 999, вероятно, есть число А ещё больше, либо где-то в коде ошибка.
Задание 2. Основная волна 2024
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Пусть на числовой прямой дан отрезок B = [70, 90]. Для какого наибольшего натурального числа А логическое выражение:
ДЕЛ(x, А) ∨ ((x ∈ B) → ¬ДЕЛ(x, 22))
истинно (т. е. принимает значение 1) при любом целом положительном значении переменной х?
def f(x):
B = 70 <= x <= 90
# просто переписываем нашу функцию, вместо отрицания ставим знак неравенства
return (x % A == 0) or (B <= (x % 22 != 0))
res = 0
# всегда внешний цикл перебирает А, потому что для каждого А нужно проверить множество x
for A in range(1, 1000):
# если функция вернула истину для всех x — функция all вернёт истину (такое А подойдёт)
if all(f(x) for x in range(1, 500)):
# запоминаем наибольшее А
res = A
print(res)
Ответ: 88.
Задание 3. Основная волна 2024
На числовой прямой даны два отрезка: P = [15;40] и Q = [21;63]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение:
(x∈P)→(((x∈Q)∧¬(x∈A))→¬(x∈P))
истинно (т. е. принимает значение 1) при любом значении переменной х.
def f(x):
# записываем в переменные значения правда/ложь в зависимости от того, попадает ли х в промежуток
P = 15 <= x <= 40
Q = 21 <= x <= 63
A = a1 <= x <= a2
return P <= ((Q and (not A)) <= (not P))
# формируем список точек для проверки (именно в них функция будет принимать новые значения)
# в первый кортеж записываем все известные границы диапазонов из условия
d = [y for x in (15, 40, 21, 63) for y in (x – 0.1, x, x + 0.1)]
res = []
# перебираем границы диапазона А
for a1 in d:
for a2 in d:
# проверяем, что правая граница больше левой и функция истина для всех х
if a2 > a1 and all(f(x) for x in range(–200, 500)):
# добавляем длину отрезка
res.append(round(a2 – a1))
print(min(res))
Ответ: 19.
Задание 4. Открытый вариант 2025
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.
Для какого наименьшего неотрицательного целого числа А логическое выражение:
((x&52≠0)∧(x&48=0))→¬(x&А=0)
истинно (т. е. принимает значение 1) при любом неотрицательном целом значении переменной х?
def f(x):
# просто переписываем нашу функцию
return ((x & 52 != 0) and (x & 48 == 0)) <= (x & A != 0)
# всегда внешний цикл перебирает А, потому что для каждого А нужно проверить множество x
for A in range(1000):
# если функция вернула истину для всех x — функция all вернёт истину (такое А подойдёт)
if all(f(x) for x in range(500)):
print(A)
break
Ответ: 4.
Задание 5. Досрочная волна 2024
На числовой прямой даны два отрезка: B = [24;90] и C = [47;115]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение:
(x∈C)→((¬(x∈A)∧(x∈B))→¬(x∈C))
истинно (т. е. принимает значение 1) при любом значении переменной х.
def f(x):
# записываем в переменные значения правда/ложь в зависимости от того, попадает ли х в промежуток
B = 24 <= x <= 90
C = 47 <= x <= 115
A = a1 <= x <= a2
return C <= (((not A) and B) <= (not C))
# формируем список точек для проверки (именно в них функция будет принимать новые значения)
# в первый кортеж записываем все известные границы диапазонов из условия
d = [y for x in (24, 90, 47, 115) for y in (x – 0.1, x, x + 0.1)]
res = []
# перебираем границы диапазона А
for a1 in d:
for a2 in d:
# проверяем, что правая граница больше левой и функция истина для всех х
if a2 > a1 and all(f(x) for x in range(–200, 500)):
# добавляем длину отрезка
res.append(round(a2 – a1))
print(min(res))
Ответ: 43.
Заключение
Мы повторили основные понятия и законы математической логики, необходимые для решения задания №15 из ЕГЭ по информатике. Теперь ты знаешь, как подходить к таким заданиям системно. Главное — внимательно переписывать логическое выражение на язык программирования и правильно выбирать диапазон перебора. Успешной подготовки и высоких баллов на экзамене!
Автор статьи
