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

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

Наиболее распространенным базисом является набор трех функций: конъюнкции (Ù или & – И), дизъюнкции (Ú – ИЛИ) и инверсии (Ø – НЕ). Функционально полными являются также системы, состоящие из двух логических функций: дизъюнкции (ИЛИ) и инверсии (НЕ), либо конъюнкции (И) и инверсии (НЕ). Функциональной полнотой обладают системы, состоящие только из одной логической функции: инверсии конъюнкции (И-НЕ) или инверсии дизъюнкции (ИЛИ-НЕ). Существуют также другие функционально полные системы логических функций.

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

1. Коммутативный (переместительный) закон:

x₁·x₂ = x₂·x₁; x₁Úx₂ = x₂Úx₁;

2. Ассоциативный (сочетательный) закон:

(x₁·x₂)·x₃ = (x₁·x₃) ·x₂ = x₁·(x₂·x₃); (x₁Úx₂)Úx₃ = x₁Ú(x₂Úx₃);

Эти законы идентичны аналогичным законам обычной алгебры.

3. Дистрибутивный (распределительный) закон:

x₁·(x₂Úx₃) = x₁·x₂Úx₁·x₃; x₁Úx₂·x₃ = (x₁Úx₂) ·(x₁Úx₃);

4. Закон поглощения. В дизъюнктивной форме логической функции конъюнкция мень­шего ранга, т.е. с меньшим числом переменных, поглощает все конъ­юнкции большего ранга, если ее изображение содержится в них. Это же справедливо и для конъюнктивных форм:

x₁Úx₁·x₂ = x₁; x₁·(x₁Úx₂) = x₁;

5. Закон склеивания:

;

6. Правило де Моргана:

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

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

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

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

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

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

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

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

Рис. 1.2.11. Схемы реализации логических функций И, ИЛИ и НЕ.

Таким образом можно построить техническое устройство, имеющее ми­нимальные аппаратные затраты.