Суперпозиции
| Определение: |
| Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. |
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Способы получения суперпозиций
Рассмотрим две булевы функции: функцию от аргументов и функцию от аргументов .
Тогда мы можем получить новую функцию из имеющихся двумя способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Подстановка одной функции в другую
| Определение: |
| Подстановкой функции в функцию называется замена i-того аргумента функции значением функции :
|
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции g вместо i-того аргумента функции f, результирующая функция h будет принимать аргументы, которые можно разделить на следующие блоки:
| 1. | – аргументы функции до подставленного значения функции |
| 2. | – используются как аргументы для вычисления значения функции |
| 3. | – аргументы функции после подставленного значения функции |
Пример:
Исходные функции:
— подстановка функции вместо второго аргумента функции . В данном примере при помощи подстановки мы получили функцию .
Отождествление переменных
| Определение: |
| Отождествлением переменных называется подстановка i-того аргумента функции вместо j-того аргумента:
|
Таким образом, при отождествлении переменных мы получаем функцию с количеством аргументов .
Пример:
— исходная функция
— функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию — проектор единственного аргумента.
Ранги суперпозиций
| Определение: |
| Ранг суперпозиции - это минимальное число подстановок и отождествлений, за которое она может быть получена из исходного множества функций. Суперпозиция ранга обозначается как |
Например, — множество суперпозиций, полученных из исходного множества за одну подстановку или отождествление, — множество суперпозиций, полученных из множества за одну подстановку или отождествление и т.д.
