Минимизация полностью определённой ФАЛ

При минимизации ФАЛ с помощью карт Вейча – Карно используются либо единичные, либо нулевые значения функции. В обоих случаях получаются равносильные выражения, которые, однако, могут отличаться по числу ЛЭ и выполняемым логическим операциям.

В п.1.5 отмечено, что ФАЛ называется полностью определённой, если заданы все 2ⁿ её значений y_i. Алгоритм минимизации такой ФАЛ с помощью карт Вейча – Карно следующий:

1) на карте, построенной для ФАЛ, содержащей n-переменных, выделяют прямоугольные области, объединяющие выбранные значения (0 или 1) функции. Каждая область может содержать только 2^k клеток, где k – целое число. Выделенные области могут пересекаться, то есть одна или несколько клеток могут принадлежать разным областям.

2) каждой из выделенных областей соответствует самостоятельное логическое произведение входных переменных, значения которых в пределах выделенной области остаются неизменными. Каждое такое произведение содержит (n – k) переменных и называется импликанта.

3) из полученного множества областей выбирают минимальное число максимально больших, включающих в себя все выбранные значения (0 или 1) функции.

4) логически суммируются импликанты, соответствующие выбранным областям. Полученная функция образует МДНФ.

При объединении клеток с единичными значениями ФАЛ получается МДНФ самой функции, а при объединении клеток с нулевыми значениями – МДНФ функции, инверсной заданной.

Применив к полученной инверсной МДНФ теоремы Де-Моргана можно получить минимальную конъюнктивно нормальную функцию (МКНФ).

Рассмотрим пример минимизации ФАЛ, заданной алгебраическим выражением:

.                (2.3)

Выделим на карте покрытие, содержащее все единичные значения ФАЛ (выделено пунктиром). Запишем для него значение импликанты, которая будет единственным слагаемым в МДНФ: Y = X2.

Если объединить нулевые значения функции (выделено штрих пунктиром), получим МДНФ, инверсную заданной:  или Y = X2. В данном простом примере в обоих случаях получилось одно и то же выражение.

Рассмотрим другой пример минимизации ФАЛ, заданной алгебраическим выражением [1]:

.     (2.4)

Выделим на карте две области, содержащие все единичные значения ФАЛ (выделено пунктиром). Запишем МДНФ как логическую сумму двух импликант: .

Выделим на карте две области, содержащие все нулевые значения ФАЛ (выделено штрих пунктиром). Запишем МДНФ, инверсную заданной, как логическую сумму двух импликант: .

Получились равносильные, но разные выражения. Чтобы доказать равносильность выражений, применим к МДНФ, инверсной заданной, теорему Де-Моргана:

.

Применив к данному выражению теорему №10 (см таблицу 7), получим ФАЛ .

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