gheorghe enescu - logica simbolicagheorghe enescu - logica simbolica

of 218/218
Dr. GHEORGHE ENESCU Logica simbolică EDITURA ŞTIINŢIFICĂ. BUCUREŞTI 1971

Post on 13-Aug-2015

341 views

Category:

Documents

26 download

Embed Size (px)

DESCRIPTION

Gheorghe Enescu - Logica simbolica

TRANSCRIPT

Dr.

GHEORGHE ENESCU

Logica simbolicEDITURA TIINIFIC. BUCURETI 1971

PREFATAast lucrare urmeaz crilor noastre Introducere n matematic (1965) i Logic i adevr (1967). Prima era at iniierii cititorului n logica simbolic (n special cuIul propoziiilor i calculul predicatelor), a doua P1: unere original a principalelor prohleme metateoretice ;icii moderne. Rapiditatea cu care ele s-au epuizat din i dovedete n ce msur publicul nostru este interesat menea probleme. De atunci a crescut numrul celor ai (printre ei un mare numt de studeni) i se resimte unei noi lucrri n acest domeniu. Cartea de fa vine lund acestei cerine. n ce raport ee afl ea cu alte anterioare puhlicate de noi (inclusiv cele dou cri)? 'roducerea n logica ma'ematic noi am reintegrat aproape a informaie refuitoare la logica propoziiilor, logica telor i logica relaiilqr (se nelege, cu excepia anumi :aje pe care le-am reprodus aproape fr schimbri, I fost revizuit). Nu au fost reintegrate capitolul intro capitolul de istoria logicii matematice i cel de logic l. Din aceste capitole am extras numai unele informaii. asaje (puine la numr) au fost reproduse din lucrarea i adevr. O serie de studii i articole cu caracter didactic e de noi n revistele "Analele Universitii" "Revista ofie" i "Gazeta matematic" au fost integrate n J.ei reprelucrri adecvate. !mnat cantitate de informaie nu a mal fost expusa lucrri anterioare. Ca arie tematic, lucrarea cuprinde toate capitolele de importan din logica modern.

Prin aceasta cititorul romn va avea n limba sa ideile d baz ale logicii moderne, ceea ce i propune lucrarea de fal Expunerea nu cere din partea cititorului cunotine speciale: Lucrrile utilizate n special au {ost:H i l b e r t, W. A e k e r m a n n, Bazele logicii Ioorf1lice (lucra. cla.ic sub aspect pedagogic); 2. S. C. K l e e n e, Inlroducere in ,,",amalemOlie (lucrare cu caracte: 1. D.!I.

,

A.

enciclopedic, dar imposibil pentru cei ce vor sii se iniieze); C hu r e h, 1nlroducerea n logic. malemalic (carte .pecioasii, dr

extrem de util pentru precizarea anumitor concepte); 4. C. I. L e w i., Lan g fo r d, Logiea simbolic;5. Ja

n L u k asi e li' i cA.C.

z,

SilogiBtica aristolelic din pUndul

4" unde nu e posibil dect un caz (,,2 < 4"). n limba latin pentru " sau" neexclusiv se folosete "vel", iar pentru cel exclusiv "aut" (aut Caesar aut nihil). n rom nete exist o conjuncie popular asemntoare cu "aut" anume "au" ("da au ba?"). n vederea exprimrii excluderii se mai poate folosi " sau" repetat ("sau p sau q") . Sensul lui "sau" neexelusiv este prin urmare acesta : cel puin una din strile de fapt are loc, iar sensul lui "sau" exclusiv este acesta : numai una din strile de fapt (exprimate de propoziiile com ponente) are loc. Exemplele pentru "sau" neexclusiv sint mai greu de dat. Iat nc un exemplu : "n triunghiul ABC, unghiul B sau unghiul C este ascuit". Vom conveni s numim pur i simplu "disjuncie" propozi ia disjunctiv-neexclusiv (sau "alternativ"), iar pe cea exclusiv "excludere". Excluderea o notm cu + i vom scrie "p + q" (citete "p exclude q") . Ca i conjuncia disjuncia poate s se afle ntre termeni sau intre propoziii. Ex. "Unii S snt PI sau P2 sau . . . P,," i "Unii S sint PI sau unii S snt P2 sau . . . sau unii S sint P,,". (Nu in toate cazurile formulrile snt echivalente). n continuare ne vom ocupa de disjuncia (neexclusiv). Reguli de adevr i) Dac disjuncia este adevrat atunci cel puin un membru este adevrat. ii) Dac nici un membru nu este adevrat, disjuncia este fals. iii) Dac cel puin un membru este aqevrat, disjuncia este adevrat etc. Pentru cazul n care, disjuncia este adev rat conform cu regula i) vom avea trei posibiliti (pentru doi membri) : (v v), (v f), (f v). Iat exemple pentru fiecare : "Ptratul este dreptunghi cu toate laturile egale sau romb cu toate unghiurile egale" (ambele componente sint adevrate, deci avem cazul v v). "Orice numr natural n (n 1) este divizibil cu 2 sau este divizibil cu 21" (componentele snt v f). "Orice n\lmr natural este o putere a lui 2 sau orice numr natural n (n > O) este divizibil cu 2" (componentele snt

2

_

Evident, ca ,i in cazul conjunciei ne intereseazi disjunoia Intre G:I:preeii propozitioDale.

29

f, v). Pentru cazul cnd disjuncia este fals putem folosi exemplul : "Qrice numr natural satisface teorema lui Fermat sau orice numr natural infirm teorema lui Fermat" (componentele snt f, f ). Simbolizare. Disjuncia se simbolizeaz prin semnul "V" i se scrie "p V q" (citete "p sau q"). Se mai utilizeaz sem nele " U ", "A" i se scrie respectiv "P U q, A P q". O disjuncie poate avea mai muli membri, ex. "p V q V r V V s". Ea poate fi aplicat i negaiilor, ex. lIP V q". precum i conjunciilor (n care caz se folosesc paranteze), exemplu ,,(p q) V (P r) " , or att negaiilor ct i conjunciilor, ex. ,,(p . q) V (p q)", or i disjunciilor ,,(P Vq) V (q V r) " i ,,(pVq) V r" i p V (q r) etc. Conjuncia i negaia pot fi aplicate disjunciei "p . (q V r)", "p V7' etc. Pentru simplificarea scrierii putem face o convenie : cnd avem o expresie care coninea att conjuncia ct i disjuncia convenim s omitem semnul care ne intereseaz mai puin i s scriem literele (or, expresii mai complicate) una lrig alta nelegnd c ele se leag mai nti ntre ele i apoi cu semnul scris. Ex. n loc de (p . q) V r putem scrie pq V r (omiterea conjunciei) sau (p q)r (omiterea disjunciei). Dac termenii disjunciei snt ordonai : Pl' P2 P,. atunci putem scrie :" "

(unde "L" nseamn suma logic adic disjuncia numit astfel din cauza unor analogii cu suma aritmetic). Disjuncia poate fi aplicat ' i sumelor logice (deci putem utiliza ambele semne) :

Pi = P l V P2 V E ..... 1

n

VA

qj E AV E .-1 j_ l Termenii "produs logic" i "sum logic" snt adesea folosii respectiv n loc de conjuncie i de disjuncie.

n

...

' C9 Propoziii im.plicative. Unele propoziii compuse au tbrma " dac a atunci b" unde "a" i "b" pot desemna o cauz i respectiv un efect (implicaia cauzaI), dou proprieti (implicaia conceptual), o mulime de premise i respectiv30

o mulime de concluzii (implicaia deductiv). Exemple : fropoziia "dac se nclzete termometrul atunci mercurul se urc" exprim o implicaie cauzal ; propoziia "dac poli gonul (euclidian) are trei laturi suma unghiurilor sale are 180 '''' exprim o relaie ntre dou proprieti ("concepte" cum mai denumesc unii proprietile), iar propoziia "dac 21 i 2 1 + 1 atunci 21 1 + 1" este o implicaie 2 deductiv. Indiferent de ce "obiecte" vor desemna "a" i "b" dac propoziiile care se refer la aceste obiecte snt de aa natur c de la prima se poate ajunge prin deducie la ultima noi vom putea spune c avem o implicaie deductiv de la "a" la "b ". Vom exprima aceast implicaie astfel "dac p atunci q" . Prin urmare "dac p atunci q" va nsemna "q se deduce din p" (unde p este condiie suficient pentru q sau q este condiie necesar pentru p) . Membrul "p" (care poate fi la rndul lui o propoziie compus) se va numi ante cedent, iar "q" consecvent.= = =

i) Este imposibil ca o implicaie adevrat s aib antece dentul adevrat i consecventul fals. ii) Dac antecedentul este adevrat i consecventul este fals, implicaia este fals. Pentru implicaia adevrat membrii se pot afla n una din situaiile (v v), (fv), (f f). Exemple. Pentru cele trei cazuri de implicaie adevrat : "dac 20 1 i 1 = 30 atunci 20 3" (vv) "dac 2 12 i 1 2 20 + 20 atunci 2 20 + 20" (f, v) "dac 2 12 i 1 2 01 atunci 2 OI" (ff). Toate aceste trei implicaii snt adevrate n virtutea teore mei "pentru orice (a, b, c) dac a b i b c atunci a = c". Se observ c antecedentul (P) este o conjuncie de dou propoziii (ex. ,,2 1 i 1 = 30 ") . Pentru regula ii) avem exemplul : "dac triunghiul dreptunghic are dou laturi per pendiculare atunci el are dou unghiuri ascuite egale". Este adevrat c "triunghiul (adic orice triunghi) dreptunghic are dou laturi perpendiculare", dar nu este adevrat c "orice triunghi dreptunghic are dou unghiuri ascuite egale". Simbolizare. Vom simboliza implicaia prin _ i vom scrie "p of' q" (citete "p implic q" sau "dac p atunci q" ) . Pentru implicaie se folosesc i alte semne ca =) , ::J. C i se scrie res pectiv p -> q, P ::J q i Cpq.= = = = = = = = = = =

Reguli de adevr

31

e. Propoziii de echiv alen (notate p = q) . Propoziiile de echivalen au forma "p dac i numai dac q". Astfel de expresii pot avea de asemenea mai multe sensuri (printre care i dependena exclusiv a lui p de q) dar noi vom avea n vedere numai sensul : "p se deduce din q i q se deduce din p". Prin urmare echivalena se reduce la o conjuncie de dou implicaii p _ q i q _ p. Exemplu : "Rombul este ptrat dac i numai dac are toate unghiurile drepte" se descompune n "dac rombul este ptrat atunci el are toate unghiurile drepte" (implicaia direct) i "dac rombul are toate unghiurile drepte atunci el este ptrat" (implicaia reciproc). Consideraiile referi toare la sensurile implicaiei pot fi extinse i asupra propo ziiilor de forma "p dac i numai dac q" .

Implicaiei p _ q i corespunde inversa (recipro(!a) q _ p_ Implicaia poate fi aplicat expresiilor fOrIqate prin - , . , V dup cum acestea pot fi aplicate implicaiei. Ex. (pq V r) _ _ r}. Ea poate fi aplicat i unor expresii formate tot cu implicaia : (p _ q) _ r etc.

Reguli de adevr

i) Dac echivalena este adevrat atunci ambii membri snt adevrai (vv) sau ambii membri snt fali (ff). ii) Dac echivalena este fals atunci valoarea membrilor ei difer (vf) sau (fv). Simbolizare. Vom simboliza echivalena prin = llIi vom scrie "p q" (citete "p este echivalent cu q" sau "p dac i numai dac q"). Se mai folosesc semnele, ..... , =, ,... llIi E i se scrie respectiv "p - q", "p = q", "p ,... q", "Epq". Noi vom folosi uneori semnul ,,=" pentru a marca o echivalen logic adev rat. Echivalena poate fi folosit de asemenea n combinaie cu propoziiile introduse mai sus, ex. "p = (q r) ", (p = q) = = p . q) V r)"I= ,,

