Форум » Логические выражения » решение 18-ого задания » Ответить

решение 18-ого задания

Eugeny1984: Добрый день! Помогите, пожалуйста решить это задание. https://yadi.sk/i/GKyBvtDfIhLgJw. У меня получается так x<=7 - это беру за истину, чтобы не получилось выражение слева ложью. И тогда подставляю в самое левое и получаю A>=7*7, отсюда А=50. В ответах стоит 9. Можете сказать, У меня ошибка или в решении?

Ответов - 8

cabanov.alexey: (x2⩽A) → (x⩽7); ¬(x2⩽A) ∨ (x⩽7); (x2>A) ∨ (x⩽7); (A<x2) ∨ (x⩽7); Если x>7 (x=8,9,10,11..), A должно быть меньше любого x2. Это требование выполняется, если A<64.

polyakovss: Здравствуйте, Eugeny1984! Если ((x*x <= A) → (x<=7)) ∧ ((y < 4) → (y*y <= A)) = 1, то одновременно ((x*x <= A) → (x<=7)) = 1 и ((y < 4) → (y*y <= A)) = 1. Рассмотрим ((x*x <= A) → (x<=7)) = 1. ((x*x <= A) → (x<=7)) = ¬(x*x <= A) ∨ (x<=7) = (x*x > A) ∨ (x<=7) = 1 (x*x > A) ∨ (x<=7) = 1. Если (x<=7) = 1, то (x*x > A) ∨ (x<=7) = 1 при любом A. Но так будет не всегда. Поэтому рассмотрим случай (x<=7) = 0, то есть (x > 7) = 1. В этом случае должно быть (x*x > A) = 1 для любых целых неотрицательных x на интервале (x > 7). Как так может быть? Может быть только в случае, если число A < минимума (x*x) на этом интервале (нарисуйте картинку). Таких чисел А будет бесчисленное множество, но Amax = min(x*x) - 1. Другие числа A будут меньше Amax. Поэтому они, тем более, будут удовлетворять (x*x > A). min(x*x) = min(x)*min(x) (x > 7) → min(x) = 8 → min(x*x) = 64 → Amax = min(x*x) - 1 = 63. Мы нашли для какого НАИБОЛЬШЕГО целого числа А исходная формула тождественно истинна. Кабанов Алексей Михайлович все написал верно, но так находят в этой задаче наибольшее A, а по условию нужно найти НАИМЕНЬШЕЕ A. Найдем наименьшее A. Рассмотрим ((y < 4) → (y*y <= A)) = 1. ((y < 4) → (y*y <= A)) = 1 → ¬(y < 4) ∨ (y*y <= A) = (y >= 4) ∨ (y*y <= A) = 1 (y >= 4) ∨ (y*y <= A) = 1. Если (y >= 4) = 1, то (y >= 4) ∨ (y*y <= A) = 1 при любом A. Но так будет не всегда. Поэтому рассмотрим случай (y >= 4) = 0, то есть (y < 4) = 1. В этом случае должно быть (y*y <= A) = 1 для любых целых неотрицательных y на интервале ((y < 4) ∧ (y >= 0)) . Как так может быть? Может быть только в случае, если число A >= максимума (y*y) на этом интервале (нарисуйте картинку). Таких чисел А будет бесчисленное множество, но Amin = max(y*y), так как (y*y <= A). Другие числа A будут больше Amin. Поэтому они, тем более, будут удовлетворять (y*y <= A). max(y*y) = max(y)*max(y) ((y < 4) ∧ (y >= 0)) → max(y) = 3 → max(y*y) = 9 → Amin = max(y*y) = 9. Мы нашли для какого НАИМЕНЬШЕГО целого числа А исходная формула тождественно истинна. Формула ((x*x <= A) → (x<=7)) ∧ ((y < 4) → (y*y <= A)) = 1 при любых целых неотрицательных x и y, если А принадлежит интервалу [9, 63]. Amin = 9; Amax = 63. Всего 55 целых чисел А, при которых формула ((x*x <= A) → (x<=7)) ∧ ((y < 4) → (y*y <= A)) = 1 при любых целых неотрицательных x и y. Ответ: 9.

Eugeny1984: polyakovss Спасибо огромное!


Eugeny1984: polyakovss Все понятно, кроме одного. Почему Amax = min(x*x) - 1 вычисляется по этой формуле. Откуда взялось минус 1? Почему именно минус 1, а не два или другое число? Подскажите, пожалуйста?

polyakovss: Здравствуйте, Eugeny1984! Все очень просто. Вернемся к решению. В этом случае должно быть (x*x > A) = 1 для любых целых неотрицательных x на интервале (x > 7). Как так может быть? Может быть только в случае, если число A < минимума (x*x) на этом интервале (нарисуйте картинку). Вам это понятно? Если да, то далее так: (x > 7) → min(x) = 8 → min(x*x) = 64. Значит, из (x*x > A) = 1 → (64 > A) → (A < 64) → Amax = 63 (62, 61, 60, ... тоже подходят для (A < 64), но максимальное подходящее равно 63). min(x*x) = 64, а Amax = 63. Вот и получается, что Amax = min(x*x) - 1 (все вычисления в целых числах), то есть (-1) следует из (x*x > A) при строгом неравенстве и вычислениях в целых числах. Замечание: если бы было (x*x > = A) = 1, то Amax = min(x*x).

Eugeny1984: polyakovss Cпасибо, действительно здесь просто

ORN: Я не могу понять почему выбираются варианты истинности импликации 0 - 0 или 1 -1. Ведь импликация дает "1" в варианте 0 - 1 Что значит фраза ""Выбором A мы можем влиять на левую часть, но не на правую".

polyakovss: Здравствуйте, ORN! Из вашего сообщения легко понять, что речь идет о разборе задания Р-26 (демо-2018) из ege18.doc: Для какого наибольшего целого числа А формула ( (x <= 9) → (x*x <= A) ) ∧ ( (y*y <= A) → (y <= 9) ) тождественно истинна (то есть принимает значение 1 при любых целых неотрицательных значениях переменных x и y)? Вы пишете: Что значит фраза "Выбором A мы можем влиять на левую часть, но не на правую"? Эта фраза относится к логическому выражению (y*y <= A) → (y <= 9). Она означает, что при изменении значения А можно сделать значение (y*y <= A) как истинным, так и ложным, а вот повлиять на логическое значение (y <= 9) изменение значения А не может, так как (y <= 9) от А не зависит. Вы пишете: Я не могу понять почему выбираются варианты истинности импликации 0 - 0 или 1 -1. Ведь импликация дает "1" в варианте 0 - 1. Рассмотрим вариант 0 - 1. Перепишем (x <= 9) → (x*x <= A) : not(x <= 9) + (x*x <= A). Если (x <= 9) = 0, то not(x <= 9) = 1 и (not(x <= 9) + (x*x <= A)) = 1 при любом значении (x*x <= A). То есть в этом случае от А ничего не зависит. А может быть любым. Поэтому этот случай и не рассматривается. Аналогично, (y*y <= A) → (y <= 9): not(y*y <= A) + (y <= 9). При варианте 0 - 1: (y <= 9) = 1, not(y*y <= A) + (y <= 9) = 1 при любом значении А. Советую все-таки внимательно ознакомиться с Сообщением 236, 237 (polyakovss) на этой странице. Надеюсь, что это поможет Вам разобраться с решением такого типа задач.



полная версия страницы