5. KONENHODNOTOV LOGIKY
V logice neexistuje mor lka. Kad si me svou logiku ( : : : ) vybudovat, jak chce. Rudolf Carnap: Logick syntax jazyka1
Stru n opakovn
S n kolika vcehodnotovmi logikami jsme se ji setkali v pedchozm vkladu. Zopakujme strun , o jak logiky se jednalo. Tabulky pro dvouargumentov spojky2 budeme ps t tak, e mon hodnoty vroku A nap eme do levho sloupce a mon hodnoty vroku B do prvnho dku. 1) V kapitole o klasick logice ve cvien (?) jsme zmnili logiku s n sledujc tveic hodnot: 1: M m dvod si myslet, e vrok je pravdiv, a nem m dvod si myslet, e je nepravdiv. 0: Nem m dvod si myslet, e vrok je pravdiv, a m m dvod si myslet, e je nepravdiv. X: M m dvod si myslet, e vrok je pravdiv, a m m tak dvod si myslet, e je nepravdiv. ?: Nem m dvod si myslet, e vrok je pravdiv, ani dvod si myslet, e je nepravdiv. 2) V kapitole o intuicionismu ve cvien (?) jsme se dov d li, e Arend Heyting navrhl pro intuicionistickou logiku n sledujc tabulky: A :A 1 0 x x 0 1 A^B 1 x 0 A_B 1 x 0 A)B 1 x 0 A,B 1 x 0 1 1 x 0 1 1 1 1 1 1 x 0 1 1 x 0 x x x 0 x 1 x x x 1 1 0 x x 1 0 0 0 0 0 0 1 x 0 0 1 1 1 0 0 0 1 Tyto tabulky ale nevystihuj pesn mnoinu intuicionistickch tautologi - formule (A ) B) _ (B ) A) je tautologi tto logiky (bez ohledu na pravdivostn hodnotu A a B je jej hodnota 1), ale nen tautologi intuicionistick logiky (lze k n toti sestrojit kripkovsk protipklad). 3) V kapitole o mod lnch logik ch jsme se podrobn zabvali L ukasiewiczovou trojhodnotovou mod ln logikou s tabulkami A :A }A A 1 0 1 1 x x 1 0 0 1 0 0 A^B 1 x 0 A_B 1 x 0 A)B 1 x 0 A,B 1 x 0 1 1 x 0 1 1 1 1 1 1 x 0 1 1 x 0 x x x 0 x 1 x x x 1 1 x x x 1 x 0 0 0 0 0 1 x 0 0 1 1 1 0 0 x 1 Cvi en 1. Zvolen zpsob z pisu se pli nehod pro zji ov n, zda je n jak sloit j formule tautologi t i on vcehodnotov logiky, umouje ale vz jemn porovn vat tabulky pro jednotliv spojky v rznch logik ch. Zjisti, pro kter spojky a kter hodnoty argument se li L ukasiewiczova a Heytingova trojhodnotov logika. Kolika dovou tabulku potebujeme pro zji t n, zda je formule ((A ) B) ) C) ) (((B ) A) ) C) ) C) tautologi, jestlie kad dek odpovd jin trojici hodnot A, B a C, jak je tomu obvykl v klasick logice? Zkus vymyslet rychlej zpsob, jak zjistit, jestli je n jak formule tautologi. 1 2
Cituje Jaroslav Peregrin: Analytick losoe (nrt!), kapitola 4, str. 5. Dvouargumentov spojky jsou spojky ^ _ ) ,, kter spojuj v dy dva vroky. Typeset by AMS-TEX 1
2
Pravdivostn hodnota x
Dve, ne se pustme do dkladn j ho zkoum n trojhodnotovch logik, musme si rozmyslet, co to znamen , e vrok m pravdivostn hodnotu x. Jak dvody n s vedou k tomu, e krom pravdivch a nepravdivch vrok pipou tme je t tet monost?
1) Neznalost skute n pravdivostn hodnoty
Vrok m pravdivostn hodnotu x, pokud nevme, zda je pravdiv i nepravdiv. Do tto kategorie spadaj napklad vroky o budoucnosti, kter vedly L ukasiewicze k vytvoen jeho trojhodnotov logiky. Vypadaj tabulky L ukasiewiczovy logiky tak, jak bychom ekali pi tomto ch p n vznamu hodnoty x? V ppad , e nevme, zda je vrok A pravdiv i nepravdiv, samozejm nevme ani o jeho negaci, zda je pravdiv i nepravdiv , take :x = x. Ale i v ppad , e nevme, zda je vrok A pravdiv i ne, vme, e je-li vrok B pravdiv, tak je pravdiv alespo jeden z vrok A a B, take A _ B by m l bt pravdiv: x _ 1 = 1. Cvi en 2. Podvej se na tabulky negace, konjunkce a disjunkce v Heytingov a L ukasiewiczov logice a rozmysli si, e skuten odpovdaj tomuto ch p n hodnoty x. Odpovd tomuto pojet lpe Heytingova nebo L ukasiewiczova implikace?
2) Nesmyslnost
Vrok s pravdivostn hodnotou x povaujeme za pln nesmysln. K logickmu folkl ru pat teba vroky Caesar je prvoslo a bezbarv zelen my lenky zuiv sp.3 Je zejm, e je-li vrok A nesmysln, budou nesmysln i v echny sloit j vroky, kter jej obsahuj, teba bezbarv zelen my lenky zuiv sp a slunko je lut. Doplnme-li na z klad tto vahy na v echna nov vznikl msta v tabulce hodnotu x, dostaneme Bo varovu trojhodnotovou logiku z roku 1939: A :A A^B 1 x 0 A_B 1 x 0 A)B 1 x 0 A,B 1 x 0 1 0 1 1 x 0 1 1 x 1 1 1 x 0 1 1 x 0 x x x x x x x x x x x x x x x x x x 0 1 0 0 x 0 0 1 x 0 0 1 x 1 0 0 x 1
Cvi en 3. Uka, e v tto logice neexistuj dn tautologick vroky - vroky, jejich pravdivostn hodnota je 1 pi libovolnm piazen pravdivostnch hodnot jednoduchm vrokm.
3) ste n pravdivost
Pravdivostn hodnotu x meme tak piadit t m vrokm, kter le n kde mezi pravdou a nepravdou - teba vrokm jako Praha je obrovsk nebo r da poslouch m jazz. Praha je urit velk , rozhodn v t ne Nov Ves, ale nen tak obrovsk jako New York. V tomto ppad ale brzy narazme na to, e bychom potebovali vce ne ti pravdivostn hodnoty: ctme, e vrok Brno je obrovsk by m l bt pravdiv j ne vrok Nov Ves je obrovsk ale mn pravdiv ne Praha je obrovsk , co je vrok mn pravdiv ne New York je obrovsk. Pro tento typ vrok byly vytvoeny fuzzy logiky, o kterch si povme v p t kapitole.
Nvod, jak si vytvo it vlastn trojhodnotovou logiku Logika je ot zkou nab dky a popt vky.
Doc. Miroslav Jauris, CSC.4
Pedstavme si, e ses v souladu Jaurisovm tvrzenm rozhodl vytvoit a nabzet vlastn trojhodnotovu logiku. Akoli se to na prvn pohled me zd t jako odv n rozhodnut, jedin, co mus ud lat, je najt si kus papru a sepsat tabulky pro vrokov spojky! No dobr , k , jak ale zadm, aby po t m logice byla popt vka? V prv ad se mus postarat o to, aby tabulky Tv logiky d valy n jak smysl. Napklad by bylo t k zdvodnit, pro ses rozhodl pisoudit negaci n sledujc tabulku: 3 Autorem prvn ho je rakousk lozof a logik Rudolf Carnap, autorem druh ho je americk jazykovdec Noam Chomsky. Striktn eeno se nejedn o vroky (ty jsou v dy buto pravdiv nebo nepravdiv ), ale o nesmysln oznamovac vty. 4 Pednka z Logiky I, zimn semestr 2002/2003.
3
A :A 1 1 x 0 0 x M lokdo by byl ochoten Ti uv it, e pravdivostn hodnota vroku s hodnotou 1 by se negov nm nem la zm nit, pinejmen m chceme-li se dret pravidla, e vroky s hodnotou 1 jsou nejvc pravdiv (tedy pravdiv) a vroky s hodnotou 0 jsou nejmn pravdiv (tedy nepravdiv). Negac pravdivho vroku by samozejm m l bt vrok nepravdiv a naopak. Pro v echny logick spojky bv nejrozumn j , aby v ppad , e vroky, kter spojuj, maj pouze hodnoty 0 a 1, byly vsledn hodnoty stejn jako v klasick logice. Chce -li si tedy vytvoit vlastn logiku, m la by vzniknout dopln nm t chto tabulek: A :A A^B 1 x 0 A_B 1 x 0 A)B 1 x 0 A,B 1 x 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 x x x x x 0 1 0 0 0 0 1 0 0 1 1 0 0 1 Ov eme toto nejsou v echna omezen, ktermi by ses m l dit, chce -li, aby po Tv logice byla popt vka. Je napklad dobrm zvykem povaovat ekvivalenci A , B za pouhou zkratku za konjunkci implikac (A ) B) ^ (B ) A), take tabulka pro ekvivalenci bude jednoznan urena tm, jak budou vypadat tabulky pro konjunkci a implikaci. V tabulce pro negaci zbv jedin voln msto, podvejme se tedy nejprve na to, jak hodnoty do n j me doplnit. M ti monosti: A :x A :1 A :0 A 1 0 0 0 x x 1 0 0 1 1 1
Cvi en 4. L ukasiewicz si pro svou trojhodnotovou logiku vybral prvn z nabzench negac zjist te,
zda lze :1 A a :0 A vyj dit pomoc symbol : ^ _ ) , } , pro kter L ukasiewicz de noval tabulky.
Cvi en 5. Rozhodni se, kterou z t chto t negac bys zvolil, kdybys pravdivostn hodnot x rozum l v e navrenmi zpsoby. Jakmile se rozhodne pro n kterou z monch negac, me zat vyplovat dal tabulky. Mon jsi se ve kole setkal s dvojic ekvivalenc zn mou jako de Morganovy zkony:5 (A ^ B) m stejnou pravdivostn hodnotu jako :(:A _ :B) (A _ B) m stejnou pravdivostn hodnotu jako :(:A ^ :B) Pokud chce , aby tyto dva z kony platily i ve tv logice, mus na to myslet pi vyplov n tabulek pro konjunkci a pro disjunkci. Konkrtn sta vyplnit tabulku pro jednu ze spojek ^, _ a tabulka pro druhou u je jednoznan urena de Morganovmi z kony. Cvi en 6. Zjisti, jestli Bovarova logika spluje de Morganovy z kony. Protoe chceme, aby v echny spojky byly zobecn nm spojek klasick logiky, meme si pi vyplov n tabulek pomoci tm, e zkusme najt n jak popis chov n klasickch spojek, kter by n m pomohl vyplnit tabulku i pro tet hodnotu. V ppad konjunkce a disjunkce se nejast ji pouvaj n sledujc vyj den: A ^ B m hodnotu 1 pr v tehdy, kdy A i B maj hodnotu 1. A ^ B m hodnotu 0 pr v tehdy, kdy alespo jeden z vrok A, B m hodnotu 0. 5 M sto obvykl ho zpisu (A ^ B) , :(:A _ :B) jsme zvolili slovn vyjden , proto e A , B ve tv logice nemus vyjadovat vztah A m stejnou hodnotu jako B.
4
A _ B m hodnotu 1 pr v tehdy, kdy alespo jeden z vrok A, B m hodnotu 1. A _ B m hodnotu 0 pr v tehdy, kdy A i B maj hodnotu 0. Chov n klasick konjunkce a disjunkce lze popsat i matematicky pravdivostn hodnotu vroku A budeme znait jAj. jA ^ Bj = min (jAj jBj) A ^ B m men z hodnot vrok A, B. jA _ Bj = max (jAj jBj) A _ B m v t z hodnot vrok A, B. Abychom mohli pout toto matematick vyj den, je poteba pravdivostn hodnot x piadit n jakou selnou hodnotu pro na e ely je vhodn hodnota 12 . Cvi en 7. Zkontroluj, e tabulky konjunkce a disjunkce v L ukasiewiczov i Heytingov logice odpovdaj t mto dv ma popism (slovnmu a matematickmu). Jak bys matematicky popsal negaci v t chto logik ch? Nejsloit j je vymyslet tabulku pro implikaci. V historii logiky vzniklo tm nepebern mnostv rznch trojhodnotovch implikac. Pro na e zkoum n fuzzy logiky v p t kapitole bude dleit rozmyslet si, jak bychom mohli matematicky popsat hodnotu vroku A ) B. M me op t n kolik monost: (1) jA ) Bj = 1 jestlie jAj jBj jA ) Bj = 0 jinak (2) jA ) Bj = 1 jestlie jAj jBj jA ) Bj = 1 ; jAj + jBj jinak (3) jA ) Bj = max (1 ; jAj jBj) protoe klasicky plat (A ) B) , (:A _ B)6 Tato vyj den vedou k n sledujcm tabulk m pro implikaci: A)B 1 x 0 A)B 1 x 0 A)B 1 x 0 1 1 0 0 1 1 x 0 1 1 x 0 x 1 1 0 x 1 1 x x 1 x x 0 1 1 1 0 1 1 1 0 1 1 1 Prvn z t chto tabulek je zajmav tm, e pravdivostn hodnota implikace je vdy 0 nebo 1, i kdy do n mohou vstupovat vroky s pravdivostn hodnotou x. Ve druh z t chto tabulek jsi pravd podobn rozpoznal L ukasiewiczovu implikaci logiku s tet z t chto implikac (a negac, konjunkc a disjunkc stejnou jako u L ukasiewicze a Heytinga) navrhl Kleene v roce 1952. Cvi en 8. Vymysli si trojhodnotovou logiku se svou vlastn implikac (nesm to tedy bt Bovarova, Heytingova, Kleenova ani L ukasiewiczova implikace) a ov , jestli v n jsou n sledujc formule tautologick: A)A ::A , A (A ^ B) , :(:A _ :B)
* Bo varova a Kleenova logika z pohledu programtora Pouit Bo varovy logiky
Pokud se zabv programov nm, mohla by T zaujmout tato interpretace Bovarovy logiky: m jme n kolik program, jejich kolem je najt odpov # na rzn ot zky typu ano - ne. To znamen , pokud pustme kterkoli z t chto program, nastane jedna z n sledujcch monost: (1) Program chvilku pot a pak odpov ano. (0) Program chvilku pot a pak odpov ne. (x) Program pot a pot , ale nikdy dnou odpov # nevyd - meme ci, e se zacyklil. Nebo chvli pot a pak se na obrazovce objev chybov hl en, program napklad neme pokraovat kvli nedostatku pam ti nebo protoe se sname uloit slo jako cel slo nebo protoe vol me proceduru, kter neexistuje : : : Programy meme samozejm kombinovat, take pokud u m me programy A a B, nen t k napsat program, kter bude odpovdat na ot zku je pravda, e i A i B daj odpov # ano?. Tento program 6 V tomto p pad plat t jA ) Bj = 1 ; min(jAj 1 ;jBj), co odpov d klasick ekvivalenci (A ) B) , :(A ^ :B).
5
meme oznait A ^ B. Co se stane, polome-li tuto ot zku, ale jeden z program A a B se zacykl? Pokud je n program pro A ^ B naps n tak, e naped pust program A, potom program B a nakonec zjist, jesli ob odpov di jsou ano, zacykl se urit tak. Pr v takto napsan programy popisuje Bovarova trojhodnotov logika mluvme o plnm vyhodnocovn.
6
Pouit Kleenovy logiky
Kleenova logika je urena n sledujcmi tabulkami: A 1 x 0
:A 0 x 1
A^B 1 x 0
1 1 x 0
x x x 0
0 0 0 0
A_B 1 x 0
1 1 1 1
x 1 x x
0 1 x 0
A)B 1 x 0
1 1 1 1
x x x 1
0 0 x 1
A,B 1 x 0
1 1 x 0
x x x x
0 0 x 1
Cvi en 9. Uka, e ani v Kleenov logice neexistuj dn tautologie.
Tak na Kleenovu logiku se meme dvat oima program tora. Program pro A ^ B, o kterm byla e v odstaveku o Bovarov logice, meme toti napsat tak tak, e programy pro A a pro B pob souasn (paraleln ), napklad tak, e se vdy provede jeden krok programu A a jeden krok programu B. Pokud v n kterm okamiku zjistme, e odpov # jednoho z t chto program je ne, je jist i odpov # programu A ^ B tak ne vpoet meme ukonit a nemusme ekat, a dob hne druh program, take si vlastn ani nev imneme, e s m o sob by b el donekonena. Tento zpsob psan sloit j ch program nazv me sten vyhodnocovn. Podobn svou logiku ch pal i s m autor: Kleene s m ov em svou logiku povaoval sp e za parci ln ne za explicitn trojhodnotovou - onu t et monost vedle 1 a 0 povaoval sp e za absenci hodnoty ne za dal hodnotu. lo mu toti zejmna o to, aby ud lil specick status t m aritmetickm vrokm, jejich pravdivostn hodnoty nezn me nebo zn t nememe. Jaroslav Peregrin: Logika a logiky, str. 71.7
Sou inov logiky Vyhodnocovn vce vrok najednou
Pedstav si, e si chce koupit auto. Sep e si tedy seznam v ech vlastnost, kter by m lo mt: cenu do 400 000 K, maxim ln rychlost alespo 250km/h, velk zavazadlov prostor, airbagy pro idie i spolujezdce, zelenolutou barvu, spotebu nejv 5l/100km, otevrac stechu, zamyk n na d lkov ovl d n a ppojku pro karavan. Pi przkumu trhu pravd podobn zjist , e v t ina aut m n kter z t chto vlastnost, ale ne v echny. Mon se proto rozhodne ud lat si pehlednou tabulku, kter Ti umon jednotliv auta srovn vat: trabant mercedes .. .
cena p rychlost prostornost airbagy barva p spoteba stecha p p p p
::: ::: :::
Me tak zkusit zavst pravdivostn hodnoty, kter budou vyhodnocovat vrok toto auto spluje v echny m poadavky. Jednm ze zpsob by bylo pisoudit kadmu poadavku stejnou dleitost a ct, e pro auto, kter spluje sedm z deseti pedpoklad, m tento vrok pravdivostn hodnotu 0 7, zatmco pro auto, kter spluje ti pedpoklady, m hodnotu jen 0 3. Tmto zpsobem ale ztrat mnoho cenn informace o tom, kter pedpoklady auto spluje a kter ne. Jinou monost je zavst pravdivostn hodnoty, kter maj vce sloek. Kad sloka pak bude vypovdat o jednom poadavku. Pro trabant a mercedes dostaneme pravdivostn hodnoty trabant = (1 0 0 0 1 0 0 : : : ) mercedes = (0 1 1 1 0 0 1 : : : ) Zajmavou a uitenou vlastnost tohoto typu pravdivostnch hodnot je to, e pravdivostn hodnotu sloenho vroku lze potat po slok ch. To znamen , e nejprve vyhodnotme pravdivostn hodnotu kadho poadavku zvl - stejn jako v klasick logice - a pak d me tyto pravdivostn hodnoty dohromady. Napklad pohledem do pedchoz tabulky snadno zjistme, e tm ide lnm autem by byl kenec 7
Peregrin oznauje pravdivostn hodnoty P a N m sto naeho 1 a 0.
7
trabantu s mercedesem, protoe vrok m poadavky spluje trabant nebo mercedes m pravdivostn hodnotu trabant _ mercedes = (1 1 1 1 1 0 1 : : : ): Vidme ale tak, e nevhodnou kombinac vlastnost trabantu a mercedesu bychom dostali zcela nepouiteln auto: trabant ^ mercedes = (0 0 0 0 0 0 0 : : : ): Pi interpretaci souinovch pravdivostnch hodnot musme bt velmi opatrn. Napklad jsme vid li, e vysok hodnota vroku trabant _ mercedes nek , e bu# trabant nebo mercedes spluje tm v echny m poadavky ale pouze tm v echny m poadavky jsou spln ny alespo jednm z aut trabant a mercedes. V n sledujc matematick de nici shrme dleit vlastnosti souinovch logik:
1. Pravdivostn hodnoty vznikaj kombinac pravdivostnch hodnot jednodu
ch logik (v na em p-
klad to byla vdy dvouhodnotov logika, ale klidn bychom mohli uvaovat i vcehodnotov logiky: teba barva n jakho auta se mi me lbit (1), nelbit (0) nebo mi bt lhostejn (x)). 2. Pravdivostn hodnota vroku obsahujcho n jakou spojku se pot po slok ch, tedy zvl v kad jednodu
logice, ze kterch se skl d souinov logika. Denice 10. Zvolme si nQlogik Ai (ne nutn rznch). Nech logika Ai m mnoinu pravdivostnch hodnot Pi . Pak souin logik ni=1 Ai m mnoinu pravdivostnch hodnot f(p1 p2 : : : pn ) pi 2 Pi g. Pravdivostn hodnota sloenho vroku se z pravdivostnch hodnot jednodu
ch vrok uruje po slok ch podle pravidel platnch v jednotlivch logik ch. Nic n m nebr n dosazovat na jednotliv sloky hodnoty n kter vcehodnotov logiky. Napklad mru sv spokojenosti s maxim ln rychlost auta mohu vyj dit na estistupov k le (0 - ned se s nm jezdit vc ne edes tkou, 51 - na d lnici bych se musel dret v pravm pruhu, 25 - maxim ln rychlost 110-130 km/h, : : : 1 - maxim ln rychlost pes 250 km/h), spokojenost s barvou auta na tstupov k le (1 zelenolut, 21 - zelen nebo lut, 0 - ostatn barvy) a spokojenost s airbagy na dvoustupov k le (1 m airbagy, 0 - nem airbagy). Je zejm, e n kter hodnoty souinov logiky lze jen t ko porovn vat: je lep auto, kter m airbagy, ale nen zelenolut, nebo zelenolut auto bez airbag? Je lep auto, kter jezd rychle za cenu vysok spoteby, a nebo pomal auto s nzkou spotebou? Proto nebvaj hodnoty souinov logiky uspo dan linern (tj. do ady od nejmen po nejv t ), ale jen sten : auto A, kter je ve v ech aspektech lep ne auto B, je urit celkov lep ne auto B. Je-li (A1 A2 : : : An ) hodnota auta A a (B1 B2 : : : Bn ) hodnota auta B, meme na i vahu shrnout takto: (A1 A2 : : : An ) (B1 B2 : : : Bn ) , pro kad i n Ai Bi :
Cvi en 11. Rozhodni, jestli lze tyhodnotovou logiku z prvn kapitoly s n sledujcmi hodnotami povaovat za souinovou logiku: 1=(1,0): M m dvod si myslet, e vrok je pravdiv, a nem m dvod si myslet, e je nepravdiv. 0=(0,1): Nem m dvod si myslet, e vrok je pravdiv, a m m dvod si myslet, e je nepravdiv. X=(1,1): M m dvod si myslet, e vrok je pravdiv, a m m tak dvod si myslet, e je nepravdiv. ?=(0,0): Nem m dvod si myslet, e vrok je pravdiv, ani dvod si myslet, e je nepravdiv.
Vroky s presupozic
Jednm z nejv t ch o k, s nimi se logikov potkaj ji cel desetilet, jsou takzvan presupozice. Presupozice je pedpoklad, kter mus bt spln n, aby dan vrok vbec mohl bt pravdiv nebo nepravdiv. Teba v ta souasn kr lovna Anglie je star pan je pravdiv , ale v ta souasn kr l Francie je holohlav nen pravdiv , ale ani nepravdiv , protoe to by musela bt pravdiv v ta souasn kr l Francie nen holohlav, ale Francie nem dnho kr le. V ta souasn kr l Francie je holohlav toti obsahuje presupozici Francie m v tuto chvli kr le. Souinov logiky nabzej pom rn elegantn e en tohoto problmu: vrok A s presupozic B budeme povaovat za vrok o dvou slok ch, z nich prvn odpovd presupozici a druh implikaci jestlie je presupozice pravdiv , tak je pravdiv i vrok. Jinak eeno, msto vroku A budeme vyhodnocovat
8
dvojici (B B ) A). Na pkladu francouzskho kr le si uk eme vznam jednotlivch pravdivostnch hodnot: (1,1) Francie m v tuto chvli kr le a tento kr l je holohlav. (1,0) Francie m v tuto chvli kr le a tento kr l nen holohlav. (0,1) Francie v tuto chvli nem kr le (a tud nem smysl pt t se, zda je holohlav). (0,0) Tato varianta nastat neme, protoe implikace s nepravdivm prvnm lenem je vdy pravdiv .
9
Smsice poznmek a citt estihodnotov teologick logika
Pro zkoum n rzn z vanosti pravdivch vrok lze v teologii pout estihodnotovou logiku, ve kter jsou pravdivostn hodnoty interpretov ny n sledovn : 1 logicky pravdiv 4 teologicky pravdiv (pravda na z klad vry) 5 3 fakticky pravdiv 5 2 fakticky nepravdiv 5 1 teologicky nepravdiv (v protikladu s pravdou vry) 5 0 logicky nepravdiv
4 trojhodnotov implikace8
V na em povd n o tom, jak vlastnosti by m ly mt tabulky pro jednotliv spojky, jsme toho o implikaci mnoho neekli, protoe popsat rozumn vlastnosti implikace je o n co n ron j ne popsat rozumn vlastnosti ostatnch spojek. Jednm ze zpsob, jak se dvat na vcehodnotov logick spojky, je tento: existuje jedna vybran hodnota, kter odpovd situaci, kdy vrok je pravdiv. Ostatn hodnoty zachycuj rozdly v dvodech, pro vrok pravdiv nen (je nepravdiv, nesmysln, jeho pravdivostn hodnota je nezn m a podobn ). Jev se jako celkem rozumn poadovat, aby vcehodnotov spojky splovaly n sledujc kritrium: pokud v echny nevybran hodnoty (v na em ppad hodnoty x a 0) nahradme jedinou hodnotou (ozname ji tak 0, k mlce neme dojt), stanou se z vcehodnotovch tabulek tabulky klasick logiky. Na prvn pohled vidme, e napklad tabulka pro negaci :x toto kritrium nespluje: A :x A A :x A A :A 1 0 1 0 1 0 x x 0 0 0 1 0 1 0 1 6= 0 1 ;;;;;;;;;! Vidme, e se v takto vznikl tabulce objevily dv rzn vsledn hodnoty pro pvodn hodnotu 0! Cvi en 12. Ani dn ze ty implikac, o kterch jsme ji mluvili (Lukasiewiczova, Heytingova, Bovarova a Kleenova) nespluje toto psn kritrium! Existuj jen 4 implikace, kter je spluj - dok e
je najt?
11 trojhodnotovch implikac9
Milan Matou ek a Petr Jirk navrhuj n sledujc mn psn kritria pro implikaci (psmena a b c oznauj pravdivostn hodnoty): (1) Pedpokl d me, e 0 x 1 napklad meme ztotonit pravdivostn hodnotu x s hodnotou 21 . (2) Je-li a < 1, potom (1 ) a) < 1. (3) Je-li a < b, potom a ) b = 1. (4) Je-li a < b, potom pro kad c plat (c ) a) (c ) b). (5) Je-li a < b, potom pro kad c plat (a ) c) (b ) c). Cvi en 13. Ov , e klasick implikace spluje kritria (2)-(5). Kter ze ty trojhodnotovch implikac, o nich byla e v textu, spluj tyto podmnky? T chto p t kritri je jednm ze zpsob, jak matematicky popsat klasickou implikaci tak, abychom ji mohli zobecnit na vce hodnot. Matou ek a Jirk d le ukazuj, e existuje pr v jeden ct implikac, kter t mto kritrim vyhovuj. Jsou to: 8 9
Miroslav Mleziva: O trojhodnotov logice, str. 6-11. Milan Matouek, Petr Jirk : Three-Element Implicative Matrices, Miscellanea logica V, str. 85-102. Jirk , slidy 112-113.
10
A 1 1 1 x x x 0 0 0
B 1 x 0 1 x 0 1 x 0
)W )J )3 )A )K )P )4 )Y )H )L )S 1 1 1 1 1 1 1 1 1 1 1
0
0 0
x
x
0
0
0
x
x
x
0 0
x 0
x 0
x x
1 0
1 x
1 1
1 0
1 x
1 1
0 1
0 1
0 0 0
0 1
0 1
x x
0 0 0
0 0 0
0 1
0 0 0
0 1
0 0 0
0 1
0 0 0
0 1
0 0 0
0 1
0 0 0
0 1
0 0 0
0 0 0
0 1 0 0 0
Autory logik s jednotlivmi implikacemi jsou Lewis, Jaskowski, Avron, Kleene, Przymuszinski, Jirk, Heyting, L ukasiewicz, Slupecki. Nen zn mo, e by se n kdo podrobn ji zabval studiem dvou implikac oznaench )3 a )4 . 'tvercov tabulky pro t chto jeden ct implikac vypadaj takto (adme je podle potu vskyt hodnoty x v tabulce hodnoty, ktermi se jednotliv implikace li , jsou zvrazn ny): A )W B 1 x 0 A )P B 1 x 0 A )Y B 1 x 0 1 1 0 0 1 1 0 0 1 1 0 0 x 1 0 0 x 1 1 0 x 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 A )J B 1 x 0
1 1 1 1
0 0 x 1
x 0
A )3 B 1 x 0
1 1 1 1
0 0 x x
1 1
x 0
1 1
A )4 B 1 x 0
1 1 1 1
0 0 1 x
x 0
A )A B 1 x 0
1 1 1 1
x 0 x 0
1 1 x 0
1 1
A )H B 1 x 0
1 1 1 1
x 0 1 0
x 0
A )L B 1 x 0
1 1 1 1
x 0 1 x
1 1
x 0
1 1
A )S B 1 x 0
1 1 1 1
x 0 1 1
x 0
A )K B 1 x 0
1 1 1 1
x 0 x x
1 1
x 0
1 1
Funk n plnost
V povd n o klasick logice jsme si ekli, e v echny spojky lze vyj dit pomoc ) a : nebo teba pomoc ^ a :. Dokonce lze vyj dit nejen spojky _ ) a ,, ale i jakoukoli dal spojku, jej tabulka obsahuje pouze nuly a jedniky. Proto ekneme, e mnoina spojek f^ :g je funkn pln. Naopak spojku : nelze vyj dit pomoc spojek ^ _ ) ,. Vidme tedy, e existuje logick spojka s tabulkou, kter obsahuje pouze dv hodnoty, kterou nelze vyj dit pomoc dvouhodnotovch spojek ^ _ ) ,. Proto ekneme, e mnoina spojek f^ _ ) ,g je funkn nepln. N sledujc tabulky ukazuj v echny jednoargumentov a dvouargumentov dvouhodnotov spojky: A True A : False 1 1 1 0 0 0 1 0 1 0 A 1 1 0 0
B 1 0 1 0
True 1 1 1 1
_ 1 1 1 0
( 1 1 0 1
A 1 1 0 0
) 1 0 1 1
B 1 0 1 0
, 1 0 0 1
^ 1 0 0 0
j 0 1 1 1
0 1 1 0
:B : ) 0 0 1 1 0 0 1 0
:A 0 0 1 1
? 0 0 1 0
# False 0 0 0 0 0 0 1 0
Pipomeme si, e se spojkami j # a jsme se sezn mili ve cviench prvn kapitoly: j je She(erovo lomtko (cvien (?)), # je Peircv symbol (cvien (?)) a je vyluovac nebo ili xor (cvien (?)). V tabulce nalezne i n kolik spojek, se ktermi jsme se dosud nesetkali. Vrok utvoen pomoc spojky True je vdy pravdiv, naopak vrok utvoen pomoc spojky False je vdy nepravdiv. V imni si, e ob spojky mohou bt jedno-, dvou- i vceargumentov, take meme ps t True(A) = A _ :A nebo teba True(A,B,C,D,E) = A _ :A. Meme je dokonce povaovat za bezargumentov spojky:
11
takovm spojk m se k konstanty a lze je pout pi tvorb vrok msto n jakho vdy pravdivho i vdy nepravdivho vroku. Napklad vrok False ) A je tautologi klasick logiky, protoe implikace s nepravdivm prvnm lenem je vdy pravdiv . Spojka :B zna dvouargumentovou negaci druhho argumentu: je to ern skka, do kter strm dva vroky a ona vyplivne negaci druhho z nich: :B (A B) = :B. Pesn de nice funkn plnosti je tato: Denice 14. ekneme, e mnoina k-hodnotovch spojek M je funkn pln, jestlie pro kad p irozen slo n 1 je kad n- rn k-hodnotov spojka ekvivalentn n jak formuli obsahuj c pouze spojky z M. Napklad v ppad klasick logiky je spojka AjB ekvivalentn formuli :(A ^ B), kter obsahuje pouze spojky : a ^. Cvi en 15. Ke v em jedno- a dvouargumentovm spojk m z pedchozch tabulek najdi ekvivalentn formule obsahujc pouze spojky : a ^! Logiky vdy zajm , zda jsou vcehodnotov logiky funkn pln. V ppad thodnotov logiky to znamen , e pomoc spojek zkouman logiky musme um t vyj dit v ech 27 jednoargumentovch funkc (rozmysli si, e jich je opravdu tolik!), v echny dvouargumentov funkce a tak d le! Cvi en 16. Kolik je trojhodnotovch dvouargumentovch funkc? Zd se skoro nemon, e by se podailo n eho takovho dos hnout pomoc rozumnho potu spojek. Proto T jist nijak nepekvap vsledek n sledujcho cvien: Cvi en 17. Uka, e v L ukasiewiczov logice nelze vyj dit jednoargumentovou funkci : A A 1 x x x 0 x O to vc T pravd podobn pekvap v ta, kterou dok zal J. Slupecki: Vta 18. Mnoina spojek f)L :x g je funkn pln . Lidsky eeno: pid me-li k L ukasiewiczov logice je t spojku , dostaneme funkn plnou logiku! Slupecki d le uk zal, e tak trojice spojek )S :1 R je funkn pln R je pitom jedna z t ch spojek, kter pravd podobn nemaj dn snadno vysv tliteln vznam: A RA 1 x x 1 0 0
12
Npovdy, een a poznmky k nkterm cvi enm een cvi en 1 Tabulky pro negaci :A, konjunkci A ^ B a disjunkci A _ B se v obou logik ch
shoduj tabulka pro implikaci se li v jedin hodnot , a to x ) 0 v dsledku toho se tabulka pro ekvivalenci10 li v obou ppadech, ve kterch hodnota jednoho z vrok A a B je x a hodnota druhho je 0. A, B i C mohou mt kad ti rzn pravdivostn hodnoty, celkem tedy existuje 3 3 3 = 27 rznch piazen pravdivostnch hodnot. Pro zji t n, zda je n jak formule tautologi, bychom tedy museli vyplnit 27- dkovou tabulku! Existuje ale o n co rychlej zpsob, jak to ud lat: Zkusme pedpokl dat, e zadan formule (v na em ppad ((A ) B) ) C) ) (((B ) A) ) C) ) C), ale postup je zcela obecn) nen tautologi, to znamen , e pi n jakm piazen hodnot 1, x a 0 vrokm A, B a C m hodnotu 0 nebo x. Zkusme nyn urit, jak ohodnocen by to mohlo bt teba v ppad L ukasiewiczovy logiky. V n sledujcm odstavci je slovy vysv tleno, jak vahy byly potebn k vypln n tabulky pod nm. Zkoumejme nejprve monost, e hodnota tto formule je 0. Protoe se jedn o implikaci (A ) B) ) C implikuje ((B ) A) ) C) ) C, mus bt prvn len pravdiv a druh nepravdiv (v tabulce implikace je jedin 0). Zkoumejme nejprve druh len. Op t vidme, e se jedn o implikaci, jej druh len, toti C, mus bt nepravdiv. Prvn len (B ) A) ) C mus bt pravdiv implikace v tabulce implikace je mnoho jedniek, ale jen jedna z nich se vyskytuje ve sloupeku, ve kterm m druh len hodnotu 0. Z toho meme usoudit, e B ) A mus bt 0, take B je 1 a A je 0. Kdy nyn tyto hodnoty doplnme do implikace (A ) B) ) C, zjistme, e je nepravdiv , akoli jsme ji dve oznaili za pravdivou. To je spor: formule ((A ) B) ) C) ) (((B ) A) ) C) ) C) tedy neme mt pravdivostn hodnotu 0. (( A ) B ) ) C ) ) ((( B ) A ) ) C ) ) C ) 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 Podobnou vahu meme provst i pro oba ppady, kdy m formule ((A ) B) ) C) ) (((B ) A) ) C) ) C) pravdivostn hodnotu x. V ppad , e prvn len je x a druh 0 dostaneme na z klad druhho lenu op t pravdivostn hodnoty pro A, B a C po ad 0, 1 a 0 jak ji vme, m pi tomto ohodnocen implikace (A ) B) ) C hodnotu 1 a ne x, jak bychom potebovali. Doporuuji Ti zkusit prozkoumat ppad, e (A ) B) ) C m hodnotu 1 a ((B ) A) ) C) ) C m hodnotu x samostatn a porovnat svj vsledek s n sledujc tabulkou: (( A ) B ) ) C ) ) ((( B ) A ) ) C ) ) C ) 1 x x 1. monost: (( A ) B ) ) C ) ) ((( B ) A ) ) C ) ) C ) 1 x x 1 x x x Implikace A ) B m bu#to hodnotu x, nebo hodnotu 0. M me tedy ti monosti: A=1, B=x A=x, B=0 A=1, B=0. Ve v ech tech ppadech m B ) A hodnotu 1, take (B ) A) ) C m hodnotu x a ne 1, jak bychom potebovali. 2. monost: (( A ) B ) ) C ) ) ((( B ) A ) ) C ) ) C ) 1 0 x x 0 x 0 0 1 0 x x 0 x 0 1 0 0 1 0 x 0 1 x 0 x 0 1 0 0 1 0 x 0 1 1 x 0 x 0 1 0 0 1 0 x 0 1 1 0,x 0 x 0
Vyzkou eli jsme v echny monosti, jak formuli ((A ) B) ) C) ) (((B ) A) ) C) ) C) piadit jinou pravdivostn hodnotu ne 1 a pokad jsme dosp li ke sporu z toho je vid t, e tato formule 10 T m ve vech logikch, trojhodnotov nevyj maje, je A , B pova ovno za zkratku za formuli (A ) B) ^ (B ) A).
13
je tautologi L ukasiewiczovy trojhodnotov logiky. K tomu, abychom to zjistili, jsme popsali pouze 14 dk tabulky, co dalo o n co mn pr ce, ne vyplnit v ech 27 dk tabulky, abychom zjistili, jestli m zkouman formule ve v ech hodnotu 1. Pedveden postup lze pout v libovoln logice, ve kter urujeme pravdivost sloench vrok pomoc tabulky, tedy i v klasick logice. een cvi en 2 Je-li vrok A pravdiv a vrok B nepravdiv, je implikace nepravdiv (1 ) 0 = 0), ale je-li vrok A nepravdiv a B tak, je implikace pravdiv (0 ) 0 = 1). Proto se domnv m, e pojet hodnoty x jako nevme, zda 0 nebo 1 lpe odpovd L ukasiewiczova implikace, pro kterou plat x ) 0 = x. een cvi en 3 Pokud n jakmu jednoduchmu vroku piadme pravdivostn hodnotu x, bude i libovoln sloit j vrok, kter jej obsahuje, mt pravdivostn hodnotu x. Dky tomu pravdivostn hodnota kadho vroku me bt x, sta prohl sit za nesmysln n jak jednodu
vrok, kter obsahuje. (Zjednodu en se na to me dvat takto: pokud jedna z v t tvocch n jak souv t ned v smysl, pak ani cel souv t ned v smysl.)
een cvi en 4
:1 A m stejnou tabulku jako }:A :0 A m stejnou tabulku jako :A
een a poznmka ke cvi en 5 Ve v ech tech ppadech se jako nejvhodn j jev negace :x . Tato negace se n kdy nazv intern negace, zatmco :1 se nazv optimistick extern negace a :0 pesimistick extern negace. Extern negace odpovdaj pedstav , e kad vrok m pravdivostn hodnotu 1 nebo 0 x znamen pouze to, e tuto skutenou pravdivostn hodnotu nezn me. V optimistick negaci meme vid t tvrzen nen zn mo, e A je pravdiv. Pesimistick negace odpovd tvrzen je zn mo, e A je nepravdiv. een cvi en 6 Jsou-li pravdivostn hodnoty vrok A i B bu#to 0 nebo 1, pot se pravdivostn hodnota sloit j ch vrok stejn jako v klasick logice a platnost de Morganovch z kon tedy nen naru ena. Je-li pravdivostn hodnota n kterho z vrok x, je pravdivostn hodnota libovolnho sloit j ho vroku tak x a de Morganovy z kony tedy plat tak. een a poznmka ke cvi en 7 Nejast ji pouvanm matematickm vyj denm (intern) negace je j:Aj = 1 ; jAj. Optimistickou extern negaci lze vyj dit pomoc j:0 Aj = 1 ; sgn jAj, kde funkce sgn x uruje znamnko sla x: sgn 0 = 0 sgn x = 1 x kladn sgn x = ;1 x z porn Npovda ke cvi en 9 Zvol piazen pravdivostnch hodnot vrokm A a B tak, aby dn z vrok :A :B A ^ B A _ B A ) B A , B nem l pravdivostn hodnotu 1. een cvi en 9 Zvolme-li pravdivostn hodnotu v ech jednoduchch vrok rovnou x, bude tak pravdivostn hodnota v ech sloit j ch vrok x, jak se snadno pesv dme pohledem do tabulek: je-li jAj = x a jBj = x, je tak j:Aj = jA ^ Bj = jA _ Bj = jA ) Bj = jA , Bj = x. een cvi en 11 Domnv m se, e tato logika nen souinovou logikou, a za ni n kdy bv vyd v na. Tak, jak jsou hodnoty oznaeny v zad n, by toti konjunkc vrok A a B s pravdivostnmi hodnotami 1=(1,0) a X=(1,1) byl vrok s pravdivostn hodnotou 1=(1,0) ale m m-li dvod v it, e B nen pravdiv, m m tm sp dvod v it, e A ^ B nen pravdiv. Konjunkci je tedy teba vyhodnocovat jako konjunkci na 1. sloce, ale jako disjunkci na 2. sloce, take nen obvyklou souinovou konjunkc. Je t z van j problm vidm v tom, e negace ve skutenosti prohazuje sloky: negac vroku s hodnotou 1=(1,0) je vrok s hodnotou 0=(0,1), co odpovd souinov negaci, ale negac vroku s pravdivostn hodnotou X=(1,1) je op t vrok s pravdivostn hodnotou X=(1,1), jak dokl d m v 1. kapitole ve cvien (?). Na prvn pohled by se mohlo zd t, e pohled na tuto logiku jako souinovou logiku obh jme otoenm hodnot ve druh sloce: 1=(1,1), 0=(0,0), X=(1,0), ?=(0,1). Pi tomto piazen sloench hodnot pvodnm hodnot m se toti konjunkce skuten chov jako souinov konjunkce (proveden konjunkce na opan hodnoty d v toti opanou hodnotu ne je hodnota disjunkce dky de Morganovm z konm:
14
:(A _ B) = :A ^ :B, take vyhodnocen druhch sloek je tentokr t v po dku). Ale ani pi tomto piazen nebude negace prostou souinovou negac, protoe souinovou negac hodnoty (1,0) je hodnota (0,1), ale negac hodnoty X je op t hodnota X. Npovda ke cvi en 12 Nejprve vypl oznaen polka tabulky: A)B 1 x 0 1 x 0
een cvi en 12 A )1 B 1 x 0
1 1 1 1
x 0
x x 1 1 1 1
A )S B 1 x 0
1 1 1 1
x 0
x 0 1 1 1 1
A )2 B 1 x 0
1 1 1 1
x 0
0 x 1 1 1 1
A )Y B 1 x 0 1 1 0 0 x 1 1 1 0 1 1 1
O implikaci )S je t usly me v souvislosti s funkn plnost. Jejm autorem je logik J. Slupecki. Implikac )Y se zabval souasn esk logik Petr Jirk. Nen mi zn mo, e by n kdo dkladn ji studoval vlastnosti implikac )1 a )2 krom Miroslava Mlezivy ve zmiovanm l nku jsou podezel, protoe pro n plat 1 ) 0 = x, zatmco v klasick logice plat 1 ) 0 = 0.
een cvi en 13
Uv d li jsme si jen jedinou implikaci, kter tato kritria nespluje, a to implikaci Bovarovu. een cvi en 15 Uve#me jen formule pro prvnch n kolik spojek, ostatn lze zskat podobn : False(A),False(A, B), A ^ :A True(A),True(A,B), :(A ^ :A) A,A B,B A _ B , :(:A ^ :B) (A ( B) , (B ) A) , :(:A ^ B) :A (A B) , :A
een cvi en 16
V ech dvouargumentovch funkc je skoro 20 000! Pesn ji, je jich 39 = 19683. Vysv tleme si, pro tomu tak je. U jsme si v imli, e tabulka trojhodnotov dvouargumentov funkce m dev t dk (nebo polek) odpovdajcch devti monm kombinacm t z kladnch hodnot. Do prvnho dku meme napsat ti rzn hodnoty pro kadou z t chto hodnot meme do druhho dku op t napsat ti rzn hodnoty (to je celkem dev t monost, jak vyplnit prvn dva dky) pro kadou z t chto devti monost m me op t ti monosti, jak vyplnit tet dek (celkem 33 = 27 monost, jak vyplnit prvn ti dky). Budeme-li takto pokraovat d l, zjistme, e m me celkem 39 = 19683 monost, jak vyplnit celou tabulku! een a poznmka ke cvi en 17 V echny spojky L ukasiewiczovy logiky maj n sledujc vlastnost: je-li hodnota v ech argument bu# 0 nebo 1, je i hodnota vsledku bu# 0 nebo 1. Ale hodnota funkce je vdy x - tedy i v ppad , e argument m hodnotu 0 nebo 1. Vsledek lze zformulovat i takto: poadovali jsme, aby se na klasickch hodnot ch 0 a 1 spojky chovaly stejn jako v klasick logice. Ov em v klasick logice neexistuje hodnota x, take rozhodn nen mon, aby hodnota n jak formule d vala pro jAj = 1 hodnotu x.
