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