Лекция № 9.

Тема: СВОЙСТВА ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ

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

1. Непротиворечивые формальные системы

2. Теорема истинности исчисления высказываний

3. Непротиворечивость исчисления высказываний

4. Полные формальные системы

5. Независимость аксиом исчисления высказываний

Краткое содержание лекционного материала

Формальная система S называется непротиворечивой, если формула AA не является теоремой в системе S. В этом определении формулу AA можно заменить любым противоречием. В системе S₁ AA(AA).

Теорема 1 (истинности). Если ^_S1A, то A – тавтология.

Доказательство. Применим индукцию по теоремам.

Докажем, методом от противного, что каждая из аксиом (A₁), (A₂), (A₃) является тавтологией. С этой целью предположим, что формула (A_i), i1,2,3, ложна при некотором распределении истинностных значений пропозициональных переменных, входящих в состав формулы (A_i). Затем, используя определение импликации и отрицания, находим противоречие.

Значит, формула (A_i) истинна при любых значениях переменных, т.е. является тавтологией.

(A₁) – тавтология:

Предположение: (A1)Л
AИ	BAЛ
	BИ	AЛ
Противоречие: AИ и AЛ

(A₂) – тавтология:

Предположение: (A2)Л
A(BC)И	(AB)(AC)Л
	ABИ	ACЛ
		AИ	CЛ
BCИ	BИ
CИ
Противоречие: AИ и AЛ

(A₃) – тавтология:

Предположение: (A3)Л
BAИ	(BA)BЛ
	BAИ	BЛ
		BЛ
AИ	AИ
AЛ
Противоречие: AИ и AЛ

Если посылки A и AB правила (MP) истинны, то его заключение B тоже истинно. Значит, если A и AB – тавтологии, то B – тавтология.

Следствие. Исчисление высказываний S₁ непротиворечиво.

Доказательство. Если бы было ^_S1AA, то по теореме 5 мы получили бы тавтологию AA.

Формальная система S называется полной, если любая ее формула A является теоремой в S тогда и только тогда, когда она истинна в S.

В системе S₁ формула A называется истинной, если A – тавтология.

Аксиома системы S называется независимой, если не выводится с помощью правил вывода из остальных аксиом системы S.

Теорема 2. Аксиомы (A₁), (A₂), (A₃) системы S₁ независимы.

Доказательство. Мы определяем новые «истинностные значения» формул, при этом предполагаем, что если AAB1, то B1. При новой оценке формул, чтобы доказать независимость, например, аксиомы (A₁), мы получим, что (A₂)(A₃)1, но (A₁)1. Тогда все формулы, выводимые из аксиом (A₂) и (A₃) при помощи правила (MP), равны 1, но аксиома (A₁) не равна 1, значит, (A₁) независима в системе S₁.

1) Независимость (A₁). Рассмотрим множество истинностных значений 1, 0, н. Определим AB0, если Aн, B1, и AB1 в остальных случаях. Оценка отрицания произвольная. Тогда легко увидеть, что (A₂)(A₃)1, но (A₁)0 при Aн и любом B.

2) Независимость (A₂). Рассмотрим опять множество истинностных значений 1, 0, н. Определим AB0, если A1, B0, и AB1 в остальных случаях. Для отрицания предположим: 1н0, 01. Тогда легко увидеть, что (A₁)(A₃)1, но (A₂)0 при A1, Bн, C0.

3) Независимость (A₃). Рассмотрим множество истинностных значений 1, 0. Используем обычное определение истинностного значения импликации. Определим A0. Тогда, ясно, что (A₁)(A₂)1. Однако (A₃)1:

(BA)((BA)B)(00)((0A)B)1(1B)0,

если B0.