f. Alte feluri de propoziii. O propoziie interesant este cea de forma "fie c nu p fie c nu q" . Ea este o disjuncie de propoziii negative i poart numele de "anticonjuncie" sau "incompatibilitate". Ex. "Fie c copiii slabi nu Iorm destul fie c nu se pot ngra". Incompatibilitatea se siIQ.bolizeaz prin j i se scrie "pjq" {cite,te : "p este incompatiHil cu q" sau "fie c nu e p.------

'12

fie c nu e q"). Un alt fel de propoziie considerat in logic este cea de forma "nici p, nici q", ea este numit i "antidis juncie". Exemplu : "NicI nu merg la teatru, nici nu rnUn aca s ". Aceast propoziie o vom nota cu "P It" (citete "nici p, nici q"). Pentru a marca o anumit' ilime ne intre "Plq" i "P It" q" putem utiliza, atunci cind le lum in consideraie pe ambele, in locul notaiei "Plq" notaia P /q". Expresia P lq se mai scrie Dpq.

t"

g. Recapitulare a simbolism.ului. Litere p, q, r, sint vari abile propoziionale (desemneaz propoziii adevrate sau false). Semnele - , " V, +, , =, 1, '" se numesc operatori sau functori logici sau conectori. Operatorii de forma N, K, A, C, E, D, au fost dai de Lukasiewicz i ei se supun unor reguli speciale, iar simbolismul lor se numete "scrierea polonez". 2. FUNCII DE ADEVRa. Definiii. n paragraful anterior noi am analizat o serie de propoziii compuse sub raportul informaiei n general i a valorii logice. Formulnd diferite reguli de adevr noi am avut in vdere faptul c adevrul i falsul se raporteaz la judecata (informaia) pe care o exprim propoziia. Dac acum vo m constitui anumite tabele in care vom pune valorile" propoziiilor componente in stinga, iar pe cele ale propoziiilor compuse in dreapta vom obine anumite "distribuii" de:valori specifice fiecrui fel de propoziie compus n parte. Fie regulile de adevr ale implicaiei (materiale). Conform cu aceste reguli vom avea tabelul :

pq I p - qv f v v

vv vf fv ff

Se obeerv c tabelul acesta este structurat dup anumite reguli de coresponden, - fiecrei perechi de valori pentru (p, f) i corespunde o valoare i numai un(pentru p -+ q. (Ex. perechii vv i corespunde valoarea v) .33

Or, prin definiie o coresponden univoc intre dou mu imi de obiecte (nu import de ce natur) X i Y nseamn functie n care X este domeniul functiei, iar Y codomenil O preche de valori ex. (vv) va fi nuit o alegere de valor. " Variabilele (p, q) vor desemna "argumentele" funciei, ia expresia format cu ajutorul operatorilor (ex. p _ q) va 1 numit "expresie funcional". Funcia de mai sus este funcie logic (uneori se spune operaJie logic) in spe o funcli de adevr deoarece este definit pe mulimi de valori logic (i ia valori de asemenea logice). Fiecare funcie de adev poate fi definit fie printr-un tabel (ca mai sus) numit "matrice", fie prin regulile de coresponden (uor de formula pe baza tabelelor), fie pe alte ci. Deoarece in cazul funciilo de adevr intervine presupunerea c pentru a determina valoa rea funciei este suficient s cunoatem valoarea argumentelor presupunere care nu este valabil pentru propoziiile compusI corespunztoare (fr anumite restricii), noi nu vom ma vorbi de aci nainte de propoziii ca valori ale variabilelOl ci pur i simplu de valorile logice (v, f) care vor fi tratate c dou "obiecte abstracte". n conformitate cu aceast procedur abstract vom procedo la reinterpretarea simbolurilor. 1: Variabilele p, q, r, . vor desemna entiti din muli. mea (v, f) in aa fel c nici o variabil nu va dcsemna n acelai timp entitatea v i entitatea f, ci una sau alta. 2. Expresiile constituite cu ajutorul operatorilor (functori lor) , . , y, etc. vor desena de asemenea entiti din mul imea (v, f) n condiiile impuse de regulile de coresponden. Despre ele vom spune de asemenea c reprezint funcii de adevr. Se mai poate considera c p, q, r, reprezint funcii propoziionale care pot s devin adevrate sau false (de exemplu, ecuaii). Funciile de adevr vor purta denumirile propoziiilor cores punztoare : negaie (funcia negaiei), conjuncie (funcia ' conjunctiv), disjuncie, implicaie numit i "implicaie mate. riaI," echivalen etc. Expresiile p, p q, p y q, p _ q, p q etc. se citesc a cum s-a artat mai sus . Definiii. Conceptul de "funcie de ade.vr" se generalizeaz n aa fel nct variabilele vor desemna ele nsele funcii (funci. . . . . =

34

.... lrIIlative), iar ulterior vor fi incluse i alte feluri de funcii 4let cele de mai sus. Un mod simplu de a defini funciile este prin tabele (,,,matri a") . Iat aceste definiii prin matrice :

" I liI "

I

tItI "1 Iti I I

pq Ipoq pq \pVq pq I p-q pq I p = q pq I p+qti I f I tItI "1 1" I I ti ti ti I "1 Iv I I

WIti

pq

v

tiI Iv I I

"ti

I Iv

ti

"1 Iti If

tIIJ

I ti

/P/qf ti \1

I

"

fJl IfJ f i

vv

ti

in stnga sint date valorile posibile ale argumentelor iar n dreapta valorile corespunztoare ale funciilor. Funciile pot fi apoi definite pe baza regulilor de corespon den care pot fi formulate pe baza matricelor indicate. Exem plificm pentru conjuncie : i) Dac p este v i q este v atunci p q este v ; ii) Dac p este v i q este f atunci p q este f; iii) Dac p este f i q este v atunci p q este f; iv) Dac p este f i q este f atunci p q este f. (Analog pentru celalte funcii). Se pot da ns definiii mai scurte i chiar mai generale dect cele date prin matrice. (1) Numim nega/ie funcia a crei valoare este v atunci cind argumentul are valoarea f i f cnd argumentul are valoa rea v (deci funcia a crei valoare este invers argumentului ei). (2) Numim conjuncie funcia care este adevrat atunci i numai atunci cnd toate argumentele ei snt adevrate. (3) Numim disjunc/ie (alternativ) funcia care este fals atunci i numai atunci cnd toate argumentele ei sint false. (4) Numim implicaJie funcia care este fals atunci i numai atunci cnd antecedentul (P) este adevrat, iar consecventul (q) cste fals. (5) Numim echivalen funcia care este adevrat atunci i numai atunci cnd toate argumentele au aceeai valoare (sau toate adevrate sau toate false). (6) Numim excludere funcia adevrat atunci i numai atunci cnd numai un argument are valoarea adevir.o o o

35

(pentru disjuncia neexclusiv se poate da i urmtoare definiie care poate fi comparat cu definiia excluderii : dU juncia este adevrat atunci inumai atunci cnd cel pui un argument es\ a,devrat): "" (7) Numim incompatibilitate funcia fals atunci i Jluma atunci cnd ambele argumente snt adevrate. (8) Numim antidisjuncEie funcia adevrat atunci i numa atunci cnd toate argumentele snt false. Dac condiiile (2) -(8) nu snt satisfcute, funciile vo avea valoarea invers celei prescrise n definiie. b. Unele proprieti ale funciilor de adevr. In continu are vom studia proprietile denumite comutativitate, asociati vitate, distributivitate, idempoten, reflexivitate i tranzitivi tate. Fiecare din aceete proprieti se exprim ntr-o "legt logic". Conjuncia i disjuncia snt comutative, adic valoa rea lor nu depinde de ordinea termenilor.

Aceleai snt asociative, adic valoarea lor nu depinde de gruparea- termenilor.

(I) p . q == q .p (2) P V q == q V P

Conjuncia i disjuncia snt distributive una fa de alta.

(4) P

(3) p . {q . r)

(p . q) . r V (q V r) = (p V q) V r=

(5) p . (q " y r) == (p - q) V (p . r) (6) p V (q . r) = (p V q) . (P V r)Semnul = nseamn logic echivalent, ceea ce este mai mult dect simpla echivalenii ( =). Ori de cte ori are loc echivalena logic are loc i simpla echivalen (reciproca nu este adev rat). Tocmai de aceea n loc de == putem scrie = dar invers nu ntotdeauna. S considerm unele exemple. Conform cu (1) este tot una dac spunem "ptratul este dreptunghi i ptratul are toate laturile egale "sau" ptratul are toate latu rile egale i ptratul este dreptunghi". Pentru (2) putem con sidera dou ipoteze, va fi indiferent n ce ordine le formulm : "x este bolnav de nervi sau x este bolnav de cancer" este logic36 j

-mvalent cu "x este' bolnav de cancer sau xeste Bolnav de .-vi", Pentru (3) fie o serie de ipoteze medicale. Medicul.firm : a) X are C8I'Cer i b) X are hepatit

Cu alte cuvinte pe lng cancer X mai are cel puin una din ttle dou holi. Nu influeneaz rezolvarea problemei dac ..edicul o va formula astfel : a ) X are cancer i hepatit sau b) X are cancer i ulcer. Pentru (4) analog mediul afirm : a ) X are cancer sau b) X are ulcer i hepatit. Ipotezele pot fi reformwate astfel : a) X are cancer sau ulcer i b) X are cancer sau hepatit. Conjuncia i disjuncia snt idempotente, adic,

lilJI1X are ulcer.

(8)

(7)

p .p = P

P V P = p.

Implicaia i echivalena snt reflexive i tranzitive :

(9) P( 1 1) (12j

p

-fo

P=

-fo

P = P (reflexivitate) q) . (q -fo r)) -fo (p -fo r) - ,1mtJJJknkJe.(10)q) . (qL=

PI

r)) (P) ,

=

Formulele (9), (10) snt legi ale identitii, iar (11) i (12) Irgi ale tranzitivitii, analog (1) -(8) poart denumirea proprietii respective (ex. "legea comutativitii" etc.). Tran sitivitatea implicaiei poate fi exemplificat astfel : "Unele aDiamale snt oameni" se deduce din "Toi oamenii snt ani .ale", "Unele animale nu snt non-oameni" se deduce din .,Un'ele animale snt oameIii" prin urmare ea se deduce i din _Toi oamenii snt animale". Tranzitivitatea echivalenei poate fi exemplificat pe baza transformrilor echivalente : , ., 2x + 3 = 5" .1 se transform n , , 2x 5 3 ". Iar aceasta n . ,2 x = 2" prin urmare ,,2x + 3 5" este '1 fthivalent cu .,2x = 2".= =

)

r)

J

37

Exist i alte proprieti care vor fi introduse ulterior o dat cu indicarea principalelor legi logice. c. Relaii de echivalen ntre expresiile logice. UneI expresii funcionale snt echivalente cu altele prin definiie Astfel p -+ q poate nsemna "nu este adevrat p (sau altfel este adevrat q", adic p y q . La rndul ei echivalena este o conjuncie ntre implicaia direct i cea invers (reciproc) (P -+ q o q -+ P ). Aceasta nseamn c n exprimare ne putem dispensa uneori de anu mii operatori definindu-i prin alii. Putem alege diferii operatori de baz, restul reducndu-se la acetia prin definiie. Desigur, nu orice grup de operatori poate constitui o baz pentru toi ceilali. Iat cteva posibiliti ( ) , ( y, ) ( -+ , ), ( o , V, ) (f), ( ). Grupul ( o , y, ) formeaz grupul de operatori al aa-numitei "algebre booleene". Ne vom opri tocmai asupra acestui grup. Iat definiiile corespunztoare ale restului operatorilqr.

-

-, -

o ,

-

-,

( 13) ( 14) (15)

P q = p y q, P/q' = p y q, P + q = pq y pq

-+

(1 6) P = q = pq o qp ( 1 7) P / q = p o q,

Nicod a redus toate expresiile funcionale la exprimarea doar cu ajutorul operatorului / (denumit i operatorul lui Sheffer).

Functorul este de asemenea suficient pentru a-i defini pe toi ceilali prin el. d. Tabelul funciilor bivalente. La ntrebarea cte funcii neechivalente putem construi pornind de la n variabile putem rspunde cu ajutorul egalitii : " N = mm unde m = numrul de valori logice admise iar n numrul de variabile.38

( 19) (20) (21) (22)

(18) p = PtP

(23) p Y q = (P/p) q/q) o = p ), p q (P/q)/( /q (24) P -+ q = P/(q/ P + q = ({P/(q/q))/(q/{P/q))) P = q ,= ({P/(q/U))/(q/{P/P) ) /({P/ (q/q))/q/{P/P))) P q = (P/P)/(q/q) / ( {P/P) /(qq

/ 'f)

(F aecare funcie va ..meric).pq lvv

Dac m = 2 (adic v, f) i n = 2 (adic p, q) vom avea fi" = 1 6. Aceste 16 funcii pot fi reprezentate ntr-un tabel.fi

notat apoi prin fi unde i este indice

--r-1 V ") P 6 = 2 3 4 75v V v v v V v v v v v V

:v

/ +- 9 10 1 gf f f fv v v v v v

14

15f f fv

16f f f f

ti fv ti

f

f

v

f f

f

V

f f

V

v v

v

f f

v

f f f

f

v v v v

f

v

f

'("DeIe din funciile din acest tabel au fost deja studiate :

12 = P V q, /, = (P

=

p, /Ij p, /5 P -+ q, /6 q, q) , /e p . q, /9 = P/q, 110 P + q, fn = ij, 113 fi, f15 P ,/ q-+= = = = = =

fa = q

estudi!lte snt nc funciile h, .h2' .h4 i .ha. Funcia h poart numele de "lege logic" sau "tautologie" u "funcie identic-adevrat" sau "identitate logic". ! Funcia h2 este negarea implicaiei, .h4 este negarea implica. i inverse, iar ha este contradicia (funcia identic-fals). general funciile pot, conform cu acest tabel, s fie elasi te n trei categorii : legi logice (tautologii), contradicii i cii realizabile. Iat definiia fiecreia din cele trei. Nuim lege logic funcia logic adevrat independent de valori iau argumentele sale (din mulimea (v, f) . Numim contradicie acea funcie logic fals independent ce valori iau argumentele ei din mulimea (v, f). Numim funcie realizabil funcia logic adevrat cel puin -un caz. De observat este c n tabelul de mai sus funciile snt opuse etric fa de jumtatea tabelului (h este opus lui h6' lui hs etc.), adic fl+" = ha." (unde n O, 7). De aci urge c unele funcii pot fi echivalate cu negaia altora i i c putem opera o reducie a exprimrii. Din tabel decurge diat c n loc de 16 funcii putem utiliza 8, iar restul s introduse prin definiie cu negaie a celor 8. Vom vedea=

39

c O asemenea reducie joac un rol fundamental n logic. i c ea st la baza transformrilor calculatorii din aceasti tiin. L3. PROBLEMA: D ECIZIEI

Problema fundamental a logicii simbolice este problema deciziei. Aceast problem ee formuleaz n felul urmtor : fiind dat o expresie logic 'iii s se decid dac ea reprezint o lege logic (tautologie), o contradicJie sau este o funcie simplu Aceast problem poate . zolvat rin mai multe mijloace din care ami ri eli.minarea tre .tat - necunoscute lor ; b) prin c) pe baza Elimi ma nareattrepH,t a necunoscutelor se face pe baza JlW!t ranae. a n vederea deciderii p e baza unor raionamente preacur t e este necesar s reinem cteva reguli mai importante care decurg din tkfiuitia funciilor de adevr. - R1) Dac u.ii membru al conjunciei este fals, atunci conjunc ia va fi fals ; Rz} Dac un membru al este adevrat atunci -!!,loarea ei va depinde de es '!.-.membrilor ; este adevrat, disjuncia "" Ba) Dac un membru a va fi adevrat ; R,) Dac un membru al disjunciei este fals, valoarea ei va epinde de relitul membrilor ; . , R6) Dac nsecventul impei este adevrat, implicatia a fi adevrata; Re) Dac antecedentul implicaiei va fi fals, implicaia va i adevrat ; R7) Dac con ei va fi fals, implicaia va epinde de antecedent ; Re> Daci antecedentul implicaiei va fi adevrat, valoarea e consecvent ; Implicaiei va depinde a Ha) Dac un membru al incompatibilitii va fi fals, incom patibilitatea va fi adevrat ; RlQ) Da c un membru al incompatibilitii va fi adevrat, valoarea incompatibilitii va depinde de cellalt membru ;

