Егэ информатика номер 15

Обозна ДЕЛ(n, m) как D(n, m). Исходная формула:
F(x, A) = ¬D(x, A) / ( (D(x, 60) / D(x, 40)) → (D(x, 30) /\ D(x, 60)) / (D(x, 30) /\ D(x, 40)) )


Правая часть импликации: (D(x, 30) /\ D(x, 60)) / (D(x, 30) /\ D(x, 40))
По дистрибутивному закону: D(x, 30) /\ (D(x, 60) / D(x, 40))

Обозначим P = D(x, 60) / D(x, 40). Импликация имеет вид P → (D(x, 30) /\ P).
Используя A → B ≡ ¬A / B, получаем:
¬P / (D(x, 30) /\ P)
По дистрибутивному закону: (¬P / D(x, 30)) /\ (¬P / P)
Так как ¬P / P истинно, выражение равно ¬P / D(x, 30).
Подставляя P обратно: ¬(D(x, 60) / D(x, 40)) / D(x, 30)
По закону Де Моргана: (¬D(x, 60) /\ ¬D(x, 40)) / D(x, 30)


F(x, A) = ¬D(x, A) / ( (¬D(x, 60) /\ ¬D(x, 40)) / D(x, 30) )
Обозначим Q(x) = (¬D(x, 60) /\ ¬D(x, 40)) / D(x, 30).
Формула: F(x, A) = ¬D(x, A) / Q(x), что эквивалентно ии D(x, A) → Q(x).

2. Условие тождественной истинности:

Формула D(x, A) → Q(x) должна быть истинна для любого натурального x.
Это означает, что если D(x, A) истинно (x делится на A), то Q(x) также должно быть истинно.
Или, что то же самое, если Q(x) ложно, то D(x, A) должно быть ложно (x не делится на A).

Найдем, когда Q(x) ложно:
Q(x) = (¬D(x, 60) /\ ¬D(x, 40)) / D(x, 30) ложно, если:
(¬D(x, 60) /\ ¬D(x, 40)) ложно И D(x, 30) ложно.
Первое условие (¬D(x, 60) /\ ¬D(x, 40)) ложно, означает, что ¬(¬D(x, 60) /\ ¬D(x, 40)) истинно, то есть D(x, 60) / D(x, 40) истинно.
Итак, Q(x) ложно, когда (D(x, 60) / D(x, 40)) И ¬D(x, 30).

60 = 2² * 3 * 5

40 = 2³ * 5

30 = 2 * 3 * 5
Если D(x, 60) истинно, то x делится на 60, а значит, и на 30. Тогда ¬D(x, 30) ложно.
Следовательно, D(x, 60) / D(x, 40) И ¬D(x, 30) сводится к D(x, 40) И ¬D(x, 30).
Таким образом, Q(x) ложно тогда и только тогда, когда x делится на 40, но не делится на 30. Это означает, что x делится на 40 (т.е. на 2³ и 5), но не делится на 3.

3. Нахождение наименьшего A:

Условие D(x, A) → Q(x) должно быть истинно для всех x.
Если Q(x) ложно (т.е. x делится на 40 и не делится на 3), то D(x, A) должно быть ложно (x не должен делиться на A).
Рассмотрим множество K = {x ∈ ℕ | D(x, 40) /\ ¬D(x, 3)}.
Для любого x ∈ K должно выполняться ¬D(x, A).
Это означает, что ни одно число из K не должно быть кратным A.
Иначе говоря, если число y кратно A (D(y, A) истинно), то y не должно принадлежать K.
Если D(y, A) истинно, то ¬(D(y, 40) /\ ¬D(y, 3)) должно быть истинно.
Если D(y, A) истинно, то ¬D(y, 40) / D(y, 3) должно быть истинно.

Предположим, A не делится на 3.
Возьмем y = НОК(A, 40). Тогда y делится на A (D(y, A) истинно) и y делится на 40 (D(y, 40) истинно).
Подставляя в условие: True → (¬True / D(y, 3))
True → (False / D(y, 3))
True → D(y, 3)
Это означает, что D(y, 3) должно быть истинно, то есть y = НОК(A, 40) должно делиться на 3.
Однако, если A не делится на 3, а 40 = 2³ * 5 тоже не делится на 3, то их наименьшее общее кратное НОК(A, 40) также не будет делиться на 3.
Получили противоречие. Следовательно, наше предположение неверно, и A должно делиться на 3.

Наименьшее натуральное число A, которое делится на 3, это A = 3.

Проверка A = 3:
Формула D(x, 3) → Q(x) должна быть истинна.
Если x не делится на 3, то D(x, 3) ложно, импликация истинна.
Если x делится на 3, то D(x, 3) истинно. Нужно, чтобы Q(x) было истинно.
Q(x) = (¬D(x, 60) /\ ¬D(x, 40)) / D(x, 30).
Если x делится на 3, может ли Q(x) быть ложным? Q(x) ложно, если D(x, 40) и ¬D(x, 30).
Если x делится на 3 (D(x, 3) истинно) и при этом Q(x) ложно, то D(x, 40) истинно и ¬D(x, 30) истинно. Но если x делится на 3 и на 40, то x делится на НОК(3, 40) = НОК(3, 2³5) = 2³3*5 = 120. Если x делится на 120, то x делится и на 30. Это противоречит ¬D(x, 30). Значит, если x делится на 3, Q(x) не может быть ложным, то есть Q(x) истинно.
Таким образом, при A=3 импликация D(x, 3) → Q(x) всегда истинна.

Ответ:
Наименьшее натуральное число A равно 3.