Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-09-26 | 512 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!