Пробный урок
📘 ЕГЭ по информатике 2027 · задание 15 из 27

Задание 15 ЕГЭ по информатике: Основные понятия и законы алгебры логики

Что проверяет задание 15, сколько баллов оно приносит и сколько времени на него закладывать — и 3 примера в формате ФИПИ с подробным решением и ответом.

Уровень
повышенный
Максимум
1 балл
Время
~3 минуты
Компьютер
не нужен

Примеры задания 15 с решениями

Сначала попробуйте решить сами, затем откройте решение и сверьте ответ

Пример 1

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Для какого наименьшего неотрицательного целого числа A формула (x & 29 ≠ 0) → ((x & 12 = 0) → (x & A ≠ 0)) тождественно истинна, то есть принимает значение 1 при любом неотрицательном целом значении x?
Показать решение и ответ
1. Импликация ложна только в одном случае: x & 29 ≠ 0, x & 12 = 0 и x & A = 0. Нужно выбрать A так, чтобы этот случай был невозможен. 2. 29 = 11101₂ (биты 4, 3, 2, 0), 12 = 01100₂ (биты 3, 2). 3. x & 12 = 0 — у x нет битов 3 и 2. Тогда x & 29 ≠ 0 значит, что у x есть бит 4 или бит 0. 4. Для каждого такого x должно быть x & A ≠ 0. Значит, A должно содержать и бит 4, и бит 0 (иначе x = 16 или x = 1 сделают формулу ложной). 5. Наименьшее такое A = 10001₂ = 17. Проверка перебором:
for A in range(256):                                    # перебираем A по возрастанию
    ok = True                                           # предполагаем, что A подходит
    for x in range(1024):                               # проверяем x; старшие биты на ответ не влияют
        f = (x & 29 == 0) or (x & 12 != 0) or (x & A != 0)   # a → (b → c) = ¬a ∨ ¬b ∨ c
        if not f:                                       # нашли x, при котором формула ложна
            ok = False                                  # A не подходит
            break                                       # дальше проверять незачем
    if ok:                                              # формула истинна при всех x
        print(A)                                        # первое такое A — наименьшее
        break                                           # остановка

Ответ: 17

Пример 2

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула ¬ДЕЛ(x, A) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4)) тождественно истинна, то есть принимает значение 1 при любом натуральном x?
Показать решение и ответ
1. Формула ложна только при ¬ДЕЛ(x, A) = 1, ДЕЛ(x, 6) = 1 и ДЕЛ(x, 4) = 1, то есть когда x делится на 6 и на 4, но не делится на A. 2. Делится на 6 и на 4 — значит, делится на НОК(6, 4) = 12. 3. Чтобы ложных случаев не было, каждое число, кратное 12, должно делиться на A. Это значит, что A — делитель 12. 4. Наибольший делитель 12 — само 12. Проверка перебором:
best = 0                                                      # наибольшее подходящее A
for A in range(1, 1000):                                      # перебираем A
    ok = all(x % A == 0 or x % 6 != 0 or x % 4 != 0           # ¬a → (b → ¬c) = a ∨ ¬b ∨ ¬c
             for x in range(1, 5000))                         # проверяем много x
    if ok:                                                    # формула истинна при всех x
        best = A                                              # запоминаем — ищем наибольшее
print(best)                                                   # 12

Ответ: 12

Пример 3

На числовой прямой даны два отрезка: P = [10, 29] и Q = [13, 18]. Укажите наименьшую возможную длину такого отрезка A, что формула (x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) тождественно истинна, то есть принимает значение 1 при любом значении переменной x.
Показать решение и ответ
1. Формула ложна, только если x ∈ P, x ∈ Q, x ∉ A и при этом ¬(x ∈ P) ложно, то есть x ∈ P. 2. Итого ложна при x ∈ P ∩ Q и x ∉ A. P ∩ Q = [13, 18]. 3. Чтобы ложных случаев не было, A должен покрывать весь отрезок [13, 18]. 4. Наименьший такой A — сам [13, 18], его длина 18 − 13 = 5.

Ответ: 5

Не получается задание 15? Разберём на пробном уроке

Бесплатно покажем, как решать задание 15 и похожие, определим пробелы и составим план подготовки к ЕГЭ.

Записаться бесплатно

Все задания ЕГЭ по информатике

Структура экзамена, баллы и темы — на странице программы ЕГЭ по информатике