Раздзел логіка прэдыкатаў




старонка3/4
Дата канвертавання01.05.2016
Памер1.92 Mb.
1   2   3   4
§4. Тэорыi першага парадку
Аналагiчна таму, як мы ўвялi фармальную тэорыю злiчэння выказванняў, у гэтым параграфе мы азначым фармальную тэорыю злiчэння прэдыкатаў гэтак, што тэарэмамi гэтай тэорыi будуць з’яўляцца логiкава агульназначныя формулы i толькi яны.

Мы будзем вывучаць фармальныя тэорыi, якiя называюцца тэорыямi першага парадку. Словы “першага парадку” паказваюць, што ў гэтых тэорыях, у адрозненне ад тэорыяў больш высокiх парадкаў, не дапускаюцца прэдыкаты, якiя маюць у якасцi аргументаў iншыя прэдыкаты i функцыi, i таксама не дапускаюцца квантары па прэдыкатах i квантары па функцыях.

(1) Сымболямi тэорыi першага парадку служаць:

злiчонае мноства прадметных зменных ;

канцоўнае (магчыма, пустое) або злiчонае мноства прадметных канстантаў ;

непустое, канцоўнае або злiчонае мноства прэдыкатных сымболяў ;

канцоўнае (магчыма, Ш) або злiчонае мноства функцыянальных лiтараў ;

спецыяльныя сымболi .

Розныя тэорыi могуць адрознiвацца адна ад адной па складзе сымболяў.

(2) Тэрмы i элементарныя формулы азначаюцца як у §2.

Азначэнне. (a) Элементарныя формулы ёсць формулы тэорыi ;

(b) калi , формулы тэорыi , – прадметная зменная, тады



, , )

ёсць формулы тэорыi ;

(c) выраз з’яўляецца формулай толькi ў тым выпадку, калi гэта вынiкае з (а),(b).

Азначэнне прапазiцыйных злучнiкаў – такое, як у злiчэннi выказванняў, выраз разглядаем як скарачэнне формулы )).

(3) Аксiёмы тэорыi :

(a) логiкавыя аксiёмы:

Для адвольных формулаў наступныя формулы ёсць аксiёмы тэорыi :

(A1) ;

(A2) ;

(A3) ;

(A4) ( ) ), дзе – формула тэорыi , –тэрм, вольны для у . У прыватнасцi, калi , атрымаем аксiёму ( ) ;

(А5) (( ) ))), калi не змяшчае вольна ;

(b) ўласныя аксiёмы, якiя змяняюцца ад тэорыi да тэорыi.

Тэорыя першага парадку, якая не мае ўласных аксiёмаў, называецца злiчэннем прэдыкатаў першага парадку.

(4) Правiлы вывядзення тэорыi :

(i) Modus ponens (MP): з i вынiкае .

(ii) Правiла абагульнення (Gen): з вынiкае ).

Мадэллю тэорыi першага парадку называецца ўсякая iнтэрпрэтацыя, у якой тоесна праўдзiвыя ўсе аксiёмы тэорыi . Паводле сцверджанняў 1 і 4 §1, калi дастасаваць правiлы modus ponens i абагульнення да праўдзiвых у дадзенай iнтэрпрэтацыi формулаў, тады атрымаюцца формулы, праўдзiвыя ў гэтай iнтэрпрэтацыi. Значыць, у кожнай мадэлi тэорыi тоесна праўдзiвыя ўсе тэарэмы тэорыi .
Прыклады тэорыяў першага парадку
1. Тэорыя групаў.

Няхай мае адзiную прэдыкатную лiтару , адзiную функцыянальную лiтару i адну прадметную канстанту . У адпаведнасцi з агульнапрынятымi абазначэннямi мы будзем пiсаць замест , замест i замест . Уласнымi аксiёмамi тэорыi з’яўляюцца:

(a) (асацыятыўнасць);

(b) (iснаванне адзінкі);

(c) (iснаванне адваротнага элементу);

(d) (рэфлексiўнасць роўнасцi);

(e) (сiметрычнасць роўнасцi);

(f) (транзiтыўнасць роўнасцi);

(g) (падстановачнасць роўнасцi).

Усякая мадэль гэтай тэорыi называецца групай.



2. Тэорыя частковага ўпарадкавання.

