Формальная логика



страница7/7
Дата15.05.2016
Размер1.06 Mb.
#12946
ТипРеферат
1   2   3   4   5   6   7

ТЕОРЕМА 1 (Подстановка вместо атомов). Если подстановка формул A1(,,), , Am(,,) свободна в формуле E[P1,,Pm] для предикатных букв P1(,,),,Pm(,,), соответственно. Тогда, если = E[P1,...,Pm], то = E* [A1,,Am ].

Следствие. Если подстановка переменных y1,...,yn свободна для w1,...,wn, соответственно, в формуле A(w1,,wn), то = A(w1,,wn)  = A(y1,,yn).

ТЕОРЕМА 4 (Эквивалентность формул). = A  B т.и т.т., когда для любой предметной области D и при любой интерпретации  предикатных букв, и любом означивании  предметных переменных на элементах области D, A[,] = B[,].

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

УТВЕРЖДЕНИЕ 3. Для конгруентных формул A и B верно = A  B.



Основные тавтологии исчисления предикатов (с кванторами):

x A(x)  xA(x)

x A(x)  xA(x)

xy A(x,y)  yx A(x,y)

xy A(x,y)  yx A(x,y)

x A(x) &xB(x)  x (A(x) & B(x))

x A(x)x B(x)  x (A(x)B(x))

x A(x)x B(x) x (A(x)B(x))

x (A(x)&B(x)) x A(x) & x B(x)

x (A(x)B(x)) (x A(x) x B(x))

Если формула C не содержит свободно x, то :

x C  C,

x C  C

x A(x)  C  x (A(x)C)

x A(x) &C  x (A(x)&C)

Теоремы 6 и 7 могут быть обобщены в исчислении предикатов, если в описание операций ‘X’(‘крест’) и ‘/’ (‘штрих’) включить замену  на  и  на .



Формула B является логическим следствием формул A1,...,Am , если для любой области D   и любых интерпретаций , , входящих в формулы A1, ... , Am , B предикатных букв и свободных предметных переменных, в строках таблицы истинности, где A1[,] = ... =Am[,] = И, также и B[,] = И. Обозначим как A1, ... , Am = B.

Данное определение соответствует условной интерпретации переменных

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

x (x2-5x-6=0  x=6x = -1), в отличие от интерпретации всеобщности

переменных : xy(x+y=y+x)2+3=3+2.

При таком определении логического следствия теорема 8 и ее следствие обобщаются на исчисление предикатов. Доказательства там и здесь по сути совпадают.



Примеры отношений логического следования:

P(x)= P(x); P(x)=xP(x); P(x) = P(y);

P(x)= xP(x); xP(x)= P(x); P(x) = xP(x);

x P(x)= P(y); P(y) = xP(x); x P(x) =yP(y).

Из таблицы истинности увидим, какие из них имеют место. Пусть D={0,1}, проинтерпретируем на D предикатную букву P(x), так что:


x y

P(x)

P(x)

x  P(x)

P(y)

x P(x)

x P(x)

0 0

0 1


1 0

1 1


J1

J1

J1

J1



Л

Л

Л



Л

Л


л

л

л



л

И

Л


0 0

0 1


1 0

1 1


J2

J2

J2

J2



Л

Л

И



И

Л


л

и

л



и

Л

И


0 0

0 1


1 0

1 1


J3=л

J3=л

J3

J3



И

И

Л



Л

Л


и

л

и



л

Л

И


0 0

0 1


1 0

1 1


J4

J4

J4

J4



И

И

И



И

И


и

и

и



и

Л

И


Очевидно, что верны следующие отношения логического следования:

P(x)= P(x), P(x)= xP(x), xP(x)= P(x). Убедиться, что они верны без ограничений на число элементов области D. А отношения P(x)= xP(x); P(x) = P(y); P(x) = xP(x) не имеют места.



Упражнение

  1. Построить истинностные таблицы над областью D = {1,2} следующих

формул:

(a) z (P(x)  Q  P(z)); (b) P(x,y) x (P(x,y)x P(x,x)).

2. Докажите, что формула xy P(x,y)  yx P(x,y) 1-общезначима.


  1. Докажите, что следующие формулы не общезначимы:

  1. (xy P(x,y)  yx P(x,y));

  2. xy P(x,y)  x P(x,x);

  3. x P(x)  x Q(x)  x (P(x)  Q(x)).

4. Общезначимы ли следующие формулы?

(a) P(x) x P(x), (b) x P(x)  P(x), (c) x P(x)  x P(x),

