ЕГЭ информатика: задание 15

Вариант 1

отрезки

На числовой прямой даны два отрезка: P = [98; 139] и Q = [49; 112]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение (x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P)) истинно (т. е. принимает значение 1) при любом значении переменной x.

Разбор

Шаг 1. Упрощаем. Импликация a → b равна ¬a ∨ b. Раскрываем импликации и применяем законы де Моргана, чтобы выражение стало дизъюнкцией: ¬P ∨ ¬Q ∨ A: A должен покрывать P ∩ Q.

Шаг 2. На прямой. P = [98; 139], Q = [49; 112], их пересечение — [98; 112], объединение — [49; 139].

Шаг 3. Наименьшая длина A — 14.

Ответ: 14

Решение на Python.

P = (98, 139)
Q = (49, 112)

def ok(A):
    for i in range(0, 161 * 4):          # x с шагом 0.25 — концы отрезков целые
        x = i / 4
        p = P[0] <= x <= P[1]
        q = Q[0] <= x <= Q[1]
        a = A[0] <= x <= A[1]
        if not ((not p) or (not ((q and not a) and p))):
            return False
    return True

print(min(a2 - a1 for a1 in range(0, 161) for a2 in range(a1, 161) if ok((a1, a2))))

Вариант 2

делимость ДЕЛ

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа A формула ДЕЛ(x, 35) → (ДЕЛ(x, 18) → ДЕЛ(x, A)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Разбор

Шаг 1. Раскрываем импликации: a → b = ¬a ∨ b. Формула ложна только при определённой комбинации делимостей — выпишем её и посмотрим, какое A её исключает.

Шаг 2. Подбираем A: для каждого кандидата проверяем все x до нескольких тысяч (значения делимости повторяются с периодом НОК чисел 35, 18 и A). Ответ: A = 630.

Ответ: 630

Решение на Python.

def ok(A):
    for x in range(1, 5000):
        if not ((not x % 35 == 0) or (not x % 18 == 0) or x % A == 0):
            return False
    return True

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

Вариант 3

поразрядная конъюнкция

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа A формула (x & 6 ≠ 0) → ((x & 67 = 0) → (x & A ≠ 0)) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Разбор

Шаг 1. Двоичные записи. 6 = 110₂, 67 = 1000011₂.

Шаг 2. Условие «x & m = 0» означает, что в x нет единиц там, где они есть в m. Раскрываем импликации и смотрим, какие биты обязаны (или не имеют права) быть в A.

Шаг 3. Проверка всех x от 0 до 255 перебором даёт A = 4 = 100₂.

Ответ: 4

Решение на Python.

def ok(A):
    for x in range(0, 256):              # старшие биты чисел меньше 128 — не дальше 7-го
        if not ((x & 6 == 0) or (x & 67 != 0) or (x & A != 0)):
            return False
    return True

print(min(A for A in range(0, 256) if ok(A)))

Вариант 4

отрезки

На числовой прямой даны два отрезка: P = [10; 43] и Q = [30; 59]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение (x ∈ P) → ((x ∈ Q) ∨ (x ∈ A)) истинно (т. е. принимает значение 1) при любом значении переменной x.

Разбор

Шаг 1. Упрощаем. Импликация a → b равна ¬a ∨ b. Раскрываем импликации и применяем законы де Моргана, чтобы выражение стало дизъюнкцией: A должен покрывать часть P, не входящую в Q.

Шаг 2. На прямой. P = [10; 43], Q = [30; 59], их пересечение — [30; 43], объединение — [10; 59].

Шаг 3. Наименьшая длина A — 20.

Ответ: 20

Решение на Python.

P = (10, 43)
Q = (30, 59)

def ok(A):
    for i in range(0, 161 * 4):          # x с шагом 0.25 — концы отрезков целые
        x = i / 4
        p = P[0] <= x <= P[1]
        q = Q[0] <= x <= Q[1]
        a = A[0] <= x <= A[1]
        if not ((not p) or q or a):
            return False
    return True

print(min(a2 - a1 for a1 in range(0, 161) for a2 in range(a1, 161) if ok((a1, a2))))

Вариант 5

делимость ДЕЛ

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула ДЕЛ(x, A) → (¬ДЕЛ(x, 12) → ¬ДЕЛ(x, 18)) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Разбор

Шаг 1. Раскрываем импликации: a → b = ¬a ∨ b. Формула ложна только при определённой комбинации делимостей — выпишем её и посмотрим, какое A её исключает.

Шаг 2. Подбираем A: для каждого кандидата проверяем все x до нескольких тысяч (значения делимости повторяются с периодом НОК чисел 12, 18 и A). Ответ: A = 4.

Ответ: 4

Решение на Python.

def ok(A):
    for x in range(1, 5000):
        if not ((not x % A == 0) or x % 12 == 0 or x % 18 != 0):
            return False
    return True

print(min(A for A in range(1, 1001) if ok(A)))

Вариант 6

отрезки

На числовой прямой даны два отрезка: P = [38; 63] и Q = [47; 109]. Укажите наибольшую возможную длину такого отрезка A, что логическое выражение ((x ∈ A) → (x ∈ P)) ∨ (x ∈ Q) истинно (т. е. принимает значение 1) при любом значении переменной x.

Разбор

Шаг 1. Упрощаем. Импликация a → b равна ¬a ∨ b. Раскрываем импликации и применяем законы де Моргана, чтобы выражение стало дизъюнкцией: A должен лежать внутри P ∪ Q.

Шаг 2. На прямой. P = [38; 63], Q = [47; 109], их пересечение — [47; 63], объединение — [38; 109].

Шаг 3. Наибольшая длина A — 71.

Ответ: 71

Решение на Python.

P = (38, 63)
Q = (47, 109)

def ok(A):
    for i in range(0, 161 * 4):          # x с шагом 0.25 — концы отрезков целые
        x = i / 4
        p = P[0] <= x <= P[1]
        q = Q[0] <= x <= Q[1]
        a = A[0] <= x <= A[1]
        if not ((not a or p) or q):
            return False
    return True

print(max(a2 - a1 for a1 in range(0, 161) for a2 in range(a1, 161) if ok((a1, a2))))

Вариант 7

поразрядная конъюнкция

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наименьшего неотрицательного целого числа A формула ((x & 67 = 0) ∧ (x & 92 ≠ 0)) → ¬(x & A = 0) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Разбор

Шаг 1. Двоичные записи. 67 = 1000011₂, 92 = 1011100₂.

Шаг 2. Условие «x & m = 0» означает, что в x нет единиц там, где они есть в m. Раскрываем импликации и смотрим, какие биты обязаны (или не имеют права) быть в A.

Шаг 3. Проверка всех x от 0 до 255 перебором даёт A = 28 = 11100₂.

Ответ: 28

Решение на Python.

def ok(A):
    for x in range(0, 256):              # старшие биты чисел меньше 128 — не дальше 7-го
        if not (not ((x & 67 == 0) and (x & 92 != 0)) or (x & A != 0)):
            return False
    return True

print(min(A for A in range(0, 256) if ok(A)))

Вариант 8

отрезки

На числовой прямой даны два отрезка: P = [37; 121] и Q = [89; 126]. Укажите наименьшую возможную длину такого отрезка A, что логическое выражение ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) истинно (т. е. принимает значение 1) при любом значении переменной x.

