Теорема о функциональной полноте.
Определение 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].
В функционально полную систему переключательных функций двух аргументов в соответствии с теоремой о функциональной полноте должны входить такие функции, которые совместно перекрывают клетками без крестиков колонки TL, T0, T1, TM, TS (табл. 1.6). Из переключательных функций, сведенных в табл. 1.6, можно составить различные функционально полные системы. Рассмотрим некоторые из них.
1. f14 (х, у)=х½у; эта переключательная функция одна обладает свойством функциональной полноты, так как является нелинейной, немонотонной, несамодвойственной, не сохраняет нуль и единицу. Следовательно, любая переключательная функция может быть представлена через функции f14 (х, у), и поэтому любая сложная функция может быть представлена через эту функцию;
2. f8 (х, у)=х¯у; эта функция, так же как и функция f14 (х, у), одна обладает свойством функциональной полноты;
3. f13 (х, у)=x®y и f0 (х, у)=0 или f11 (х, у)=y®x и f0 (х, у)=0, т. е. импликация и константа нуль;
4. f6 (х, у)=хÅу; f1 (х, у)=xÙy и f15 (х, у)=1, т. е. сумма по модулю два, произведение и константа единица. Функциональная полнота этой системы следует не только из теоремы о функциональной полноте, но и из доказанной ранее теоремы Жегалкина (см. п. 1.3.2).
В связи с тем, что существует большое число различных функционально полных систем переключательных функций, возникает проблема выбора функционально полной системы, представляющей наибольший практический интерес.