DVBogdanov.ru / Тренировочный вариант по информатике, задание 18

Задание №1701/18

Задание

Обозначим через \(\text{ДЕЛ}\left(n,m\right) \) утверждение «натуральное число \(n\) делится без остатка на натуральное число \(m\)». Для какого наименьшего натурального числа \(A\) формула \[\lnot\text{ДЕЛ}\left(x,5940\right)\wedge\text{ДЕЛ}\left(x,A\right)\wedge\text{ДЕЛ}\left(x,6300\right)\rightarrow\text{ДЕЛ}\left(x,5940\right)\vee\lnot\text{ДЕЛ}\left(x,A\right) \] тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной \(x\))?

Решение

Обозначим через \( D_{m}\left(x\right) \) условие, что \(x\) является делителем \(m\) и упростим исходное выражение, используя законы логики: \[ \lnot D_{5940} \wedge D_A \wedge D_{6300} \rightarrow D_{5940} \vee \lnot D_A = D_{5940} \vee \lnot D_A \vee \lnot D_{6300} \vee D_{5940} \vee \lnot D_A = \] \[ = D_{5940} \vee \lnot D_A \vee \lnot D_{6300} = \left( D_A \wedge D_{6300} \right) \rightarrow D_{5940}. \]

Каноническое разложение чисел 6300 и 5940 на простые сомножители имеет вид: \[ 6300 = 2^2 \cdot 3^2 \cdot 5^2 \cdot 7^1,\quad 5940 = 2^2 \cdot 3^3 \cdot 5^1 \cdot 11^1. \]

Очевидно, что необходимо сделать истинной посылку \( D_A \wedge D_{6300} \) лишь в случае истинности заключения \( D_{5940} \), иначе импликация окажется ложной. Истинность \(D_{6300}\) гарантирует, что \(x\) делится на числа 4, 9, 25, 7 и их делители. Но \(D_{5940}\) будет истинным, если \(x\) делится на числа 4, 27, 5 и 11. Делимость на 4 и 5 обеспечивается предикатом \( D_{6300} \), поэтому необходимо и достаточно, чтобы \( D_A \) обеспечивал делимость на 27 и 11. Таким образом, наименьшим значением \(A\) является число \(27 \cdot 11 = 297.\)

Подробнее...

Замечание

Следует отметить, что значение \(A=33\) не является правильным ответом. Действительно, делимость \(x\) на 3 и на 9 вовсе не гарантирует его делимость на 27. Например, \(\text{НОК}\left(33, 6300\right)=69300\) по определению делится и на 33, и на 6300, но при этом не делится на 5940. Соответственно, при \(x=69300\) выражение \(\left( D_{33} \wedge D_{6300} \right) \rightarrow D_{5940} \) оказывается ложным.

Подробнее...

Ответ

297

Подробнее...
Добавить комментарий
Комментарии (0)
#Задачи на логику #Логические уравнения #Подготовка к ЕГЭ по информатике #Уравнения с делителями