Минимизация булевых функций

1. РАЗДЕЛ 1. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Тема 1.2. Минимизация булевых функций

«Если исключить невозможное, то,
что останется, сколь бы невероятным
оно ни было, должно быть истиной»
А. Конан-Дойль
1.
Разложение функций по переменным. Нормальные
формы (ДНФ, СДНФ, КНФ, СКНФ).
2. Построение нормальных форм для заданной булевой
функции.
3. Карты Карно.

2. 1. Разложение функций по переменным. Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ).

Рассмотрим булевы функции, представленные в виде
суперпозиции элементарных функций И, ИЛИ, НЕ.
Используя законы алгебры логики, можно заменить
громоздкие булевы функции им равносильными, но
более
простыми.
Такой
процесс
называется
минимизацией булевых функций. Его проводят для
упрощения
сложных
логических
выражений
в
программах, а также для того, чтобы построенные на их
основе функциональные схемы не содержали лишних
элементов.
Минимизировать булевы функции надо, приводя их к
так называемой нормальной форме.
Существуют две разновидности нормальных форм —
дизъюнктивные (ДНФ) и конъюнктивные (КНФ).

3.

Элементарной
конъюнкцией
/
дизъюнкцией
называется выражение, состоящее из конечного числа
переменных и их отрицаний, взятых в этом выражении
не более одного раза и разделенных операциями
конъюнкции/ дизъюнкции:
Дизъюнктивной / Конъюнктивной нормальной
формой называется дизъюнкция/конъюнкция конечного
числа
элементарных
конъюнкций/дизъюнкций.
Сокращенно они обозначаются ДНФ и КНФ
соответственно.

4.

Нормальная форма называется совершенной, если в
каждой ее элементарной дизъюнкции (конъюнкции)
представлены все переменные, входящие в данную
функцию (либо сами, либо с отрицанием).
Любая булева функция и любая формула алгебры
логики могут быть представлены множеством различных
дизъюнктивных форм, равносильных между собой.
Например: