PhilosophyDay

Равносильность формул исчисления высказываний. конъюнктивная нормальная форма

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

Страница 2

рÚ ( 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 )