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

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

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

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

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

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

Каждой строке i сопоставим переменную \(y_i\). Функция покрытия F(y1,…,yp) принимает значение 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\), то есть множества единиц всех простых импликант K1,…,Kp. Матрица инцидентности этого покрытия называется таблицей Квайна. Строка i показывает, какие единичные наборы покрывает \(K_i\).1

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

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

Пусть три строки матрицы покрывают столбцы так: первая — 1 и 2, вторая — 2 и 3, третья — 1 и 3. Тогда функция покрытия равна (y1∨y3)(y1∨y2)(y2∨y3). После раскрытия и поглощений получаем y1y2∨y1y3∨y2y3. Значит, существуют ровно три тупиковых покрытия из двух строк. В таблице Квайна эти три покрытия дали бы три тупиковые ДНФ.

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

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

Источники

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