Матлогика(Лагодинский)

Применение логики предикатов к логико-математической практике

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

Определение предела последовательности “Число a называется пределом последовательности {an}, если для всякого положительного числа ε >0 существует такое натуральное число n0, что для всякого натурального n, большего n0, |an– a|<ε” на языке логики предикатов записывается так:

îïð

a=lim an Û ("ε)[ε>0®($n0)(n0 ÎNÙ("n)(n>n0 ®| an -a|<ε))].

Короче это можно записать так:

îïð

a=lim an Û ("ε>0)($n0 ÎN)("n>n0)(| an -a|<ε).

Утверждение “Число a не является пределом последовательности {an}” означает, что существует такое положительное число ε, что для всякого натурального n0 найдется такое натуральное n>n0, что |an– a|≥ε. На языке логики предикатов это запишется так:

($ε>0)(n0 ÎN)($n>n0)(| an -a|³ε).

Теоремы математики допускают формулировки в виде условных предложений. Часто в теореме можно выделить три части: условие теоремы – предикат P(x), заданный на множестве M1, заключение теоремы – предикат Q(x), заданный на множестве M2, разъяснительная часть, описывающая множества объектов, о которых идет речь в теореме. Строение теоремы может быть таким: “Если любой элемент x из множества M обладает свойством P(x), то он обладает свойством Q(x)”. Теорема формулируется так: ("xÎM)(P(x) ®Q(x)). Например, теорема о конечных приращениях (теорема Лагранжа) гласит: “Если f(x) непрерывна на [a, b] и дифференцируема на (a, b), то найдется на (a, b) такая точка c, что f(b) -f(a) =f¢(c)(b-a). ” Пусть предикат P(a,b,x) выражает свойство функции y=f(x) быть непрерывной на [a, b] и дифференцируемой на

41

(a, b), а Q(a,b,x) =(f(b) -f(a) =f¢(c)(b-a)). Тогда теорема Лагранжа может быть сформулирована так: ($cÎ(a,b))(P(a,b,x) ®Q(a,b,x)).

5. Формализованное исчисление предикатов

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

Алфавит исчисления предикатов состоит из предметных переменных x1, x2,..., предметных констант c1, c2,..., предикатных

букв P1n,P2n, , функциональных букв f1n,f2n, , знаков логических связок ¬, , , →, кванторов , и скобок (, ). Верхние индексы предикатных и функциональных букв указывают число аргументов.

Термами являются отдельно взятые предметные переменные и константы,атакжевыражениявидаfn(t1,...,tn),гдеfn–n-местный функциональный символ, t1,..., tn – термы.

Формула исчисления предикатов определяется следующим об-

разом:

1) еслиPn–предикатнаябуква,t1,...,tn–термы,тоPn(t1,...,tn)– формула, при этом все вхождения переменных в эту формулу назы-

ваются свободными;

2) если F1,F2 – формулы, то формулами являются F1,(F1 ® F2),

(F1 ÙF2),(F1 ÚF2) – тоже формулы;

3) если F(x) – формула, содержащая свободные вхождения переменной x, то ("x)(F(x)) и ($x)(F(x)) – формулы, при этом вхождения переменной x в них называются связанными, вхождения же всех остальных предметных переменных в эти формулы остаются свободными (связанными), если они были свободными (связанными) в формуле F(x), которая называется областью действия квантора;

4) никаких других формул нет.

Совокупность G={c1, c2,...: f1, f2: P1, P2,...} называется сигнатурой данного исчисления предикатов.

Система аксиом исчисления предикатов состоит из двух групп:

первая – это аксиомы исчисления высказываний ИВ, а вторая включает следующие аксиомы:

42