Няхай мае адзiную прэдыкатную лiтару i не мае функцыянальных лiтараў i прадметных канстантаў. Замест i будзем адпаведна пiсаць i . Уласнымi аксiёмамi тэорыi з’яўляюцца:

(a) (iррэфлексiўнасць);

(b) (транзiтыўнасць).

Усякая мадэль гэтай тэорыi называецца ўпарадкаванай структурай.

§5. Уласцiвасцi тэорыяў першага парадку
Усякая тэорыя першага парадку улучае ў сябе злiчэнне выказванняў у тым сэнсе, што ўсе аксiёмы злiчэння выказванняў ёсць аксiёмы тэорыi i правiла вывядзення (modus ponens) ёсць правiла вывядзення тэорыi . Адсюль няцяжка атрымаць

Сцверджанне 1. Калi формула тэорыi атрыманая з таўталогii шляхам падстановы ў яе замест зменных формулаў тэорыi , тады ёсць тэарэма тэорыi .

Доказ. Няхай атрымана з таўталогii з дапамогаю падстановаў. Паводле тэарэмы пра поўнасць для злiчэння выказванняў выводная ў злiчэннi выказванняў. Зрабiўшы ў вывядзеннi падстановы наступным чынам: (а) калi некаторая прапазiцыйная лiтара ўваходзiць у , тады замест усiх яе ўваходжанняў у кожную формулу з вывядзення падстаўляем тую формулу тэорыi K, якая падстаўлялася ў пры пабудове ; (б) калi прапазiцыйнай лiтары, што ўваходзiць у вывядзенне, няма ў , тады замест усiх яе ўваходжанняў у вывядзенне падстаўляем адвольную (тую сама для дадзенай лiтары) формулу тэорыi . Атрыманая паслядоўнасць формулаў будзе вывядзеннем формулы ў . ■

У тэорыi будуць выводнымi i iншыя формулы.



Прыклад 1. для адвольнай формулы тэорыi K.

Для доказу разгледзiм наступныя формулы:

1. (аксiёма 4);

2. (формула атрымана падстановай , у таўталогiю , значыць, паводле сцверджання 1, выводная ў );

3. (MP, 1,2),

г.зн. ├ .



Сцверджанне 2. Усякае злiчэнне прэдыкатаў першага парадку несупярэчлiвае.

Доказ. Для адвольнай формулы абазначым праз h ) выраз, якi атрымлiваецца з ў вынiку прапускання ўсiх квантараў i тэрмаў (з адпаведнымi дужкамi i коскамi). Напрыклад,

.

h ) – формула злiчэння выказванняў, у якой ролю лiтараў выконваюць . Вiдавочна, h h( ), h h ) h . Для ўсякай аксiёмы злiчэння прэдыкатаў h ) – таўталогiя. Для схемаў аксiёмаў (1) – (3) гэта вiдавочна, для схемы (4) –

h ) h h ,

для схемы (5) –



)) h h h h .

Калi h ) i h h ) h – таўталогii, тады h – таўталогiя. Калi h – таўталогiя, тады h ) h – таўталогiя.

Значыць, калi – тэарэма ў , тады h ) – таўталогiя. Калi б iснавала формула ў такая, што ├K i ├K , тады h i h h( ) былi б таўталогiямi, што немагчыма. Такiм чынам, несупярэчлiвая. ■

Тэарэма дэдукцыі ў той фармулёўцы, у якой яна была даказаная для злiчэння выказванняў, не можа быць перанесеная у адвольную тэорыю першага парадку .



Прыклад 2. K паводле правiла Gen, але не заўсёды ├K . Сапраўды, няхай . Возьмем мноства, у якiм не менш за два элементы, i iнтэрпрэтацыю на гэтым мностве, у якой адпавядае прэдыкат , дзе – фiксаваны элемент мноства. Тады – не тоесна праўдзiвы прэдыкат i, значыць, формула не логiкава агульназначная. Нiжэй мы пакажам (сцверджанне 4), што кожная тэарэма ўсякага злiчэння прэдыкатаў з’яўляецца логiкава-агульназначнай формулай, i, значыць, формула – не тэарэма тэорыi .

Аднак у больш слабой фармулёўцы тэарэма дэдукцыi праўдзiцца для тэорыi .



Азначэнне. Няхай – мноства формулаў, , – вывядзенне з . Будзем казаць, што залежыць ад ў гэтым вывядзеннi, калi:

(i) i абгрунтаваннем служыць прыналежнасць да ;

(ii) абгрунтаваная як непасрэдны вынiк паводле MP або Gen некаторых папярэднiх формулаў, з якiх прынамсi адна залежыць ад .

Лема. Калi не залежыць ад ў вывядзеннi , тады .

Доказ. Няхай – вывядзенне з i , у якiм не залежыць ад . Будзем даказваць нашае сцверджанне iндукцыяй па . Пры – аксiёма або элемент , таму .

Дапусцiм, што лема сапраўдная для ўсiх вывядзенняў даўжынi меншай за . Калi – аксiёма або , тады . Калi – непасрэдны вынiк якiх-небудзь (адной або дзвюх) папярэднiх формулаў, тады нiводная з гэтых формулаў не залежыць ад , бо не залежыць ад . Паводле iндукцыйнага меркавання з выводныя гэтыя формулы i, значыць, . ■



Сцверджанне 3 (Тэарэма дэдукцыi). Няхай i iснуе такое вывядзенне з , у якiм нi пры адным дастасаваннi правiла Gen да формулаў, залежных у гэтым вывядзеннi ад , не злучаецца квантарам нiякая вольная зменная формулы . Тады .

Доказ. Няхай – вывядзенне формулы з , якое адпавядае ўмовам сцверджання 3. Дакажам па iндукцыi, што для ўсiх .

Няхай . Калi – аксiёма або элемент , тады з формулаў (A1) i паводле MP атрымаем , значыць, .

Калi , тады ├ паводле сцверджання 1, значыць, i ў гэтым разе .

Дапусцiм цяпер, што для ўсiх . Калi – аксiёма або , тады даказваецца гэтаксама, як для .

Калi iснуюць такiя, што , тады, паводле iндукцыйнага меркавання, i . Паводле схемы аксiёмаў (A2), формула – аксiёма. Адсюль, паводле правіла МР, i .

I, нарэшце, калi iснуе , такi, што , тады, паводле меркавання iндукцыi, , i або не залежыць ад , або не з’яўляецца вольнай зменнай формулы . Калi не залежыць ад , тады паводле лемы , адсюль, паводле правiла Gen , г. зн. . Формула – аксiёма тэорыi , адсюль паводле MP атрымаем . Калi не з’яўляецца вольнай зменнай формулы , тады з паводле правiла Gen атрымаем . Формула – аксiёма тэорыi (А5), адсюль паводле MP атрымаем , г. зн. . Такiм чынам, заўсёды . Сцверджанне 3 атрымаем пры . ■



Вынiк 1. Калi i iснуе вывядзенне, пабудаванае без ужывання правiла абагульнення да вольных зменных формулы , тады .

Вынiк 2. Калi формула замкнёная i , тады .

Сцверджанне 4. Усякая тэарэма злiчэння прэдыкатаў з’яўляецца логiкава агульназначнай формулай.

Доказ. Як мы адзначалi ў §3, падстанова ў таўталогiю адвольных формулаў логiкi прэдыкатаў дае логiкава агульназначную формулу, таму аксiёмы, якiя задаюцца схемамi (А1) – (А3), логiкава агульназначныя. Паводле сцверджанняў 5 i 6 §3, аксiёмы, зададзеныя схемамi (А4), (А5), таксама логiкава агульназначныя. Адсюль i з сцверджанняў 4 i 1 §3 вынiкае логiкавая агульназначнасць адвольнай выводнай формулы. ■

Сцверджанне 5. (Тэарэма Гёдэля пра поўнасць). Кожная логiкава агульназначная формула тэорыi першага парадку з’яўляецца тэарэмай тэорыi .

Доказ гэтага сцверджання нетрывiяльны, i мы яго не будзем падаваць; яго можна знайсцi ў кнiгах [1], с.78, [2], с.268, [3], с.339.

З сцверджанняў 4 i 5 вынiкае

Сцверджанне 6. Ва ўсякiм злiчэннi прэдыкатаў першага парадку тэарэмамi з’яўляюцца логiкава агульназначныя формулы i толькi яны.

Такiм чынам, як i ў злiчэннi выказванняў, ├ калi i толькi калi ╞ .



§6. Фармальная арытметыка
Першая аксiяматыка элементарнай тэорыi лiкаў (арытметыкi натуральных лiкаў) была прапанаваная Дэдэкiндам у 1901 г. Гэтая аксiяматыка, вядомая як сiстэма аксiёмаў Пэана, улучае наступныя аксiёмы:

