Лекция № 9. Основные вопросы, рассматриваемые на лекции:

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

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

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

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

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

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

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

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

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

Теорема 1 (истинности). Если |¾ _{S 1} A, то A – тавтология.

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

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

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

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

Предположение: (A 1)=Л
A =И	B Þ A =Л
	B =И	A =Л
Противоречие: A =И и A =Л

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

Предположение: (A 2)=Л
A Þ(B Þ C)=И	(A Þ B)Þ(A Þ C)=Л
	A Þ B =И	A Þ C =Л
		A =И	C =Л
B Þ C =И	B =И
C =И
Противоречие: A =И и A =Л

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

Предположение: (A 3)=Л
Ø B ÞØ A =И	(Ø B Þ A)Þ B =Л
	Ø B Þ A =И	B =Л
		Ø B =Л
Ø A =И	A =И
A =Л
Противоречие: A =И и A =Л

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

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

Доказательство. Если бы было |¾ _{S 1} A ÙØ 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.