Тема 6 Минимизация булевых функций

6.1 Сокращенная и тупиковая ДНФ

6.2 Метод импликантных матриц

Цель данного раздела – изложение основных методов построения минимальных дизъюнктивно нормальных форм.

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

Дизъюнктивная нормальная форма называется Минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.

Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

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

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

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется Элементарной, если при .

Число R называется Рангом элементарной конъюнкции. В случае r=0 конъюнкция называется Пустой и Полагается равной 1.

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

Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.

Обозначим через множество всех точек , где . Ясно, что - множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции Подмножество Из , определенное следующим образом:

Например, функции

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Соответствует подмножество

Вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции Соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем утверждение 2. Пусть

Отсюда .

Тогда .

А это значит, что .

Отсюда .

Пусть ДНФ, где - элементарные конъюнкции. Подмножество называется интервалом R-го ранга, если оно соответствует элементарной конъюнкции К R-го ранга. Как показано выше, . Итак, с каждой ДНФ функции F связано покрытие такими интервалами , что .

Пусть - ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

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

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

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

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

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

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и - все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной ДНФ.

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

Теорема 1. Если в произвольной ДНФ булевой функции F произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получиться сокращенная ДНФ функции F.

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

Пример 2. Найти сокращенную ДНФ для функции . Применяя правило обобщенного склеивания, получаем: .

Затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

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

Пример 3. Найти сокращенную ДНФ для функции

После раскрытия скобок с помощью дистрибутивного закона, получаем:

.

Так как , , то имеем:

.

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

.

Рассмотрим табличный метод построения сокращенной ДНФ. Этот метод основан на составлении прямоугольной таблицы (минимизирующей карты).

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

Z X y	0	1
00
01
11
10

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0
0 1
1 1
1 0

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

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

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0	1	1	0	1
0 1	0	1	1	0
1 1	1	1	1	0
1 0	0	1	0	0

В данной таблице объединены клетки в максимальные интервалы

.

Этим интервалам соответствуют элементарные конъюнкции

, , , ,

Следовательно, сокращенная ДНФ для данной функции имеет вид:

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

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

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

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

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

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

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

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

Элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т. е. .

Ввиду этого введем следующее определение.

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

Теорема 5. Всякая минимальная ДНФ является тупиковой.

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

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

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

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции F все такие элементарные конъюнкции , что ;

3) составляем выражение вида

(*)

4) применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем .

Теперь каждая ДНФ является тупиковой ДНФ функции .

Рассмотрим работу данного алгоритма на следующем примере.

Пример 5. Рассмотрим булеву функцию, заданную следующей таблицей:

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Найдем сокращенную ДНФ данной функции по методу Нельсона. Для этого составим КНФ данной функции .

Применяя законы дистрибутивности, получаем:

.

Обозначим , , , , , .

Составляем выражение (*)

Преобразуем данное выражение к виду

= =.

Таким образом, имеет шесть тупиковых ДНФ:

Две из них и являются минимальными.

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

			…		…
…
				+
…

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением I-строки и J-столбца отметим крестиком.

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

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

.

Из предыдущего примера следует, что сокращенная ДНФ для данной функции . Очевидно, что

.

Строим импликантную матрицу

	(0,0,1)	(0,1,0)	(0,1,1)	(1,0,0)	(1,0,1)	(1,1,0)
				+	+
				+		+
		+	+
		+				+
	+		+
	+				+

Отсюда видно, что данная функция имеет два минимальные ДНФ:

; .

Вопросы для самоконтроля.

1. Дайте определение основных логических операций булевой алгебры.

2. Дайте определение булевой функции.

3. Что такое таблицы истинности булевой функции?

4. Каково число булевых функций от переменных?

5. Какие булевы функции называются элементарными?

6. Дайте определение формулы алгебры логики.

7. Какие формулы алгебры логики называются равносильными?

8. Сформулируйте законы алгебры логики.

9. Какая формула алгебры логики называется двойственной к данной формуле алгебры логики?

10. Сформулируйте принцип двойственности.

11. Сформулируйте теорему о разложении и следствие из нее.

12. Дайте определение СДНФ.

13. Приведите алгоритмы построения СДНФ.

14. Дайте определение СКНФ.

15. Приведите алгоритмы построения СКНФ.

16. Дайте определение ДНФ.

17. Как найти ДНФ?

18. Дайте определение КНФ.

19. Как найти КНФ?

20. Какая формула алгебры логики называется тождественно истинной?

21. Какая формула алгебры логики называется тождественно ложной?

22. Какая формула алгебры логики называется выполнимой?

23. Что называется проблемой разрешимости?

24. Сформулируйте методы решения проблемы разрешения.

25. Что называется алгеброй Жегалкина?

26. Сформулируйте законы алгебры Жегалкина.

27. Что называется полиномом Жегалкина?

28. Сформулируйте алгоритмы построения полиномов Жегалкина.

29. Какая система булевых функций называется полной?

30. Что называется замыканием множества булевых функций?

31. Какой класс булевых функций называется замкнутым?

32. Дайте определение пяти важнейших замкнутых классов.

33. Сформулируйте теорему о полноте.

34. Сформулируйте алгоритм Поста.

35. Какая система булевых функций называется несократимой?

36. Каково максимальное возможное число функций в несократимой полной системе булевых функций?

37. Что такое релейно-контактная схема?

38. Почему любую булеву функцию можно изобразить в виде релейно-контактной схемы?

39. В чем состоит проблема анализа релейно-контактных схем?

40. В чем состоит проблема синтеза релейно-контактных схем?

41. Что такое логические элементы?

42. Приведите геометрическое изображение логических элементов.

43. Что такое логическая схема?

44. Что Вы понимаете под двоичным сумматором?

45. Какая ДНФ называется минимальной?

46. Чему равно число всех ДНФ от переменных?

47. Сформулируйте тривиальный алгоритм построения МДНФ?

48. Что такое элементарная конъюнкция?

49. Что такое ранг элементарной конъюнкции?

50. Что называется интервалом элементарной конъюнкции?

51. Какой интервал называется максимальным?

52. Что называется областью истинности булевой функции?

53. Сформулируйте теорему об области истинности булевой функции.

54. Что называется покрытием области истинности булевой функции?

55. Какое число элементов содержится в интервале?

56. Какая ДНФ называется сокращенной?

57. В чем состоит геометрическая интерпретация задачи минимизации булевой функции?

58. Сформулируйте геометрический метод построения сокращенной ДНФ.

59. Сформулируйте метод Нельсона построения сокращенной ДНФ.

60. Сформулируйте метод Блейка построения сокращенной ДНФ.

61. Сформулируйте метод карт Карно построения сокращенной ДНФ.

62. Какая связь между МДНФ и сокращенной ДНФ?

63. Какое покрытие области истинности булевой функции называется неприводимым.

64. Какая ДНФ называется тупиковой?

65. Какая связь между МДНФ и тупиковой ДНФ?

66. Сформулируйте алгоритм построения всех тупиковых ДНФ.

67. Как строится импликантная матрица?

68. Сформулируйте алгоритм нахождения МДНФ методом импликантных матриц.

< Предыдущая		Следующая >