Минимизация методом карт Карно

Цель работы

Изучение методов минимизации функций алгебры логики (ФАЛ).

Основные понятия

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

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

Исходными формами функции при решении канонической задачи минимизации являются ее ДСНФ и КСНФ. Если функция задана в другой форме, то ее преобразуют в ДСНФ или КСНФ. Рассмотрим минимизацию функций, заданных в дизъюнктивной нормальной форме.

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

где а - любая логическая функция.

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

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

Минимизируемая ФАЛ может содержать несколько тупиковых ДНФ.

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

Минимизация методом карт Карно

При минимизации ФАЛ небольшого числа переменных (три-пять) используются простые табличные методы, одним из которых является метод карт Карно.

Карты Карно позволяют минимизировать как полностью, так и не полностью определенные ФАЛ. Карта Карно (рис. 4.1) для ФАЛ четырех переменных, в которой проставленные единицы соответствуют единичным наборам ФАЛ, а нулевые не отмечены, соответствует аналитическому выражению минимизируемой ФАЛ

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

X 1 X 2 X 3 X 4

Рис. 4.1. Структура карты Карно

Рассмотренное свойство удобно использовать для группировки отдельных единичных наборов в так называемые "подкубы" (объединения из 2, 4, 8 и т.п. числа единичных наборов) с целью исключения одной, двух или нескольких переменных, входящих в единичные наборы. При склеивании единичных наборов, входящих в какой-либо подкуб, происходит исключение одной или нескольких переменных. Это является следствием того, что в подкубы входят пары наборов, отличающихся значением одной, двух или нескольких переменных.

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

Таблица 4.1

X 1 X 2 X 3 X 4				1 1 0 1 1 0 0 1   X1 X4 10

Таблица 4.2

X 1 X 2 X 3 X 4				0 0 0 1 0 0 1 1   X4 10

Таблица 4.3

X 1 X 2 X 3 X 4				0 1 0 0 0 1 1 0 10

Таблица 4.4

X 1 X 2 X 3 X 4				0 0 1 0 1 0 1 0 10

Таблица 4.5

X 1 X 2 X 3 X 4				0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 10

Таблица 4.6

X 1 X 2 X 3 X 4				0 0 1 1 0 1 1 0 0 1 1 1 0 1 1 0 10

Таблица 4.7

X 1 X 2 X 3 X 4				0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0   10

0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0

Таблица 4.8

X 1 X 2 X 3 X 4

0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0

Таблица 4.9

X 1 X 2 X 3 X 4

0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0

Таблица 4.10

X 1 X 2 X 3 X 4

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

Пример 1. Найти минимальную ДНФ для функции, заданной картой

Карно (табл.4.11).

В данном случае набор (1,1,0,0) можно объединить только с набором (1,1,1,0), набор (1,0,0,1) - с набором (1,0,1,1), набор (0,1,1,1) - с набором (1,1,1,1), а набор (0,0,1,0) - с набором (1,0,1,0).

Таблица 4.11

X 1 X 2 X 3 X 4

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

Окончательное выражение минимальной ДНФ имеет вид:

+ +

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

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

1) Закон двойного отрицания

2) Переместительный закон (закон коммутативности)

3) Сочетательный закон (закон ассоциативности)

4) Распределительный закон (закон дистрибутивности)

а (в Ú с) = а в Ú a с

а Ú в c = (a Ú в) (a Ú c)

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

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

Значения функции в столбце "а Ú в с" получается при использовании значений столбцов "а" и "в с", а в столбце "(а Ú в) (а Ú c)" - при использовании столбцов "а Ú в" и "а Ú с". Сравнение значений двух правых столбцов таблицы доказывает правильность второй записи распределительного закона.

Номер набора	а	в	с	в с	а Ú в	а Ú с	аÚ в c	(а Ú в) (а Ú с)

5) Правило де-Моргана

6). Правила операций с константами 0 и 1

7) Правила операций с переменной и ее инверсией

8) Закон повторения

Следствие закона повторения - правило приведения подобных членов в выражении:

a a ... a = a

a Ú a Ú... Ú a = a

9) Закон поглощения

Для доказательства правильности закона используем аналитический метод и уже известные законы.

10) Закон склеивания

3. Задание

1) Изучить теоретический материал.

2) Изучить способы задания ФАЛ и основные законы алгебры логики.

2) Используя законы алгебры логики, минимизировать заданную функцию. Синтезировать схему, реализующую минимизированную функцию на логических элементах в базисе «И», «ИЛИ», «НЕ».

3) Минимизировать функцию, заданную числовым набором, методом карт Карно. Сравнить полученные выражения. Вариант выбирается из таблицы 4.16 по указанию преподавателя.

4) Построить схему, реализующую минимизированную функцию, на логических элементах. Построить ее таблицу истинности.

Таблица 4.16

№ варианта	Функция F(X1,X2,X3.X4)	№ варианта	Функция F(X1,X2,X3.X4)
	2,4,5,7,10,14 0,2,5,11,14,15 1,5,6,8,11,13 3,4,7,11,12,15 2,4,6,9,11,15 2,3,8,12,13,14 4,5,8,10,11,13 0,1,3,4,9,14 8,9,11,10,13,15 5,7,8,9,11,15 5,10,12,13,14 1,4,5,6,7,8,9,12,13 3,4,5,7,9,13,14,15 0,1,2,3,4,6,7,8,9,11,15		3,5,7,9,11,13,14 1,3,4,6,9,11,13 1,2,3,5,7,8,10 1,3,7,8,9,11 3,5,8,8,11,12,13 0,2,4,8,9,10,11,13 1,2,3,6,9,11,12 3,4,5,7,9,11,12,14 1,6,7,8,11,14,15 2,3,5,7,9,10,11,15 3,5,6,8,9,11,12,14 1,3,5,7,8,10,11 0,3,4,5,7,11,13 0,2,6,8,10,11,15

4. Содержание отчета

1) Аналитическое выражение для заданной функции.

2) Карта Карно для заданной функции.

3) Минимизация функции методом Карты Карно ы с пмощью законов алгебры и логики.

4) Аналитические выражения для минимизированной функции.

5) Схема, реализующая минимизированную функцию, на логических элементах. Ее таблица истинности.

6) Описание последовательности построения моделируемых схем.

7) Краткие выводы.

Контрольные вопросы

1) Что такое ДСНФ?

2) Что такое КСНФ?

3) Что такое сокращенная ДНФ?

4) Что такое тупиковая ДНФ?

5) Что такое импликанта?

6) Что такое простая импликанта?

7) Что такое вес кода?

8) Какие наборы являются соседними?

9) Что такое подкуб?

Дата добавления: 2015-07-11