Суперпозиции — различия между версиями

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

Версия 18:53, 2 января 2020

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

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

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

Рассмотрим две булевы функции: функцию [math]f[/math] от [math]n[/math] аргументов [math]f(x_{1}, x_{2}, \ldots, x_{n})[/math] и функцию [math]g[/math] от [math]m[/math] аргументов [math]g(y_{1}, y_{2}, \ldots, 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}, \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})[/math]


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

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

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


См. также

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