09. Минимизация нормальных форм
P Импликантой булевой функции 
называется такая её элементарная конъюнкция K, для которой выполняется равносильность 
.
P Простой называется такая импликанта, которая при удалении из неё любой буквы перестаёт быть импликантой булевой функции 
.
P Сокращённой называется ДНФ, состоящая из всех простых импликант данной булевой функции.
P Минимальной называется ДНФ, имеющая наименьшее число символов переменных из всех ДНФ, задающих данную булеву функцию.
Для получения сокращённой ДНФ из СДНФ применяются следующие логические операции:
1) операция полного склеивания 
;
2) операция неполного склеивания
;
3) операция поглощения 
.
Теорема 1.9. (Теорема Квайна.) Если в СДНФ формулы произвести все возможные операции неполного склеивания, а затем операции поглощения, то получится сокращённая ДНФ.
Например, применив в формуле 
один раз операцию неполного склеивания и два раза – операцию поглощения, получим сокращённую ДНФ: 
.
Для получения минимальной ДНФ из сокращённой ДНФ данной СДНФ используется Таблица Квайна. В заголовки столбцов таблицы записываются элементарные конъюнкции СДНФ, в заголовки строк – простые импликанты сокращённой ДНФ. В таблице звёздочками отмечаются те ячейки, для которых элементарная конъюнкция, стоящая в заголовке строки, входит в элементарную конъюнкцию, стоящую в заголовке столбца. Затем выбираются ДНФ, содержащие минимальное число простых импликант, таких, что каждый столбец таблицы Квайна содержит по крайней мере одну звёздочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. Затем из этих ДНФ выбирается минимальная ДНФ.
Пример. Найти сокращённую и минимальную ДНФ булевой функции 
, заданной таблицей истинности:
|
X |
Y |
Z |
F |
|
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
1 |
Решение. 1) Составим СДНФ функции (см. пункт 1.8):
.
2) Выполним в полученной формуле все операции неполного склеивания и поглощения:
Полученная формула является сокращённой ДНФ.
3) Составим таблицу Квайна:
|
|
|
|
| |
|
|
* |
* | ||
|
|
* |
* | ||
|
|
* |
* |
Составим минимальную ДНФ: 
. □
Задачи и упражнения
1.35. Найдите сокращённую и минимальную ДНФ булевых функций, заданных таблицами истинности:
|
X |
Y |
Z |
F1 |
F2 |
F3 |
|
1 |
1 |
1 |
0 |
1 |
0 |
|
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
| < Предыдущая | Следующая > |
|---|
