Геометрический

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

Изобразим область определения произвольной булевой функции трех переменных – это вершины трехмерного куба. Элементам куба можно поставить во взаимо-однозначное соответствие конъюнкции различного ранга: вершинам куба – конъюнкции третьего ранга, ребрам – второго, граням – первого. Каждый геометрический эквивалент меньшей размерности покрывается всеми геометрическими эквивалентами большей размерности. Конъюнкции большего ранга покрываются конъюнкциями меньшего ранга (см. рисунок).

Так, например, конъюнкции и покрываются конъюнкцией (две вершины – ребро);

Конъюнкции , , , покрываются либо двумя конъюнкциями и , либо только (четыре вершины – либо два ребра, либо одна грань).

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

Для функций и на приведенных ниже чертежах мини-мальными формами будут , или Для второй функции задача решается неоднозначно.

Пример: 1 Минимизировать функцию, заданную следующей таблицей истинности

Ее формула в СДНФ имеет вид:

Отметим на чертеже вершины, соответствующие конъюнкциям, входящим в СДНФ данной функции.

Заметим, что четыре вершины лежат в одной грани , а две на одном ребре Откуда следует, что минимальная форма функции и есть сумма этих интервалов , т.е. Другого варианта решения здесь не может быть. Задача решается однозначно.

Date: 2015-05-22; view: 523; Нарушение авторских прав