realizabil.

V

,..

:

40

Ru) Dac un membru al antidisjunciei este adevrat, _tidisjuncia va fi fals ; R12) Dac un membru al antidisjunciei va fi. fals, valoarea n va depinde de ceilali membri. Exemplul 1. S se decid prin raionamente bazate pe ftgulile indicate asupra expresiei (p -+ (p + q V p. Se observ c dac presupunem c p este fals, p va fi ,ade Tirat (conform cu definiia negaiei) i deci toat disjuncia 'Q. fi adevrat. Dac ns p este adevrat atunci p va Urfala i deci conf. cu R, valoarea va depinde de cellalt membru. Vedem deci ce se ntmpl in continuare cu cellalt membru .mnci cnd raionm mai departe n virtutea lui p este ade Tirat. Dac p este adevrat p -+ (p + q) va depinde conform cu Re de p + q. Deoarece p este adevrat, exchiaerea Ya depinde de q. Presupunem n continuare c q este adevrat, Uunci excluderea va fi fals (deoarece p a fost deja presupus n adevr!!t), implicai a va fi fals (Ra)' iar disjuncia va fi fals (ambii membri snt fali). Dac q va fi fals, p + q va fi adevrat, implicaia adevrat, i disjuncia adevrat. Prin vmare, deoarece disjuncia este numai ntr-un caz adevrat, n nu reprezint o lege logic (nici o contradicie), CU) fje..Procesu de maI sus poate fi prezentat mai pe scurt dac Tom proceda ntructva analog cu modul n care se rezolv KUaiile n algebr punnd constantele n locul variabilelor li aplicnd "regulile de operaie". acest scop este chiar mai comod s utilizm pentru con IIlantele tJ, f semnele cifrice 1, O. Mai mult, ele ne vor ajuta a utilizm i alte analogii cu algebra. eon"enie. 1 == v, O :!!:= f. (Adic 1 va desemna adevrul. O va desemna falsul). Toate tabelele vor putea}i refcute conform cu aceast convenie. De exemplu,

!pJjzeb

fI

aceast convenie :p.u se transform logica n aritmetic ci se obin avantaje n mnuirea limbajului i n intro rea unor procedee de lucru ce in de exprimarea cifric.41

-;fI f

p

Ipv

devine

p O

Ip1

Io

Notnd apoi expresiile logice cu A, B, C, . putem da o formulare mai concis regulilor de mai sus, substituindu-l un ir de echivalene..

R1) A . 0 = 0, RII) A - l = A, Rs) Ay1 = 1, R.) AyO = } R6) A 1 = 1, Rs) O - A = 1, R7) A - O = A Ra) 1 -A=A ; Re) O/A= 1, RlO) l/A A, Ru) 1 .t' A O Ru) O.t' A=A, R18) 1 + A = A, O + A = A, Ru) (1 = A) A, (O = A) A.-+ = = ==

=

Revenim asupra exemplului 1. Sup. p

Sup. P cellalt membru. Continum deci raionamentul asupra aces tuia, punnd valoarea cunoscut n locul variabilei P , ( 1 -:1 _ (1 + q) . Valoarea implicaiei depinde de 1 + q, iar 1 + de ipotezele in legtur cu q. Sup. q = 1. Conci. 1 + q = O, 1 -O = O, disjuncia va fi O. Sup. q = O. Concl. 1 + q = 1 , 1 _ 1 = 1, disjuncia va fi 1 . O nou prescurtare s e poatt obine dac aezm ipotezele (supoziiile) i concluziile um dup alta fr comentariu dezvoltat. Sup. p = O. ConcI. p 1 i P Sup. P = 1. ConcI. p = O ; (1 Sup. q = 1. ConcI. (1 - (1 + Sup. q = O. Concl. (1 - (1 +=

= O. = 1.

Concluzii

P = 1 i (P - (p + q)) Y P = 1 Concluzie p = O. Disjuncia va depinde d.

-+

(P ++

q) Y 1

=

1+

- (1

q)) V O = (1 (1 - O)- 1)

q) V O

=

1

+ q

1)) Y O

=

YO

=

O YO = O=

O)) V O = (1

VO = 1 VOp

1.

Prin urmare, dei adevrat, intr-un caz, expresia noastr nu e adevrat n toate.

ExemplulSup. p. Sup,=

= 1. Conf. cu R6 expresia este adev. p = O. Aplic R7 U V (q.r) - O = 1 v(q.r) - O ==

2.

S se decid asupra expresiei

y (q . r) - P

1 -0

0 _0

=

1.

Este deci suficient s facem ipoteze asupra lui p pentru a elimina toate necunoscutele i a decide. Expresia este o lege logic. Exemplul 3. S se decid asupra expresiei (P - q) _ r V s. Sup. P O. ConcI. (O - q) - r v s = O - r v s = 1. Sup. P 1. Conci. (1 - q) - r V s q - r V s. Mai departe trebuie s facem noi supoziii n vederea elimi nrii necunoscutelor. Sup. q 1 O. ConcI. O - r V s Sup. q 1 ConcI. 1 - r V s r V s Avem din nou nevoie de supoziii. Sup. r 1. ConcI. 1 _ 1 V s = 1 _ 1" = 1 - O O.= = = = = = =

Sup. pentru Sup. Sup.

rS

=

=

=

O. ConcI. 1

_ Ovs-f=

=

1 -s.

Din nou supoziii ,

s.

s

==

O.

1.

ConcI. 1 ConcI. 1

_O -O= 1 _ 1

1

= =

O

1.

Deoarece rezultatul eliminrii lui p este ntr-un caz 1 , iar rezultatele restului eliminrilor este o dat O i o dat 1, avem de a face cu o funcie realizabil. b. Metoda m.atricelor. O metod foarte simpl de rezolvare este metoda matricelor. Ca i n cazul matricelor unei funcii se aaz n stnga tabel ului sus argumentele (p, q. r . . . ), se descompune expresia n expresiile componente din ce n ce mai simple pn se ajunge la variabile, se aaz n dreapta expresiile n ordinea complexitii crescnde i se decide asupra lor pe rind n funcie de datele anterioare pn ce se obine soluia expresiei date. Exemplu 1. S se decid asupra expresiilor.

(q - P) b) Cp V q) - q c) (p - q) - (P - q) V (p - qj d) (p V q) = P V qa

)

p _

II J

pq0111 10

q -p1 O O O

/" p - (q -P)1 O 1 1

b)

11 10 01 00

fiO O 1 1

I pVq I1 O 1 1

( PYq)1 1 1 O

->

00

-)

pq11 10 01 00

qO 1 O 1

/ p - q / p - q / (P - q) V (P-q) / (P -q) - ((P - q)V(P -qn1 O O O O 1 O O 1 1 O O

4)

pq11 10 01 00

pVq pVq1 1 1 O O O O 1

/

I

1 1 1

pVq

=

PVq

O O O O

Prin urmare, a) i h) snt funcii realizahile, c) este o funcie identic-adevrat (lege logic), iar d) este o contradicie. Dei foarte simplu, procedeul matricelor devine practic inutilizabil pentru mai mult de trei variabile.

Exemplul

2.

a) ((p V q) - (qb) P - (p V q)

V r))

-+

(p

-+

r)

=

P V (p o r)

011 001

111 1 10 101 100

O O o o

010 000

1 1 1I

o O 1 1 o o 1

1 O o

1

1

1 I

1 1

1 O 1 1 o 1 1

1

1 O 1 o

I 1

1 1

1 O o o O 1 1

1

.1 I 1

1 1

44

pQI'11 1 1 10 10 1 1 00 01 1 010 001 000

1

pVq1 1 1 1 1 1 O O

I

per1 O 1 O O O O O

I

PV(P 1 1 1 1 O O O O

PV(p e r) O O O O 1

I

p e (PVq)

=

PV(P e 1')

O O

O

1

1 1

O O O O O

Prin urmare funcia a) este o lege logic, iar funcia b) este contllldicie.c.

Metoda formelor normale. Pe baza- relaiei de echiva

len logic ntre anumite expresii noi putem efectua operaii de transformare echivalent n virtutea unor reguli logice. Tre cerea de la o expresie logic la alta echivalent cu ea n virtu tea anumitor reguli logice ne d posibilitatea s decidem asupra unor expresii pe baza altora. Pe de alt parte, despre valoarea unei funcii putem decide n anumite cazuri dac inem seama dc o serie de corelaii ntre anumite proprieti structurale ("sintactice") i cele de valoare ("semantice"). n general vorbind, din anumite proprieti structurale ale

unei expresii noi plltem conchide la alte proprieti. Se impune, deiigur, ca proprietatea dat s fie univoc reprezentat de o roprietate structural a expresiei. -Asemenea expresii care au anumite proprieti structurale in care noi putem conchide existena altor proprieti pentru

expresia dat i pentru orice alt expresie echivalent cu e a se numesc expresii "canonice" s a u , ,,normale". Dac i n arit1 2 4 8 . metica se cere ca din lru I d e fracll = - = 6 3 12 24 s s e aleag fracia care va reprezenta univoc pe oricare din mnlimea fraciilor considerate atunci noi va trebui s gsim.. - < = = --

J

-

o aiemenea fracie care are anumite proprieti ce nu mai aparin altei fracii din mulimea considerat. O astfel de fracie este aceea care are proprietatea de a fi ,,ireductibil",

tn callul nostru

Prin urmare, dac o fracie !!.- este ireduc3 b tibili, noi putem spu.ne c ea reprezint univoc toate fraciile din mulimea considerat.

.

"\ n lic exist expresii de o structur tip la care pot fi reduse prin trail sTormat-eC1iivaiente alte ex resii i care (lato or

Definiii (1) Numim termeni primi variabilele i negaiile lor (P , q, r, . , p, q, r, . . . ) (2) Numim conjuncie prim orice termen prim i orice conjuncie de termeni primi (ex. p , q, p . q, p . q .) (3) Numim disjuncie prim orice termen prim i orice dis juncie de termeni primi (ex. p, q, p V q , P V q , . . . ) Din aceste definiii decurg unele concluzii importante cu privire la conjuncii i disjuncii : a) se admite i cazul cnd avem conjuncii (resp. disjuncii) cu un singur membru, b) n anumite cazuri una i aceeai expresie poate fi tratat ca membru al unei conjuncii cu un singur membru sau ca membru al nnei disjuncii cu un singur membru. Se poate de asemcnea vorbi de conjuncii i disjuncii cu o mulime vid de argu mente. Conjunciile (resp. disjunciile) cu un singur merpbru pot fi tratate ca avnd restul membrilor vizi. (5) Numim form normal conjung, CjlDj}lDcia oricrlJi multimi de disjuDctii prime. (6) Numim form normal disjunctivji disjuncia eriet:eL. multimi de coD)Uiictii prime. Cazuri intercsante. Termenii primi vor fi att forme normale onjunctive ct i forme normale disjunctive, la fel conjunciile prime i disjunciile prime. De i resp. p q , p V q, P V q , exempl u, p, q , r, p, q, r, p . q, . . . Cnd n calcul se introduc i constantele 1 (adevrat) i O (fals) noiunea de form normal se generalizeaz i in raport cu aceasta-o n funcie de un alt limbaj formele normale pot primi i alte definiii.. . .

Vezi lucrarea noastr "Introducere tn logica matematici" (p. 56- 57, 60-61).

46

l'e t

