§ 8. Теорема о функциональной полноте
Перейдем к рассмотрению одного из основных вопросов алгебры логики вопроса о необходимых и достаточных условиях полноты.
Теорема
1.5 (о
функциональной полноте).
Для того, чтобы система функций
была полной, необходимо и достаточно,
чтобы она целиком не содержалась ни в
одном из пяти замкнутых классов
T0,
T1,
S,
M
и L.
Необходимость.
Пусть система
полна, следовательно, ее замыкание
совпадает со множеством всех булевых
функций: [
]
= P2.
(*)
Предположим, что
содержится в одном из указанных классов
целиком. Обозначим этот класс через R.
По определению замкнутого класса R=[
R]. В соответствии
с третьим свойством замыкания справедливо
соотношение: (
R)([
]
[R]),
т.е. (
R)
([
]R).
(**)
Сравнивая правые
части выражений (*) и (**), делаем вывод,
что множество всех булевых функций P2
является подмножеством замкнутого
класса R.
Это неверно. Остается утверждать, что
целиком не содержится ни в одном из пяти
замкнутых классов T0,
T1,
S,
M
и L.
Достаточность.
Пусть
целиком не содержится ни в одном из пяти
замкнутых классов T0,
T1,
S,
M
и L.
Тогда из
можно выделить подсистему
,
содержащую не более пяти функций, которая
также обладает этим свойством. Для этого
из системы
возьмем функции f0,
f1,
fS,
fM
и fL,
которые не
принадлежат
соответственно классам T0,
T1,
S,
M
и L
и положим
= { f0,
f1,
fS,
fM,
fL
}.
Пример.
Если
={
,x1&x2},
то можно выбрать f0
= f1
= fM
=
, fS
= fL
= x1&x2.
Доказательство достаточности будем проводить в три этапа.
I. Построение при помощи функций f0, f1 и fS констант 0 и 1
Так как функция f0 не сохраняет константу 0, то f0(0,0,...,0)=1; так как функция f1 не сохраняет константу 1, то f1(1,1,...,1)=0. Рассмотрим 4 возможных случая для функций f0 и f1 на противоположных наборах.
1. Пусть f0(1,1,...,1)=0, f1(0,0,...,0)=0. Составим функцию одной переменной (x)= f0(x,x,...,x) и вычислим ее значения в 0 и 1: (0)= f0(0,0,...,0)=1, (1)= f0(1,1,...,1)=0.
Следовательно,
(x)=
.
По лемме 1.1 из
и fS
можно получить константу. Имея одну из
констант и используя отрицание
,
можно получить вторую константу.
2. Пусть f0(1,1,...,1)=0, f1(0,0,...,0)=1. Рассуждаем совершенно аналогично случаю 1.
3. Пусть f0(1,1,...,1)=1, f1(0,0,...,0)=0. Составим две функции одной переменной (x)= f0(x,x,...,x) и (x)= f1(x,x,...,x) и вычислим их значения в точках 0 и 1:
(0)= f0(0,0,...,0)=1 и (1)= f0(1,1,...,1)=1, т.е. (x)1;
(0)= f1(0,0,...,0)=0 и (1)= f1(1,1,...,1)=0, т.е. (x)0.
4. Пусть f0(1,1,...,1)=1, f1(0,0,...,0)=1. Составим функцию одной переменной (x)= f1(x,x,...,x) и вычислим ее значения в 0 и 1:
(0)= f1(0,0,...,0)=1, (1)= f1(1,1,...,1)=0.
Следовательно,
(x)=
.
По лемме 1.1 из
и fS
можно получить константу. Имея одну из
констант и используя отрицание
,
можно получить вторую константу.
II. Построение
при помощи констант 0
и 1
и функции fM
функции
Этот этап осуществляется на основе леммы 1.2.
III. Построение
при помощи констант 0
и 1
и функций
и fL
функции x1&x2.
Этот этап осуществляется на основе леммы 1.3.
Таким образом, при
помощи формул над
(а значит, и над
)
нам удалось реализовать функции
и x1&x2,
которые, как известно, составляют полную
систему. Этим достаточность доказана.
Рассмотрим пример 1.1, иллюстрирующий возможности теоремы о функциональной полноте. Покажем, что система функций f1=x1&x2, f2=0, f3=1 и f4= x1x2 x3 является полной. В самом деле, f3 T0, f2 T1, f2 S, f4 M, f1 L.
Раз система этих функций целиком не содержится ни в одном из 5 указанных классов, значит, полна.С другой стороны, удаление любой из этих функций приводит к неполной системе:
{f2,
f3,f4}
,
{ f1,
f3,f4
}
, {
f1,
f2,
f4}
,
{ f1,
f2,
f3}
.
Теорема
1.6. Из всякой полной в P2
системы
функций можно выделить полную подсистему,
содержащую не более четырёх функций.
При доказательстве
теоремы о функциональной полноте было
показано, что из
можно выделить полную подсистему
,
содержащую не более пяти функций. Но
если функция f0
не сохраняет константу 0 (f0T0),
то она либо не самодвойственная:
f0(0,0,...,0)=
f0(1,1,...,1)=1,
либо не монотонная: 1=f0(0,0,...,0)>
f0(1,1,...,1)=0,
поэтому полной будет либо система
{f0,f1,fM,
fL},
либо система {f0,f1,fS,
fL}. Пример
1.1 показывает, что константа 4 не может
быть понижена.