Русская Википедия:Метод Куайна

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

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

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

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

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

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

Операция склеивания сводится к нахождению пар членов, соответствующих виду <math>w \cdot x</math> или <math>w \cdot \overline{x}</math>, и преобразованию их в следующие выражения: <math>w \cdot x \lor w \cdot \overline{x} = w \cdot (x \lor \overline{x}) = w</math>. Результаты склеивания <math>w</math> теперь играют роль дополнительных членов. Необходимо найти все возможные пары членов (каждый член с каждым).

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

<math>x_1</math> <math>x_2</math> <math>x_3</math> <math>f(x_1, x_2, x_3)</math>
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

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

<math>f(x_1, x_2, x_3) = \overline{x_1} \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot \overline{x_3} \lor x_1 \cdot \overline{x_2} \cdot x_3 \lor x_1 \cdot x_2 \cdot \overline{x_3} \lor x_1 \cdot x_2 \cdot x_3</math>

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

<math>

f(x_1, x_2, x_3) = \cancel{\overline{x_1} \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot \overline{x_3}} \vee \cancel{x_1 \cdot \overline{x_2} \cdot x_3} \vee \cancel{x_1 \cdot x_2 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_2 \cdot x_3} = x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2 </math>

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

<math>

x_2 \cdot \overline{x_3} \vee x_1 \cdot \overline{x_2} \vee x_1 \cdot \overline{x_3} \vee x_1 \cdot x_3 \vee x_1 \cdot x_2

</math>

Член <math>x_2 \cdot \overline{x_3}</math> поглощает те члены исходного выражения, которые содержат <math>x_2 \cdot \overline{x_3}</math>, то есть первый и четвёртый. Эти члены вычёркиваются. Член <math>x_1 \cdot \overline{x_2}</math> поглощает второй и третий, а член <math>x_1 \cdot x_3</math> — пятый член исходного выражения.

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

<math>

f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \vee \cancel{x_1 \cdot \overline{x_2}} \vee \cancel{x_1 \cdot \overline{x_3}} \vee \cancel{x_1 \cdot x_3} \vee \cancel{x_1 \cdot x_2} \vee x_1

</math>

Здесь склеивается пара членов <math>x_1 \cdot \overline{x_2}</math> и <math>x_1 \cdot x_2</math> (склеивание пары членов <math>x_1 \cdot \overline{x_3}</math> и <math>x_1 \cdot x_3</math> приводит к тому же результату), результат склеивания <math>x_1</math> поглощает 2-, 3-, 4-, 5-й члены выражения. Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращённая форма выражения заданной функции (в данном случае она совпадает с минимальной формой)

<math>f(x_1, x_2, x_3) = x_2 \cdot \overline{x_3} \lor x_1</math>
Файл:Структурная схема логического устройства на базисе И, ИЛИ, НЕ при минимизации функции методом Квайна.PNG
Структурная схема функции

Члены сокращённой формы (в нашем случае это <math>x_2 \cdot \overline{x_3}</math> и <math>x_1</math>) называются простыми импликантами функции. В итоге, мы получили наиболее простое выражение, если сравнивать его с начальной версией — СДНФ. Структурная схема такого элемента показана на рисунке справа.

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

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

<math>x_1</math> <math>x_2</math> <math>x_3</math> <math>x_4</math> <math>f(x_1, x_2, x_3, x_4)</math>
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

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

<math>

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot{x_4} \vee \overline{x_1} \cdot \overline{x_2} \cdot{x_3} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3 \cdot x_4

</math>
<math>

\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4} \vee \overline{x_1} \cdot x_3 \cdot \overline{x_4} \vee x_2 \cdot x_3 \cdot \overline{x_4} \vee x_1 \cdot x_2 \cdot x_3

</math>

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

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

Члены СДНФ заданной функции вписываются в столбцы, а в строки — простые импликанты, то есть члены сокращённой формы. Отмечаются столбцы членов СДНФ, которые поглощаются отдельными простыми импликантами. В следующей таблице простая импликанта <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3}</math> поглощает члены <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot \overline{x_4}</math> и <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4</math> (в первом и во втором столбцах поставлены крестики).

