Минимизация булевых функций

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

Операция удаления элементарной конъюнкции:

Операции удаления множителя:

Замечание. Для построения тупиковой д.н.ф. можно использовать геометрический и табличный методы.

4.1. С помощью операций удаления эл. конъюнкции и множителя построить тупиковые днф для заданной функции.

1)

4.2. Табличный способ построения м.д.н.ф.

a) составим табл.1. Отметим конъюнкции не принадлежащие с.д.н.ф. данной ф-ции.

Вычеркнем все конъюнкции в этих строках.

b) вычеркнутые в этих строках конъюнкции вычеркнем также во всех остальных

строках таблицы.

c) в каждой строке выберем из оставшихся конъюнкций лишь конъюнкции с наи-

меньшим числом сомножителей, а остальные вычеркнем.

d) в каждой строке выберем поодному оставшемуся элементу и составим из них днф.

e) из всех днф, полученных в d), выберем минимальную.

Построить минимальную днф для функции . Составим таблицу:

После применения пунктов a,b,c останутся выделенные конъюнкции

После применения пунктов d и e получим минимальную д.н.ф.:

4.3. Геометрический метод построения тупиковых д.н.ф.

a) по таблице построить носитель ф-ции (носитель ф-ции - единичный n-мерный куб с отмеченными вершинами, в которых значения функции равно 1)

b) построить всевозможные неприводимые покрытия (покрытие называется неприводимым, если 1) все интервалы, входящие в это покрытие, являются max; 2) при удалении любого интервала, оставшийся набор интервалов не является покрытием)

c) построить т.д.н.ф., соответствующие этим покрытиям

d) выбрать из этих т.д.н.ф. - минимальную.

Найти минимальную д.н.ф. для функции

(001) (011)

(101) (111)

(000) (010)

(101) (110)

4.4. Используя известные методы минимизации найти минимальную д.н.ф. функции.

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

4.5. Выяснить, являются ли тупиковыми (или минимальными) следующие д.н.ф.

1)

2)

3)

Дата добавления: 2014-12-27