Задание 15 ЕГЭ по информатике: законы математической логики

Задание 15 ЕГЭ по информатике проверяет знание понятий и законов математической логики: нужно найти число A или отрезок A, при котором логическое выражение истинно при любом x. Решают его, выясняя, при каких x выражение может стать ложным, или перебором на Python.

Как решать

Выражение должно быть истинным при любом x, поэтому удобнее искать, когда оно ложно. Дизъюнкция ложна, только если ложны все её части; импликация P → Q ложна, только если P истинно, а Q ложно. Запишите условия ложности и найдите все x, которые под них попадают: A нужно выбрать так, чтобы таких x не осталось.

Выражения с ДЕЛ(x, A). Если A стоит в части, которая должна спасать выражение, то A обязано делить все x, при которых остальные части ложны. Выпишите эти x: наибольшее подходящее A равно их наибольшему общему делителю.

Выражения с отрезками. Отметьте отрезки P и Q на числовой прямой и найдите точки, в которых выражение ложно без A. Отрезок A должен покрыть все эти точки; если они образуют два куска, A покрывает и промежуток между ними. Длина отрезка равна разности его концов.

Выражения с поразрядной конъюнкцией &. Запишите константы в двоичной системе. Условие x & 22 = 0 означает, что у x стоят нули во всех разрядах, где у числа 22 единицы. Выясните, какие разряды x могут быть единичными при ложных остальных частях, и соберите A из этих разрядов.

Проверка на Python — перебор: для каждого кандидата A выражение проверяется при всех x из достаточно широкого диапазона. Для отрезков берите точки с шагом 0,5, чтобы учесть открытые концы; для поразрядных операций — все числа меньше 2ᵏ, где k — число разрядов самой длинной константы.

Примеры с решением

Пример 1

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». На числовой прямой дан отрезок B = [40; 80].

Для какого наибольшего натурального числа A логическое выражение

(x ∈ B) → (ДЕЛ(x, 18) → ДЕЛ(x, A))

истинно, то есть принимает значение 1, при любом целом положительном значении переменной x?

Проверка ответа на Python

def dvd(n, m):
    """ДЕЛ(n, m): n делится на m без остатка."""
    return n % m == 0


def ok(a):
    for x in range(1, 1001):
        in_b = 40 <= x <= 80
        # (x ∈ B) → (ДЕЛ(x, 18) → ДЕЛ(x, A))
        if not ((not in_b) or (not dvd(x, 18)) or dvd(x, a)):
            return False
    return True


print(max(a for a in range(1, 1001) if ok(a)))

Ответ: 18

Выражение ложно, только если x лежит на отрезке B, делится на 18 и не делится на A. На отрезке [40; 80] на 18 делятся 54 и 72, поэтому A должно делить оба числа. Наибольший общий делитель 54 и 72 равен 18, значит, A = 18. При остальных x выражение истинно при любом A.

Пример 2

На числовой прямой даны отрезки P = [15; 40] и Q = [25; 65]. Укажите наименьшую возможную длину отрезка A, для которого логическое выражение

((x ∈ P) ∨ (x ∈ Q)) → ((x ∈ A) ∨ ((x ∈ P) ∧ (x ∈ Q)))

истинно, то есть принимает значение 1, при любом значении переменной x.

Проверка ответа на Python

P = (15, 40)
Q = (25, 65)


def inside(x, seg):
    return seg[0] <= x <= seg[1]


# Точки с шагом 0.5: в них формула становится ложной, если x не лежит в A.
need = []
for k in range(0, 201):
    x = k / 2
    p, q = inside(x, P), inside(x, Q)
    formula_without_a = (not (p or q)) or (p and q)
    if not formula_without_a:
        need.append(x)
print(int(max(need) - min(need)))

Ответ: 50

Выражение ложно, когда x принадлежит ровно одному из отрезков P и Q и не принадлежит A. Точки, которые лежат ровно в одном отрезке, образуют два куска: [15; 25) и (40; 65]. Отрезок A должен содержать оба куска, а значит, и промежуток между ними. Наименьший такой отрезок — [15; 65], его длина 50.

Пример 3

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа A формула

(x & 58 ≠ 0) → ((x & 22 = 0) → (x & A ≠ 0))

тождественно истинна, то есть принимает значение 1 при любом неотрицательном целом значении переменной x?

Проверка ответа на Python

def ok(a):
    for x in range(256):
        f = (x & 58 == 0) or (x & 22 != 0) or (x & a != 0)
        if not f:
            return False
    return True


print(min(a for a in range(256) if ok(a)))

Ответ: 40

Формула ложна, когда x & 58 ≠ 0, x & 22 = 0 и x & A = 0. В двоичной записи 58 = 111010₂ (единицы в разрядах 1, 3, 4, 5), 22 = 010110₂ (разряды 1, 2, 4). Условие x & 22 = 0 запрещает единицы в разрядах 1, 2 и 4, поэтому x & 58 ≠ 0 возможно только за счёт разрядов 3 или 5. При x = 8 и x = 32 первые две части истинны, и A обязано содержать разряды 3 и 5. Наименьшее такое A = 8 + 32 = 40.

Типичные ошибки

Потренироваться на тренажёре

Частые вопросы

Что значит «тождественно истинна»?

Выражение принимает значение 1 при любом допустимом значении переменной x. Достаточно одного x, при котором выражение ложно, чтобы A не подошло.

Какой диапазон x перебирать в программе?

Такой, чтобы в него попали все значения, от которых зависит ответ. Для отрезков — все точки от левого конца самого левого отрезка до правого конца самого правого с шагом 0,5, для поразрядных операций — все числа меньше 2ᵏ, для ДЕЛ с отрезком — числа до 1000.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 14 и задание 16.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.