8. DEDUKCIJA TEIGINIŲ LOGIKOJE

AMLKon6.pdf

88
8. DEDUKCIJA TEIGINIŲ LOGIKOJE
8.1. Dedukciniai samprotavimai
Dedukcinis samprotavimas, tai tokia mąstymo forma, kada, remiantis logikos dėsniais (tautologijomis), iš duotų žinomų pirminių teiginių (prielaidų) gaunami nauji teiginiai (išvados). Iš teisingų prielaidų gaunamos teisingos išvados.
Paprasčiausiais dedukcinio samprotavimo pavyzdžiais gali būti jau mūsų nagrinėti samprotavimai, atlikti remiantis modus poenens, modus tollens ar kitais paprastais logikos dėsniais.
Realiuose gyvenimiškuose uždaviniuose dažniausiai prielaidų būna daugiau nei dvi, o pačios prielaidos būna sudėtingi teiginiai, sudaryti iš tam tikro skaičiaus pirminių teiginių. Tokiai prielaidų visumai, kaip taisyklė, nepavyksta iš karto pritaikyti kokio nors žinomo paprasto logikos dėsnio. Tada išvadų pagrindimui taikomi kiti (teisingumo lentelių, formaliosios dedukcijos) logikos metodai.
Panagrinėkime dedukcinio samprotavimo pavyzdį. Tegul turime samprotavimą, sudarytą iš 3 prielaidų (q1, q2, q3) ir išvados r, kurių kiekvienas, savo ruožtu, sudarytas iš paprastų teiginių p1, p2, p3, pavyzdžiui,
p1 – asmuo visą semestrą sirguliuoja;
p2 – asmuo praleidinėja paskaitas;
p3 – asmuo išlaiko egzaminą:
q1 p1
q2 p3
q3 p2∧p1 → ¬p3
r ¬p2
Samprotavimas bus pagrįstas, jeigu išvada r logiškai išplauks iš prielaidų q1, q2, q3, kitaip, išvedimo taisyklė bus
89
tautologija Tokį pagrįstą samprotavimą viena eilute užrašome panašiai, kaip ir įprasto samprotavimo atveju:
q1 ∧ q2 ∧ q3 |= r; p1 ∧ p3 ∧ ((p2∧p1)→¬p3) |= ¬p2,
Dažnai sutinkamas užrašymas, kuriame vietoj konjunkcijos simbolių „∧“ rašomi kableliai „ , “:
q1, q2, …, qm |= r, p1, p3, p2∧p1→¬p3 |= ¬p2.
Dar sutinkamas užrašymas, kada prielaidos per kablelį rašomos virš brūkšnio, o išvada apačioje po brūkšnio:
q1, q2, …, qm; p1, p3, p2∧p1→¬p3.
r ¬p2
Bendru atveju dedukcinio samprotavimo pagrįstumą nusako apibrėžimas:
Apb.: Sakoma, kad teiginys r logiškai išplaukia iš teiginių q1, q2, …, qm (teiginių logikoje):
q1, q2, …, qm |= r,
jeigu bet kuriam galimam teisingumo reikšmių pasiskirstymui, kai tas reikšmes įgyja paprastieji teiginiai p1, p2, …, pn, sudarantys formules q1, q2, …, qm ir r, formulė r įgyja reikšmę t kiekvieną kartą, kai visos qi įgyja reikšmes t.
Pastaba. Tais atvejais, kai visos prielaidos qi įgyja reikšmę t, o išvada r įgyja reikšmę k, sakoma, kad r logiškai neišplaukia iš teiginių q1, q2, …, qm arba, jog tai yra nepagrįstas samprotavimas.
Tačiau yra galimas ir tokia situacija, jog neegzistuoja nei vienas atvejis, jog visi qi įgytų reikšmę t. Tai būna tada, kai tarp prielaidų yra ir viena kitai prieštaraujančios prielaidos arba, kitaip sakant, prielaidos yra tarpusavyje nesuderinamos.
Apb.: Samprotavimas, kuriame nėra prieštaraujančių prielaidų yra vadinamas tinkamu samprotavimu, gi samprotavimas, kuriame yra
90
prieštaraujančios prielaidos yra vadinamas netinkamu samprotavimu.
Patikrinti ar išvada išplaukia iš prielaidų (ar samprotavimas pagrįstas ar nepagrįstas) naudojami teisingumo lentelių ir formaliosios dedukcijos metodai.
8.1.1. Teisingumo lentelių metodas
Apibrėžime išraiška q1, q2, …, qm |= r reiškia, kad jeigu pagal pirminius teiginius p1, p2, …, pn bus sudarytos teisingumo lentelės visoms formulėms q1, q2, …, qm ir r, tai neegzistuos tokios eilutės, kuriai visi q1, q2, …, qm įgytų reikšmes t, o r įgytų reikšmę k.
Tai yra apibendrintas apibrėžimas anksčiau mūsų nagrinėto loginio išplaukimo santykio, nes dedukciniame samprotavime, jeigu sakoma, kad iš prielaidų q1, q2, …, qm išplaukia išvada r, tai reiškia, kad iš jų konjunkcijos išplaukia r: q1 ∧ q2 ∧ …, ∧ qm |= r.
8.1 Pavyzdys. Teisingumo lentelių pagalba įrodykime teisingumą tokių dedukcinių išraiškų:
1. p1, p3, p2∧p1→¬p3 |= ¬p2, (3 eil. )
2. p1, p1→p3, p3 |= p1∨p2→p3, (1, 3 eil. )
3. p2∧p1→¬p3, ¬p2, p1 → p3 |= ¬(p1∧p2). (3, 7, 8, eil.)
Sudarome teisingumo lentelę, kurioje nepriklausomi kintamieji yra p1, p2, p3, o teisingumo reikšmės bus ieškomos išraiškoms q1, q2, q3 (8.1 lentelė):
Teisingumo lentelėje galime matyti, kad:
1 – mos išraiškos prielaidos p1, p3, p2∧p1→¬p3 drauge teisingos tik 3-čioje eilutėje, o išvada ¬p2 3-čioje eilutėje irgi turi reikšmę “teisinga”, taigi [p1 ∧ p3 ∧ (p2∧p1→¬p3)] |= ¬p2, nes nėra nei vienos eilutės, kurioje kairiojoje pusėje būtų t, o dešiniojoje k;
91
8.1. lentelė Dedukcinių samprotavimų iš 8.1 Pavyzdžio pagrįstumo įrodymas teisingumo lentelių metodu
p1
p2
p3
p2∧p1→¬p3
¬p2
p1→p3
p1∨p2→p3
¬(p1∧p2)
1
t
t
t
k
k
t
t
k
2
t
t
k
t
k
k
k
k
3
t
k
t
t
t
t
t
t
4
t
k
k
t
t
k
k
t
5
k
t
t
t
k
t
t
t
6
k
t
k
t
k
t
k
t
7
k
k
t
t
t
t
t
t
8
k
k
k
t
t
t
t
t
2 - ros išraiškos prielaidos p1, p1→p3, p3 drauge teisingos tik 1 ir 3-čioje eilutėje, o išvada p1∨p2→p3 šiose eilutėse irgi turi reikšmę “teisinga”, taigi teisinga ir visa išraiška [p1 ∧ (p1→p3) ∧ p3] |= (p1∨p2→p3);
3 - ios išraiškos prielaidos p2∧p1→¬p3, ¬p2, p1→p3 drauge teisingos 3, 7, ir 8 eilutėms, o išvada ¬(p1∧p2) šiose eilutėse irgi turi reikšmę “teisinga”, taigi teisinga ir visa išraiška. [(p2∧p1→¬p3) ∧ ¬p2 ∧ (p1 → p3)] |= ¬(p1∧p2), arba iš prielaidų išplaukia išvada.
8.1.2. Formaliosios dedukcijos metodas
Šiuo metodu loginis išplaukimas įrodomas nuosekliai pertvarkant prielaidas, naudojant žinomas tautologijų išraiškas. Jo imamasi tada, kai dedukcinės sistemos prielaidose yra didelis pirminių teiginių pi skaičius ir teisingumo lentelėse turėtų labai išaugti bendras eilučių kiekis. Formaliosios dedukcijos samprotavimo pagrįstumą nusako apibrėžimas:
Apb.: Pagal formaliosios dedukcijos metodą galima teigti, jog q1, q2, …, qm |= r, jei galima sukonstruoti iš prielaidų qi tokią seką formulių v1, v2, …, vl (= r), kurioje
92
kiekviena formulė vi yra arba prielaida (q), arba išplaukia iš ankstesnių sekos narių: v1, v2, …, vi-1 |= vi.
Kitais žodžiais tariant, naudojantis dvejomis taisyklėmis (taisyklė p: formulė v yra prielaida, taisyklė t: formulei v sekoje yra tokios ankstesnės formulės u1, u2, …, us, kad u1, ∧ u2 ∧ …∧ us |= v), yra konstruojama seka formulių v1, v2, …, vl (= r), kurios paskutinė vl yra įrodomoji tezė r.
8.2 Pavyzdys: Įrodykime formaliosios dedukcijos metodu, kad: p ∨ q, p → r, q → s |= r ∨ s. Tai gali būti užrašyta ir mums įprastu būdu, rašant prielaidas vieną po kitos:
p ∨ q
p → r
q → s
/∴ r ∨ s
Šio pavyzdžio sakinių prasmės gali būti tokios:
p – namo grįšiu per Kalėdas,
q – namo grįšiu per Velykas,
r – puošiu eglutę,
s – marginsiu margučius:
grįšiu namo per Kalėdas arba per Velykas,
jeigu grįšiu per Kalėdas, tai puošiu eglutę,
jeigu grįšiu per Velykas, tai marginsiu margučius,
vadinasi, puošiu eglutę arba marginsiu margučius.
Išvedimo seka formaliosios dedukcijos metodu dažnai rašoma eilutė po eilutės, ir kiekvienoje eilutėje atspindimi 4 dalykai:
eilutės numeris ( ),
numeriai eilučių, kurių išraiškos įtakoja į tą eilutę { },
93
pati išvedimo sekos išraiška, kuri yra arba prielaida, arba išvada iš ankstesnių eilučių išraiškų,
komentaras, kuriame nurodoma su kokia taisykle ir iš kokių ankstesnių eilučių gauta ši eilutė.
Tada mūsų pavyzdžio išvedimas atrodytų taip:
{1} (1) p → r p
{1} (2) p ∨ q → r ∨ q 1 t
{3} (3) q → s p
{3} (4) r ∨ q → r ∨ s 3 t
{1,3} (5) p ∨ q → r ∨ s 2,4 t
{6} (6) p ∨ q p
{1,3,6} (7) r ∨ s 5,6 t
Sudėtingesniems išvedimams, su didesniu prielaidų skaičiumi taikomi automatinės dedukcijos metodai.
8.1.3. Samprotavimo netinkamumo nustatymas
8.3 Pavyzdys: Parodykime teisingumo lentelių metodu, kad samprotavimo: q → s, ¬s ∧ p, p → q, |= p → q prielaidos nesuderinamos Jį galima užrašyti ir mums įprastu būdu, rašant prielaidas vieną po kitos:
q → s,
¬s ∧ p,
p → q,
/∴ p → q.
Šio pavyzdžio sakinių prasmės gali būti tokios:
p – staiga užšildo saulė,
q – ištirpsta daug sniego,
s – vanduo užlieja laukus:
jeigu ištirpsta daug sniego, tai vanduo užlieja laukus,
laukų vanduo neužliejo, bet saulė užkaitino,
jeigu staiga užšildo saulė, tai ištirpsta daug sniego,
vadinasi, jei saulė užšildo, tai vanduo užlieja laukus.
94
Panašiai, kaip ir 8.1. lentelėje, į teisingumo lentelę (8.2. lentelė) surašykime nepriklausomus teiginius p, q, s, visas tris prielaidas ir išvadą.
8.2. lentelė Samprotavimo netinkamumo iš 8.3 Pavyzdžio įrodymas teisingumo lentelių metodu
p
q
s
q → s
¬s ∧ p
p → q
p → q
1
t
t
t
t
k
t
t
2
t
t
k
k
t
t
k
3
t
k
t
t
k
k
t
4
t
k
k
t
t
k
k
5
k
t
t
t
k
t
t
6
k
t
k
k
k
t
t
7
k
k
t
t
k
t
t
8
k
k
k
t
k
t
t
1
2
3
4
5
6
7
Matome, kad 4, 5, 6 stulpeliuose, kurie pristato samprotavimo prielaidų teisingumo reikšmes, nėra nei vienos eilutės, kurioje visos trys prielaidos drauge būtų teisingos. Tai ir reiškia, kad prielaidos yra nesuderinamos.
8.2. Automatinė formalioji dedukcija
8. 2. 1. Rezoliucijos taisyklė
Paprasčiausiu jos variantu galima laikyti silpnosios alternatyvos neigimo dėsnį (disjunktyvų silogizmą) (6.27)
|= [(p∨q)∧¬p]→q,
kuris, pagal dedukcijos teoremą įgyja pavidalą:
[(p∨q)∧¬p] |= q, arba p∨q, ¬p |= q
o perrašytas į tradicinį pavidalą atrodytų taip:
p∨q, ¬p
q.
Antecedento teigimo dėsnis (6.28) |= [(p→q)∧p]→q taip pat gali būti lengvai pertvarkytas į rezoliucijos taisyklės
95
pavidalą implikaciją (p→q) pakeičiant disjunkcija (¬p∨q): [(p→q)∧p]→q ≡ [(¬p∨q)∧p]→q, arba
¬p∨q, p
q.
Sudėtingesnis rezoliucijos taisyklės variantas būtų implikacijos pereinamumo dėsnis (hipotetinis silogizmas) (6.31):
|= [(p→q)∧(q→r)]→(p→r),
kuris, implikacijas pakeitus disjunkcijomis ir perrašytas į tradicinį pavidalą atrodytų taip:
¬p∨q, ¬q∨r
¬p∨r.
Kitaip sakant, jeigu turime kelias disjunkcijų pavidalo prielaidas, kurių vienoje yra simbolis, o kitoje jo neigimas, tai šie simboliai tarsi atkertami, o abi likę prielaidų dalys sujungiamos į vieną disjunkciją. Tokia apibendrinta rezoliucijos (atkirtos) taisyklė užrašoma taip:
α1∨p∨α2, α3∨¬
p∨α4
α1∨α2∨ α3∨α4,
kur simboliu αi žymimas sudėtingas teiginys - αi = αi(p, q, r, ...). Atsižvelgiant į disjunkcijos komutatyvumą, rezoliucijos taisyklė gali būti užrašyta ir paprasčiau:
α1∨p, ¬
p∨α2
α1∨α2,

kur p gali būti tiek paprastas simbolis, tiek ir sudėtingas sakinys.
Rezoliucijos taisyklė yra labai patogi prastinti prielaidas, tačiau tam prielaidos turi būti išreikštos disjunkcijų pavidalu. Iš kitos pusės, žinių bazėje prielaidos yra tarpusavyje susiję konjunkciniais ryšiais, vadinasi, jeigu išvedimui norime naudoti rezoliucijos taisyklę, tai žinių bazė turi būti sudaryta iš disjunkcijų konjunkcijos, arba turi turėti konjunkcinės normaliosios formos pavidalą.
96
8. 2. 2. Rezoliucijos taisyklės taikymas
Pritaikykime rezoliucijos taisyklę 8.2. Pavyzdžio sprendimui.
p ∨ q
p → r
q → s
/∴ r ∨ s
Perrašome visas prielaidas ir išvadas į disjunkcijų pavidalą:
p ∨ q
¬p ∨ r
¬q ∨ s
/∴ r ∨ s
Toliau, perrinkinėjame iš eilės visas prielaidas, panašiai kaip formaliosios dedukcijos metode, tačiau taikome tik vieną rezoliucijos taisyklę tol, kol gausime išvadą. Je išvada negaunama, reiškia ji iš prielaidų neišplaukia.
p ∨ q (1)
¬p∨r (2)
¬q∨s (3)
{1,2} p ∨ q, ¬p∨r, |= q∨r (4)
{1,3} p ∨ q, ¬q∨s, |= p∨s (5)
{2,5} ¬p∨r, p∨s, |= r ∨ s (6)
Trečiu žingsniu - (6) fornulė, gauname samprotavimo išvadą. Reiškia išvada iš prielaidų išpalukia. Didelės apimties samprotavimams spręsti gali būti naudojamos kompiuterinės programos.


Comments