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

Поста.

Определение. Класс функций F называется полным, если его замыкание совпадает с P_n: [F] = P_n.

Другими словами, множество функций F = {f₁, ..., f_n} называется полной системой, если любая функция алгебры логики представима посредством суперпозиции функций из множества F.

Пример 1. Из представимости функций в виде СДНФ следует полнота системы функций {xy, xvy, }. Случай тождественного нуля не приводит к ограничениям, так как 0=x^

Пример 2. Представимость функций полиномами Жегалкина связана с полнотой системы функций

{xy, x + y, 0, 1}.

Пример 3. Так как , то система { , xvy} – полная.

Пример 4. Так как ,то система { , x^y} – полная.

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

Проверим, что все рассмотренные в примерах полные системы являются базисами.

1. и xvy.

xvy – монотонная функция. - линейная и самодвойственная. Суперпозицией таких функций нельзя получить функции от большего числа переменных.

Примеры. (К доказательству теоремы Поста)

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

Решение.

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

Поэтому, если функционально замкнутый класс содержит одну из функций Шеффера, то он совпадает с классом всех булевых функций.

Данный нам класс является собственным функционально замкнутым классом, поэтому он не может содержать функции Шеффера.

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

Таким образом, дополнение не может быть функционально замкнутым классом.

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

Решение.

1) Необходимость. Дано: Ф – полная система функций; F – функционально замкнутый класс, причем [F] P_n.

Доказать:: и .

От противного: .

Но тогда все функции Ф принадлежат F – функционально замкнутому классу и ему же принадлежали бы все их суперпозиции. Т.е., [F] = P_n.

2) Достаточность. Дано: - для всякого функционально замкнутого класса.

Доказать:: [Ф] = P_n

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

Этот класс не может быть собственным, так как Ф не содержится ни в каком собственном классе. Поскольку он, кроме того, не пуст, то он содержит все функции алгебры логики [Ф] = P_n.

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

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

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

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

1. Необходимость. Необходимость следует из необходимости условия задачи N.

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

Поскольку этот класс, кроме того, не пуст, то он совпадает с классом всех функций алгебры логики P_n.

Оказывается, что все предполные классы легко перечисляются. Ими являются Т₀, Т₁, Т_*, , Т_L.

Однако удобнее доказывать не предполноту этих классов, а непосредственно критерий полноты, который вытекает из этого факта и задачи P.

Напротив, исходя из критерия полноты, докажем предполноту классов Т₀, Т₁, Т_*, , Т_L и то, что всякий собственный функционально замкнутый класс содержится в одном из них.

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

Пусть . Отождествим все переменные. Тогда, если φ(1,..., 1) = 1, то мы получим 1; если φ(1, …, 1) = 0, то получим 0.

Теорема (Пост). Для полноты системы функций необходимо и достаточно, чтобы для каждого из классов Т₀, Т₁, Т_*, , Т_L в Ф нашлась бы функция ему не принадлежащая.

Необходимость. Необходимость следует из необходимости условия задачи N (В противном случае все функции из Ф принадлежали бы, вместе с их суперпозициями, какому-либо собственному функционально замкнутому классу).

Достаточность. Дано: пусть , не входящие в Т₀, Т₁, Т_*, , Т_L.

Доказать: [Ф] = P_n.

Доказательство: возьмем из Ф функцию, не сохраняющую ноль, и функцию, не сохраняющую 1. Отождествим в них переменные. В силу задачи Q в первом случае мы получаем 1 или , во втором случае получаем 0 или .

В результате мы получаем обе константы или отрицание (быть может, и то и другое).

1. Пусть мы получили константы. Покажем, что тогда можно представить отрицание в виде суперпозиции.

Поскольку константы не принадлежат классам Т_* и одному из классов Т₀ или Т₁, а - линейная функция, то для этой цели естественно воспользоваться немонотонной функцией из Ф. Действительно, в силу задачи K отрицание можно представить в виде суперпозиции произвольной немонотонной функции и констант.

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

2. Рассмотрим теперь другой случай, когда при отождествлении переменных как у функции, не принадлежащей Р₀, так и у функции, не принадлежащей Р₁, получается отрицание.

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

Таким образом, в обоих случаях мы имеем функции 0, 1, . Мы еще не использовали нелинейной функции.

Применяя задачу F, мы получаем из нее и одной из констант какую-либо нелинейную функцию двух переменных. А затем, используя задачу, можно получить из этой функции и отрицания любую нелинейную функцию от двух переменных, например, ху (или xvy, или функцию Шеффера ).

φ	Т0	Т1	Т*		ТL
φ1
φ2
...	...	...	.,.	...	...
φk

Поскольку мы построили полную систему функций, теорема доказана.

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

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

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

Т₀, Т₁, Т_*, , Т_L.

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

Примиер 2. Доказать, что функционально замкнутые классы Т₀, Т₁, Т_*, , Т_L являются предполными и других предполных классов нет.

Решение.

В силу задачи 1 другие классы не могут быть предполными. В силу задачи 2 каждый из пяти перечисленных классов является предполным.

Пример 3. Доказать, что ни один из классов

Т₀, Т₁, Т_*, , Т_L­ не содержится в другом.

Решение.

Если бы какой-либо класс содержался в другом, то в формулировке теоремы Поста его можно было бы отбросить.

Замечание. Ясно, что теорема Поста позволяет выяснить вопрос о том, является ли полная система базисом. Это удобно сделать с помощью таблиц Поста.