01.3. Задание двоичных функций формулами

Пусть имеется некоторый класс (т. е. множество) двоичных функций K. Он может быть как конечным, так и бесконечным. Обозначим через F1, F2, ..., входящие в него функции, и пусть X = {X1, X2, ...} — множество двоичных переменных. Дадим индуктивное определение Формулы над классом K:

Символ переменной XI, XI ΠX есть формула над K;

Если F — обозначение некоторой функции от M переменных из класса K и Ф1, ..., ФM — формулы над K, то запись Ф = F(Ф1, ..., ФM) есть формула над K.

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

Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивный характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф1, ..., ФM, входящих в формулу Ф = F(Ф1, ..., ФM), уже подсчитаны и равны соответственно B1, ..., BM, BI ΠF2, то значение формулы Ф равно значению функции F(B1, ..., BM). Поставим в соответствие каждой формуле Ф(X1, ..., XN) функцию FФ(X1, ..., XN), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(X1, ..., XN).

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

X1	F1
0	0
1	1

X1	X2	F
0	0	0
0	1	0
1	0	1
1	1	1

X1	X2	X3	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

И т. д. Поэтому естественным оказывается следующее определение.

Определение 1.6. Под Функциями, реализуемыми формулой Ф понимается функция FФ, а также все функции, которые получаются из FФ удалением или добавлением несущественных переменных.

С другой стороны, одной функции может соответствовать множество различных формул. Например, рассматриваемые выше функции могут быть заданы любой из следующих формул:

X1, , , , ... .

Чтобы учесть эту неоднозначность, введем понятие равносильности формул.

Определение 1.7. Две формулы Ф1 и Ф2 называются Равносильными (обозначается Ф1 = Ф2), если они реализуют одинаковые множества функций.

Замечание 1.8. Заметим, что для проверки равносильности формул Ф1 и Ф2 достаточно добавить к функции те переменные, которые входят в Ф2, но не входят в формулу Ф1, а к функции добавить переменные из Ф1, которые не входят в формулу Ф2, а затем сравнить таблицы полученных функций.

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

Определение 1.9. Подформулой формулы Ф называется сама формула Ф; Подформулой формулы F(Ф1, ..., ФM) называется она сама, а также все подформулы формул Ф1, ..., ФM.

Свойство 1.10. Если Ф1 — подформула формулы Ф, и Ф1 равносильна Ф2, то подформула Ф¢, полученная из Ф путем замены Ф1 на Ф2 будет равносильна формуле Ф.

Свойство 1.11. Если формулы Ф1 и Ф2 равносильны, то, подставив одновременно в них вместо некоторых переменных любые формулы, получим в результате также равносильные формулы.

< Предыдущая		Следующая >