По теме
СДНФ - совершенная дизъюнктивная нормальная форма
Что значит нормальна форма:
Нормальная форма логической формулы не содержит знаков импликации, эквиваленции и отрицания неэлементарных формул.
Существует два вида нормальной формы: конъюнктивная нормальная форма, т. е. конъюнкция нескольких дизъюнкций (КНФ) и дизъюнктивная нормальная форма, т. е. дизъюнкция нескольких конъюнкций (ДНФ), пример:
КНФ: \(\left (x\vee \bar{y}\vee z \right )\wedge \left (y\vee z \right )\)
ДНФ: \( \left (x\wedge \bar{y}\wedge z \right )\vee \left (y\wedge z \right )\)
Совершенно конъюнктивная НФ - конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых, пример:
СКНФ: \( (x\vee y\vee \bar{z})\wedge ( x\vee \bar{y}\vee z )\)
Совершенно дизьюнктивная НФ - дизьюнкция коньюнкций , причём в каждой коньюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых коньюнкций, в каждой коньюнкции нет одинаковых слагаемых, пример:
СДНФ: \( ( x\wedge y\wedge \bar{z}) \vee ( x\wedge \bar{y} \wedge z ) \)
Взаимозаменяемые обозначения:
| Логика | булева алгебра |
| ∨ | + |
| ∧ | ∙ |
Правила построения СДНФ и СКНФ по таблице истинности
Пример: Восстановите логическую функцию по ее таблице истинности:
| x | y | z | F |
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
РЕШЕНИЕ
СДНФ составляется на основе таблицы истинности по следующему правилу:
для каждого набора переменных, при котором функция равна 1, записывается произведение, в котором с отрицанием берутся переменные, имеющие значение «0».
|
x |
y |
z |
F |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
Получаем СДНФ:
\(F(x,y,z)=\bar{x}\bar{y}\bar{z}+\bar{x}\bar{y} z+x\bar{y} \bar{z}+x\bar{y}z+xyz\)
СКНФ составляется на основе таблицы истинности по правилу:
для каждого набора переменных, при котором функция равна 0, записывается сумма, в которой с отрицанием берутся переменные, имеющие значение 1.
|
x |
y |
z |
F |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |