double arrow

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


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

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

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

Пример: (Ø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), равносильны тогда и только тогда когда они приводятся к СДНФ (СКНФ) отличающихся только порядком дизъюнктивных (конъюнктивных) членов.

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


Сейчас читают про: