Минимизация логических функций методом Квайна
Метод Квайна позволяет представлять функции в ДНФ или КНФ с минимальным числом членов и минимальным числом букв в членах.
Этот метод содержит два этапа преобразования выражения функции: на первом этапе осуществляется переход от канонической формы (СДНФ или СКНФ) к так называемой сокращенной форме, на втором этапе - переход от сокращенной формы логического выражения к минимальной форме.
Рис. 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 последние цифры в номере зачетной книжки.
| 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 |
ДЕШИФРАТОРЫ
Дата добавления: 2016-07-18; просмотров: 3884;
Поиск по сайту
Узнать еще
- I. Расчёт методом контурных токов.
- I. Решение логических задач средствами алгебры логики
- II. Расчёт методом суперпозиции.
- II. Решение логических задач табличным способом
- III. Решение логических задач с помощью рассуждений
- IV. Расчёт простых цепей постоянного тока методом эквивалентных преобразований сопротивлений.
- А. Модели экономического прогноза на базе производственных функций.
- Адаптация человека в различных экологических нишах Земли
Публикации по технике и механике
Публикации по биологии
Публикации по информатике
Публикации по строительству
Публикации по физике
Публикации по химии
Публикации по электронике
Публикации по искусству
Публикации по истории
Публикации по медицине
