Докажите, что функцию XOR3 можно вычислить, используя лишь одно отрицание (и много конъ- юнкций и дизъюнкций).

задан 29 Янв '15 2:02

изменен 29 Янв '15 16:00

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


9917

Понятно, что являет собой функция xor от двух переменных (исключающее "или"). Но что имеется в виду под XOR3?

(29 Янв '15 11:54) falcao

$%x_1 ⊕ x_2 ⊕ x_3$% т.е. та же функция, но уже от трех переменных.

(29 Янв '15 12:19) Leva319

Теперь задача понятна! Сейчас попробую изложить решение.

(29 Янв '15 13:16) falcao
10|600 символов нужно символов осталось
0

Пусть имеется три булевых переменных. Из них от 0 до 3 могут принимать значение 1. Обозначим через $%h_k$% высказывание, что ровно $%k$% из трёх переменных равны 1. Нас интересует случай, когда $%k$% нечётно: при этом $%{\rm xor}_3$% будет равно 1, то есть речь идёт о высказывании $%h_1\lor h_3$%.

Легко записать $%h_3$% без использования отрицания: это конъюнкция $%x_1\land x_2\land x_3$%. Также легко записать $%h_1\lor h_2\lor h_3$%: это дизъюнкция $%x_1\lor x_2\lor x_3$%.

Рассмотрим функцию голосования: $%x_1x_2\lor x_1x_3\lor x_2x_3$% (для удобства я здесь конъюнкцию обозначил в виде произведения). Она принимает значение 1 тогда и только тогда, когда большинство значений переменных равно 1. Это значит, что мы записали $%h_2\lor h_3$%. Используя отрицание (один раз), мы получим высказывание $%h_0\lor h_1$%. Беря теперь его конъюнкцию с $%h_1\lor h_2\lor h_3$%, мы выражаем $%h_1$%. Осталось взять дизъюнкцию полученного $%h_1$% и уже имеющегося $%h_3$%.

ссылка

отвечен 29 Янв '15 13:30

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

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

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

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

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

отмечен:

×76

задан
29 Янв '15 2:02

показан
553 раза

обновлен
29 Янв '15 13:30

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

по почте:

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

по RSS:

Ответы

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

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