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