Мат_Логика(лекции)

1.A;

2.` (A→A); (пример 1 выше МР(1,2));

3.A ` A.

Пример 3. A, B ` A B.

Доказательство.

1.A;

2.B;

3. A→(B→A B); A3;

4.	B→A B;	MP (1, 3);
5.	A B;	MP (2, 4).

Следствие: A1, ..., Am ` A1 ... Am.

Следующие две теоремы носят общий характер, т.е. применимы в самой общей ситуации, и потому называются метатеоремами.

Метатеорема 1 (МТ1).
1) A1, ..., Am		` Ai,		1 ≤ i ≤ m;
2)	A1, ..., Am ` B1
	A1, ..., Am		Bn			`
	...........................
	B1, ..., Bn	`
		` C

Доказательство.

1) и 2). Прямое следствие определения.

Метатеорема 2 (МТ2) (теорема дедукции (ТД)). (i) Если = {A1, ..., Am} и , A `

B, то

` (A→B).

( )

(ii) Обратно, если ` (A→B), то , A ` B.

Доказательство.

(i) 1) Если B – аксиома, то

= (A B).

,

(B

`

(A B))

`

B.

` →

→

→

(1)

(

MP

)=

B, B

A

→

B

)

A

→

B

)

→(

` (

2)Если B – член списка , то аналогично ` B (см. пример 2 выше) и, как и выше, получаем ( ).

3)Если B = A, то ` (A→B) (см. пример 1), откуда и ( ) следует очевидным образом.

4)Пусть теперь B получается по правилу МР из двух других формул C и C→B, уже выведенных из , A, и значит, удовлетворяющих условию ( ). (Если это не так, то B очевидно, относится к одному из предыдущих случаев 1)–3).) Другими словами, пусть

i) ` (A→C) и ii) ` (A→(C→B)).

11

Имеем согласно 1) и аксиоме A2 :

` ((A→C)→((A→(C→B))→(A→B))).

Отсюда и из i) и правил вывода МР находим:

` ((A→(C→B))→(A→B)).

Отсюда и из ii) находим

` (A→B).

(ii)Применим правило МР к A, A→B. Отсюда, поскольку по условию A→B выводимо из, ввиду метатеоремы MT1 следует, что B выводимо из , A. Теорема доказана.

Лемма. Пусть A(p1, ..., pm)	– формула		ИВ, где p1, ..., pm – переменные и пусть
(α1, ..., αn) {0, 1}n – набор значений переменных p1, ..., pn. Тогда
p1α1 , ..., pnαn ` A,			A(α1, ..., αn) = 1,
соответственно		¯
α1	αn		A(α1, ..., αn) = 0.
p1	, ..., pn	` A,

Доказательство. Индукция по числу k логических связок , , →,¯.

1)Начальный шаг k = 0 очевиден.

2)Пусть, например, A = A1 A2. A1 = A1(p1, ..., pn), A2 = A2(p1, ..., pn). Тогда

(a) A(α1, ..., αn) = 1

A1(α1, ..., αn) = 1

=

p1α1 , ..., pαn

`

A1;

A2(α1, ..., αn) = 1

α

n

=

p1 1 , ..., pnαn ` A2.

Тогда

p1α1 , ..., pαn

`

A1

α

n

A2

=

p1α1 , ..., pnαn

A.

. 3

p1 1 , ..., pnαn

`

`

= A1, A2 ` A1

A2

= A

(b) A(α1, ..., αn) = 0

, , (b1)

=

