Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Дисциплины:
2017-09-26 | 525 |
5.00
из
|
Заказать работу |
|
|
Определение. Система булевых функций {f1, f2, …,fn} называется полной, если любая переключательная функция может быть представлена суперпозицией функций данной системы.
Теорема Поста-Яблонского. Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала:
- хотя бы одну функцию, не сохраняющую константу нуль;
- хотя бы одну функцию, не сохраняющую константу единица;
- хотя бы одну функцию, не являющуюся линейной;
- хотя бы одну функцию, не являющуюся монотонной;
- хотя бы одну функцию, не являющуюся самодвойственной.
Это критерий полноты системы.
Система функций {f1, f2, …,fn}, являющаяся полной, называется базисом.
Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций fi, образующих тот базис, превращает систему функций {f1, f2, …,fn } в неполную.
Будем рассматривать функции, зависящие от n аргументов. Число различных функций равно .
Тривиальная полная система состоит из всех функций.
Функции инверсии, дизъюнкции и конъюнкции образуют полную систему. Это вытекает из основной теоремы, утверждающей, что любая булева функция может быть записана в виде дизъюнкции минтермов (или конъюнкции макстермов).
Базис { /\,\/,¯ } не минимален, так как может быть уменьшен за счет выбрасывания из него /\ или \/. Это следует из формул де Моргана:
Базисы {/\,¯} и {\/,¯} являются минимальными.
Другие базисы:
а) { ,/\,1}- функционально полная система (это следует из теоремы Жегалкина);
б) функция импликации и константа 1: {x→y,1};
в) функция импликации и инверсии: {x→y,¯}.
Пример. Доказать, что функция Шеффера образует полную систему
f14(xy)=x | y= .
Доказательство. Выразим ¯ и /\ через функцию Шеффера:
|
Так как {¯,/\} – полная система, утверждение доказано.
Пример. Выразим функцию, используя только функцию Шеффера:
.
Пример. Доказать, что А↓В образует функционально полную систему
Так как инверсия и дизъюнкция выражаются только через функцию «стрелка Пирса», а {¯,\/} – функционально полная система, то А↓В является функционально полной системой.
Пример. Выразить функцию, используя только функцию «стрелка Пирса»:
Выбор функционально полной системы по таблице.
Пример. {\/,¯}.
Инверсия – не сохраняет 0 и 1 и не монотонна, \/ - не самодвойственна, не линейна.
Пример. { ~, ¯ }.
Обе функции самодвойственны. Система { ~, ¯ } не полна.
Можно показать, что из всякой полной системы функций можно выбрать полную подсистему, содержащую не более четырех функций. Пусть { f1, f2,…, fn} – функционально полная система. Тогда среди fi найдется fk, не сохраняющая константу нуль, т.е. fk(00…0)=1.
Если fk(11…1)=1, то эта же функция не самодвойственна, так как fk(00…0)≠0.
Если же fk(11…1)=0, то эта же функция не сохраняет константу 1 и не монотонна.
Присоединив к fk недостающие три функции, получим систему, состоящую не более чем из четырех функций.
Пример. Составить минимальный базис, включающий функцию
f11(xy)=y→x.
f11(xy) Є К1. Значит, надо добавить любую функцию, которая не принадлежит классу К1. Существует 6 минимальных базисов, содержащих функцию f11(xy). Это {f0,f11}, {f2,f11},{f4,f11},{f6,f11},{f10,f11},{f11,f12}.
Базисы {f8,f11} и {f11,f14} не минимальны, так как f8 и f11 и сами функционально полны.
Пример. Выразить функцию в системе {f0,f11}:
Для преобразований используем систему {\/,/\,¯} как основную:
Глава 2. Минимизация булевых функций.
|
|
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!