Разбор

Шаг 1. Упрощаем. Импликация a → b равна ¬a ∨ b. Раскрываем импликации и применяем законы де Моргана, чтобы выражение стало дизъюнкцией: A должен покрывать P ∩ Q.

Шаг 2. На прямой. P = [37; 121], Q = [89; 126], их пересечение — [89; 121], объединение — [37; 126].

Шаг 3. Наименьшая длина A — 32.

Ответ: 32

Решение на Python.

P = (37, 121)
Q = (89, 126)

def ok(A):
    for i in range(0, 161 * 4):          # x с шагом 0.25 — концы отрезков целые
        x = i / 4
        p = P[0] <= x <= P[1]
        q = Q[0] <= x <= Q[1]
        a = A[0] <= x <= A[1]
        if not ((not (p and q)) or a):
            return False
    return True

print(min(a2 - a1 for a1 in range(0, 161) for a2 in range(a1, 161) if ok((a1, a2))))

Вариант 9

делимость ДЕЛ

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа A формула (ДЕЛ(x, A) ∧ ДЕЛ(x, 21)) → ДЕЛ(x, 14) тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Разбор

Шаг 1. Раскрываем импликации: a → b = ¬a ∨ b. Формула ложна только при определённой комбинации делимостей — выпишем её и посмотрим, какое A её исключает.

Шаг 2. Подбираем A: для каждого кандидата проверяем все x до нескольких тысяч (значения делимости повторяются с периодом НОК чисел 21, 14 и A). Ответ: A = 2.

Ответ: 2

Решение на Python.

def ok(A):
    for x in range(1, 5000):
        if not (not (x % A == 0 and x % 21 == 0) or x % 14 == 0):
            return False
    return True

print(min(A for A in range(1, 1001) if ok(A)))

Вариант 10

поразрядная конъюнкция

Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14 & 5 = 1110₂ & 0101₂ = 0100₂ = 4. Для какого наибольшего неотрицательного целого числа A формула (x & A ≠ 0) → ((x & 74 = 0) → (x & 47 ≠ 0)) тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Разбор

Шаг 1. Двоичные записи. 74 = 1001010₂, 47 = 101111₂.

Шаг 2. Условие «x & m = 0» означает, что в x нет единиц там, где они есть в m. Раскрываем импликации и смотрим, какие биты обязаны (или не имеют права) быть в A.

Шаг 3. Проверка всех x от 0 до 255 перебором даёт A = 111 = 1101111₂.

Ответ: 111

Решение на Python.

def ok(A):
    for x in range(0, 256):              # старшие биты чисел меньше 128 — не дальше 7-го
        if not ((x & A == 0) or (x & 74 != 0) or (x & 47 != 0)):
            return False
    return True

print(max(A for A in range(0, 256) if ok(A)))

Логика: выражение, истинное при любом x

Законы логики

Как решать перебором

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

Разобранные варианты

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Для самостоятельного решения

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15