(d) x P(x) x P(x), (e) y (P(y)x (P(x)Q))y (P(y)x(P(x)Q)).

5. Доказать УТВЕРЖДЕНИЕ 1 и УВЕРЖДЕНИЕ 2(a).

6. Применимо ли УТВЕРЖДЕНИЕ 1 к доказательству общезначимости

следующих формул или установите это другим способом:

(a) xy P(x,y)  y P(y,y); (d) xz P(x,z)  z P(y,z);

(b) y P(y,y)  xy P(x,y), (e) P(x,x)  y P(x,y);

(c) P(x,x)  y P(y,y); (f) y P(x,y)  P(y,y).


  1. Выполнить указанные подстановки и выяснить, свободны ли эти

подстановки:

  1. zP(z,w,y), Q вместо P(w), Q в P(z) Q;

  2. xP(x,w,y), Q(w) вместо P(w), Q(w) в y( P(z) Q(y));

  3. zP(z,w,y), Q(w) вместо P(w), Q(w) в x( P(x) Q(x));

  4. P(w,v,x), Q вместо P(v,w),Q(w) в x(P(x,y)Q(x) P(y,x));

  5. zQ(z,w,w,y), xP(v,w,x) вместо P(w),Q(v,w) в x( P(x) Q(x,x));

  6. zQ(z,w,w,y), xP(v,w,x) вместо P(w),Q(v,w) в x( P(x) y Q(y,y));

  7. zwP(z,w,y), Q(z,w)& wR(w) вместо P(w), Q(w) в zP(z) Q(z).

8. Найти эквивалентные формулы с тесными отрицаниями:

  1. x (( P(x)yQ(x,y))yR(y));

  2. ((xP(x)xQ(x,y))xP(x)).

  1. Доказать УТВЕРЖДЕНИЕ 3.

10. Найдите: (a) формулу, которая была бы 1-общезначимой и 2-общезначимой, но не была бы 3-общезначимой; (b) формулу, которая была бы 1-, 2-, 3-общезначимой, но не 4-общезначимой.

11. Доказать, что = A т. и т. т., когда = x A, и не всегда A = x A.



2. 2. Система аксиом в исчислении предикатов

Аристотелевская силлогистика была развита в дальнейшем в исчисле ние предикатов*), где она именуется как исчисление классов, или одно местных предикатов. Во времена Аристотеля не было известно исчисле ние высказываний, однако многие законы исчисления высказываний он интуитивно использовал. Ощущая ограниченность своей силлогистики, Аристотель

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

А к с и о м ы:

1а A(BA)

1б (AB)((A(BC))(AC))

2 A(BA&B)

3а A&BA


3б A&BB

4а AAB


4б BAB

5. (AC)((BC)(ABC))

6. (AB)((A B) A)

7. AA


8. (AB)((A B) (A  B))

9а. A  B  (AB)

9б. A  B  (BA)

10. A (AC)

и п р а в и л о в ы в о д а modus ponens .

Н о в ы е а к с и о м ы и п р а в и л а в ы в о д а:

11 С A(x)  C x A(x) (- введение)

12 x A(x)A(t) (- удаление)

13 A(x)C  x A(x)C ( - удаление)

14 A(t)x A(x) ( - введение),

где подстановка терма t свободна для переменной x в формуле A(x), и формула C не содержит свободно x.

Ф о р м у л а B в ы в о д и м а и з ф о р м у л A1,  , Am , если существует список формул B1,,Bl такой, что Bl=B, и каждая формула Bi есть аксиома или одна из формул A1, …, Am , или получается из предыдущих формул по одному из правил вывода, где все свободные переменные формул A1, …, Am остаются фиксированными, т.е. правила с кванторами (, ) не применяются ни к какой переменной, входящей свободно в формулы A1, …, Am, кроме случаев, когда эти правила применялись до использования формул A1, …, Am в качестве допущений.

ТЕОРЕМА (О дедукции). Если A1, …, Am  B, то A1, …, Am-1  AmB, где применение правил -введения и -удаления фиксированно для свободных переменных формул A1, …, Am .

(Без доказательства).

ТЕОРЕМА (Производные правила вывода). Производные правила исчисления высказываний с формулами исчисления предикатов и новые правила с кванторами.




(-удаление) ( - введение)

( - введение) ( -удаление),

где t свободно для x в A(x). где x не входит свободно в Г,C.


