PhilosophyDay

Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма

Другая философия / Логика высказываний / Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма

Страница 2

По сформулированному алгоритму получаем:

(р®q)Úq®rÚq º (`рÙ qÙ r) Ú( р Ù`qÙ`r ) Ú ( р Ù`qÙr)Ú ( р ÙqÙr).

Другой метод приведения формулы к совершенной дизъюнктивной нормальной форме заключается в следующем: приводим формулу к дизъюнктивной нормальной форме, а затем приписываем в каждом дизъюнктивном члене недостающие переменные согласно правилу (24).

Так , для формулы (р®q)Úq®rÚq имеем следующую цепочку преобразований _ _

(р®q)Úq®rÚq º(`рÚ qÚ q) Ú (rÙ q) º `р Úq Ù r Ù q º (`рÚ q)Ù(`qÚ`r ).

Отрицаем последнее выражение:

_ _ _

(`р Ú q)Ù(`qÙ`r ) º(`рÙ`q) Ú (`qÙ`r ) º( р Ù`q) Ú (qÙr).

Затем, пользуясь (24), имеем:

( ( р Ù`q) Ù (r Ú`r)) Ú (( рÚ` р) Ù( qÙr)) º ( р Ù`q Ù r) Ú ( р Ù`q Ù`r) Ú (`рÙ qÙ r) Ú( рÚ q Úr ) º(`рÙ qÙ r) Ú ( р Ù`qÙ`r) Ú( р Ù`qÙr) Ú ( р ÙqÙr).

Аналогичным образом определяется совершенная конъюнктивная нормальная форма какой-то формулы. Она удовлетворяет условиям:

a) в ней нет двух одинаковых конъюнкций;

b) ни одна конъюнкция не содержит двух одинаковых дизъюнкций;

c) ни одна конъюнкция не содержит переменного высказывания вместе со свои отрицанием;

d) в каждой конъюнкции содержится в качестве дизъюнктивных членов все переменные входящие в формулу.

Правила приведения произвольной формулы к совершенной конъюнктивной нормальной форме аналогичны тем, которые были описаны для нахождения совершенной дизъюнктивной нормальной форме и выражаются в двойственных терминах. Так, для формулы (р®q)Úq®rÙq пользуясь ее таблицей истинности и правилом двойственности сразу можно записать совершенную конъюнктивную нормальную форму. Для этого выписываем дизъюнкции переменных, при которых формула истинна, затем расставляем знаки отрицания, чтобы при этих значениях выписанные дизъюнкции обращались в ложь. И наконец соединяем все дизъюнкции знаком конъюнкции. Для предыдущей формулы получаем:

(р®q)Úq®rÙqº( р Ú `qÚ` r) Ù(` р Úq Ú r ) Ù (`рÚqÚ `r) Ù (`рÙ`qÙ `r)

Чтобы привести формулу к совершенной конъюнктивной нормальной форме по другому методу, надо привести ее к конъюнктивной нормальной форме, а затем восстановить в каждом конъюнктивном члене недостающие переменные, пользуясь правилом (23). Так для формулы (р®q)Úq®rÙq имеем следующую цепочку преобразований:

(р®q)Úq® (rÙq) º( `р Ú qÚ q) Ú (rÙq) º (`рÙ`q) Ú(rÙq) º (рÙ`q) Ú(rÙq).

По закону двойственности имеем:

_

(рÙ`q) Ú(rÙq) º (`рÚ`q) Ù (`r Ú`q) º (`рÚq) Ù (`r Ú`q).

В полученной конъюнктивной нормальной форме восстанавливаем недостающие переменные, пользуясь (23).

(`рÚq) Ù (`r Ú`q) º((` р Úq) Ú (rÙ`r)) Ù (( рÚ` р) Ú (`r Ú`q)) º (`рÚ qÚ r) Ù (` рÚ q Ú `r) Ù( рÚ`qÚ`r ) Ù (`рÙ`q Ù` r ).