Проблема минимизации в монофункциональных базисах

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

Все определения для ФАЛ в базисе {-, &, }, введенные в главе 1, имеют свои аналоги и для рассматриваемого базиса. Совершенной нормальной формой в дальнейшем будем считать выражение (2-5), операнды которого будут иметь наибольший возможный для данной функции ранг. Определение минимальной нормальной формы вполне аналогично определению МДНФ в классе ДНФ.

Понятиям интервал и максимальный интервал из геометрической интерпретации области определения функции алгебры логики соответствовали понятия импликанта и простая импликанта при минимизации в классе ДНФ. В базисе Вебба соответствующие понятия будем называть инверсантой и простой инверсантой.

Инверсанта и функции f характеризуется тем, что всегда из и =1 следует f =0. Очевидно, что все F_i из (2-5) являются инверсантами заданной функции f. Отметим, что тоже является инверсантой функции f.

По аналогии с классическим базисом будем говорить, что выражение в базисе Вебба, операндами которого являются все простые инверсанты заданной функции, является сокращенной нормальной формой функции. Минимальная нормальная форма будет получаться из сокращенной выбрасыванием некоторых инверсантов. Определение тупиковой формы в рассматриваемом базисе Вебба формулируется по аналогии с классическим базисом {-, &, }.

Тупиковой ДНФ функции f называется дизъюнкция простых импликантов, из которых ни один простой импликант нельзя удалить так, чтобы полученная ДНФ все еще представляла функцию. Получение МДНФ можно разбить на два этапа. На первом находят сокращенную ДНФ. На втором строят тупиковые ДНФ функции, удаляя подмножества элементарных конъюнкций из сокращенной ДНФ. Из полученных тупиковых ДНФ выбирают МДНФ.

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

Введем теперь операции следующих типов: