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