Expresiile "p V q, (p . q) V r, P V (q r), p (q V p) snt ' forme normale, dar expresiile p ... q, p . q, p V ij, P (q P), p V (q V r) nu snt forme normale, deoarece nu satisfac proprie tile de mai sus i, se nelege, nici definiiile date. Deoarece orice expresie poate fi transformat, pe baza anu mitor reguli, n expresie de form normal echivalent cu ea, dat ce am decis asupra valorii formei normale am decis i u privire la orice alt expresie echivalent ei., (7) Clasa tuturor expresiilor echivalente cu o expresie dat poart numele de "clas de echivalen". De aci decurge c a decide asupra formei normale nseamn a decide asupra cli echivalente' 1 _ e. CUIIl se decide cu ajutorul formelor normale? Mai nti stabilim dou corelaii iniiale ntre proprieti struc turale i valoarea logic. I a) Expresia de forma )\, V este totdeauna adevrat (lege logic). b) Expresia de forma A este totdeauna fals (contra-;.4 11cle ). .1 " I Aceste dou propoziii pot fi demonstrate pe baza matricelor. J. i A = O. Pe de Prin urmare, putem scrie alt parte, A V poate face parte dintr-un membru disjunctiv (membru al unei conjuncii) iar A parte dinlr-un membru conjunctiv (membru al unei disjuncii). Fie (X y A Y o dis junce unde (X reprezint restul membrilor. Conform cu A V A = 1 i cu echivalena A V 1 = 1, vom avea (X V A V V = (X y l = l. Fie (X A o conj uncie unde CI. reprezint restul membri O i cu echivalena A O = O, vom lor. Conform cu A A

d. Proprieti ale formelor normale O propriette gene ral a formelor normale const n aceea c ne atia cade numai pe variab!!s( O alt proprietate const n aceea c operator da denumirea form L (conjuncia, respectiv ? i juncia) nu !1re nJP;m D;;;' ;eSjej, "'l'rin definiie, se inelege c tii LrmeJe normale nu apar ali operatori dect V, - .

a::!,

: p

l

r

r \

\-vA-== )

=

avea IX . A = IX O = O. De aci se deduce c dae o conjuncie este format numai din membri de forma IX V A V fiecare membru al ei va fi adevrat i deci toat conjuncia va fi adevrat i dac o disjuncie este format numai din membri de forma IX A fiecare membru al ei va fi fals i. deci toat disjuncia va fi fals (se presupune c n ambele cazuri IX poate fi, i vid). De aci decurg urmtoarele criterii (n fond, teoreme) de decizie n formele normale : 1. Dac n fiecare membru al formei normale conjunctive este coninut o expresie de forma A V atunci forma nor mal reprezint o funcie identic-adevrat (lege logic, tautologie ). 2. Dac n fiecare membru al formei normale disjunetive este coninut o expresie de forma A atunci forma nor mal reprezint o funcie identic-fals (irealizabil, contra dicie). 3. Oricare expresie din clasa de expresii echivalente cu forma normal respectiv va avea aceeai valoare ca i forma nor mal. 4. Pentru a decide asupra valorii unei expresii este suficient 8-0 aducem la forma normal, dac nu are loc nici cazul 1, nici 2, atunci avem o funcie realizabil.

f. Cum. se aduce la f'orm.a Dorm.al o expresie? a) Dac exist operatori care nu trebuie s apar in forma normal i eliminm conform cu definiiile date mai sus. Ex. n loc de A B vom pune V B, n loc de AlB vom pune ....-.A . B ete. b) Dac negaia nu cade pe variabile o coborm conform cu regulile :(bl) A se nlocuiete cu A, (ba) A V B se nlocuiete cu A . ii (adic conform cu legea dublei negaii i aa-numitele legi ale lui de Morgan). (c) Dup efectuarea operaiilor conform cu (a) i (b) adueem expresia la frma normal dorit pe baza regulilor de asocia': tivitate i ;;;' stribuitivitat Ordonarea membrilor se poate face pe bazo comunicativitlli (b2) A . B se nlocuiete cu A V i

lt

48

ta> ({P - q) . (q _ r _ (p - r), (b) P - ( q-P), (c) (J .q) = p, (ci) (P fq) (qfP) Rezolv prima expresie. (. P - q) (q (P - r)Trebuie s eliminm operatorul implicaiei.

Eumple.

S

se

aduc la forma

normal expresiile

- p)

p V q )

(q V ,,) V Cii V r)

Coborm negaia pe variabile conform cu regulile .(b1) -(b3).

(p V q) V ("q V f/V P V r ti. V p V r (p q) V (q . i1 V p V , -

(i> q) V (q

Se observ c aceasta este o f.n. disjunctiv. Conform cu criteriul de decizie ea nu reprezint o contradicie i deci epresia iniial (echivalent cu ea) nu exprim o contradicie. \ Pentru a ajunge la f.n. conjunctiv tnbuie s distribuim de cteva ori disjuncia fa de conjuncie. ! Putem pentru simplificare s scriem e::iC'presia fr semnul disjunciei (p q) (q pr,. Di tribu vom lia o putem nc'1' e u partea (q ', 1iJ P , dic _ . ('fi . ) prq . pr . . p, fa de q . ,. I distrIbuI vom obIne q( Distribuim apoi (P q) fa de prq prfui obinem .

pe p rjiJa de p q, obinem : prqp prqq prpp prP-ii, ceea ce este f.n.c. Se vede c n fiecare membru este coninut o expresie de forma A V , adic n primul p V p, in al doilea q V q, n al treilea p V p, n al patrulea p V p. Prin urmare, avem o lege logic, iar expresia (a) este i ea o lege logic. n continuare vom pune formulele una sub alta fr a indica operaiile.i

q2 . ((PC-- p) Distribuim n continuare p rq fa de p q,((Pr

_

_

(b) p - (q - P)

P V (Q V P )

p . (q V P)

p . (q . p) p . (q . li) p.q.p

49

Ultima expresie p o q o P poate fi tratat att ca form nor mal conjunctiv cu membrii p , q , P ct i ca form normali disjunctiv cu un singur membru (P q o P). n aceast ultimi calitate se vede c ea conine n unicul membru o expresii de forma A o (adic aci p o p. ) ceea ce nseamn c repre zint o contradicie i deci c (b) este o contradicie.

o

(c) (P o q) implicaii)

p o p q) P ) (P -+ (P o q)) (descompunerea echivalenei r:=

o

PiiP o pp o pq

(P o q V P) o (iv (P q (P V ii V P) o (P V (P o qo

Aceasta este o f.n.e. Funcia reprezentat nu este lege logic. Vrem s vedem dac este contradicie, deci o aducem la f.n.d. Reintroducem semnul disjunciei.

(P V ii V P) (iP V pq V pp V pq) (P V ii VP)PP V (P V ii V P)pq V (P V ii VP)PP V (P V ii V P) pq PPPVPPiiVPPP VPqPVPqii Vpqp VPPPVPPii VPPP Vpqp V V Pqii V pqp .

(P V ii 'l P) (P V P) (P V q) (P V ii V P) ( p V q)P V Cfi V q)P)

.!

'-

Se observ c nu exprim o contradicie. De remarcat este c n aceast formul o serie de membri se repet. Contiorm cu legea A V A A (idempotena) noi i putem reduce fr a influena nici valoarea expresiei, nici procesul de decizie.=

(d)

P/q o q/P p o q o q op

zabil.50

Ca i expresia (c), expresia (d) este o funcie simplu reali

3) o Q)_'!. _V oP Q (I p:!) qp (f.n.e.) I PqV qq VPP V qP (f.n. d .)o ( VP)

V

ii)

4. LI STA PRINCIPALELOR LEGI LOGICEo dat ce am expus procedeele de decizie cititorul poate face cunotin cu lista celor mai importante legi logice. ntr-un paragraf anterior a fost dat deja un grup de legi logice (I}-(23) unele referitoare la anumite proprieti ale funciilor, altele referitoare la echivalena funciilor (definirea unor operatori prin alii). (2 4) p . (PVq) = P (2 5) P V ( p q) -= P (legil absorbiei) . De exemplu, valoarea propoziiei "ba plnge, ba plnge sau se vait" se reduce la valoarea propoziiei "plnge" (se consi der c avem o persoan bine determinat la care ne raportm), la fel pentru "ba danseaz, ba danseaz ori cnt" valoarea se reduce la valoarea afirmaiei "danseaz". Analog pentru (25) "Cnt sau cnt i danseaz", "Huliganul njur sau njur i se bate".

(28) P q = p V 'ii (29) P V q p 'ii (legile lui de Morgan). " Nu-i adevrat c ninge i plou" ceea ce nseamn c "nu ninge sau nu plou". "Nu-i adevrat c un huligan vorbete frumos sau este panic " ceea ce nseamn c "un huligan nici nu vorbete frumos ' i nici nu este panic". (30) P - (q _ P) (3I) P _ (P _ q). Acestea snt legi ale implj caiei materiale care spun c adevrul decurge din orice ( 3 0) i respectiv c falsul implic orice (31), ca n cazurile: "Dac toi oamenii snt fiine raionale, atunci cel puin unele fiine raionale snt oameni (adevrul decurge din ade vr) . "Dac toi oamenii snt octogenari, atunci cel puin unii o ctogenari sint oameni", (adevrul decurge din fals, adic 1 implic adevrul). "Dac nici o pasre nu este animal, atunci nici un animal nu este pasre" (falsul implic falsul) (32) (P - p) _ P (33) P _ q) (P _ q) _ p (legile reducerii la absurd).=

(26) P _ P (27) P P (legile dublei negaii). De exemplu, "Nu este adevrat c 2 nu difer de 4 ", prin urmare, 2 difer de 4" (pentru 26) i ,,3 > 2 dac i numai dac nu este adevrat c 3 > 2".=

=

51

(37) P J (legea noncontradiciei) Nu este adevrat c p i non-p. ( 3 8) p Y P (legea terului exclus) Este adevrat p sau este adevrat non-p (or, p este adevrat sau p este fals). (3 9) pq V pq = P (40) pq . Pii. = P (legile excluderii). "Plou i stau n cas sau plou i nu stau n cas" este echi valent cu "plou". "Plou sau e vreme friguroas i plou sau nu e vreme frigu roas" este echivalent cu "plou". ExerciJii. S se substituie n fiecare lege ali operatori decit cei ce apar n legea respectiv i s se verifice dac ceea ce se obine este sau nu lege loic. Exemplu pentru p q q P s punem in locul conjunciei pe rind -+ , =, /' i/ , + i s se decid dac acetia au pro prietatea comutativitii. Astfel :=

Legea (34) spune c conjuncia implic partea sa, sau c; dac este adevrat conjuncia atunci este . adevrat i UI membru oarecare al ei, iar legea (39) spune c disjuncia este implicat de partea sa, sau c, dac este adevrat un membn: oarecare al disjunciei atunci este adevrat disjuncia. (36) p _ q) p) -+ q (legea modus ..R0nens) Dac este adevrat c p -+ q i dac este adevrat p atunci este adevrat q.

q

"Nici o propozIIe nu este adevrat" implic faptul c nici propoziia "Nici o propoziie nu este adevrat" nu est adevrat, prin urmare, Nu este adevrat c "nici o prop( ziie nu este adevrat" (exemplu pentru (32)). "Triunghiul echilateral are un unghi drept". De aci decurg c "nu toate laturile snt egale" (cci la unghiuri inegale s opun laturi inegale), iar din faptul c este echiIateral decurg (prin definiie) c "toate laturile snt egale". Prin urmart nu este adevrat c "triunghiul echilateral are un ungh drept". (34) (p q) _ p (resp. (p . q) -+ q) (3 5) P -+ (p Y q) (resp-+

(p y q.

p + q = q +p p - q = q -p P/q = q/P etc.52

5. FORM E L E NORMALE PER FECTE

a. n vederea rezolvrii &hor probleme cum ar fi problema daci dou expresii date sint sau nu echivalente, problema ipotezelor i concluziilor, precum! i problema minimizrii este util s introducem un nou tip de form normal, aa zisele "forme normale perfecte". Definiie. Numim form normal perfect aceea form nor mali care pe lng condiiile descrise anterior satisface nc urmtoarele proprieti : ,a) iecare membru al formei normale conine pe fiecare diri.- literele care intr n componena expresiei (cu sau fr negaie) ; b) nicCun termen prim nu poate aprea mai mult de (lo singur dat intr-un singur membru ; c) nici un membru nu poate aprea mai mult de o dat ; d) nici o liter nu poate intra ntr-un membru mpreun cu negaia ei. Exemple. Expresia (p V q) (p V q) este o form normal conjunctiv perfect (f.n.c.p.), iar expresia (p q) V @ p) este o form normal disjunctiv perfect. Funcia (p V q) r nu este n f.n.c.p. ece nu satisface condiia a). Expresia ppqr V prq satisface co:lldiia a) dar nu sa.!isface condiia b) deoarece p se repet n primul membru. Expresia pqr pqr pqr satisface condiiile a) i b) dar nu pe c). Expresia p r:;. pqr satisface condiiile a) -c) dar nu satisface condiia d)_ Convenie. Pentru a face mai comod analiza formei normale convenim ca n membrii ei s scriem literele n ordine alfa betic. Pentru a aduce o expresie la forma normal perfect procedm astfel : a) aducem expresia la una sau alta din cele dou forme normale (neperfecte) generale ; b) dac ntr-un membru lipsete o atunci ea se adaug. ' liter conform cu expresiile : , - --. ' "

--

este m !!J,e'iipctiv. iar , litera ce trebuie adu gaU i dup aceea se opere az distrihuiile, undeIX

I

/ri V (t t) (pentru f.n.c.) i I IX (t V 1) (pentru f.n.d.)__ o ."

/

