Функция покрытия и таблица Квайна в задаче минимизации ДНФ

Задачу минимизации ДНФ удобно свести к задаче покрытия. Для матрицы \(M\in B^{p,s}\) выбирают строки так, чтобы каждый столбец содержал единицу хотя бы в одной выбранной строке. Функция покрытия \(F(y_{1},\ldots,y_p)\) равна 1 ровно для тех наборов y, которые задают такое покрытие.1

Для булевой функции f строят таблицу Квайна: её строки соответствуют простым импликантам, столбцы — единичным наборам f, а \(M[i,j]=1\) означает, что импликанта \(K_i\) покрывает набор \(\alpha_j\). Тогда тупиковые ДНФ f взаимно соответствуют тупиковым покрытиям этой таблицы.1

Что важно запомнить
  • Функция покрытия матрицы монотонна.
  • Её нижние единицы и простые импликанты соответствуют тупиковым покрытиям.
  • Таблица Квайна — матрица инцидентности «простая импликанта ↔ единичный набор функции».
  • Минимизация ДНФ после построения простых импликант превращается в задачу выбора подходящего покрытия таблицы Квайна.1

Функция покрытия

Пусть множество \(N=\{\alpha_{1},\ldots,\alpha_s\}\) покрывается системой подмножеств \(N_{1},\ldots,N_p\). Этой системе сопоставляют матрицу \(M\in B^{p,s}\): элемент M[i,j] равен 1 тогда и только тогда, когда \(\alpha_j\in N_i\). Набор строк I покрывает M, если в каждом столбце имеется единица хотя бы в одной строке из I. Покрытие называют тупиковым, если никакое его собственное подмножество уже не является покрытием.1

Каждой строке i сопоставим переменную \(y_i\). Функция покрытия \(F(y_{1},\ldots,y_p)\) принимает значение 1 тогда и только тогда, когда строки с \(y_i=1\) покрывают все столбцы. Для неё справедливо представление

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

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

Таблица Квайна

Для функции f берут \(N=N_f\), а в качестве покрывающих множеств — все максимальные грани \(N_f\), то есть множества единиц всех простых импликант \(K_{1},\ldots,K_p\). Матрица инцидентности этого покрытия называется таблицей Квайна. Строка i показывает, какие единичные наборы покрывает \(K_i\).1

Если строки \(i_{1},\ldots,i_r\) образуют тупиковое покрытие таблицы Квайна, то \(K_{i_{1}}\vee \ldots \vee K_{i_r}\) является тупиковой ДНФ функции f. Обратно, любая тупиковая ДНФ состоит из простых импликант и задаёт тупиковое покрытие таблицы. Поэтому после построения сокращённой ДНФ задача перечисления и последующего сравнения тупиковых ДНФ становится чистой задачей о покрытиях.1

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

Пусть три строки матрицы покрывают столбцы так: первая — 1 и 2, вторая — 2 и 3, третья — 1 и 3. Тогда функция покрытия равна \((y_{1}\vee y_{3})(y_{1}\vee y_{2})(y_{2}\vee y_{3})\). После раскрытия и поглощений получаем \(y_{1}y_{2}\vee y_{1}y_{3}\vee y_{2}y_{3}\). Значит, существуют ровно три тупиковых покрытия из двух строк. В таблице Квайна эти три покрытия дали бы три тупиковые ДНФ.

Частые ошибки
  • Путать простую импликанту функции f с простой импликантой функции покрытия F. У них разные переменные и разный смысл.
  • Считать любое покрытие таблицы Квайна тупиковым. В тупиковом покрытии нельзя удалить ни одну выбранную строку.
  • Считать таблицу Квайна готовым решением задачи минимизации. Она лишь переводит выбор ДНФ в задачу покрытия.

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

Источники

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