Разложение функций алгебры логики по переменным

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

Чтобы иметь возможность единообразно записывать переменные с отрицанием и без отрицания введем следующее обозначение:

Легко видеть, что x^ = 1 тогда и только тогда, когда x = , то есть значение “основания” равно значению “показателя”.

Лемма 2.2. (О разложении функции по одной переменной). Пусть f(x₁ , ... , x_n) - произвольная функция алгебры логики, тогда справедливо следующее представление f в форме разложения по переменной x₁ :

(2.1)

Доказательство. Отметим прежде всего, что представление (2.1), естественно, справедливо для произвольной переменной x_i из множества переменных функции f. Для доказательства рассмотрим произвольный набор значений переменных (₁, ... , _n) и покажем, что левая и правая части соотношения (2.1) принимают на нем одно и то же значение.

Рассмотрим набор значений переменных (1, ₂, ... , _n). Левая часть (2.1) принимает на этом наборе значение f(1, ₂ ,..., _n ), а правая часть - значение 1f(1, ₂, ... , _n )  0f(0, ₂, ... , _n ) = f (1, ₂, ... , _n ). Таким образом, на наборах (1, ₂, ... , _n) левая и правая части (2.1) принимают одинаковые значения.

Рассмотрим набор значений переменных (0, ₂, ... , _n). Левая часть (2.1) принимает на этом наборе значение f(0, ₂ ,..., _n ), а правая часть - значение 0f(1, ₂, ... , _n )  1f (0, ₂, ... , _n ) = f (0, ₂, ... , _n ). Таким образом, на наборах (0, ₂, ... , _n) левая и правая части (2.1) принимают одинаковые значения.

Тем самым мы доказали, что левая и правая части соотношения (2.1) принимают одинаковые значения на всех наборах (₁, ... , _n). 

Лемма 2.3. Конъюнкция (произведение) тогда и только тогда, когда .

Доказательство. Произведение (конъюнкция) равно 1 тогда и только тогда, когда каждый сомножитель равен 1, но x^ = 1 тогда и только тогда, когда x = . 

В дальнейшем будем употреблять следующие обозначения:

Эти записи имеют смысл и при k = 1.

Теорема 2.4. (О разложении функции по нескольким переменным). Пусть f(x₁ , ... ,x_n) - произвольная функция алгебры логики. Тогда ее можно представить в следующей форме:

(2.2)

Доказательство. Рассмотрим произвольный набор значений переменных (₁, ... , _n) и покажем, что левая и правая части соотношения (2.2) принимают на нем одно и то же значение. Левая часть дает f(___k+1 ,_n). Правая часть дает



Представление (2.2) называется дизъюнктивным разложением функции по k переменным.

Пример. Для k = 2 разложение в дизъюнктивную форму имеет вид:

Выпишем такое разложение для конкретной функции трех переменных по переменным x₂ и x₃:

В качестве следствий получаем два специальных разложения.

1. Разложение по одной переменной, выписанное ранее.

2. Разложение по всем n переменным.

Если k = n , то получаем разложение

Оно может быть преобразовано при f(x₁, ... , x_n)  0 следующим образом:

Итак, в этом случае разложение имеет вид:

Это разложение называется совершенной дизъюнктивной нормальной формой (совершенная ДНФ.). Оно определено для любой функции f, не равной константе 0.

Теорема 2.5. Произвольную функцию алгебры логики можно выразить формулой при помощи операций , ,  , причем операция  применяется только к переменным.

Доказательство.

1. Пусть f(x₁, ... , x_n) = 0. Тогда, очевидно,

f(x₁, ... , x_n) = x₁   x₁ .

2. Пусть f(x₁, ... , x_n)  0. Представим ее в форме совершенной ДНФ.:

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

Итак, оказалось, что любую булеву функцию можно выразить формулой над множеством операций {, ,  }, состоящим из трех функций: отрицания, конъюнкции и дизъюнкции. Данная теорема носит конструктивный характер, так как она позволяет для каждой функции построить реализующую ее формулу (совершенную ДНФ). А именно, берем таблицу для функции f(x₁, ... , x_n) (f 0) и отмечаем в ней все строки (₁, ... , _n), в которых f(₁, ... , _n) =1, для каждой такой строки образуем логическое произведение , а затем соединяем все полученные конъюнкции знаком дизъюнкции.

Пример. Построить совершенную ДНФ для функции, заданной таблицей:

x1 x2 x3	f(x1, x2, x3)	x1 x2 x3	f(x1, x2, x3)
0 0 0	1	1 0 0	0
0 0 1	1	1 0 1	1
0 1 0	0	1 1 0	0
0 1 1	0	1 1 1	1

Имеем:

. 

Если в таблице значений функции много 1 и мало 0, то целесообразно строить функцию по-другому. Совершенная ДНФ есть выражение типа “ &”, то есть логическая сумма произведений . Спрашивается нельзя ли для функции алгебры логики получить разложение типа “&  “?

Аналогично только что проведенным доказательствам легко получить, что:

• тогда и только тогда, когда x = ;

• обращается в 0 только на наборе (x₁, ... , x_n) = (₁, ... , _n);

• имеет место следующее разложение в конъюнктивную нормальную форму по одной переменной

f (x₁ ,..., x_n ) = (x₁ f (0, x₂ ,..., x_n )) ( f (1, x₂ , ... , x_n ))

• имеет место следующее представление функции в виде совершенной конъюнктивной нормальной формы (совершенная КНФ) для f 1:

.

Использование совершенной КНФ позволяет упростить запись формулы для функции, таблица значений которой содержит мало нулей. 

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

.

Последовательное применение такого разложения ко всем переменным позволяет выразить произвольную функцию алгебры логики через элементарные функции , x+y, xy или, используя соотношение , лишь через функции x+y, xy, 1.