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

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

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

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

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

(2.1)

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

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

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

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

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

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

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

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

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

(2.2)

Доказательство. Рассмотрим произвольный набор значений переменных (a₁, ... , a_n) и покажем, что левая и правая части соотношения (2.2) принимают на нем одно и то же значение. Левая часть дает f(a₁,..., a_k,a _k+1 ,..., a_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) и отмечаем в ней все строки (s₁, ... , s_n), в которых f(s₁, ... , s_n) =1, для каждой такой строки образуем логическое произведение , а затем соединяем все полученные конъюнкции знаком дизъюнкции.

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

Имеем:

. ð

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

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

* тогда и только тогда, когда x = s;

* обращается в 0 только на наборе (x₁, ... , x_n) = (s₁, ... , s_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.

2.5. Функциональная полнота систем функций алгебры
логики

Выше мы видели, что всякая функция алгебры логики может быть выражена в виде формулы через элементарные функции , xÙy, xÚy. В связи с этим возникает вопрос, какими свойствами должна обладать система функций, чтобы через функции этой системы можно было выразить произвольную функцию алгебры логики? Мы собираемся дать достаточно исчерпывающий ответ на этот вопрос и показать, что таким свойством обладают и другие системы функций.

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

Замена переменных.

Пусть f(x₁, x₂, ... , x_n) - заданная функция алгебры логики. Будем говорить, что функция j(y₁, y₂, ... , y_n) получена операцией замены переменных из функции f(x₁, x₂, ... , x_n), если осуществлена подстановка переменных

,

то есть вместо каждого вхождения переменой x₁подставляется переменная y₁, вместо каждого вхождения переменой x₂подставляется переменная y₂, ... , вместо каждого вхождения переменой x_nподставляется переменная y_n , при этом y_i не обязана отличаться от y_kпри i¹k . Очевидно, что замена переменных включает в себя переименование переменных, перестановку переменных и отождествление переменных.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: