Полные системы булевых функций (стр. 3 из 6)
 |  |  |
 |  |  |
 |  |  |
 |  |
В этом списке имеется два одночлена X1X3 и Х2Х3Х4, которые не поглощают других одночленов из этого списка, следовательно, являются простыми импликантами. Поэтому сокращенная ДНФ имеет вид
,οна же является и минимальной
В общем случае процесс построения минимальных ДНФ может быть охарактеризован следующей схемой.
Рис. 1
Сначала получают сокращенную ДНФ. Далее однозначный процесс переходит в ветвящийся процесс построения всех тупиковых ДНФ и, наконец, из тупиковых ДНФ выделяются минимальные. Самым трудоемким этапом этого процесса является построение тупиковых ДНФ. Его можно немного упростить, заранее удалив часть членов сокращенной ДНФ, не участвующих в построении тупиковых ДНФ и тем самым сократить количество просматриваемых подмножеств
Проблема минимизации является важнейшей для технических приложений логических функций и ей посвящено много работ, в которых предложены различные алгоритмы решения этой задачи. Рассмотрим подробнее один из таких алгоритмов.
3. Алгоритм Квайна и Мак-Класки минимизации булевой функции
Этот алгоритм используется наиболее часто, так как он может быть реализован на ЭВМ, и при его применении практически отсутствуют ограничения на число переменных. Минимизацию функции в этом методе рекомендуется выполнить в следующей последовательности.
1. Привести булеву функцию к СДНФ.
2. В СДНФ произвести все возможные склеивания Полученная после этого ДНФ является сокращённой, но среди простых импликант могут оказаться лишние.
3. Перейти от сокращённой ДНФ к минимальной, т.е. исключить лишние импликанты. Для этого рекомендуется воспользоваться импликантой матрицей, в которой каждой строке соответствует простая импликанта, а каждому столбцу – конституента ( элементарная конъюнкция, содержащая все переменные) СДНФ заданной функции Эта матрица заполняется следующим образом под конституентами, в которые входит данная простая импликанта, ставится метка "1" Для нахождения минимального покрытия функции необходимо удалить из таблицы некоторые лишние простые импликанты С этой целью реализуется следующий алгоритм.
1. Выделение ядра Квайна. Если в каком-либо столбце импликантной матрицы имеется только одна 1, то импликанта, находящаяся в соответствующем столбце, не является лишней и должна быть включена в минимальное покрытие функции. Такие импликанты называются существенными, а их совокупность называют ядром Квайна.
Вычёркивая строки, в которых находятся существенные импликанты, и столбцы, покрываемые этими импликантами, получаем матрицу меньших размеров Если в ней имеются столбцы, содержащие по одной 1, то операцию выделения существенных импликант следует повторить.
2 Сжатие по столбцам или строкам. Из матрицы вычёркивается тот столбец, в который полностью входит какой-либо другой столбец и та строка, которая полностью покрывается другой.
После выполнения всех указанных действий в матрице останутся только те простые импликанты, которые входят в минимальное покрытие функции. Соединив эти импликанты и найденные ранее существенные импликанты знаками дизъюнкций, получим минимальную ДНФ заданной функции.
Пример 7 Минимизировать булеву функцию
.Решение. Функция задана в ДНФ, поэтому займемся сразу отысканием простых импликант, проводя операцию склеивания. Для этого представим каждую элементарную конъюнкцию двоичным набором, ставя на k-ом месте 0, если Хk входит с отрицанием, 1 – если без отрицания и знак "–", если эта переменная не входит в конъюнкцию Тогда функция примет вид:
.Разобьем эти наборы на классы, в каждом из которых содержатся наборы с одинаковым числом единиц и расположим их в порядке возрастания суммы всех чисел набора (рис 2 а)
Для исключения переменных по правилу склеивания сравним все наборы всех смежных классов. Если при этом какая-либо переменная исключается, то в разряд, соответствующий этой переменной, записываем прочерк. Например, двоичные наборы 0100 и 0101 образуют набор 010–. Все полученные наборы опять разбиваем на классы. Объединяем снова наборы из двух смежных классов, причём сравнению подлежат только те, у которых прочерк находится в одном и том же разряде, получаем новый набор импликант (рис. 2 в). Нетрудно убедиться, что дальнейшее объединение наборов невозможно, следовательно, все полученные импликанты – простые.
Построим импликантную матрицу (табл. 3 а). Выделяя столбцы, содержащие по одной единице, находим существенные импликанты, образующие ядро Квайна: 0–0– –0–0. При этом первая из них является существенной для 0000, 0001, 0100, 0101, а вторая – для 0000, 0010, 1000, 1010. Вычёркивая столбцы с этими конституентами и строки с существенными импликантами, получим табл. 3 б. В этой таблице нет столбцов, содержащих только одну единицу, следовательно существенных импликант в этой таблице нет и ядро Квайна состоит из двух импликант, найденных выше: 0–0– и –0–0.
Переходим к операциям сжатая по строкам и столбцам. Вторая строка табл. 3 б поглощает первую, а четвёртая – третью, поэтому первую и третью строки можно вычеркнуть (табл. 3 в).
В табл. 3 в первый столбец полностью входит в четвёртый, а второй – в третий, После вычеркивания четвертого и третьего столбцов таблица принимает вид 3 г. Из этой таблицы видно, что импликанта 111– является лишней, так как не содержит единиц ни в одном столбце, а две остальные входят в минимальное покрытие. Таким образом, заданная функция имеет четыре простых импликанты: 0–0–, –0–0, 1––0 и –111. Объединяя их знаком дизъюнкции, получаем минимальную ДНФ в виде
.Алгоритм Квайна позволяет получать минимальные дизъюнктивные нормальные формы заданных функций Однако в ряде случаев минимальные конъюнктивные нормальные выражения оказываются "меньше" дизъюнктивных, поэтому при решении задач минимизации желательно получить не только дизъюнктивные, но и конъюнктивные нормальные формулы и выбрать из них наименьшее. Методы получения минимальных конъюнктивных выражений двойственны рассмотренным выше методам и мы не будем на них останавливаться.
4. Геометрическое представление логических функций
Обозначим через Еn множество всех наборов (α1,..., αη), состоящих из чисел ноль и единица. Множество Еn называется n-мерным кубом, а набор (α1, ..., αη) - вершинами куба.
Пусть σ1, ..., σr- фиксированный набор чисел из 0 и 1. Множество всех вершин (α1,..., αη) куба Еn таких, что αi1 = σ1, αi2 = σ2, ... , αir = σr, 1 < i1 < i2 < ...< ir, называется (n – r) - мерной гранью. Очевидно, что (n – r)-мерная грань является (n – r) - подкубом куба Еn.
Например, в трехмерном кубе Е3 наборы (0,0,1) и (0,0,0) образуют одномерную ( n = 3, r = 2) грань (ребро), а наборы (1,0,0), (1,0,1), (1,1,0), (1,1,1) - двухмерную грань.
Пусть f(X1,X2,…,Xn) - произвольная булева функция. Ей сопоставляется в соответствие подмножество Νf вершин куба Еn, таких что (α1, ..., αη)
Nf тогда и только тогда, когда f(α1, ..., αη) = l Очевидно, что по подмножеству Nf исходная функция f(X1, X2., ... , Χn) восстанавливается однозначно. Таким образом геометрический способ задания булевой функции заключается в задании множества вершин n-мерного куба Еn, в которых данная функция истинна.Пример 8. Пусть функция f(X1, X2, Х3) задана табл. 4. Составить для нее множество Nf.
Таблица 4
| X1 | X2 | X3 | f(X1, X2, Х3) |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Решение. Очевидно, что Nf = {(0,0,0), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}. Множество Nf изображено на рис. 3.