Изменения

Перейти к: навигация, поиск

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

30 байт добавлено, 06:40, 8 октября 2011
Нет описания правки
}}
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует [[Представление функции формулой, полные системы функций|замыкание]] данного множества функций.<br/>
== Способы получения суперпозиций ==
Рассмотрим две [[Определение булевой функции|булевы функции]]:<br/>функцию <tex>f</tex> от <tex>n</tex> аргументов <tex>f(x_{1}, x_{2}, ..., x_{n})</tex> и<br/>функцию <tex>g</tex> от <tex>m</tex> аргументов <tex>g(x_{1}, x_{2}, ..., x_{m})</tex>.<br/>
Тогда мы можем получить новую функцию из имеющихся двумя способами:
{{Определение
|definition =
'''Подстановкой''' функции <tex>g</tex> в функцию <tex>f</tex> называется замена i-того аргумента функции <tex>f</tex> значением функции <tex>g</tex>:<br/>
<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>
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции g вместо i-того аргумента функции f, результирующая функция h будет принимать аргументы, которые можно разделить на следующие блоки: <br/>
{|
|1. <tex> x_{1}, ..., x_{i-1}</tex>
|}
'''Пример:'''<br/><tex> f(a,b) = a \vee b </tex> {{---}} первая исходная функция<br/><tex> g(a) = \neg a </tex> {{---}} вторая исходная функция<br/><tex> h(a,b) = f(a,g(b)) = a \vee \neg b </tex> {{---}} подстановка функции <tex>g</tex> вместо второго аргумента функции <tex>f</tex><br/>
В данном примере при помощи подстановки мы получили функцию <tex>h(a,b)=a \leftarrow b</tex>.
{{Определение
|definition=
'''Отождествлением переменных''' называется подстановка i-того аргумента функции <tex>f</tex> вместо j-того аргумента:<br/>
<center><tex>h(x_{1}, ..., x_{n-1}) = f(x_{1}, ..., x_{i}, ..., x_{j-1}, x_{i}, x_{j+1}, ..., x_{n-1})</tex></center>
}}
'''Пример:'''<br/><tex> f(a,b) = a \vee b </tex> {{---}} исходная функция<br/><tex> h(a) = a \vee a </tex> {{---}} функция с отождествленными первым и вторым аргументами<br/>
Очевидно, в данном примере мы получили функцию <tex>P_{1}</tex> {{---}} проектор единственного аргумента.
== Ранги суперпозиций ==
Суперпозиция имеет ранг <tex>n</tex>, если минимальное число подстановок и отождествлений, за она может быть получена из исходного множества функций <tex>K</tex>, равно <tex>n</tex>. Обозначение: <tex>K^{n}</tex><br/>
Например, <tex>K^{1}</tex> {{---}} множество суперпозиций, полученных из исходного множества <tex>K</tex> за одну подстановку или отождествление, <tex>K^{2}</tex> {{---}} множество суперпозиций, полученных из множества <tex>K \cup{K^{1}} </tex> за одну подстановку или отождествление и т.д.
39
правок

Навигация