Задания для самостоятельной работы
8.1.
Написать подпрограмму, вычисляющую
значение булевой функции
в ДНФ на наборе
.
Каждая элементарная конъюнкция функции
кодируется с помощью вектора вхождения
и обращения (см. задачу 4.4).
Указание.
Алгоритм вычисления булевой функции в
ДНФ, заданной в виде совокупности
векторов вхождения -
и обращения -
на наборе
представлен структурограммой на рис.
8.18.
8.2.
Используя результаты задачи 8.1, написать
подпрограмму, вычисляющую вес производной
булевой функции в ДНФ по заданной
переменной
(исходная функция также хранится в виде
совокупности векторов вхождения и
обращения).
8.3. Используя результаты задачи 8.2, модифицировать программу построения бинарного графа (задача 4.4) так, чтобы в качестве переменной разложения на текущем шаге выбиралась переменная, по которой производная имеет максимальный вес.
9. Программная реализация логических функций
Представление логических функций схемами из элементов - это исторически первый и наиболее исследованный вид их реализации. Другой ее вид - реализация логических функций программами.
Под
программой будем понимать пронумерованную
последовательность команд
,...,
,
взятых из некоторого фиксированного
набора (системы команд). Программа
работает над конечным множеством
пронумерованных (или проименованных)
двоичных ячеек. Номер (или имя) ячейки
называется ее адресом; именем ячейки
часто будет служить имя логической
переменной, значение которой хранится
в этой ячейке.
Система
команд содержит команды-операторы вида
(выполнить операцию
над содержимыми ячеек
,...,
и
результат положить в ячейку
)
и двухадресные условные переходы двух
видов:
1)
"если
,
то
,
иначе
(если
,
то перейти к выполнению команды
,
иначе перейти к
);
2)
"если
(
),
то
,
иначе
".
1) Модели дискретных устройств с памятью рассмотрены в [1, с.295-331], [2, с.163-243], [3, с.110-150], [4, с.219-227,264-294].
1)
Адекватность
понимается в том смысле, что между всеми
элементами E
схемы и всеми функциональными символами
,
входящими в соответствующую формулу,
можно установить взаимно однозначное
соответствие.
2)
Максимальное
число возможных входов, которые могут
быть подключены к выходу элемента E,
называется коэффициентом
разветвления
(коэффициентом
объединения по выходу)
и является одной из технических
характеристик реальных элементов. Если
,
то считается, что элемент E
перегружен. В этом случае необходимо
преобразовать логическую схему, возможно
путем введения в нее некоторых
дополнительных элементов, чтобы число
нагрузок на элемент E
было меньше или равно коэффициенту
разветвления
(см. [4] стр. 240-245).