Суперпозиции

Определение:

Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.

Способы получения суперпозиций

Рассмотрим две булевы функции:
функцию $f$ от $n$ аргументов $f(x_{1}, x_{2}, ..., x_{n})$ и
функцию $g$ от $m$ аргументов $g(x_{1}, x_{2}, ..., x_{m})$.

Тогда мы можем получить новую функцию из имеющихся двумя способами:

1. Подстановкой одной функции в качестве некоторого аргумента для другой;
2. Отождествлением аргументов функций.

Подстановка одной функции в другую

Определение:

Подстановкой функции $g$ в функцию $f$ называется замена i-того аргумента функции $f$ значением функции $g$: $h(x_{1}, ..., x_{n+m-1}) = f(x_{1}, ..., x_{i-1}, g(x_{i}, ..., x_{i+m-1}), x_{i+m}, ..., x_{n+m-1})$

Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

При подстановке функции g вместо i-того аргумента функции f, результирующая функция h будет принимать аргументы, которые можно разделить на следующие блоки:

1. $x_{1}, ..., x_{i-1}$	– аргументы функции $f$ до вставленной функции $g$
2. $x_{i}, ..., x_{i+m-1}$	– используются как аргументы для вставленной функции $g(x_{i}, ..., x_{i+m-1})$
3. $x_{i+m}, ..., x_{n+m-1}$	– аргументы функции $f$ после вставленной функции $g$

Пример:
$f(a,b) = a \vee b$ — первая исходная функция
$g(a) = \neg a$ — вторая исходная функция
$h(a,b) = f(a,g(b)) = a \vee \neg b$ — подстановка функции $g$ вместо второго аргумента функции $f$
В данном примере при помощи подстановки мы получили функцию $h(a,b)=a \leftarrow b$.

Отождествление переменных

Определение:

Отождествлением переменных называется подстановка i-того аргумента функции $f$ вместо j-того аргумента: $h(x_{1}, ..., x_{n-1}) = f(x_{1}, ..., x_{i}, ..., x_{j-1}, x_{i}, x_{j+1}, ..., x_{n-1})$

Пример:
$f(a,b) = a \vee b$ — исходная функция
$h(a) = a \vee a$ — функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию $P_{1}$ — проектор единственного аргумента.

Ранги суперпозиций

Суперпозиция имеет ранг $n$, если минимальное число подстановок и отождествлений, за она может быть получена из исходного множества функций $K$, равно $n$. Обозначение: $K^{n}$
Например, $K^{1}$ — множество суперпозиций, полученных из исходного множества $K$ за одну подстановку или отождествление, $K^{2}$ — множество суперпозиций, полученных из множества $K \cup{K^{1}}$ за одну подстановку или отождествление и т.д.

Список литературы

1. Композиция функций в математике
2. Дискретная математика, МГУ