ДНФ суммы тупиковых: критерий вхождения конъюнкции и локальность критерия

ДНФ суммы тупиковых ΣT — дизъюнкция всех простых импликант функции, которые входят хотя бы в одну тупиковую ДНФ. В отличие от ДНФ пересечения тупиковых, ΣT всегда реализует исходную функцию и содержится в сокращённой ДНФ.1

Критерий вхождения формулируется геометрически: простая импликанта K входит в ΣT тогда и только тогда, когда соответствующая максимальная грань \(N_K\) не является регулярной. Проверка локальна: для ΣT достаточно анализировать окрестность второго порядка \(S_{2}(N_K,f)\).1

Что важно запомнить
  • ΣT объединяет простые импликанты, встречающиеся хотя бы в одной тупиковой ДНФ.
  • K∈ΣT ⇔ максимальная грань \(N_K\) нерегулярна.
  • Регулярная грань состоит только из регулярных точек.
  • Критерий локален: для вхождения в ΣT достаточно окрестности \(N_K\) второго порядка.1

ДНФ суммы тупиковых

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

Регулярные точки и грани

Для точки \(\alpha\in N_f\) обозначим через \(\Pi_\alpha(f)\) пучок всех максимальных граней, проходящих через α. Точка α называется регулярной, если существует \(\beta\in N_f\), для которой \(\Pi_\beta(f)\) строго содержится в \(\Pi_\alpha(f)\). Интуитивно покрытие β автоматически обеспечивает часть возможностей покрытия α. Максимальная грань называется регулярной, если все её точки регулярны.1

Критерий вхождения

Ключевая теорема курса утверждает: простая импликанта K входит в ДНФ \(\Sigma T\) тогда и только тогда, когда её максимальная грань \(N_K\) не является регулярной. Если вся грань регулярна, её можно избежать при построении тупиковых покрытий. Если же грань содержит нерегулярную точку, существует тупиковое покрытие, в котором без этой грани такую точку покрыть нельзя.1

Локальность критерия

На первый взгляд критерий требует знания всех максимальных граней функции. Однако в курсе вводится окрестность \(S_r(N,f)\). S0 содержит саму грань N, а \(S_r\) состоит из максимальных граней, пересекающих хотя бы одну грань предыдущей окрестности. Для проверки ядровости достаточно S1, а для проверки регулярности и, следовательно, вхождения K в ΣT достаточно \(S_{2}(N_K,f)\).1

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

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

Если максимальная грань \(N_K\) содержит хотя бы одну нерегулярную точку, она сама нерегулярна. Тогда по теореме соответствующая простая импликанта K встречается хотя бы в одной тупиковой ДНФ и входит в ΣT. Если же каждая точка \(N_K\) регулярна, K в ΣT не входит.

Частые ошибки
  • Перепутать знак критерия. В ΣT входят импликанты нерегулярных, а не регулярных граней.
  • Смешивать ΣT и ∩T. Первая собирает члены хотя бы одной тупиковой ДНФ, вторая — члены всех тупиковых ДНФ.
  • Понимать «локальность» как свойство отдельных переменных. Речь идёт об окрестностях максимальных граней.

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

Источники

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