PA1 ("x)(F(x)) ® F(y);

PA2 F(y) ®($x)(F(x));

где F(x) – любая формула, содержащая свободные вхождения x, причем ни одно из них не находится в области действия квантора по y (если таковой имеется); формула F(y) получена из формулы F(x) заменой всех свободных вхождений x на y.

Правила вывода. К правилу вывода MP из исчисления высказываний добавляются еще два правила вывода:

"	-правило, или правило обобщения		F®G(x)		;
		F®("x)(G(x))
$-правило,илиправилоконкретизации				G(x) ® F		приусло-
				($x)(G(x)) ® F

вии, что G(x) содержит свободные вхождения x, а F не содержит. Формула G называется выводимой из гипотез F1,..., Fm с фик-

сированными вхождениями в гипотезы свободных переменных, если существует такая конечная последовательность формул B1, B2,..., Bk=G, каждая формула которой является либо аксиомой, либо гипотезой, либо получена из предыдущих формул последовательности по одному из правил вывода (сама эта последовательность называется выводом G из гипотез F1,..., Fm). При этом, если Bi есть первая гипотеза, встречающаяся в выводе, то дальше в этом выводе не могут быть использованы " - и $-правила вывода по любой переменной x, которая входит свободно хотя бы в одну из гипотез. Обозначение используется то же, что и в исчислении высказываний: F1,..., Fm|–G. Если гипотезы отсутствуют, то говорят,

что G выводима из аксиом (или просто выводима), и называют G

теоремой исчисления предикатов и пишут |–G.

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

Поскольку не является разрешимой логика предикатов, то и исчисление предикатов не является разрешимой теорией.

Другим важнейшим требованием, предъявляемым к аксиоматической теории, является ее непротиворечивость. В непротиворечивой теории невозможно доказательство истинности какого-либо утверждения и его отрицания одновременно. Однако доказательство этого свойства теории весьма сложно (и из-за бесконечности утверждений теории, и из-за отсутствия точного понятия доказательства). Поэтому в математике более естественным считается другой признак непротиворечивости теории.

43

Формальная теория T есть теория множества M(T) всех своих моделей, поэтому она семантически (т. е. по смыслу) непротиворечива, если и только если M(T) ¹Æ, т. е. существует хотя бы одна ее содержательная модель (интерпретация). Исчисление предикатов семантически непротиворечиво.

Неприятие современниками неевклидовой геометрии Лобачевского-Бояи объясняется тем, что законность этой теории обосновывалась отсутствием в ней противоречий, ее модели были построены значительно позже. Но развитие математической логи-

ки привело и к доказательству формальной (синтаксической) не-

противоречивости исчисления предикатов.

Логическая система называется полной в узком смысле, если нельзя без противоречия присоединить к ее аксиомам в качестве новой аксиомы никакую не выводимую в ней формулу так, чтобы полученная при этом система была бы непротиворечивой. В отличие от исчисления высказываний исчисление предикатов не является теорией, полной в узком смысле. К его аксиомам можно присоединить без противоречия недоказуемую в ней формулу ( x) (F(x))→( x)(F(x)). Содержательный смысл этой формулы состоит в том, что все предметы тождественны. Эта формула ложна, если область определения предиката F(x) содержит больше, чем один предмет, но истинна для одноэлементных множеств. Однако логически ниоткуда не следует, что существуют многоэлементные множества.

Логическая система называется полной в широком смысле, если любая тождественно истинная формула в ней доказуема. Исчисление предикатов полно в широком смысле.

Ни одна из аксиом исчисления предикатов не выводима из других. Это означает, что система аксиом исчисления предикатов не-

зависима.

44

Заключение

Логика, опыт и интуиция

Нужно теперь признать, что, хотя логика необходима для познания реального мира, она все же недостаточна. Логика связывает факты, которые дает опыт, эксперимент. Но для построения теории необходим еще и набор аксиом. Аксиомы не могут быть получены только логикой – они не могут (по определению) быть доказаны. Но они не могут быть взяты непосредственно из опыта.

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

Возникает естественный вопрос: как выбрать эти новые аксиомы, если они невыводимы?

Великий голландский философ Б.Спиноза учил, что существуют три пути (способа) познания: а) интуитивный, б) логический и в) чувственный. При этом первый – высший, а третий – низший. Но интуиция по Спинозе – это не мгновенное озарение (таково обыденное понимание этого слова), а целостное усмотрение истины, вытекающее из всех знаний познающего субъекта, несводимое к логике. Нельзя логически доказать, что А.С. Пушкин – великий поэт, тем не менее мы это хорошо знаем.

А. Эйнштейн (который хорошо знал и понимал учение Б. Спинозы) говорил, что аксиомы – свободное творение человеческого сознания и вводятся интуитивно, без опоры на логику. Из аксиом логически выводятся теоремы, из них – другие теоремы, и если теория имеет отношение к реальному миру, из этих теорем делаются выводы о свойствах реального мира. Если оказывается, что на самом деле эти свойства – другие, то теория опровергается. Но если все выводы теории согласуются с опытом, это еще не означает, вообще говоря, истинности теории. Мы знаем, что импликация A→B при истинном B истинна независимо от A. Известно, что Кар-

45

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

Варианты контрольных работ

Каждый вариант содержит 9 заданий. 1. Доказать равенство множеств.

2. Построить таблицу истинности для логической функции f(x, y, z).

3. Найти выражение для функции, двойственной функции f(x, y, z) и определить номер двойственной функции.

4. Упростить выражение для функции f(x, y, z).