(Р1) 0 ёсць натуральны лiк;

(Р2) Для кожнага натуральнага лiку iснуе натуральны лiк, якi абазначаецца i называецца (адразу) наступным за ;

(Р3) для кожнага натуральнага лiку ;

(Р4) Калi , тады ;

(Р5) Калi ёсць некаторая ўласцiвасць натуральных лiкаў, i калi:

(1) натуральны лiк 0 мае ўласцiвасць i

(2) для кожнага натуральнага лiку з таго, што мае ўласцiвасць вынiкае, што i мае ўласцiвасць , тады ўласцiвасць маюць усе натуральныя лiкi (прынцып iндукцыi).

Гэтых аксiёмаў, разам з некаторымi элементамi тэорыi мностваў, дастаткова для пабудовы не толькi арытметыкi, але i тэорыi рацыянальных, рэчаiсных, камплексных лiкаў. Аднак у гэтых аксiёмах ёсць iнтуiцыйныя, не вызначаныя строга паняццi, як, напрыклад, “уласцiвасць”. Мы пабудуем тэорыю першага парадку , якая грунтуецца на сiстэме аксiёмаў Пэана.

мае адзiную прэдыкатную лiтару , адзiную прадметную канстанту i тры функцыянальныя лiтары . Далей мы будзем пiсаць замест , 0 замест , замест адпаведна , дзе i - тэрмы. Уласныя аксiёмы тэорыi :

(S1) ;

(S2) ;

(S3) ;

(S4) ;

(S5) ;

(S6) ;

(S7) ;

(S8) ;

(S9) ( , дзе – адвольная формула тэорыi .

Заўважым, што аксiёмы (S1) – (S8) – канкрэтныя формулы, а (S9) – схема аксiёмаў, якая спараджае бясконца многа аксiёмаў. Схема аксiёмаў (S9) называецца прынцыпам матэматычнай iндукцыi.

(S3), (S4) адпавядаюць (P3), (P4). (P1), (P2) сцвярджаюць iснаванне нуля i аперацыi “адразу наступны”, якiм у тэорыi адпавядаюць прадметная канстанта i функцыянальная лiтара . (S1), (S2) даюць неабходныя ўласцiвасцi роўнасцi, якiя Дэдэкiнд i Пэана лiчылi iнтуiцыйна вiдавочнымi. (S5) – (S8) – рэкурсiўныя роўнасцi, якiя з’яўляюцца азначэннямi складання i множання.

З дапамогаю MP з (S9) можна атрымаць правiла iндукцыi: з i ( выводная .
У 1931г. Гёдэль даказаў тэарэму пра няпоўнасць, якую мы фармулюем беэ доказу; доказ можна знайсцi ў кнiгах [1,3,4].

Сцверджанне 1 (Тэарэма Гёдэля для тэорыi ). Калi тэорыя несупярэчлiвая, тады iснуе замкнёная формула тэорыi такая, што абедзве формулы i невыводныя ў гэтай тэорыi (такiя формулы называюцца неразвязальнымi сцверджаннямi тэорыi ).

Тэарэма Гёдэля праўдзiцца не толькi для тэорыi , а i для даволi шырокага класу фармальных тэорыяў, якiя задавальняюць пэўныя ўмовы (гл. [1,3]).



§7. Дастасаванні да натуральнае мовы
Вывучэнне матэматычнае логікі дазваляе нам быць больш дакладнымі ў сваёй логіцы (логіцы даследчыка – логіцы, якою мы карыстаемся пры вывучэнні матэматыкі і ў штодзённым жыцці). У гэтым параграфе мы разгледзім пытанні, што ўзнікаюць пры выкарыстанні злічэння выказванняў і злічэння прэдыкатаў у разважаннях, якія перадаюцца натуральнаю моваю.

Мы ўжо не аднойчы карысталіся логікавымі злучнікамі і квантарамі для перакладу сказаў з натуральнай мовы на мову алгебры выказванняў (логікі прэдыкатаў). Мы карыстаемся алгебрай выказванняў з таго моманту, як навучыліся размаўляць, хоць самі і не разумелі гэтага. Фармуляванне логікавых законаў, паняццяў у сымбалічнай форме дазваляе больш паспяхова імі карыстацца пры нашых разважаннях. Напрыклад, мы ўжо адзначалі, што раўназначнасць



абгрунтоўвае метад доказу ад адваротнага, законы дэ Моргана і формулы логікі прэдыкатаў



і

дапамагаюць правільна сфармуляваць адмаўленне. Фармальнае вывучэнне логікі не толькі дапамагае правяраць разважанні, але і дазваляе развіць і пашырыць нашыя прыродныя здольнасці лагічна думаць.

Некаторыя з чытачоў пры адказе на пытанне, ці правільнае пэўнае разважанне (практыкаванні 1.2.11 і 3.3.13), мабыць, убачылі, што памыліліся, калі карысталіся сваёй логікай даследчыка (логікай, з дапамогай якой яны вывучаюць матэматыку), а не матэматычнай логікай (логікай, якую мы вывучаем). Хтосьці, магчыма, ставіцца скептычна да сцверджання, што ў працэсе вывучэння логікі развіваюцца здольнасці знаходзіць правільныя доказы, але, бясспрэчна, што пры вывучэнні логікі павялічваюцца магчымасці правяраць правільнасць разважанняў. Мы ўжо ведаем два метады аналізу разважанняў – алгебру выказванняў і логіку прэдыкатаў (тэорыю мадэляў) і злічэнні выказванняў і прэдыкатаў (тэорыю доказаў).

Пры перакладзе выразаў звычайнай мовы на мову алгебры выказванняў (логікі прэдыкатаў) мы можам больш дакладна прааналізаваць пэўнае разважанне, але часам можам пры гэтым пазбавіцца некаторых адценняў сэнсу.



Прыклад 1. (а) Прафесар паставіў “чатыры”, і Алена заплакала.

(б) Алена заплакала, і прафесар паставіў “чатыры”.



Прыклад 2. (а) Я абяцаў табе зрабіць гэта, але я баюся.

(б) Я баюся, але я абяцаў табе зрабіць гэта.



Прыклад 3. (а) Пачаў накрапваць дождж, і шаман заспяваў хвалу багам.

(а) Шаман заспяваў хвалу багам, і пачаў накрапваць дождж.

Ва ўсіх трох прыкладах сказ (а) мы запісваем формулай алгебры выказванняў , а (б) – , якія раўназначныя як формулы алгебры выказванняў. Але ў жывой мове гэтыя сказы маюць розныя, зусім не раўназначныя адценні. У прыкладзе пра экзамен другі сказ успрымаецца як вынік першага, так што (а) мы разумеем гэтак: Алена засмуцілася тым, што атрымала “чатыры”, а (б) – што Алена “выплакала” “чатыры”. У гэтым прыкладзе, мабыць, больш правільным будзе злучнік “і” перадаць не кан’юнкцыяй, а імплікацыяй і запісаць сказы формуламі і адпаведна. Але гэты пераклад будзе таксама недакладны, бо ў выпадку, калі прафесар не паставіў “чатыры”, першая формула набывае логікавае значэнне 1, а выказванне (а) непраўдзівае. Для дакладнага аналізу сказаў трэба высветліць, якая з падзеяў адбылася раней і, такім чынам, што было прычынай, а што вынікам; гэта можна зрабіць з дапамогаю логікі прэдыкатаў. Няхай (Прафесар паставіў “чатыры” ў момант ), (Алена заплакала ў момант ). Тады сказ (а) запішацца формулай логікі прэдыкатаў , а сказ (б) – формулай .

Аналагічныя заўвагі можна зрабіць пра прыклад 3, дзе (а) мы разумеем наступным чынам: шаман заспяваў хвалу багам у знак удзячнасці за дождж, які паслалі богі, а (б) – што шаман наваражыў дождж.

У прыкладзе 2 (а) выглядае як спроба апраўдацца тым, хто не выканаў абяцанне, а (б) – як намер перамагчы страх і зрабіць тое, што абяцаў, і сябры гэтага чалавека па-рознаму будуць ставіцца да яго ў выпадках (а) і (б).

Злучнікі “і”, “але”, “нягледзячы на”, “не зважаючы на”, “хоць” перакладаюцца на мову алгебры выказванняў як , але пры гэтым губляюцца некаторыя адценні сэнсу.


1   2   3   4


База данных защищена авторским правом ©shkola.of.by 2016
звярнуцца да адміністрацыі

    Галоўная старонка