ТЕОРЕМА (О замене). Если - A ~ B и E[A] -формула с выделенным вхождением подформулы A, а E[B]=E[A] - результат замены этого вхождения на формулу B, x1,...,xp - свободные переменные формул A, B, попадающие в область действия кванторов формул E[A] или E[B] при построении их, начиная с A, B, соответственно. Тогда если Г  A  B,

то Г - E[A] ~ E[B], где Г список формул, не содержащих свободно переменные x1,...,xp .

ЛЕММА. Пусть x – некоторая переменная, A(x) – произвольная формула, а y произвольная переменная, не обязательно отличная от x, такая, что:


  1. ‘y’ свободна для ‘x’ в A(x), (ii) ‘y’ не входит свободно в A(x) (кроме случая, когда ‘y’ есть ‘x’), а A(y) есть результат подстановки ‘y’ вместо свободных вхождений ‘x’ в A(x).

Тогда: (a)  x A(x)  y A(y); (b)   x A(x)  y A(y).

УТВЕРЖДЕНИЕ. Если формулы A и B конгруентны, то - A ~ B.



Примеры построения доказательств :

1). -  x A(x)~x  A(x) :

1. x A(x) (допущение)

2. A(x) (допущение противного)

3. x A(x) ( - введение)

4. A(x) ( - введение,2)

5. x A(x) ( - введение, 4)

6. A(x)x  A(x) (теорема дедукции,1,5)

7. x  A(x) (допущение)

8. x A(x) (допущение противного)

9.  A(x) (допущение)

10 A(x) (- удаление,8)

11.  x A(x) (слабое удаление )


  1. x A(x) ( - удаление,7)

  2. x A(x) (-введение,8)

14. x  A(x) x A(x) (теорема дедукции,7,12)

15.  x A(x)  x  A(x) ( - введение, 6,13).

2) x (P(x)Q(x))  x P(x) x Q(x) :


  1. x (P(x)Q(x)), x P(x)  P(x)Q(x) (удаление)

  2. x (P(x)Q(x)), x P(x)  P(x) (удаление)

x (P(x)Q(x)), x P(x)  Q(x) (удаление)

x (P(x)Q(x)) x P(x)  Q(x) (введение)

x (P(x)Q(x)) x P(x) x Q(x) (введение)

Формула вида Q1 x1…Qn xn A, где A бескванторная формула, а Qi есть  или , называется предваренной (или пренексной) нормальной формой.



ТЕОРЕМА 9. У всякой формулы исчисления предикатов есть эквивалентная ей предваренная нормальная форма.

ТЕОРЕМА (Геделя о полноте исчисления предикатов). - E  = E.

(Без доказательства).



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

Упражнение

1. Обосновать допустимость производных правил вывода исчисления предикатов.

2. Доказать основные тавтологии исчисления предикатов с кванторами.

3. Доказать, что следующие теоремы имеют место, если A(x,x) является результатом подстановки ‘x’ вместо свободных вхождений ‘y’ в A(x,y), причем ‘x’ свободно для ‘y’ в A(x,y) :



  1. xy A(x,y)x A(x,x) b)x A(x,x)xy A(x,y)

4. Какое из утверждений верно: A(x)  x A(x) или  A(x) x A(x)?

5. Привести к предваренной форме формулу:

(x P(x)x Q(x)) & (Rx S(x))

6. Являются ли выводимыми следующие формулы:



  1. xy A(x,y)  y A(x,y);

(b) A(x)x A(x);

(c) (A(x)x A(x))(x A(x)(A(x)x A(x)));



  1. x A(x)(A(x)x A(x));

  2. (x A(x)A(y))  (xA(x)yA(y));

  1. (A(y)x A(x))  (yA(y)x A(x))).

7. Доказать УТВЕРЖДЕНИЕ об эквивалентности конгруентных формул.

Г л а в а 3
ФОРМАЛЬНАЯ АРИФМЕТИКА

Индукция математическая - полная индукция, средство доказа тельства общих положений в математике и др. дедуктивных науках. Метод математической индукции опирается на два суждения – единичное (базис индукции) – A(0), утверждающее выполни мость свойства A(.) для 0. Второе суждение (общее, условное) означает, что если из того, что произвольное число n обладает свойством A(n) (индукционное допущение), то и следующее за n натуральное число n+1 обладает этим свойством (индукционный шаг). Тогда делается заключение, что любое натуральное число n обладает свойством A(.).

Опишем теперь одну формальную систему, предназначенную для

формализации элементарной теории чисел.

А л ф а в и т: (1) символы алфавита исчисления предикатов: предикатные

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

