Базисы и формы представления логических функций

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

Базисы могут быть избыточными и минимальными. Например, система функций И, Или, НЕ (булев базис, базис Буля) – избыточный базис, так как при удалении из него некоторых функций (функции ИЛИ или функции И) система остаётся полной.

Минимальными базисами являются системы: 1) И, НЕ; 2) ИЛИ, НЕ; 3) И-НЕ (базис Шеффера); 4) ИЛИ-НЕ (базис Пирса). При удалении из таких базисов любой операции они перестают быть полными системами функций.

Одни и те же преобразования логических переменных можно задать в раз­личных формах (базисах). Выбор базиса зависит от простоты реализации той или иной функции с помощью логических операций данной системы функций. Чаще всего используются базисы Шеффера и Пирса, т. к. они содержат только одну операцию, и для реализации сложной схемы нужен только один тип ЛЭ. В развитых сери­ях стандартных интегральных схем (ИС) наряду с базовыми ЛЭ обычно имеется и ряд других, выполняющих другие логические операции.

В табл. 2.9 приведено несколько полезных свойств булевых функций НЕ, И, ИЛИ, формулы перехода между базисами И-НЕ и ИЛИ-НЕ (законы де Моргана), а также формулы перехода от операций импликация, тождественность и сумма по модулю 2 в базис Буля. Все приведённые соотношения можно легко проверить с помощью их таблиц истинности.

Таблица 2.9

№	Формулы булевой алгебры	Формулы в упрощённой записи	Название свойства
			Коммутативность (перемена мест операндов)
			Ассоциативность (последовательность выполнения операций)
			Дистрибутивность (раскрытие скобок)
			Законы исключённого третьего
			Законы тождественных операндов
			Законы поглощения
			Свойства нуля
			Свойства единицы
			Свойство двойного отрицания
			Законы (формулы) де Моргана
			Свойство импликации
			Свойства эквивалентности
			Свойства сложения по модулю два

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

Докажем некоторые из приведённых свойств:

7. ;

;

12. ; ;

13. ; .

Введём понятие терма.

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

Термы, состоящие только из одной переменной, взятой с отрицанием или без него, называются первичными термами.

Ранг терма определяется количеством переменных, входящих в данный терм.

Терм в виде конъюнкции переменных, взятых с отрицанием или без него, называется конъюнктивным термом, конституентой единицы (любой такой терм, принимающий значение 1, автоматически приводит к единичному значению функции) или минтермом (для принятия функцией значения 1 требуется минимальное количество единичных термов, а точнее только один). Под минтермом обычно понимается конъюнктивный терм, содержащий все переменные логической функции.

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

Теорема 2.1. Любая логическая функция может быть представлена как суперпозиция только трёх функций: И, ИЛИ и НЕ.

Доказательство данной теоремы основано на лемме о дизъюнктивном разложении.

Лемма. Любая булева функция f (x ₁ , x ₂ , …, x_m) от m переменных может быть представлена так:

. (2.4)

Действительно, при x_i = 0 правая часть этой формулы принимает значение

;

аналогично при x_i = 1 правая часть

.

Итак, правая часть формулы (2.4) при всех наборах аргументов совпадает с левой, что доказывает справедливость формулы (2.4).

Разложим функцию f (x ₁ , x ₂ , …, x_m) последовательно по переменным x ₁ , x ₂ , …, x_m :

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

Примем для σ {0, 1} x ^σ= при σ = 0 и x ^σ= x при σ = 1. Тогда окончательная форма представления любой булевой функции будет иметь вид:

. (2.5)

Поскольку значения функции на каждом конкретном наборе равны либо 0, либо 1, то в формуле (2.5) останутся только такие термы, которые соответствуют наборам переменных, на которых функция равна единице:

. (2.6)

Представление булевой функции в форме дизъюнкции конъюнктивных термов (конституент единицы) K_i

, , (2.7)

называется дизъюнктивной нормальной формой (ДНФ) этой функции.

Если все конъюнктивные термы в ДНФ являются минтермами, т. е. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ) этой функции. СДНФ называется совершенной, потому что каждый терм в дизъюнкции включает все переменные; дизъюнктивной, потому что главная операция в формуле – дизъюнкция. Понятие “ нормальной формы ” означает однозначный способ записи формулы, реализующей заданную функцию.

С учётом сказанного выше из теоремы 2.1 вытекает следующая теорема.

Теорема 2.2. Любая булева функция (не равная тождественно 0) может быть представлена в СДНФ, причём такое представление единственно.

Пример 2.3. Пусть имеем таблично заданную функцию f (x ₁ , x ₂ , x ₃) (табл. 2.10).

Таблица 2.10

x 1	x 2	x 3	f (x 1 , x 2 , x 3)

На основании формулы (2.6) получаем:

.

Как видно, при составлении СДНФ функции нужно составить дизъюнкцию всех минтермов, при которых функция принимает значение 1.

Представление булевой функции в форме конъюнкции дизъюнктивных термов (конституент нуля) D_i

, , (2.8)

называется конъюнктивной нормальной формой (КНФ) этой функции.

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

Теорема 2.3. Любая булева функция (не равная тождественно 1) может быть представлена в СКНФ, причём такое представление единственно.

Доказательство теоремы может быть проведено аналогично доказательству теоремы 2.1 на основании следующей леммы Шеннона о конъюнктивном разложении.

Лемма Шеннона. Любая булева функция f (x ₁ , x ₂ , …, x_m) от m переменных может быть представлена так:

. (2.9)

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

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

Пример 2.4. Для функции f (x ₁ , x ₂ , x ₃), заданной табл. 2.10, написать её СКНФ.

В отличие от СДНФ, при составлении СКНФ в таблице истинности логической функции нужно смотреть комбинации переменных, при которых функция принимает значение 0, и составить конъюнкцию соответствующих макстермов, но переменные нужно брать с обратной инверсией:

.

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

Пример 2.5. Для функции f (x ₁ , x ₂ , x ₃), заданной табл. 2.10, попробовать перейти от СДНФ к СКНФ.

Используя результат примера 2.3 получим:

Как видно, под общей инверсией получилась СКНФ логической функции, которая является обратной по отношению к функции, полученной в примере 2.4:

,

т. к. содержит все макстермы, которых нет в выражении для СКНФ рассматриваемой функции.

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

1. Используя свойства операций (см. табл. 2.9) тождественность (), сумма по модулю 2 (), импликация (), переходим к операциям И, ИЛИ, НЕ (в базис Буля).

2. Используя свойства отрицания и законы де Моргана (см. табл. 2.9) добиваемся, чтобы операции отрицания относились только к отдельным переменным, а не к целым выражениям.

3. Используя свойства логических операций И и ИЛИ (см. табл. 2.9), получаем нормальную форму (ДНФ или КНФ).

4. При необходимости переходим к совершенным формам (СДНФ или СКНФ). Например, для получения СКНФ часто нужно использовать свойство: .

Пример 2.6. Преобразовать в СКНФ логическую функцию

.

Выполняя по порядку шаги приведённого выше алгоритма, получим:

Используя свойство поглощения, получим:

.

Таким образом, мы получили КНФ функции f (x ₁ , x ₂ , x ₃). Чтобы получить её СКНФ, нужно каждую дизъюнкцию, в которой не хватает какой-либо переменной, повторить дважды – с этой переменной и с её отрицанием:

.