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

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

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

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

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

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

1) ;

2) ;

3) .

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

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

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

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

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

1) , ;

2) , .

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

.

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

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

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

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

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

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

.

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

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

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