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

Рефераты / Математика / Элементы математической логики. Исчисление высказываний

Закон поглощения:

для конъюнкции дизъюнкций: рÙ( q Úр) ºp (7)

для дизъюнкции конъюнкций: рÚ(qÙ р) ºp (71)

Закон двойственности (теорема де Моргана):

для конъюнкции: р<

b>Ùqº`р Ú`q (8)

для дизъюнкции: рÚqº`р Ù`q (81)

Закон двойного отрицания: `р º р (9)

Уже из внешнего вида формул (1) – (9) отчетливо виден двойственный характер этих законов относительно операций конъюнкции и дизъюнкции: если дана некоторая тождественно истинная функция высказывания, в выражении которой не входит знак «®», то при замене всех входящих в нее знаков «Ú» на «Ù» и «Ù» на «Ú», 1 на 0 и 0 на 1, она остается тождественно истинной. Запишем, например закон противоречия в формуле p Ù`p≡0 применяя к этому выражению закон двойственности, получим закон исключенного третьего p Ú`p≡1 (91)

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