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

Хотя представление БФ в среднем короче, чем их задание в виде таблицы, все же задание в виде СДНФ и СКНФ крайне неэффективно. Сравнивая разные представления для, скажем, мажоритарной функции, убеждаемся, что с сокращенным представлением работать значительно проще. Есть и другие аргументы, приводящие к постановке задачи о поиске самых коротких представлений для булевых функций.

Определимся со словом короче. В основном используются 2 понятия:

Рангом ЭК называется число входящих в нее литералов. Рангом ДНФ называется сумма рангов входящих в нее ЭК.

Длиной ДНФ называется число входящих в нее ЭК.

Минимальной называется ДНФ, имеющая минимальный ранг среди всех равносильных.

Кратчайшей называется ДНФ, имеющая минимальное число ЭК (т.е. длину).

Кратчайшая ДНФ не обязана быть минимальной, но поиск минимальных проводится среди кратчайших.

Существует много алгоритмов поиска минимальных ДНФ. Мы опишем несколько из них.

Тривиальный алгоритм минимизации.

А. Выписываем все возможные ДНФ от данного n в порядке возрастания их рангов.

Б. Последовательно сравниваем функцию с ДНФ. Первая ДНФ, которая окажется равной данной, имеет минимальный ранг.

Этот «алгоритм» приведен в двух целях: во-первых, он доказывает существование решения; во-вторых, по нему можно оценить трудоемкость тупого перебора.