Функциональная полнота.

Определение. Класс функций K называется предполным в С, если в С не существует класса К’, чтобы имело место К ÌК’ÌC, т.е. не найдётся класса, который бы включал в себя полностью данный класс и был меньше, чем С.

Мы выделили 5 классов функций алгебры логики. Различных классов функций гораздо больше; так, a-функции образуют свой класс, пересечение классов снова будет классом.

Пост установил, что классы М, D, L, CC1 и CC0 являются предполными и других предполных классов в С нет.

Результаты работ Поста позволили ответить на важный вопрос: какими свойствами должны обладать функции множества F, чтобы это множество порождало класс С. Такие множества называют функционально полными, поставленный вопрос известен как вопрос об условиях функциональной полноты.

Инженерная трактовка этого вопроса: какими свойствами должны обладать функции элементов, чтобы схемой из этих элементов можно было реализовать любые функции.

Решение задачи формулируется как теорема Поста.

Теорема. Для того, чтобы множество функций порождало класс всех функций С, необходимо и достаточно, чтобы это множество содержало, по крайней мере, одну немонотонную, одну несамодвойственную, одну нелинейную, одну не сохраняющую константу ноль и одну не сохраняющую константу единица функцию.

Необходимые условия формулируются из результатов Поста о предполных классах. Необходимо, чтобы по отношению любого из этих классов в F была функция, не принадлежащая классу. Действительно, если в рассматриваемом множестве нет, например, несамодвойственной функции, то в результате суперпозиции будут реализовываться только самодвойственные функции, то естьт.е. нельзя получить, например, конъюнкцию, которая не является самодвойственной.

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

Пусть множество содержит функцию ff₀, не сохраняющую константу ноль, ff₁, не сохраняющую константу единица, ff₂ –немонотонную, ff₃ – несамодвойственную и ff₄ – нелинейную функцию (функции не обязательно различны).

По определению ff₀ (0,0,…,0) =1. Для этой функции возможны два варианта значений ff₀ (1, 1,…,1).

· Если ff₀ (1, 1,…,1)=1, то функция является b-функцией, и при подстановке вместо всех аргументов одного произвольного аргумента она превращается в константу 1. Имея константу 1, из функции ff₁ получаем константу 0, так как ff₁(1, 1,…,1)=0.

· Если ff₀ (1, 1,…,1)=0, то функция является d-функцией, и при подстановке вместо всех аргументов одного произвольного аргумента она превращается в инверсию. В этом случае рассмотрим функцию ff₃. Для неё найдется набор значений аргументов <aa₁, aa₂,…, aa_n>, такой, что
ff(aa₁, aa₂,…, aa_n)= ff(`aa<sub>1</sub>, `aa₂,…, `aa_n).

В функцию ff₃ поставим произвольную переменную в прямой форме, если компонента набора aa_i равна 1, и в инверсной форме, если компонента набора равна 0, Получим константу, равную ff(aa₁, aa₂,…, aa_n). Из неё с помощью инверсии получается вторая константа.

С помощью констант из функции ff₂ можно получить инверсию.

Для неё найдется два соседних набора, таких, что на меньшем наборе функция равна единице, а на большем – нулю. Если подставим в ff₂ константы этого набора, где они совпадают, и произвольную переменную, где наборы отличаются, получим инверсию этой переменной.

Константы и инверсия позволяет получить конъюнкцию переменных из функции ff₄. Запишем эту функцию в виде полинома Жегалкина, выделим в нём первое вхождение переменных в конъюнкцию, и все переменные, кроме переменных конъюнкции, заменим на константу 0, а переменные конъюнкции заменим произвольно на два различных аргумента, например на xx и yy. В результате возможны (с точностью до инверсии константы С₀ в полиноме) следующие варианты:

1. xxyy,

2. xxyyÅxx,

3. xxyyÅyy,

4. xxyyÅxxÅyy.

В первом случае получаем конъюнкцию, что и необходимо получить, во втором варианте полученная функция равна функции `xxyy, из которой с помощью инверсии получим конъюнкцию. То же самое можно сказать и о третьем варианте, где функция равна `yyxx. Для последнего варианта функция равна дизъюнкции.

Теорема доказана.

В табл. 5.13 показана принадлежность простейших функций к предполным классам. Здесь + означает, что функция принадлежит, х –что функция не принадлежит к классу. Здесь символом ‘ обозначена инверсия.

Из таблицы легко видеть, что функциональной полнотой обладают множества {`xx, xxÚyy}, {`xx, xx×yy}, {xx×yy, xxÅyy, 1}. {xx®yy, 1}. Особый интерес представляют две последние функции, составляющие монофункциональный базис. Такие функции, отвечающие всем условиям теоремы Поста, получили название функций шефферовского типа.

Теорема позволяет определить, является ли заданное множество функционально полным, если нет, то какой функции в нём не хватает. Можно решать задачу построения функции шефферовского типа от более чем двух переменных. Это должна быть d-функция, так как она не сохраняет константы. Как d-функция она немонотонна, и дальше нужно распределить единицы и нули в таблице так, чтобы функция была нелинейной и несамодвойственной.

Задачи Контрольные вопросы и задания

5.8.1. Представление функций