5. Найти СДНФ и СКНФ для функции с заданным номером и упростить по методу Квайна СДНФ.

6. Найти полином Жегалкина для функции с заданным номером.

7. Доказать секвенцию табличным методом. 8. Доказать тавтологию методом резолюций. 9. Проанализировать вывод секвенции.

Вариант 1.

1. (C∆( A\ C)) \ B=( AÈC) \ B.

2. f(x,y,z) =(x¯y) Ùy~ z.

3. f(x,y,z) =((x. ~ y) ~ (y¯z)) Ú(y| z).

4. f(x,y,z) =(x| y) ¯(yÚz) Å(yÙz).

5.  N(f) =120 6.  N(f) =198.

7. (aÙb) ®b, bÚ(aÙc) |=(a®b) Ú(aÙc).

8. |=( A® B) Ù A® B.

9. 1)  AÚB, A |= AÚB; 4)  AÚB, B|= AÚB; 7)  A, B|= AÙB; 2)  AÚB, A |= AÚB; 5)  AÚB, B|= AÚB; 8)  AÚB|= AÙB;

46

3)  AÚB|= A; 6)  AÚB|= B; 9) |= AÚB® AÙB.

Вариант 2.

1.  BÇ(C∆( AÇC) = BÇ( AÈC).

2. f(x,y,z) =(xÅy) Ú(yÙz).

3. f(x,y,z) =(x~ y) ¯(yÚz) Å(yÙz).

4. f(x,y,z) =(x¯y) | (yÙz) Ù(yÚz).

5.  N(f) =225 6.  N(f) =105.

7. a®b, b®c|=(aÚb) ®(bÙc).

8. |=( A® B) Ù( AÙC® BÙC).

9. 1)  A,B|= AÙB; 4)  A,C|= AÙC; 7)  A, BÚC|=( AÙB) Ú( AÙC). 2)  AÙB|=( AÙB) Ú( AÙC); 5)  AÙC|=( AÙB) Ú( AÙC);

3)  A,B|=( AÙB) Ú( AÙC); 6)  A,C|=( AÙB) Ú( AÙC);

Вариант 3.

1. ( A∆(B\ A)) \ C=( AÈB) \ C.

2. f(x,y,z) =(xÅy) Ùy| z.

3. f(x,y,z) =((x®y) Ù(zÅy).

4. f(x,y,z) =(x~ y) ~ (yÚz) Ú(y| z).

5.  N(f) =156 6.  N(f) =54.

7. (aÙb) ®b, bÚ(aÙc) |=(a®b) Ú(aÙc).

8. |=( A® B) Ú(C® D) ®( AÙC® BÚD).

9. 1)  AÚB, A |= AÚB; 4)  AÚB,B|= AÚB; 7)  A, B|= AÙB; 2)  AÚB, A |= AÚB; 5)  AÚB,B|= AÚB; 8)  AÚB|= AÙB; 3)  AÚB, A|= A; 6)  AÚB|= B; 9) |= AÚB® AÙB.

Вариант 4.

1. ( AÇC)∆((C\ B) \ A) =( AÈB) ÇC.

2. f(x,y,z) =(x| y) Úy®z.

47

3. f(x,y,z) =(xÙy) ®(y¯z) ~ (zÙy).

4. f(x,y,z) =(x¯y) Å(y®z) Ú(yÙz).

5.  N(f) =99 6. N(f) =154.

7. a, aÙc|=(aÚbÚc) ®(bÚc) ®(aÙb)

8. |=( A®C) Ù(B®C) ®( AÚB®C).

9. 1)  A, AÚC|= AÚ(BÙC); 4)  B,C|= AÚ(BÙC); 7)  AÚB, AÚC|= = AÚ(BÙC).

2)  B,C|=BÙC; 5)  B, A|= AÚ(BÙC);

3)  BÙC|= AÚ(BÙC); 6)  B, AÚC|= AÚ(BÙC);

Вариант 5.

1.  AÇ(B∆BÈC) =( AÇ(BÈÑ). 2. f(x,y,z) =(x¯y) Ùy®z.

3. f(x,y,z) =(x~ y) ®(y¯z) ~ (zÚy).

4. f(x,y,z) =(x| y) Å(y¯z) ~ (y\ z).

5.  N(f) =225 6.  N(f) =105.

7. a®(b®a), (a®b) Ùc|=(aÚb) ®((a®c) ®a). 8. |=( AÙB®C) ®( A®(B®Ñ)).

9. 1)  A|= A; 4)  A, A |= A; 7) |= A ~ A.

2) |= A® A; 5)  A|= A;

3)  A, A |= A; 6) |= A® A;

