Аналитический метод минимизации ФАЛ

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 04:03, 31 мая 2016.

Описание метода

Основным методом минимизации логических функций, представленных в виде СКНФ, является операция попарного неполного склеивания и элементарного поглощения. Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной. В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:


Аналогично для КНФ:


Возможность поглощения следует из очевидных равенств:

Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей.

Правило склеивания

Заключается в замене логической суммы двух элементарных конъюнкций, отличающихся только знаком отрицания над одной из переменных, одной элементарной конъюнкцией, которая является общей частью рассматриваемых слагаемых, т.е.

Например,

Правило поглощения

Дизъюнкцию двух элементарных конъюнкций, из которых одна полностью содержится в другой, можно заменить конъюнкцией, имеющей меньший ранг, например:

Список источников

  1. Студопедия
  2. bourabai.ru/
  3. http://edu.dvgups.ru/
  4. www.swsys.ru