logo search
Diskretnaya_matematika_1_semestr

Задача минимизации булевых функций.

Любую булеву функцию можно представить в виде ДНФ, при чем это представление не единственно.

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

Задача минимизации: необходимо найти такое представление функции в виде ДНФ, которое имеет минимальный индес простоты.

Рассматривается 3 отдельных задачи:

1)минимизация числа конъюнкций

2)минимизация числа букв

3)минимизация числа отрицаний

Эти задачи можно решать следующим образом:

1)найти всевозможные представления ф-ции в виде ДНФ с ограниченным числом конъюнкций,букв, отрицаний;

2)среди этих предствалений найти то, которое имеет минимальный индекс простоты. Такой способ называется переборным (ограничение на число букв, конъюнкций, отрицаний)

Редко применим.

  1.