Полные системы булевых функций.

Определение. Система булевых функций {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. Минимизация булевых функций.