Лекция дискрет 15

Th.4.1.5 Теорема дедукции исчисления L (продолжение)

Пусть Γ- множество формул исчисления L, A и B - формулы L. Γ,A ├ B тогда и только тогда, когда Γ ├ A B

Доказательство Th.4.1.5 ( )

Существует вывод B 1,…,B i ,…,B n = B из посылок Γ,A . Индукцией по
длине вывода n доказываем, что для любого k n						Γ ├ A B k
k = 1, т.е. B 1= B Возможные обоснования включения B 1 в вывод
а) аксиома B 1			б) посылка B 1 Γ			в) посылка B 1 = A
1. B 1	аксиома		1. B 1	посылка		1. A A Th.4.1.2
2. B 1(A B 1) A1			2. B 1(A B 1) A1			(A B 1)
3. A B 1	МР к 1,2		3. A B 1	МР к 1,2
Получили:	├A B1		Получили: B 1 ├A B 1			Получили: ├A B1
Th.4.1.1(1): Γ├A B 1			Th.4.1.1(1): Γ├A B 1			Th.4.1.1(1): Γ├A B 1

Предположим, что для любого i < k имеет место Γ ├ A B i и рассмотрим вывод длины k B 1,…,B j,…,B l,…,B k . Возможны четыре обоснования включения B k в вывод

а) аксиома B k		б) посылка B k Γ			в) посылка B k = A
г) B k – результат применения правила MP к предшествующим
	формулам B j и B l = B j B k
а) аксиома B k		б) посылка B k Γ			в) посылка B k = A
1. B k	аксиома	1. B k	посылка		1. A A Th.4.1.2
2. B k (A B k) A1		2. B k (A B k) A1			(A B k)
3. A B k	МР к 1,2	3. A B k	МР к 1,2
Получили:	├A Bk	Получили: B k├A B k			Получили: ├A Bk
Th.4.1.1(1): Γ├A Bk		Th.4.1.1(1): Γ├A Bk			Th.4.1.1(1): Γ├A Bk

Предположили, что для любого i < k имеет место Γ ├ A B i и рассматриваем вывод длины k B 1,…,B j,…,B l,…,B k . Осталось рассмотреть одно возможное обоснование включения B k в вывод

г) B k – результат применения правила MP к некоторым двум предшествующим формулам B j и B l;

в этом случае хотя бы одна из формул B j и B l	должна иметь вид
импликации, пусть, например, B l = B j B k
1. A B j	ИП (т.к. j < k)
2. A ( B j B k )	ИП (т.к. l < k)
3. (A ( B j B k )) ((A B j) (A B k))	А2
4. (A B j) (A B k)	МР к 2,3
5. A B k	МР к 1,4

Индукционное предположение: Γ├ A B j и Γ ├ A ( B j B k ), т.к. j < k и l < k. Применяя Th.4.1.1(3), получаем Γ ├ A B k

Доказано Th.4.1.5

Пример к Th.4.1.5		Γ,A ├ B		( ) Γ ├ A B
Следствие к Th.1.4.6		Γ,A ├ B
Если	М’ М		то М’ - счётное B
	М’ - бесконечное
	М - счётное
	М = Q, М’ = Q+	A	[«избыточная» – см. Th.4.1.1(1)]
	Применим теорему дедукции, получим Γ ├ A B
Пусть	М’ М		Если	М = Q, М’ = Q+,	A	B
	М’ - бесконечное		то М’ = Q+- счётное

М - счётное

Q и Q+ - множество рациональных чисел и множество неотрицательных рациональных чисел соответственно

Антипример к Th.4.1.5		Γ,A ├ B		( ) Γ ├
Th.1.4.6			Γ,A ├ B
Если	N’ N		то N’	- счётное B
	N’ - бесконечное
	[ N’, + ] - аддитивная		A [«избыточная» – см.
	абелева полугруппа
	Применяем теорему дедукции:
Пусть	N’ N		Если	[ N’, + ] - ААП
	N’ - бесконечное		то	N’ - счётное

A B

Th.4.1.1(1)]

A B

ААП – аддитивная абелева полугруппа: например, если N’ – множество нечётных чисел, то N’ не замкнуто относительно операции сложения; значит, [ N’ , + ] вообще не образует полугруппу. Тем не менее, A B

есть истинное утверждение, так как любое бесконечное N’ – счётное. Получили формально выводимую из , но сомнительную по содержанию формулу A B

Доказали:	Γ,A ├ B ( )	Γ ├ A B
Пусть:	A 1 , A 2 , A 3 ├ B
	Тогда верно:
A 1 , A 2 ├ A 3 B A 1 , A 3 ├ A 2 B A 2 , A 3 ├ A 1 B
	…………………….
A 3 ├ A 1 (A 2 B ) ….. ├ A 3		(A 2 (A 1 B ))

Когда имеют дело с длинными цепочками дедуктивных рассуждений, уже не так легко сохранить уверенность, что не сбился в сторону. А во время спора говорящий может и умышленно пытаться склонить своих слушателей к заключению, которое не вполне оправдано его посылками.

С.Клини

Эффектный и эффективный, но опасный приём:

Дополнительное введение необходимых посылок с последующим их удалением применением Th.4.1.5 (слева направо)

		Г, A ├ B Г├A B
		Допустим, имеет место выводимость├ B
1.	A	посылка: согласно Th.4.1.1(1) при расширении
		множества посылок выводимость сохраняется,
		поэтому выполняется A ├ B (при этом = )

2.

3.

B

A B

по условию имеет место выводимость ├ B

Th.4.1.5 к 1 и 2

Любое утверждение A может быть объявлено причиной B !

Сравните:
B	Сегодня утром солнце взойдёт на востоке
A	Ночью комары громко пищали

Дедукция – вывод частных заключений из общего утверждения

Холмс: Ватсон! Взгляните на эти звезды и расскажите мне, какой вывод, используя дедуктивный метод, вы можете сделать.

Ватсон: Я вижу на небе миллионы звезд. А раз они существуют, значит, среди них, возможно, есть и планеты. Из чего мы, в свою очередь, делаем вывод, что некоторые из них напоминают нашу Землю. Следовательно, на каких-то из них может существовать жизнь.

Холмс: Ватсон, вы – идиот. Это означает, что у нас украли палатку.

3) Свойства исчисления высказываний L - продолжение

	Th.4.1.6	Для любых формул A , B и C исчисления L имеет место
		A B , B C ├ A C
		Будем строить вывод A B , B C , A ├ C
1.	A B	посылка
2.	B C	посылка
3.	A	посылка
4.	B	МР к 1,3
5.	C	МР к 2,4
6.	A C	Th.4.1.5 к 3,5
!	Транзитивность импликации и причинно-следственной связи

Если сумма цифр числа М делится на 9 (A ), то число М делится на 9 (B ). Если число М делится на 9 (B ), то его можно представить в виде М=3Ν (C ).

Если сумма цифр числа М делится на 9 (A ), то его можно представить в виде М=3Ν (C ) .

Транзитивность причинно-следственной связи

A B , B C ├ A C

A

B

C

A B B C

A C

У меня высокая температура

Яболен

Яне пойду на занятия

Если у меня высокая температура, то я болен Если я болен, то я не пойду на занятия

Если у меня высокая температура, то я не пойду на занятия