Элементы математической логики. Исчисление высказываний

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

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

р&Ugr

ave;( р Ú q1 Ú q2 Ú … Ú qп ) ≡ р (21)

рÚ ( р Ù q1Ù q2 Ù… Ù qп ) ≡ р (211)

рÙ( р Ú q1 ) Ù( рÚ q2 ) Ù …Ù (рÚ qп ) ≡ р (22)

рÚ ( р Ù q1 ) Ú (рÙ q2 ) Ú … Ú (р Ù qп ) ≡ р (221)

Из них, а также (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)

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

_ _ _

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

Приведение формулы к нормальной форме дает иной, чем таблицы истинности метод решения проблемы разрешимости.

Чтобы формула была тождественно истинной необходимо и достаточно, чтобы в ее конъюнктивной нормальной форме каждый конъюнктивный член содержал элементарное высказывание вместе со своим отрицанием.

Доказательство получаем из (25)(91) и (15), а также определения конъюнкции. Так формула (р Ú`рÚ q) Ù( р Ú`qÚ q) тождественно истинна.

Чтобы формула была тождественно ложной необходимо и достаточно, чтобы в ее дизъюнктивной нормальной форме каждый дизъюнктивный член содержал элементарное высказывание вместе со своим отрицанием. Так формула:

(р ÙrÙ`р) Ú ( р Ù r Ù`r ) тождественно ложна.

Доказательство получаем из того, что р Ù`р≡0, (16) и определения дизъюнкции.

Формула будет выполнимой, если в ее дизъюнктивной нормальной форме есть хотя бы один дизъюнктивный член, который не содержит элементарное высказывание вместе со своим отрицанием.

 Скачать реферат