Задача к ЕГЭ по информатике на тему «Деление без остатка» №1

Просмотров 6 Комментарии 0

Обозначим через ДЕЛ( $n$ , $m$ ) утверждение «натуральное число $n$ делится без остатка на натуральное число $m$ ». Для какого наименьшего натурального числа $A$ формула

(Д Е Л(x,A) ∧¬ ДЕ Л(x,15)) → (Д ЕЛ (x,18)∨Д Е Л(x,15))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной $x$ )?

Решение руками

Введем обозначения: $A = Д ЕЛ (x, A ),P = ДЕ Л(x, 15),Q = ДЕ Л (x, 18))$

Таким образом истиным для всех $x$ должно быть выражение $(A∧ P-) → (Q ∨ P)$ .Упростим это выражение, раскрыв импликацию: $-- A ∨ Q ∨ P$ .

Из этой формулы видно, что множество $A$ должно перекрыть множество, которое не перекрыто множеством $Q ∨P$ . Множество $Q ∨P$ – это множество всех чисел, которые не делятся либо на 15 либо на 18. Поэтому чтобы найти наименьшее $A$ достаточно выбрать наименьшее из чисел 15 и 18 – это 15.

Решение программой

for a in range(1, 1500):
    # Переменная-флаг,
    # которой присваивается 1, если хотя бы одно выражение выдаёт ложь
    f = 0
    for x in range(1, 5000):
        # Если выражение ложно(нам нужны только истинные),
        # то приостанавливаем цикл
        if (((x % a == 0) and (x % 15 != 0)) <= ((x % 18 == 0) or (x % 15 == 0))) == False:
        #if (((x % a != 0) or (x % 15 == 0) or (x % 18 == 0))) == False:
            f = 1
            break
    if f == 0:
        print(a)
        break

Получаем ответ: $15.$

Ответ: 15