Форум » Логические выражения » Задание 15. Не ДЕЛ. » Ответить
Задание 15. Не ДЕЛ.
Amo: Здравствуйте. В учебнике для подготовки в ЕГЭ - 2021 нашла такую задачу. Обозначим через ВЗПР(x, y) утверждение "натуральные числа х и y не имеют общих натуральных делителей, кроме 1". При каком наименьшем натуральном значении A формула (ВЗПР(х, 360) -> ВЗПР(х, А)) /\ (ВЗПР(х, А) -> ВЗПР(х, 240)) истинна при любом натуральном х. Задачу я эту решила, написав программу на Python, ответ получился 30, он сошёлся с ответами в учебнике. Решила попробовать решить эту же задачу руками.... вот тут и начались проблемы. Я вообще не могу понять, как там получается 30! Объясните, пожалуйста. Вот ход моих мыслей при решении этой задачи вручную. 1. Избавляемся от импликации. (!ВЗПР(х, 360) \/ ВЗПР(х, А)) /\ (!ВЗПР(х, А) \/ ВЗПР(х, 240)) 2. !ВЗПР(х, 360) \/ ВЗПР(х, А), чтобы это выражение было истинным примем ВЗПР(х, А) = 1, !ВЗПР(х, 360) = False => ВЗПР(х, 360) = True. Ищем множество значений, на которых функция ВЗПР(х, 360) принимает значение True: Натуральные делители числа 360: 2, 3, 5, значит все числа, которые на эти числа делятся в множество ВЗПР(х, 360) не входят. Нужное нам множество имеет вид: {7, 11, 13, 17, 19, 23, 29, 31, 33, ...} 3. !ВЗПР(х, А) \/ ВЗПР(х, 240), чтобы это выражение было истинным примем !ВЗПР(х, А) = 1, ВЗПР(х, 240) = False => для A ВЗПР(х, 240) = True. Ищем множество значений, на которых функция ВЗПР(х, 240) принимает значение True: Натуральные делители числа 240: 2, 3, 5, значит все числа, которые на эти числа делятся в множество ВЗПР(х, 240) не входят. Нужное нам множество имеет вид: {7, 11, 13, 17, 19, 23, 29, 31, 33, ...} 4. Как я понимаю теперь нам нужно искать пересечение этих множеств, потому что скобки связаны между собой операцией /\. Но здесь и близко нет числа 30.....
Ответов - 6
Поляков: Интересная задача. Здесь не нужно избавляться от импликаций. Рассмотрим первую: (ВЗПР(х, 360) -> ВЗПР(х, А)). Разложим 360 на простые сомножители: 360 = 23*32*5. Если x и 360 - взаимно простые (англ. coprime), то x не делится ни на 2, ни на 3, ни на 5. Поэтому импликация верна тогда и только тогда, когда A раскладывается на произведение 2, 3 и 5. С другой стороны, нужно выполнить второе условие: (ВЗПР(х, А) -> ВЗПР(х, 240). Здесь 240 = 24*3*5. Для того чтобы импликация была истинной, необходимо, чтобы A обязательно делилось на 2, 3 и 5. Наименьшее число, удовлетворяющее двум условиям - A = 2*3*5.
Amo: Огромное спасибо, я бы никогда до такого решения не додумалась!
MEA: Обозначим ВЗПР(х, A) как Ba Запишем в новых обозначениях: (В360 -> ВА)*(ВА -> B240)= (!В360 + ВА)*(!ВА + B240)= !В360*!ВА+!В360*B240+ВА* B240 Предикат !B360 = D2+D3+D5, где предикат D2 обозначение функции ДЕЛ(x, 2), т.е. x - делится на 2 !В240 = D2+D3+D5 !В360*B240 = 0 Перепишем выражение с использованием предикатов делимости: (D2+D3+D5)*!ВА+ВА* !(D2+D3+D5) ВА XOR (D2+D3+D5) ВА = !(D2+D3+D5) !(D2+D3+D5) = В30 Ответ: 30 Но не всем нравится алгебраическое решение логических выражений.
Муффазалов: Мы в шоке!
Kolobok256: Помогите, пожалуйста, решить эту задачу на Python
OlgaChe1: Kolobok256 пишет: Помогите, пожалуйста, решить эту задачу на Python [pre2] def vzp(x,y): a=[] b=[] for i in range(2,int(x**0.5)+1): if x%i==0: a.append(i) if x%(x//i)==0 and (x//i)!=i: a.append(x//i) for i in range(2,int(y**0.5)+1): if y%i==0: b.append(i) if y%(y//i)==0 and (y//i)!=i: b.append(y//i) for i in range(len(a)): if a[ i] in b: return False return True for A in range(1,100000): k=True for x in range(1,1000): if ((((vzp(x,360))) <= ((vzp(x,A)))) and (((vzp(x,A))) <= ((vzp(x,240)))))==False: k=False break if k: print(A) break [/pre2]
полная версия страницы