Вариант 6.

1. ( AÇC)∆((BÇC) \ A) =CÇ(BÈ A).

2. f(x,y,z) =(xÅy) Ùy¯z.

3. f(x,y,z) =((x¯y) | (yÙz) ®(z® y).

4. f(x,y,z) =(x| y) ¯(yÚz) Ú(yÙz).

5.  N(f) =89 6.  N(f) =150.

48

7. aÚb, aÙb|=(aÚbÚc) ®(cÚ(aÙb).

8. |=( A® B) ®(( A®(B®Ñ)) ®( A®C)).

9. 1)  A|= AÚ(BÚC); 4)  B|= AÚ(BÚC); 7)  AÚB|= AÚ(BÚC); 2)  B|=BÚC; 5) C|=BÚC; 8) ( AÚB) ÚC|= AÚ(BÚC).

3)  BÚC|= AÚ(BÚC); 6) C|= AÚ(BÚC);

Вариант 7.

1.  BÇ( A∆( A\ C)) = B\ ( AÇC).

2. f(x,y,z) =(x~ y) Úy| z.

3. f(x,y,z) =(x| y) ¯(yÙz) ®(zÚy).

4. f(x,y,z) =(xÅy) ®(y| z) Ù(y¯z)

5.  N(f) =86 6.  N(f) =149.

7. a®b, b®c|=(a®b) ®(bÙc) Ú(b®c) Ú(bÚa).

8. |=( AÙB®Ñ) ®( AÙC® B).

9. 1) |= AÚ A; – теорема 5)  B|= AÚB; 9)  A |= AÙB® AÚB;

2)  AÙB, A, B|= AÙB; 6)  A, AÙB|= AÚB; 10)  AÚ A |= AÙB®

®AÚB;

3)  AÙB, A, B|= AÙB; 7)  A |= AÙB® AÚB; 11) |= AÙB® AÚB. 4)  A, AÙB|= B; 8)  A, AÙB|= AÚB;

Вариант 8.

1.  BÇ(C∆( A\ C)) =BÇ(CÈ A).

2. f(x,y,z) =(x~ y) Ùy®z.

3. f(x,y,z) =((x~ y) Ú(y| z)) Ù(z® y).

4. f(x,y,z) =(x~ y) Å(y¯z) Ú(y| z).

5.  N(f) =210 6.  N(f) =101.

7. a®b, c®a|=b®(aÚc).

8. |=( AÙC® B) ®( AÙB®Ñ).

9. 1)  A® B,B®C, A|=B; 5) ( A® B) Ù( B®C) |= A® B;

49

2)  A® B,B®C, A|=B®C; 6) ( A® B) Ù( B®C) |= B®C;

3)  A® B,B®C, A|=C; 7) ( A® B) Ù( B®C) |= A®C;

4)  A® B,B®C|= A®C; 8) |=( A® B) Ù( B®C) ®( A® B).

Вариант 9.

1.  BÇ( A∆( A\ C)) = B\ ( AÇC).

2. f(x,y,z) =(x| y) ÚyÅz.

3. f(x,y,z) =((x| y) Ù(yÚz)) Ù(zÅy).

4. f(x,y,z) =(yÙz) \ (xÅy) ¯(y~ z).

5.  N(f) =54 6.  N(f) =120.

7. ((a®b) Ù(a®b) ®a, (aÚb) ®(bÙc) |=(a®b) Úb®c.

8. |=( A®(B®C)) ®( AÙB®Ñ).

9. 1)  AÚ A, A|= AÚ A; 5)  AÚ A, A|= AÚ A; 2)  AÚ A, A|= AÚ A; 6)  AÚ A|= A;

3)  AÚ A|= A; 7) |= AÚ A;

4)  AÚ A, A|= AÚ A; 8) |= AÚ A.

Вариант 10.

1. ( A∆( AÇC)) \ B=( AÈC) \ B.

2. f(x,y,z) =(x~ y) Ùy| z.

3. f(x,y,z) =((x¯y) | (yÚz)) ÙzÙy.

4. f(x,y,z) =(yÙz) Å(x®y) ~ (yÙz).

5.  N(f) =147 6.  N(f) =210.

7. c®(aÚb), c®(aÙb) |=aÚbÚ(aÙb).

8. |=( A® B) Ù(C® B) ®( AÚC® B).

9. 1)  A, AÙB|= A; 5)  B, AÙB|= B;

2)  A, AÙB|= A; 6)  B|= AÙB; 3)  A |= AÙB; 7)  AÚB|= AÙB;

4)  B, AÙB|= B; 8) |= AÚB® AÙB.

50