Тема 9.4. Теоремы о функциональной полноте

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

Лемма о немонотонных функциях. Если функция немонотонна, то подстановкой констант из неё можно получить отрицание.

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

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

Иначе говоря, существует представление дизъюнкции и конъюнкции в виде суперпозиции констант, отрицаний и нелинейной функции .

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

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

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

Очевидно, что из обычной полноты системы следует её слабая полнота.

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

Доказательство:

1) Необходимость. Классы монотонных и линейных функций замкнуты и содержат 0 и 1. Поэтому если не содержит немонотонных или нелинейных функций, то их нельзя получить с помощью суперпозиций функций из системы и констант.

2) Достаточность. Пусть содержит немонотонную и нелинейную функцию. Тогда по лемме 1 подстановкой констант из монотонной функции получаем отрицание, а затем по лемме 2 из нелинейной функции с помощью отрицаний и констант получаем дизъюнкцию и конъюнкцию.

Пример 9.6:

а) Система функционально полна в слабом смысле, так как конъюнкция нелинейна, а операция немонотонна.

б) В функционально полной системе единственная функция – штрих Шеффера – нелинейна и немонотонна.

Для формулировки необходимых и достаточных условий «cильной» полноты (в отличие от слабой) нужно ввести ряд определений, описывающих ещё три замкнутых класса функций.

Определение: Функция называется сохраняющей ноль, если выполняется и сохраняющей единицу, если выполняется .

Оба данных класса функций являются замкнутыми, что проверяется подстановкой констант в суперпозиции. Равным образом замкнутый класс образуют самодвойственные функции (такие, что ).

Теорема (вторая – основная – теорема о функциональной полноте). Для того чтобы система функций была функционально полной (в сильном смысле), необходимо и достаточно, чтобы она содержала: 1) нелинейную функцию, 2) немонотонную функцию, 3) функцию, не являющуюся самодвойственной, 4) функцию, не сохраняющую ноль, 5) функцию, не сохраняющую единицу.

Дата добавления: 2015-10-28