2
правки
Изменения
м
== Список литературы ==#[http[Категория://ru.wikipedia.org/wiki/Композиция_функций Композиция функций в математикеДискретная математика и алгоритмы]]#[http[Категория://mathcyb.cs.msu.su/paper/books/dmcour.pdf Дискретная математика, МГУБулевы функции]]
→Отождествление переменных
{{Определение
|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(x_y_{1}, x_y_{2}, ...\ldots, x_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(x_y_{i1}, ...\ldots, x_y_{i+m-1})</tex>
|-
|3. <tex> x_{i+m}, ...\ldots, x_{n+m-1} </tex> |– {{---}} аргументы функции <tex>f</tex> после вставленной подставленного значения функции <tex>g</tex>
|}
{{Определение
|definition=
'''Отождествлением переменных''' (англ. ''identification of variables'') называется подстановка <tex>i</tex>-того аргумента функции <tex>f</tex> вместо <tex>j</tex>-того аргумента:
<center><tex>h(x_{1}, ...\ldots, x_{nj-1}, x_{j+1}, \ldots, x_{n}) = f(x_{1}, ...\ldots, x_{i}, ...\ldots, x_{j-1}, x_{i}, x_{j+1}, ...\ldots, x_{n-1})</tex></center>
}}
Таким образом, при отождествлении <tex>c</tex> переменных мы получаем функцию <tex>h</tex> с количеством аргументов <tex>n-c+1</tex>.
'''Пример:'''
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
== Ранги суперпозиций ==
{{Определение
|definition =
'''Ранг суперпозиции''' (англ. ''rank of function composition'') {{---}} это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций.
Суперпозиция <tex>K</tex> ранга <tex>n</tex> обозначается как <tex>K^{n}</tex>
}}
== См. также ==
* [[Определение_булевой_функции|Булевы функции]]
* [[Представление_функции_формулой,_полные_системы_функций|Представление функции формулой, полные системы функций]]
== Ранги суперпозиций Источники информации ==Суперпозиция имеет ранг <tex>n</tex>* Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, если минимальное число подстановок и отождествлений2006, за она может быть получена из исходного множества функций <tex>K<стр 62-63*[http:/tex>, равно <tex>n</tex>ru. Обозначение: <tex>K^{n}<wikipedia.org/tex><br wiki/>Композиция_функций Композиция функций в математике]Например, <tex>K^{1}<*[http://tex> {{mini---}} множество суперпозицийsoft.ru/nstu/diskr/index.php Е.Л. Рабкин, полученных из исходного множества <tex>K</tex> за одну подстановку или отождествлениеЮ.Б. Фарфоровская, <tex>K^{2}</tex> {{---}} множество суперпозицийДискретная математика, полученных из множества <tex>K \cup{K^{1}} </tex> за одну подстановку или отождествление и тГлава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций.дПолные наборы.Базисы]
