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