Минимизация логических функций методом Квайна

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

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

Рис. 1

 

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

Для выполнения операции склеивания в выражении функции выяв­ляются пары членов вида и , различающихся лишь тем, что один из аргументов в одном из членов представлен без инверсии, а в другом - с инверсией. Затем проводится склеивание таких пар чле­нов: , и результаты склеивания w вводятся в выражение функции в качестве дополнительных членов. Далее выполняется операция поглощения. Она основана на равенстве (член w поглощает член ). При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате операции скле­ивания.

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

 

Таблица 2

Совершенная ДНФ этой функции

(3)

Для получения сокращенной формы проводим операции склеивания и поглощения:

(4)

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

Таблица 3

 

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

Вторая импликанта поглощает 1-й и 3-й члены СДНФ (крес­тики поставлены в первом и третьем столбцах второй строки) и т.д. Импликанты, которые не могут быть лишними и, следовательно, не могут быть исключены из сокращенной формы, составляют ядро. Вхо­дящие в ядро импликанты легко определяются по импликантной матри­це. Для каждой из них имеется хотя бы один столбец, перекрываемый только данной импликантой.

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

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

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

(5)

Структурная схема, соответствующая этому выражению, приведена на рис.2.

Рис. 2

 

До сих пор рассматривалось получение минимальной ДНФ. При использовании метода Квайна для получения минимальной конъюнктивной нормальной формы (МКНФ) логической функции имеются следую­щие особенности:

- исходной для минимизации формой логического выражения задан­ной функции является СКНФ;

- пары склеиваемых членов имеют вид w v д: и wv x;

- операция поглощения проводится в соответствии с выражением

Рассмотрим применение метода Квайна на примере минимизации функции, заданной таблицей истинности (табл. 4).

Таблица 4

Совершенная КНФ рассматриваемой функции

Склеивающиеся пары членов:

1-й и 3-й члены (результат склеивания );

1-й и 4-й члены (результат склеивания );

2-й и 3-й члены (результат склеивания ).

Проводим операции склеивания и поглощения:

Члены операции склеивания

Полученное выражение является сокращенной формой функции.

Для перехода к минимальной форме строим импликантную матрицу (табл. 5).

 

Таблица 5

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

 

1.3. Минимизация логических функций методом карт Вейча

 

Метод минимизации функции с помощью карт Вейча обеспечивает простоту получения результатов. Он используется при минимизации относительно несложных функций (с числом аргументов до пяти). Карта Вейча представляет собой опре­деленную форму таблицы истинности. Табл. 6 являются картами Вейча для функций соответственно двух (а), трех (б), четырех (в) аргу­ментов.

Таблица 6

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

 

1-я клетка

Число клеток карты равно числу всех возможных наборов значений аргументов ( п — число аргументов функций ). В каждую из клеток карты записывается значение функции на соответствующем этой клетке наборе значений аргументов. Пусть функция задана таблицей истиннос­ти (табл. 7). Таблица истин­ности этой функции в форме карты Вейча представлена табл. 8.

Таблица 7

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

Таблица 8Таблица 9

Сформулируем правила получения МДНФ функций с помощью карт Вейча. Все клетки, содержащие 1, объединяются в замкнутые области. При этом каждая область должна представлять собой прямоугольник с чис­лом клеток 2k, где k - 0, 1, 2,... . Значит, допустимое число клеток в области 1, 2, 4, 8,...,. Области могут пересекаться и одни и те же клетки могут входить в разные области. Затем проводится запись выражения МДНФ функции. Каждая из областей в МДНФ представляется членом, число букв в котором на k меньше общего числа аргументов функции п (т.е. равно ). Каждый член МДНФ составляется лишь из тех аргу­ментов, которые для клеток соответствующей области имеют одинако­вое значение (без инверсии либо с инверсией).

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

Рассмотрим минимизацию с помощью карты Вейча функции трех аргументов, представленной табл. 9. Все клетки, содержащие 1, охва­тываются двумя областями. В каждой из областей 21 клеток, для них n-k = 3-l = 2, и эти области в МДНФ будут представлены членами, содержащими по две буквы. Первой области соответствует член (аргумент здесь не присутствует, так как для одной клетки этой области он имеет значение без инверсии, для другой — с инверсией); второй области соответствует член . Следовательно, МДНФ функ­ции

Рассмотрим пример минимизации функции четырех аргументов, заданной табл. 10. Первая и четвертая области имеют по две клетки, для них п- k - 4 -1=3. Эти области в МДНФ будут представлены членами, содержащими по три буквы. Вторая и третья области содер­жат по четыре клетки и в МДНФ выражаются членами, содержащими по две буквы (п - k = 4 -2 = 2). Минимальная ДНФ функции

Таблица 10Таблица 11

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

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

Таблица 12Таблица 13

Для получения МКНФ функции замкнутыми областями охватыва­ются клетки с нулевыми значениями функции, и при записи членов логического выражения берутся инверсии аргументов, на пересечении которых находятся области. Так, для функции, приведенной в табл. 13, МКНФ

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

Рис.3 Таблица истинности здесь состоит из двух карт, каж­дая из которых представляет собой карту четырех переменных. Одна из них соответствует х5= 1, другая - х5 = 0. Эти карты можно мысленно расположить одна над другой (рис.3). При этом области охвата клеток могут быть трехмерными, т.е. одной областью могут охваты­ваться клетки двух карт.

Для функции, приведенной в табл. 23, МДНФ

Таблица 14

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

 

1.4. Минимизация функций с использованием карт Карно

Отличие карт Карно от карт Вейча заключается в способе обозначе­ния строк и столбцов таблицы истинности. Таблица 15 иллюстрирует карты Карно для функций трех и четырех аргументов.

Аргументы функции делятся на две группы, комбинации значений аргументов одной группы приписываются столбцам таблицы, комбина­ции значений аргументов другой группы - строкам таблицы. Столбцы и строки обозначаются комбинациями, соответствующими последова­тельности чисел в коде Грея (это сделано для того, чтобы склеивающиеся клетки находились рядом). Обозначения столбца и строки, на пересече­нии которых находится клетка таблицы, образуют набор, значение функции на этом наборе записывается в клетку.

Для получения МДНФ функции охватываются областями клетки таблицы, содержащие 1. Как и в случае минимизации с помощью карт Вейча, области должны быть прямоугольной формы и содержать 2k клеток (при целочисленном значении k). Для каждой области составля­ется набор из двух комбинаций: приписанных столбцам и приписанных строкам, на пересечении которых расположена область. При этом если области соответствуют несколько комбинаций кода Грея, приписанных столбцам или строкам, то при составлении набора области записывает­ся общая часть этих комбинаций, а на месте различающихся разрядов комбинаций ставятся звездочки. Например, для функции, представлен­ной табл. 16, области I будет соответствовать набор 1*00 или член МДНФ , области II - набор 0**1 или член МДНФ . Таким образом, для этой функции МДНФ

Таблица 15

Таблица 16Таблица 17

Для получения МКНФ областями охватываются клетки, содержа­щие 0, и члены МКНФ записываются через инверсии цифр, получаемых для наборов отдельных областей. Так, для функции, представленной в табл. 17, области I соответствует набор *100 и член МКНФ , области II — набор О*1* и член . Таким образом, МКНФ функции

 

1.5. Задание для выполнения

Для функции четырех аргументов F(x1,x2,x2,x4):

а) записать СДНФ;

б) записать СКНФ;

в) упростить функцию с помощью метода Квайна – записать МДНФ и МКНФ;

г) упростить функцию с помощью карты Вейча – записать МДНФ и МКНФ;

д) упростить функцию с помощью карты Карно – записать МДНФ и МКНФ;

е) сравнить МДНФ и МКНФ, полученные в п. в)-д);

ж) реализовать МДНФ и МКНФ на логических элементах.

Для выбора варианта взять 2 последние цифры в номере зачетной книжки.