РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

3 РАВНОСИЛЬНОСТЬ ФОРМУЛ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ. КОНЪЮНКТИВНАЯ НОРМАЛЬНАЯ ФОРМА

Формулы φ и ψ называются равносильными, если формула φ ≡ ψ тождественно истина. Например, формула (p Ù`p) Ú q равносильна q, потому что формула (p Ù`p) Ú q ≡ q тождественно истина (проверку с помощью таблиц истинности предоставляем читателю). Формулы p Ú`p и qÚ`q также равносильны, потому что тождественно истинна формулы p Ú`p ≡ qÚ`q.

Равносильность формул может быть использована для упрощения формул, т.е. для замены какой-то формулы другой формулой, ей равносильной, (эквивалентной), но содержащей либо меньшее число связок, либо меньшее число переменных, либо другие переменные, либо и то, и другое, и третье вместе взятой.

Из определения равносильности формул следует, что тождества (3) - (9) дают нам правила преобразования исходной формулы в новую, ей равносильную к этим правилам добавим и другие правила. Так, любую формулу можно заменить эквивалентной (равносильной) формулой, в которой не содержится знаки «→», «≡» и в которой отрицание опущено лишь на элементарные высказывания. С помощью таблиц истинности можно убедиться в эквивалентности следующих формул:

(р ≡ q) ≡ (р → q) Ù (q→р) (10)

р → q ≡`p Ú q (11)

(р ≡ q) ≡ (`p Ú q) Ù (`qÚр) (12)

(р ≡ q) ≡ (p Ù q) Ú (`рÙ`q) (13)

_____

(р → q) ≡ р Ù`q (14)

р Ù1 ≡ р (15)

р Ù0 ≡ 0 (16)

р Ú0 ≡ р (17)

рÚ 1 ≡ 1 (18)

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

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

Итак, подобно тому, как в алгебре мы имеем возможность преобразовывать, одно выражение в другое, с какой-то точки зрения более простое (скажем, приводить алгебраическое выражение к удобному для логарифмирования виду, заменять таблицу, задающую определитель, числом и т.д.), мы можем преобразовать составные высказывания. Важное значение в алгебре высказываний имеет преобразование любого составного высказывания к конъюнктивной нормальной форме. Эта нормальная форма состоит из конъюнкции дизъюнкций, где каждый дизъюнктивный член является либо элементарным высказыванием, либо его отрицанием.

На основании установленных эквивалентностей вводим следующие правила:

а1) Со знаками Ú и Ù можно оперировать как в алгебре, пользуясь ассоциативным, коммутативным и дистрибутивным законами;

а2) `р можно заменить р;

а3) р Ùq можно заменить выражением`р Ú `q, а р Ú q - выражением`рÙ`q ;

а4) р → q можно заменить выражением `p Ú q, а р ≡ q – выражением (`p Ú q) Ù(`qÚр).

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

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

Последовательным применением правила а3) получаем :

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

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

Применяя к последней формуле закон дистрибутивности, получаем формулу:

(`р Ú <sup>`</sup>q )Ù( qÙ`q) Ù (`rÚ`q).

Наконец, применяя правило а2) получаем конъюнктивную нормальную форму:

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

Очевидно, что эта форма определяется не однозначно. Так, используя то, что qÚ`q ≡ 1 и (15), получаем другую конъюнктивную нормальную форму первоначальной формулы: (`pÚq) Ù (`rÚ`q)

Запишем обобщения законов поглощения (7):

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

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