Минимизация логических функций. Последовательность действий, выполняемых при минимизации логических функций с помощью карт Карно

Обозначают эту операцию символом Ú или знаком сложения (+) (Y=X1+X2).

      Функция  называется инверсией.

      Алгебра логики позволяет упростить сложные формулы и оптимизировать структуру логического управляющего устройства, реализующего любую сложную функцию.

      В алгебре логики имеется четыре основных закона (таблица 1): переместительный (свойство коммутативности); сочетательный (свойство ассоциативности); распределительный (свойство дистрибутивности); инверсии (правило де Моргана).

Таблица 1 – Основные законы алгебры логики

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

Таблица 2 – Основные законы алгебры логики

№ п/п	Правило	а	б
1	Инверсии
2	Неизменности	Х+0=Х	Х×1=Х
3	Универсального и нулевого множества	Х+1=1	Х×0=0
4	Повторения	Х+Х=Х	Х×Х=Х
5	Дополнительности
6	Склеивания
7

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

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

      Различают аналитические и табличные методы минимизации. Наиболее распространенным аналитическим методом является метод непосредственных тождественных преобразований.

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

            Стремление к алгоритмизации привело к разработке табличных методов минимизации логических функций. Одним из них является метод, основанный на использовании карт Карно.

Карты Карно – это графическое представление таблиц истинности логических функций. Они представляют собой таблицы, содержащие по 2ⁿ прямоугольных ячеек, где n – число логических переменных. Ячейки, в которых функция принимает значения, равные единице, заполняются единицами. В остальные ячейки записываются нули. Процесс минимизации заключается в формировании прямоугольников, которые объединяют соседние ячейки. Совокупность прямоугольников, охватывающих все единицы, называют покрытием.

Необходимо отметить следующее:

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

2.   Чем больше ячеек в прямоугольнике, тем меньше переменных содержится в соответствующем ему элементарном произведении.

            Последовательность действий, выполняемых при минимизации логических функций с помощью карт Карно:

1.Составляется таблица для n-переменных логической функции и производится разметка ее сторон.

2.  Ячейки таблицы, соответствующие наборам переменных, обращающих функцию в единицу, заполняются единицами, остальные ячейки – нулями.

3.  Выбирается наилучшее покрытие таблицы правильными прямоугольниками. Наилучшим считается такое покрытие, которое образовано минимальным числом прямоугольников, а если таких вариантов несколько, то из них выбирается тот, который дает максимальную суммарную площадь прямоугольников.

4.  Производится запись логической функции каждого прямоугольника путем суммирования функций каждой ячейки прямоугольника и её минимизация.

5.  Определяется логическая функция всего покрытия путем суммирования логических функций всех прямоугольников входящих в покрытие и её минимизация.

6.  Качество минимизации оценивается коэффициентом покрытия – k,

k=m/s

m – количество прямоугольников в покрытии

s – суммарная площадь прямоугольников

Покрытие считается тем лучше, чем меньше коэффициент покрытия k

Пример 1. (Метод тождественных преобразований)

  Преобразовать выражение (××X3 + X1×)(X1+X3),

применив законы и правила алгебры логики:

  Решение: (×X3 + X1×)( + X3)=

по закону 3:          ×X3×X1 + ×X3×X3 +

                                                 + X1××X1 + X1××X3=

по правилу 5б:     ××X3×X3 + X1××X1 + X1××X3=

по правилу 4б:     ××X3 + X1× + X1××X3=

по закону 3:          (X1 + )××X3 + X1×=

по правилу 5а:     ×X3 + X1×= ×(X3 +X1).

Пример 2

Пример 3

Пример 4. (Метод карты Карно с последующим применением метода тождественных