Нормальные формы формул.
Дизъюнктивная нормальная форма (ДНФ):
Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию (возможно, одночленную) переменных или их отрицаний.
Пример: (Øx1 Ú Øx2 Ú x3).
Формула находится в ДНФ, если она представляет собой дизъюнкцию (возможно, одночленную) элементарных конъюнкций.
Пример: (Øx1 & Øx2) Ú (x2 & x3).
Теорема: Для любой формулы А алгебры логики может быть построена равносильная ей формула В, находящаяся в ДНФ.
Конъюнктивная нормальная форма (КНФ ):
Формула называется элементарной конъюнкцией, если она представляет собой конъюнкцию (возможно, одночленную) переменных или их отрицаний.
Пример: (Øx1 & Øx2 & x3).
Формула находится в КНФ, если она представляет собой конъюнкцию (возможно, одночленную) элементарных дизъюнкций.
Пример: (Øx1 Ú Øx2) & (x2 Ú x3).
Теорема: Для любой формулы алгебры логики может быть построена равносильная ей формула, находящаяся в КНФ.
Совершенная дизъюнктивная нормальная форма (СДНФ ):
|
|
Формула находится в СДНФ, если:
1) она находится в ДНФ;
2) в каждую элементарную конъюнкцию входят все переменные или их отрицания, причём на i-ой позиции находится xi или Øxi;
3) все дизъюнктивные члены различны.
Пример: (Øx1 & x2 & x3) Ú (x1 & Øx2 & x3).
СДНФ формулы определяется однозначно с точностью до порядка дизъюнктивных членов.
Теорема: Пусть формула А зависит от списка переменных <x1…xn> и эта формула не равна тождественно 0 тогда существует равносильная ей формула В находящаяся в СДНФ
Совершенная конъюнктивная нормальная форма (СКНФ ):
Формула находится в СКНФ, если:
1) она находится в КНФ;
2) в каждую элементарную дизъюнкцию входят все переменные или их отрицания, причём на i-ой позиции находится xi или Øxi;
3) все конъюнктивные члены различны.
Пример: (Øx1 Ú x2 Ú x3) & (x1 Ú Øx2 Ú x3).
СКНФ формулы определяется однозначно с точностью до порядка конъюнктивных членов.
Теорема: Пусть формула А зависит от списка переменных <x1…xn> и эта формула не равна тождественно 1 тогда существует равносильная ей формула В находящаяся в СКНФ
Теорема о единственности СДНФ(СКНФ):
Пусть В1 и В2 две СКНФ формулы А относительно списка переменных <x1…xn>, тогда они отличаются друг от друга только порядком дизъюнктивных (конъюнктивных) членов.
Критерий равносильности формул:
Две формулы А и В, зависящие от списка переменных <x1…xn> и не равны тождественно 0 (или 1), равносильны тогда и только тогда когда они приводятся к СДНФ (СКНФ) отличающихся только порядком дизъюнктивных (конъюнктивных) членов.
Представление логической функции в виде формулы алгебры логики: