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

ВВЕДЕНИЕ

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

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

Устройства компьютера строятся на основе логических элементов. Элемент памяти может находиться в двух устойчивых состояниях. Одно из этих состояний можно обозначить «0», а второе — «1». Таким образом, можно считать, что такой элемент представляет собой логическую переменную. Логические операции также реализуются с помощью логических элементов.

В практической деятельности приходится решать 2 вида задач:

 анализ логических схем;

 синтез логических схем [1].

При анализе логических схем необходимо определить, какое значение будет на выходе схемы при определенных входных значениях.

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

Задача синтеза логических схем (формул) в общем случае не представляет трудностей. Более трудоемкой задачей является минимизация полученной логической формулы. Существует множество алгоритмов минимизации логических формул, в данной работе мы рассмотрим три из них и остановимся на одном, который и будет реализован.