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

 

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

Метод карт Карно (карты минитермов)

Метод карт Вейча

Минтерм - выражение соответствующее минимальному поименованному участку карты (кодовое имя клетки)

Отличие методов заключается в различном расположении имен (кодов) клеток карты в последовательности определяемой рефлексным (циклическим ) кодом.

В каждую клетку внесен символ истинности или ложности соответствующий кодовому слову клетки.

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

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

 

Минимизация логических функций методом диаграмм Вейча (карт Карно).

 

Карта для двух переменных

 

	х2
х1

 

Таблица истинности

 

Х2	Х1	выход

 

Карта для трех переменных

 

	х2
х1
		х3

 

Таблица истинности

 

х3	х2	х1	выход

 

карта Карно для четырех переменных

 

	х1
х2
				х4
	.	.
		х3

 

карта Карно для пяти переменных

Данная карта состоит из двух карт Карно для четырех переменных

 

х5

 

	х1
х2
				х4
	.	.
		х3

 

 

	х1
х2
				х4
	.	.
		х3

 

карта Карно для большого количества переменных

Диаграммы Карно для шести переменных содержат 64 полные конъюнкции . Для большего количества переменных представление визуальной диаграммы затруднительно. При количестве переменных 6 и более необходимо заменить две или три переменных новой переменной.

 

Нормальная дизъюнктивная форма (сложение между скобками) умножение в скобках.

y=(x1^x2^x3)v( …………v

 

 

Х1 (А)	Х2 (В)	Х3 (С)	Y	Y выражение
				Ā^B^C
				A^B^C

 

Пример

Пусть имеются три независимых параметра система считается исправной при выполнении следующего неравенства

В для нашей схемы карта Карно запишется в виде

 

	х2
х1
		х3

Выражение упростится до вида

 

Конструктивно исключен один из элементов И и три элемента Не кроме того вместо трехвходовых элементах схема контроля будет реализована на двухвходовых элементах.

Тоже выражение при реализации функции СКНФ

СКНФ

 

	х2
х1
		х3

 

	х2
х1
		х3

 

В нашем случае обе функции будут реализованы по одной схеме с использованием разных элементов Однако подобная симметрия не всегда возможна поэтому необходим Анализ как функции МКНФ так и функции МДНФ выбирается та схема которая содержит меньшее количество элементов.

 

. Результат минимизации может быть неоднозначен, и одной заданной таблице истинности могут соответствовать различные схемы.

Рассмотрим для примера функцию неравнозначности (ИСКЛЮЧАЮЩЕЕ ИЛИ). Ее таблица истинности следующая:

 

ИСКЛЮЧАЮЩЕЕ ИЛИ
x1	x2	F(x1,x2)

 

Уравнение по первой стандартной форме:

(3.5)

Уравнение по второй стандартной форме:

(3.6)

Преобразуем вторую скобку в уравнении 6 по принципу двойственности:

(3.7)

 

Рис. 3.3. Схемы по уравнениям 3.5 (а) и 3.7 (б)

 

Для построения схемы по уравнению 5 необходимы 2 элемента НЕ, два двухвходовых элемента И и один двухвходовый элемент ИЛИ. В схеме, построенной по уравнению 3. 7 на один элемент НЕ меньше (рис. 3.3 ).

Как было отмечено выше, существуют полные наборы логических функций, к которым относятся три функции ИЛИ, И, НЕ, функция ИЛИ-НЕ, функция И-НЕ. Все построенные нами схемы использовали полный набор функций ИЛИ, И, НЕ. Однако представляет интерес и имеет практическое значение использование для построения схем базовых логических элементов ИЛИ-НЕ и И-НЕ. Для построения схемы на элементах ИЛИ-НЕ (рис. 3.4 ) воспользуемся уравнением 3. 6. Преобразуем его по принципу двойственности:

Для построения схемы на элементах И-НЕ (рис. 3.4 б) преобразуем уравнение 5, избавляясь от операции логического сложения:

 

Рис. 3.4 . Схемы элемента ИСКЛЮЧАЮЩЕЕ ИЛИ на элементах
ИЛИ-НЕ (а) и И-НЕ (б)

 

Пример

Реализация системы управления и контроля за несколькими независимыми параметрами.

 

 

Y=

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

 

Вопросы для самопроверки

6.1. Сформулируйте правило перехода от таблицы истинности к первой стандартной форме. Приведите примеры. Запишите уравнение функции равнозначности в первой стандартной форме.

6.2. . Сформулируйте правило перехода от таблицы истинности ко второй стандартной форме. Приведите примеры. Запишите уравнение функции неравнозначности во второй стандартной форме.

6.3. Докажите, что уравнения функции ИСКЛЮЧАЮЩЕЕ ИЛИ, записанные в первой и второй стандартных формах преобразуются одна в другую.

6.4. Постройте схему устройства, описываемого уравнением, полученным в пункте 6.1.

6.5. Постройте схему элемента ИЛИ на элементах И-НЕ.

6.6. Постройте схему элемента И на элементах ИЛИ-НЕ.

6.7. Постройте схему элемента реализующего функцию равнозначности на элементах И-НЕ.

6.8. Постройте схему элемента реализующего функцию равнозначности на элементах ИЛИ-НЕ.

6.9. Постройте схему элемента ИСКЛЮЧАЮЩЕЕ ИЛИ на элементах И, ИЛИ, НЕ.