( A2

(α1

, ..., αn) = 1

=

α1

αn

¯

p1α1 , ..., pαn

` A2.

A1

(α1

, ..., αn) = 0

=

p1

, ..., pn

A1

;

Тогда

n

`

α1

αn

¯

α1

p1

, ..., pn

A1

MP

αn

( ) :

`

A¯1

→

A1 `

A2

= A¯ =

p1

, ..., pn

` A.¯

Аналогично рассматриваются оставшиеся случаи

( A2

! .

A(α1, ..., αn) = 0 = (

A2

(α1

, ..., αn) = 0

(α1

, ..., αn) = 0

(b2)

A1

(α1

, ..., αn) = 0

A1

(α1

, ..., αn) = 1

Замечание. В доказательстве леммы использовалось утверждение ( ). Это утверждение следует непосредственно из аксиомы A5 :

` A1 A2→A1

12

и примера 7 ниже.
Пример 4:					B ` (A→B).
Доказательство.
1.	B, A ` B;					(MP1);			(Другой вариант решения: применить к B и аксиоме A1 :
2.	B ` (A→B); (ТД).
B→(A→B) правило МР.)
Пример 5:						¯		¯
					A→B, B		` A.
Доказательство.
1.	A→B;					¯	¯		посылка;
2. (A→B)→((A→B)→A); A9;
3.	¯								посылка;
	B;		¯		¯
	(A								MP(1,2);
4.		→	B)	→	A	;
	¯								¯
5.				¯					B,A
	B→(A→B);								A1A,B;
6.		¯							MP(3,5);
	A→B;
7.	¯								MP(6,4).
	A;
							¯	`	¯
Пример 6: A→B, A→B									A.
Доказательство.
1.	A→B;								посылка;
2.		¯				¯	¯		посылка;
	A→B;
3. (A→B)→((A→B)→A); A9;
4.		¯		¯					MP(1,3);
	A→B)→A
5.	¯								MP(2,4).
	A
Пример 7.
				¯		¯
1) A→B ` B→A;

` → ` ¯→ ¯

2) (A B) B A.

Доказательство.

1)Применим ТД к примеру 5.

2)Это следует из 1), так как всякая формула, выводимая из доказуемой формулы, доказуема.

Пример 8: A ` A B.

Доказательство: применить теорему дедукции ТД (ii) к аксиоме A7.

` ¯

Пример 9: A A A.

¯

Доказательство. Это частный случай примера 8 при B = A.

Пример 10:	, A	B	= ` A.¯
	, A	` B¯
		`

Доказательство.

13

1.

, A ` B;

посылка;

2.

¯

посылка;

, A ` B;

3.

(A→B);

ТД (i);

4.

¯

ТД (ii);

(A→B);

5.

¯

пример 6 (3,4).

A;

Пример 11:

`

.

A B

A

Доказательство.

1. ` (A → A B);

A7;

2.

A → A B,

A B

`

A

;

пример 5;

3.

¯

¯

MT1(1,2);

A B

` A;

Пример 12: B A ` A .

Доказательство. Аналогично примеру 11.

					¯
Пример 13: ` A A (закон исключенного третьего).
Доказательство.
				¯
1.	¯				пример 11;
	A A			` A;
	¯			¯
2.				¯	пример 12;
	A A			` A;
3.	¯				пример 10 (1,2);
	A A;			¯
	¯				A10;
4. A A→A A;
5.	¯				MP(4,5).
	A A;
				, A	C	` C.¯
Пример 14: , B					` C = , A B
					`
Доказательство.
1.	, A ` C;					посылка;
2.	, B ` C;					посылка;
3.	` (A→C);					ТД (i);
4.	` (B→C);					ТД (ii);
5.	(A→C)→((B→C)→(A B→C));					A4;
6.	` ((B→C)→(A B→C));					MP(3,5);
7.	` (A B→C);					MP(4,6)
8.	, A B ` C;					ТД (ii).

Теорема (о полноте ИВ). Всякая тождественно истинная формула исчисления высказываний (тавтология) доказуема (выводима):

|= A = ` A.

Доказательство. Пусть A = A(p1, ..., pn) – формула ИВ, где p1, ..., pn – переменные. Если A – тавтология, то

A(α1, ..., αn) = 1

при любых наборах (α1, ..., αn) {0, 1}n значений переменных p1, ..., pn; в частности,
A(α1, ..., αn−1, 1) = 1,	(1)

14

A(α1, ..., αn−1, 0) = 1,					(2)
Согласно предыдущей лемме из (1) и (2) имеем:
p1α1 , ..., pnα−n−11 , pn ` A,
p1α1 , ..., pnα−n−11 , p¯n ` A.		= , B B¯
, B	A		` A) и примера 11
Отсюда и из примера 12 (согласно которому , B¯	` A
¯	`		α1	αn−1	}. Итак,
(согласно которому ` B B) имеем ` A, где в нашем случае = {p1				, ..., pn−1

pα1 1 , ..., pαn−n−11 ` A.

Беря в этой формуле αn−1 = 1 и αn−1 = 0 соответственно, получаем

p1α1 , ..., pnα−n−22 , pn−1	` A,
p1α1 , ..., pnα−n−22 , p¯n−1	` A.
Рассуждая как и выше, получаем отсюда:
p1α1 , ..., pnα−n−22 ` A.		(3)
Продолжая этот процесс, получаем в итоге ` A.

§6. ПРОБЛЕМЫ АКСИОМАТИЧЕСКИХ ТЕОРИЙ: РАЗРЕШИМОСТЬ, НЕПРОТИВОРЕЧИМОСТЬ, ПОЛНОТА, ПРОБЛЕМА НЕЗАВИСИМОСТИ

Для анализа того, насколько удовлетворительно построена формальная аксиоматическая теория, рассматривают ряд проблем:

1.проблема разрешимости;

2.проблема непротиворечивости;

3.проблема полноты;

4.проблема независимости.

Определение. Формальная аксиоматическая теория называется разрешимой, если существует эффективный метод (алгоритм), позволяющий для любой формулы этой теории определить, доказуема (выводима) она или нет.

Определение. Формальная аксиоматическая теория называется непротиворечивой, если в ней не существует формулы, доказуемой одновременно со своим отрицанием.

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

Определение. Формальная аксиоматическая теория называется полной в широком смысле, если всякая тождественно истинная формула в ней доказуема.

15

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

Определение. Система аксиом формальной аксиоматической теории называется независимой, если каждая из ее аксиом независима от остальных.

Считается, что аксиоматическая теория удовлетворительна с точки зрения общих требований, предъявляемых к аксиоматическим теориям, если она разрешима, непротиворечива, полна (в узком и широком смыслах) и обладает независимой системой аксиом.

Рассмотрим исчисление высказываний как формальную аксиоматическую теорию с точки зрения вышеуказанных проблем.

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

Доказательство. Пусть A – произвольная формула ИВ. Составим для A таблицу истинности. По таблице установим, является ли A тождественно истинной. Если да (т.е. |= A), то A доказуема (т.е. ` A) согласно доказанной ранее теореме (|= A ` A). Таким образом, мы имеем в ИВ эффективный метод, позволяющий определить, доказуема ли формула исчисления высказываний или нет.

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

¯

Доказательство. Пусть A – произвольная формула ИВ. Формулы A и A не могут быть одновременно тождественно истинны, а значит, они не могут быть одновременно доказуемы. Теорема доказана.

Теорема 3. Исчисление высказываний является полным в узком смысле .

Доказательство. Пусть A = A(p1, ..., pn) – произвольная недоказуемая формула. Тогда A не является тождественно истинной, т.е. существует такой набор (α1, ..., αn) {0, 1}n, что

A(α1, ..., αn) = 0.

( )

Обозначим исчисление высказываний через S. Соответственно через S1 обозначим новую аксиоматическую теорию, полученную прибавлением к S новой аксиомы A. При этом все правила доказуемости и все определения в S1 остаются прежними. Чтобы доказать, что S полно в узком смысле, нужно доказать, что S1 – противоречивая теория. Для этого в S1 найдем формулу, доказуемую одновременно со своим отрицанием.

Рассмотрим n тождественно истинных формул B1, ..., Bn, где Bi = pi p¯i, i = 1, ..., n (тождественная истинность формул Bi доказана в примере 11 §9). Напомним, что

Bi,	если αi = 1,
Biαi = B¯i,	если αi = 0.

Рассмотрим формулу

C = A(B1α1 , B2α2 , ..., Bnαn ).

Так как Bi тождественно истинны, то Biαi принимают значения αi при любых значениях pi, а значит, C принимает согласно ( ) значение 0 при любых значениях pi, т.е.

