Минимизация логических функций методом Квайна.
Алгоритм получения сокращенной ДНФ. 1) Логическая функция, подлежащая минимизации представляется в СДНФ; 2) проводится операция неполного склеивания ко всем возможным парам конъюнкций ( 3) выполняется операция поглощения ( 4) полученные импликанты проверяются на «простоту»; 5) если полученные импликанты являются простыми, то полученная формула является сокращенной ДНФ, если нет то перейти к 2. Пример. 1) 2) выполним операции склеивания первого и второго, а также третьего и четвертого слагаемых:
3) выполним операции поглощения:
4) Недостаток метода. Трудоемкость отыскания всех возможных пар склеиваемых конъюнкций, особенно при увеличении числа переменных и конституент «1».
|
);
);
;
являются простыми импликантами, следовательно, полученная формула является сокращенной ДНФ.
