ПРО223_Алексеева_ЦУиМП_Лек_2
.docx3 вариант
Вопрос:
Как выполняется этап получения сокращенной дизъюнктивной нормальной формы по методу Квайна?
Ответ:
Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.
Метод Квайна состоит из двух основных этапов:
получение сокращенной ДНФ из СДНФ;
построение, исходя из сокращенной, тупиковых ДНФ, и выбор из их числа МДНФ.
На первом этапе к СДНФ применяют операции склеивания
и поглощения
Необходимо найти все возможные пары членов (каждый член с каждым). Если в СДНФ выполнить все операции склеивания, а затем все операции поглощения, то в результате будет получена сокращенная ДНФ.
С помощью операции поглощения на первом этапе минимизации исключаются только те члены ДНФ, к которым применены все возможные для них склеивания.
Склеивание происходит между смежными минтерами (конституентами единицы).
Минтерм — булева функция, принимающая истинное значение лишь при одной-единственной комбинации своих аргументов.
Смежными называются минтермы, отличающиеся формой вхождения в них лишь одного аргумента (в один минтерм аргумент входит в прямой форме, а другой – в инверсной).
Два смежных минтерма склеиваются, что приводит к замене их конъюнкцией с числом аргументов (n-1) на единицу меньшим, чем в исходных минтермах.
Импликантами или контермами называются конъюнкции, получаемые в результате склеивания двух смежных минтермов.
Полученные импликанты более не склеиваются и называются простыми (или первичными). Они покрывают склеиваемые минтермы и, следовательно, функция Y принимает следующий вид:
ДНФ функции, состоящая из простых импликант, называется сокращенной ДНФ.
На втором этапе используют таблицу простых импликант, представляющую собой прямоугольную таблицу, называемую импликативной. Столбцы такой таблицы являются минтермами минимизируемой функции, строки – ее различными простыми импликантами. Если некоторый минтерм покрывает какая – либо из простых импликант, то на пересечении соответствующих столбца и строки ставится метка (например, +).
Получение тупиковых ДНФ с помощью таблицы простых импликант связано с построением на ее основе так называемой сокращенной таблицы простых импликант.
Такая таблица получается при вычеркивании из таблицы простых импликант:
1) тех столбцов, которые содержат только по одной метке;
2) тех строк, импликанты которых содержат метки в вычеркнутых столбцах;
3) одного из тех двух столбцов, у которых имеются метки в одинаковых строках;
4) тех строк, которые в результате (в соответствии с п. 1-3) не содержат ни одной метки.
Построению тупиковой ДНФ при этом соответствует выбор такой совокупности простых импликант, которая включает все те импликанты, которые принадлежат строчкам, вычеркнутым в соответствии с п. 2 (так называемое ядро булевой функции), и, кроме того, некоторую систему импликант из сокращенной таблицы, метки которых, по крайней мере, один раз накрывают все ее столбцы. В отличие от ядра такая система в общем случае может содержать различные наборы простых импликант. Выбор набора импликант с минимальным суммарным числом переменных при нескольких возможных вариантах соответствует построению минимальной ДНФ заданной функции.
Выбор оптимальной минимальной тупиковой формы для реализации функции в данном случае будет определяться удобством реализации.
Может существовать несколько тупиковых ДНФ функций. Искомая оптимальная МДНФ совпадает с той из тупиковых ДНФ, которая содержит минимальное число вхождений аргументов.