c) dac un termen apare mai mult de o dat el este redu onform cu regulile

A.A. AVAV

A se nlocuiete c

u{)

V A se nlocuiete cu A

d) dac un membru apare mai mult de o dat, atunci e este redus conform cu aceleai reguli de mai sus (aci }. v_reprezenta nu un termen ci un membru), :, e) dac o liter pJ.re !preun cu nega ia ei n1:r.- u membru _ ati'n:ci tot meb:rul es, di1!lin_t. Cum justificm introducerea sau eliminarea unei expresii Este permis s ,se adauge la o expresie dat o alt expresie .dac noua expresie obinut n urma operaiilor amintite ,(introducere, eliminare) nu este diferit ca valoare de cea iniial. ntr-adevr, adugnd la expresia O( expresia (t . t) prin disjuncie, deci O( V (t . t) valoarea expresiei nu se schimb, ceea ce se dovedete prin demonstrarea tezei corespunztoare :

A

V (B . B ) = A=

1, i A 1 = A. n exemplele pe b. care le vom considera expresiile vor fi aduse dej a la formele normale (generale). a) (p_ q) V(q r) V p. Pornind de la definiia fn.p. urm rim rind pe rnd dac condiiile snt satisfcute. n caz c nu, noi le realizm conform cu regulile a) -e) de mai sus. n expresia a) condiia prim nu este satisfcut deoarece n membrul (p __se Jie.ra._:!l n membrul (q, . r) llpsete litera,.p -l iar In membrul p lipsete att q cit i r. Adugm pe rind literele care lipsesc dup regula respectiv :

Se tie c B . B

=

Analog pentru oc

Exerciii de norDlalizare perfecti .

O i c A V O = A. (t V 1) se tie c B V B

, Prin distribuie readucem expresia la forma normal :

P . q) .o>(r V r

!V

q

r)

