Минимизация логических функций методом Квайна


Минимизация логических функций методом Квайна

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

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

Содержание

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

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

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

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

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

\mathbf{x_1}
         0                   0                   0                    0                   1                   1                   1                   1         
\mathbf{x_2}
         0                   0                   1                   1                   0                   0                   1                   1         
\mathbf{x_3}
         0                   1                   0                   1                   0                   1                   0                   1         
\mathbf{f}({x_1},{x_2},{x_3})
         0                   0                   1                   0                   1                   1                   1                   1         

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

\mathbf{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}

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

Файл:Результат склеивания функции при минимизации, метод Квайна.PNG


Членами результата склеивания являются Файл:Члены результата склеивания функции при минимизации, метод Квайна.PNG

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

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

Файл:Член операции склеивания №2, метод Квайна.PNG

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

\mathbf{f}({x_1},{x_2},{x_3})={x_2}\cdot\overline{x_3} \lor{x_1}
Структурная схема функции

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

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

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

\mathbf{x_1}
   0       0       0       0       0       0       0       0       1       1       1       1       1       1       1       1   
\mathbf{x_2}
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
\mathbf{x_3}
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
\mathbf{x_4}
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
\mathbf{f}({x_1},{x_2},{x_3},{x_4})
1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1

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

\mathbf{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}

Конечное выражение достигается засчёт повторного использования операций склеивания и поглощения:

\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}

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

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

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

\times


\times

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

\times


\times

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

\times


\times

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

\times


\times

      
{x_1}\cdot{x_2}\cdot{x_3}

\times


\times

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

Нажмите на изображение для его увеличения
\mathbf{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}       (а)

Структурная схема, соответствующая этому выражению приведена на рисунке слева. Переход от сокращённой схемы к МДНФ был осуществлён путём исключения лишних членов — импликант \overline{x_1}\cdot\overline{x_2}\cdot\overline{x_4} и {x_2}\cdot{x_3}\cdot\overline{x_4}. Покажем допустимость подобного исключения членов из логического выражения.
Импликанты \overline{x_1}\cdot\overline{x_2}\cdot\overline{x_4} и {x_2}\cdot{x_3}\cdot\overline{x_4} становятся равными лог. 1 соответственно при следующих наборах значений аргументов: \mathbf{x_1} = 0, \mathbf{x_2} = 0, \mathbf{x_4} = 0 и \mathbf{x_2} = 1, \mathbf{x_3} = 1, \mathbf{x_4} = 0.
Роль этих импликант в выражении сокращённой формы функции заключается лишь в том, чтобы на приведённых наборах значений аргументов присваивать функции \mathbf{f}({x_1},{x_2},{x_3},{x_4}) значение 1. Однако при этих наборах функция равна 1 из-за остальных импликант выражения. Действительно, подставляя набор значений, указанных выше в формулу (а), получаем:

  • при \mathbf{x_1} = 0, \mathbf{x_2} = 0, \mathbf{x_4} = 0

\mathbf{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;

  • при \mathbf{x_2} = 1, \mathbf{x_3} = 1, \mathbf{x_4} = 0

\mathbf{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};

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

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

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

{z}\cdot({z}\vee{y})={z}\vee{z}\cdot{y}={z}\cdot(1\vee{y})={z}

См. также

Примечания


Wikimedia Foundation. 2010.

Смотреть что такое "Минимизация логических функций методом Квайна" в других словарях:

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

  • СДНФ — (Совершенная Дизъюнктивная Нормальная Форма)  это такая ДНФ, которая удовлетворяет трём условиям: в ней нет одинаковых элементарных конъюнкций в каждой конъюнкции нет одинаковых пропозициональных букв каждая элементарная конъюнкция содержит… …   Википедия

  • СКНФ — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактиро …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.