Все тупиковые ДНФ можно получить через таблицу Квайна без перебора произвольных ДНФ. Сначала строят сокращённую ДНФ f, затем таблицу Квайна. Для этой таблицы записывают функцию покрытия F в КНФ, раскрывают её в ДНФ и устраняют повторы и поглощения. Простые импликанты F перечисляют все тупиковые
Каждое найденное покрытие строк \(i_{1},\ldots,i_r\) переводится обратно в тупиковую ДНФ \(K_{i_{1}}\vee \ldots \vee K_{i_r}\) исходной функции. Ядровые и регулярные грани можно использовать для предварительного уменьшения задачи
Что важно запомнить
- Построить все простые импликанты f и сокращённую ДНФ.
- Составить таблицу Квайна.
- Записать КНФ функции покрытия по столбцам таблицы.
- Раскрыть скобки, привести подобные и выполнить поглощения.
- Каждый оставшийся конъюнкт \(y_{i_{1}}\ldots y_{i_r}\) перевести в ДНФ
Шаг 1. Построение таблицы Квайна
Нужно знать полное множество простых импликант функции f. Они образуют строки таблицы Квайна, а столбцы соответствуют всем \(\alpha \in N_f\). Единица на пересечении означает, что данная импликанта покрывает данный единичный
Шаг 2. Функция покрытия
Пусть \(y_i\) означает выбор i-й строки. Для каждого столбца j записывают дизъюнкцию всех \(y_i\), для которых \(M[i,j]=1\). Конъюнкция таких дизъюнкций по всем столбцам и есть функция покрытия:
\(F(y)=\bigwedge_j(\bigvee_{i:M[i,j]=1}y_i)\).
Шаг 3. Перечисление тупиковых покрытий
КНФ F раскрывают в ДНФ. Затем удаляют повторяющиеся множители и поглощаемые конъюнкции. Полученная сокращённая ДНФ F состоит из всех её простых импликант. Нижние единицы F, а значит и эти простые импликанты, взаимно однозначно соответствуют тупиковым покрытиям исходной
Шаг 4. Возврат к ДНФ функции f
Если простая импликанта функции покрытия имеет вид \(y_{i_{1}}\ldots y_{i_r}\), то строки \(i_{1},\ldots,i_r\) образуют тупиковое покрытие таблицы Квайна. Следовательно, ДНФ \(K_{i_{1}}\vee \ldots \vee K_{i_r}\) является тупиковой ДНФ f. Повторив это для всех конъюнктов сокращённой ДНФ F, получаем все тупиковые
Размер задачи иногда уменьшают заранее. Ядровые грани входят во все тупиковые ДНФ, а регулярные не входят ни в одну. После их учёта остаётся меньшая задача покрытия для нерешённой части
Пример простыми словами
В примере из предыдущего вопроса функция покрытия после сокращения равна \(y_{1}y_{2}\vee y_{1}y_{3}\vee y_{2}y_{3}\). Поэтому алгоритм сразу выдаёт три тупиковых покрытия: {1,2}, {1,3}, {2,3}. Если строки таблицы Квайна соответствуют \(K_{1},K_{2},K_{3}\), то тупиковые ДНФ равны \(K_{1}\vee K_{2}, K_{1}\vee K_{3}\) и \(K_{2}\vee K_{3}\).
Частые ошибки
- Останавливать раскрытие КНФ до удаления поглощений. Тогда будут перечислены и нетупиковые покрытия.
- Выбирать только покрытие минимальной длины. Вопрос требует построить все тупиковые покрытия, а не только кратчайшее.
- Забывать, что строки таблицы Квайна должны соответствовать всем простым импликантам f.
