2015-03-08
503
Необходимо решить задачу простейшего представления функций алгебры логики, т. е. Решить задачу минимизации. Для этого необходимо указать: 1) Базис логических функций; 2) Представление функций в выбранном базисе; 3) Критерии минимизации представления функции в данном базисе. Если не задано дополнительное условие, то используют стандартный базис И, ИЛИ, НЕ. Функцию представляют в ДНФ или КНФ. Элементарную дизъюнкцию в дальнейшем будем называть конъюнктивным термом, элементарную конъюнкцию – дизъюнктивным термом. Ранг терма – число переменных, входящих в данный терм.
Длина формулы, находящейся в ДНФ или в КНФ – число термов, которые ее образуют. Минимальной ДНФ или КНФ называют такую форму, которая имеет наименьшую длину. Булева функция находится в минимальной ДНФ или КНФ, если она минимальный суммарный ранг термов. Минимальная форма не допускает никаких последующих упрощений.
В общем случае существует несколько способов записи одной и той же функции.
Сложность записи можно оценивать числом элементарных операций.
|
|
|
Форма записи булевой функции, в которой использовано наименьшее число операций по сравнению с другими называют абсолютно минимальной в принятом базисе.
Задачу поиска наиболее простой записи функции называют задачей минимизации.
Пример:
Состав устройства, реализуйщий булеву функцию обычно представляют как схему, соединяющие ячейки устройств. Пусть ячейки, реализующие булевы функции обозначают:
И
ИЛИ НЕ
Например: Изобразим схематично СДНФ функции (f2(х1, х2) – СДНФ):
f2(х1, х2)= 
1Ú х1 Ú x 1 х2
