Замыкание. Основные замкнутые классы
Полином Жегалкина Конъюнкция вида называется монотонной конъюнкцией (отсутствует отрицание переменных). Полиномом Жегалкина от n переменных называется сумма по модулю 2 различных монотонных конъюнкций, составленных из этих переменных. , – длина полинома. Жегалкин рассматривал только операции конъюнкции и сложения по модулю 2. В алгебре с этими операциями справедливо: Теорема: для любой булевой функции существует полином Жегалкина, представляющий данную функцию и причём только один. Доказательство: существование следует из того, что для любой булевой функции можно построить СДНФ, далее дизъюнкцию и отрицание можно заменить на конъюнкцию и сложение по модулю 2. Докажем единственность. Рассмотрим множество булевых функций от переменных - . Число булевых функций равно . Покажем, что число полиномов Жегалкина от переменных тоже и тогда, так как для любой функции существует полином Жегалкина, для каждой функции такой полином будет единственный. Общий вид полинома Жегалкина от трёх переменных: перестановок Полином Жегалкина от переменных мы представим как т.к. число слагаемых равно числу подмножество множества из элементов, то оно будет равно . Каждый поэтому число полиномов Жегалкина совпадает с числом . Замыкание. Основные замкнутые классы. Рассмотрим множество булевых функций Замыканием класса называется множество функций, представляющих собой суперпозиции различных функций класса (само входит). Обозначение: Свойства: 1. 2. 3. 4. 5. Класс функций называется замкнутым, если он совпадает со своим замыканием. - замкнутый. Основные замкнутые классы: 1. Класс (булевы функции, сохраняющие константу 0) 2. Класс (булевы функции, сохраняющие константу 1) 3. Класс S (самодвойственные функции). 4. Класс (монотонные функции) 5. Класс (линейные функции) Лемма: (о нелинейной функции) Пусть тогда из этой функции путем подстановки вместо её переменных констант 0,1 и функций или , а так же, если необходимо, взятия отрицания над всей функцией, можно получить нелинейную функцию . В силу того, что полином Жегалкина для – единственный
Популярное: Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (4170)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |