Полные системы булевых функций (стр. 2 из 6)

f (X₁,X₂,..., X_n) =

,

где

.

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

Например, из табл. 1 следует, что f₂ = X₁ÙX₂ и f₈ = X₁ÚX₂ – функции, сохраняющие константу 0; f₁₀ = X₁↔X₂ – функция, не сохраняющая константу 0, но сохраняющая константу 1; f₇ = X₁

X₂ - несамодвойственная функция; f₂, f_g – монотонные функции; f₁₄ = X₁→X₂ – немонотонная функция, так как монотонность нарушается на набоpax (0, 0) и (1, 0); f₃ - нелинейная функция, так как соответствующий ей многочлен Жегалкина X₁ + X₂ + X₁X₂ – нелинеен.

Теорема Поста. Система D = {f₁, f₂, ... f_m} булевых функций является полной тогда и только тогда, когда среди функций этой системы существуют: функция, не сохраняющая константу 0, функция, не сохраняющая константу 1, а также нелинейная, несамодвойственная и немонотонная функции.

Пример 2. Доказать полноту системы

.

Решение. Пусть K₀ – класс функций, сохраняющих константу 0; К₁ – класс функций, сохраняющих константу 1; К_л, K_c, К_м – классы линейных, самодвойственных и монотонных функций соответственно.

Составим таблицу Поста следующего вида.

Таблица 2

№	φi	K0	К1	Кл	Kc	Км
1	X1 X2	+	–	+	–	–
2	X1 Ú X2	+	+	–	–	+
3	1	–	+	+	–	–

Знак "+", стоящий на пересечении i- й строки и j-гo столбца этой таблицы, показывает, что функция φ_i – принадлежит соответствующему классу, записанному в j-ом столбце,

Из табл. 1 видим, что φ₁ = f₇ не сохраняет константу 1 и не является монотонной, φ₂ = f₈ – нелинейная и несамодвойственная функция, φ₃ = f₁₆ не сохраняет константу 0. Следовательно, все условия теоремы Поста выполнены, и заданная система

является полной.

Пример 3. Доказать, что система {|} является базисом.

Решение. Рассматриваемая система состоит из одной функции f₁₅ (функции Шеффера). Из табл. 1 видим, что f₁₅ – функция, не сохраняющая 0 и 1, немонотонная (монотонность нарушается на наборах (1, 0) и (1, 1), несамодвойственная, так как

, a двойственная функция нелинейная, так как многочлен Жегалкина для этой функции имеет вид: 1 + X₁X₂. Следовательно, система {f₁₅} = {|} удовлетворяет всем условиям теоремы Поста и является базисом.

Исследуя различные наборы функций, можно показать, что для множества булевых функций двух переменных существуют 17 различных базисов, в каждом из которых нельзя вычеркнуть ни одну функцию без потери полноты. Наиболее распространенными из них являются конъюнктивный базис Буля

, дизъюнктивный базис Буля . импликативныи базис . базис Шеффера {|}, базис Жегалкина .

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

2. Сокращенные и тупиковые дизъюнктивные нормальные формы

Известно [4], что всякую булеву функцию можно записать, причем единственным образом, в ДНФ, то есть в виде дизъюнкции элементарных конъюнкций (суммы произведений). В связи с этим можно ставить вопрос об отыскании для заданной функций такой ДНФ, которая была бы наиболее простой по сравнению с ее другими ДНФ.

ДНФ называется минимальной, если она содержит по сравнению с другими эквивалентными ей формами минимальное количество букв (при подсчете учитывается каждое вхождение буквы в формулу).

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

Элементарную конъюнкцию φ_к назовем импликантой булевой функции f, если не существует такого двоичного набора переменных, при котором функция φ_к принимает значение 1, а функция f – значение 0, то ecть φ_k Ú f = f.

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

Пример 4. Проверить, являются ли одночлены

и импликантами булевой функции

.

Решение. Полагая в первом случае Х₁ = 1, X₂ = 1, имеем φ₁ = l и φ₂ = l и

,

следовательно, φ₂ – импликанта заданной функции.

Во втором случае полагаем X₁ = 0, X₂ = l. Тогда

φ₂ = 1, а

,

следовательно, φ₂ не является импликантой функции f.

Справедливы следующие утверждения:

1. Если

импликанты булевой функции f, то и также являются ее импликантами.

2. Если функция

есть импликанта функции f, то функции также являются импликантами функции f.

Элементарная конъюнкция, входящая в ДНФ булевой функции, называется ее простой импликантой, если никакая ее часть не является импликантой этой функции.

Сокращенной ДНФ данной булевой функции называется ее ДНФ, составленная только из простых импликант.

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

.

Например,

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

Сокращенная ДНФ, из которой удалены все лишние импликанты, называется тупиковой ДНФ

Исключение лишних импликант из сокращенной ДНФ проводится с помощью правила поглощения: дизъюнкцию двух элементарных конъюнкций, из которых одна полностью содержится и другой, можно заменить конъюнкцией, имеющей меньший ранг, например, X Ú XF = X,

.

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

Пример 5. Упростить булеву функцию

.

Решение. Эта функция содержит только простые импликанты, т. е. является сокращенной Однако она избыточна, так как одночлен Х₁X₂ можно удалить, не разрушая равносильности. После этого получим функцию:

.

Пример 6. Найти минимальную ДНФ для функции

.

Решение. Склеивая первый и третий одночлены по переменкой Х₂, получим Х₁X₃X₄. Из первого и четвертого, а затем из второго и третьего слагаемых после склеивания получим соответственно X₁X₂X₃,

и т. д. Окончательный список импликант имеет вид