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

Определение 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)					*		*	*

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

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

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

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

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

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

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

Дата добавления: 2014-01-06