Здравствуйте! Используя основные эквивалентности, доказать эквивалентность формул:

$$A = (x\bar{y} \ or\ \bar{x}z) \ xor \ ((y \to z) \to \bar{x}y)$$

$$B = (x (\bar{y}\bar{z}) \ xor \ y) \ xor \ z)$$

Нас учили, что нужно привести обе к виду, где используются только конъюнкция и xor (и тогда станет видно, что они эквивалентны), но я что-то не могу понять, как тут формулы преобразовать.

задан 15 Сен '15 21:53

изменен 15 Сен '15 21:54

но я что-то не могу понять, как тут формулы преобразовать. - Наверное так - link2 и link1

(15 Сен '15 22:37) all_exist
10|600 символов нужно символов осталось
1

Да, самый удобный способ именно этот. Я буду вместо xor использовать стандартный знак $%+$%, поскольку это сложение по модулю 2, где $%1+1=0$%. Получатся полиномы, которые удобно сравнивать.

Вообще, все законы булевой алгебры в таком виде становятся очень простыми: помимо правил обычной алгебры добавляется только два, а именно: $%xx=x$% и $%x+x=0$%.

Для начала надо выразить дизъюнкцию. Заметим, что $%\bar x=x+1$%, то есть отрицание -- это прибавление единицы. Воспользуемся законом де Моргана и законом двойного отрицания. Получим, что $%x\lor y=\overline{\overline{x\lor y}}=\overline{\bar x\bar y}=(x+1)(y+1)+1=xy+x+y$%. Это значит, что дизъюнкция -- не что иное как сумма плюс произведение.

Выразим импликацию. Согласно известному правилу, $%(x\to y)$% есть $%\bar{x}\lor y$%, а это в силу предыдущего есть $%\bar{x}y+\bar x+y=(x+1)y+x+1+y=xy+x+1$% (формула напоминает предыдущую).

Теперь всё единым способом выражается: $%x\bar{y}\lor\bar{x}z=x\bar{y}\bar{x}z+x\bar{y}+\bar{x}z=x(y+1)+(x+1)z=xy+xz+x+z$%. В самом начале мы применили т.н. "закон противоречия", согласно которому $%x\bar{x}=0$%, и один член отбрасывается. Этот закон следует из сказанного ранее: $%x(x+1)=xx+x=x+x=0$%.

Далее, $%(y\to z)\to\bar{x}y=(yz+y+1)\to(x+1)y=(yz+y+1)(xy+y)+yz+y+1+1$%, что упрощается до $%xyz+xy+xy+yz+y+y+yz+y=xyz+y$%. В итоге $%A=(xy+xz+x+z)+(xyz+y)=xyz+xy+xz+x+y+z$%.

Теперь преобразуем $%B=x(y+1)(z+1)+y+z=x(yz+y+z+1)+y+z=xyz+xy+xz+x+y+z$%. Получился в точности тот же полином, что и выше.

Полиномы Жегалкина, которые были использованы здесь, удобны ещё и тем, что булева функция ими представляется единственным способом (в отличие от разного рода дизъюнктивных форм и прочего).

ссылка

отвечен 15 Сен '15 22:36

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

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

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

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

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

отмечен:

×1,293
×150

задан
15 Сен '15 21:53

показан
2290 раз

обновлен
15 Сен '15 22:38

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

по почте:

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

по RSS:

Ответы

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

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