Докажите, что любое утверждение про А1, А2, ... Аn можно записать в виде f1 XOR f2 XOR ... XOR fm, где все fi имеют вид Ai1 И Ai2 И ... Аik (количество множителей может в разных fi быть разным.)

задан 24 Май '17 18:06

Это переформулировка утверждения о том, что всякая булева функция может быть представлена в виде полинома Жегалкина. Сложение -- это XOR, а конъюнкция -- это умножение.

Доказательство основано на том, что всё выразимо через конъюнкцию и отрицание, а отрицание x равно x+1. Здесь + есть сложение по модулю 2, то есть XOR.

(24 Май '17 19:05) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×412

задан
24 Май '17 18:06

показан
439 раз

обновлен
24 Май '17 19:05

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

по почте:

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

по RSS:

Ответы

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

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