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

Работа любого КЦУ с одним выходом может быть описана логическим выражением или системой m логических выражений, если у КЦУ m выходов. Другими словами, всякому КЦУ с одним выходом или каждому из m выходов многовыходного КЦУ взаимно однозначно соответствует логическое выражение, в котором буквы соответствуют входным переменным, а знаки операций – ЛЭ, выполняющим эти операции. Подобные логические выражения именуют уравнениями связи «вход-выход» КЦУ. В этих условиях упрощение схемы КЦУ сводится к минимизации логических выражений, соответствующих этим устройствам.

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

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

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

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

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

Например,

Операция объединения смежных минтермов по разнящейся переменной именуется склеиванием.

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

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

Процесс минимизации логических функций значительно упрощают карты Карно. Карты Карно представляют собой прямоугольную таблицу (матрицу), разбитую горизонтальными и вертикальными линиями на клетки (ячейки). Общее число ячеек совпадает с числом минтермов и равно 2ⁿ, где n – число переменных упрощаемой функции. Таким образом, каждая ячейка карты соответствует определенному минтерму, размещение которых осуществляется таким образом, чтобы смежные минтермы находились в соседних ячейках. Соседними считаются ячейки, имеющие общие стороны, а также расположенные на краях одних и тех же строк или столбцов карты.

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

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

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

Поскольку для функции четырех переменных существует 16 входных наборов, карта Карно разделена на 16 ячеек (рис. 2, в).

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

 

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

 

 

			x2
х1
			x3

а)

		х3
	*			х2
х1
	x4

б)

 

Рис. 3. Альтернативный способ маркировки строк и столбцов карты Карно для функции трех (а) и четырех (б) переменных

 

 

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

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. V . СЛОВАРЬ ВИКТИМОЛОГИЧЕСКИХ ТЕРМИНОВ
2. Аварии на химико-технологических объектах: характеристика разрушительного воздействия, типовая модель развития аварии, поражающие факторы.
3. АВТОМАТИЗАЦИЯ Технологических ПРОЦЕССОВ и производств
4. Автоматизация технологических процессов и производств (по отраслям)
5. Автоматизация технологических процессов и производств (по отраслям) 190631 Техническое обслуживание и ремонт автомобильного транспорта
6. Автоматизация технологических процессов и производств (по отраслям)»
7. Автоматизация технологических процессов и производств», 230100.62 «Информатика и вычислительная техника»
8. Анатомо-морфологическая база высших психических функций
9. Аппаратура для проведения исследований проприорецептивных функций
10. Биологических структур в филогенезе
11. Блоки модуля методологических оснований концептуальной модели педагогической системы вузовского формирования функциональных компетентностей будущих учителей физической культуры
12. Виды диагностики технических систем, технологических процессов