Математическая логика и теория алгоритмов 4

Теорема о дедукции в ИВ

Теорема (о дедукции). Пусть 1, … , , , – формулы ИВ. Тогда

1, … , , 1, … , , → .

Примеры

Покажем, что → ¬ → ¬ .

Покажем, что → → → → .

Теорема о замене в ИВ

Формулы и назовем эквивалентными (обозначим ≡ ), если

и .

Замечание . Для любых формул и ИВ

≡ → и → .

Утверждение 1. Отношение ≡ является отношением эквивалентности на множестве формул ИВ, т.е. для любых формул , , ИВ:

а) ≡ ;

b) ≡ ≡ ;

с) ≡ , ≡ ≡ .

Утверждение 2. Для любых формул , , 1, 1, 2, 2 ИВ таких, что1 ≡ 1 и 2 ≡ 2, имеют место эквивалентности:

1.1 2 ≡ 1 2,

2.1 2 ≡ 1 2,

3.1 → 2 ≡ 1 → 2,

4.¬1 ≡ ¬1.

Теорема (о замене). Пусть - формула ИВ, - ее подформула,

′ получается из заменой некоторого вхождения на формулу ′

ИВ и ≡ ′. Тогда ≡ ′.

Свойства выводимых и эквивалентных формул ИВ

Утверждение 3. Пусть , , – формулы ИВ. Тогда

1. → ;

2.;

3.;

4., ;

5.→ , → → (свойство транзитивности);

Свойства выводимых и эквивалентных формул ИВ

Утверждение 3. Пусть , , – формулы ИВ. Тогда

6. → ( → ) ≡ → ( → ) (свойство перестановочности посылок);

7.→ ( → ) ≡ → (свойство соединения и разъединения посылок);

8.→ ≡ ¬ → ¬ (свойство контрапозиции).

Основные эквивалентности исчисления высказываний

Теорема 3. Пусть , , - формулы ИВ. Тогда имеют место следующие эквивалентности:

• ≡ , ≡ (законы идемпотентности);
• ≡ , ≡ (законы коммутативности);
• ( ) ≡ ( ), ( ) ≡ ( )	(законы
ассоциативности);

•( ) ≡ ( ) ( ), ( ) ≡ ( ) ( )

(законы дистрибутивности);

Основные эквивалентности исчисления высказываний

Теорема 3.

•¬( ) ≡ ¬ ¬ , ¬( ) ≡ ¬ ¬ (законы де Моргана);

•¬¬ ≡ (закон двойного отрицания);

•→ ≡ ¬ ;

•¬ .