ДНФ суммы минимальных ΣM функции f — дизъюнкция всех простых импликант, которые входят хотя бы в одну минимальную ДНФ этой функции. Это объект, описывающий весь набор простых импликант, способных участвовать в глобально минимальных по рангу
Теорема Ю. И. Журавлёва показывает, что принадлежность простой импликанты к ΣM не обладает той же локальностью, что принадлежность к ΣT: при любом n≥3 существуют две функции с общей простой импликантой K и одинаковой окрестностью K порядка n−3, но K входит в ΣM только одной из этих
Что важно запомнить
- ΣM объединяет члены всех минимальных ДНФ, а не является одной выбранной минимальной ДНФ.
- ΣM и ΣT в общем случае различаются.
- Для цепных функций нечётной длины ΣM может быть существенно уже ΣT.
- Теорема Журавлёва показывает нелокальность критерия вхождения в
Определение ΣM
Пусть функция f имеет несколько минимальных ДНФ. Рассмотрим все простые импликанты, встречающиеся хотя бы в одной из них. Их дизъюнкция называется ДНФ суммы минимальных и обозначается ΣM. Поскольку минимальная ДНФ является тупиковой, всегда выполняется включение множества её членов в ΣT, но обратное включение для ΣM не обязано
Почему ΣM и ΣT различаются
В лекциях используется класс цепных функций. Их сокращённая ДНФ геометрически представляет цепь последовательно соединённых рёбер куба. Для цепной функции нечётной длины 2k−1 существует единственная минимальная ДНФ, состоящая из чередующихся рёбер \(N1\vee N3\vee \ldots \vee N_{2k-1}\). При длине не меньше 5 ДНФ \(\Sigma T\) совпадает со всей сокращённой ДНФ, а ΣM содержит только рёбра этой единственной минимальной
Теорема Ю. И. Журавлёва
Для любого n≥3 существуют функции f′ и f″ от n переменных и общая простая импликанта K такие, что
\(S_{n-3}(N_K,f')=S_{n-3}(N_K,f'')\),
но K входит в ΣM одной функции и не входит в ΣM
Следовательно, даже знание большой локальной окрестности максимальной грани может быть недостаточно, чтобы решить, участвует ли соответствующая импликанта хотя бы в одной минимальной ДНФ. Это принципиально отличается от ΣT, для которой критерий вхождения определяется окрестностью второго порядка.
Пример простыми словами
Рассмотрим цепную функцию, сокращённая ДНФ которой состоит из пяти последовательно соединённых рёбер K₁,K₂,K₃,K₄,K₅. Для такой нечётной цепи единственная минимальная ДНФ содержит чередующиеся рёбра: \(\Sigma M = K_{1}\lor K_{3}\lor K_{5}\). При этом все пять рёбер входят хотя бы в одну тупиковую ДНФ, поэтому \(\Sigma T = K_{1}\lor K_{2}\lor K_{3}\lor K_{4}\lor K_{5}\). На этом примере видно, что ΣM может быть существенно уже
Частые ошибки
- Отождествлять ΣM с конкретной минимальной ДНФ. ΣM объединяет члены всех минимальных ДНФ.
- Считать, что ΣM всегда совпадает с ΣT. Цепные функции дают явные контрпримеры.
- Переносить локальный критерий для ΣT на ΣM. Теорема Журавлёва как раз показывает, что такой перенос неверен.
