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

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

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

хотя бы одну переключательную функцию, не со­храняющую нуль;

хотя бы одну переключательную функцию, не со­храняющую единицу;

хотя бы одну нелинейную переключательную функцию:

хотя бы одну немонотонную переключательную функцию;

хотя бы одну несамодвойственную переключатель­ную функцию.

Таблица 1.6

Переключательные функции двух аргументов

x					Линейные (TL)	Сохраняющие 0 (T0)	Сохраняющие 1 (T1)	Монотонные (TM)	Самодвойственные (Ts)
y
f0(x,y)					*	*		*
f1(x,y)						*	*	*
f2(x,y)						*
f3(x,y)					*	*	*	*	*
f4(x,y)						*
f5(x,y)					*	*	*	*	*
f6(x,y)					*	*
f7(x,y)						*	*	*
f8(x,y)
f9(x,y)					*		*
f10(x,y)					*				*
f11(x,y)							*
f12(x,y)					*				*
f13(x,y)							*
f14(x,y)
f15(x,y)					*		*	*

Может показаться, что любая функционально пол­ная система должна содержать не менее пяти переключательных функций. Однако ввиду того, что многие переключательные функции удовлетворяют одновремен­но нескольким требованиям, предъявляемым теоремой о функциональной полноте, количество независимых переключательных функций, входящих в функциональ­но полную систему, всегда меньше пяти^[2].

В функционально полную систему переключательных функций двух аргументов в соответствии с теоремой о функциональной полноте должны входить такие функ­ции, которые совместно перекрывают клетками без крестиков колонки T_L, T₀, T₁, T_M, T_S (табл. 1.6). Из переключательных функций, сведенных в табл. 1.6, можно составить раз­личные функционально полные системы. Рассмотрим некоторые из них.

f₁₄ (х, у)=х½ у; эта переключательная функция одна обладает свойством функциональной полноты, так как является нелинейной, немонотонной, несамодвойст­венной, не сохраняет нуль и единицу. Следовательно, любая переключательная функция может быть представлена через функции f₁₄ (х, у), и поэтому любая сложная функция может быть представлена через эту функцию;

f₈ (х, у)=х¯ у; эта функция, так же как и функция f₁₄ (х, у), одна обладает свойством функциональной пол­ноты;

f₁₃ (х, у)=x®y и f₀ (х, у)=0 или f₁₁ (х, у)=y® x и f₀ (х, у)=0, т. е. импликация и константа нуль;

f₆ (х, у)=хÅ у; f₁ (х, у)=xÙ y и f₁₅ (х, у)=1, т. е. сум­ма по модулю два, произведение и константа единица. Функциональная полнота этой системы следует не толь­ко из теоремы о функциональной полноте, но и из дока­занной ранее теоремы Жегалкина (см. п. 1.3.2).

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

Функционально полные системы логических функций.

Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение.

Основная функционально полная система логических функций.

Наибольшее распространение получил набор, в состав которого входят три логические функции:

· f₁₀ – инверсия (логическая связь НЕ, логическое отрицание);

· f₁ – конъюнкция (логическая связь И, логическое умножение),

· f₇ – дизъюнкция (логическая связь ИЛИ, логическое сложение).

Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f₁₀ и f₁ или f₁₀ и f₇. Свойства этих функций были рассмотрены ранее.

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