Алгоритм построения всех тупиковых покрытий и всех тупиковых ДНФ

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

Каждое найденное покрытие строк i1,…,ir переводится обратно в тупиковую ДНФ \(K_i1\vee \ldots \vee K_ir\) исходной функции. Ядровые и регулярные грани можно использовать для предварительного уменьшения задачи покрытия.1

Что важно запомнить
  1. Построить все простые импликанты f и сокращённую ДНФ.
  2. Составить таблицу Квайна.
  3. Записать КНФ функции покрытия по столбцам таблицы.
  4. Раскрыть скобки, привести подобные и выполнить поглощения.
  5. Каждый оставшийся конъюнкт \(y_i1\ldots y_ir\) перевести в ДНФ \(K_i1\vee \ldots \vee K_ir\).1

Шаг 1. Построение таблицы Квайна

Нужно знать полное множество простых импликант функции f. Они образуют строки таблицы Квайна, а столбцы соответствуют всем \(\alpha\in N_f\). Единица на пересечении означает, что данная импликанта покрывает данный единичный набор.1

Шаг 2. Функция покрытия

Пусть \(y_i\) означает выбор i-й строки. Для каждого столбца j записывают дизъюнкцию всех \(y_i\), для которых M[i,j]=1. Конъюнкция таких дизъюнкций по всем столбцам и есть функция покрытия:

\(F(y)=\bigwedge_j(\bigvee_{i:M[i,j]=1}y_i)\). 1

Шаг 3. Перечисление тупиковых покрытий

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

Шаг 4. Возврат к ДНФ функции f

Если простая импликанта функции покрытия имеет вид \(y_i1\ldots y_ir\), то строки i1,…,ir образуют тупиковое покрытие таблицы Квайна. Следовательно, ДНФ \(K_i1\vee \ldots \vee K_ir\) является тупиковой ДНФ f. Повторив это для всех конъюнктов сокращённой ДНФ F, получаем все тупиковые ДНФ.1

Размер задачи иногда уменьшают заранее. Ядровые грани входят во все тупиковые ДНФ, а регулярные не входят ни в одну. После их учёта остаётся меньшая задача покрытия для нерешённой части \(N_f\).1

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

В примере из предыдущего вопроса функция покрытия после сокращения равна y1y2∨y1y3∨y2y3. Поэтому алгоритм сразу выдаёт три тупиковых покрытия: {1,2}, {1,3}, {2,3}. Если строки таблицы Квайна соответствуют K1,K2,K3, то тупиковые ДНФ равны K1∨K2, K1∨K3 и K2∨K3.

Частые ошибки
  • Останавливать раскрытие КНФ до удаления поглощений. Тогда будут перечислены и нетупиковые покрытия.
  • Выбирать только покрытие минимальной длины. Вопрос требует построить все тупиковые покрытия, а не только кратчайшее.
  • Забывать, что строки таблицы Квайна должны соответствовать всем простым импликантам f.

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

Источники

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