Контрольная работа: Логика высказываний

рÚ ( р Ù q₁ Ù q₂ Ù… Ù q_п ) ≡ р (21¹ )

рÙ( р Ú q₁ )Ù( рÚ q₂ )Ù …Ù (рÚ q_п ) ≡ р (22)

рÚ ( р Ù q₁ ) Ú (рÙ q₂ )Ú … Ú (р Ù q_п ) ≡ р (22¹ )

Из них, а также (9), (3), (15)-(18) получаем новые эквивалентности, а значит, правила преобразования, которые позволяют сокращать число переменных, входящих в формулу:

рÚ ( qÙ`q) ≡ р (23)

рÙ ( qÚ`q) ≡ р (24)

рÚ ( qÚ`q) ≡ 1 (25)

рÙ ( qÙ`q) ≡ 0 (26)

Используя, справа налево дистрибутивный закон (6), получаем два новых соотношения:

(р Ùq ) Ú (р Ùr) ≡ р Ù (q Úr) (27)

(р Úq )Ù (р Úr) ≡ р Ú (q Ùr) (28)

Например, упростить выражение:

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

Применяя (28), учитывая, что rÙ`r ≡ 0 и (17) получаем:

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

Иногда оказывается полезным для упрощения формулы повторить в ней какие-то выражения, используя, справа налево законы поглощения (21)-(22).

Например, упростить выражение

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

Повторим `рÚq и, используя (6), (2), (17), (4) получаем:

(р Úq )Ù (`рÚq) Ù (`рÚq) Ù (`рÚ`q) ≡ (qÚ(рÙ`р)) Ù (`рÚ (qÙ`q)) ≡ (qÚ0) Ù (`рÚ 0) ≡ qÚ`р ≡ `рÚq.

Иногда для каких-то целей необходимо вводить в формулу новые переменные (буквы). Это делается с учетом тождеств (24) и (25) и законов дистрибутивности (6). Так, в выражение р Ú q можно ввести букву r. В самом деле, используя (3), а также (6), получаем:

р Ú q≡(р Úq) Ú (r Ù`r ) ≡ (р ÚqÚr) Ù (рÚ qÚ`r )

4 ДИЗЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА. ПРОБЛЕМА РАЗРЕШИМОСТИ

Для каждой формулы наряду с конъюнктивной нормальной формой существует дизъюнктивная нормальная форма. Она состоит из дизъюнкции конъюнкций, в которой каждый конъюнктивный член является элементарным высказыванием или его отрицанием.

Преобразование формулы к дизъюнктивной нормальной форме происходит следующим образом: отрицанием первоначальную формулу и приведем ее к конъюнктивной нормальной форме, а затем вновь отрицанием полученное выражение согласно правилу а3).

Например, привести к дизъюнктивной нормальной форме формулу:

р Ù (р®q).

Отрицаем эту формулу и приводим полученное выражение к конъюнктивной нормальной форме:

р Ù (р®q) ≡`рÚ (р ®q) ≡`рÚ (`рÚq) ≡`рÚ (`рÙ`q) ≡(`рÚ`р) Ù(`р Ú`q) ≡ ≡(`рÚр) Ù(`р Ú`q)