Дискретная математика. Ерош И.Л - 17 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

17
ностью определенными булевыми функциями. Очень часто функции не
определены на большом числе наборов. В таблице истинности и, сле
довательно, в диаграммах Вейча такие функции кроме 0 и 1 будут со
держать еще и «—». Это означает, что такой набор никогда на вход
устройства не поступает. Следовательно, поведение комбинационной
схемы при таком наборе не имеет значения, и на месте «—» может быть
произвольно поставлена либо 1, либо 0. Этот процесс называется до
определением булевой функции. Доопределение булевой функции же
лательно выполнять так, чтобы получить возможно более простое вы
ражение. В этом случае, как правило, реализованная комбинационная
схема также оказывается более простой.
Пояснить наличие не полностью определенных булевых функций мож
но с помощь следующего простого примера. Известно, что устройство уп
равления современным лифтом является цифровым. В 9этажном доме
это устройство должно помнить коды всех 9 этажей, во всяком случае,
до тех пор, пока клиент не попадет на свой этаж. Память в цифровых
устройствах реализуется с помощью элементарных автоматов (простых
элементов памяти с двумя устойчивыми состояниями – триггеров). Если
взять три триггера, то на них можно реализовать 8 различных комбина
ций, и эти комбинации сопоставить этажам дома. В 9этажном доме тре
буется использовать 9 различных комбинаций, следовательно, память
этажей должна содержать 4 триггера. Но на 4х триггерах можно реали
зовать 16 различных комбинаций, 9 из них сопоставить этажам, а ос
тальные 7 окажутся не использованными. Очевидно, в таком устройстве
управления существуют комбинации, которые никогда на вход устрой
ства поданы быть не могут (в 9этажном доме нельзя нажать кнопку
13го этажа). Поведение устройства на этих наборах не имеет значения.
Пусть задана диаграмма Вейча некоторой не полностью определен
ной функции:
1–– 1
1–
––
–1
Приведенная функция имеет прочерки в шести клетках, в каждой
из которых может быть поставлена как 1, так и 0. Следовательно, су
ществует 2
6
= 64 различных способа доопределения булевой функции.
Однако из диаграммы легко выбрать наилучший, который дает следу
ющий результат минимизации: F = ùAùC Ú ùBD.
A
B
D
C

Страницы