(2) предикатная константа : = ;

(3) функциональные константы : , +,  ;

(4) предметная константа : 0 ;

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

Т е р м ы : (1) а , b, c , …- предметные переменные ;

(2) 0 – предметная константа ;

(3) если t, s – термы, то t , t + s, t  s – термы.

Ф о р м у л ы: (1) t = s, где t, s – термы, - элементарные формулы;

(2) если A, B – формулы, то A&B, AB,  A, A  B, A  B, x A(x), x A(x) – формулы.

А к с и о м ы и п р а в и л а в ы в о д а:


  1. аксиомы исчисления предикатов 1-12 и правило вывода modus ponens;

  2. нелогические аксиомы*):

13° (Аксиома индукции) (A(0)& a (A(a) ® A(a¢))) ® a A(a), где A(a) - произвольная формула;

14°. a¢ = b¢ ® a = b;

15°. Ø (a¢ = 0);

16°. a = b ® (a = c ® b = c);

17°. a = b ® a¢ = b¢;

18°. a + 0 = a;

19°. a + b¢ = (a + b)¢;

20°. a  0 = 0;

21°. a  b¢ = a  b + a.

ТЕОРЕМА 1.  a = a.

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

1. a=b®(a=c®b=c) (аксиома 16)

2. 0=0®(0=0®0=0) (аксиома 1а)

