Профильный класс
Практикум по информатике

Проблема минимизации логических функций

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

Проблема минимизации логических функций решается на основе применения законов склеивания и поглощения с последующим перебором получаемых дизъюнктивных форм и выбором из них оптимальной (минимальной). Существует большое количество методов минимизации ЛФ. Все они отличаются друг от друга спецификой применения операций склеивания и поглощения, а также различными способами сокращения переборов. Среди аналитических методов наиболее известным является метод Квайна-Маккласки, среди табличных - метод с применением диаграмм Вейча [6]. Графические методы минимизации отличаются большей наглядностью и меньшей трудоемкостью. Однако их применение эффективно при малом числе переменных п<5.

Рассмотрим последовательность действий минимизации ЛФ на примере.

Пример2.15. Найти минимальную дизъюнктивную форму функции, заданной таблицей истинности (табл. 2.6).

Таблица 2.6

Таблица истинности функции Y=f(X1,X2,X3)

X1

Х2

Х3

Y

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

1

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

1

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

glava 249.jpg

Штриховыми линиями в этом выражении отмечены пары конъюнкций, к которым можно применить операцию склеивания типа . Особенно это видно при использовании диаграммы Вейча, в которой “склеиваемые” конъюнкции находятся по соседству друг с другом. Диаграмма Вейча просто по-другому интерпретирует таблицу истинности (табл. 2.7).

Таблица 2.7

Диаграмма Вейча функции Y

Иллюстрация к теме «Проблема минимизации логических функций»

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

В результате применения операций склеивания и поглощения можно получить другое аналитическое выражение:

в котором отсутствуют возможности дальнейших склеивании и поглощений. Однако последнее выражение является избыточным, так как отдельные конъюнкции могут быть “липшими”, т.е. их “составные части” могут включаться в другие конъюнкции. У данной функции существует пять безызбыточных дизъюнктивных форм, из которых только две являются минимальными:

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

Минимизация “вручную” возможна только для функций, зависящих от 4-5 переменных, так как трудоемкость переборов растет в квадратичной зависимости от числа переменных. Применение мощных ЭВМ для этих Целей позволяет расширить границы до п= 12-15. Если при этом учесть, что функции могут быть частично определены (значения функций на некоторых наборах переменных можно определять произвольно), а также что иногда приходится решать задачи совместной минимизации систем ЛФ, то минимизация ЛФ становится сложной инженерной, практической и научной проблемой.

DVD диски - расшифровывается аббревиатура DVD как digital versatile disc, т.е. универсальный цифровой диск. Внешне DVD-диски похожи на CD и в них используется тот же принцип записи информации, но благодаря усовершенствованию технологии, емкость таких дисков во много раз больше, чем емкость CD-диска. Самые простые DVD-диски (однослойные и односторонние) имеют емкость 4,9 Гб. Для чтения таких дисков нужны специальные DVD-приводы Персональный компьютер - характеристики, логические основы, процессор и управление устройствами Информационно-логические основы Классификация элементов и узлов