Метод Квайна

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

Большинство методов минимизации состоит из двух этапов:

1. получение сокращенных ДНФ, т.е. дизъюнкции простых импликант;

2. исключение лишних простых импликант, т.е. получение минимальных ДНФ.

Поиск сокращенной ДНФ основан на операциях:

1. неполного склеивания: А х Ú А ù х = А х Ú А ù х Ú А,

где А – любая элементарная конъюнкция;

2. поглощения: А Ú A = A, где Î { x, ù x }.

Теорема Квайна: если в СДНФ логической функции произвести все операции неполного склеивания, а затем все операции поглощения, то получим сокращенную ДНФ.

{ Пример: минимизировать булевую функцию, заданную номерами конституент 1 – F (x₁, x₂, _, x₃, x₄) = Ú (1, 3, 5, 7, 14, 15).

Дата добавления: 2014-01-06