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

Определение. Система булевых функций {f₁, f₂, …,f_n} называется полной, если любая переключательная функция может быть представлена суперпозицией функций данной системы.

Теорема Поста-Яблонского. Для того чтобы система булевых функций была полной, необходимо и достаточно, чтобы она содержала:

- хотя бы одну функцию, не сохраняющую константу нуль;

- хотя бы одну функцию, не сохраняющую константу единица;

- хотя бы одну функцию, не являющуюся линейной;

- хотя бы одну функцию, не являющуюся монотонной;

- хотя бы одну функцию, не являющуюся самодвойственной.

Это критерий полноты системы.

Система функций {f₁, f₂, …,f_n}, являющаяся полной, называется базисом.

Минимальным базисом называется такой базис, для которого удаление хотя бы одной из функций f_i , образующих тот базис, превращает систему функций {f₁, f₂, …,f_n } в неполную.

Будем рассматривать функции, зависящие от n аргументов. Число различных функций равно .

Тривиальная полная система состоит из всех функций.

Функции инверсии, дизъюнкции и конъюнкции образуют полную систему. Это вытекает из основной теоремы, утверждающей, что любая булева функция может быть записана в виде дизъюнкции минтермов (или конъюнкции макстермов).

Базис { /\,\/,¯ } не минимален, так как может быть уменьшен за счет выбрасывания из него /\ или \/. Это следует из формул де Моргана:

Базисы {/\,¯} и {\/,¯} являются минимальными.

Другие базисы:

а) { ,/\,1}- функционально полная система (это следует из теоремы Жегалкина);

б) функция импликации и константа 1: {x→y,1};

в) функция импликации и инверсии : {x→y,¯}.

Пример. Доказать, что функция Шеффера образует полную систему

f₁₄(xy)=x | y= .

Доказательство. Выразим ¯ и /\ через функцию Шеффера:

Так как {¯,/\} – полная система, утверждение доказано.

Пример. Выразим функцию, используя только функцию Шеффера:

.

Пример. Доказать, что А↓В образует функционально полную систему

Так как инверсия и дизъюнкция выражаются только через функцию «стрелка Пирса», а {¯,\/} – функционально полная система, то А↓В является функционально полной системой.

Пример. Выразить функцию, используя только функцию «стрелка Пирса»:

Выбор функционально полной системы по таблице.

Пример. {\/,¯}.

Инверсия – не сохраняет 0 и 1 и не монотонна, \/ - не самодвойственна, не линейна.

Пример. { ~ , ¯ }.

Обе функции самодвойственны. Система { ~ , ¯ } не полна.

Можно показать, что из всякой полной системы функций можно выбрать полную подсистему, содержащую не более четырех функций. Пусть { f₁, f₂,…, f_n} – функционально полная система. Тогда среди f_i найдется f_k , не сохраняющая константу нуль, т.е. f_k(00…0)=1.

Если f_k(11…1)=1, то эта же функция не самодвойственна, так как f_k(00…0)≠0.

Если же f_k(11…1)=0, то эта же функция не сохраняет константу 1 и не монотонна.

Присоединив к f_k недостающие три функции, получим систему, состоящую не более чем из четырех функций.

Пример. Составить минимальный базис, включающий функцию

f₁₁(xy)=y→x.

f₁₁(xy) Є К₁. Значит, надо добавить любую функцию, которая не принадлежит классу К₁. Существует 6 минимальных базисов, содержащих функцию f₁₁(xy). Это {f₀,f₁₁}, {f₂,f₁₁},{f₄,f₁₁},{f₆,f₁₁},{f₁₀,f₁₁},{f₁₁,f₁₂}.

Базисы {f₈,f₁₁} и {f₁₁,f₁₄} не минимальны, так как f₈ и f₁₁ и сами функционально полны.

Пример. Выразить функцию в системе {f₀,f₁₁}:

Для преобразований используем систему {\/,/\,¯} как основную:

Глава 2. Минимизация булевых функций.