Есть неограниченное количество устройств-конъюнкций и дизъюнкций и ровно 2 инверсии. Возможно ли на основе этих элементов реализовать устройство с тремя входами (x,y,z) и тремя выходами (неX, неY, неZ)?

задан 17 Июн '15 1:13

изменен 17 Июн '15 11:32

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

10|600 символов нужно символов осталось
2

Возможно. Это хорошая задача.

Удобно описывать этот способ не на языке устройств, а, скажем, на языке программ, где можно использовать and и or любое число раз, а not только дважды. По описанию этого способа легко сконструировать требуемое устройство.

Введём такие обозначения: будем использовать символ $%h$% с одним или несколькими индексами, имея в виду функцию, которая принимает значение 1 тогда и только тогда, когда число единиц среди $%x$%, $%y$%, $%z$% равно одному из индексов.

Например, $%h_3=x\land y\land z$%; $%h_{123}=x\lor y\lor z$%.

Также нетрудно выразить функцию голосования, принимающее то значение, которое среди $%x$%, $%y$%, $%z$% встречается в большинстве. Здесь подходит любое из двух равенств: $%h_{23}=(x\land y)\lor(x\land z)\lor(y\land z)$% или $%h_{23}=(x\lor y)\land(x\lor z)\land(y\lor z)$%.

Теперь используем первый оператор not, строя функцию $%h_{01}=\neg h_{23}$%. Беря конъюнкцию, имеем $%h_1=h_{01}\land h_{123}$%. Далее берём дизъюнкцию, и получаем функцию $%h_{13}=h_1\lor h_3$%.

Теперь используем оператор not второй раз: $%h_{02}=\neg h_{13}$%. После этого в нашем распоряжении оказывается функция $%h_2=h_{02}\land h_{23}$%, а также $%h_0=h_{01}\land h_{02}$%.

Далее отрицания всех переменных выражаются без использования not. Сделаем это для переменной $%x$%, так как для двух остальных формулы будут аналогичными. Если $%h_3=1$%, то $%\neg{x}=0$%.

Пусть $%h_2=1$%. В этом случае $%\neg{x}=y\land z$%, что легко проверяется непосредственно. Действительно, если $%y=z=1$%, то $%x=0$%, а в противном случае $%x=1$%, и среди $%y$%, $%z$% есть ноль.

Пусть $%h_1=1$%. Здесь $%\neg{x}=y\lor z$%, что проверяется аналогично.

Наконец, если $%h_0=1$%, то $%x=y=z=0$%, и $%\neg{x}=1$%.

Таким образом, отрицание $%x$% выражается в виде дизъюнкции: $%\neg{x}=h_0\lor(h_1\land(y\lor z))\lor(h_2\land y\land z)$%. Ввиду того, что из случаев $%h_0=1$%, $%h_1=1$%, $%h_2=1$%, $%h_3=1$% имеет место ровно один, формула всегда даёт верный ответ. При $%h_3=1$% происходит умножение на ноль, и этот дизъюнктивный член можно не включать.

ссылка

отвечен 17 Июн '15 1:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×129
×10

задан
17 Июн '15 1:13

показан
534 раза

обновлен
17 Июн '15 11:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru