logikos teorija
SUTRUMPINTOS TEISINGUMO LENTELĖS
Mes naudojame teisingumo lenteles, kai norime nustatyti ar formulė tapačiai teisinga, ar iš duotų formulių išplaukia kita formulė. Tačiau, kad įrodyti, ar formulė yra tapačiai teisinga, ar formulė logiškai išplaukia, dažnai yra paprasčiau taikyti teoremas. Jeigu mums reikia įrodyti, kad formulė nėra tapačiai teisinga ar logiškai išplaukia, mums nereikia sudarinėti pilnos teisingumo lentelės. Tereikia surasti tinkamą eilutę, kuri tai įrodytų. Jeigu vis dėlto tenka atlikti daug skaičiavimų pagal teisingumo lenteles, tai galima panaudoti metodą, pagreitinantį skaičiavimą. Jo esmė ttokia, kad t ir k reikšmės priskiriamos vienintelei raidei. Raidė pasirenkama ta, kuri dažniausiai naudojama formulėje. Tuomet formulė supaprastėja. Po to t ir k reikšmės priskiriamos kokiai nors kitai raidei. Panagrinėkime kokio nors dvejetainio ryšio pradinę teisingumo lentelę. Jeigu mes formulei A priskiriame reikšmes t arba k, tai esant fiksuotoms A reikšmėms A B lentelė tampa vienetinio ryšio, priklausančio nuo B, lentele. Vienetiniam ryšiui galimos tik 4 lentelės:
T t
T K (kaip ir B)
K T (B)
K K
Taigi, parenkant vieną A reikšmių, formulė gali įgyti vieną iiš reikšmių t, B, B, k. Žinomų loginių operacijų atveju gauname tokias lenteles:
A A_B
B_A AB BA
T B B t
K B t B
Lentelės ( ) tęsinys ( )
AB
BA AB
BA A
B t k
k B t
Pavyzdžiui:
P (Q R (R P))
kai P yra k, tai viskas yra t:
k (Q R (R k))
kai P yra t:
t (Q R (R t))
Q R (R k)
Q R R
toliau kai R yra t:
Q t t
t k
k
kai R yra k:
Q k k
Q t
t
Pateikta formulių sistema vadinama analize pagal teisingumą. Šį metodą pritaikė 1950 m. W. van O. Quine.
PAGRINDINĖS IŠPLAUKIMO TAISYKLĖS
G. Geutzeu (kažkoks austras)
Šios taisyklės yra dedukcinių samprotavimų pagrindas.
1 Jei iš , A╞ B, tai ,╞ A B (implikacijos įvedimas)
Ši taisyklė įveda implikaciją, jeigu įrodyta, kad iš A╞ B. Galbūt dar darant kitas prielaidas (aibė ) ši taisyklė plačiai naudojama įrodymuose. Tarkim, kad reikia įrodyti implikacinės struktūros sakinį A B. ??? prie jo įrodytų sakinių prijungiamas ssakinys A ir tada iš ir A išvedama B. Po to sakoma, kad teorema įrodyta. Toks formulavimas ir nusako, kaip taikoma implikacijos įvedimo taisyklė, t.y. , A╞ B prie išplaukimo ,╞ A B.
2 Jeigu , A╞ C ir , B╞ C, tai , AB╞ C (disjunkcijos pašalinimas)
Pagal šią taisyklę išvadai C iš disjunkcijos A arba B gauti pakanka gauti išvadą C iš A ir iš B, t.y., norint išvesti C iš AB, ši disjunkcija pašalinama ir įrodomi du sskirtingi išplaukimai , A╞ C ir , B╞ C.
1) P (Q R) = t
2) P Q = P _ Q
3 Jeigu iš , A╞ B ir , A╞ B, tai iš ╞ A (neigimo įvedimas)
Ši taisylė yra netiesioginio įrodymo pagrindas. Netiesioginis įrodymas – tai įrodymas prieštaros metodu. Teiginiui A įrodyti daroma prielaida, kad A yra klaidingas, o ne A yra teisingas. Tada iš A ir jo įrodytų teiginių aibės išvedame prieštarą BB. Po to sakome, kad gauta prieštara įrodo teoremą. Toks formulavimas reiškia, kad neigimo įvedimo taisyklė taikoma netiesiogiai. Iš tikrųjų, pagal ją gauname , A╞ B ir , A╞ B, tai ╞ t.
4 Jeigu iš ╞ A ir ╞ A B, tai ╞ B (implikacijos pašalinimas)
Ši taisylė bus pagrindinė tolimesnėje mūsų teorijoje. Su ja jau buvom susidūrę netiesiogiai, kai samprotavom, kad tapačiai teisingas teiginys A B yra stipresnis nei teiginys jei A tapačiai teisinga, tai B tapačiai teisinga. Tuomet ši taisyklė ir buvo įrodyta.
5 Jeigu iš ╞ A, tai ╞ AB (pirmasis disjunkcijos įvedimas)
6 Jeigu iš ╞ B, tai ╞ AB (antrasis disjunkcijos įvedimas)
Šios taisyklės kaip ir tapačiai teisingos formulės išreiškia logikos dėsnius. Kartu šios taisyklės akivaizdžiau nei tapačiai teisingos formulės išreiškia samprotavimų metodus.
TEIGINIŲ LOGIKOS TTAIKYMAS NATŪRALIAI KALBAI
NATŪRALIOS KALBOS SAKINIŲ UŽRAŠYMAS MATEMATINĖS LOGIKOS KALBA
Natūralios kalbos teiginiai esti įvairių konstrukcijų. Daugelyje jų galima išskirti tokias komponentes, kurios pačios yra sakiniai. Šie paprastesni sakiniai grupuojami į sudėtinius jungtukais ir skyrybos ženklais. Kiekvienas jungtukas turi savo atspalvį. Logikoje šie atspalviai išnyksta. Ir visa kalbinių jungimo priemonių gausybė išreiškiama nedideliu loginių operacijų skaičiumi. Pvz.:
1 Nustatykite sakinio “Jis baigė, o aš stovėjau ir vis klausiau” loginę struktūrą.
Pažymėsim elementarius teiginius: P – jis baigė; Q – aš stovėjau; R – vis klausiau. Tada PQR. Pirmu atveju konjunkcija išreikšta “,” ir jungtuku “o”, antru atveju – jungtuku “ir”. Logine prasme abu sąryšiai konjunkciniai. Semantine prasme sąryšių atspalviai yra skirtingi. Jungtukas “o” turi reiškinių sugretinimo prasmę, o jungtukas “ir” turi neutralią jungiamąją prasmę.
2 Nustatyti sakinio “Kadangi skaičių x galima užrašyti x = 2n + u (kur 0 u < 2, n Z), tai funkcijų sin x ir cos x reikšmių apskaičiavimas pakeičiamas intervale 0 u < 2 esančio argumento sin ir cos reikšmių apskaičiavimu.” loginę struktūrą.
Pažymim P – skaičių x galime užrašyti formule x = 2n + u; R – 0 = u; Q – 0 < u; S – u < 2; T – n Z; V – ssin x reikšmės apskaičiavimas pakeičiamas; W – cos x reikšmės apskaičiavimas pakeičiamas.
P(QR) STVW(QR) S
3 Kokia yra sakinio “Funkcija y = cos x apibrėžta intervale (0, ) turi atvirkštinę funkciją.” loginė struktūra? Šio sakinio loginė struktūra iš karto nepastebima. Sakinys tvirtina, kad “funkcija turi atvirkštinę funkciją” – R, bet tik esant sąlygoms “funkcija y = cos x” – P ir “funkcija apibrėžta intervale (0, )” – Q, t.y. šis sakinys yra lygiavertis tokiam sakiniui: “Jeigu funkcija y = cos x nagrinėjama intervale (0, ), tai ji turi atvirkštinę funkciją”. O šio sakinio loginė struktūra labai aiški.
LOGIKA
SAMPROTAVIMŲ ANALIZĖ. TEIGINIŲ LOGIKOS METODAI
Ši analizė susideda iš 2 dalių:
a) samprotavimo struktūros nustatymas
b) patikrinimas, ar išvada išplaukia iš duotų prielaidų.
Pvz.:
4. Išanalizuokim samprotavimą:
“Jeigu 10-taine sistema parašytas skaičius (sveikas) baigiasi 5” -P, “tai jis dalijasi iš 5” -Q. 10-taine sistema parašytas skaičius dalijasi iš 5. Mums reikia patikrinti, ar ši išvada išplaukia iš duotų prielaidų. Užsirašom samprotavimo struktūrą: PQ, P?Q. Norint nustatyti, ar teisinga išvada, galima naudoti įv. metodus. Pats paprasčiausias yra teis. lent. metodas (nenaudosim, nes per daug paprasta). Ši samprotavimo struktūra atitinka MP taisyklę: gaunam PQ, P╞ Q.
5. “Aš užmokėčiau už televizoriaus remontą” -Q, “jeigu jis dirbtų” -P, jis nedirba, todėl aš nemokėsiu (prielaida).
QP, P Q
1. QP čia kontrpozicija 4. Q, todėl QP, P╞ Q
2. P (arba 52 formulė)
3. P Q;
6. “Jeigu jis nebūtų jai pasakęs” – Q, “ji nebūtų sužinojusi” – P, “jei ji nebūtų paklaususi” – R, jis jai nebūtų pasakęs. Ji sužinojo, vadinasi, ji paklausė.
Q P, R Q, P R
Surašom prielaidas: tuomet taikom kontrpoziciją:
1. Q P
2. R Q
3. P
4. PQ
5. Q (MP, 3, 4)
6. QR (52)
7. R (MP, 5, 66)
todėl išvada teisinga
Q P, R Q, P╞R
7. “Profsąjungos palaikys prezidentą” -P, “tik tuo atveju, jei jis pasirašys įstatymą” -Q; “žemdirbiai jį palaikys “ -R, “tik tuo atveju, jei jis uždės veto” -S. Aišku, kad prezidentas arba nepasirašys įstatymo, arba neuždės jam veto. Vadinasi, prezidentas praras arba darbininkų, susivienijusių į profsąjungas, balsus, arba praras žemdirbių balsus.
PQ, RS, Q S, P R
Šio samprotavimo teisingumui nustatyti naudosime disjunkcijos pašalinimo taisyklę, t. y. skaidysim įrodymą į 2 dalis.
1) PQ PS, Q P R
2) PQ RS, S P R
1) 1. PQ
2. R
3.
4. Q P 52,
5. P MP, 3,
6. P P D?
įrodėm
2) 1. PQ
2. RS
3. S
4. S R 52
5. R MP
6. P R
išplaukimas įrodytas
Toliau pateiksime sąrašą loginių operacijų ir joms atitinkamų kalbos.
A_B A jei ir tik jei B
1. jei A, tai ir B ir atvirkščiai, jei B, tai ir A ir atv.
2. A jei B ir B jei A
3. dėl A būtina ir pakanka B
4. A_B
5. A tada ir tik tada, kai B
A_B
1. jei A, tai B
2. A atveju bus B
3. dėl B pakanka A
4. dėl A būtina B
5. A iššaukia B
6. B jei A
AB
1. AB
2. ne tik A, bet ir B
3. B nors ir A
4. A tuo pat metu, kaip ir B
5. B nepaisant A
6. kaip A, taip ir B
7. A kartu su B
AB
1.AB arba abu
2.AB
3.A jei ne B
Sakinių pervedimas į logikos kalbą
Nors teiginių skaičiavime
tačiau frazes “Neringai gimė vaikas ir ištekėjo” ir “Neringa ištekėjo ir jai gimė vaikas” Neringos pažįstami suprastų labai skirtingai. Tai susijų su įįvykių tvarka laike. Tačiau dėl loginės analizės dažnai galima nekreipti dėmesio į laiką. Kita problema susijusi su terminų dviprasmiškumu, kuriuos reikia pakeisti loginėmis operacijomis. Pvz., jei meniu parašyta: “Arbata arba kava nemokamai”. Mes nenustebsime, jei mes paprašysime dviejų ir mums teks už tai susimokėti. Tačiau jei parašyta, kad “knygų aukas priima fakulteto raštinė arba biblioteka”, mes negalvojame, kad jei paaukojam raštinėj, tai vėliau bibliotekoj nepriims, nes mes aukojom raštinėj. Ši problema susijusi su jungtuko “arba” dviprasmiškumu.
ĮRODYMŲ TEORIJA
1. Formalusis įrodymas ir fformalusis išvedimas
Matematikai įrodinėja teoremas, t. y. išveda jas iš duotų prielaidų tokiu būdu: teiginiai rašomi į tam tikrą sąrašą, vad. įrodymu arba išvedimu.
Mes kalbėsim apie įrodymą ir prielaidas vadinsime aksiomomis, jei jos išlaiko savo statusą visoje nagrinėjamoje teorijoje, t. y. jos yra tpč. teisingos. Mes kalbėsim apie išvedimą, jei nebūsim tikri, kad visos prielaidos išlaiko savo statusą. Kiekvienas perėjimas nuo vieno teiginio prie kito nagr. sąraše yra pagrįstas logiškai. Pvz.: Teiginys seka iš kitų teiginių, jei jis tenkina išplaukimo apibrėžimą. Išplaukimas buvo apibrėžtas remiantis teisingumo lentelėmis. Apibrėždami išplaukimą, tapačiai teisingas formules, mes naudojome meta kalbą, t.y. kitą kalbą, nei kurioje rašomi teiginiai. Būtent meta kalboje mes gauname įvairius rezultatus apie tapatųjį teisingumą ir išplaukimą, kurie yra patogesni nei teisingumo lentelių vartojimas. Toks logikos nagrinėjimas vadinamas modelių teorija. Pakeisdami atomus t ir k reikšmėmis, mes gauname modelius arba konkrečias realizacijas.
Kitas būdas: Šis būdas vadinamas įrodymų teorija,nagrinėja klausimą, ar negalima parašyti loginius įrodymus ir išvadas taip, kaip yra daroma geometrijoje. Tačiau kadangi pati logika yra nagrinėjimo objektas, tai išvedimai negali remtis loginiais kriterijais, jie gali remtis tik aksiomomis ir taisyklėmis. Įrodymų teorijoje kai kurie teiginai vadinami aksiomomis,o naujų teiginių sudaymui naudojamos išvedimo tasyklės. Vėliau mes pamatysime, kad modelių ir įrodymų teorija duoda eekvivalenčius rezultatus.
2.1Ap. Teorijos L aksiomomis vadinamos visos formulės, turinčios 1.3 T-os 1A-10B formulių pavidalą. Šios formulių formos vad. aksiomų schemomis.
Kiekviena aksiomų schema sukuria begalinę aksiomų aibę, pvz.:
aksiomų schema 1a A(BA) atitinka tokios formulės : P(PP), Q(PQ),P(QRP), (P(RP))(R(P(RP)))
Pateiktame aksiomų schemų sąraše yra kiekvieno iš 5 loginių operacijų : neig. Konj. Disj. Injekc. Ekviv. aksiomų schemos.
1a ir 1b aksiomų schemos – tai implikacijos AS. 3 AS įveda konjunkcijos operatorių, o 4 ir 5 jį pašalina. 5a ir 5b įveda disjunkcijos operatorių, o 6 jį pašalina. 7 schema įveda neigimo operatorių, o 8 jį pašalina. 9 schema įveda ekvivalencijos operatorių, o 10a ir 10b jį pašalina.
2.2 Teorijos L vienintelė išvedimo taisyklė vadinama implikacijos pašalinimu arba MP taisykle. Ši taisyklė leidžia pereiti nuo formulių pavidalo A ir AB prie formulės B. Naudojant MP taisyklę A ir AB vadinamos prielaidomis, o B – šios taisyklės išvada.
2.3 Formaliuoju įrodymu teorijoj L vad. baigtinė formulių B1, B2, . BN seka kai kiekviena šios sekos formulė yra arba aks. schema, arba gaunama pagal MP taisyklę iš kurių nors dviejų ankstesnių šios sekos formulių.
Form. Įrodymas yra paskutiniosios formulės BK įrodymas. F-lė B vadinama formaliai įrodoma, arba formaliąja teorema, jei ji turi formalųjį įrodymą. Teiginį “f-lė B formaliai įrodoma teorijoje LL” žymėsime ├L B ir ir sutarsim iki naujų formalių teorijų pasirodymo indeksą L praliesti, tai ├ B.
Pvz.: Pabandykime įrodyti, kad ├AA (AA) yra įrodoma). F-lės AA įrodomumui nustatyti pagal 2.3 apibr. reikia užrašyti baigtinę formulių seką, kurios paskutinė formulė būtų AA ir taip, kad kiekviena šios sekos formulė būtų aks. schema arba gauta pagal MP taisyklę. Aišku, kad pirmosios šios sekos f-lės turėtų būti aksiomos. Be to, viena iš šių aksiomų turi bagtis formule AA. Galima būtų panaudoti aks-ų schemą 1b, kuri baigtųsi f-le AA , jei f-lę C pakeistume į f-lę A : (AB)((A(BA))(AA)) (1)
dabar, norint iš šios f-lės pagal MP taisyklę gauti f-lę AA, reikia pašalinti (?) implikaciją : 1=(2(AA)), kur 1 žymi (AB), o 2 žymi (A(BA)). Iš pradžių pašalinti 1, o po to 2. Norint pašalinti 1 reikia ją tirėti formulių sekoje. O vietoj 1 gali būti įrašyta tik aks. schema. Palyginę 1 su 1a aks. schema, galime pastebėti, kad B reikia pakeist BA. Tuomet (1) atrodys taip : (A(BA))((A)A))(AA))
yra aks. schema 1a.
Dabar šį įrodymą galime užrašyti tokia seka :
1. A(BA) 1. AS 1a
2. (A(BA))
((A(BA))A))(AA)) 2. AS 1b; C keičiam A, B keičiam BA
3. (A((B
A))(AA) 3. MP ( 1,2 )
4. A
((BA)A) 4. AS 1a, B keičiam BA.
5. AA 5. MP
( 4,3 )
Reikia pasakyti, kad čia faktiškai įrodyta ne konkreti formulė, o visa AA pavidalo klasė, nes šiame įrodyme A ir B yra bet kokios formulės. Taip pat reikia pasakyti, kad kiekviena iš 5 šio įrodymo formulių yra teoremos, taip pat ir aksiomos. Bet kurios aksiomos įrodymą sudaro pati aksioma.
2.4 Formulės B formaliuoju išvedimu iš prielaidų A1, A2, . An vadinama baigtinė formulių B1, B2, .Bk seka, pasibaigianti formule B, kur B = Bk . Kiekviena iš šios sekos formulių yyra arba viena iš prielaidų A1, A2, . An, arba aksioma, kuri gaunam pagal MP taisyklę. Iš dviejų ankstesniųjų. Akivaizdu, kad įrodymas yra atskiras formaliojo išvedimo atvejis iš tuščios pirelaidų aibės.
Pvz.: Nustatykime, kad iš A(BC), AB ├ C.
Padarę prielaidą AB ir aksiomų schemos 4a, pagal MP galim gauti f-lę B. O iš f-lių A ir B ir prielaidos A(BC), pagal MP gausime C.
1. AB 1. Prielaida
2. ABA 2. AS 4a
3. A 3. MP ( 1,2 )
4. ABB 4. AS 4b
5. B 5. MP ( 1,4 ))
6. A(BC) 6. Prielaida
7. BC 7. MP ( 3,6 )
8. C 8. MP ( 5,7 )
1. Išvedamumo santykio savybės
1.1 T a) A1, A2, . An ├ Ai ( i = 1,n )
b) A1, A2, . An ├ B1, A1, A2, . An ├ BB2, . ., A1, A2, . An ├ Bk ir B1, B2, . Bn ├ C, tai A1, A2, . An ├ C.
a) Iš duotos prielaidų aibės išvedama kiekviena šios aibės prielaida.
b) Jei iš duotos prielaidų aibės išvedama kiekviena formulė iš kokios nors prielaidų aibės, o iš šios prielaidų aibės išvedama formulė C, tai C išvedama ir iš pradinės prielaidų aibės.
a) f-lei Ai išvesti iš A1, A2, . An pakanka paeiliui užrašyti f-les A1, A2, . An bet kokia tvarka, tik paskutinę užrašant f-lę Ai.
b)Išvedant f-lę C iš f-lių B1, B2, . Bn , šias formules pakeitus duotaisiais jų išvedimais iš formulių A1, A2, . An gaunamas f-lės C išvedimas iš iš formulių A1, A2, . An.
Taigi, pagal 2.1T, formulių, išvedamų iš AA1, A2, . An klasę sudaro kiekviena iš šių formulių, taip pat visos formulės, išvedamos iš f-lių, jau priklausančių šiai klasei.
Teiginių logikos modelių teorijoje buvo vartotos dvi svarbis sąvokos : tapačiojo teisingumo ir loginio išplaukimo. Įrodymų teorijoje panašią reikšmę turi įrodomumo ir išvedamumo sąvokos. Palyginsim šių sąvoku prasmę:
1. ╞ AB tai reiškia, kad f-lė AB yra tapačiai teisinga, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių
Išvedamumo santykio savybės
2.1T.a) A1, A2,..,An |- Ai (i=1,n). b) jjei A1, ., An |- B1; A1, ., An |- B2; A1, ., An |- Bk ir B1,.,Bk |- C, tai A1, ., An |- C. a) Iš duotosios prielaidų aibės išvedama kiekviena iš šios aibės prielaida. b) Jei iš duotos prielaidų aibės išvedama kiekviena formulė iš kurios nors prielaidų aibės, o iš šios prielaidų aibės išvedama C, tai C išvedama ir iš pradinės prielaidų aibės. Įrodymas: a) Formulei Ai išvesti iš formulių A1, A2,.An pakanka paeiliui užrašyti visas formules A1, A2,.An bet kuria tvarka, tik paskutinę užrašant Ai. b) išvedant formulę C iš formulių B1,.,Bk , formules B1,.,Bk pakeitus duotaisiais jų išvedimais iš formulių A1, A2,..,An, gaunamas formulės C išvedimas iš A1, A2,..,An.
Taigi, pagal 2.1T. formulių išvedamų iš A1, A2,..,An klasę sudaro kiekviena iš šių formulių, taip pat visos formulės, išvedamos iš formulių jau priklausančių šiai klasei. Teiginių logikos modelių teorijoje buvo naudotos 2 svarbios sąvokos: tapačiojo teisingumo ir loginio išplaukimo. Įrodymų teorijoje panašią reikšmę turi įrodomumo ir išvedamumo sąvokos. Palyginsim šių sąvokų variantus: 1) |= A=>B. Toks užrašymas reiškia, kad formulė A=>B yra tapačiai teisinga, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių atomų rinkiniams formulė A=>B įgyka tik t reikšmes. 2) AA|=B. Tai reiškia, kad iš formulės A išplaukia formulė B, t.y. kad esant visiems į bent vieną iš formulių A arba B įeinančių atomų reikšmių rinkiniams, kai formulė A įgyja reikšmę t, tai ir B įgyja t reikšmę. 3)
|- A=>B, reiškia , kad formulė A=>B įrodoma, t.y. kad egzistuoja baigtinė formulių seka pasibaigianti A=>B, be to, kiekviena šios sekos formulėyra aksioma arba gaunam pagal MP taisyklę. 4) A |- B. Reiškia, kad iš A išvedama B, t.y. kad egzistuoja baigtinė formulių seka pasibaigianti B, be to, kiekviena šios sekos formulė yra arba A, arba aksioma, arba gaunama pagal MP taisyklę.
Sąvokos 1-4 yra tarpusavyje susijusios. 1.13T. nustatė ryšį tarp tapačiojo teisngumo ir loginio išplaukino. Dabar pateiksim teoremas. kurios nurodys ryšį tarp įrodomumo ir išvedamumo, tarp tapčiojo teisingumo ir įrodomumo.
2.2T. Tarkime. kad bet kuri formulių aibė, tuomet: a) jei |- A=>B, tai , A|-B; b) jei |-A=>B, tai A|-B (vienos formulės atžvilgiu). Įrodymas: sąlygoje duotų formulės A=>B išvedimą iš formulių aibės galima paversti formulės B išvedimu iš aibės ir A. 1..k. A=>B; k+1. A; k+2. B (MP k+1, k). Išvados: a) jei įrodoma formulė |-A1=>(.(An-1(An)).), tai A1, A2, ., An |-B b) Jei įrodoma konjunkcija |- AA1A2..An B, tai A1, A2, ., An |-B. Įrodymas: a) Įrodoma pritaikius n kartų 2.2T.
b) Pagal išvados sąlygą gauname A1A2..An |- B (2.1). Įrodysima, kad iš sekos išvedame konjunkciją A1, A2, ., An|- A1A2..An. Kad sėkmingai tai padaryti, pritaikysim konjunkcijos įvedimo (KĮ) taisyklę: A, B |- AB. Įrodymas: 1. A; 2. B; 3. A(B AB) (AS3); 4. B AB; 5. AB. (įrodyta).
1. A1, ..An |- An 2.1T a);
2. A1, ..An |- An-1 2.1T a);
3. An, An-1 |- AnAn-1 KĮ;
4. A1, .., An |- AnAn-1 2.1T b)
5. A1, .., An |- An-2 2.1T a)
6. An-2, An-1, An |- An-2An-1An
7. A1,.., An |- An-2An-1An 2.1Tb
…
3n-5. A1.An |- A2..An
3n-4. A1.An |- A1
3n-3. A1.An |- A1.An.
Iš 2.2, 2.1 pagal 2.1T b) dalį gauname A1..An |- B.
ĮRODYMŲ TEORIJA. DEDUKCIJOS TEOREMA
Dedukcijos teoremoje yra išreikšta formalaus išvedimo savybe, atitinkanti gerai žinomą neformalaus mąstymo būdą. Šią teoremą suformulavo ir įrodė moksl. J.herbrand 1930m.
2.3T a)jei iš ,A├B, tai ├AB
b)jeigu iš A├B, tai ├AB
Pagal teoremos sąlygą egzistuoja formulės B išvedimas. B1 ,.,Bm
Kur Bm=B iš formulių aibės, ir A, t.y. duotasis išvedimas. Reikia įrodyti, kad egzistuoja formulės AB išvedimas iš formuliu aibės , t.y. gaunamasis išvedi-mas. Šie abu išvedimai turi 2 skirtumus: 1.
Duotasis išvedimas baigiasi formule B, o gaunamasis AB; 2. Duotajam išvedime galima remtis prielaida A, o gaunamąjame išvedime tokios prielaidos nėra. Egzistuoja algoritmas, paverčiantis duotąjį išvedimą gaunamuoju išvedimu. Jį panagrinėsime: sakykim, kad duotąjame išvedime prieš kiekv. Formulę parašome simbolius A, tuomet paskutinė formulė bus AB. Tačiau tai nėra iš tiesų išvedimas iš formulių aibės . Tačiau prieš kiekv. formulę ABI galima įrašyti papild. formules taip, kad formuliu seka pavirstų gaunamuoju išvedimu iš formulių aibės . Papild. formu-lės parenkamos atsizvelgiant į ttai, su kokiu pagrindimu formulė Bi įeina I duortąjį išvedimą. Galimi 4 variantai: 1.Bi aibės prielaida; 2. Bi tai prielaida A; 3.BI tai aksioma; 4. BI tai formulė gauta pagal MP taisyklę iš kurių nors dviejų ankstesniųjų.
Panagrinėsime:
1. Tarkim Bi = Aj kur Aj . Šiuo atveju Bi yra ne tik duotojo, bet ir gaunamojo išvedimo prielaida. Tuomet gaunamajame išvedime prieš formulę AAj įrašysim 2 formu-les Aj ir Aj (AAj) o tai yra AS1a, kur galimi pakeitimai vietoj A –– Aj, o vietoj B – A. Mūsų pageidaujamą formulę gaunam pagal MP taisyklę.
2.Tarkim, kad BI prielaida A, tuomet BI yra duotojo išvedimo, bet ne gaunamojo išvedimo prielaida. Šiuo atveju gaunamajame išvedime bus formulės AA. Šios formulės įrodymas buvo ppateiktas kaip pvz. ir jį sudarė 4 formulės, vadinasi į gaunamąjį išvedimą reikia patalpinti šias 4 įrodymo formules.
3. tarkim BI yra aksioma, tuomet elgiamės taip pat kaip ir pirmuoju atveju.
4. tarkim, kad BI yra formulė, gauta pagal MP taisyklę iš formulių Bp ir Bq. Tuomet formu-lė Bq turi turėti pavidalą BpBi. Gaunamajame išvedime mes turim turėti formules s. ABp, t.A(BpBI) ir v. ABi. O tai galima pastebėti, kad šie trys nariai atitinka AS1b. tuomet tas formules mes jau turime sekoje, įterpiame AS1b su atitinkamais pakeitimais (ABp)((A (BpBI)(ABI)) AS1b
(B-Bp, C-BI) ir 2*MP taisyklė.
v+1. (A(BpBI))(ABI),
MP(s,v). v+2. ABI ,MP(t,v+1)
Šiuo atveju įterpiam 3 formules
Pvz.: sakykim kad duotas išvedi-mas A(BC), AB├C reikia įrodyti A(BC) ├ABC
1.A(BC) 1.prielaida
2.(A(BC))(AB)(A(BC))
3.AB(A(BC)) AS1a (A-A(BC), B-AB)
4.(AB(B(AB))((AB((BAB)AB))(ABAB)) AS1b(A-AB,B-BAB, C-AB)
5.AB(BAB) AS1a (A-AB)
6.(AB((BAB)AB))(ABAB) MP (2,4)
7.AB((BAB)AB) AS1a (A-AB, B-BAB)
8.ABAB
3)ABA (3 var.) AS4a
9.ABA
10.(ABA)(AB(ABA)) AS1a(A-ABA,B-AB)
11.AB(ABA) MP(9,10)
4)A MP(2,3) (4 var.)
12.(ABAB)((AB(ABA))(ABA)) AS1b(A-AB,B-AB,C-A)
13.(AB(ABA))(ABA) MP(8,12)
14.ABA MP(11,12)
5)ABB AS4b (3 var.)
17.AB(ABB)
6)B MP(2,5)
7)BC MP(4,1)
8)C MP(6,7)
18.,19.,
20.lygiagrečiai 6 6.B 20.ABB MP(17,19) 21.,22.,
23.lygiag.7 BC 23.AB(BC) MP(3,22)
24.,25.,26.lyg.8 C 26.ABC MP(23,25)
remdamiesi įrodymu teorija sudarėm gaunamą išvedimą. Taikant aprašytą algoritmą ir imant 26 formules kaip duotąjį išvedimą, gausime formulės įrodymą, kurį sudarys 80 formulių
(A(BC))(ABC)
kaip matyti iš pvz.2.3T įrodyme aprasytas duotojo išvedimo trans-formavimas į gaunamąjį labai išplečia gaunamąjį iišvedimą. Duotajame išvedime yra k f-lių, o gaunamajame 3k+2. Tačiau dažnai nebūtina turėti patį įrodymą. Užtenka nustatyti tik patį įrodomumo faktą. Pvz. irodomumo fakto nustatymui daug padeda dedukcijos teorema. Pvz. nustatykime kad formulė yra įrodoma
9.├(A(BC))(B(AC))
už įrodymo ženklo yra ‘’, tai yra ši formulė buvo gauta taikant deduk.T tokiai formulei
8.A(BC)├B(AC)
į dešinę už įrodymo ženklo yra ‘’. Vadinasi ši f-lė buvo gauta taikant deduk.T
7.A(BC),B├AC
už įrodymo ženklo yra ..
6.A(BC), B,A ├C
norint nustatyti pradinės f-lės įrodomumą, pakanka nustatyti kad egzistuoja f-lės C išvedimas iš duotų prielaidų. Bandom sudaryti f-lės C išvedimą
1.A(BC) prielaida
2.B prielaida 3.A prielaida
4.BC MP(3,1) 5.C MP(2,4)
suradom f-lės C išvedimą iš duotų prielaidų. Toliau darydami žingsnius tiesiogine tvarka, taikydami deduk.T gausim kad pradinė f-lė yra įrodoma.
Jei A├B ,tai├AB
Jei 9 f-lėje pakeisim A į B, o B į A gausime f-lę 10. ├(B(AC))(A(BC))
Panaudosim AS9, kurioje atliksim pakeitimus 11.├((A(BC))(B(AC)))((B(AC))(A(BC)))((A(BC))_(B(AC))) AS9(A-A(BC),B-B(AC))
12.├((B(AC))(A(BC)))((A(BC))_(B(AC))) MP(9,11)
13.├(A(BC))_(B(AC)) MP(10,12)
turėdami paprastą išvedimo įro-dymą, deduk.T galime nustatyti, kad egzistuoja įrodymas daugeliui sudėtingų f-lių. Neturim pačio įrodymo, bet nu-statom, kad jis egzistuoja.
TEORIJOS NEPRIEŠTARINGUMAS
Apibendrinant 2.2T ,2.3T rezultatus galima tvirtinti, kad AB įrodoma tada ir tik tada, kai iš A išvedama B.tokiu budu ryšys tarp įrodomumo ir išveda-mumo yra nustatytas. Panašiai buvo nustatytas ryšys tarp tapačiojo teisingumo ir loginio išplaukimo modelių teorijoje. JJeigu pavyktų įrodyti, kad sąvokos f-lė E yra įrodoma ir f-lė E tapačiai teisinga yra lygiareikšmės, tai užbaigtume ekvivalentumo nustatymą tarp modelių ir įrodymų teorijų.
2.5Ap. Formalioji aksiominė teorija ,vad. neprieštaringa jei nėra nei vienos tokios f-lės A, kad f-lės A ir A būtų įrodomos vienu kartu. Formalioji aksiomine teorija vadinama prieštaringa, jei egzistuoja tokia f-lė A, kad f-lės A ir A yra įrodomos abi kartu.
2.4T kiekviena įrodoma f-lė yra tapačiai teisinga. Jei ├ E, tai ╞ E.
teorijos L aksiomos tai 1.3T pirmosios 13 f-lių. Ir pagal šią te-
oremą jos yra tapačiai teisingos. Atitinkamai pagal 1.9T jei MP taisyklės prielaidos A ir AB yra tapačiai teisingos, tai šios taisyklės išvados B yra tapačiai teisinga. Pagal šios teoremos sąlygą, f-lė E yra įrodoma, tai yra ji užbaigia baigtinę f-lių seką, sudarytą iš aksiomų arba iš f-lių gautų pagal MP taisyklę iš bet kurių 2 ankstesnių f-lių. Bet visos šitos f-lės yra tapačiai teisingos. Todėl tapačiai teisinga ir f-lė E.
išvada: teorija neprieštaringa.
∆ tarkime, kad teorija prieštarin-ga. Tada pagal 2.5Ap egzistuoja tokia f-lė A, kad A ir A įrodomos abi kartu. Pagal 2.4T jos yra abi tapačiai teisingos. Tačiau taip būti negali, nes pagal neigimo Ap, kai A=t, tai A=k.
LOGINIŲ OPERATORIŲ ĮVEDIMO IR PAŠALINIMO TAISYKLĖS.
T. atvirkštinę 2.4T įrodyti yra žymiai sunkiau. Todėl reikia plėtoti teoriją. Iki šiol įvedimo ir išvecimo egzistavimui įrodyti taikėme tik 2 taisykles. Tai MP leidžianti pašalinti ‘’, todėl dar vad. ‘’ pašalinimo taisykle ir deduk. teorema, leidžianti įvesti ‘’, todėl dar vad. ‘’ įvedimo taisykle. Dabar nustatysime ir ki-tų loginų operatorių įvedimo ir pašalinimo taisykles.
2.5T. bet kuriai baigtinių f-lių ai-bei ir bet kurioms f-lėms A, B, C teisingos taisyklės užrašytos lentelėje.
Op. Nr. Įvedimas Pavad.
1 jei ,A├B,tai DT
├AB IĮ
3 A,B├AB KĮ
6 A├AB DĮ1
7 B├AB DĮ2
9 Jei ,A├B ir
,A├B,tai
├A RA,NI
12 AB,BA EĮ
├AB
Op. Nr. Pašalinimas Pavad.
2 A,AB├B MP,IP
4 AB├A KP1
5 AB├B KP2
8 Jei ,A├C ir
,B├C,tai
,AB├C DP
10 A├A NNP
11 A,A├B SNP
13 AB├AB EP1
AB├BA EP2
Įrodysim kiekvieną taisyklę 1)taisyklė, įvedanti ‘’ buvo įrodyta kaip T.2.3 2) taisyklė, pašalinti ‘’ yra pra-dinė teorijos taisyklė, todėl neįrodoma
3-7, 10, 12-14 taisyklės pagrin-džiamos naudojant atitinkamą aksiomų schemą ir MP. Pvz-iu galima laikyti konj. Įvedimo taisyklės įrodymą pateiktą 2.2T įrodyme.
8) yra disj. pašalinimo taisyklė
Jei , A├C ir , B├C, tai ,AB├C
1. ,A├C 1.prielaida
2. ,B├C 2. Prielaida
3.
├AC 3. IĮ (1)
4. ├BC 4. IĮ (2)
5.AC,BC, 5.Įrodymas bus
AB├C pateiktas atskirai
6.,AB├C 6.Įrodymas bus
žemiau
5 eilutę
1’AC 1’priel. 2’BC
2’priel
3’ AB 3’prielaida
4’(AC)((BC)(ABC)) 4’ AS6
5.’ (BC)(ABC) 5.’ MP(1’,4’)
6.’ ABC 6.’ MP(1’, 5’)
7.’ C 7.’MP(3’,6’)
6 eilutė
1.’ ,AB├E,E 1.’2.1Ta
2.’ ├AC 2.’pagr. įr.3 žings.
3.’,AB├AC;3.’2.1Tb(2’,1’)
4.’├BC 4.’pagr.įr.4 žings.
5.’,AB├BC;5.’2.1Tb(1’,4’)
6.’,AB├AB 6.’ 2.1Ta
7.’AC,BC,AB├C
7.’Pagr. įrodymo 5 žingsnis
8.’,AB├C;8.’2.1Tb(3’,5’,6’,7’
9)taisyklė ‘’įved. (savarank.)
11)taisyklė silpno ‘’ pašalini-mas A,A├B
1.A,A,B├A 1. 2.1Ta
2. A,A,B├A 2. 2.1Ta
3. A,A├B 3. NĮ(1,2)
4. B├B 4.NNP
5. A,A├B 5. 2.1Tb(3,4)
Įrodytosios taisyklės aprašo labai paplitusius ssamprotavimo būdus. Norint įrodyti konj. struk-tūros sakinį AB atskirai įrodo-ma A ir B, o po to sakoma-teore-ma įrodyta, t.y. įrodyta AB. frazėje – teorema įrodyta slypi netiesioginis perėjimas nuo A ir B prie AB. Pvz.: įrodom sakinį trapecijos vidurinė linija yra lygiagreti su pagrindais ir yra lygi jų sumos pusei. Įrodomas atskirai kiekvienas iš šių sakinių. Konj. Pašalinimo taisyklės taiko-mos jau įrodytiems konjunkcinės struktūros sakiniams. Sakykim, reikia spręsti uždavinį : raskite trapecijos kurios pagrindai A ir C vidurinę liniją. Iš įįrodyto sakinio naudojamas tik 2 narys ir randa-ma trapecijos vidurinė linija. Ekvivalencinės struktūros sakinių įrodymas susideda iš 2 etapų:
1) AB įrodymas ir 2) BA įrodymo. Ekvivalencijos pašalinimo taisyklės taikomos jau įrodytiems sakiniams- ekvi-valencijoms. Pvz.: trikampis yra statusis tada ir tik ttada, kai jo didžiausios kraštinės kvadratas = kitų dviejų kraštinių kvadratų sumai. Tai ekvivalencija. Pagal taisyklę EP2 gauname- jei trikampio didžiausios kraštinės kvadratas=kitų 2 kraštinių kvad-ratų sumai, tai toks trikampis sta-tusis. Praktikoje dažnai taikomos trumpesnės samprotavimo sche-mos, pagrįstos tokiais išvedimais iš ekvivalencijos:
1)AB, A├B; 2)AB,B├A;
3) AB, A├B;
4) AB, B├A;
5) AB├AB;
6) AB├BA;
7)AB,B├A; (MT)
8)AB├BA;(K)kontrapozicija
7)-oji taisyklė įrodoma tokia seka
∆ 1)AB, B,A├B 1)2.1a
2)AB,B,A├AB 2)2.1a
3)AB,B,A├A 3)2.1a
4)A,AB├B 4)MP
5)AB,B,A├B 5)2.1b(3,2,4)
6)AB,B├A 6)MĮ(5,1) ▲
7-ajam taisymui pritaikę IĮ tai-syklę gausime 8-ąją taisyklę.
3)-ioji taisyklė:
∆ 1)AB,A├AB 1)2.1a
2)AB├BA 2)EP2
3)AB,A├BA 3)2.1b(1,2)
4)AB,A├A 4)2.1a
5)BA,A├B 5)7 tais.(MT)
6)AB,A├B 6)2.1b(3,4,5)
Teorijoje L kaip ir bet kurioje ak-
siominėje teorijoje, turinčioje silpno neigimo pašalinimo, konj. pašalinimo(KP1 ir KP2), galima naudoti lygiavertį 2.5A.
2.6Ap. Formalioji aksiominė teorija vad. neprieštaringa, jei jos teorijoje egzistuoja nors viena neįrodoma f-lė. Jei visos f-lės įįrodomos, tai teorija vad. priešta-ringa.
Iš tikrųjų kad duotoji teorija ne-prieštaringa pagal 2.5Ap. tuomet nėra nė vienos tokios f-lės A, kad A ir A būtų įrodomos vienu metu. Todėl f-lė AA yra neį-rodoma. Jei būtų įrodoma tai pagal KP1 ir KP2 taisykles būtų įrodomos ir A ir A. tokiu būdu surandame neįrodomą f-lę, todėl pagal 2.6Ap. teorija L neprieš-taringa.
Tarkim, kad teorija L nepriešta-ringa pagal 2.6Ap. tuomet egzis-tuoja tokia f-lė B, kuri nėra įrodoma. Vadinasi nė vienai –lei A neturi ggalioti, kad A ir A yra įrodomos, nes jei taip būtų,tai pagal SNP taisyklę turėtų būti įrodoma ir f-lė B.
TEORIJOS ‘L’ PILNUMAS
Svarbiausia matematikos problema – neprieštaringumas, kuris buvo išnagrinėtas prieš tai buvusiame skyrelyje.
Kita svarbi problema – teorijos pilnumas.
Teorija L turi 13 formulių, vadinamų aksiomomis. Kyla klausimas, ar galima prie šių aksiomų prijungti naujas formules, kad įrodymų formulių būtų daugiau. Atsakant į šį klausimą, reikia apibrėžti, kokių savybių formules norime turėti teorijoje. Skirtingas savybes atitiks skirtingo pilnumo sąvokos.
Teorijoje L tokia pageidaujama savybe būtų formulių tapatusis teisingumas, nes kiekviena tapačiai teisinga formulė išreškia logikos dėsnius.
A 2.7.Logiškai neprieštaringas skaičiavimas vadinamas pilnu tapataus teisingumo požiuriu juo įmanoma bet kuri tapačiai teisinga formulė.
Prieš nustatant teorijos pilnuma, įrodysim 4 lemas:
L 2.1.Tarkim, kad duoti loginių operatorių ┐, , , , _ apibrėžimai. Kiekvieno iš 5-ių loginių operatorių teisingumo lentelės kiekvienoje eilutėje yra teisingas toks išvadamumas:
A ┐A
1.k k A ├ ┐┐A
2.k t ┐A ├ ┐A
A B AB
3.t t t A, B ├ AB
4.t k k A, ┐B ├ ┐(AB)
5.k t k ┐A, B ├ ┐(AB)
6.k k k ┐A, ┐B ├ ┐(AB)
A B AB
7.t t t A, B ├ AB
8.t k t A, ┐B ├ AB
9.k t t ┐A, B ├ AB
10.k k k ┐A, ┐B ├ ┐(AB)
A B AB
11.t t t A, B ├ AB
12.t k k A, ┐B ├ ┐(AB)
13.k t t ┐A, B ├ AB
14.k k t ┐A, ┐B ├ AB
A B A_B
15.t t t A, B ├ A_B
16.t k k A, ┐B ├ ┐(A_B)
17.k t k ┐A, B ├ ┐(A_B)
18.k k t ┐A, ┐B ├ A_B
1-os įrodymas:
∆1)A, ┐A├ A 1) 2.1 a
2)A, ┐A├ ┐A 2)2.1 a
3)A├ ┐┐A 3)NĮ(1,2)
▲
9-os įrodymas:
∆1) ┐A, B├ B 1)2.1 a
2) B├ AB 2)DĮ2
3)┐A, B├ AB 3)2.1 b (1,2)
▲
15-os įrodymas:
∆1) A,B, A├ B 1)2.1 a
2)A, B├ AB 2)IĮ(1)
3)A, B, B├ A 3)2.1 a
4)A, B├ BA 4)IĮ(2)
5)AB, BA├ A_B 5) EĮ
6)A, B├ A_B 6)2.1 b (2,4,5)
▲
16-os įrodymas:
∆1)A,┐B, A_B├ A 1)2.1 a
2)A,┐B,A_B├ A_B 2)2.1 a
3)A_B├ AB 3)EP1
4)A,┐B,A_B├ AB 4)2.1b(2,3)
5)A,AB├ B 5)IP(1,4)
6)A,┐B,A_B├ B 6)2.1b(1,4,5)
7)A,┐B,A_B├ ┐B 7)2.1a
8)A,┐B├ ┐(A_B) 8)NĮ(6,7)
▲
2.1. lemos savybę išplėsime bet kuriai formulei:
L 2.2 Bet kurios formulės E, sudarytos iš atomų P1, ., Pn, kiekviena is 2n teisingumo lentelės eilučiu yra teisingas atitinkamas išvedamumas.
2.2 lemos, įrodymas pateiktas pavyzdžiu:
Tarkim, formulė E yra tokia formulė:
P( Q R _ Q ) ( P,Q,R)=(t,k,k)
P, Q, R ├ ( PP ( QR_Q))
1 Q ├ Q
2 P, Q, R ├ Q
3 P, Q, R ├ Q
4 Q, R ├ ( Q R )
5 P,Q,R├ R
6 P, Q, R├( Q R )
7 ( Q R ), Q├ ( Q R _Q )
8 P, Q, R ├ ( Q R _ Q )
1 2.1 L (2 eilutė) 1 žingsnis
2 2.1 a
3 2.1 b ( 2,1)
4 2.1 L (10 eilutė) 2 žingsnis
5 2.1 a
6 2.1 b (3,4,5)
7 2.1 L (17 eilutė) 3 žingsnis
8 2b (6,3,7)
4 žingsnis analogiškas 3-iam
Konkrečios formulės kokrečiai eilutei taikomas metodas tinkamas kiekvienu atveju
L 2.3 Jei formulė E, sudaryta iš atomų P1, .. ,Pn ir tik iš jų yra tapačiai teisinga, tai galioja tokios aksiomos:
P1 P1 , P2 P2 , Pn Pn ├ E
Analogiškai galima įrodyti n atvejį. Jei yra n, tai DP reikia taikyti 2k+1+2n-2+..+2+1 kartų.
L 2.4 Bet kuriai formuliai A arba A ęrodoma formulė ├ A A
∆
1 ( A A ), A ├ A A
2 ( A A ), A ├ ( A A )
3 ( A A ) ├ A
4 ( A A ), A ├ A A
5 ( A A
), A ├ ( A A )
6 ( A A ), A ├ A
7 ├ ( A A )
8├ A A 1 DĮ 1
2 2.1 a
3 NĮ (1,2)
4 DĮ 2
5 2.1 a
6 NĮ (4.5)
7 NĮ (3.6)
8 NNP (7)
T 2.6. Jei formulė E yra tapačiai teisinga, tai ji įrodoma
∆ Pagal 2.4 lemą žinoma, kad formulės P1┐P1, P2┐P2, ., Pn┐Pn yra įrodomos. Formulė E – tapačiai teisinga, todėl pagal 2.3 lemą ji yra išvedama iš formulių P1┐P1, P2┐P2, .., Pn┐Pn. Remiantis gauta išvada ur 2.1 teoremos dalimi, gauname, kad E yra įrodoma.
▲
Šia teorema baigiasi modelių teorijos ir įrodymų teorijos lygiavertiškumo įrodymas. Dabar galim perrinkti visus rezultatus iš modelių teorijos, keisdami tapataus teisingumo ženklą į įrodomumo ženklą. Tokiu būdu visos formulės, pateiktos 1.3 teoremoje, yra įrodomos. Nors teiginių skaičiavimas, naudojant teisingumo lenteles, atrodo labiau natųralus, tačiau, istoriškai jis parodė vėliau. Pirmiausiai tai padarė amerikiečių matematikas E. Kostas 1921m., įrodęs 2.4 ir 2.6 teoremas, ir lenkų matematikas J.Lukoševičius.
Redikatu skaiciavimas
1.Lingvistiniai samprotavimai fformules , laisvi ir susieti kintamieji.
Teiginiu skaiciavimuose mes nagrinejam loginius santykius priklausancius nuo budo, kuriais loginiai teiginiai yra sujungti I tam tikrus blokus.
Patys sie blokai nebuvo analizuojami. Predikatu skaiciai.
Tuo tikslu ivesim dvi naujas operacijas:
- visuotinumo kvantorius; egzistavimo kvantorius
panagrinekim tteigini “Sokratas yra zmogus”.
Sio teiginio dalis isreiksta konstrukcija “-yra zmogus” arba “X yra zmogus” vad. predikatu.
Ziurint is matematiniu poziciju, predikatas yra isreiskiamas teigianciaja junkcija, kurios reiskiniu aibe yra teiginiai.si funkcija kekvienam kintamojo X reiksmiai pateikia tam tikra teigini. Jei X yra “sokratas” tai teiginys bus teisngas. Jei X bus “seironas “ tai teiginys bus klaidingas . teiginys taip pat bus kalidinghas jei vietoj X istatysim koki nors daikta.
“Jonas myli Onute”. Tai teiginys kuris gali buti sudarytas is 3 tokiu funkciju: “X myli Onute”,”Jonukas myli Y”,”X myli Y”. mes vadinsime predikatu bet kokia teigiancia funkcija, esant bet kokiam n , n>=0 objektu vadinsime bet kuria X, Y reiksme. Jei n=0 tai predikatas yra teiginys. Jei n=1 tai predikatas aatitinka tai , kas yra savybe. Jei n=2 tai predikatas yra dvejetainis rysis( jei n=3 . trejetainis ir t.t.)
kintamieji israiskose naudojami kaip loginiai, vietoj kuriu galima istatyti reiksmes . Vietoj kintamuju nebutina statyti vardus, galima sakyti ir taip:
a)kazkas myli Onute b) niekas nemyli Onutes c) visi myli Onute d) kekvienas ka nors myli e) ka nors visi myli f) kekvienas myli save g) nera tokio kuris nemyletu saves.
Pazymekime L( X, Y) teigini “ X myli Y”, tuomet
a) X LL(X, Onute) b) X L(X, Onute)
c) X L( X, onute) d) X Y L ( X, Y )
e) Y X L ( X,Y) f) X L(X,X) g) XL(X,X)
teiginiu logikoje ziamiausias lygis buvo – atomai. Predikatu logikoja zemiausias israusku lygis vad. elementariomis predikatu israiskomis , arba jonais.
P, P(-), P(-,-), P(-,-,-)
Q,Q(-), Q(-,-), Q(-,-,-)
P- zymi nulvieti jona, P(-) – vienvieti jona ir t.t.
Israiskas su kintamaisiais pvz: P(x,y,z ), P(y,z,x), P(u,v,w) ir t.t. vad skirtingomis 3-viecio jono ivardinimo formomis. Ivardinimo formu kintamieji turo buti skirtingi. Ivardinimo formos P(x,y,z ), P(y,z,x), P(u,v,w) vad. elementariomis predikatinemis israiskomis su duotais kintamaisiais.
Dabar jau galime aprasyti sakiniu klase , kuir gales buti formuojama is jonu. Koks bebutu n-vietis jonas P(-.-) ir koks bebutu sakinys nebutinai skirtingu kintamųjų r1, r2,..rn išraišką P(r1,r2.rn) vad. Elemntaria formule arba atomu. Formulių klasę sudaro visos elementarios formulės ir sudėtinės formulės, kurios gaunamos iš elementarių formulių daugkartinių loginių simolių panaudojimo.,,,,,,_. Jei A, B yra elementarios formulės, tai A, AB, AB, AB, A_B yra sudėtinės formulės. Jei A yra formulė, o x kintamasis, tai xA, xA yra sudėtinės formulės. Kvantorių prioritetasyra didesnis už aukčiau žinomų log. Operacijų prioritetus. xAB, tai reiškia (XA)B, o jei norim kitaip, reikia rasyti ssu ( ) X(AB). Kintamasis esantis po kvantoriaus zenklu, vad. susietu kintamuoju. Kintamasis kuris neturi su juo susijusio kvantoriaus, vad, laisvuoju kintamuoju. Panagrinekim formule X(P(X)XQ(X,Z)YR(X,Y)VQ(Z,X). formules dalije XQ(X,Z), X susietas kvantoriumi X
Si susietuma galima zymeti visiems formules X-ams, suteokiant indeksa 1. Indeksas 2, 3 galima pazymeti kintamuosius, susietus kvantoriais Y ir X . formules nagrinejimas prasideda nuo giliausio lygio. Esant tam paciamlygmenyje keliems kvantoriams , nagrinejams kairiausias dar nepazymetas kvantorius.
Tuomet musu formule atrodys taip:
X3(P(X3)X1Q(X1,Z)Y2P(X3,Y2))VQ(Z,X)
kintamieji kurie neturiindeksu yra laisvi
dar viena formule
Y(P(Y)XQ(X,Z)ZR(Y,Z))VQ(Z,X). sudeja inde-ksus : Y3(P(Y3)X1 Q(X1,Z)Z2 R(Y3,Z2))VQ(Z,X)
nutrinam kintamuosius kurie turi indeksus
3(P(3)1 Q(1,Z)2 R(3,2))VQ(Z,X)
3(P(3)1 Q(1,Z)2 R(3,2))VQ(Z,X)
pastebesim kad sios 2 formules yra lygevertes. Dar karta perasom be indeksu ir susietuma pakeiciam “– “
1) X(P(X)XQ(X,Z)YR(X,Y)VQ(Z,X).
2) Y(P(Y)XQ(X,Z)ZR(Y,Z))VQ(Z,X).
ir dar 3 formules . pagal schematini sujungima galima spresti , kad sios formules yra lygiavertes.
3) X(P(X)XQ(X,Z)XR(X,X)VQ(Z,X).
4) Z(P(Z)XQ(X,Z)YR(Z,Y)VQ(Z,X).
5) X(P(X)XQ(X,Z)YR(X,Y)VQ(Z,Y).
(5) nera lygeverte (1) ir (2), nes nesutampa laisvuju kintamuju vardai.
Kintamuju apibrezimo sritis. Tapatusis teisingumas .
Teiginiu logikoje mes sakome, kad kekvienas atomas isreiskia koki nors teigini, kuris yra tiesa arba melas. Analogiskai sakome kiekvienam klasikiniam skaiciavime apie kekviena jona. Taciau , kad butu ka nors galima teigti apie n-vieti jona, pirmiausia reikia nustatyti is kokios srities reiksmes gali igyti kintamieji. Sakykim kad ta sritis yra tam ttikra ne tuscia aibe poziuriu D.
Dabar galima sakyti , kad predikatai isreiksti jonu P(-,,-) arba yvardijimo forma P(r1,.,r n) tampa teiginiu bet kokiam kintamojo r1,..r n reiksmems is aibes D. Pvz . galima naudotis predikatu X0)
1)Pvz D sriti sudaro du objektai kuriuos pazymesim skaiciais 1 ir 2. Tai yra D= {1,2} sakysim mums reikia sudaryti teisngumo lentele tokiai formuliaiP(Y) VX(P(X)Q) sudarant sios formules teisingumo lentele mums reikia vienvietes logines funkcijos attitinkancios P(X), nulvietes atitinkancios Q ir elementu is D atitinkanciu laisvaji kintamaji Y. tures 3 iejimo stulpelius . norin sudaryti lentele reikia sudaryti vienviete funkcija
X 1 2 3 4
1 t T k k
2 t k t k
