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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное учреждение

Высшего профессионального образования «Омский государственный институт сервиса»

(ФГБОУ ВПО «ОГИС»)

Курсовая работа

По дисциплине: Анализ эффективности информационных систем

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

Выполнила: студентка 71-ПИ

Гр. Адова Кристина Евгеньевна

Руководитель работы

Калиберда Елена Анатольевна

к.т.н., доцент

Омск 2011г.



ВВЕДЕНИЕ

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

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

Каждый из нас стремится что-то минимизировать, к примеру, минимизировать время на выполнение какой-либо работы, минимизировать затраты на что-либо, минимизировать объем каких-либо документов и т.д.

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

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

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

Для достижения данной цели необходимо:

1. Определить понятия логической функции и минимизации;

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

3. Выделить сходства и различия данных методов;

4. Определить недостатки и преимущества каждого метода.



ГЛАВА 1. ВВЕДЕНИЕ В АЛГЕБРУ ЛОГИКИ

1.1 ПОНЯТИЕ ЛОГИЧЕСКОЙ ФУНКЦИИ И МЕТОДОВ МИНИМИЗАЦИИ

Логическая функция - это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

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

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

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

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

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

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

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

1.2 МЕТОДЫ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ

Существует два направления минимизации:

Ш Кратчайшая форма записи (цель - минимизировать ранг каждого терма);

Ш Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).

1. Метод эквивалентных преобразований

В основе метода минимизации булевых функций эквивалентными преобразованиями лежит последовательное использование законов булевой алгебры. Метод эквивалентных преобразований целесообразно использовать лишь для простых функций и для количества логических переменных не более 4-х. При большем числе переменных и сложной функции вероятность ошибок при преобразовании возрастает. [1]

Пример

(1)

2. Метод Квайна.

При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде СДНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант. [2]

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

Для этого:

Ш Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.

Ш Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.

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

Алгоритм метода Квайна (шаги):

1. Нахождение первичных импликант (исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз, непомеченные импликанты переходят в функции на этом шаге).

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

3. Нахождение существенных импликант (если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным).

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

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

6. Результат записывается в виде функции.

Пример.

Пусть задана функция:

(2)

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции F каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2) конституента 2 с конституентой 4 и т. д. В результате получаем:

(3)

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

(4)

(5)

с появлением одного и того же элементарного произведения . Дальнейшие склеивания невозможны. Произведя поглощения (из полученной ДНФ вычеркиваем все поглощаемые элементарные произведения), получим сокращенную ДНФ:

(6)

Переходим к следующему этапу. Для получения минимальной ДНФ необходимо убрать из сокращенной ДНФ все лишние простые импликанты. Это делается с помощью специальной импликантной матрицы Квайна. Строки такой матрицы отмечаются простыми импликантами булевой функции, т. е. членами сокращенной ДНФ, а столбцы -- конституентами единицы, т. е. членами СДНФ булевой функции.

Импликантная матрица имеет вид см. табл. 1.1

Таблица 1.1 Импликантная матрица

Простые импликанты	Конституенты единицы

Как уже отмечалось, простая импликанта поглощает некоторую конституенту единицы, если является ее собственной частью. Соответствующая клетка импликантной матрицы на пересечении строки (с рассматриваемой простой импликантой) и столбца (с конституентой единицы) отмечается крестиком (табл. 1.). Минимальные ДНФ строятся по импликантной матрице следующим образом:

1. ищутся столбцы импликантной матрицы, имеющие только один крестик. Соответствующие этим крестикам простые импликанты называются базисными и составляют так называемое ядро булевой функции. Ядро обязательно входит в минимальную ДНФ.

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

Следовательно функция имеет вид:

(7)

3. Метод Квайна-Мак-Класки.

Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Формализация производится следующим образом:

1. Все конституенты единицы из СДНФ булевой функции F записываются их двоичными номерами.

2. Все номера разбиваются на непересекающиеся группы. Признак образования і-й группы: і единиц в каждом двоичном номере конституенты единицы.

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

4. Склеивания производят всевозможные, как и в методе Квайна. Неотмеченные после склеивания номера являются простыми импликантами.

Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна.

Пример.

(8)

Образуем группы двоичных номеров. Признаком образования і-й группы является і единиц в двоичном номере конституенты единицы (табл.1.2).

Таблица 1.2 Группы двоичных номеров

Номер группы	Двоичные номера конституент 1
0	-
1	0001 *
2	0011 *
	0101 *
