Задание 15 ЕГЭ по информатике считается заданием повышенной сложности и требует глубокого понимания основ математической логики. Оно направлено на проверку знаний ключевых понятий, законов и приемов работы с логическими выражениями.
Давайте рассмотрим основные понятия и теоретические аспекты, которые необходимы для успешного выполнения этого задания:
Алгебра логики (булева алгебра) — это раздел математики, который занимается операциями и правилами, применяемыми к логическим выражениям. В алгебре логики рассматриваются высказывания, которые могут быть либо истинными, либо ложными, и на основе таких высказываний выполняются различные логические операции, такие как «и», «или», «не» и другие.
Таблицы истинности — это удобный способ представить и проанализировать, как изменяется результат логической операции в зависимости от значений входных высказываний. В такой таблице перечислены все возможные комбинации истинности (истина или ложь) для исходных высказываний, а также указано значение результата операции для каждой из этих комбинаций.
Логические высказывания могут комбинироваться друг с другом с помощью логических операций:
1. Конъюнкция (логическое «И»)
Обозначения: A ∧ B, A ⋅ B, A & B, A ∩ B, A and B, AB
Конъюнкция, или логическое «И», — это операция, которая возвращает истинное значение только тогда, когда оба высказывания истинны. Если хотя бы одно из высказываний ложно, то и результат будет ложным.
Пример:
Результат A ∧ B: истина, если оба утверждения верны, в противном случае — ложь.
Таблица истинности для операции конъюнкции:
2. Дизъюнкция (логическое «ИЛИ»)
Обозначения: A ∨ B, A + B, A ∪ B, A or B
Дизъюнкция, или логическое «ИЛИ», возвращает истину, если хотя бы одно из высказываний истинно. Ложь получается только тогда, когда оба высказывания ложны.
Пример:
Результат A ∨ B: истина, так как хотя бы одно из утверждений истинно.
Таблица истинности для операции дизъюнкции:
3. Отрицание (логическое «НЕ»)
Обозначения: ¬A, ∼A, Ā, NOT A
Отрицание, или логическое «НЕ», меняет значение истинности высказывания на противоположное. Если исходное высказывание истинно, то результат его отрицания будет ложным, и наоборот.
Пример:
Таблица истинности для операции отрицания:
4. Импликация (логическое «ЕСЛИ..., ТО...»)
Обозначения: A→B, A⇒B, A⊃B
Импликация — это условное высказывание, которое говорит, что если первое утверждение (предпосылка) истинно, то второе утверждение (следствие) также должно быть истинно. Импликация ложна только в случае, если первое утверждение истинно, а второе ложно; во всех других случаях она считается истинной.
Пример:
Результат A→B: истина, потому что в случае дождя улица действительно мокрая.
Таблица истинности для операции импликации:
5. Эквиваленция (логическое «РАВНОЗНАЧНОСТЬ»)
Обозначения: A↔B, A⇔B, A≡B
Эквиваленция — это операция, которая возвращает истину, когда оба высказывания имеют одинаковое значение истинности (оба истинны или оба ложны). Если значения истинности высказываний различны, эквиваленция будет ложной.
Пример:
Результат A↔B: истина, так как оба утверждения истинны.
Таблица истинности для операции эквиваленции:
Также для решения задачи очень важно помнить про порядок выполнения логических операций:
Также для решения этого задания могут понадобиться основные законы алгебры логики:
Построение таблицы истинности — это процесс, в котором перечисляются все возможные комбинации значений переменных логического выражения и вычисляются результаты выражения для каждой комбинации. Вот алгоритм построения таблицы истинности:
1. Определи количество переменных: сначала определите, сколько логических переменных используется в выражении (например, A, B, C).
2. Найди число строк: для n переменных потребуется 2^n строк, поскольку каждая переменная может принимать одно из двух значений (0 или 1), и нужно учитывать все возможные комбинации. Например, для двух переменных A и B потребуется 2^2 = 4 строки, а для трех переменных 2^3 = 8.
3. Заполни колонки переменных: создайте отдельные колонки для каждой переменной и начните заполнять их значениями 0 и 1. Распределяйте значения так, чтобы каждая переменная менялась с разной частотой:
4. Вычисли промежуточные результаты: если логическое выражение сложное и содержит несколько операций, добавьте столбцы для промежуточных операций, таких как ¬A, A ∧ B, A ∨ B, и заполните их значениями для каждой строки. Не забывайте про порядок выполнения логических операций!
5. Рассчитай итоговое выражение: после заполнения всех промежуточных столбцов определите значение итогового выражения для каждой строки, используя уже вычисленные значения. Запишите полученные значения в последний столбец таблицы.
6. Проверь правильность: убедитесь, что каждая комбинация возможных значений переменных и соответствующие результаты выражения указаны верно.
Таким образом, таблица истинности будет наглядно показывать, каким будет результат логического выражения для каждой возможной комбинации входных значений.
Побитовая конъюнкция — это операция, которая выполняется между двумя числами на уровне их битов. Её суть заключается в том, чтобы сравнить каждый бит двух чисел и вернуть 1 только в тех позициях, где оба сравниваемых бита равны 1. Во всех остальных позициях результат будет 0.
Как работает побитовая конъюнкция?
1. Числа преобразуются в двоичную систему (последовательности 0 и 1).
2. Сравниваются соответствующие биты (поразрядно) двух чисел.
3. На каждой позиции возвращается 1, если оба бита равны 1, иначе — 0.
В программировании побитовая конъюнкция обозначается как &.
Пример
Возьмём два числа: 14 и 5.
Выполним побитовую конъюнкцию:
1110 (14)
& 0101 (5)
----
0100 (результат = 4)
В результате получится число 4, так как только в третьем бите (слева направо) оба числа имеют 1.
Для программного способа решения задачи нам нужно знать некоторые функции и библиотеки языка Python:
1) itertools — это встроенный модуль в Python, который предоставляет множество удобных инструментов для работы с итераторами. Он содержит функции для создания и работы с различными последовательностями и комбинациями данных, позволяя работать с огромными наборами данных более эффективно и лаконично.
Основные особенности модуля:
Пример: вы можете использовать itertools для создания всех возможных комбинаций из списка, фильтрации данных, объединения или повторения элементов.
2) combinations — это функция из модуля itertools, которая генерирует все возможные комбинации определённой длины из заданной последовательности. При этом элементы в комбинации не повторяются, и порядок элементов не имеет значения.
Результатом будут все возможные пары из [1, 2, 3]
3) Цикл for в Python — это инструмент, который позволяет выполнять один и тот же блок кода несколько раз, перебирая элементы из какой-либо последовательности, например списка, строки, диапазона чисел или другого итерируемого объекта. Например:
Этот код перебирает список numbers, на каждой итерации сохраняет текущий элемент в переменную num, печатает значение num.
4) Оператор if проверяет, выполняется ли какое-то условие, и, если оно истинно (то есть True), выполняет блок кода. Это позволяет программе принимать решения на основе условий. Например:
В этом примере, если number больше 5, будет выполнен первый блок, иначе — блок после else
5) all — это встроенная функция Python, которая проверяет, выполнено ли все условия или все элементы истинны в итерируемом объекте (например, списке, строке, множестве).
Как работает:
Перейдём к примеру решения прототипов задач:
Разберём задачу №15 ЕГЭ 2025 из демоверсии ФИПИ:
На числовой прямой даны два отрезка: P = [15; 40] и Q = [21; 63]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно (т.е. принимает значение 1) при любом значении переменной x.
Решение с помощью программирования:
1. Открываем нашу среду разработки и анализируем условие: нам нужно найти минимальную длину отрезка A, при которой выражение (x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) всегда истинно для любого x.
2. Понимание логического выражения:
Выражение (x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) будет истинным, когда x ∈ P, выполнение (((x ∈ Q) ∧ ¬(x ∈ A)) должно приводить к ¬(x ∈ P).
Иными словами, отрезок A должен быть таким, чтобы соблюдалась эта логика для всех x в P и Q.
3. Мы создаём массив ox, представляющий все значения x с шагом 0.25 от 10 до 65 (диапазон чуть шире P и Q, чтобы учесть все случаи).
4. Функция func(x) проверяет истинность логического выражения для заданных границ a1 и a2 (границы отрезка A).
5. Используем itertools.combinations(ox, 2) для перебора всех возможных пар значений (a1, a2), где a1 < a2. Для каждой пары вычисляем разницу a2 − a1 (длина отрезка A).
6. Для каждого отрезка A = [a1, a2] проверяем, выполняется ли логическое выражение func(x) для всех значений x в ox.
7. В конце выбираем минимальную длину отрезка A (просят по условию), при которой логическое выражение истинно.
8. На выходе алгоритм возвращает минимальную длину отрезка A, которая гарантирует истинность логического выражения (это и есть наш ответ).
Ответ: 19
Досрочная волна 2021:
На числовой прямой даны два отрезка: P = [17; 54] и Q = [37; 83]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение
(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))
истинно (т.е. принимает значение 1) при любом значении переменной x.
Решение с помощью аналитики:
1. Сначала давайте преобразуем наше длинное выражение: избавимся от записи «x ∈», заменив её просто записью отрезка (например «x ∈ P» заменим просто «P»): P → ((Q ∧ ¬A) → ¬P)
2. Воспользуемся эквивалентностью логических выражений: A → B эквивалентно ¬A ∨ B, то есть P → ((Q ∧ ¬A) → ¬P) эквивалентно P → (¬(Q ∧ ¬A) ∨ ¬P) (преобразовали выражение в скобках), эквивалентно ¬P ∨ (¬(Q ∧ ¬A) ∨ ¬P) (преобразовали внешнее выражение)
3. Теперь воспользуемся законом Де Моргана: ¬(A ∧ B) = ¬A ∨ ¬B:
¬P ∨ ((¬Q ∨ A) ∨ ¬P) (здесь мы пользуемся ¬(¬A) = A)
4. По ассоциативности (A ∨ (B ∨ C) = A ∨ B ∨ C) получим ¬P ∨ ¬Q ∨ A ∨ ¬P. А т.к. A ∨ A = A, то можем наше выражение можно записать ¬P ∨ ¬Q ∨ A.
5. Инвертируем выражение ¬(¬P ∨ ¬Q) = P ∧ Q, тогда ¬P ∨ ¬Q ∨ A = ¬(P ∧ Q) ∨ A. Мы помним, что это выражение означает, что x принадлежит каждому отрезку. Выражение должно быть равно единице и x ∈ A должно выполняться (по условию), тогда давайте рассмотрим 2 варианта:
1) ¬(P ∧ Q) = 0, A = 1;
2) ¬(P ∧ Q) = 1, A = 1
6. Изобразим эти случаи на числовой прямой (значения x отмечены фиолетовым цветом):
7. Мы видим, что минимальная возможная длина отрезка A равна 54 – 37 = 17.
Ответ: 17
Досрочная волна 2024:
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа A логическое выражение
¬ДЕЛ(x, A) → (ДЕЛ(x, 28) → ¬ДЕЛ(x, 49))
истинно (т.е. принимает значение 1) при любом натуральном значении переменной x?
Решение программированием:
1. Открываем нашу среду разработки и анализируем условие: ДЕЛ(x, m) означает, что x делится на m без остатка (x mod m = 0). Перепишем выражение с использованием эквивалентности логических операций: (x % A != 0) → ((x % 28 == 0) → (x % 49 != 0)).
2. Создаем функцию func(x), которая проверяет истинность выражения для каждого x:
def func(x): return (x % a != 0) <= ((x % 28 == 0) <= (x % 49 != 0)) (помним о том, что импликация эквивалентна <=)
3. Мы проверяем для каждого A от 1 до 999 (если сомневаетесь, диапазон можно сделать больше), выполняется ли условие для всех x от 1 до 100000 (тут тоже диапазон можно ставить больше, но обычного этого вполне достаточно):
4. Если условие выполняется для всех x, мы выводим A, используя: print(a)
Так как задача требует найти наибольшее значение A, программа будет выводить все подходящие значения A, и последним выведенным будет искомое наибольшее.
Ответ: 196
Основная волна 08.06.2024:
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Пусть на числовой прямой дан отрезок B = [70, 90].
Для какого наибольшего натурального числа A логическое выражение
ДЕЛ(x, A) ∨ ((x ∈ B) → ¬ДЕЛ(x, 22))
истинно (т.е. принимает значение 1) при любом целом положительном значении переменной x?
Решение аналитическим способом:
1. Анализируем условие задачи:У нас есть логическое выражение: ДЕЛ(x, A) ∨ ((x ∈ B) → ¬ДЕЛ(x, 22)), где:
Задача состоит в нахождении наибольшего значения A, при котором выражение истинно (= 1) для всех x > 0.
2. Упростим логическое выражение:Сначала преобразуем импликацию: (x ∈ B) → ¬ДЕЛ(x, 22) ≡ ¬(x ∈ B) ∨ ¬ДЕЛ(x, 22)
Подставим это в изначальное выражение: ДЕЛ(x, A) ∨ (¬(x ∈ B) ∨ ¬ДЕЛ(x, 22))
Сгруппируем: (ДЕЛ(x, A) ∨ ¬(x ∈ B)) ∨ ¬ДЕЛ(x, 22)
3. Разберём возможные случаи для x:
1) Если ДЕЛ(x, A) = 1 (то есть x делится на A), то всё выражение становится истинным независимо от остальных условий.
2) Если ДЕЛ(x, A) = 0 (то есть x не делится на A), то выражение истинно только если: ¬(x ∈ B) ∨ ¬ДЕЛ(x, 22) = 1
4. Рассмотрим x ∈ B = [70, 90]Если x ∈ B, то условие упрощается: ¬ДЕЛ(x, 22) = 1. То есть, x не должно делиться на 22. Если x ∉ B, то ¬(x ∈ B) = 1, и всё выражение автоматически истинно.
5. Ограничение на A:Теперь важно, чтобы ДЕЛ(x, A) гарантировал истинность выражения для всех x > 0. Чтобы выражение было истинно для любого x, A должно быть таким, чтобы оно покрывало все случаи, когда (x ∈ B) ∧ ДЕЛ(x, 22) = 1
Числа x ∈ B, которые делятся на 22, — это пересечение [70, 90] с числами, кратными 22: {0, 22, 44, 66, 88, … } ∩ [70, 90] = {88}. Значит, единственное число из отрезка B, которое делится на 22, — это 88.
Для выражения быть истинным, 88 обязательно должно делиться на A. Таким образом, A должно быть делителем числа 88.
6. Найдём наибольшее A:Делители числа 88: 1, 2, 4, 8, 11, 22, 44, 88. Наибольшее значение A из этого списка — 88.
7. Проверка:Если A = 88, то:
Ответ: 88
Основная волна 19.06.2024 (Центр):
Для какого наибольшего целого неотрицательного числа A формула
(x + y ≤ 30) ∨ (y ≤ x + 2) ∨ (y ≥ A)
тождественно истинна (т.е. принимает значение 1) при любых целых положительных x и y?
Решение с помощью программирования:
1. Анализируем условие задачи: у нас есть три подвыражения, соединённых логической операцией "или" (∨):
Логическое выражение истинно для любых x и y, если хотя бы одно из трёх подвыражений истинно для всех комбинаций x и y. Задача — найти максимальное A, при котором это выполняется.
2. Чтобы выражение было истинным для любых x и y:
Поэтому задача сводится к поиску такого A, при котором для всех y < A выполняется хотя бы одно из двух условий:
1) x + y ≤ 30;
2) y ≤ x + 2
3. Перебираем значения A: для проверки каждого значения A перебираем x и y (в коде — в пределах большого диапазона, например 1 ≤ x, y < 1000).
Проверяем, выполняется ли выражение (x + y ≤ 30) ∨ (y ≤ x + 2) ∨ (y ≥ A) для всех комбинаций x и y. Если это так, сохраняем значение A.
4. Поскольку задача требует найти наибольшее значение A, проще проверять значения A, начиная с больших (например, от 1000 вниз). Как только мы найдём первое значение A, для которого выражение выполняется для всех x и y, это и будет наибольшее A.
Ответ: 17
Основная волна 04.07.2024:
Для какого наибольшего целого неотрицательного числа A формула
(x + y ≤ 24) ∨ (y ≤ x - 2) ∨ (y ≥ A)
тождественно истинна (т.е. принимает значение 1) при любых целых положительных x и y?
Решение аналитикой:
1. Нам нужно найти наибольшее неотрицательное целое число A, при котором формула: (x + y ≤ 24) ∨ (y ≤ x - 2) ∨ (y ≥ A) была тождественно истинна для любых положительных целых чисел x и y.
2. Ищем случаи, когда первые два условия ложны. Формула будет ложной только тогда, когда все три условия ложны одновременно. Поэтому нам нужно найти такие значения x и y, при которых:
1) x + y > 24 (первое условие ложно);
2) y > x − 2 (второе условие ложно).
3. Выражаем y из условий: y > 24 – x (из первого условия); y > x -2 (из второго). Таким образом, для одновременного выполнения обоих условий y должно быть больше максимума из двух выражений: y > max(24 − x, x − 2)
4. Наша цель — найти такие значения x, при которых y минимально. Рассмотрим функцию: f(x) = max(24 − x, x − 2). Найдем минимальное значение y при различных x:
для x = 13: f(13) = max(24 − 13, 13 − 2) = max(11, 11) = 11; y > 11 ⟹ y ≥ 12
для x = 12: f(12) = max(24 − 12, 12 − 2) = max(12, 10) = 12; y > 12 ⟹ y ≥ 13
Видим, что минимальное y достигается при x = 13, где y ≥ 12.
5. Чтобы формула была истинна при этих x и y, третье условие должно быть истинным: y ≥ A. Подставляем минимальное y = 12: 12 ≥ A ⟹ A ≤ 12. Таким образом, наибольшее целое A = 12
6. Проверяем полученное значение A: для любых положительных целых x и y:
Поскольку минимальное y в этом случае равно 12, то при A = 12 формула всегда истинна.
Ответ: 12
Следующее задание из варианта с досрочной волны(I) 2023:
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например,
14 & 5 = 11102 & 01012 = 01002 = 4
Для какого наименьшего неотрицательного целого числа A формула
x & 39 = 0 ∨ (x & 11 = 0 → ¬(x & A = 0))
тождественно истинна (т.е. принимает значение 1) при любом неотрицательном целом значении переменной x?
Решение с помощью программирования:
1. Переводим задачу на язык программирования: мы работаем с поразрядной конъюнкцией (&) чисел. Нам необходимо найти наименьшее неотрицательное целое число A, при котором выражение: x & 39 = 0 ∨ (x & 11 = 0 → ¬(x & A = 0)) истинно для любого x. Упростим выражение:
2. Определяем логическое выражение в функции (def func(x): return (x & 39 == 0) or ((x & 11 == 0) <= (x & a != 0))):
3. Мы ищем наименьшее значение A, поэтому перебираем A от 0 до 999:
for a in range(1000):
a — это текущее проверяемое значение.
4. Проверка условия для всех x: для каждого значения a, мы проверяем, выполняется ли функция func(x) для всех x от 0 до 999:
if all(func(x) for x in range(1000)):
Функция all возвращает True, если func(x) == 1 для всех x в заданном диапазоне. Таким образом, мы проверяем истинность выражения для всех x.
5. Вывод результата: как только мы находим значение a, при котором выражение истинно для всех x, мы его выводим и завершаем цикл:
print(a)
break
6. Итоговый результат: алгоритм завершится, как только найдётся наименьшее A, при котором формула истинна для всех x.
Ответ: 36
Для закрепления материала разберём аналогичную задачу:
Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Так, например, 14 & 5 = 11102 & 01012 = 01002 = 4. Для какого наименьшего неотрицательного целого числа А формула
x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?
Решение аналитическим способом:
1. Разбираем битовые операции: для начала рассмотрим побитовые операции (&) и запишем двоичные представления чисел:
2. Анализируем формулу: x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0) раскрывается так: если x & 29 ≠ 0 (т.е. у x есть хотя бы один бит, совпадающий с 29), и при этом x & 17 = 0 (т.е. биты 4 и 0 у x не установлены), то должно выполняться x & A ≠ 0 (т.е. у A должен быть хотя бы один бит, совпадающий с битами x).
3. Определяем критические биты:
Таким образом, остаются только биты 3 и 2. Это значит, что у x должен быть установлен хотя бы один из этих битов.
4. Ищем минимальное A: нам нужно подобрать A, чтобы выполнялось x & A ≠ 0, если у x установлен хотя бы один из битов 3 или 2. Рассмотрим варианты:
1) A = 4 (бит 2 установлен). Не подходит, так как если у x установлен только бит 3, то x & A = 0.
2) A = 8 (бит 3 установлен). Не подходит, так как если у x установлен только бит 2, то x & A = 0.
3) A = 12 (биты 3 и 2 установлены). Подходит, так как любой x, у которого есть бит 2 или 3, обязательно даст x & A ≠ 0
5. Проверяем решение: при A=12 (двоичное 11002): если x содержит бит 3 или 2 (и при этом биты 4 и 0 не установлены), то x & A ≠ 0 всегда выполняется. Таким образом, A = 12 удовлетворяет формуле.
Ответ: 12
Задание №15 ЕГЭ по информатике проверяет глубокое понимание логики, операций над числами и работу с логическими выражениями. Оно требует не только теоретических знаний, но и умения грамотно использовать программирование для поиска решений.
Основные знания для выполнения задания:
1. Логические операции и таблицы истинности:
Понимать порядок выполнения логических операций и их эквивалентности.
2. Преобразование логических выражений:
3. Работа с отрезками числовой прямой:
4. Побитовые операции:
5. Программирование:
Небольшие лайфхаки:
Следуя этим рекомендациям, вы сможете решать задачи №15 уверенно и без лишних затруднений.
Удачи на экзамене!
В варианте ЕГЭ-2025 две задачи по теории вероятностей — это №4 и №5. По заданию 5 в Интернете почти нет доступных материалов. Но в нашем бесплатном мини-курсе все это есть.
