- •Часть I
- •1. Математическая логика
- •1.1.Булева алгебра
- •1.5. Системы и базисы булевых функций
- •2. Нормальные формы бф.
- •2.2 Совершенные нормальные формы.
- •2.3. Приведение к совершенным формам днф и кнф.
- •2.4. Сокращенные и тупиковые нормальные формы.
- •3. Методы минимизации булевых функций.
- •3.1. Метод Квайна – Мак-Класки
- •3.2. Минимизация по картам Карно-Вейча
- •3.3. Понятие интервала функции.
- •3.4. Слабоопределенные бф.
- •Этапы минимизации бф. Табл. 6
- •Контрольные вопросы и задания
2. Нормальные формы бф.
В дискретной математике, точно так же, как и в непрерывной, существуют канонические формы записи функций. В дискретной математике их принято называть нормальными.
Существуют 2 вида нормальных форм для БФ: дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ).
ДНФ называется дизъюнкция элементарных конъюнкций.
КНФ – конъюнкция элементарных дизъюнкций.
ДНФ: ; КНФ:
Элементарными конъюнкциями и дизъюнкциями называются такие конъюнкции и дизъюнкции, которые не могут быть сокращены (или преобразованы) с помощью формул булевой алгебры внутри себя самих.
Например: элементарные конъюнкции – , , , 0.
не являются элементарными конъюнкциями – , , , 1.
элементарные дизъюнкции – , , , 1.
не являются элементарными дизъюнкциями – , , 0.
Среди нормальных форм различают
совершенную (СДНФ, СКНФ)
сокращенную (ДСНФ, КСНФ)
тупиковые: минимальную и кратчайшую
(ТДНФ: МДНФ, КДНФ;
ТКНФ: МКНФ, ККНФ)
|
ДНФ |
КНФ |
||
Совершенная |
СДНФ |
СКНФ |
||
Сокращенная |
ДСНФ |
КСНФ |
||
Тупиковая |
ТДНФ |
ТКНФ |
||
Минимальная Кратчайшая |
МДНФ |
КДНФ |
МКНФ |
ККНФ |
Любая БФ может быть представлена в виде большого множества различных нормальных форм и только единственным образом в виде своих совершенных и сокращенных форм.
|
|
|
|
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
[произвольная ДНФ]
[произвольная ДНФ]
[тупиковая ДНФ,
минимальная и кратчайшая
одновременно.]
[совершенная ДНФ].
Для приведения любого логического выражения (БФ) к нормальным формам приведем следующий алгоритм.
2.1 Алгоритм приведения БФ к нормальным формам:
Привести функцию к системе <&,V,-> (если функция дана в другой системе БФ)
Снять отрицания над функциями по законам де Моргана:
, .
Применить законы склеивания и поглощения.
Применить дистрибутивность для конъюнкций и дизъюнкций.
в ДНФ
в КНФ
и
в КНФ
в ДНФ
Повторить п.3 и действия с константами 1 и 0.
Пример:
.
2.2 Совершенные нормальные формы.
Разложение Шеннона.
Любая БФ , не равная тождественно нулю, единственным образом представима в виде прямого разложения Шеннона:
,
где n – количество переменных ,
– знак отрицания, если , или его отсутствие, если на j-м наборе,
– значение функции на j-м наборе.
|
|
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
(СДНФ)
Конъюнкция всех переменных с соответствующими знаками (отрицания или его отсутствия) на единичном ( ) наборе функции называется конституентой единицы функции.
Дизъюнкция всех переменных с противоположными знаками над ними на нулевом ( ) наборе функции называется конституентой нуля функции.
Любая БФ , не равная тождественно 0, единственным образом представима в виде обратного разложения Шеннона:
.
(СКНФ), в данном случае совпадает с ДНФ).