Question

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

$$
eg 	ext{ДЕЛ}(x, A) 	o (	ext{ДЕЛ}(x, 14) 	o 
eg 	ext{ДЕЛ}(x, 4))$$

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

Accepted Answer

28

Answer

Идея решения: свести логическое выражение к условию на множества, найти, какие числа должны быть покрыты множеством делителей *A*, и выбрать наибольший делитель.

Обозначим:
- $\bar{A}$ — множество натуральных чисел, для которых $
eg 	ext{ДЕЛ}(x, A)$ (не делятся на *A*);
- $P$ — множество натуральных чисел, для которых $	ext{ДЕЛ}(x, 14)$ (делятся на 14);
- $Q$ — множество натуральных чисел, для которых $	ext{ДЕЛ}(x, 4)$ (делятся на 4).

Исходное выражение должно быть истинным для всех *x*:

$$
eg 	ext{ДЕЛ}(x, A) 	o (	ext{ДЕЛ}(x, 14) 	o 
eg 	ext{ДЕЛ}(x, 4))$$

Раскроем импликации. Импликация $B 	o C$ эквивалентна $
eg B \lor C$:

$$	ext{ДЕЛ}(x, A) \lor (
eg 	ext{ДЕЛ}(x, 14) \lor 
eg 	ext{ДЕЛ}(x, 4))$$

$$	ext{ДЕЛ}(x, A) \lor 
eg(	ext{ДЕЛ}(x, 14) \land 	ext{ДЕЛ}(x, 4))$$

Это означает: либо *x* делится на *A*, либо *x* не делится одновременно на 14 и 4.

Для истинности при всех *x* необходимо, чтобы множество чисел, делящихся одновременно на 14 и 4, было полностью покрыто множеством делителей *A*.

Множество $P \cap Q$ — это числа, кратные одновременно 14 и 4, то есть кратные $	ext{НОК}(14, 4)$.

Вычислим НОК:
- $14 = 2 	imes 7$
- $4 = 2^2$
- $	ext{НОК}(14, 4) = 2^2 	imes 7 = 28$

Множество $P \cap Q = \{28, 56, 84, 112, \ldots\}$ — все числа, кратные 28.

Чтобы выражение было истинным для всех *x*, множество делителей *A* должно содержать все числа, кратные 28. Это возможно, если *A* — делитель числа 28.

Делители числа 28: $\{1, 2, 4, 7, 14, 28\}$.

Наибольший делитель — 28.

Проверим с помощью программы:

```python
for a in range(100, 0, -1):
    k = 0
    for x in range(1, 1000):
        if (x % a != 0) <= ((x % 14 == 0) <= (x % 4 != 0)):
            k += 1
    if k == 999:
        print(a)
        break
```

Программа перебирает значения *A* от 100 вниз и проверяет, для скольких значений *x* из диапазона [1, 999] выполняется исходное логическое выражение. Когда все 999 значений удовлетворяют условию, выводится *A*.

![Рисунок](https://ege.sdamgia.ru/formula/svg/10/10c4fcbf531d94c4170124e070dbe1a6.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/12/12a7cb0919bf5d9b63f01d42ad81ebf2.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/32/3259c3032187705cc75259ab34f88211.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/09/09777e5f2128782805ab6ee504679fd9.svg)

![Рисунок](https://ege.sdamgia.ru/formula/svg/9d/9ddedac295b63e35f3d42d4c9f067325.svg)

Задание №15Математическая логикаЕГЭ по информатике