Простая импликанта   <math>\overline{x_1} \cdot \overline{x_2} \cdot\overline{x_3} \cdot \overline{x_4}</math> <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \cdot x_4</math> <math>\overline{x_1} \cdot \overline{x_2} \cdot x_3 \cdot \overline{x_4}</math> <math>\overline{x_1} \cdot x_2 \cdot x_3 \cdot \overline{x_4}</math> <math>x_1 \cdot x_2 \cdot x_3 \cdot \overline{x_4}</math> <math>x_1 \cdot x_2 \cdot x_3 \cdot x_4</math>
<math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3}</math> <math>\times</math> <math>\times</math>
<math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}</math> <math>\times</math> <math>\times</math>
<math>\overline{x_1} \cdot x_3 \cdot \overline{x_4}</math> <math>\times</math> <math>\times</math>
<math>x_2 \cdot x_3 \cdot \overline{x_4}</math> <math>\times</math> <math>\times</math>
<math>x_1 \cdot x_2 \cdot x_3</math> <math>\times</math> <math>\times</math>

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

В нашем примере ядро составляют импликанты <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3}</math> и <math>x_1 \cdot x_2 \cdot x_3</math> (ими перекрываются второй и шестой столбцы). Исключение из сокращённой формы одновременно всех импликант, не входящих в ядро, невозможно, так как исключение одной из импликант может превратить другую в уже нелишний член.
Для получения минимальной формы достаточно выбрать из импликантов, не входящих в ядро, такое минимальное их число с минимальным количеством букв в каждом из этих импликант, которое обеспечит перекрытие всех столбцов, не перекрытых членами ядра. В рассматриваемом примере необходимо импликантами, не входящими в ядро, перекрыть третий и четвёртый столбцы матрицы. Это может быть достигнуто различными способами, но так как необходимо выбирать минимальное число импликант, то, очевидно, для перекрытия этих столбцов следует выбрать импликанту <math>\overline{x_1} \cdot x_3 \cdot \overline{x_4}</math>.

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

Файл:Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна.PNG
Структурная схема, соответствующая выражению в МДНФ (второй этап) при минимизации функции методом Квайна
<math>

f(x_1, x_2, x_3, x_4) = \overline{x_1} \cdot \overline{x_2} \cdot \overline{x_3} \vee x_1 \cdot x_2 \cdot x_3

\vee \overline{x_1} \cdot x_3 \cdot \overline{x_4}</math>       (а)

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}</math> и <math>x_2 \cdot x_3 \cdot \overline{x_4}</math>. Покажем допустимость подобного исключения членов из логического выражения.

Импликанты <math>\overline{x_1} \cdot \overline{x_2} \cdot \overline{x_4}</math> и <math>x_2 \cdot x_3 \cdot \overline{x_4}</math> становятся равными лог. 1 соответственно при следующих наборах значений аргументов: <math>x_1 = 0</math>, <math>x_2 = 0</math>, <math>x_4 = 0</math> и <math>x_2 = 1</math>, <math>x_3 = 1</math>, <math>x_4 = 0</math>.

Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции <math>f(x_1, x_2, x_3, x_4)</math> значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

  • при <math>x_1 = 0</math>, <math>x_2 = 0</math>, <math>x_4 = 0</math>

<math>f(0, 0, x_3, 0) = 1 \cdot 1 \cdot \overline{x_3} \vee 0 \cdot 0 \cdot x_3 \vee 1 \cdot x_3 \cdot 1 = \overline{x_3} \vee x_3 = 1</math>;

  • при <math>x_2 = 1</math>, <math>x_3 = 1</math>, <math>x_4 = 0</math>

<math>f(x_1, 1, 1, 0) = \overline{x_1} \cdot 0 \cdot 0 \vee x_1 \cdot 1 \cdot 1 \vee \overline{x_1} \cdot 1 \cdot 1 = x_1 \vee \overline{x_1} = 1</math>;

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

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

  • для минимизации берётся не СДНФ, а СКНФ функции;
  • склеиваемые пары членов меняются на: <math>w \vee x</math> или <math>w \vee \overline{x}</math>;
  • правило операции поглощения выглядит следующим образом:

<math>z \cdot (z \vee y) = z \vee z \cdot y = z \cdot (1 \vee y) = z</math>

См. также

Примечания

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

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Краткое описание метода Квайна Шаблон:Wayback www.ptca.narod.ru
  2. ↑ Лекция: Минимизация ФАЛ Шаблон:Wayback www.works.tarefer.ru
  3. ↑ Пример минимизации переключательной функции методом Квайна Шаблон:Wayback matri-tri-ca.narod.ru
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Метод_Куайна&oldid=10372923