Алгоритм построения днф
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
A→B= ךAvB A⇔B=(A^B)v(ךAvךB)
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
ך(AvB)= ךA^ךB ך(A^B)= ךAvךB
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения днф
Приведем к ДНФ формулу :F=((X→Y)↓ ך(Y→Z))
Выразим логические операции → и ↓ через :v ^ ך
F=(( ךXvY)↓ ך(ךYvZ))= ך ((ךXvY)v ך (ךYvZ))
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
F= ך ((ךXvY)v ך (ךYvZ))=( ך ךX^ ךY)^( ךYvZ)=(X^ ךY)^( ךYvZ)
Используя закон дистрибутивности, приводим формулу к ДНФ:
F=(X^ ךY^ ךY)v(X^ ךY^Z)
Конъюнктивная нормальная форма (КНФ) в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкцийлитералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к КНФ. Для этого можно использовать: Закон двойного отрицания, Закон де Моргана, Дистрибутивность.
Примеры и контр примеры
Формулы в КНФ:
ך A^(BvC) (AvB)^( ך BvCv ך D)^(Dv ך E)A^B
Формулы не в КНФ:
ך (BvC) (A^B)vC A^(Bv(D^E))
Но эти 3 формулы не в КНФ эквивалентны следующим формулам в КНФ:
ך B^ ך C (AvC)^(BvC) A^(BvD)^(BvE)
Построение КНФ
Алгоритм построения КНФ
1) Избавиться от всех логических операций, содержащихся в формуле, заменив их основными: конъюнкцией, дизъюнкцией, отрицанием. Это можно сделать, используя равносильные формулы:
A→B= ך AvB A↔B=(A^B)v(ך A^ ך B)
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул:
ך (AvB)= ך A^ ך B ך (A^B)= ך Av ך B
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Пример построения КНФ
Приведем к КНФ формулу
F=(X→Y)^(( ך Y→Z) → ך X)
Преобразуем формулу F к формуле не содержащей → :
F=( ך XvY)^( ך (ך Y→Z)v ך X)=( ך XvY)^( ך (ך ך YvZ)v ך X)
В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания:
F=( ך XvY)^(( ך Y^ ך Zv ך X)=( ך XvY)^(( ך Y^ ך Z)v ך X)
По закону дистрибутивности получим КНФ:
F=( ך XvY)^( ך Xv ך Y)^( ך Xv ך Z)
k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно kлитералов.
Например, следующая формула записана в 2-КНФ:
(AvB)^( ך BvC)^(Bv ך C)
Переход от КНФ к СКНФ
Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение : (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:
(XvY)^(Xv ך Yv ך Z)=(XvYv(Z^ ך Z))^(Xv ך Yv ך Z)=(XvYvZ)^(XvY vך Z)^(Xv ךYv ךZ)
Таким образом, из КНФ получена СКНФ.
Переход от КНФ к СКНФ
Если в простой дизъюнкции не хватает какой-то переменной (например, z), то добавляем в нее выражение :Z^ ך Z=0 (это не меняет самой дизъюнкции), после чего раскрываем скобки с использованием распределительного закона:
(XvY)^(Xv ךY ךZ)=(XvYv(Zv ךZ))^(Xv ךYv ךZ)=(XvYvZ)^(XvYv ךZ)^(Xv ךYv ךZ) Таким образом, из КНФ получена СКНФ.
25. Совершенные дизъюнктивные и конъюнктивные нормальные формы и алгоритмы приведения к ним. Примеры.
Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая конъюнктивная нормальная форма, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных дизъюнкций
в каждой дизъюнкции нет одинаковых пропозициональных переменных
каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
k-конъюнктивной нормальной формой называют конъюнктивную нормальную форму, в которой каждая дизъюнкция содержит ровно k литералов.
Например, следующая формула записана в 2-КНФ:
Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:
в ней нет одинаковых элементарных конъюнкций
в каждой конъюнкции нет одинаковых пропозициональных букв
каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Для любой функции алгебры логики существует своя СДНФ, причём единственная.
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:
|
|
|
|
|
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
Совершенная ДНФэтой функции:
