Тупиковые и минимальные ДНФ: определения и соотношение

Тупиковая ДНФ функции f — такая реализующая f ДНФ, из которой нельзя удалить ни отдельные буквы, ни целые элементарные конъюнкции и сохранить ту же функцию. Поэтому её члены являются простыми импликантами, а геометрически она задаёт неприводимое покрытие \(N_f\) максимальными гранями.1

Минимальная ДНФ в терминологии курса имеет минимальный ранг, а кратчайшая — минимальную длину. Минимальная ДНФ обязательно тупиковая. Среди кратчайших ДНФ всегда существует тупиковая. Обратное неверно: тупиковость означает неприводимость, но не глобальную оптимальность.1

Что важно запомнить
  • Тупиковая ДНФ неприводима по удалению букв и целых конъюнктов.
  • В тупиковую ДНФ входят только простые импликанты.
  • Минимальная ДНФ минимизирует ранг, кратчайшая — длину.
  • Минимальная ДНФ всегда тупиковая, но тупиковая ДНФ не обязана быть минимальной или кратчайшей.1

Тупиковая ДНФ

Пусть A реализует f. В курсе ВМК A называется тупиковой, если любая попытка упростить её удалением некоторых букв или целых элементарных конъюнкций приводит к ДНФ, уже не реализующей f. Это более сильное требование, чем просто отсутствие одинаковых или поглощаемых членов.1

Отсюда следуют два свойства. Во-первых, каждый член тупиковой ДНФ является простой импликантой. Если бы из него можно было удалить букву и всё ещё получить импликанту, исходная форма не была бы тупиковой. Во-вторых, ни один конъюнкт нельзя удалить целиком. Геометрически максимальные грани, соответствующие членам A, образуют тупиковое, то есть неприводимое по удалению компонент, покрытие \(N_f\).1

Минимальная и кратчайшая ДНФ

Оптимальность задаётся глобальным сравнением со всеми ДНФ функции. Минимальная ДНФ имеет наименьший возможный ранг R, то есть минимальное суммарное число литералов. Кратчайшая ДНФ имеет наименьшую длину λ, то есть минимальное число элементарных конъюнкций. Эти оптимумы могут достигаться разными формами.1

Соотношение понятий

Минимальная по рангу форма не может содержать удаляемую букву или лишний член, поэтому она обязательно тупиковая. Для задачи минимизации это позволяет сначала построить тупиковые ДНФ, а затем сравнивать их по рангу. Для длины лекционный курс формулирует более осторожный результат: среди кратчайших ДНФ всегда есть тупиковая.1

Обратное утверждение неверно. Неприводимое покрытие может оказаться далеко не самым экономным среди всех неприводимых покрытий. Поэтому слово «тупиковая» означает, что локально удалять уже нечего, но не означает, что найден глобальный оптимум.

Пример простыми словами

Аналогия с покрытиями помогает различить понятия. Пусть множество можно покрыть двумя разными наборами максимальных блоков. Оба покрытия могут быть неприводимыми: из каждого нельзя убрать ни одного блока. Но одно использует три блока, а другое четыре. Оба соответствуют тупиковым формам, однако только первое может быть кратчайшим.

Частые ошибки
  • Отождествлять тупиковую и минимальную ДНФ.
  • Проверять тупиковость только удалением целых конъюнктов. В определении курса учитывается и удаление букв.
  • Считать ДНФ без поглощений автоматически тупиковой. В ней всё ещё может быть целиком лишняя простая импликанта.
  • Путать минимальность по рангу с кратчайшестью по числу конъюнктов.

Другие вопросы

Источники

  1. 1 Ложкин С. А. Лекции по основам кибернетики Вариант 2017 г. (гр. 311–319), глава 1, §§4, 7, МГУ, факультет ВМК