5.6.2 Минимальные кнф

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

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

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

1-4:

2-6:

3-4:

3-6:

4-5:

5-6: .

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

Затем выполняются операции поглощения:

.

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

.

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

В данном примере между «сокращенными» элементарными дизъюнкциями, полученными в результате операций склеивания и поглощения, также можно выполнить операции склеивания и поглощения. Выполним неполные склеивания:

3-6:

4-5: .

Здесь 3-6 и 4-5 – номера «сокращенных» элементарных дизъюнкций, участвующих в операциях неполного склеивания (номером 3 обозначена элементарная дизъюнкция , номером 4 -).

Выполним операции поглощения:

.

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

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

.

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

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

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

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

	*			*
		*				*
			*	*	*	*

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

Из таблицы 5.7 видно, что в данном примере ничего исключить нельзя: при исключении любой строки импликантной матрицы один из столбцов остается неотмеченным.

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