3	0111 *
	1110 *
4	1111 *



Склеим номера из соседних групп табл. 1. Склеиваемые номера обозначим звездочками (номер отмечается в том случае, если участвует в склеивании хотя бы один раз). На месте разрядов, по которым произошло склеивание, проставляются прочерки. Результаты склеивания занесем в табл. 1.3

Таблица 1.3 Результаты склеивания

Номер группы	Двоичные номера конституент 1
1 (1-2)	00-1 *
	0-01 *
2 (2-3)	0-11 *
	01-1 *
3 (3-4)	-111
	111-

Склеим номера из соседних групп табл. 1.3 Склеиваться могут только номера, имеющие прочерки в одинаковых позициях. Склеиваемые номера отметим. Результаты склеивания занесем в табл. 1.4.

Таблица 1.4 Результаты склеивания 2

Номер группы	Двоичные номера конституент 1
1	0--1
	0--1
2	-111
	111-

Имеем три простые импликанты: -111, 111-, 0--1.

Строим импликантную матрицу (табл. 1.5).

логический функция минимизация квайн



Таблица 1.5 Импликантная матрица

Простые импликанты	Конституенты единицы
(0--1)
(-111)
(111-)

По табл. 5. определяем совокупность простых импликант - 0--1 и 111-, соответствующую минимальной ДНФ. Для восстановления буквенного вида простой импликанты достаточно выписать произведения тех переменных, которые соответствуют сохранившимся двоичным цифрам:

(9)

Разбиение конституент на группы позволяет уменьшить число попарных сравнений при склеивании.

4. Метод диаграмм Вейча.

Метод позволяет быстро получать минимальные ДНФ булевой функции f небольшого числа переменных. В основе метода лежит задание булевых функций диаграммами некоторого специального вида, получившими название диаграмм Вейча. Для булевой функции двух переменных диаграмма Вейча имеет вид (Рис 1).

Рис.1. Диаграмма Вейча



Каждая клетка диаграммы соответствует набору переменных булевой функции в ее таблице истинности. На (Рис 1) это соответствие показано, в клетке диаграммы Вейча ставится единица, если булева функция принимает единичное значение на соответствующем наборе. Нулевые значения булевой функции в диаграмме Вейча не ставятся. Для булевой функции трех переменных диаграмма Вейча имеет следующий вид (Рис 2).

Рис.2. Диаграмма Вейча для трех переменных

Добавление к ней еще такой же таблицы дает диаграмму для функции 4-х переменных (Рис 3).

Рис.3. Диаграмма Вейча для четырех переменных

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

5. Карты Карно.

Метод карт Карно - это один из графических методов минимизации функции. Эти методы основаны на использовании особенности зрительного восприятия, так как с его помощью можно практически мгновенно распознать те или иные простые конфигурации. [5]

Построим таблицу метода карт Карно (табл. 1.6).

Таблица 1.6 Карты Карно

X1X2	X1X2	X1X2	X1X2	X1X2
X3X4
X3X4
X3X4
X3X4

Теперь подсчитаем совокупность всех крестиков с метками минимальным количеством крестиков. Таких крестиков в нашем случае будет 5: три четырехклеточных и два двухклеточных. Этим крестикам соответствуют следующие простые импликанты:

для первого - X₃X₄;

для второго - X₁X₃;

для третьего - X₂X₃;

для четвертого - X₁X₂X₄;

для пятого - X₁X₂X₄;

Минимальная ДНФ будет выглядеть так:

(10)

6. Метод неопределенных коэффициентов.

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

В методе неопределенных коэффициентов используются законы универсального и нулевого множеств и законы повторения. В начале все коэффициенты неопределенны (отсюда и название метода).

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

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид (Рис 4):

Рис.4. Система неопределенных коэффициентов

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

(11)

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

(12)

ГЛАВА 2. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ

2.1 СХОДСТВА И РАЗЛИЧИЯ МЕТОДОВ МИНИМИЗАЦИИ

Отобразим сходства методов минимизации логических функций в (табл. 2.1) и отличия в (табл. 2.2).

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

	Метод эквивалентных преобразований	Метод Квайна	Метод Квайна-Мак-Класки	Метод диаграмм Вейча	Карты Карно	Метод неопределенных коэффициентов
