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

2019-01-09T17:03:45Z

176.59.3.251: /* Отождествление переменных */ вместо i должна стоять j

{{Определение
|definition =
'''Суперпозиция функций''' (или '''сложная функция''', или '''композиция функций''', англ. ''function composition'') {{---}} это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
}}
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.

== Способы получения суперпозиций ==
Рассмотрим две [[Определение булевой функции|булевы функции]]:
функцию <tex>f</tex> от <tex>n</tex> аргументов <tex>f(x_{1}, x_{2}, \ldots, x_{n})</tex> и
функцию <tex>g</tex> от <tex>m</tex> аргументов <tex>g(y_{1}, y_{2}, \ldots, y_{m})</tex>.

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

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

{{Определение
|definition =
'''Подстановкой''' (англ. ''substitution'') функции <tex>g</tex> в функцию <tex>f</tex> называется замена <tex>i</tex>-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:

<center><tex>h(x_{1}, \ldots, x_{n+m-1}) = f(x_{1}, \ldots, x_{i-1}, g(x_{i}, \ldots, x_{i+m-1}), x_{i+m}, \ldots, x_{n+m-1})</tex></center>
}}

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

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

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

'''Пример:'''

Исходные функции:
#<tex> f(a,b) = a \vee b </tex>
#<tex> g(a) = \neg a </tex>

<tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex>. В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.

=== Отождествление переменных ===
{{Определение
|definition=
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:

<center><tex>h(x_{1}, \ldots, x_{j-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{j-1}, x_{j}, x_{j+1}, \ldots, x_{n})</tex></center>
}}

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

'''Пример:'''

<tex> f(a,b) = a \vee b </tex> {{---}} исходная функция

<tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.

== Ранги суперпозиций ==
{{Определение
|definition =
'''Ранг суперпозиции''' (англ. ''rank of function composition'') {{---}} это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций.
Суперпозиция <tex>K</tex> ранга <tex>n</tex> обозначается как <tex>K^{n}</tex>
}}

== См. также ==
* [[Определение_булевой_функции|Булевы функции]]
* [[Представление_функции_формулой,_полные_системы_функций|Представление функции формулой, полные системы функций]]

== Источники информации ==
* Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, 2006, стр 62-63
*[http://ru.wikipedia.org/wiki/Композиция_функций Композиция функций в математике]
*[http://mini-soft.ru/nstu/diskr/index.php Е.Л. Рабкин, Ю.Б. Фарфоровская, Дискретная математика, Глава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Булевы функции]]

Викиконспекты - Вклад участника [ru]

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