Метод Квайна поиска СокДНФ

Поэтапная минимизация логических функций предполагает следующий алгоритм минимизации: ДСНФ СокДНФ (Сокращенная ДНФ) ТДНФ (Тупиковая ДНФ) МДНФ (Минимальная ДНФ).

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

Операция полного склеивания: (члены и склеены по переменной ).

Операция неполного склеивания: .

Операция поглощения: (член поглощается членом ).

Порядок нахождения СокДНФ по Квайну:

1. Преобразовать исходную логическую функцию к ДСНФ.

2. В полученной ДСНФ выполнить все операции неполного склеивания.

3. Выполнить все операции поглощения.

4. Повторять шаги 2 и 3 до тех пор, пока среди конъюнкций не останется склеивающихся между собой.

Пример 1. Получить СокДНФ функции

1 - 2 *

1 - 3 *

1 - 4

1 - 5

1 - 6

2 - 3

2 - 4 *

2 - 5

2 - 6

3 - 4 *

3 - 5

3 - 6

4 - 5

4 - 6 *

5 - 6 *

1 - 2 2 - 3 * 3 - 4 4 - 5 5 - 6

1 - 3 2 - 4 3 - 5 4 - 6

1 - 4 * 2 - 5 3 - 6

1 - 5 2 - 6

1 - 6

– СокДНФ

Пример 2. Получить СокДНФ функции

1 - 2 * 2 - 3 * 3 - 4

1 - 3 2 - 4

1 - 4 *

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

Для нахождения тупиковых и минимальной ДНФ используется метод импликантных (импликативных) матриц.

Импликантная матрица – это таблица, в которой столбцы изображают конъюнкции ДСНФ, а строки – простейшие импликанты СокДНФ.

Составим импликантную матрицу для функции

(ДСНФ)

1 - 2 * 2 - 3 3 - 4 * 4 - 5 * 5 - 6 *

1 - 3 * 2 - 4 3 - 5 4 - 6

1 - 4 2 - 5 3 - 6

1 - 5 2 - 6 *

1 – 6

Дальнейшее склеивание невозможно. Следовательно, полученная запись – СокДНФ.

СокДНФ	ДСНФ
	Ö	Ö
	Ö		Ö
		Ö				Ö
			Ö	Ö
				Ö	Ö
					Ö	Ö

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

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

В тупиковую ДНФ должны входить импликанты, поглощающие все конъюнкции.

ТДНФ 1 =

ТДНФ 2 =

ТДНФ 3 =

ТДНФ 4 =

ТДНФ 5 =

Из полученных ТДНФ выбирается МДНФ:

ТДНФ 1 =

ТДНФ 3 =