Нормальные формы формул. Представление логической функции в виде формулы алгебры логики

Нормальные формы формул.

Дизъюнктивная нормальная форма (ДНФ):

Формула называется элементарной дизъюнкцией, если она представляет собой дизъюнкцию (возможно, одночленную) переменных или их отрицаний.

Пример: (Øx₁ Ú Øx₂ Ú x₃).

Формула находится в ДНФ, если она представляет собой дизъюнкцию (возможно, одночленную) элементарных конъюнкций.

Пример: (Øx₁ & Øx₂) Ú (x₂ & x₃).

Теорема: Для любой формулы А алгебры логики может быть построена равносильная ей формула В, находящаяся в ДНФ.

Конъюнктивная нормальная форма (КНФ ):

Формула называется элементарной конъюнкцией, если она представляет собой конъюнкцию (возможно, одночленную) переменных или их отрицаний.

Пример: (Øx₁ & Øx₂ & x₃).

Формула находится в КНФ, если она представляет собой конъюнкцию (возможно, одночленную) элементарных дизъюнкций.

Пример: (Øx₁ Ú Øx₂) & (x₂ Ú x₃).

Теорема: Для любой формулы алгебры логики может быть построена равносильная ей формула, находящаяся в КНФ.

Совершенная дизъюнктивная нормальная форма (СДНФ ):

Формула находится в СДНФ, если:

1) она находится в ДНФ;

2) в каждую элементарную конъюнкцию входят все переменные или их отрицания, причём на i-ой позиции находится x_i или Øx_i;

3) все дизъюнктивные члены различны.

Пример: (Øx₁ & x₂ & x₃) Ú (x₁ & Øx₂ & x₃).

СДНФ формулы определяется однозначно с точностью до порядка дизъюнктивных членов.

Теорема: Пусть формула А зависит от списка переменных <x₁…x_n> и эта формула не равна тождественно 0 тогда существует равносильная ей формула В находящаяся в СДНФ

Совершенная конъюнктивная нормальная форма (СКНФ ):

Формула находится в СКНФ, если:

1) она находится в КНФ;

2) в каждую элементарную дизъюнкцию входят все переменные или их отрицания, причём на i-ой позиции находится x_i или Øx_i;

3) все конъюнктивные члены различны.

Пример: (Øx₁ Ú x₂ Ú x₃) & (x₁ Ú Øx₂ Ú x₃).

СКНФ формулы определяется однозначно с точностью до порядка конъюнктивных членов.

Теорема: Пусть формула А зависит от списка переменных <x₁…x_n> и эта формула не равна тождественно 1 тогда существует равносильная ей формула В находящаяся в СКНФ

Теорема о единственности СДНФ(СКНФ):

Пусть В1 и В2 две СКНФ формулы А относительно списка переменных <x₁…x_n>, тогда они отличаются друг от друга только порядком дизъюнктивных (конъюнктивных) членов.

Критерий равносильности формул:

Две формулы А и В, зависящие от списка переменных <x₁…x_n> и не равны тождественно 0 (или 1), равносильны тогда и только тогда когда они приводятся к СДНФ (СКНФ) отличающихся только порядком дизъюнктивных (конъюнктивных) членов.

Представление логической функции в виде формулы алгебры логики: