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

Мы рассмотрели лишь достаточное условие полноты системы. Перейдем теперь к установлению критерия полноты. Прежде познакомимся с понятиями замыкания и замкнутого класса.

Замыкание.

Пусть К – некоторое подмножество элементарных функций. Замыканием подмножества К называется множество булевых функций, представимых в виде формул через функции К. Обозначение замыкания : [K].

Пример: замыканием множества булевых функций является само это множество. Обозначим множество всех булевых функций через Р₂ (2- так как функция принимает только два значения). Тогда [P₂]= P₂ .

Свойства замыкания :

1. K [K];

2. если K₁ K₂, то [K₁] [K₂];

3. [K₁][K₂][K₁K₂].

Можно теперь сформулировать еще одно определение полной системы:

К – полная система, если ее замыкание- все булевы функции .

Замкнутый класс.

Множество К называется функционально замкнутым (или просто замкнутым), если его замыкание – само множество К..

Дадим еще одно определение замкнутого множества (класса).

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

1. переименование некоторой переменной какой-нибудь функции рассматриваемой системы;

2. подстановка некоторой функции из этой системы вместо некоторой переменной любой из функции этой системы.

К замкнутым классам относятся: множество всех булевых функций Р₂; класс функций от одной переменной; класс, содержащий только тождественные функции вида f(X)=X.

Приведем следующее утверждение:

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

Действительно, в противном случае найдется замкнутый класс К такой, что {f₁, f₂, …, f_m}КР₂ и КР₂ . значит, найдется функция f такая , что fК , т.е. не может быть выражена через {f₁, f₂, …, f_m}, что противоречит полноте этой системы.

Рассмотрим некоторые функционально замкнутые классы функций, которые называются важнейшими замкнутыми классами. Они используются в критерии полноты.

Класс Т₀ – класс функций, сохраняющих 0, т.е. f(0,0,…0)=0.

Примеры функций, принадлежащих к Т₀: 0, х, ху=00=0, xvy=0v0=0, x+y=0+0=0.

Функции, не принадлежащие к Т₀: 1, x|y=0|0=1, xy=00=1.

Класс Т₁- класс функций, сохраняющих 1, т.е. f(1,1,…,1)=1.

К этому классу относятся , например, 1, x, xy=11=1, xvy=1v1=1, xy=11=1.

Примеры функций, не принадлежащих классу Т₁: 0, x|y=1|1=0, xy=11=0.

Класс S – класс самодвойственных функций.

Самодвойственной функцией называется функция f(x₁, x₂, …,x_n), если f(x₁, x₂, …,x_n)  f*(x₁, x₂, …,x_n), где .

К S относится , например, :

Функции ху, xvy, xy не относятся к самодвойственным функциям.

Класс L – класс линейных функций.

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

К линейным относятся: 1, 0, х, , х+у.

Функции не линейные.

Класс монотонных функций M.

Введем отношение частичного порядка на множестве упорядоченных наборов (векторов).

Вектор = (₁ , ₂ ,…,_n) предшествует вектору  = (₁ , ₂ ,…, _n), если _i  _i для любых i= 1 – n. Обозначение

Например, , т.к. 11, 0  1, 1  1. векторы (01) и (10) – не сравнимы.

Говорят так же, что  и  сравнимы.

Функция f(x₁, x₂, …,x_n) называется монотонной, если любых векторов  и  списка переменных таких, что , имеем f() f().

К монотонным относятся, например, функции : х, ху, xvy.

Проверим монотонность xy и xvy. Составим таблицы истинности :

По таблице истинности легко установить монотонность и этой функции.

Функция ху не является монотонной, т.к. , но f(00)=1, a f(10)=0.

Любые элементарные суперпозиции не выводят из рассмотренных классов. Тем самым доказывается их функциональная замкнутость.

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

Для того, чтобы система булевых функций была полной, необходимо и достаточно, чтобы для каждого из классов Т₀, Т₁, S, L, M нашлась функция f_i из этой системы не принадлежащая этому классу.

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

Рассмотрим пример: докажем полноту системы {+, v, 1,0}.

Составим таблицу:

Для 0 и 1 таблица заполняется тривиально. Не составляет труда проверить принадлежность х+у и xvy к Т₀ и Т₁. Более подробно покажем заполнение оставшихся ячеек.

Для функции х+у.

S: , значит, х+уS;

L: x+yL;

M: составим таблицу истинности:

Функция не монотонная, т.к., например, , а f(01)>f(11).

Для функции xvy.

S: для xvy двойственной является ху, следовательно, х+уS;

L: , значит, xvyL;

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

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