(p V p V (p

(q V q)

p qr V pqr V qrp Y qrp ypq ypq54

Deoarece n ultimii doi membri lipsete litera r o vom aduga : (Procesul poate fi nfptuit n ' minte fr a mai scrie toate etapele). Ordonm literele alfabetic : PQ1 V pq; V pqr V jiqr Vpqr V p q; V pqr V pqr. Se observ c membrii PfJ! i pq; se repet, prin urmare i vom reduce : pqr V p q; V pqr V PQ1 V pqr ceea ce este f.n.d.p. b) S se normalizeze perfect C) se deduce B (A C) i reciproc. Demonstraie. Formula A (B C) conf. cu def. 1 este echivalent cu A (EC). De aci prin comutativitate se obI ine (BC) A, iar prin asociativitate B(CA) i n fine prin comuta tivitate 1i(AC). Dar din B(AC) prin def. 1 se obine a doua parte a reg. IX, adic B (A C). n mod analog se dove dete c i prima parte se deduce din a doua. i X. Regul. Din A (B -> C) se deduce (A . B) C=

Drmonstraie. Se demonstreaz prin asociativitate i aplica I't'g. VIII combinat cu def. 1 i def. 2. XI. Regul. Din A -> (A B) se deduce A B i reciproc. folosete asociativitatea i reg. VIII (combinat cu III).rea

reciproc.

Trrma 22

p(q . '1) (pq . pr)

Dr lJUJnslraie Seria1

Seria a II-a

Seria a III-a

(p . q) P (P / q. qjr) (q.r) q (VI) p(q. r) pq.78

(p . q) q(p jq, qjr) p (q (p . q (q.r) '1 (VI) p(q.r) p '1 (PIPq) qjpr) pq (Pr (P q p'1) "

Seria a IV-a (.,

) (VII)

p(q . r)

-r

(Pr - (pq.pr (IX)) (VII) q.e.d.

pr _ (p(q. r) - (pq.pr) .... p(q. r) _ p(q. r) - (Pq.pr ( XI) p(q . r) _ (pq. pr)Teorema 23. (pq .pr) - p(q. r) Demonstraie :( ,

p - (q - (p . q (P lq, qlr) q _ (r - (q. r*

(j> _ q) - (rp _ rq) (p /r , q /q . r, r lP) (r _ (q . r - (Pr _ p ( q . r "

( ., . . ) (VII)

q _ (Pr _ p(q . r) (I X) pr _ (q - p(q.r)

4 , (P /q , q/p(q . r) , r/p) _p(q . r)_(pq_p(p(q. r ( , ) (VII) pr-(pq_(p(p(p(q. r))) (IX) pq _ (Pr-p(p(q . r (VIII) se nlocuiete p (p (q . r cu p (p . r pq _ (Pr - p(q . r (IX) (P q .pr) _ p(q . r) q.e.d.Din 30 i 31 se obine prin prescurtare :

p (q. r) = pq.prDeoarece orice formul poate fi verificat prin forma normal conjunctiv, nu este necesar mai departe s demonstrm, ci, pe baza celor de mai sus formulm reguli de aducere la

f.n.e.

79

10.

PROPRI ETI LE SISTEMULUI AXIOMATIC

a. Un sistem axioma tic pentru a fi acceptat trebuie s satis fac trei proprieti formale : necontradicia (consistena), completitudine a i independena (ultima nu este socotit obli gatorie de ctre toi). Aceste proprieti pot fi definite pur formal ("sintactic") sau pe baza unei interpretri ("semantic " ). Necon'radicia. Spunem c un sistem axiomatic este necontra dictoriu dac i numai dac n el nu poate fi demonstrat o formul mpreun cu negaia ei, adic dac o formul de forma A . A nu este teorem n acest sistem. Independena. Spunem c un sistem axiomatic este inde pendent dac nici una dintre axiomele sale nu poate fi dedus din restul axiomelor. Compleritudine/J. Spunem c un sistem S este complet dac, adugnd la acest S o formul A nedemonstrabil n S, obinem o contradicie astfel : (S . A) (B. B). (Completitudinen in sens restrins, valabil pentru logica propoziiilor). Cum se demonstreaz aceste proprieti? Un proceden obi nuit este acela al interpretrii. De acest procedeu se folosesc Hilbert i Ackermann n lucrarea lor Bazele logicii teoretice. Apelul la interpretare cere s dm definiii aa-zis "semantice" pentru cele trei proprieti, i nu pur formale ("sintacticd. Spunem c un sistem este semantic necontradictoriu dl\c Vi numai dac prin interpretare toate axiomele i teoremele (obinute din axiome cu ajutorul regulilor) au o anumit pro prietate (de exemplu de a fi adevrate), pe care nici o alt formul din sistem nu o are. Spunem c un sistem de axiome este semantic independell.! , dac i numai dac pentru fiecare axiom se poate indica .o astfel de interpretare a variabilelor care d o anumit valoare (sau anumite valori) pentru tot restul axiomelor n timp ce axioma considerat nu are aceast valoare (sau aceste valori). i mai general vorbind, printr-o anumit interpretare axioma considerat nu are o anumit proprietate pe care o au toate celelalte. Spunem c un sistem axiomatic este sistem complet dac i numai dac toate formulele identic-adevrate construibile n sistem snt axiome sau teoreme in acest sistem. Aceast noiune nu este identic cu prima, ea are o valabilitate mai general.10

c. Independena. Axioma 1. Fie mulimea de valori (0, 1,2)**, D efi nim operatorii ncgaiei i disjuDciei astfel

Dm demonstraia acestor trei proprieti. b. Necontradicia. Pentru a demonstra aceast proprietate, apelm la mulimea de semnificaii (1, O). Operatorii vor fi definii matriceal. Se arat mai nti c toate axiomele au valoarea 1, indiferent de valorile 1 sau O acordate variabilelor. Calculul se face matrice al. n al doilea rnd, se arat c toate fo rmulele deduse prin cele trei reguli au de asemenea valoarea 1. Regula 1 (modus ponens). A, A -+ B f-- B Formulele A i A-+B reprezint axiome, Bau teoreme, deci : A = l , A-+B =1. Presupunem c B =O. Substituim in A-+B = l p e A i B c u valorile lor, respectiv cu 1 i O , i obinem 1 -+ -+ O = 1, ceea ce contrazice definiia implicaiei i deci nu poate fi acceptat. Rezult de aici c B nu poate avea valoarea O, ci trebuie s aib valoarea 1. Orice formul dedus prin r e gula I din axiome va avea valoarea 1. Regula substi,u/iei. Fie o axiom A* care conine o variabil p, ceea ce vom scrie A(p) ; A(P) 1. Aceasta nseamn c oricaro ar fj valorile lui p, 1 sau O, valoarea axiomei nu se schimb, de ci A( l) 1 i A (O) = 1. Punnd n locul lui p o variahil q, vom obine formula A(q). Presupunnd c A(q) O, din O i A(O) = O. Or, aces te q = 1 sau q = O, rezult c A(l) dou formule contrazic formulele A(l) = 1 i A(O) = O. n concluzie A(q) nu poate avea valoarea O, ci trebuie s fie . A ( q) = 1.= = = =

p

0 1 2 1 0 2

Io

0 1 2

2

1

O O O O 1 2 O 2 O

Se demonstreaz c axiomele 2, 3, 4 precum i teoremele care decurg din ele au valoarea O n ti mp ce axioma 1 nu are aceast proprietate. Verificm acest lucru pentru axioma 2. Sau teorem .

Poate fi elaM resturilor Ca de modulul ". 81

p q o o o 1 O 2 1 1 2 2 21 O O

pV (p v q)O O O O O O 2 O 2 O 2 O

1 0

1 O 1 O

1 2

1 2

2

O

2

O 1

0

O O

O

Analog se arat c 2 i 4 au valoarea O. Axioma 1 nu are aceast proprietate.

n cazul n care p ia valoarea 2, rezultatul va fi 2. Axioma 2. Considerm mulimea de semnificaii (O, 1, 2, 3). Definim operatorii y.-,

oyOyO= O l ylyl =Oyl =O 2 Y 2 Y 2 = OY 2 1 Y 2 = 2.=

(p y P) y P

pP

O 1 2 3 1 0 3 2

XI2 3O 1

O 1 2 3 O O O O O O O

Negaia

1 1 1 1 2 2 1 2 3

Disjuncia

Se demonstreaz matriceal c axiomele 1, 3 i 4, precum i teoremele care decurg din ele au n raport cu aceste semni ficatii numai semnificaiile O sau 2, n timp ce axioma 2 nu are aeeast proprietate. Fie moma 1. Se suhstituie pe rnd p cu O, 1, 2, 3.

P yp yp O yO yO = l yO = O l ylyl =Oyl =O 2y2y2 = 3 y2 = 2 3V3 y3 = 2 y3 = 282

Axioma 2 nu are aceast proprietate, deoarece pentru cazul 1. 3Y1 3 y (2 Y 1) Axioma 3. Considerm aceeai mulime de semnificaii ca i Y astfel : i mai sus (O, 1, 2, 3). Definim operatorii= = -

pP

O 1 2 31 O O 2

, qp O 1 2 3

I

O 1 2 3 O O O O O 1 2 3 O 2 2 3 O 3 O 3

Se poate demonstra matriceal c axiomele 1, 2 i 4 precum i toate teoremele care se deduc din ele iau valoarea O, n timp ce axioma 3 nu are aceast proprietate. ntr-adevr, pentru cazul n care p = 2 i q = 3, axioma 3 ia valoarea 3. Axioma 4. Considerm din nou mulimea de semnificaii (O, 1, 2, 3). Definim operatorii, y.-,

p P-

O 1 2 3 1 O 3 O

XIO 1 2 3

O 1 2 3 O O O O O 1 2 3 O 2 2 O O 3 O 3

n aceste condiii axiomele 1, 2 i 3, precum i toate teoremele care s e deduc din ele au valoarea O, n timp ce axioma 4 nu are ac east proprietate. ntr-adevr, pentru p = 3, q 1 i r = 2, axioma 4 ia valoarea 2.=

d. CODlpletitudinea. Demonstraia decurge astfel. La siste mul de axiome se adaug formula p V q.

1 . (p y q) Y P) 2 . P y q (la 1 i ap lic modus ponens) 3 . q Y P (qJP) P y p (P (f) 5. p y p4.

83

Din 4, prin regula corespunztoare legii idempotenei, se deduce 6. p. Din 5, prin regula idempotenei, se deduce 7. p. n acest fel s-a dovedit o contradicie 8. p .p. Completitudinea este n acest fel demonstrat. De notat este c semnificaiile de mai sus pot fi interpretate ca fiind valori logice (de exemplu, n logica bivalent sau respectiv n logicile n-valente cnd avem mai mult de dou valori). La fel de bine valorile respective pot nsemna i altceva (numere crora li se impun anumite condiii, vezi nota", p. 8 1).c.

Alte sisteIll e axioIll atice

a) Sistemul lui Frege

AXl AX2 AXa Ax4 Axs

p (q p) (p (q - r)) (p - (q _ r))

-

AXa P

(P - q) - (q - p) P -P-

((P - q) - (P - r)) (q - (p - r))

Regula substituiei i regula detarii. Ceilali operatori se reduc prin definiie la _ , - . b) Sistemul lui Lukasiewicz. Lukasiewicz a artat c sistemul lui Frege poate fi nlocuit cu unul mai simplu care are la Laz aceiai operatori ( - , _ ) . El conine trei scheme de axiome i regula modus ponens . Sch. AX2 (A _ (BSch. Axl A _ (B_ _

P

Sch. AXa (A: _ B) _ (B

C)) - A _ B) - (A - C))_

A)

A)

Fiecare schem de axiome desemneaz o mulime infinit de axiome. (Substituia este nlocuit prin aplicarea schemelor, totui deosebirea este mai mult o subtilitate teoretic, practic neavnd un rol deosebit). c) Sisfemul lui Russell. Conine n plus fa de sistemul lui Hilbert i Ackermann axioma : (p V (q V r)) _ (q V (p V r))

84

Or, aceast axiom aa cum a artat Paul Bernays este 5uper flui. Regulile snt a 5ubstituiei i modus ponen6. d) Sistemul lui Alonzo Clurch. Acest sistem conine un ope rator (_) i o constant f (fals). Regulile snt a substituiei i modus ponens.

Ax1 P - (q - P) Axl (s _ (p _ q)) _ ((s - p) - (s - q)) Ax3 ((P - f) - f) - p. e) Sistemul lui Nicod. J. Nic o d a construit un sistem cu Q singur axiom i cu un singur operator (incompatibilitatea notat f ). Ax . (p f(qIr)) f( (s f(s 1s) ) f ( (tlq) I ((P It) I (P It)Pe lng regula substituiei admite regulaA, Af(BfC)

C

11.

OBSERVAII

CU

PRIVIRE

LA

SIMBOLISM

a. Constantele 1 i O. Introducerea cifrelor 1 i O pentru adevr i respectiv fals deschide, aa dup cum am vzut n cazul minimizrii, anumite posibiliti pentru formulare de noi metode de rezolvare. n acelai timp noi putem defini mai concis funciile logice i formula anumite legi ntr-un mod anal og cu cel din algebra numeric.

= min lP, q) P V q = mu (p, q) p= l -P P q = max (f, q)p.q-+

DefiniEii

Legi p"

np

=

=

p (idemp otena "produsului", adic a conjunctiei) p (idempotenta sumei, adic a disjunciei)

b. Scrierea lui Lukasiewicz. Am vzut c Luks8iewicz a introdu8 sistemul de notare a operatorilor prin N, K, A, C, E, D (incompatibilitate), 1 (exdudere) : Np, Kpq, Apq, Epq, Dpq, Ipq. Aceast scriere prezint pentru nceput anumite .dificulti de citire. De exemplu, formula (P _ q) _ q _ r) _ __ (P _ T)) care este una din axiomele lui Lukasiewicz se scrie : CCpqCCqrCpr. Pentru a putea citi aceast expresie procedm de la dreapta spre stnga : considerm argumentele pr, apoi Cpr, argumentele q, r, apoi Cqr, la rndul lor Cpr i Cqr formeaz argumente pentru CCqrCpr, urmeaz apoi Cpq _i n fine ntreaga expresie are ca argumente aceste dou impli -caii. Putem folosi provizoriu parantezele. Fie CCCKAPqrApqCprq

C[C[CK(Apq)r(Apq)] (Cpr)]qTranscriem ncepnd cu implicaia din dreapta :

((((p V q) . r)

_

(P V q)) - (P

_

r))

_

q

lat i expresii pentru forme normale :

KApqAPNqANpq AKpqKPNqKNpqLegi :f2)

(1) Cpp, Epp

[3 ] [4] [ 51 [ 61 [7] [8] [9] I lO]

CKpqKqp CApqAqp NKpNp ApNp E NKpqANpNq ENApqKNpNq CpCqp CNpCpq EKpKqrKKpqr

(Il) EApAqrAApqr (12) EKpAqrAKpqKpr (13) AEpKqrKApqApr (1 4) EKpApqp (1 5 ) EApKpqp (16) CKpqp (17) CKpqq (18) CKCpqCqrCpr (19) CCpqCNqNp (20) CKCpqpq.

III

LOGICA PREQICATELOR

1. SIMBOLISMPn acum nu am intrat n structura intcrn a propoziiilor elementare. Simbolismul i aparatul logic introdus pn aci nu este totui suficient pentru a studia raionamente mai complicate cum snt cele de tip silogistic. ntr-adevr, conside rnd silogismul

Toate coniferele snt plante Bradul este un conifer Bradul este o plant el poate fi simbolizat cu ajutorul simbolismului propoziional astfl (p . q) _ r, ceea ce evident, nu este o lege logic. Este nevoie s ptrundem n structura acestor propoziii. Conform logicii generale propoziia "Toate coniferele snt plante" con st din a) subiect ("conifere"), b) predicat ("plante"), c) copula ("snt"), d) cantitatea ("toate"). Simbolic TS P. tr-o . udecat care are la baz schema S P.Jus.te . p") termenii i P desemneaz ceva determinat, de ex. S poate deSemna-tiii IndIVId sau o insuire, iar P o nsu ire. O nsu ire poate s le I su lect, Iar un In IVI poate I numai subiect. De exemplu, "Liviu Rebreanu" este r.m!:IL_iD..db.i d.wY....Jllll!L_P_ C?.!!!L.luca numai rol de subiect, dar termenul " 0ll:':J.0ate-t_.i_.s_i= L.ir-..t n jeca"iii "oamenii .kt _dar n judecata snt muritori ', termenUl " om' este 8ub ;so ciaie'Teste--o't'm_eiur :;m".._te E_cat. Posibili . .

87

"latea ca o noiune s joace rol de ,mbiect sau de predicat este unul din principiile care guverneaz silogistica aristotelic. Se poate proceda i altfel : putem considera o logic n care $ubiecte snt numai indivirii, iar predicate numai nsuirile {i relaiile). n acest caz vom avea urmtoarea schem logic ,individul x are nsuirea F". Convenim s notm indivizi o_!ecare cu x, y, z, , . . i nsu ;irile cu F, G, -II; . . . -Atribuira unei iiisuiirl individului va fi notat CJlJ(x) sau simplu cu Fx. Semnele x, y, z, . . . ! H, . . . snt variabile i anume primele snt variabile individuale, !ttr celelalte variabile predicative. !!1.diviz.ii ckr c!Din!,L.pot. fC notai cu a, b, c . . . Mulimea indivizilor la .care raporteaz variabilele individuale va fi numit domeniu de,semnificaie al acestor variabile. Schema ,,_fx" :va fi nuJlltii $heUl de funcie propoziional. p'ac !_)ocJ!! .luLE_.p.u..Il m . predicate determmate, ex. ;,OM", ,,"Plant'binem funcii p }Dp0'l'lOnale ffin1ij;-PI.!!t (_ ll!L ea ce se . Eit _us. este ". Schema Fx se citete in genere F de .JdI!!!.!. 1 .I3 ! ,,_ ().!!!.'., x" (sau chiar "x este F"). Funnia proDozitional nu este nc pro oziie dar ea oate fi Uansformat n ro ozitlc fIe. 'prin $U stltula variabilei.. fie prin specificarea extinderii nsu-" (P!oprietii) asupra indivizilor. ' n general dn. F e::;i-; ci d prop()ziii individuale .c!:.a!, Fb, Fc, (prin substituie), s e _ y" va fi considerat ca un predicat de x i y i se va scrie ?,:;;. (,L_rrjcite1! 1) nu exist reguli generale de decizie, dei exist anumite teoreme de asemenea cu aciune limitat. S-ar putea pune problema reducerii predi catelor n-adice la cele monadice, ceea ce n anumite cazuri se i face. Prin aceasta nu nseamn c ele snt inutile' cci exist mulimi i anume cele infinite care nu pot fi caracte ri zate numai prin predicate monadice (proprieti ale elemen telor) ci snt necesare predicate nadice (relaii ntre ele mente). Mai mult, unele formule snt realizabile pe o mulime infi nit dar nu pe o mulime finit, de exemplu formula :

n vederea economiei de scriere atunci cnd cuantori de acelai tip urmeaz unul dup altul n prefix noi putem adopta conveniile :x..

)

n legtur cu realizabilitatea formulelor pe mulimi infinite demonstreaz urmtoarea teorem. Teorema lui Lowenheim. Dac o formul este realizabil ntr-o mulime infinit (oarecare) ea este realizabil i intr-. mulime numrabil (adic o mulime biunivoc-corespondenti cu irul numerelor n atur ale) .se

6.

RElAII iNTR E SILOGI STIC I LOGICA PREDICATE10R

Mai sus am indicat dej a echivalentele n logica predica'telo:r pentru judecile A, E, 1, O. Conform cu echivalenele indicate silogistica (bazat pe aceste judeci) este echivalent cu UD fragment al logicii predicatelor monadiee. Chiar din cele spuse n paragraful consacrat problemei deciziei rezult c 1) problema deciziei poate fi rezolvat pentru silogistic, 2) silogistica este adecvat numai pentru studierea unor teo rii referitoare la mulimile finite, dar nu infinite.

Despre decizie vezi mai pe larg n [22] i {28].

n cele ce urmeaz, vom reda modurile silogismului cu aju torul aparatului pred catelor monadice. Ca semn al deduciei vom utiliza r-'Fig. 1.

Darii : Vx(Mx _ Px), 3x(Sx . Mx) 1- 3x(Sx , Px) Ferio : Vx(Mx _ Px), 3x(Sx . Mx) r- 3x(Sx , Px)Fig. II.

Celate,"" : V x(Mx - Px), V x(Sx - Mx) r- V x(Sx - Px

Barbara

:

V x(Mx - Px), Vx(Sx - Mx) r- V x(Sx _ Px)

Cesare : Vx(Px - Mx), Vx(Sx _ Mx) r- Vx(Sx - Px) Festino : Vx(Px Mx), 3x(Sx . Mx) f- 3x(Sx , Px)

Camestres : V x(Px _ Mx), V x(Sx _ Mx) 1-- V x(Sx - Px)

Baroco : Vx(Px - Mx), 3x(Sx . Mx) f- 3 x(Sx , Px)Fig. III.

Darapti : Vx(Mx Px), Vx(Mx _ Sx),. 3xMx 3X(Sx Disa"!,is i ,3x(Mx . Px), Vx(x - Sx) 3x(Sx , Px) Datisi : Vx(Mx - Px), 3x(Mx. Sx) f- 3x(Sx , Px)--. O'

Px)

Bocardo : 3x(Mx . Px), Vx(Mx - Sx) 1-- 3x(Sx , Px).

Felap'ton : Vx(Mx - Px), V x(Mx _ Sx), 3xMx 1-- '3x(8x

Px)

Feriso Vx(Mx _ Px), 3x(Mx . Sx) 1-- 3x(Sx, Px) (sau Ferison)Fig. VI.

Bamalip : Vx(Px _ Mx), Vx(Mx (sau Bramantip)(sau Calemes)

_

Sx), 3xPx

3x(Sx . Px)_

..

Camenes : Vx(Px _ Mx), Vx(Mx _ Sx) Vx(Sx Dimaris : 3x(Px . Mx), Vx(Mx (sau Dimatis)_

Px)

Sx) 3x(Sx , Px). -

Fesapo : Vx(Px _ Mx), Vx(Mx - Sx), 3xMx 1- 3 x(Sx , Px) Ferison : Vx(Px _ Mx); 3x(Mx . Sx) 1-- 3x(Sx, Px)tDO

Avem apoi transcrierea formelor singulare in fig. I ,i II.

Barbar. Vx(Mx -+ Px), Ma Pa Celarent : Vx(Mx -+ Px), Ma Pa Cesar. : Vx(Px -+ Mx), Ma Pa Came5tres : Vx(Px -+ Mx), Ma PaPrin schimbarea ordinii premiselor in fig. a IV-a ie ebia modurile cu numele respective : Baralipton, Celantes, Dabitis, Fapesmo i Frisesomorum. (Redarea lor se face de asemenea prin schimbarea ordinii premiselor in deduciile de mai eue). Analog sint redate modurile formate prin subalternarea conclulliei la modurile Barbara, Celarent, Cesare, Carrustres, Calemes, adic modurile "slabe" Barbari, Celaront, Cuaro, Camestros, Calemos. Este important s observm c in "transcrierile" modurilor la cele nsemnate cu se introduce o premie n plus. Aceasta pentru a preciza caracterul nevitl al predicatului. Introducerea existenei (fie ca o supoziie general care limiteaz utilizarea variabilelor predicative, fie ca mai sus prin redarea expres, ex. 3xMx) ne d posibilitatea s redm raporturile din ptratul logic clasic i o serie de inferene' imediate. De exemplu, "dac A este adevrat atunci I este adevrat" (A 1) poate fi re dat :

Cazul general :

Vx(Sx -+ Px), 3xSx 3x(SxoPx). Vx(Fx -+ Gx) 3x(Fx o Gx)

Fx -+ Gx poate fi adevrat chiar cnd x nu exist, or n acest caz afirmatia . c 3x(Fx o Gx) este pur i simplu fals. Conversiunea "dac Toi S snt P atunci Unii P snt S", redat prin :nu este adevrat din urmtoarele motive

Vx(Sx -+ Px), 3xSx 3x(Pxo Sx)nu este totui valabil n forma :Ul!.

pe ptratul logic snt n general valabile n c atelor.

Vx(Fx -+ Gx) 3x(Gxo Fx) din aceleai motive ca i mai Prin urmare, nu toate raporturile ,i inferenele bazatecalculul prerli

101

7.

CALCULUL AXIOMATIC AL PREDICATELOR

Vom expune n continuare calculul axiomatic al predicate lor n varianta Hilbert-Ackermann. La axiomele calculului propoziional se adaug axiomele : Axs VxFx - Fy. AXa Fy - 3xFx. AX6 nseamn "dac predicatul F se realizeaz pentru orice x atunci el se realizeaz i pentru un x oarecare" ; Axe nseamn : "dac predicatul F se realizeaz pentru un y oarecare atunci putem afirma c exist x pentru care F se realizeaz". Regulile de deducie prime vor fi : 1. Regula modus ponens (formulat ca i n calculul propoziiilor). II. Regulile substituiei III. Regulile cuantorilor IV. Regula redenumirii. II. Regulile substituiei. Deoarece n logica predicatelor avem trei feluri de variabile (propoziionale, individuale i predica tive), vom avea trei reguli de substituie. IlO() ntr-o formul A putem nlocui o variabil propoziio nal cu o formul B dac fie respect condiiile : a) variabila propoziional este nlocuit pretutindeni unde apare n A ; b) B nu conine variabile individuale libere care snt legate n A sau variabile individuale legate care n A snt lihere, c) daei variabila propoziional se afl n domeniul de aciune al unui cuantor, atunci variabila legat de acest cuantor nu se afl n B. II) O variabil individual liber poate fi substi tuit eu orice alt variabil individual cu condiiile c : a) sublltituia se face pretutindeni unde apare variabila n for mul, h) variabila cu care o nlocuim nu apare legat n for mula dat. I1y) Substituia pentru variabile predicative. Fie o formul A care conine predicatul F, pe scurt A (F ( . . . )). F conine n variabile individuale (libere sau legate). F poate fi nlocuit cu o formul B care conine cel puin n variabile libere dac : a) variabilele libere ale lui B nu apar legate n A, b) variabilele legato ale lui B nu apar libere n A, c) n fiecare caz de apariie a lui F n A variabilele lui F snt nlocuite numai cu asemenea102

variabile care nu apar legate n B *. Aceast parte a regulii substituiei necesit nc unele explicaii. Presupunem c F conine un numr de variabile pe care le notm astfel deci vom avea F(, x2, x,,). Presupunem apoi c F apare de n ori n A i vom nota diferitele sale apariii cu FI' F2' . . . . , F Variabilele individuale n diferite apa riii (fie s zicem Fi' Fj), pot fi asemenea sau diferite. For mula B conine cel puin variabile libere pe care convenim s le ordonm astfel Yl' Y2 . . . , y", . . . pe scurt B(Yl' ) unde Y; i Yj pot fi Iili identice. Y2' . . . y" Substituia se produce astfel : a) stabilim pentru fiecare Fi o coresponden astfel c oricrui i corespunde un singur Yi (acela care are acelai indice), b) nlocuim n B pe fiecare Y. cu corespondentul su xi ; c) formula Bj astfel obinut adic B, ( ) poate fi pus n locul lui Fi' Exemplu. S desemnm prin A formula VX3y(F(x, y) F(x, z)), iar prin B formula 3n(H(n, t) H(n, s . S se substituie B n locul lui F. Vedem c B satisface condiiile impuse pentru a putea fi substituit (F con ine dou variabile, iar B dou variabile libere). F apare de dou ori : Fl(X, y) , F2(x, z) ; vom avea n genere Fi(xV x2) . Pentru Fl(XV x2), xl = x, iar x2 = y ; pentru F2(xt> x2) , n formula B avem variabilele n, r, X1 = X, iar X2 deci B(n, t, n, ) Ordonm variabilele libere din B astfel c Yl = t, Y2=S. Stabilim corespondena ntre B (yv Y2' . . . )n Xl ' X2,

x"'

m'

n

'

. .

x.

Xl '

X , z

X II

_

z.

n,

S

s .

i

F.(xv x2) :

,

B(t,F2(x, z) - B (t,

s, . . . ) s, . . . )

nlocuim n B variabilele cu corespondentele lor din Fi i obinem respectiv B I (X, Y, . . . ) i B2(x, z, . ) adic, reve nind la formula pe care o reprezint B vom avea : 3 n(H(n, X) H (n, y)) i respectiv 3n(H(n, x) . H(n, z)) formule pe care le vom substitui n A respectiv n locul lui FI i F2 i vom obine : V x3Y(3n(H(n, x) . H(n, y)) 3n(H(n, x) . H (n, z ). . .

n e d iia 1 938

a

crii lui Hilbert i Ackermann condiia c) lipsete1 03

III. RfJ8ulile cuantorilor III IX) Din A B(x) se deduce A V xB(x) (x este liber n B ,i nu apare n A) ; III ) Din B(x) A se deduce 3xB(x) A (x este liber n B i nu apare n A). IV. Regula redenumirii. O variabil legat poate fi nlocuit cu o alt variabil (care dup nlocuire va aprea, de aseme nea legat) , in ntreg domeniul de aciune din care ea face 'parte, cu conditia ca dup nlocuire s se obtin din nou formul i ca nou variabil legat s nu apar liber n formula iniia l V. Regul (derivat) . Dac formula A(x) (unde x este liber) este demonstrahil, atunci V xA {x) este demonstrahil. Sec vena demonstrativ este urmtoarea :

A(x) A(x) V P V P p V P V A(x) (p V p) A ( x) (p V P) VxA(x) VxA(x)Aceast regul corespunde afirmaiei c dac A(x) este vala bil pentru un x oarecare (arbitrar ales) ea este v al abil n general (VxA(x)). VI. Regul (derivat). Fie o formul A(, x2, x..' Yl' Yz' , . . Y..) unde xi snt variabile libere, iar y; snt variabile legate. Variabilele xi pot fi nlocuite cu alte variabile z.> iar Yi' cu variabile Uj astfel ca locurile n care stau variabile identice s fie puse variabile identice, iar locurile n care stau variabile diferite s fie puse variabile diferite. (Demonstl'aia regulii se face prin substituie i redenumire). Exemplu. n Vx3y(F(x, y) V G (x, z)) vom nlocui pe x i y respectiv cu t i s, iar pe z cu u i vom obine Vt3s(F(t, s) V VG{t, u)) . Aceaatii condiie lipse,te de uemenea in ediia din 1938. Fr aceast condiie din 3%(20 y) ,.r obtine 3X(2O x).

1 04

Teoreme. Teorema 1. V x(F xyF x) .

dect terul exclus generalizat. P ornim de dej a demons trat). Substituim p cu Fx i

Aceast formul nu este altceva la p y p (formulobinem :

Fx y Fx

stratI

A p licm apoi regula care spune c dac A(x) atunci V xA(x) e demonstrat i obinem :

e demonAXa

Vx(Fx

Teorema 3. Vx(A y Fx) - A V VxFx. FfA y Fz (reg. 111") :

Ax .),

Teorema 2. VxFx -

Y Fx) 3 xFx (Se demonstreaz din(A V Fy)

n Ax, operm

Operm

n

aceast formul

Vx(A V Fx)

-

AIA : -

Aplicm definiia implicaiei i regula eubstituirii de echiva lente : Conform cu regula De aci prinIII

V x (A y Fx)

(i\. V Fy)

Vx(1\ - Fx)X

Fy) (calc. propoziiilor) :- (A-

} :

Vx((A - F x) . A)

- Fy

Retlenumim pe y

"'''A - Fx) . A)cu x

-

(reg. IV) :

VyFy

105

Aplicm regula X (calc. propoziiilor) :

Yx(A. - Fx) - (A - YxFx)Prin definiia implicaiei i substituirea de echivalente ob inem :

Yx(X V Fx) Suprimm dubla negaie :

(A V VxFx) .

Vx(A V Fx) - (A V V xFx) q.e.d.Teorema 4. Yx(A _ Fx) _ (A _ VxFx) (Se obine din Th. 3).VII. ReguL. Dac formula A _ (B _ C(x)) este demon strabiI atunci este demonstrabil I formula A _ (B _

-. VxC(x)).

Supoil ie : A - ( B _ C (x) ) (A. B) - C(x) (reg. X calc. prop.)

(A . B) - YxC(x) (reg. lUx) A _ (B _ Y xC (x) ) (reg. X calc. prop.)i

(Se consider c A

Se obine din p - (p V q) prin substituii i reg. III.

Teorema 5. A - Yx(A V Fx) .

B nu conin variabila x).

Teorema 6. Vx(A V Fx) = A V YxFx (Se descompune ntr-o conjuncie de implicaii dup care se poate demonstra utili znd Ax5, reg. IV (calc. pred.), reg. X (calc. propoz.), I I I (c ale. pred.). Teorema Th . 6) . Teoremaa

7. 8.

Vx(A

Fx)=

=

A -. VxFx (se dem. rl i n

Vx(A. Fx)

A . VxFx.

Se descompune n dou implicaii :

) Vx(A . Fx) _ (A . YxFx) ; b) (A . YxFx) -. Vx(A. Fx)(cititorul urmeazs

Dem. lui a) Secven demonstrativ indice singur regulile aplicate).1 06

'v'x(A . Fx) -> (A . \fxFx). 'v'y(A. Fy) (A. Fx). ( A . Fx) -> Fx Yr(A. Fy) -> Fx 'v' x ( A . Fx) -> \fxFxSe ap lic (p - q) ((p r) (p (q . r ) i regula modus ponens consecutiv i se obine formula dorit.

'v'x( A . Fx) A

( A . Fx) - A

L) (A . \fxF(x) \fx(A. Fx).

) i b) se obine Th. 8. Teorema 9. VxVyF(x, y) VyVxF(x, y). \fx\fyF(x, y) \fy\fxF(x, y) \fz\fuF(z, u) \fuF(x, u) (din Ax5). \fuF(x, u) F(x, y) (din Ax. 5) \fz"(uF(z, u) F(x, y) \fz\fuF(z, u) \fxF(x, y) 'v'x\fyF(x, y) \fy'v'xF(x, y) Analog se obine i \fy\fxF(x, y) \fx"(yF(x, y) Teorema 10. \fx(Fx . Gx} = (\fxFx. \fxGx). a) \fx(Fx . Gx) (\fxFx. \fxGx) \fy(Fy. Gy) -> (Fx. Gx) (Fx . Gx) Fx (Fx. Gx) GxDina=

VyFy Fx A . \fyFy A. Fx. (A. \fxFx) -> \fx(A . Fx).

"(y(Fy. Gy) Fx \fy(Fy. Gy) Gx

}

din acestea se obine respectiv :

\fx(Fx. Gx) \fXFX . dm acestea : Vx(Fx. Gx) VxGx \fx(Fx. Gx) (VxFx VxGx)1 07

}

b) (V"Fx. Y"Gx) _ Y"(F,,. G,,)VyFy - Fx VyGy - Gx (VyFy. YyGy) _ (Fx. Gx) (VxFx. VxGx) _ Vx(Fx. Gx) Din a) i b) ee obine Th. 10.

Teurema

Il.

Yx(Fx _ Gx) _ (Y"Fx _ YxGx)

Yy(Fy _ Gy) _ (Fx _ Gx) F" _ (Yy(Fy _ Gy) _ Gx) VyFy - Fx YyFy _ (Yy(Fy _ Gy) _ Gx) YyFy. Vy(Fy _ Gy) _ Gx VxFx. Y,,(Fx _ Gx) _ YxGx Y,,(Fx _ Gx) _ \;fxFx-

VyFy

3yFy Fx 3xFx \;fxFx \;fxFx -> 3xFx \;fxFx -,. 3 xFx

variabile libere. Dac A(x, y, . . . . ) = B(x, y, u) este o formul demonstrabil i exist o formul C astfel c ea conine pe A ( . . . ) ca parte (o dat sau de mai multe ori), iar A( . . . ) conine alte variabile n loc de y, . . . . i dac D este o astfel de formul care se obine din C prin nlocuirea n ea a lui A( . . . ) n unele sau n toate locurile cu B( . . . ) , atunci C D cstc de asemenea demonstrat. Pentru deducia de formule se poate folosi ca regul princi piul dualitii despre care am discutat deja mai sus.u x, , u=

Exerciii. S se demonstreze teoremele ; Teorema 14. \;fx(Fx -> Gy) -> (3xFx 3xGx) Teorema 15. \;fx(Fx A) -> (3xGx -;. A) Teorema 16. 3 x\;fyF(x, y) -> \;fY3xF( x, y) VIII. Regul (generalizare a regulii schimbului de echiva. le nte) Fie date dou formule A(x, .1', u) i B(x, y, u) care conin variabilele libere x, y, u i nu conin alte

8.

PROPRI ETILE SISTEMU LUI AXIOMATIC AL PREDICATELOR

Pentru demonstrarea acestor proprieti vom urmI ca i n cazul calculului propoziiilor ndeaproape textul lui Hil bert i Ackermllnn. Formulare dupA (16].109

a. Necontradicia. Pentru a demonstra c sistemul expus mai sus este ne contradictoriu se dovedete c toate formulele axiome sau teoreme posed o proprietate pe care nici o alt formul corect a calculului nu o posed. n acest scop ne slujim de urmtorul procedeu : a) nesocotim cuantorii i varia bilele individuale, b) tratm variabilele predicative ca varia bile propoziionale, c) formulele astfel obinute vor deveni toate formule ale logicii propoziiilor, ale cror variabile vor lua semnificaii din mulimea (1,0) (unde :;:::: 1), d) orice axio m sau teorem va lua valoarea 1 i nu valoarea O. Dac lucrurile stau astfel atunci sistemul este necontradictoriu. Pentru axiomele AXl - Ax, proprietatea este deja demon Itrat. Fie Ax5" VxFx Fy. Ea devine prin procedeul de mai sus F F. Ax6 Fy 3x Fx de asemenea devine F F. Or, s-a demonstrat n logica propoziiilor c p p este o teorem, prin urmare F .... F va fi teorem i deci va avea valoarea 1. Mai departe urmeaz s artm c regulile de deducie transformate corespunztor duc de la formule cu valoarea 1 numai la formule cu valoarea 1. Deoarece am suprimat variabilele individuale i cuantorii aplicarea lor se reduce la simpla repetiie a formulei sau la aplicarea regulilor din logica propoziiilor. Regula modus ponens rmne neschimbat, regula substituiei se reduce la cea din calculul propoziiilor, regulile cuantorilor se transform in simple repetiii, adic :

B (x) A VxB(x)A

Iar

regula: reaenumirii de asemenea se reduce la o smpl repetiie, ca de exemplu n cazul :1110.

B (x) -> A 3 xB(x) .... A

dcvine A B A .... B devine

BA BA

nu se confunda bara acestor reguli cu negaia. Vezi i m. d.)

VxFx Fy VzFz Fy

care devinc

n legtur cu aceast demonstraie de neco ntradicie se ridic o problem. Domeniul din care iau valori formulele noastre este finit (respectiv fier,are formul ia valoarea 1). Ce se ntmpl dac introducem premise cu domenii infinite? (De exemplu, axiome matematice.) Nu devine sistemul ne contradictoriu? Pentru a rezoha aceast problem Hilbert i Bernays au construit o teorie special (vezi Grundlagen d6r Mathematik).h. Independena. Se cere acum s demonstrm c nilii.una d in axiomele Ax! - AXe i regulile indicate nu snt de prisos. 1. Axiomele 1 -4. n calculul propoziiilor accste axiome snt independente (ele nu devin de priws chiar atunci cnd se ia fi axiom suplimentar cum e ca zul n sistemul lui Russell, Fau o alt axiom ca p -> p). Pentru a demonstra c nici n cazul de fa ele nu snt de prisos, operm din nou o "reducere" a calculului predicatelor la calculul propoziiilor n acelai mod n care am procedat mai sus. Ambele axiome predicative Axs i A X6 devin F -;, F, or ele nu se pot deduce din F _ F i deci nici dintro axiom suplimentar cum e p -;. p. Regu lile de dt due ie sufer aceleai trallfGrm ri ca i n eazui --L" u- contradiciei.

2. Independena AX6 i AXa.

Procedeu. Pentru a demonstra independena Axs se nlo cuiete pretutindeni n formula considerat expresia de forma VxA(x) cu expresia de forma VxA(x)V p V p. De exemplu, formula 'Ix (A. Fx) _ (A. VxFx) devine prin transformarea indicat (Vx(A. Fx) V p V ii) _ (A . (VxFx V p V p . Expre siile nlocuite snt Vx(A. Fx) i respectiv VxFx. n acest caz orice formul carc se pOlite deduce din AXl - Ax, i Ax" devine din nou formul deductihil din aceleai axiome dup transformarea amintit. Dimpotriv, AX6 devine prin trans formarea amintit (VxFx V p V p) _ Fy, formul care DU mai este totdeauna adevrat. ntr-adevr, membrul nti al implicaiei, adic (VxFx V P V ii) 1 (deoarece disj uncia conine un membru adevrat p V p) n timp ce Fy poate fi ad e vrat sau fals. Dac Fy = O atunci formula devine 1 _ O = = O. Pentru a demonstra independena axiomei AXa vom n locui orice parte de forma 3xA(x) cu 3xA(x).p.p. To ate for=

1 111

z.

(p V p) prin aplicarea regwii HI). Regula redenumirii. Elimi nm din

nlocuim pe VxA(x) din formule cu VxA(x) opop. Formula Vx(Fx V Fx) demonstrabil cu aju torul acestei reguli devine Vx(Fx V Fx) op op care este in demonstrabil deoarece pop = O, iar Vx(Fx V Fx)oO O. ). nlocuim n formule partea de forma 3xA(x) cu 3xA(x) V V p V p. Formula 3x(FxoF) demonstrabil cu ajutorul aces tei reguli devine 3x(Fxo Fx) V p V p, ceea ce nu mai poate fi dedus. ntr-adevr, 3x(Fxo Fx) V p V P este echivalent cu 3x(Fxo Fx) (p V p), formul ce se obine din (Fxo Fx)=

deduse din AXl - AX5 se vor deduce i n acest caz, dimpotriv AXa (adic Fy 3xFx, nu este deductibil deoarece ea devine : Fy (3xFx op op). Avnd n vedere c O , ( 3xFxo pop) 1 sau Fy = O. Cnd o. Or Fy p op Fy 1, vom avea 1 O O. Regula substitulei. IX). Se arat c exist o formul care nu poate fi dedus fr regula Hot), de exemplu VxFx 3xFx. ). Eliminm variabila z dintre variabilele individuale astfel c vom obine de exemplu din F(x, z) pe Fx, iar din Gz pe G. n acest caz toate formulele care au fost demonstrate fr aceast regul H) vor fi demonstrate i de astdat, n timp ce formula 'Ix Fx Fz care se obine din AX5 prin y/z devine o formul indemonstrabil, adic VxFx F. y). nlocuim n formul orice parte de forma 'Ix A(x) care conine predicatul G cu formula VxA(x) V p V p. Orice for mul demonstrabil fr IIy) devine din nou demonstrahil n timp 'ce VxGx Gy devine Vx(Gx V p V p) Gy ceea nu se deduce, cci p V P = 1 i deci (Gx V p V p) 1 , iar Gy 1 sau Gy O . Cnd Gy O implicaia devine 1 ->mulele=