16

тождественно ложна. Следовательно, формула ¯ тождественно истинна, а значит,

C C

доказуема в S и, тем самым, в S1, поскольку в S1 правила доказуемости те же, что и в S. С другой стороны, по определению в S1 доказуема формула A, а значит, доказуема и формула C = A(B1α1 , ..., Bnαn ) как полученная из A подстановкой. Итак, в S1 имеется

две противоположные доказуемые формулы и ¯. А значит, 1 противоречива. Теорема

C C S

доказана.

Теорема 4. Исчисление высказываний является полным в широком смысле .

Доказательство. Это не что иное, как теорема о полноте из §5.

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

Доказательство. Для доказательства этой теоремы воспользуемся следующей леммой.

Лемма. Аксиома A данной формальной аксиоматической теории независима от остальных, если все остальные аксиомы обладают некоторым свойством G, которое сохраняется правилами доказуемости, а аксиома A не обладает этим свойством G.

Доказательство. Предположим, что A зависима от остальных аксиом, т.е. получается из них с помощью правил доказуемости. Но тогда поскольку свойством G, которое сохраняется правилами доказуемости, аксиома A также должна обладать этим свойством. Противоречие. Лемма доказана.

Доказательство теоремы. В качестве свойства G возьмем свойство формулы быть тождесвтенно истинной.

1) Возьмем, например, аксиому

A7 : A→A B

и докажем ее независимость от остальных аксиом ИВ. Для этого определим но-новому дизъюнкцию:

	p	q	p q
	1	1	1
	1	0	0
	0	1	1
	0	0	0
При таком определении				( )
	p q = q.

Нетрудно видеть, что все аксиомы ИВ, не содержащие значка , не изменят своих истинных значений, т.е. останутся тавтологиями. Лишь аксиомы A4, A7 и A8 содержат значок дизъюнкции , поэтому проверим их на свойство G, т.е. являются ли они тавтологиями.

A4 перепишется с учетом ( ) так:

(A→C)→((B→C)→(B→C)),

откуда сразу следует, что A4 является тавтологией.

17

Аналогично, A8 перепишется с учетом ( ) как B→B, а значит, очевидно, является тавтологией.

С другой стороны, A7 с учетом ( ) переписывается как A→B, а значит, не является тавтологией, так как принимает значение 0, когда A = 1, B = 0. Следовательно, согласно лемме, A7 независима от остальных аксиом.

Аналогично проверяется независимость A8.

2) Проверим независимость аксиомы A5. Для этого по-новому определим конъюнкцию:

p	q	p q
1	1	1
1	0	0
0	1	1
0	0	0

Тогда, очевидно, p q = q, и прямая проверка показывает, что все аксиомы, кроме A5, в новом определении являются тавтологиями. Следовательно, A5 независима.

Аналогично доказывается независимость аксиомы A6.

3) Подобным же образом доказывается независимость остальных аксиом A1 − A4 и A9, A10. Например, независимость аксиомы A9 доказывается посредством нового определения отрицания:

p	p¯
1	1
0	0

Теорема доказана.

§7. ЛОГИКА ПРЕДИКАТОВ

7.1. Определение предиката.

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

Для этих целей служат предикаты.

Определение. Предикатом G(X1, ..., Xn) называется функция , определенная на некотором множестве DG и принимающая значения И или Л. По числу переменных предикаты называются одноместными, двуместными, ..., n-местными и т.д.

Через DG здесь обозначена область определения предиката G.

Определение. Областью истинности предиката G называется множество

TG = {(X1, ..., Xn) DG | G(X1, ..., Xn) =И}.

Операции над предикатами определяются так же, как и для высказываний. Дадим определение этих операций на примере одноместных предикатов.

18

Определение. Пусть даны одноместные предикаты P (X) и Q(X) с областью определения D. По определению,

R(X) = P (X) Q(X) есть одноместный предикат с областью определения D и областью истинности TR = TP ∩ TQ;

G(X) = P (X) Q(X) есть одноместный предикат с областью определения D и областью истинности TG = TP TQ;

¯

