Понятие суперпозиции

Функцию , соответствующую формуле , будем называть суперпозицией функций из , а процесс получения функции из – операцией суперпозиции.

Операция суперпозиции включает две простые операции.

1) Операция подстановки переменных. Пусть

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

.

2) Операция бесповторной подстановки функций. Она позволяет строить выражения , где – либо формула, либо переменная из , причем хотя бы одно из отлично от переменной. Обозначим эту операцию буквой .

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

Пример 3. Пусть имеется элемент, работа которого описывается некоторой булевой функцией (рис. 1, а). Результаты применения операции приведены на рис. 1, б (изменение обозначения входов) и рис. 1, в (подача одного и того же сигнала на несколько входов).

а) б) в)

Рис. 1. Иллюстрация применения операции

Пример 4. Выразим операцию отрицания через штрих Шеффера:

; ; .

Пример 5. Пусть работа двух элементовописывается функциями и . Соединим элементы, как показано на рис. 2.

Рис. 2. Иллюстрация применения операции

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

.

Пример 6. Рассмотрим систему функций , где

, , .

Представим в виде суперпозиции этих функций сумму по модулю 2:

, или .

Для стрелки Пирса по аналогии можно записать:

, или .