=

=

=

=

ce

=

= .

=

=

O 0 Regulile cuantorilor. IX).=

formul variabila legat Prin aceat transformare formula VzFz Fx demonstra bil prin redenumire devine F Fx, ceea ce nu mai eete demonstrabil. Redm cele de mai sus ntr-un tabel sinoptic :

1 12

sau

Axioma Iregula

Proprietatea Necontradicia

I.

Procedeul

Rezultat

Ax. Ax.

Eliminm cuantorii Ele devin F-+F, dar i variab. individ. Ax. i Ax, ca atare nu se pot deduce din aceastaSe reduce la regula subst. din calc. prop. Devin simple repetiii

\cuantorilor i regulaAx.

Reg. subst. Regulile

redenumirii Independ. Partea

V xA(x) se inlocuiete cu V x A(x) V Vp VP

de

forma

Ax, devine (VxFxVp VP) -+ Fy care nu este universal adev.

Ax.

3xA(x) se nlocuiete cu 3 xA(x).

p

.

p

Ax. devine Fy_(3xA(x) p P)

care nu este univ. ade vrat

R egula II,.)

Formula Vx Fx _ _ 3x Fx nu poate fi il,.)

dedus frz.

Regula II)Regula IIy)

Independent

Eliminm pe

,VxFx_Fz nu poatefi dedus

