Изменения

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

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

145 байт убрано, 06:47, 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> {{---}} проектор единственного аргумента.
1302
правки

Навигация