Понятие минимизации булевых функций.

Необходимо решить задачу простейшего представления функций алгебры логики, т. е. Решить задачу минимизации. Для этого необходимо указать: 1) Базис логических функций; 2)Представление функций в выбранном базисе; 3) Критерии минимизации представления функции в данном базисе. Если не задано дополнительное условие, то используют стандартный базис И, ИЛИ, НЕ. Функцию представляют в ДНФ или КНФ. Элементарную дизъюнкцию в дальнейшем будем называть конъюнктивным термом, элементарную конъюнкцию – дизъюнктивным термом. Ранг терма – число переменных, входящих в данный терм.

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

В общем случае существует несколько способов записи одной и той же функции.

Сложность записи можно оценивать числом элементарных операций.

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

Задачу поиска наиболее простой записи функции называют задачей минимизации.

Пример:

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

И

ИЛИ НЕ

Например: Изобразим схематично СДНФ функции (f₂(х₁, х₂) – СДНФ):

f₂(х₁, х₂)= ₁Ú х₁ Ú x₁ х₂