Попалась задача по дискретной математике. Подскажите, как это доказать.

Если можно, то подробное доказательство.

Заранее спасибо!

задан 24 Фев '13 17:04

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

Я бы при доказательстве воспользовался принципом двойственности. Представим себе, что мы переименовали символы $%0$% и $%1$%. Тогда класс $%T_1$% перейдёт в $%T_0$%, дизъюнкция -- в конъюнкцию, а эквиваленция -- в сумму по модулю $%2$%. Поэтому достаточно доказать, что $%\{\&,\oplus\}$% есть базис класса $%T_0$%.

Последнее становится очевидным, если заметить, что класс $%T_0$% состоит в точности из тех функций, которые в своём представлении полиномом Жегалкина имеют равный нулю свободный член. То есть они выражаются через сложение и умножение. Остаётся добавить, что одним сложением не обойтись (все функции, через него выразимые, будет линейны, и конъюнкцию будет не выразить). Также не обойтись одним умножением (то есть конъюнкцией): это монотонная функция, и через неё не выразить сложение по модулю $%2$%, так как это не монотонная операция. Значит, построен базис данного класса.

ссылка

отвечен 24 Фев '13 17:30

Спасибо Вам!) Все понятно)

(24 Фев '13 18:55) Archi
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,306
×797
×150

задан
24 Фев '13 17:04

показан
2011 раз

обновлен
24 Фев '13 18:55

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

по почте:

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

по RSS:

Ответы

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

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