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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источники

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