2. Приведение к дизъюнктивной нормальной форме днф
Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.
Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций.
Примеры ДНФ являются формулы упражнения 4 в § 4.4.
Упражнение 4.
Получить СДНФ логической функции f (x, y, z), используя табличное представление функции,
если f задана булевой формулой:
1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
\
В таком случае совершенная ДНФ (СДНФ) - это ДНФ, каждая элементарная конъюнкция которой включает все переменные с отрицаниями или без.
Процедура приведения к ДНФ:
1 |
Все отрицания “спустить” до переменных с помощью (4.19) и (4.21) |
|||||||||||
Закон двойного отрицания: |
||||||||||||
Свойства констант 0 и 1:
Правила де Моргана:
|
||||||||||||
2 |
Раскрыть скобки с помощью (4.14),(4.16),(4.17). |
|||||||||||
|
||||||||||||
3 |
Удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью (4.18), (4.22), (4.23).
|
|||||||||||
4 |
Удалить константы с помощью (4.20).
|
|||||||||||
Процедура приведения ДНФ к СДНФ состоит в расщеплении (обратном склеивании: использовании (4.25) в обратную сторону) конъюнкций, которые содержат не все переменные.
эквивалентное соотношение склеивание |
|
|
(4.25) |