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

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

ВВЕДЕНИЕ
Одним из значительных достижений науки и техники середины двадцатого столетия явилось создание и широкое использование электронных цифровых машин с программным управлением. Рациональное конструирование, или синтез схем для таких машин является важной задачей ученых и инженеров.
Булевы функции являются основным аппаратом для построения таких математических моделей. Теория булевых функций находит применение не только в логических системах и при синтезе различного рода схем, но и в диагностике и контроле схем, в теории кодирования, в теории конечных автоматов, в теории игр, в языках программирования и даже для математического моделирования природных процессов.
Устройства компьютера строятся на основе логических элементов. Элемент памяти может находиться в двух устойчивых состояниях. Одно из этих состояний можно обозначить «0», а второе – «1». Таким образом, можно считать, что такой элемент представляет собой логическую переменную. Логические операции также реализуются с помощью логических элементов.
В практической деятельности приходится решать 2 вида задач:
 анализ логических схем;
 синтез логических схем [1].
При анализе логических схем необходимо определить, какое значение будет на выходе схемы при определенных входных значениях.
При синтезе схем необходимо построить схему, реализующую ту или иную логическую функцию. Сначала функцию можно упростить с помощью законов алгебры логики. Затем надо определить порядок действий и каждое действие представить в виде соответствующего логического элемента.
Задача синтеза логических схем (формул) в общем случае не представляет трудностей. Более трудоемкой задачей является минимизация полученной...

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