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

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

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

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

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

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

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

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

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

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

Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math]-того аргумента функции [math]f[/math] значением функции [math]g[/math]: [math]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})[/math]

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

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

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

Пример:

Исходные функции:

1. [math] f(a,b) = a \vee b [/math]
2. [math] g(a) = \neg a [/math]

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

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

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

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

Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math].

Пример:

[math] f(a,b) = a \vee b [/math] — исходная функция

[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию [math]P_{1}[/math] — проектор единственного аргумента.

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

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

Ранг суперпозиции (англ. rank of function composition) — это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций. Суперпозиция [math]K[/math] ранга [math]n[/math] обозначается как [math]K^{n}[/math]

Источники информации

• Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, 2006, стр 62-63
• Композиция функций в математике
• Е.Л. Рабкин, Ю.Б. Фарфоровская, Дискретная математика, Глава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы