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

Перейдем к рассмотрению одного из основных вопросов алгебры логики - вопроса о необходимых и достаточных условиях полноты.

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

 Необходимость. Пусть система полна, следовательно, ее замыкание совпадает со множеством всех булевых функций: [ ] = P₂. (*)

Предположим, что содержится в одном из указанных классов целиком. Обозначим этот класс через R. По определению замкнутого класса R=[ R]. В соответствии с третьим свойством замыкания справедливо соотношение: ( ÍR)®([ ] Í [R]), т.е. ( ÍR) ® ([ ]ÍR). (**)

Сравнивая правые части выражений (*) и (**), делаем вывод, что множество всех булевых функций P₂ является подмножеством замкнутого класса R. Это неверно. Остается утверждать, что целиком не содержится ни в одном из пяти замкнутых классов T₀, T₁, S, M и L.

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

= { f₀, f₁, f_S, f_M, f_L }.

Пример. Если ={ ,x₁&x₂}, то можно выбрать f₀ = f₁ = f_M = , f_S = f_L = x₁&x₂.

Доказательство достаточности будем проводить в три этапа.

I. Построение при помощи функций f₀, f₁ и f_S констант 0 и 1

Так как функция f₀ не сохраняет константу 0, то f₀(0,0,...,0)=1; так как функция f₁ не сохраняет константу 1, то f₁(1,1,...,1)=0. Рассмотрим 4 возможных случая для функций f₀ и f₁ на противоположных наборах.

1. Пусть f₀(1,1,...,1)=0, f₁(0,0,...,0)=0. Составим функцию одной переменной j(x)= f₀(x,x,...,x) и вычислим ее значения в 0 и 1: j(0)= f₀(0,0,...,0)=1, j(1)= f₀(1,1,...,1)=0.

Следовательно, j(x)= . По лемме 1.1 из и f_S можно получить константу. Имея одну из констант и используя отрицание , можно получить вторую константу.

2. Пусть f₀(1,1,...,1)=0, f₁(0,0,...,0)=1. Рассуждаем совершенно аналогично случаю 1.

3. Пусть f₀(1,1,...,1)=1, f₁(0,0,...,0)=0. Составим две функции одной переменной j(x)= f₀(x,x,...,x) и y(x)= f₁(x,x,...,x) и вычислим их значения в точках 0 и 1:

j(0)= f₀(0,0,...,0)=1 и j(1)= f₀(1,1,...,1)=1, т.е. j(x)º1;

y(0)= f₁(0,0,...,0)=0 и y(1)= f₁(1,1,...,1)=0, т.е. y(x)º0.

4. Пусть f₀(1,1,...,1)=1, f₁(0,0,...,0)=1. Составим функцию одной переменной y(x)= f₁(x,x,...,x) и вычислим ее значения в 0 и 1:

y(0)= f₁(0,0,...,0)=1, y(1)= f₁(1,1,...,1)=0.

Следовательно, y(x)= . По лемме 1.1 из и f_S можно получить константу. Имея одну из констант и используя отрицание , можно получить вторую константу.

II. Построение при помощи констант 0 и 1 и функции f_M функции

Этот этап осуществляется на основе леммы 1.2.

III. Построение при помощи констант 0 и 1 и функций и f_L функции x₁&x₂.

Этот этап осуществляется на основе леммы 1.3.

Таким образом, при помощи формул над (а значит, и над ) нам удалось реализовать функции и x₁&x₂, которые, как известно, составляют полную систему. Этим достаточность доказана. 

Рассмотрим пример 1.1, иллюстрирующий возможности теоремы о функциональной полноте. Покажем, что система функций f₁=x₁&x₂, f₂=0, f₃=1 и f₄= x₁Åx₂Å x₃ является полной. В самом деле, f₃ Ï T₀, f₂ Ï T₁, f₂ Ï S, f₄ Ï M, f₁ Ï L.

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

{f₂, f₃,f₄} Ì , { f₁, f₃,f₄ } Ì , { f₁, f₂, f₄} Ì , { f₁, f₂, f₃} Ì .

Теорема 1.6. Из всякой полной в P₂ системы функций можно выделить полную подсистему, содержащую не более четырёх функций.

 При доказательстве теоремы о функциональной полноте было показано, что из можно выделить полную подсистему , содержащую не более пяти функций. Но если функция f₀ не сохраняет константу 0 (f₀ÏT₀), то она либо не самодвойственная: f₀(0,0,...,0)= f₀(1,1,...,1)=1, либо не монотонная: 1=f₀(0,0,...,0)> f₀(1,1,...,1)=0, поэтому полной будет либо система {f₀,f₁,f_M, f_L}, либо система {f₀,f₁,f_S, f_L}.  Пример 1.1 показывает, что константа 4 не может быть понижена.