Суперпозиции — различия между версиями
Lukyanov (обсуждение | вклад) |
Lukyanov (обсуждение | вклад) (исправил баги) |
||
Строка 8: | Строка 8: | ||
Рассмотрим две [[Определение булевой функции|булевы функции]]: | Рассмотрим две [[Определение булевой функции|булевы функции]]: | ||
функцию <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}, ..., x_{n})</tex> и | ||
− | функцию <tex>g</tex> от <tex>m</tex> аргументов <tex>g( | + | функцию <tex>g</tex> от <tex>m</tex> аргументов <tex>g(y_{1}, y_{2}, ..., y_{m})</tex>. |
Строка 33: | Строка 33: | ||
|- | |- | ||
|2. <tex> x_{i}, ..., x_{i+m-1} </tex> | |2. <tex> x_{i}, ..., x_{i+m-1} </tex> | ||
− | |– используются как аргументы для вставленной функции <tex>g( | + | |– используются как аргументы для вставленной функции <tex>g(y_{1}, ..., y_{m})</tex> |
|- | |- | ||
|3. <tex> x_{i+m}, ..., x_{n+m-1} </tex> | |3. <tex> x_{i+m}, ..., x_{n+m-1} </tex> | ||
Строка 52: | Строка 52: | ||
'''Отождествлением переменных''' называется подстановка i-того аргумента функции <tex>f</tex> вместо j-того аргумента: | '''Отождествлением переменных''' называется подстановка i-того аргумента функции <tex>f</tex> вместо j-того аргумента: | ||
− | <center><tex>h(x_{1}, ..., x_{n-1}) = f(x_{1}, ..., x_{i}, ..., x_{j-1}, x_{i}, x_{j+1}, ..., x_{n | + | <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> |
}} | }} | ||
Версия 19:00, 8 октября 2011
Определение: |
Суперпозиция (сложная функция) — это функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных. |
Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.
Содержание
Способы получения суперпозиций
Рассмотрим две булевы функции: функцию от аргументов и функцию от аргументов .
Тогда мы можем получить новую функцию из имеющихся двумя способами:
- Подстановкой одной функции в качестве некоторого аргумента для другой;
- Отождествлением аргументов функций.
Подстановка одной функции в другую
Определение: |
Подстановкой функции | в функцию называется замена i-того аргумента функции значением функции :
Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.
При подстановке функции g вместо i-того аргумента функции f, результирующая функция h будет принимать аргументы, которые можно разделить на следующие блоки:
1. | – аргументы функции | до вставленной функции
2. | – используются как аргументы для вставленной функции |
3. | – аргументы функции | после вставленной функции
Пример:
Исходные функции:
— подстановка функции вместо второго аргумента функции . В данном примере при помощи подстановки мы получили функцию .
Отождествление переменных
Определение: |
Отождествлением переменных называется подстановка i-того аргумента функции | вместо j-того аргумента:
Пример:
— исходная функция
— функция с отождествленными первым и вторым аргументами
Очевидно, в данном примере мы получили функцию
— проектор единственного аргумента.
Ранги суперпозиций
Суперпозиция имеет ранг
, если минимальное число подстановок и отождествлений, за она может быть получена из исходного множества функций , равно . Обозначение:Например,
— множество суперпозиций, полученных из исходного множества за одну подстановку или отождествление, — множество суперпозиций, полученных из множества за одну подстановку или отождествление и т.д.