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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
  
Суперпозиция - это ...
+
{{Определение
 +
|definition =
 +
'''Суперпозиция (сложная функция)''' - это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.
 +
}}
 +
 
 
<br><br>
 
<br><br>
Множество всех возможных не повторяющихся суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.<br>
+
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.<br>
  
 
== Способы получения суперпозиций ==
 
== Способы получения суперпозиций ==
Строка 57: Строка 61:
  
 
== Ранги суперпозиций ==
 
== Ранги суперпозиций ==
Суперпозиция имеет ранг <tex>n</tex>, если минимальное число подстановок и отождествлений, за она может быть получена из исходного множества функций, равно <tex>n</tex>.<br>
+
Суперпозиция имеет ранг <tex>n</tex>, если минимальное число подстановок и отождествлений, за она может быть получена из исходного множества функций <tex>K</tex>, равно <tex>n</tex>.<br>
Обозначение: <tex>K^{n}</tex>
+
Обозначение: <tex>K^{n}</tex><br>
 
Например, <tex>K^{1}</tex> - множество функций, полученных из исходного множества <tex>K</tex> за одну подстановку или отождествление, <tex>K^{2}</tex> - множество функций, полученных из множества <tex>K \cup{K^{1}} </tex> за одну подстановку или отождествление и т.д.
 
Например, <tex>K^{1}</tex> - множество функций, полученных из исходного множества <tex>K</tex> за одну подстановку или отождествление, <tex>K^{2}</tex> - множество функций, полученных из множества <tex>K \cup{K^{1}} </tex> за одну подстановку или отождествление и т.д.
  

Версия 00:40, 8 октября 2011

Эта статья находится в разработке!


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




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

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

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

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

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

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

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


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

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

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(x_{i}, ..., x_{i+m-1})[/math]
3. [math] x_{i+m}, ..., x_{n+m-1} [/math] – аргументы функции [math]f[/math] после вставленной функции [math]g[/math]

Пример:
[math] f(a,b) = a \vee b [/math] - первая исходная функция
[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].

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

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


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


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

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

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

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