|
Докажите, что любое утверждение про А1, А2, ... Аn можно записать в виде f1 XOR f2 XOR ... XOR fm, где все fi имеют вид Ai1 И Ai2 И ... Аik (количество множителей может в разных fi быть разным.) задан 24 Май '17 18:06 
АндрейК |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
24 Май '17 18:06
показан
698 раз
обновлен
24 Май '17 19:05
Связанные исследования
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Это переформулировка утверждения о том, что всякая булева функция может быть представлена в виде полинома Жегалкина. Сложение -- это XOR, а конъюнкция -- это умножение.
Доказательство основано на том, что всё выразимо через конъюнкцию и отрицание, а отрицание x равно x+1. Здесь + есть сложение по модулю 2, то есть XOR.