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

Формулы. Реализация функций формулами

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

Пусть – некоторое подмножество функций из.

а) Базис индукции. Каждая функция называется формулой над.

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

Пример 1. Пусть – множество элементарных функций. Следующие выражения являются формулами над:

1);

2);

3).

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

Пусть – произвольная формула над, тогда формулы, которые использовались для ее построения, будем называть подформулами формулы.

Пусть является формулой над множеством. Возьмем множество функций.

Рассмотрим формулу, которая получается из путем подстановки. Говорят, что формулы и имеют одно и то же строение.

Пример 2. Следующие формулы и имеют одинаковое строение:

1),;

2),.

Строение формулы обозначается через и формула однозначно определяется строением и упорядоченной совокупностью. Поэтому можно писать

.

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

а) Базис индукции. Если, где, то формуле сопоставим функцию.

б) Индуктивный переход. Пусть, где является либо формулой над, либо символом переменной. Сопоставим формуле функцию.

Если функция соответствует формуле, то говорят также, что формула реализует функцию.

Введенное ранее понятие булевой функции не позволяет рассматривать функции от меньшего числа аргументов как функции от большего числа переменных. Для устранения этого недостатка введем следующее определение.

Функция зависит существенным образом от аргумента, если существуют такие значения переменных, что

.

В этом случае называется существенной переменной. В противном случае – несущественной или фиктивной.

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

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

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

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

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

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

.

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

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

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

а) б) в)

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

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

;;.

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

  f

g

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

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

.

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

,,.

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

, или.

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

, или.

Дата добавления: 2014-01-04