Метод Куайна

Материал из testwiki
Перейти к навигации Перейти к поиску

Метод Куайна — способ представления функции в ДНФ или КНФ с минимальным количеством членов и минимальным набором переменных.[1][2][3]
Преобразование функции можно разделить на два этапа:

  • на первом этапе осуществляется переход от совершенной формы (СДНФ или СКНФ) к так называемой сокращённой форме;
  • на втором этапе — переход от сокращённой формы к минимальной форме.

Первый этап (получение сокращённой формы)

Представим, что заданная функция f представлена в СДНФ. Для осуществления первого этапа преобразование проходит два действия:

  1. Операция склеивания;
  2. Операция поглощения.

Операция склеивания сводится к нахождению пар членов, соответствующих виду w⋅x или w⋅x‾, и преобразованию их в следующие выражения: w⋅x∨w⋅x‾=w⋅(x∨x‾)=w. Результаты склеивания w теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).

Потом выполняется операция поглощения. Она основана на равенстве w∨w⋅z=w⋅(1∨z)=w (член w поглощает выражение w⋅z). Вследствие этого действия из логического выражения вычёркиваются все члены, поглощаемые другими переменными, результаты которых получены в операции склеивания.
Обе операции первого этапа могут выполняться до тех пор, пока это может быть осуществимо.
Применение этих операций продемонстрировано в таблице:

x1 x2 x3 f(x1,x2,x3)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1

СДНФ выглядит так:

f(x1,x2,x3)=x1‾⋅x2⋅x3‾∨x1⋅x2‾⋅x3‾∨x1⋅x2‾⋅x3∨x1⋅x2⋅x3‾∨x1⋅x2⋅x3

Результат операции склеивания нужен для преобразования функции на втором этапе (поглощения)

f(x1,x2,x3)=x1‾⋅x2⋅x3‾∨x1⋅x2‾⋅x3‾∨x1⋅x2‾⋅x3∨x1⋅x2⋅x3‾∨x1⋅x2⋅x3=x2⋅x3‾∨x1⋅x2‾∨x1⋅x3‾∨x1⋅x3∨x1⋅x2

Членами результата склеивания являются

x2⋅x3‾∨x1⋅x2‾∨x1⋅x3‾∨x1⋅x3∨x1⋅x2

Член x2⋅x3‾ поглощает те члены исходного выражения, которые содержат x2⋅x3‾, то есть первый и четвёртый. Эти члены вычёркиваются. Член x1⋅x2‾ поглощает второй и третий, а член x1⋅x3 — пятый член исходного выражения.

Повторение обеих операций приводит к следующему выражению:

f(x1,x2,x3)=x2⋅x3‾∨x1⋅x2‾∨x1⋅x3‾∨x1⋅x3∨x1⋅x2∨x1

Здесь склеивается пара членов x1⋅x2‾ и x1⋅x2 (склеивание пары членов x1⋅x3‾ и x1⋅x3 приводит к тому же результату), результат склеивания x1 поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

f(x1,x2,x3)=x2⋅x3‾∨x1
Файл:Структурная схема логического устройства на базисе И, ИЛИ, НЕ при минимизации функции методом Квайна.PNG
Структурная схема функции

Члены сокращённой формы (в нашем случае это x2⋅x3‾ и x1) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.

Второй этап (табличный) (получение минимальной формы)

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

x1 x2 x3 x4 f(x1,x2,x3,x4)
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

СДНФ, собранная по этой таблице выглядит следующим образом:

f(x1,x2,x3,x4)=x1‾⋅x2‾⋅x3‾⋅x4‾∨x1‾⋅x2‾⋅x3‾⋅x4∨x1‾⋅x2‾⋅x3⋅x4‾∨x1‾⋅x2⋅x3⋅x4‾∨x1⋅x2⋅x3⋅x4‾∨x1⋅x2⋅x3⋅x4
x1‾⋅x2‾⋅x3‾∨x1‾⋅x2‾⋅x4‾∨x1‾⋅x3⋅x4‾∨x2⋅x3⋅x4‾∨x1⋅x2⋅x3

Члены этого выражения являются простыми импликантами выражения. Переход от сокращённой формы к минимальной осуществляется с помощью импликантной матрицы.

Импликантная матрица

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта x1‾⋅x2‾⋅x3‾ поглощает члены x1‾⋅x2‾⋅x3‾⋅x4‾ и x1‾⋅x2‾⋅x3‾⋅x4 (в первом и во втором столбцах поставлены крестики).

Простая импликанта   x1‾⋅x2‾⋅x3‾⋅x4‾ x1‾⋅x2‾⋅x3‾⋅x4 x1‾⋅x2‾⋅x3⋅x4‾ x1‾⋅x2⋅x3⋅x4‾ x1⋅x2⋅x3⋅x4‾ x1⋅x2⋅x3⋅x4
x1‾⋅x2‾⋅x3‾ × ×
x1‾⋅x2‾⋅x4‾ × ×
x1‾⋅x3⋅x4‾ × ×
x2⋅x3⋅x4‾ × ×
x1⋅x2⋅x3 × ×

Вторая импликанта поглощает первый и третий члены СДНФ (указано крестиками) и т. д. Импликанты, не подлежащие исключению, образуют ядро. Такие импликанты определяются по вышеуказанной матрице. Для каждой из них имеется хотя бы один столбец, перекрываемый только этой импликантой.

В нашем примере ядро составляют импликанты x1‾⋅x2‾⋅x3‾ и x1⋅x2⋅x3 (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту x1‾⋅x3⋅x4‾.

Минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции:

Файл:Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна.PNG
Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна
f(x1,x2,x3,x4)=x1‾⋅x2‾⋅x3‾∨x1⋅x2⋅x3∨x1‾⋅x3⋅x4‾       (а)

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант x1‾⋅x2‾⋅x4‾ и x2⋅x3⋅x4‾. Покажем допустимость подобного исключения членов из логического выражения.

Импликанты x1‾⋅x2‾⋅x4‾ и x2⋅x3⋅x4‾ становятся равными лог. 1 соответственно при следующих наборах значений аргументов: x1=0, x2=0, x4=0 и x2=1, x3=1, x4=0.

Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции f(x1,x2,x3,x4) значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

  • при x1=0, x2=0, x4=0

f(0,0,x3,0)=1⋅1⋅x3‾∨0⋅0⋅x3∨1⋅x3⋅1=x3‾∨x3=1;

  • при x2=1, x3=1, x4=0

f(x1,1,1,0)=x1‾⋅0⋅0∨x1⋅1⋅1∨x1‾⋅1⋅1=x1∨x1‾=1;

Использование метода для получения минимальной КНФ

Для получения Минимальной конъюнктивной нормальной формы (МКНФ), используя метод Куайна, вводятся следующие критерии:

  • для минимизации берётся не СДНФ, а СКНФ функции;
  • склеиваемые пары членов меняются на: w∨x или w∨x‾;
  • правило операции поглощения выглядит следующим образом:

z⋅(z∨y)=z∨z⋅y=z⋅(1∨y)=z

См. также

Примечания

Шаблон:Примечания

  1. ↑ Краткое описание метода Квайна Шаблон:Wayback www.ptca.narod.ru
  2. ↑ Лекция: Минимизация ФАЛ Шаблон:Wayback www.works.tarefer.ru
  3. ↑ Пример минимизации переключательной функции методом Квайна Шаблон:Wayback matri-tri-ca.narod.ru
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Метод_Куайна&oldid=7035