Метод эквивалентных преобразований	-	Над множествами определяют операции, во многом сходные с арифметическими.	Преобразования двоичной информации.	Преобразования двоичной информации.	Над множествами определяют операции, во многом сходные с арифметическими.	Преобразование двоичной входной информации и операции над множествами сходные с арифметическими.
Метод Квайна	Над множествами определяют операции, во многом сходные с арифметическими.	-	Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна.	Интерпретируют таблицу истинности, присутствует аналитический метод.	Векторы соседних клеток карты Карно = векторы соседних секций таблицы склеивания метода Мак- Класки; объдинение в контуры на карте Карно = склеивание в методе Мак-Класки; Нахождение МДНФ и МКНФ.	Позволяет строить Сокр. ДНФ не по СДНФ, а по произвольной ДНФ.
Метод Квайна-Мак-Класки	Преобразования двоичной информации.	Нахождение минимальных ДНФ далее производится по импликантной матрице, как и в методе Квайна.	-	Позволяет строить Сокр. ДНФ не по СДНФ, а по произвольной ДНФ.	Метод склеивания.	Над множествами определяют операции, во многом сходные с арифметическими.
Метод диаграмм Вейча	Преобразования двоичной информации.	Интерпретируют таблицу истинности, присутствует аналитический метод.	Над множествами определяют операции, во многом сходные с арифметическими.	-	Интерпретируют таблицу истинности, присутствует аналитический метод.	Метод склеивания.
Карты Карно	Над множествами определяют операции, во многом сходные с арифметическими.	Векторы соседних клеток карты Карно = векторы соседних секций таблицы склеивания метода Мак- Класки; объдинение в контуры на карте Карно = склеивание в методе Мак-Класки; Нахождение МДНФ и МКНФ.	Метод склеивания.	Преобразование двоичной входной информации и операции над множествами сходные с арифметическими.	-	Интерпретируют таблицу истинности, присутствует аналитический метод.
Метод неопределенных коэффициентов	Преобразование двоичной входной информации и операции над множествами сходные с арифметическими.	Позволяет строить Сокр. ДНФ не по СДНФ, а по произвольной ДНФ.	Интерпретируют таблицу истинности, присутствует аналитический метод.	Нахождение минимальных ДНФ далее производится по импликантной матрице.	Преобразование двоичной входной информации и операции над множествами сходные с арифметическими.	-



Таблица 2.2 Отличия методов минимизации логических функций

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

2.2 НЕДОСТАТКИ И ПРЕИМУЩЕСТВА МЕТОДОВ МИНИМИЗАЦИИ ЛОГИЧЕСКИХ ФУНКЦИЙ

В (табл. 2.2.) приведем недостатки и преимущества каждого метода.

Таблица 2.2 Недостатки и преимущества методов минимизации логических функций

Эквивалентные преобразования	+	Позволяет однозначно установить, совместна система или нет, и если совместна, найти её решение.
	-	Приходится решать большую систему уравнений и велика вероятность ошибки при упрощении.
Квайн	+	Удобство графического представления поиска минимизации функции.
	-	Необходимость полного попарного сравнения всех min-термов на этапе нахождения первичных импликант.
Квайн-Мак-Класки	+	Минимизация сложности комбинационных схем.
	-	Время работы метода растёт экспоненциально с увеличением входных данных.
Диаграмма Вейча	+	Простота и наглядность для небольшого числа аргументов.
	-	Неприменяемость метода для большого числа аргументов (> 6) вследствие сложности диаграмм и потери наглядности.
Карты Карно	+	Простота отыскания склеивающихся компонент; простота выполнения самого склеивания; нахождение всех min форм функции.
	-	Метод не является алгоритмически систематическим, многое зависит от навыков разработчика. Удобство обращения и экономия времени во многом зависит от его способности распознавать оптимальные конфигурации покрытия карт Карно; затруднительно использовать карты Карно при n > 6.
Неопределенные коэффициенты	+	Точность; простой способ применения; распространенность.
	-	При преобразовании может получиться достаточно сложная рациональная функция, интегрирование которой займет много времени и сил.



ЗАКЛЮЧЕНИЕ

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

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



БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. http://ru.wikipedia.org/wiki/ / Представление функции в виде полинома Жегалкина.

2. http://ru.wikipedia.org/wiki/ / Минимизация логических функций методом Квайна.

3. http://ptca.narod.ru/lec/lec4_2.html / Метод Квайна-Мак-Класки

4. http://ptca.narod.ru/lec/lec4_4.html / Метод диаграмм Вейча

5. http://ru.wikipedia.org/wiki/ / Карта Карно

Размещено на Allbest.ru