P (X) есть одноместный предикат с областью определения D и областью истинности

D \ TP ;

R(X) = P (X)→Q(X) есть одноместный предикат с областью определения D и областью

\ → ¯ W

истинности (D TP ) TQ; другими словами, (P (X) Q(X)) = P (X) Q(X).

7.2. Кванторные операции

1. Квантор общности .

Определим эту операцию на двухместном предикате (на произвольном n-местном предикате она определяется аналогично). Пусть предикат G(X, Y ), определенный на множестве M, т.е. DG = M × M. Предикат R(Y ) = XG(X, Y ) есть по определению одноместный предикат с областью определения M такой, что

	И,	если для любого X M имеем G(X, Y0) =И,
R(Y0) =	Л	в противном случае, т.е. если существует X0 M

такое, что G(X0, Y0) =Л.

Предикат R(Y ) читается так: "для любого X G(X, Y )".

Определение. R(Y ) называется предикатом, полученным из предиката G(X, Y ) навешиванием квантора общности . При этом переменная Y называется свободной, а переменная X связанной.

В общем случае для n-местного предиката P (X1, ..., Xn), определенного на области M

(т.е. такого, что DP = M × M × ... × M) предикат R = R(X2, ..., Xn) X1P (X1, X2, ..., Xn),

| {z }

n

полученный навешиванием квантора общности на переменную X1, является (n − 1)- местным предикатом. При n = 1 предикат R = X1P (X1) является высказыванием. Переменная X1 под знаком квантора общности называется связанной, остальные переменные X2, ..., Xn – свободными.

2. Квантор существования .

Пусть дан двуместный предикат G(X, Y ). Предикат P (Y ) = XG(X, Y ) по определению есть одноместный предикат, заданный на множестве M (т.е. с областью определения M), такой, что

R(Y0) =	И,	если существует X0 M такое, что G(X0, Y0) =И,
	Л	в противном случае, т.е. если G(X0, Y0) =Л для любого X0 M.

Определение. Предикат R(Y ) называется предикатом, полученным из предиката G(X, Y ) навешиванием квантора существования .

19

Аналогично для любого n ≥ 1 определяется (n − 1)-местный предикат, полученный из n- местного предиката, заданного на множестве M, навешиванием квантора существования.

7.3. Язык логики предикатов

Аналогично логике высказываний определим алфавит логики предикатов (ЛП) и формулы ЛП. Язык ЛП является расширением языка логики высказываний (ЛВ).

Алфавит ЛП:

1. Переменные высказывания: p, q, r, p1, q1, ..., p2, q2, ...

Постоянные высказывания: И, Л.

2. Предметные переменные: X, Y, Z, ..., X1, X2, ..., Y1, Y2, ..., Z1, Z2, ...

Предметные постоянные: a, b, c, a1, b1, c1, ...

3.Предикатные переменные: G, Q, R, G1, Q1, R1, ...

4.Логические связки: , , →,¯, , .

5.Вспомогательные символы: ( , ).

Определение формул ЛП:

1.Каждое переменное или постоянное высказывание по определению является формулой.

2.Если G есть n-местная предикатная переменная, а θ1, θ2, ..., θn – предметные переменные или предметные постоянные, то G(θ1, θ2, ..., θn) – формула.

3. Если и – формулы, то → ¯ – формулы.

A B A B, A B, A B, A

4. Если A(X) – формула, содержащая свободную переменную X, то XA(X) и XA(X) по определению суть формулы.

Из этого определения следует, что все формулы ЛВ являются формулами ЛП.

Значения формул ЛП:

Определение. Сигнатурой σA формулы A логики предикатов называется следующий список переменных, входящих в формулу A:

σA = {X1, ..., Xn, q1, ..., qm, G1, ..., Gl},

где

1)X1, ..., Xn – свободные переменные формулы A,

2)q1, ..., qm – переменные высказывания,

3)G1, ..., Gl – предикатные переменные.

Примеры:

1) A = Y Z(G(X, Y )→G(Y, Z)), σA = {X, G}. 2) A = X(q→G(X)), σA = {q, G}.

20