26.Область истенности булевой фун-ции. Покрытие обл. Заданной в днф.
Покрытие
области истинности булевой функции
максимальными интервалами называется
неприводимым,
если после удаления из него любого
интервала оно перестает быть покрытием.
ДНФ булевой функции
,
соответствующая неприводимому покрытию,
называется тупиковой.
Теорема 5 Всякая минимальная ДНФ является тупиковой.
Доказательство этого утверждения следует из того, что покрытие, соответствующее минимальной ДНФ, является неприводимым.
Заметим, что булева функция может обладать несколькими различными минимальными ДНФ. Существуют также тупиковые ДНФ, не являющиеся минимальными ДНФ. Соответствующие примеры будут разобраны ниже.
Из того, что минимальная ДНФ является тупиковой, следует общая схема решения задачи минимизации булевых функций.
1 Выделяются все максимальные интервалы, и строится сокращенная ДНФ.
2 Строятся все тупиковые ДНФ.
3 Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.
27.Метод Блейка,Нельсона, графический метод.
ДНФ – метод Блейка. Этот метод основан на следующей теореме.
Теорема 1 Если в произвольной ДНФ булевой функции f произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получится сокращенная ДНФ функции f.
Следовательно,
чтобы найти сокращенную ДНФ, надо к
произвольной ДНФ данной функции
применить правило обобщенного склеивания
до тех пор, пока это возможно, а затем
правило поглощения.
Пример 2 Найти сокращенную ДНФ для функции
.
Применяя
правило обобщенного склеивания,
получаем:
,
а затем правило поглощения и находим
сокращенную ДНФ:
.
ДНФ – метод Нельсона. Этот метод основан на следующей теореме.
Теорема 2 Если в произвольной КНФ булевой функции раскрыть все скобки в соответствии с дистрибутивным законом и устранить все элементарные поглощения, то в результате получится сокращенная ДНФ этой функции.
Пример 3 Найти сокращенную ДНФ для функции
.
После раскрытия скобок с помощью дистрибутивного закона, получаем:
.
Так
как
,
,
то имеем:
.
Далее, применяя правило поглощения, получаем сокращенную ДНФ:
.
Геометрич.
Метод: Пусть
.
Обозначим
,
,
.
Найдем соответствующие этим конъюнкциям
интервалы
,
,
.
Изобразим эти интервалы……..
Очевидно,
что
и
– все максимальные интервалы. Интервал
не является максимальным, ибо
.
Следовательно, покрытию подмножества
соответствует сокращенная ДНФ функции
,
равная
.
28. Минимальная днф. Метод инпликантных матриц.
Дизъюнктивная нормальная форма называется минимальной, если она включает минимальное число символов по сравнению со всеми другими эквивалентами ей дизъюнктивными нормальными формами.
Пример Найти минимальные ДНФ для функции
.
Из
предыдущего примера следует, что
сокращенная ДНФ для данной функции
.
Очевидно, что
.
Строим импликантную матрицу в виде таблицы
Отсюда видно, что данная функция имеет две минимальные ДНФ:
;
.