шпорки) , 1ый семестр (Луцик Ю) / 25 Метод Квайна

25 Метод Квайна
Теорема Квайна. Для получения мин формы логической функции необходимо в СДНФ произвести все возможные склеивания и поглощения, так чтобы в результате была получена сокращенная ДНФ. Сокращенная ДНФ в общем случае может содержать лишние простые импликанты, к-ые необходимо выявить на 2-ом этапе минимизации.
На первом этапе выполняется переход от функции, заданной в форме СДНФ, к сокращенной ДНФ. Это основано на использовании следующих соотношений:
1) соотношение неполного склеивания
, где и - две конъюнкции, а F - любое элементарное произведение;
2) соотношение поглощения .
Суть метода - последовательное выполнение всех возможных склеиваний и затем всех поглощений, что приводит к сокращенной ДНФ. Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.
Из общего числа простых импликант необходимо отобрать их минимальное число, исключив лишние. Формирование тупиковых форм и выбор минимального покрытия начинается с выявления обязательных простых импликант, то есть таких, к-ые (и только они) покрывают некоторый исходный набор. Пример::
fСДНФ= V (1,2,5,6,7)=x1x2x3+ x1x2x3+ x1x2x3+ x1x2x3+ x1x2x3.
Выполним операцию склеивания:
1 - 3 (x1) x2x3 1
2 - 4 (x1) x2x3 2
3 - 5 (x2) x1x3 3
4 - 5 (x3) x1x2 4
В результате выполнения первого шага склеивания получаем четыре новые конъюнкции, простых импликант не выявлено. Полученные конъюнкции более не склеиваются и образуют сокращенную ДНФ.
fсокр СДНФ=x2x3+ x2x3+ x1x3+ x1x2 .
Для выявления обязательных простых импликант и формирования на их основе минимального покрытия строится импликантная таблица (табл. 13). В строках импликантной таблицы записываются простые импликанты, а в столбцах ? конституенты единицы. Звездочка ставится, если простая импли-канта покрывает конституенту. Таблица 13
x1x2x3 X1x2x3 x1x2x3 x1x2x3 x1x2x3
x2x3 * *
x2x3 * *
x1x3 * *
x1x2 * *
Простые импликанты х2х3+х2х3являются обязательными, так как только они покрывают конституенты х1х2х3 и х1х2х3 => включаются в минимальное покрытие. Остается одна непокрытая конституента x1x2x3, которая может быть покрыта одной из двух оставшихся простых импликант. Это приводит к получению двух тупиковых форм: f мднф = х2х3+х2х3+х1х3 или f мднф =х2х3+х2х3+х1х2