V x A(x)

care con- ' VxGx-+Gy deTine indemonstrabilA ine G e inlocuit cu V x A(x) VPVP

Regula III.)

V xA(x) se inlocuiet:.. cu V xA(x) .p.p

V x(FxVi!..x) de!.ine V x(FxV Fx) p psi deci indemonstrabil

Reula III.)

3xA(x) se lnloculete cu 3xA(x)V

VpVP

Formula 3z(F,a- . Fx) demonstrabill cu ajutorul reg . III devine apoi indemonstrabill Formula Vz F_Px demonstrabill prill IV. devine F_Jlz nedemonstrabiH. 1'3

Regula IV

Eliminm pe este legat

%

cind

c. Completitudinea. Calculul predicatelor nu este complet n sensul n care acest lucru a fost definit n legtur cu calcu lul propoziiilor. ntr-adevr, exist o formul indemonstra bil 3xFx _ VxFx (ea este fals de ndat ce domeniul lui x este mai mare de un element) formul care anexat la siote mul de axiome amintit nu-l transform totui n sitem contra dictoriu. ntr-adevr, dac dup anexarea acebtei formule ncercm s demonstrm necontradicia prin procedeul de mai sus nu vom obine o contradicie, cci ea devine ca i cele dou axiome F _ F (dup eliminarea: cuantorilor ;i varia bilelor). Hilbert i Ackermann dau procedur pur formal de demon straie a imposibilitii de a deduce aceast formul. a) Se leag variabilele lihere din formule prin V care se aaz n faa ntregii formule, b) se nlocuiesc expresiile de forma Vx A(x) i 3xA(x) respectiv cu A(1). A(2) i A(l) V A(2) (unde 1 ,2 snt nume de obiecte individuale). Vom avea acum pe lng variabilele p, q, r, . . . formele F(l), F(2), G(l, 2) , .. . . pe care le nlocuim cu diferite variabile propoziionale, aHfel c n ultim imtan avem pNte tot nu mai variabile proro zionale. IIl.. acest caz orice formul demomtrabil a lcgicii predicatelor devine o formul identic-adevrat a logicii pro poziiilor. Demonstraia se face pe rnd pentru axiome reguli. Ax6 Prin procedura indicat VxFx _ Fy devine Vy(VxFx Fy). Eliminnd pe Vx obinem Vy F(I) . F(2 _ Fy), apoi prin eliminarea luiyobinem [(F(l ) . F(2 F(1 )] . [(F(1 ) . F(2 _ F(2)]. nlocuim termenii F( . . . ) prin variabilele pro poziionale : P . q) _ p) . p . q) _ q), ceea ce este o lege logicii propoziiilor. Ax Fy _ 3xFx devine Vy (Fy 3xFx). Eliminnd pe rnd cuantorii dup procedeul de mai obinem :o a ISUS,

[F( l ) - (F( l) V F (2) ) ] . [F (2) (F(1) V F ( 2)) ] De unde : (p (p V q)) . (q _ (p V q)) ceea ce este lege logic. Aplicarea regulilor de deducie conserv proprietatea irrdicat._ _

Vy(Fy - (F(l) V F(2)

i apoi

o

114

Regula substituiei. oc) . Dac n locul variabilei propozlIO nale avem de pus o formul predicativ, prin procedeul dat mai sus ea devine o formul a logicii propoziiilor care se sub stituie dup regula indicat acolo. (3) Variabilele individuale disprnd formula obinut prin substituie IIf3) devine o simpl repetiie .y) Regula se reduce la cea din calculul propo ziiilor. Regulile III revin la reguli din calculul propoziiilor. Re gula IV devine o simpl repetiie. Regula modus ponens apli cat la formulele predicative se transform dup cum urmea z : A(x), A(x) _ B ( x) B(x) \fx A(x), \fx(\f(x) _ B(x 'Ix B(x) A(1).A(2 ) , ( A(l ) _ B ( 1 . ( A (2 ) _ B(2 B ( l). B (2 ) p. q, (p _ r) . (q _ s) r s

Ultima este o regul a logicii propoziiilor. n acest fel s-a dovedit c orice formul adevrat a logicii predicatelor devine propoziie adevrat a logicii propoziiilor. Formula 3xFx _ \fxFx nu are aceast proprietate. Prin transformare ea devine (F(l ) V F(2 _ (F( l ) F(2 , adic (p V q) _ (p . q) , ceea ce nu este lege logic. Prin urmare, n sensul strict de mai sus sistemul axiomatic al predicatelor nu este complet. Dar complctitudinea poate fi definit i n alt sens. Pentru aceasta vom apela la noiunea de formul universal valabil. Hilb ert si Ackermann definesc n felul urmtor aceast notiune ,,0 formul a calculului predicatelor se numete univesal-f)fJla bil dac, independent de aceea care este domeniul indivizilor, prin orice substituie a variabilelor respective cu propoziii, nume de indivizi din domeniul dat i predicate ale acestor indi vizi ea deTine propoziie adevrat". Un sistem este complet dac n el pot fi de duse toate formulele universal valabile construibile n acest sistem. Demonstraia acestui fel de com115

pletitudine a fost dat de Kurt Godel. Aceast demonstraie se folosete de forma normal Skolem i de o interpretare n domeniul numerelor naturale. Kurt Giidel a dovedit c fie crei formule universal-valabile i corespunde o form norma l Skolem care este deductibil din sistemul de axiome. Con form cu echivalena deductiv dac A i B snt deductiv echi valente i dac una din ele este adevrat cefllalt va fi dJ / asemenea adevrat : M, A f- B ; M, B f- A, A B M, B f- A, B A Din cele de mai sus rezult c dac orice form normal Skolem universal valabil se deduce din axiomele predicatelor, atunci sistemul este complet. Teorema lui Godel despre completitudine. Orice formul uni versal valabil a logicii predicatelor este demonstrabil n acest calcul (Cititorul dispune n limba romn de demon straia acestei teoreme n "Elemente de logic matematic". de P.S. Novikov).9.

M, A f- B ;

I

I

EXTINDEREA LOGICII PREDICATELOR

Logica predicatelor expus mai sus are unele particulariti : a) ea folosete numai predicate de indivizi, b) variabilele pre dicative nu snt cuantificate, c) operatorii pentru variabile se reduc la cuantori. Totui exist mai multe ci de a dezvolta logica predicatelor : 1) introducerea operatorului descripiei (LX) i a operatorului abstraciei (Ax ), 2) introducerea predi catelor de predicate, 3) cuantificarea predicatelor.Operatorul descripiei. Expresii de felul