3. (a=b®(a=c®b=c))®((0=0®(0=0®0=0))®(a=b®(a=c®b=c)) (аксиома 1а)

4. (0=0®(0=0®0=0))®(a=b®(a=c®b=c)) (modus ponens)

5. (0=0®(0=0®0=0))®"c (a=b®(a=c®b=c)) (введение)

6. (0=0®(0=0®0=0))®"b"c (a=b®(a=c®b=c)) (введение)

7. (0=0®(0=0®0=0))®"a"b"c (a=b®(a=c®b=c)) (введение)

8. abc (a=b®(a=c®b=c)) (modus ponens)

9. abc (a=b®(a=c®b=c))® bc (a+0=b®(a+0=c®b=c)) (удаление)

10. bc (a+0=b®(a+0=c®b=c)) (modus ponens)

11. bc (a+0=b®(a+0=c®b=c))® c (a+0=a®(a+0=c®a=c)) (удаление)

12. c (a+0=a®(a+0=c®a=c)) (modus ponens)

13 c (a+0=a®(a+0=c®a=c))®(a+0=a®(a+0=a®a=a)) (удаление)

14. a+0=a®(a+0=a®a=a) (modus ponens)

15. a+0=a (аксиома 18)

16. a=a (2 раза modus ponens).



ТЕОРЕМА 2.  a=b ® b=a.

ТЕОРЕМА 3.  a=b&b=c ® a=c.

ТЕОРЕМА 4.  a=b ® a+c=b+c.

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

Докажем  A(0) ( где A(0)  a=b®a+0=b+0).

1. a=b (допущение)

2. a+0=a (аксиома 18)

3. b+0=b (аксиома 18)

4. ? =a+0®(?=b+0®a+0=b+0) (аксиома 16)

5. a+0=a ® a=a+0 (теорема 2)

6. a=a+0 (modus ponens,2,5)

(? есть a)

7. a=b+0 ® a+0=b+0 (modus ponens 6,4)

8. ??=a ® (??=b+0®a=b+0) (аксиома 16)



  1. a=b ® b=a (теорема 2)

  2. b=a (modus ponens 1,9)

(?? есть b)

  1. b=b+0 ® a = b+0 (modus ponens 10,8)

  2. b+0 = b ® b = b+0 (теорема 2)

  3. b = b+0 (modus ponens 3,12)

14. a = b+0 (modus ponens 13,11)

15. a+0 = b+0 (modus ponens 14,7)

16. a = b®a+0 = b+0 (теорема дедукции 1,15) (т.е. A(0))

17. A(c) (допущение) (докажем A(c¢))

18. a = b (допущение)

19. a+c = b+c (modus ponens 18,17)

20. a+c¢ = (a+c)¢ (аксиома 19)

21. b+c¢ = (b+c)¢

22. a+c = b+c ® (a+c)¢ = (b+c)¢ (аксиома 17)

23. (a+c)¢ = (b+c)¢ (modus ponens 19,22)

24. a+c¢ = (a+c)¢ & (a+c)¢ = (b+c)¢ ® a+c¢ = (b+c)¢ (теорема 3)

25. a+c¢ = (a+c)¢ & (a+c)¢ = (b+c)¢ (введение & 20,23)

26. a+c¢ = (b+c)¢ (modus ponens 24,25)

27. b+c¢ = (b+c)¢ ® (b+c)¢ = b+c¢ (теорема 2)

28. (b+c)¢ = b+c¢ (modus ponens 21,27)

29. a+c¢ = (b+c)¢ & (b+c)¢ = b+c¢ (введение & 26,28)

30. a+c¢ = (b+c)¢ &(b+c)¢ =b+c¢ ® a+c¢=b+c¢ (теорема 3)

31. a+c¢ = b+c¢ (modus ponens 29,30)

32. a=b ® a+c¢ = b+c¢ (теорема дедукции 18,31) ( т.е. A(c¢))

33. A(c) ® A(c¢) (теорема дедукции 17,32)

34. c (A(c)®A(c¢)) (введение,33)

35. A(0)& c (A(c)®A(c¢)) (введение & 16,34)

36. A(0)& c (A(c)®A(c¢))®c A(c) (аксиома 13)

37. c A(c) (modus ponens 35,36)

38. A(c) (удаление,37).

ТЕОРЕМА 5.  a=b ® ac=bc

ТЕОРЕМА ГЕДЕЛЯ (О неполноте формальной арифметики).

Если A13,..., A21  Ф, то A13,..., A21 = Ф. Обратное неверно.

(Без д о к а з а т е л ь с т в а)

Заметим, что нельзя избавиться от неполноты арифметики добавлением новых аксиом.


Упражнение

1. Доказать теоремы 2, 3, 5.

2. Доказать справедливость законов коммутативности, ассоциативности и дистрибутивности для операций “+” и “”.

3. Определяя отношение “x < y” формулой z (z  0 & x + z = y), доказать следующие свойства :

x < y (y < z  x < z); x  x; x < x ; 0  x;

x < y  (y < x); x < y  x  y;

x < y  x +z < y+z ; x  y  x < y ;

z  0  x + z > x; x  y  (y  z  x  z);

x = y  x < y  y < x. x  y & y  x  x = y;

x  0  yx  y; y  0  !u!v (x = yu + v & v < y).

С П И С О К Л И Т Е Р А Т У Р Ы


  1. Горский Д.П. Логика.M.1963.

  2. Лукасевич Я.Аристотелевская силлогистика с точки зрения современ

ной формальной логики.М.1959.

  1. Краткий словарь по логике. Под редакцией Д.П.Горского. М:Просве

щение.1991.

  1. Розен В.В Дедуктивные умозаключения.Учебное пособие для изучающих

логику. Саратов. Изд-во СГУ,1990.

  1. Гамова А.Н. Математическая логика и теория алгоритмов.Учебное посо

бие для студентов механико-математического факультета и факультета

компьютерных наук и информационных технологий.2-е изд., допол.



Саратов: Изд-во СГУ, 2000 г.

  1. Я.А.Слинин. Современная модальная логика. Ленинград. Изд-во ЛГУ

ЛГУ,1976.

*) на языке символов это выражается как AA для суждений, и A=A для понятий и объектов.

**) A или неA

***) контрадикторность

*) речь идет о двоичной (классической) логике

1 Для сокращения количества скобок договоримся о приоритете логических операций: {}, {&,}, {,}

1 определение в упр.3

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

1 Схемами аксиом

*) в примерах 1,3,5 подстановка будет свободной

*) см раздел 2.4

*) Аксиомы Пеано


Каталог: sites -> default -> files -> textdocsfiles -> 2013
2013 -> Имени н. Г. Чернышевского
2013 -> В. Д. Шадриков “ 05 ” апреля 2000 г. Номер государственной регистрации
2013 -> Сборник научных трудов Саратов 2011
2013 -> Физической культуры на формирование картины мира
2013 -> Сборник научных трудов Саратов 2012
2013 -> Рабочая программа дисциплины (модуля) Политическая психология Направление подготовки 030200 «Политология»
2013 -> Сборник научных статей иц «Наука» 2010 (082) ббк 74. 58 я43 П18
2013 -> Самостоятельная работа студентов в условиях перехода на двухуровневую систему впо материалы докладов
2013 -> Профессиональный компонент срс в обучении английскому языку: проверка обратной связи
2013 -> Образовательная программа для получения дополнительной квалификации «Юридический психолог»


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7




База данных защищена авторским правом ©dogmon.org 2022
обратиться к администрации

    Главная страница