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

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

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

если f — обозначение некоторой функции от m переменных из класса K и Ф₁, ..., Ф_m — формулы над K, то запись Ф = f(Ф₁, ..., Ф_m) есть формула над K.

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

Установим теперь связь между формулами и двоичными функциями. Сначала заметим, что для произвольного набора значений переменных, входящих в формулу, можно, используя индуктивный характер определения, вычислять ее значение на этом наборе. Действительно, если значение формул Ф₁, ..., Ф_m, входящих в формулу Ф = f(Ф₁, ..., Ф_m), уже подсчитаны и равны соответственно b₁, ..., b_m, b_i Î F₂, то значение формулы Ф равно значению функции f(b₁, ..., b_m). Поставим в соответствие каждой формуле Ф(x₁, ..., x_n) функцию f_Ф(x₁, ..., x_n), зависящую от тех же переменных, значения которой при всех значениях переменных совпадают со значениями формулы Ф(x₁, ..., x_n).

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

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

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

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

x₁, , , , ... .

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

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

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

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

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

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

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

Л е к ц и я 2