Метод Квайна

Рассмотрим метод Квайна для нахождения МДНФ, представляющей данную булеву функцию. Определим следующие триоперации:

- операция полного склеивания - ~ ~ φ;

- операция неполного склеивания - ~ ~ ;

- операция элементарного поглощения - ~ φ, .

 

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

 

Пример 6.6.3. Определить сокращенную ДНФ функции f. Пусть функция f(x,y z) задана совершенной ДНФ .

Решение. Произведем в два этапа все возможные операции неполного склеивания, а затем элементарного поглощения, имеем

φ ~ ~

~ ~

~ ~

~ ~

~ .

Таким образом, сокращенной ДНФ функции f является формула .

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

Пример. Пусть функция f(x,y z) задана совершенной ДНФ . Тогда, производя операции склеивания, а затем элементарного поглощения, имеем

φ ~ ~

~ .

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

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

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

Пример. Пусть функция f(x,y z) задана совершенной ДНФ .

Матрица Квайна имеет вид

Импликанты	Конституенты единицы
	*	*
		*	*
			*	*

 

По матрице Квайна находим, что минимальная ДНФ заданной функции есть .

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

В качестве минимальной ДНФ выбирается тупиковая, имеющая наименьшее число вхождений переменных.

В силу принципа двойственности для булевых алгебр все приведенные понятия и рассуждения очевидным образом можно преобразовать для нахождения минимальных конъюнктивных нормальных форм (МКНФ).

Контрольные вопросы

Лекция № 11

Так как здание всего мира совершенно и возведено премудрым Творцом, то в мире не происходит ничего, в чем не было бы виден смысл какого-нибудь максимума или минимума.

Эйлер