Задание P-21 из ege2018kp

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

Задание P-21 из ege2018kp

Wally: Здравствуйте, у меня возникли некоторые вопросы, касающиеся задания 18. 1)Третий пункт разбора этого задания: "Чтобы формула была тождественно истинной для любых X необходимо, чтобы not P + not Q=0, а также А=1". Почему not P + not Q должно быть именно 0? Ведь и 1+1=1. 2)Восьмой пункт разбора задания гласит: "Так как биты {3,1} числа Х могут быть ненулевыми, в этих разрядах в А должны стоять нули...". Вопрос: почему? "...а вот биты {4,2,0} в Х - нулевые, поэтому в числе А эти биты могут быть равны 1". Такой же вопрос: почему?

Ответов - 14

MEA: Про битовые операции рекомендую посмотреть http://kpolyakov.spb.ru/download/mea18bit.pdf Метод проще, чем метод приведения к импликации.

dbaxps: Еще лучше полный текст Вашей Р-21

polyakovss: Здравствуйте, dbaxps! Это просто ege18.doc ссылка: P-21 Решение (2 способ, Н.Г. Неуймина, г. Екатеринбург).

dbaxps: Спасибо

polyakovss: Здравствуйте, Wally! Всё очень просто. 1) Исходное выражение в пункте 2 переписано так: A + (not(P) + not(Q)) = 1. Если (not(P) + not(Q)) = 1, то от A ничего не зависит. А может быть любым. Значит, и натуральное число "а" в А = (x & a = 0) может быть любым натуральным числом. Но (not(P) + not(Q)) = 1 не при при любых натуральных значенях переменной x, то есть может быть (not(P) + not(Q)) = 0. Вот тогда, чтобы A + (not(P) + not(Q)) = 1 при любом натуральном значении переменной x, А должно быть равно 1. Вот и получили, что должно быть А=1 при (not(P) + not(Q)) = 0. 2) Далее выясняется какими свойствами должен обладать x для того, чтобы было (not(P) + not(Q)) = 0. Оказывается, что для того, чтобы в любом случае (not(P) + not(Q)) = 0, четвертый, второй и нулевой биты x должны быть равны 0 (пункты 4, 5, 6, 7). Теперь определим а. A = (x & a = 0) = 1. То есть должно быть (x & a = 0). Поскольку четвертый, второй и нулевой биты x равны 0, четвертый, второй и нулевой биты а могут быть любыми (x & a = 0 для этих битов). Поэтому, так как нужно найти наибольшее подходящее а, четвертый, второй и нулевой биты а могут быть равны 1. Так как значение других битов в х при (not(P) + not(Q)) = 0 мы не знаем, то для того, чтобы A = (x & a = 0) = 1, нужно сделать для этих битов в x (x & a = 0). Значит, в а все биты, кроме четвертого, второго и нулевого, должны быть равны 0.

Wally: polyakovss, спасибо за ответ.

dbaxps: E(A) => (!E(20)=>E(5)) ~ 1 !E(A) + E(20) + E(5) ~ 1 E(20 + E(5) = E(16) + E(4) + E(4) + E(1) = E(21) E(A) => E(21) ~ `1 Теорема 1 ************** Для выполнения ∀ x∈N: E(k,x) => E(m,x) = True необходимо и достаточно, чтобы множество единичных битов "k" полностью входило во множество единичных битов "m" А(мах) = 21 I might be advocating MEA for a while, but I am not expecting it to help much

Wally: Что такое E(A)? Что такое ~1? Что такое E(A)=>E(21)~1? => - это импликация? Почему E(20)+E(5)=E(21)? Что такое !Е(20) ?

dbaxps: Смотри http://kpolyakov.spb.ru/download/mea18bit.pdf Этот документ отвечает на все вопросы. МЕА давала ту же ссылку ранее. Внимательнее читайте свою тему ! - означает отрицание. => означает импликацию Детали техники например :- Первые 2 поста на стене https://vk.com/bderzhavets Они использует технику МЕА в ракурсе который мне удобен из-за привычки работать с Bitwise2. Смотри также :- http://egekp.unoforum.pro/?1-4-0-00000278-000-0-0-1550989755 Мой код и код МЕА решают одну и ту же задачу Здесь приведены совсем простые решения без полного обоснования корректности https://informatics-ege.blogspot.com/2018/12/2017-18.html если нужны обоснования , то смотрите 2 топовых поста со стены.

polyakovss: Здравствуйте, dbaxps! Участник Wally задал два вполне конкретных вопроса. В своем сообщении 78 Вы не ответили ни на один из них. Я понимаю, что Вы хотите представить хорошую методику. Но таким сообщением Вы, скорее всего, от нее отпугнёте.

MEA: polyakovss пишет: В своем сообщении 78 Вы не ответили ни на один из них. Приведено полное решение задачи. Получен ответ. В решении использованы базисные предикаты. Е(а) означает число х имеет в двоичной записи единицы хотя бы одну 1 как в числе А Достаточно сравнить длину рассуждений в двух решениях.

Wally: Длина решения может и короче, но я вообще ничего не понял. Е(20) какие-то, знаки =>, ~, ! откуда-то взялись.

polyakovss: Здравствуйте, MEA! Никто не обсуждал здесь достоинства или недостатки какого-либо метода решения. Тем более, что мной в сообщении 118 не отрицались достоинства Вашего метода. Вы пишете: Приведено полное решение задачи. Получен ответ. А разве кто-нибудь об этом спрашивал? А вот на два заданных вопроса в сообщении dbaxps ответа, действительно, не последовало. Когда человек задает вопрос, он хочет получить ответ именно на заданный вопрос, а уже потом может познакомиться с полезной информацией. Самое интересное, что так в итоге и получилось.

MEA: Не согласна с Вами. По сути вопрос как решается был. Решение приведено. Рекомендовано короткое решение. Источник указан. Всё корректно. Впрочем, за Вами остаётся право не согласится со мной. Это нюансы не имеющие отношение к задаче и вопросу. И эта запись, как и запись Ваша отступили от предмета обсуждения и диалог в рамках этой темы форума не может быть продолжен.

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