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

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

СОДЕРЖАНИЕ Введение 4 1 Обзор предметной области 6 2 Методы решения задачи 8 2.1 Карты Карно 9 2.2 Метод Куайна 12 2.3 Метод сочетаний 13 3 Техническая реализация 15 3.1 Структурный уровень 15 3.2 Функциональный уровень 16 3.3 Принципиальный уровень 17 ЗАКЛЮЧЕНИЕ 19 Список литературы 20

СПИСОК ЛИТЕРАТУРЫ 1) А.В. Гладкий. Математическая логика. М.: РГГУ, 1998, 480 с. 2) И. П. Норенков. Основы автоматизированного проектирования: учеб. для вузов. M.: Издательство МГТУ им. Н. Э. Баумана, 2000, 360 с. 3) В. В. Фаронов. Delphi. Программирование на языке высокого уровня: Учебник для вузов. Спб.: Питер, 2003, 640 с. 4) “Избранные вопросы булевых функций” Под редакцией С.Ф. Винокурова и Н.А. Перязева, М.: ФИЗМАТЛИТ 2001. 5) Карты Карно. Википедия – свободная энциклопедия [Электронный ресурс]. – [2010]. – Режим доступа: http://ru.wikipedia.org/wiki/Карта _Карно 6) Т. Н. Кравченко. Логические основы ЭВМ. Основные логические элементы. [Электронный ресурс]. – [2010]. – Режим доступа: http://kravchenko-t-n.narod.ru/inf_1_kurs/bilet9.htm 7) Учебное Пособие "Схемотехника. Изучение и проектирование на компьютере." [Электронный ресурс]. – [2010]. – Режим доступа: http://sheme.edu.knu.kg/contents/ch3.htm