5.6 Минимизация формул алгебры логики

Основные этапы минимизации любой формулы алгебры логики следующие:

1) получение СДНФ или СКНФ (как показано в подразделе 5.5);

2) получение сокращенной ДНФ или КНФ;

3) получение тупиковых ДНФ или КНФ и выбор из них минимальной ДНФ или КНФ.

5.6.1 Минимальные днф

Пример 5.6 – Пусть для некоторой формулы получена следующая СДНФ:

Требуется получить для нее минимальную ДНФ.

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

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

Однако для построения сокращенной ДНФ требуется сначала выполнить именно операции неполного склеивания. Поскольку, как показано выше, , и учитывая свойствоAA=A, можно записать:

Это и есть результат неполного склеивания первой и четвертой конституент единицы.

Аналогично выполним другие неполные склеивания:

1-5:

2-3:

2-5: .

Здесь 1-5, 2-3 и 2-5 – номера конституент единицы (т.е. элементарных конъюнкций из СДНФ), участвующих в операциях склеивания.

Затем выполняются операции поглощения. Так как, например, , можно записать:

Аналогично:

.

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

Операции склеивания между полученными элементарными конъюнкциями невозможны. Таким образом, все возможные операции неполного склеивания и поглощения выполнены. Получена сокращенная ДНФ.

В данном случае в операциях склеивания и поглощения участвовали все конституенты единицы (все пять). Если бы какие-либо из них не участвовали в операциях склеивания и поглощения, то они вошли бы в сокращенную ДНФ без изменений.

Следует обратить внимание, что при получении сокращенной ДНФ необходимо выполнять сначала операции неполного склеивания, а затем - поглощения (а не сразу – операции полного склеивания), чтобы элементарные дизъюнкции могли участвовать в склеивании несколько раз. Например, если бы в рассмотренном примере было сразу выполнено полное склеивание между конституентами единицы с номерами 1 и 4, то конституента 1 не могла бы затем участвовать в склеивании с конституентой 5.

Примечания

1Обычно при описании решения задач, подобных рассмотренной в примере 5.6, для краткости сразу записывают результаты полного склеивания, имея в виду, что в действительности сначала выполняются неполные склеивания (поэтому элементарные конъюнкции могут участвовать в них несколько раз), а затем - поглощения.

2Элементарные конъюнкции, входящие в состав сокращенной ДНФ, называются простыми импликантами. Подробное объяснение этого названия выходит за рамки данного курса.

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

Импликантная матрица – это таблица, где в заголовке указываются конституенты единицы (из СДНФ), а сбоку – простые импликанты, т.е. элементарные конъюнкции из сокращенной ДНФ. На пересечении i-й строки и j-го столбца ставится отметка, если i-я простая импликанта «входит» в j-ю конституенту единицы.

Для рассматриваемого примера импликантная матрица приведена в таблице 5.6.

Таблица 5.6 – Импликантная матрица для примера 5.6

	*			*
	*				*
		*	*
		*			*

Если при исключении какой-либо простой импликанты (т.е. строки импликантной матрицы) все столбцы остаются помеченными, значит, эту простую импликанту можно исключить из сокращенной ДНФ.

Из таблицы 5.6 видно, что в данном примере можно исключить или , или. Таким образом, можно построить две тупиковые ДНФ:или. Так как их длина (т.е. количество переменных в них) одинаково, обе они являются минимальными ДНФ.

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