Нормальные формы логических функций

Лекция 1.хх

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

, , (2.7)

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

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

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

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

Пример 3. Пусть имеем таблично заданную функцию f (x1 , x2 , x3) (табл. 10).

Таблица 10

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

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

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

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

, , (2.8)

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

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

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

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

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

. (2.9)

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

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

Пример 4. Для функции f (x1 , x2 , x3), заданной табл. 10, написать её СКНФ.

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

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

Пример 5. Для функции f (x1 , x2 , x3), заданной табл. 10, попробовать перейти от СДНФ к СКНФ.

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

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

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

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

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

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

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

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

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

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

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

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

2.2.6. Минимизация логических функций

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

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

Метод Квайна

Минимизируемая функция представляется в СДНФ, и к ней применяются все возможные операции неполного склеивания

, (2.10)

а затем поглощения

, (2.11)

и эта пара этапов применяется многократно. Таким образом, удаётся снизить ранг термов. Это процедура повторяется до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом.

Заметим, что левую часть уравнения (2.10) сразу можно было минимизировать более простым и очевидным способом:

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

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

Метод карт Карно

Метод карт (таблиц) Карно является более наглядным, менее трудоёмким и надёжным способом минимизации логических функций, но его использование практически ограничено функциями 3-4 переменных, максимум – 5-6 переменных.

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

Таблицы истинности и карты Карно для функций И и ИЛИ двух переменных представлены на рис. 8. В каждую клетку карты записывается значение функции на соответствующем этой клетке наборе значений аргументов.

x	y	f		y			x	y	f		y
0	0	0	x	1	0		0	0	0	x	1	1
0	1	0		0	0		0	1	1		1	0
1	0	0					1	0	1
1	1	1				1	1	1

а) И б) ИЛИ

Рис. 8. Пример карт Карно для функций двух переменных

В карте Карно для функции И только одна 1, поэтому её ни с чем невозможно склеить. В выражении для минимальной функции будет только терм, соответствующий этой 1:

f = x y.

В карте Карно для функции ИЛИ уже три 1 и можно составить две склеивающиеся пары, при этом 1, соответствующая терму xy, используется дважды. В выражении для минимальной функции нужно записать термы для склеиваемых пар, оставляя в них все переменные, которые для этой пары не меняются, и убирая переменные, которые меняют своё значение. Для горизонтальной склейки получим x, а для вертикальной – y, в итоге получим выражение

f = x + y.

На рис. 9 приведены таблицы истинности двух функций трёх переменных (а) и их карты Карно (б и в). Функция f2 отличается от первой тем, что на трёх наборах переменных она не определена (в таблице это обозначено прочерком).

При определении минимальной ДНФ функции используются следующие правила. Все клетки, содержащие 1, объединяются в замкнутые прямоугольные области, которые называются k-кубами, где k = log2K, K – количество 1 в прямоугольной области. При этом каждая область должна представлять собой прямоугольник с числом клеток 2k, где k = 0, 1, 2, 3, … . Для k = 1 прямоугольник называется один-куб и содержит 21 = 2 единицы; для k = 2 прямоугольник содержит 22 = 4 единицы и называется два-куб; при k = 3 область из 23 = 8 единиц называется три-куб; и т. д. Единицы, которые невозможно объединить в прямоугольники, можно назвать ноль-кубами, которые содержат только одну единицу (20 = 1). Как видно, при чётном k области могут иметь форму квадрата (но не обязательно), а при нечётном k – только прямоугольников.

x1	x2	x3	f1	f2	б в
0	0	0	0	–
0	0	1	1	1
0	1	0	0	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	–
1	1	0	1	1
1	1	1	1	–

Рис. 9. Пример карт Карно для функций трёх переменных

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

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

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

Для функции по карте Карно на рис. 9, б находим

поскольку для верхней замкнутой области переменные x1 и x2 имеют значения без инверсий, для нижней x1 имеет значение с инверсией, а x3 – без инверсии.

Неопредёленные значения в карте на рис. 9, в можно доопределить, заменив нулём или единицей. Для данной функции видно, что оба неопределённых значения выгоднее заменить 1. При этом образуются две области, являющиеся различными видами 2-кубов. Тогда выражение для минимальной ДНФ функции будет следующим:

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

Карты Карно можно рисовать разными способами (рис. 10).

	x2		x2x3	x2

x1		x1
	x3

а б

	00	01	11	10
0
1

Рис. 10. Разные способы изображения карт Карно
для функции 3 переменных

Но самыми удобными вариантами карт Карно для функций 2-4 переменных являются показанные на рис. 11 таблицы, т. к. в них для каждой ячейки показаны все переменные в прямом или инверсном виде.

а б

Рис. 11. Наиболее удобное изображение карт Карно
для функций 3 (а) и 4 (б) переменных

Для функций 5 и 6 переменных больше подходит способ, показанный на рис. 10, в.

	000	010	011	010	110	111	101	100
00
01
11
10

Рис. 12. Изображение карты Карно для функции 5 переменных

	000	010	011	010	110	111	101	100
000
001
011
010
110
111
101
100

Рис. 13. Изображение карты Карно для функции 6 переменных

Нормальные формы логических функций