Пример 5.2.

В результате выполнено перекрытие четырех интервалов 3^го ранга двумя интервалами 2^го ранга. Таким образом, установлено взаимо-однозначное соответствие между заданием функции в виде ДНФ и покрытием множества Т для данной функции интервалами некоторого ранга.

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

(5.5.)

есть суммарный ранг ДНФ, который численно совпадает с числом букв, входящих в ДНФ. Тогда задача о минимизации есть задача нахождения такого покрытия множества Т, которое имеет минимальный суммарный ранг R. Интервал Y называется максимальным, если не существует другого интервала с рангом, меньшим, чем у Y, и такого, что