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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 5.

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

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

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

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

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

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