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

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

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

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

Операция склеивания сводится к нахождению пар членов, соответствующих виду или , и преобразованию их в следующие выражения: . Результаты склеивания w теперь играют роль дополнительных членов.

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

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


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

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

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

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

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

Структурная схема функции

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

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

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

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

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

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

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

Простая импликанта

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

Нажмите на изображение для его увеличения
(а)

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

  • при = 0, = 0, = 0

;

  • при = 1, = 1, = 0

;

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

Пусть заданная функция f представлена в СДНФ.

Переход к сокращенной форме основан на последовательном применении двух операций: операции склеивания и операции поглощения.

Для выполнения операции склеивания выявляются в выражении пары членов вида и , различающихся лишь тем, что один из аргументов в одном из членов представлен без инверсии, в другом—с инверсией. Затем проводится склеивание таких пар членов: , и резуль-таты склеивания w вводятся в выражение функции в качестве дополнительных членов. Далее проводится операция поглощения. Она основана на равенстве

(член w поглощает член w? z). При проведении этой операции из логического выражения вычеркиваются все члены, поглощаемые членами, которые введены в результате проведения операции склеивания.

Операции склеивания и поглощения проводятся последовательно до тех пор, пока их выполнение оказывается возможным.

Покажем выполнение этих операций применительно к функции, представленной в табл. 3.5.

Записываем СДНФ функции

(3.12)

Попарным сравнением членов (каждого из членов со всеми последующими) выявляем склеивающиеся пары членов:

первый и четвертый члены (результат склеивания );

второй и третий члены (результат склеивания );

второй и четвертый члены (результат склеивания );

третий и пятый члены (результат склеивания ):

четвертый и пятый члены (результат склеивания ).

Таблица 3.5

f(x1,x2,x3)

Результаты операции склеивания вводим в выражение функции и проводим операцию поглощения ими членов исходного выражения: Член поглощает те члены исходного выражения, которые содержат, т. е. первый и четвертый. Эти члены вычеркиваются. Член поглощает второй и третий, а членx1? x3 – пятый член исходного выражения.

Повторяем операции склеивания и поглощения:

Член операции склеиванияЗдесь склеивается лишь пара членов и , (склеивание пары членов и, приводит к тому же результату), результат склеивания х1, поглощает второй, третий, четвертый и пятый члены выражения.

Дальнейшее проведение операций склеивания и поглощения оказывается невозможным, сокращенная форма выражения заданной функции (в данном примере она совпадает с минимальной формой)

(3.13)

Члены сокращенной формы (в рассмотренном примере такими членами служат и х1 называются простыми импликантами функции.

Как видим, получено выражение существенно более простое по сравнению с СДНФ функции.

На рис. 3.27 приведена структурная схема логического устройства в базисе И, ИЛИ, НЕ, построенная с использованием выражения (3.13).