2.4.1. Минимизация булевых функций. Постановка задачи

Задача минимизации состоит в том, чтобы для данной булевой функции найти наиболее короткое представление (наиболее короткую формулу) в виде композиции функций из данного базиса или данной полной системы функций.

Мы рассмотрим следующую постановку: функция задана таблицей значений (или СДНФ); требуется найти ДНФ данной функции, имеющую наиболее короткую длину (наименьшее число переменных в её записи).

В основе методов минимизации булевых функций в классе ДНФ лежит операция "склеивания": если в ДНФ, представляющей данную функцию, имеется две конъюнкции K1 и K2 вида K1 = A·Xi и K2 = A· (расстановка отрицаний в которых отличается только по одной переменной), то их можно «склеить», т. е. заменить конъюнкцией A, (так как ), что значительно упрощает формулу.

При решении задач минимизации элементарные конъюнкции, содержащие R переменных, называют Минитермами ранга r. Кроме того, если , то A называется Импликантой B. Например, минитермы, получаемые в результате склеивания, являются импликантами исходной СДНФ.

< Предыдущая		Следующая >