Совершенные нормальные формы

• Часть 1
• | 2
• | 3
• | 4

Определение. Совершенной дизъюнктивной формулой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:

1.      различны все члены дизъюнкции;

2. различны все члены каждой конъюнкции;
3. ни одна конъюнкция не содержит одновременно переменную и отрицание этой переменной;
4. каждая конъюнкция содержит все переменные, входящие в формулу, т. е. имеет вид

,

где дизъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=1.

Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x1, x2, …, xn)  существует такая формула F1, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки дизъюнктивных членов.

Определение. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:

1. различны все члены конъюнкции;
2. различны все члены каждой дизъюнкции;
3. ни одна дизъюнкция не содержит переменную вместе с отрицанием этой переменной;
4. каждая дизъюнкция содержит все переменные, входящие в исходную формулу, т. е. имеет вид

,

где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0.

Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn)  существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов.

предыдущаяследующая