double arrow

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


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

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

Рис. 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

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

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

Метод минимизации функции с помощью карт Вейча обеспечивает простоту получения результатов. Он используется при минимизации относительно несложных функций (с числом аргументов до пяти). Карта Вейча представляет собой опре­деленную форму таблицы истинности. Табл. 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

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

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

Отличие карт Карно от карт Вейча заключается в способе обозначе­ния строк и столбцов таблицы истинности. Таблица 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 последние цифры в номере зачетной книжки.

x1 № варианта                                
x2                                
x3                                
x4                                
F(x1,x2,x3,x4) 1,21,41,61                                
F(x1,x2,x3,x4) 2,22,42,62                                
F(x1,x2,x3,x4) 3,23,43,63                                
F(x1,x2,x3,x4) 4,24,44,64                                
F(x1,x2,x3,x4) 5,25,45,65                                
F(x1,x2,x3,x4) 6,26,46,66                                
F(x1,x2,x3,x4) 7,27,47,67                                
F(x1,x2,x3,x4) 8,28,48,68                                
F(x1,x2,x3,x4) 9,29,49,69                                
F(x1,x2,x3,x4) 10,30,50,70                                
F(x1,x2,x3,x4) 11,31,51,71                                
F(x1,x2,x3,x4) 12,32,52,72                                
F(x1,x2,x3,x4) 13,33,53,73                                
F(x1,x2,x3,x4) 14,34,54,74                                
F(x1,x2,x3,x4) 15,35,55,75                                
F(x1,x2,x3,x4) 16,36,56,76                                
F(x1,x2,x3,x4) 17,37,57,77                                
F(x1,x2,x3,x4) 18,38,58,78                                
F(x1,x2,x3,x4) 19,39,59,79                                
F(x1,x2,x3,x4) 20,40,60,80                                

Сейчас читают про: