7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

1/33

1

Capitolul 2Logica clasica propoziiilor ( p )

Ceea ce numim astzi logica clasic a propoziiilor ( p ) reprezint numitorul

comun al unor perspective diferite de expunere formal a acestui compartiment al logiciisimbolice. Capitolul de faanalizeazcteva din aceste moduri de explicitare ale p : Teoria

funciilor de adevr (2.1), Tablourile analitice (2.2), Axiomatica (2.3), Deducia natural(2.4), Calculul secvenilor(2.5) iRezoluia(2.6).

2.1. Teoria funciilor de adevr

2.1.1. Sintaxa p

Logica propoziiilor reprezint partea cea mai simpl a logicii simbolice. Dac nsilogistica tradiional, aa cum am vzut n capitolul anterior, ne-am interesat i de structurainterna unei propoziii (i.e. structura subiect-predicat), n p aceastanalizrmne n afara

oricror consideraii. Descompunerea unei propoziii o vom face pn la obinerea unorpropoziii elementare i nimic mai mult. Dac, de exemplu, descompunem propoziia(compus!) Studenii sunt preocupai de logic i vor obine rezultate bune vom obine

propoziiile elementare Studenii sunt preocupai de logic i Studenii vor obine notebune, fr smai avem n vedere structura interna acestor propoziii elementare. Aadar,unitile sintactice nedecompozabile ale p sunt propoziiile elementare. Din propoziii

elementare, aidoma exemplului de mai sus, putem construi propoziii compuse de varii feluri.Date fiind propoziiile elementare Clujul este un oratransilvan i A venit toamna putemobine Nua venit toamna, Clujul este un oratransilvansaua venit toamna, DacClujuleste un oratransilvan, atunci a venit toamna etc. Aadar, asupra propoziiilor putem operan diverse moduri. n primul caz am negatpropoziia dat, n al doilea am conectat disjunctivcele doupropoziii, iar n cel de-al treilea le-am conectat implicativetc.

Logicasimbolica propoziiilor nu se intereseaznsde coninutul propoziiilor (i.e.

de ceea ce ele exprim), ci de relaiile logice posibile dintre ele. Motiv pentru care recurge lao simbolizare corespunztoare i, implicit, la un nou nivel de abstractizare. Pe scurt, limbajullogicii propoziiilor, p

1, conine urmtoarele categorii de simboluri (i.e. alfabetul):

1. Simboluri pentru variabile propoziionale:p, q, r, ..., 1p , 2p ,..., 1q , 2q ,...2. Simboluri pentru operatorii logici: ,...,,, 3. Simboluri pentru constante: 1 i 0.

1 p nseamnlogica simbolica propoziiilor, aa cum este ea explicitatn limbajul expus.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

2/33

2

4. Simboluri auxiliare: ), (, ], [, }, {.Simbolurile p, q, r,... denot aadar propoziii arbitrare; - este operatorul unar al

negaiei; ,, sunt, corespunztor, operatori binari: comjuncie, disjuncie, implicaie2; 1 i0 denotvalorile logice adevrat i fals3.

Formula p . Acest concept va fi definit pe baza unor reguli recursive, reguli care

permit obinerea de noi formule din cele deja construite. Prin ...,,...,,,21

nelegem, n

cele ce urmeaz, formule arbitrare ale p .

Definiie 1. a) Orice variabilpropoziionaleste o formula p .

b) Daceste o formula p, atunci este o formula p .

c) Daci sunt formule ale p, atunci este o formula p

(unde denotoricare din urmtorii 10 operatori binari: ,,,/,,,,,, + # 4).

Prin ,, ,... vom nelege mulimi de formule ale p .

Definiie 2. Gradul unei formule este numrul ocurenelor operatorilor logici din

formul, i.e.:a) Orice variabilpropoziionalare gradul zero.b) Dacare gradul n, atunci are gradul 1+n .c) Daci au gradele n, respectiv m, atunci are gradul

1++ mn .

2.1.2. Semantica p

2.1.2.1. Funcii de adevrPentru a decupa semnificaia integral a unui operator logic nu este suficient

nicidecum sne rezumm la exemple din limbajul natural. Va trebui ca nelesul lor s fie

complet explicitat prin definiii semantice. Aceste definiii arat, n fiecare caz n parte, moduln care valoarea logic a propoziiei compuse (i.e. a propoziiei care conine operatorulrespectiv) depinde strict de valorile logice ale propoziiilor care-o compun. S dm ctevaexemple. Fie propoziia Stiloul este albastru. Considerm cpropoziia este adevrat. Dacnegm aceastpropoziie, atunci vom obine propoziia compusNu este adevrat cstilouleste albastru sau Stiloul nu este albastru, simbolic p , i care este o propoziie fals.Invers, dacp era fals, atunci p este adevrat. Corelm aceste valori logice ale propoziieicompuse, p , cu valorile logice ale componentei ei,p, ntr-un tabel sau matricei obinem:

p p Aicipeste argumentul funciei negaie.

1 00 1

Aceastmatrice reprezintdefiniia semantica negaiei.

2O expunere n detaliu a operatorilor binari o facem n Semantica p .3Singurele cu care operm, logica clasicfiind o logicbivalent.4Din motive tipografice simbolul nonimplicaiei a putut fi redat doar prin #.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

3/33

3

La fel putem proceda considerndp: 2 + 2 = 4 i q: Tabla este neagr. Dnd valori

logice lui pi q, n toate combinaiile posibile, putem construi definiii pentru toi operatoriibinari ai p . Smenionm civa:

p q qp p q qp p q qp p q qp

1 1 1 1 1 1 1 1 1 1 1 11 0 0 1 0 1 1 0 0 1 0 00 1 0 ; 0 1 1 ; 0 1 1 ; 0 1 00 0 0 0 0 0 0 0 1 0 0 1

pi qsunt argumentele funciilor corespunztoare.

Cunoscnd matricea unui operator, putem construi, corespunztor, definiia acestuia.Conjuncia, de exemplu, este funcia de adevr care ia valoarea logic adevrat atunci cnd

ambele argumente sunt adevrate. Disjuncia este funcia de adevr care ia valoarea logicadevrat dac cel puin un argument este adevrat. Argumentele implicaiei ( ) se numescp= antecedent i q= consecvent. Din matricea corespunztoare rezultcimplicaia este falsdoar dacantecedentul este adevrat i consecventul fals. n fine, echivalena ( ) ia valoarealogic adevrat doar dacargumentele p, q au aceeai valoare logic. Trebuie s remarcmns urmtorul fapt: ceea ce intr n discuie n stabilirea valorii de adevr a propoziieicompuse (i.e. n definirea funciei/operatorului) este strict valoarea logic a propoziiilorcomponente i nimic altceva. n caz contrar, propoziia implicativ, construit cu pi q, demai sus ar fi o propoziie deloc uzual n nelegerea curent, de genul: Dac 2 + 2 = 4,atunci tabla este neagr. Aadar, orice consideraie cu privire la sensul propoziiilor esteeliminat. Acesta este motivul pentru care aceste funcii se numescfuncii de adevr.

Definiie 1. Funcia de adevr este o funcie de la mulimea valorilor logice alepropoziiilor componente la valoarea logic a propoziiei compuse. (simbolic:( ) ( )nnA ppAppAf ,...,,...,: 11 , unde este un operator logic).

Numrul funciilor care pot fi construite n logica bivalent depinde de numrul

variabilelor propoziionale, n, i se calculeazduprelaia simpl ( )n22Nr = .

Pentru n= 1, numrul funciilor este de patru, adic:

p ( )p1 ( )p2 ( )p3 ( )p4

1 1 1 0 0

0 1 0 1 0

Tabelul de adevr de mai sus are cinci coloane i dou linii. Prima coloan conineasignrile fcute variabilei propoziionale p, iar celelalte patru reprezint funciile unarecorespunztoare, adic: verum(p),p, p ifalsum(p).

Definiie 2. Prin interpretarea unei variabile propoziionale se nelege asignarea(atribuirea) unei valori de adevr variabilei respective.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

4/33

4

Dac cunoatem tabelul de adevr al unei funcii, atunci cunoatem semnificaia

funciei, respectiv i putem construi definiia. Din cele patru funcii de mai sus, ( )p3 estetocmai negaia. Negaia este aadar funcia de adevr (unar!) care ia valoarea logicadevratdacp este fals; fals n caz contrar. La fel putem construi definiii i pentru celelalte funciiunare.

Pentru n= 2, ) 162Nr 22 == . Cele 16 funcii binaredistincte sunt redate de ceea cese numete Tabelul lui Wittgenstein5.

p q ( )qp,16 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 01 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 00 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 00 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0

T p q / + q # p C

82

Nr1 ==

L ; 4

2

Nr22

==

L ; 22

Nr33

==

L ; 12

Nr44

==

L

Tabelul conine 18 coloane i 4 linii. Primele doucoloane reprezinttoate categoriilede asignri fcute variabilelor p i q, iar celelalte funciile binare corespunztoare.Completarea liniilor o facem dup urmtorul algoritm simplu: n linia nti ( 1L ) vom scriealternativ valori omogene al cror numr este numrul total al funciilor (16) mprit la 2,

pentru linia a doua vom mpri acest numr la 22 , apoi la 32 pentru linia a treia i, n fine, la42 pentru linia a patra. Cele 16 funcii binare sunt, corespunztor: tautologia (T ), disjuncia

neexclusiv( ), implicaia convers( ), prependena ( p), implicaia ( ), postpendena (q),echivalena ( ), conjuncia ( ), incompatibilitatea ( / ), disjuncia exclusiv ( + ),

postnonpendena ( q ), non-implicaia ( # ), prenonpendena ( ), nonimplicaia convers

( ), rejecia ( ) i contradicia (C).Din construcia tabelului se poate observa c funciile 169 se pot obine,

corespunztor, din negarea funciilor 18 , motiv pentru care incompatibilitatea de mai sus

se mai numete i anticonjuncie, disjuncia exclusiv antiechivalen, rejecia antidisjuncie etc.

Tot n construcia tabelului observm c 1 este ntotdeauna adevrat, 16 este

ntotdeauna fals, iar celelalte funcii conin n matricea lor valori de adevr neomogene.Motiv pentru care putem opera urmtoarea clasificare a funciilor de adevr: valide

(tautologii, adevruri logice), nesatisfiabile (contradicii, falsiti logice) i satisfiabile(realizabile), terminologie pe care o vom aplica cu referire la orice formul a p (aa cum

vom arta mai jos).

5Comp. L. Wittgenstein, Tractatus logico-philosophicus, 5.101.6Din motive tipografice pentru celelalte funcii vom omite argumentele.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

5/33

5

2.1.2.2. Dualitatea

Definiie. Doi operatori logici7 se numesc duali dac matricea unuia se obine dinmatricea celuilalt nlocuind reciproc valorile logice 1 i 0 n toate ocurenele lor.

Exemplu. Dacn matricea operatorului executm aceste nlocuiri obinem matriceaoperatorului + .

p q qp p q qp +

1 1 1 0 0 01 0 0 0 1 10 1 0 1 0 10 0 1 1 1 0

Dac i n celelalte cazuri procedm similar, vom gsi urmtoarele perechi deoperatori duali: T - , , , # (exerciiu).

Ceilali, pqp ,, i q , constituie gama operatorilor autoduali. Operatorul unar este de asemenea autodual (de ce?).

2.1.2.3. Procedeul matriceal ca procedeu de decizie n p

Definiie 1. O formula p se numete valid(simbolic: ) dacpentru orice

interpretare a variabilelor sale ia valoarea logicadevrat.

Definiie 2. O formul a p se numete nesatisfiabil dac pentru orice

interpretare a variabilelor sale ia valoarea logicfals.

Definiie 3. O formula p se numete satisfiabildacexistdou interpretri

ale variabilelor ei n care ia valori logice opuse.

Remarc. n sens largsatisfiabilitatea nu exclude validitatea, fiind satisfiabildacexist(cel puin) o interpretare n care este adevrat.

Pentru a constata validitatea unei formule (valide!) procedeul matriceal este unulfoarte practic, atunci cnd numrul variabilelor formulei nu este prea mare (mai mare de 3).

Slum un exemplu:

8

( ):,, rqp [( qp 1/ ) r2

3 ] 6 ( pq 4

5 )

Numrul liniilor matricei este n2 , unde n reprezint numrul variabilelorpropoziionale. Numrul coloanelor este dat de numrul operatorilor logici ai formulei plusnumrul variabilelor propoziionale. Vom construi aadar o matrice (tabel de adevr) cu 8 linii

7Corespunztor, funcii de adevr, n cele ce urmeazvom considera cele douexpresii interschimbabile.8Menionarea variabilelor, dupsimbolul , nu este necesar.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

6/33

6

i 9 coloane. Pentru a facilita construcia matricei, putem nota operatorii logici n ordineaexecutrii operaiilor.

p q r 1/ 2 3 4 5 6

1 1 1 0 0 1 0 1 1

1 1 0 0 1 1 0 1 11 0 1 1 0 0 0 0 01 0 0 1 1 1 0 0 00 1 1 1 0 0 1 1 00 1 0 1 1 1 1 1 10 0 1 1 0 0 1 1 00 0 0 1 1 1 1 1 1

Completarea interpretrilor variabilelor o facem i n acest caz dup algoritmul maisus aplicat (n cazul Tabelului lui Wittgenstein), numai caici avem, corespunztor, coloane,nu linii.

Coloana ultimei operaii menionate,6

, reprezint valorile logice ale formulei ,

pentru toate cele 8 interpretri ale variabilelor sale. Aa cum ne aratmatricea, avem o funcierealizabil.

Smai lum un exemplu. Fie : [ ( ) qrp / ] [ ( ) pqp ].Facem, corespunztor, matricea, fra mai numerota operatorii logici.

p q r r rp ( ) qrp / p q qp ( ) pqp

1 1 1 0 0 1 0 0 1 1 11 1 0 1 1 0 0 0 1 1 1

1 0 1 0 0 1 0 1 0 1 11 0 0 1 1 1 0 1 0 1 10 1 1 0 0 1 1 0 0 1 10 1 0 1 0 1 1 0 0 1 10 0 1 0 0 1 1 1 0 1 10 0 0 1 0 1 1 1 0 1 1

Cum coloana final a matricei formulei conine o serie omogen de valori de 1,rezultc este o formulvalid.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

7/33

7

Formule valide remarcabile ale p

Prezentm mai jos cteva tautologii remarcabile ale p , cu referire la operatorii

menionai n frontul fiecrei grupe ( ) ,,,, . n dreptul fiecrei formule vom specificadenumirea uzuala tautologiei respective n p .

( ) 1. ppk 2... ; ,...2,1,0=k ; 1 i 2 Eliminarea negaiilor multiple

2. ppk +12... ; ,...2,1,0=k

( ) 3. ( ) ppp ; idempotena conjunciei4. ( ) ( )pqqp ; comutativitatea conjunciei5. ( )[ ] ( )[ ]rqprqp ; asociativitatea conjunciei6. ( )[ ] ( ) ( )[ ]rpqprqp ; distributivitatea conjunciei (n raport cu

disjuncia)7. ( )[ ] pqpp ; 7 9 Absorbia conjunciei8. ( )[ ] ( )qpqpp 9. ( )[ ] pqqp 10. ( ) pqp ; 10 13 Atenuarea conjunciei11. ( ) qqp 12. ( ) ( )qpqp 13. ( ) ( )qpqp 14. ( ) ( )qpqp ; 14 i 15 Legile lui De Morgan15. ( ) ( )qpqp 16. ( )pp ; principiul noncontradiciei

(

) 17. ( ) ppp

; idempotena disjunciei18. ( ) ( )pqqp ; comutativiatea disjunciei19. ( )[ ] ( )[ ]rqprqp ; asociativitatea disjunciei20. ( )[ ] ( ) ( )[ ]rpqprqp ; distributivitatea disjunciei (n raport cu

conjuncia)21. ( )[ ] ( )qpqpp ; 21 23 Absorbia disjunciei22. ( )[ ] pqpp 23. ( )[ ] pqqp 24. ( )qpp ; 24 i 25 Introducerea disjunciei25. ( )qpq

26. ( ) ( )qpqp ; 26 i 27 Legile lui De Morgan27. ( ) ( )qpqp 28. pp ; principiul terului exclus

( ) 29. pp ; reflexivitatea implicaiei

30. ( ) ( )[ ] ( )rprqqp ; tranzitivitatea implicaiei31. ( )[ ] ( )[ ]rqprqp ; legea importaiei / exportaiei

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

8/33

8

32. ( )[ ] ( )[ ]rpqrqp ; permutarea premiselor33. ( )[ ] ( )qpqpp ; absorbia implicaiei34. ( )[ ] ( ) ( )[ ]rpqprqp ; autodistributivitatea implicaiei35. ( ) ( )pqqp ; 35 37 Legi ale contrapoziiei36. ( ) ( )pqqp

37. ( ) ( )pqqp 38. ( )pqp ; 38 i 39 Paradoxurile implicaiei39. ( )qpp 40. ( )qpp ; ex falso quodlibet41. ( ) ( )[ ]qrpqp ; 41 44 atenuarea implicaiei42. ( ) ( ) ( )[ ]qrprqp 43. ( ) ( ) ( )[ ]rprqqp 44. ( ) ( ) ( )[ ]rqrpqp 45. ( )[ ] qqpp ; modus ponens46. ( )[ ] qqpp ; modus ponendo ponens47. ( )[ ] qpqp ; 47 i 48 modus tollendo tollens48. ( )[ ] pqqp 49. ( ) ( )[ ] qqpqp ; dilema constructiv50. ( ) ppp ; 50 52 reductio ad absurdum51. ( ) ppp 52. ( ) ( )[ ] pqpqp 53. ( )[ ] ppqp ; legea lui Peirce

( ) 54. pp ; reflexivitatea echivalenei

55. ( ) ( )pqqp ; simetria echivalenei56. ( ) ( )[ ] ( )rprqqp ; tranzitivitatea echivalenei57. ( )[ ] ( )[ ]rqprqp ; asociativitatea echivalenei58. ( ) ( )qpqp ; 58 i 59 contrapoziia echivalenei59. ( ) ( )qpqp 60. ( ) ( )qpqp ; 60 i 61 atenuarea echivalenei61. ( ) ( )pqqp 62. ( ) ( )qpqp ; respingerea echivalenei63. ( ) ( ) ( )[ ]qpqpqp ; condiiile de adevr ale echivalenei

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

9/33

9

2.1.2.4. Relaia de consecinsemantic

Pentru explicitarea nelesului acestui concept s dm mai nti un exemplu. Fieurmtoarele formule ale p : ( ) ( )qpqp : , ( ) rqp : i qp : . Sprezentmn tabelul de mai jos matricea celor trei formule.

p q r qp qp r

1 1 1 1 1 0 0 0 11 1 0 1 1 0 1 1 11 0 1 0 0 1 0 1 11 0 0 0 0 1 1 1 10 1 1 0 0 1 0 1 10 1 0 0 0 1 1 1 10 0 1 1 0 0 0 1 00 0 0 1 0 0 1 1 0

Pe baza acestei matrice putem observa c de ori cte ori formulele i suntsimultanadevrate i formula este adevrat(conversa nefiind valabil). n acest caz vomspune cformula este o consecinsemantica formulelor i . Mai putem constata cde ori cte ori este adevrat i este adevrat (reciproca nefiind nici n acest cazvalabil). i n acest caz vom spune c este consecinsemantica lui .

Definiie. Fie ,,...,1 n formule ale p . este o consecin semantic a

formulelor n ,...,1 (simbolic n ,...,1 ) dacpentru orice interpretare a variabilelor

propoziionale care apar n ,,...,1 n , formula este adevratde ori cte ori n ,...,1

sunt simultan adevrate ( n ,...,1 sunt premisele iar este consecina lor semantic).

Exerciii.1. Se dau urmtoarele formule ale p : ( ) ( )qpqp :1 , ( ) ( )qpqp :2 ,

( ) ( )qpqp :3 , ( ) ( )[ ]qrpqp :4 . Stabilii cazurile n care relaiade consecinsemanticare loc.

2. Ce putem spune despre relaia dac este o formul valid a p ? Dardaceste o formulnesatisfiabil?

3. Construii o demonstraie pentru urmtoarele enunuri:a) Dac i , atunci .

b) Dac i , atunci .4. Argumentai curmtorul condiional are loc:Pentru nn ,...,:1 1 ddac n ...1 .

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

10/33

10

2.1.2.5. Scheme deductive cu operatori ai p

Din cele 16 funcii de adevr binare, 10 pot figura n scheme deductive valide.Celelalte 6 (p, q, p , q , T , ), numite i funcii degenerate, nu exprim propriu-ziscorelaii logice ntre argumentele lor, motiv pentru care nu pot construi scheme deductivevalide. Sconsiderm n continuare cteva exemple de scheme valide.

Cu ajutorul implicaiei materiale putem construi urmtoarele scheme:

qp q p q q p q

q p 1 1 1modus ponens modus tollens 1 0 0

0 1 10 0 1

Verificarea validitii lor o putem face fie construind o formul implicativde genul

premise concluzie, pe care-o verificm cu ajutorul procedeului matriceal, adic( )[ ] qpqp , fie o justificm pe baza matricei (i.e. definiiei semantice a) implicaiei. n

acest din urmcaz, alegem din matrice liniile care stipuleazcondiiile din premisele schemei,adic 1=p i ( ) 1= qp , respectiv doar prima linie. Pentru concluzie ne rmne o singuralegere, 1=q . La fel putem justifica i modus tollens.

n schimb, urmtoarele scheme sunt nevalide (de ce?):

qp qp p q

q p

Cu incompatibilitateaputem construi alte scheme deductive:

p / q p / qp sau q

q p

Exerciii.

1. Se dau urmtoarele definiii:Def. 1. O formul a p este satisfiabil dac exist dou interpretri distincte ale

variabilelor sale astfel nct formula ia, corespunztor, valori logice distincte.Def. 2. O formul a p este satisfiabil dac exist cel puin o interpretare n care

formula este adevrat.Def. 3 O formula p estesatisfiabildacformula nu este nesatisfiabil.

Ce raporturi logice putem stabili ntre cele trei definiii?

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

11/33

11

2. Unele funcii din tabelul lui Wittgenstein exprim raporturi de condiionare( ,,,, i T ), altele exprimraporturi deopoziie(negaiile funciilor precedente) iaraltele exprimraporturi mixte(p, q, p i q ).

a) Artai c funciile p, q, p i q exprim raporturi mixte (i.e. pot fi redate,fiecare, ca o conjuncie dintre o funcie care exprimun raport de condiionare i una care

exprimun raport de opoziie).b) Verificai, prin transformri sintactice adecvate, crelaiile respective au loc.

3. Construii toate schemele valide n care figureaz operatori binari ai p .

Argumentai validitatea lor.

4. Formulai concluzia, n termenii incompatibilitii, pe baza urmtoarelor premise:(p/q)/[(p/p) / (q/q)]

q/q

5. Construii dou scheme deductive valide, una n care una dintre premise esteq , iar cealaltn care una din premise este qp .

6. Formulai concluzia, n termenii rejeciei, pe baza urmtoarelor premise:( ) ( )qpqp (p / p)/ (p / p)

7. Explicai simbolic ideea excluderii covalenei propoziiilor.

8. S se determine, n termenii rejeciei, cea de-a doua premis mpreun cu careexpresia de mai jos poate constitui o schemdeductivvalid. Formulai concluzia.

(p / p)/ (q/ q)

9. Constituie urmtoarea combinaie de premise o schemdeductivvalid? De ce?p / pp / (q / q)

10. Ce concluzie se poate formula, n termenii rejeciei, pe baza urmtoarelor premise:[( pp ) q ] [( pp ) q ]

( pp ) ( pp )

11. Construii o schemdeductivvalidn care premisele sunt( ) ( )pqqp

p / p

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

12/33

12

2.1.3. Transformri echiveridice n logica propoziiilor

2.1.3.1. Conceptul echiveridicitii

Vom ilustra mai nti ideea de echiveridicitate, pe baza ctorva exemple simple.a) Fie urmtoarele douformule ale p :

( )rqp : ; ( ) ( )rpqp :

Svedem n ce relaie logicse aflele, comparnd matricele:

p q r rq ( )rqp qp rp ( ) ( )rpqp

1 1 1 1 1 1 1 1 11 1 0 1 1 1 0 1 11 0 1 1 1 0 1 1 11 0 0 0 0 0 0 0 10 1 1 1 0 0 0 0 1

0 1 0 1 0 0 0 0 10 0 1 1 0 0 0 0 10 0 0 0 0 0 0 0 1

Vom constata c valorile din coloana final (respectiv valorile acestor funcii deadevr pentru asignrile corespunztoare) sunt identice. Vom spune ci sunt formuleechiveridice.

b) Fie acum formulele qp : i qp : . Similar,

p q qp p qp

1 1 1 0 1 11 0 0 0 0 10 1 1 1 1 10 0 1 1 1 1

i n acest caz este valabilconstatarea de mai sus.

c) n fine, considerm formulele: ( )[ ] ( )[ ]qqprqp +/: i( ) ss: [ ( ) tqp ].

Fr s facem matricele corespunztoare putem constata c ambele formule suntvalide: prima este o implicaie cu consecventul adevrat iar a doua o implicaie cuantecedentul fals. i n acest caz cele douformule sunt echiveridice.

Sconstruim acum o definiie pentru conceptul echiveridicitii. Fie npp ,...,1 ( 1n )

toate variabilele care apar ntr-o formul, fie mqq ,...,1 ( 1m ) toate variabilele care apar

ntr-o formul .

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

13/33

13

Definiie. Formulele i se numesc echiveridice (sau semantic echivalente) dac

pentru orice interpretare datvariabilelor mqp ,...,1 ele iau aceeai valoare logic(simbolic

eq).

Remarc1.Pentru a fi echiveridice formulele nu trebuie s coninneaparat aceiai

operatori logici (comp. exemplul b) sau aceleai variabile (sintactic sau numeric) (comp.exemplul c).

Remarc 2. Echiveridicitatea nu trebuie confundat cu operatorul echivalen, ,din Tabelul lui Wittgenstein. Aceasta este un operator binar al limbajului obiect care, pus ntredou formule, i , formeaz o nou formulmai complex a limbajului obiect.Eq este, n schimb, un operator binar al metalimbajului care, pus ntre simbolurile i ,genereazexpresia eq, n care i sunt termenii relaiei eq i nu formule ca atare(nseamnformula , iar formula). Firete, aa cum am constatat din exemplelede mai sus, ntre eq i existurmtoarea relaie:

eq ddac este o formulvalid(i.e. ).

Aadar, dou formule i ale p sunt echiveridice ddac ele sunt logic

echivalente, adicpentru orice interpretare a variabilelor lor ele iau aceeai valoare logicideci .

Echiveridicitatea are urmtoarele proprieti:1. Refl: eq .2. Sym: Daceq , atunci eq .3. Trans: Daceq i eq atunci eq .

2.1.3.2. Operatori fundamentali, operatori derivai

Definiie 1. Un operator logic introdus cu ajutorul unei definiii semantice (matrice)se numete operator fundamental (la fel putem spune, corespunztor, despre o funcie deadevr).

Definiie 2. Un operator logic introdus cu ajutorul unei definiii sintactice se numeteoperator derivat (respectiv o funcie de adevr derivat).

Exemple: qpqp df = ; qpqp df =/ etc.

Fie, n cele ce urmeaz, o mulime { }nOOM ,...,1= , 1n , de operatori fundamentali.

Definiie 3. Un operator iO se numete funcional independent de ceilali operatori

din mulimea M dacel nu se poate defini sintactic prin ceilali operatori.

Definiie 4. O mulime de operatori fundamentali { }nOOM ,...,1= , 1n , se numeteindependentdacfiecare operator este funcional independent de ceilali operatori.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

14/33

14

Exemple.1. Fie { }= ,,M . M nu formeaz o mulime independent, deoarece se poate

defini sintactic prin i :( )qpqp df =

Similar, se poate defini prin i .

2. { }= ,M este independent.Argument. Trebuie sartm coperatorul nu poate fi definit doar cu operatorul

i invers. Din variabile i din negaie putem construi doar formule de formapppp ...,,, etc. Aceste formule sunt fie echiveridice cu p, fie cu p , pe baza

formulelor 1 i 2, 2.3.Cu ajutorul negaiei se pot construi aadar numai acele funcii binare care sunt

echiveridice fie cup, fie cu q, fie cu p , fie cu q , adic:

p q ( )qp,1 ( )qp,2 ( )qp,3 ( )qp,4

1 1 1 1 0 01 0 1 0 0 10 1 0 1 1 00 0 0 0 1 1

ntruct nici una din aceste funcii nu este echiveridiccu conjuncia, conchidem coperatorul nu poate fi definit doar prin intermediul negaiei. Similar, nu poate fi definitdoar cu ajutorul . Cu ajutorul nu pot fi construite dect formule de forma

pppp ..., , toate fiind echiveridice cup.

2.1.3.3.Completitudine funcional

Definiia 3.3. O mulime M de operatori fundamentali se numete funcional completdacorice alt operator al p se poate defini prin operatorii mulimiiM.

Vom da n continuare cteva exemple de mulimi funcional complete de operatorilogici: { }= ,1M , { }= ,2M , { }= ,3M , { }/4 =M i { }=5M . Vom considera n celece urmeazdoar urmtorii operatori din tabelul lui Wittgenstein: + /,,,,,, .

{ }= ,1M este funcional complet { }= ,2M este funcional completqp eq ( )qp qp eq ( )qp

qp eq ( )qp q eq q qp eq ( )qp ( )pq q eq ( ) ( )[ ]pqqp eq

( ) ( )( )pqqp qp + eq ( ) ( )[ ]pqqp q+ eq ( ) ( )pqqp

qp / eq ( )qp qp / eq qp qp eq qp qp eq ( )qp

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

15/33

15

{ }= ,3M este funcional completqp eq ( )qp qp eq qp

qp eq ( ) ( )[ ]pqqp eq ( ) ( )[ ]pqqp qp + eq ( ) ( )[ ]pqqp

qp / eq q qp eq ( )qp

{ }/4 =M este funcional completp eqp/q

qp eq ( )qp / eq ( ) ( )qpqp ///qp eq ( ) ( )qqpp ///qp eq qp eq ( )qqp //qp eq ( ) ( ) ( )[ ]qqppqp /////

qp eq ( ) ( )qpqp eq ( ) ( )( )[ ]qpqp eq

( ) ( )[ ]qpqp // eq ( ) ( )qpqp /// eq ( ) ( ) ( )[ ]qqppqp ///// .qp + eq ( )[ ] ( )[ ]ppqqqp /////

qp + eq ( ) ( )qpqp eq ( ) ( )[ ]qpqp eq( ) ( )qpqp / eq ( ) ( )qpqp /// eq ( )[ ] ( )[ ]qppqqp /////

qp eq ( ) ( )[ ] ( ) ( )[ ]qqppqqpp /////// qp eq ( )qp eq qp eq ( )qp eq ( )qp / eq

( ) ( )[ ]qqpp /// eq ( ) ( )[ ] ( ) ( )[ ]qqppqqpp ///////

{ }=5M este funcional complet

p eq pp qp eq ( ) ( )qqpp qp eq ( ) ( )qpqp qp eq [ ( ) qpp ] [ ( ) qpp ]qp eq [ ( ) qpp ] [ ( ) pqq ]

qp eq ( ) ( )pqqp eq ( ) ( )pqqp eq ( ) ( )pqqp eq [ ( ) ( )pqqp ] eq ( ) ( )pqqp eq[ ( ) qpp ] [ ( ) pqq ]

qp + eq [ ( ) ( )qqpp ] ( )qp

qp + eq ( ) ( )qpqp eq ( ) ( )[ ]qpqp eq( ) ( )[ ]qpqp eq ( ) ( )[ ]qpqp eq [ ( ) ( )qpqp ] eq ( ) ( )qpqp eq [ ( ) ( )qqpp ] ( )qp

qp / eq ( )qp eq q eq ( )qp eq ( )qp eq( ) ( )qpqp eq [ ( ) ( )qqpp ] [ ( ) ( )qqpp ].

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

16/33

16

Dupcum am artat mai sus, operatorii / i pot reda, fiecare, orice alt operator al

p . Mai mult, demonstrm mai jos urmtorul rezultat.

Teorem. Operatorii / i sunt singurii operatori binari care pot constitui, fiecare,mulimi funcional complete de operatori fundamentali.

Demonstraie. Presupunem c este un operator binar, altul dect / i , prinintermediul cruia orice alt operator poate fi definit. Fie pi qdouvariabile propoziionale.Dac pentru 1=p i 1=q vom avea 1=qp , atunci orice formul construit din p, q ioperatorul ar lua ntotdeauna valoarea logic1 dacvariabilele propoziionalepi qar luavaloarea logic 1. n acest caz negaia n-ar putea fi definit cu ajutorul acestui operator.Similar, dac pentru 0=p i 0=q vom avea 0=qp , atunci orice formul construitnumai din variabilelepi qi operatorul ar fi ntotdeauna fals, dacambele variabile iauvaloarea logicfals. Nici n acest caz negaia n-ar putea fi definitutiliznd doar operatorul .De aici rezult c pentru a putea reda negaia matricea operatorului trebuie s aibeurmtoarea form:

p q qp

1 1 01 00 10 0 1

Dac n ocurenele rmase (liniile 2 i 3) vom pune 1, 1 respectiv 0, 0, atunci vomobine matricele operatorilor / i . n schimb, dac vom pune celelalte posibiliti decombinare ale valorilor logice, respectiv 0, 1 sau 1, 0, vom obine, corespunztor, p i q ,adic qp eq p i qp eq q . n aceste din urmcazuri ar nsemna coperatorul binar

poate fi definit doar cu ajutorul negaiei. Am vzut nsmai sus cnegaia nu poate forma,

singur, o mulime funcional complet de operatori fundamentali (conjuncia n-a putut fidefinitdoar cu ajutorul negaiei!).

2.1.3.4. Demonstraii de completitudine funcional

n paragraful precedent am vzut c anumite mulimi de operatori pot traduceechiveridic orice alt operator. Ele au fost numite mulimi funcional complete. De data aceastavom demonstra cteva rezultate cu privire la completitudinea funcional.

Teorema 1. { }= ,M este funcional complet. (Echivalent: orice funcie de adevr

a p poate fi generatde o expresie care conine strict operatorii negaie i conjuncie).Demonstraie. Fie ( )npp ,...,1 o funcie n-ar de adevr. Dup cum tim, matricea

unei asemenea funcii va conine n2 linii, corespunztoare celor n2 interpretri diferite alevariabilelor sale. Numerotm aceste interpretri de la 1 la n2 . Fie acum o funcie ikf definit

astfel: ikf = kp , dac 1=kp

ikf = kp , dac 0=kp ,

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

17/33

17

unde ienumerinterpretrile ( ni 2,...,1= ), iar kenumervariabilele funciei ( nk ,...,1= ). Din

construcia acestei funcii rezultc, n interpretarea i, ikf este adevrat.

Construim acum o funcie ig , corespunztoare unei interpretri i, astfel:

ig = ini ff ...1

Din definiia funciei ikf i din definiia semantica conjunciei rezultcfuncia ig

este adevratn interpretarea i. ns ig este totodatfalsn orice altinterpretare, diferit

de interpretarea aleas, i. Acest lucru rezultdin faptul cntr-o interpretarej, diferitde i, celpuin o funcie ikf are un argument care difer de valoarea de adevr pe care kp o ia n

interpretarea i; adic funcia ikf ia valoarea logic fals i cu aceasta ntreaga conjuncie

ini ff ...1 devine fals.

Dup cum funcia ( )npp ,...,1 este sau nu o formul valid a p vom avea,corespunztor, urmtoarele doucazuri:

1. ( )npp ,...,1 ia valoarea logic adevrat pentru toate celen2 interpretri, adic este o

formul valid. n acest caz ( )npp ,...,1 poate fi scris, echivalent / echiveridic n forma:( ) ( ) ( )nnn pppppp ...... 221 . i astfel, funcia ( )npp ,...,1 a fostdefinitutiliznd doar i .

2. ( )npp ,...,1 nu este o formul valid. n acest caz fie mii ,...,1 cele m interpretri n care( )npp ,...,1 ia valoarea logicfals. Construim acum o funcie de adevr hastfel:

miiggh = ...

1

Funcia hva fi falsdoar daccel puin un conjunct este fals, echivalent, doar daccelpuin o funcie

rig ( mr ,...,1= ) este adevrat. Echivalent, funcia h va fi fals ntr-o

interpretare ri n care i ( )npp ,...,1 este fals, motiv pentru care vom pune ( )npp ,...,1 h= .

i deci i n acest caz funcia ( )npp ,...,1 a fost definitdoar pe baza i .Srevenim acum cu explicaii i exemple la teorema de mai sus.

Spresupunem cfuncia de adevr (i.e. formula) considerateste ( ) ( )21, ppqp = a creimatrice este:

1p 2p 21 pp 4,...,1=i

2,1=k ; ikf = kp , dac 1=kp

1i 1 1 1 ikf = kp , dac 0=kp

2i 1 0 0

3i 0 1 04i 0 0 1

Avem, aadar, pentru linia nti: 111 pf = , 212 pf = ; pentru linia a doua: 121 pf = ,

222 pf = , pentru linia a treia: 131 pf = , 232 pf = ; pentru linia a patra: 141 pf = , 242 pf = .

Iar acum funcia ig = ini ff ...1 :

1=i : =1g 111211211 === ppff

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

18/33

18

2=i : 1112122212 ==== ppffg

3=i : 1112132313 ==== ppffg

.4=i : 1112142414 ==== ppffg

Aadar, funcia ig este adevratn interpretarea i. Sartm c ig este falsn orice

alt interpretare. S lum funcia 2g citit n interpretarea 1. n acest caz,001212 === ppg (deoarece n interpretarea 1 12 =p i deci 02 =p ). Dup cum

rezultdin acest exemplu, funcia ig estefalsn orice altinterpretare, deoarece cel puin un

conjunct al funciei ig este fals (deoarece existcel puin un kastfel c kp ia valoarea logic

opusvalorii ei din interpretarea i) i astfel ntreaga conjuncie este fals.Pentru cele doucazuri mai sus menionate:1. ( )npp ,...,1 este valid. Fie ( ) ( ) ( )122121, pppppp = eq

( ) ( )1221 pppp eq ( ) ( )1221 pppp eq ( ) ( )122121 pppppp eq( ) ( )2211 pppp eq ( ) ( )2211 pppp . i deci ( )21,pp a fost definitdoar

prin intermediul i .

2. ( )npp ,...,1 nu este valid. Fie ( ) ( )[ ]321321 :,, pppppp .

1p 2p 3p 21 pp ( ) 321 ppp ( )[ ]321 ppp

1i 1 1 1 1 1 01 1 0 1 0 11 0 1 0 0 11 0 0 0 0 10 1 1 0 0 10 1 0 0 0 1

2i 0 0 1 1 1 00 0 0 1 0 1

Cele douinterpretri n care este falssunt prima i a aptea; le renumerotm 1i i

2i . Construim acum funcia mii ggh = ...1 , adic

( ) ( ) ( )321321321 ,,21 pppppppppggh ii === . S artm

acum, prin transformri sintactice, c ( )321 ,, ppp poate fi redatn expresia de mai sus, careconine doar operatorii i .

( )321 ,, ppp ( )[ ]321 ppp = eq {[ ( ) ( )2121 pppp ] 3p } eq( ) ( )[ ]321321 pppppp eq ( ) ( )321321 pppppp .

n cazul funciei ( ) ( )qppp =21, procedm similar.Adic ( ) ( )212121 ppppggh ii == eq ( ) ( )2121 pppp eq

( ) ( )1221 pppp eq 21 pp .Teorema 1 exprimun rezultat fundamental cu privire la completitudinea funcionala

mulimilor de operatori. Fiindcconjuncia poate fi definitutiliznd i sau i (i.e.( ) ( ) ( )qpqpqp dfdf == , rezult c { }= ,M i { }= ,M formeaz, de

asemenea, mulimi funcional complete de operatori. Mai mult, definiiile ppp df /= i

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

19/33

19

( )qpqp df /= ne aratc { }/=M formeazo astfel de mulime funcional complet. Iar

definiiile ppp df = i ( )qpqp df = ne arat c i i pot fi reduse la . ifiindc { }= ,M este o mulime funcional complet de operatori, rezult c i { }=M formeazo astfel de mulime.

Cum { }= ,M i { }= ,M sunt mulimi funcional complete, conchidem c

{ }= ,,M este funcional complet. Dei acest lucru rezult cu claritate din cele de maisus, vom demonstra acest fapt ntr-o teorem al crei rezultat este paralel celui coninut nTeorema 1.

Teorema 2. { }= ,,M este funcional complet. (Echivalent: orice funcie deadevr a p poate fi generatde o expresie care conine strict operatorii negaie, conjuncie

i disjuncie).Demonstraie. Vom considera din nou funciile ikf i ig , aa cum au fost definite n

Teorema 1. Dupcum funcia ( )npp ,...,1 este sau nu o formulnesatisfiabilvom avea, dinnou, doucazuri:

1. ( )npp ,...,1 este o formulnesatisfiabil. n acest caz ( )npp ,...,1 poate fi scrisechivalent / echiveridic n forma: ( ) ( ) ( )nn pppppp ...2211 .

Exemplu. ( )npp ,...,1 : ( ) ( )[ ] ( ){ }313221 pppppp ( ) ( )[ ] ( ){ }313221 pppppp eq ( ) ( )[ ] ( ){ }313221 pppppp

eq ( ) ( )[ ] ( )313221 pppppp eq ( ) ( )[ ] 313221 pppppp eq( ) ( ) ( ) ( )3132312231313121 pppppppppppppppp eq ( ) ( ) ( ) ( )33223311 pppppppp eq ( ) ( ) ( )332211 pppppp .

2. ( )npp ,...,1 este o formul satisfiabil (n sens larg). n acest caz, din celen2

interpretri vom alege, de data aceasta, acele interpretri (i.e. linii) n care ( )npp ,...,1 iavaloarea logicadevrat. Fie lii ,...,1 toate aceste interpretri. Construim acum o funcie

liiggh = ...

1

i punem, simplu, ( )npp ,...,1 = h .

Exemplu. ( )npp ,...,1 : ( )[ ]321 ppp , adicformula luatla exemplul Th1, cazul

2. n acest caz ( )npp ,...,1 = h =

( ) ( ) ( ) ( ) 321321321321 pppppppppppp ( ) 321 ppp ( )321 ppp . Putem verifica acest lucru, obinnd acelai rezultat prin transformri

sintactice corecte ale formule ( )npp ,...,1 .

( )[ ]321 ppp eq ( ) ( )[ ]{ }32121 ppppp eq ( ) ( )[ ] 32121 ppppp eq ( ) ( )[ ] 32121 ppppp eq ( ) ( ) ( ) ( ) 322122111 ppppppppp eq ( ) ( ) 32121 ppppp .

Pentru a ajunge la rezultatul cutat va trebui ca n fiecare disjunct s introducemvariabilele care lipsesc. n exemplul nostru, n primi doi disjunci lipsete variabila 3p iar n

ultimul lipsesc variabilele 1p i 2p . DacD este disjunctul considerat, atunci introducerea

unei variabile ip se face dupurmtoarea relaie:

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

20/33

20

Deq ( )ii ppD eq ( ) ( )ii pDpD .Faptul c aceast relaie are loc este uor de remarcat. Cci ii pp ia ntotdeauna

valoarea logic adevrat, iar adugarea unui argument adevrat unei conjuncii (D fiind oconjunciede variabile propoziionale negate sau nenegate) nu-i altereazvaloarea de adevr.

Pe baza acestei relaii avem:

21 pp

eq ( ) ( )3321 pppp

eq ( ) ( )321321 pppppp

21 pp eq ( ) ( )321321 pppppp

3p eq ( ) ( )1313 pppp eqeq ( ) ( ) ( ) ( )213213213213 pppppppppppp n fine ( )npp ,...,1 ( ) ( ) ( )= 321321321 ppppppppp

( ) ( ) ( )321321321 ppppppppp , de unde, prin reordonareadisjuncilor (pe baza comutativitii), dupce am eliminat disjuncii care se repet, obinemrezultatul dorit.

Exerciii.

1. Se d urmtorul ir de valori de adevr, care reprezint valorile unei funcii deadevr binare ( )21,pp , n asignarea standard: 1100.a) S se determine, pe baza Th 1 i Th2 de mai sus, dou expresii, una care conine strictoperatorii i iar cealaltoperatorii , i i care pot genera funcia dat.

b) Sse demonstreze, prin transformri sintactice corecte, echiveridicitatea ( )21,pp eq 1p ,n ambele cazuri.

Soluie. ( )21,pp este prependena, adic

1p 2p ( )21,pp

1 1 11 0 1

0 1 00 0 0

a) n acord cu Th 1 ( )21,pp ( ) ( )2121 pppph == , iar n acord cu Th 2,( )21,pp ( ) ( )2121 pppph ==

.

b) ( ) ( )2121 pppp eq ( ) ( )2121 pppp eq ( )221 ppp eq 1p .Similar pentru cealaltexpresie.

2. Aceleai cerine ca la exerciiu 1 pentru funciile p , qi q .

3. Se dau urmtoarele funcii de adevr:

1 9 ( )[ ] ( )rprqp = /( )[ ]/2 rqp += [ ( ) rqp ]( )[ ] ( )rprqp = /3 ( ) ( )[ ] ( )rprpqp =4

9n cele ce urmeazvom omite menionarea argumentelor dupsimbolul , iar pentru variabile vom utiliza

simbolurile qp, ,..., n loc de 21,pp ,...

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

21/33

21

( ) ( ) ( )[ ]qpqpqp +=5 a) Construii matricele acestor funcii de adevr.

b) Determinai, n fiecare caz, dou expresii, una care conine strict operatorii i iarcealaltoperatorii , i i care pot genera funcia dat.c) Verificai acest fapt prin transformri sintactice adecvate.d) Pentru 1 construii o expresie echiveridicn care operatorul nu mai apare; pentru

2 , una n care + i nu mai apar; pentru 3 , o expresie care nu conine iar

pentru 4 i 5 construii expresiile echiveridice corespunztoare care nu conin .

2.1.4. Procedee de decizie n p

Aa cum am vzut n paragraful 2.1.2.1, formulele p pot fi formule ntotdeauna

adevrate (valide), uneori adevrate (satisfiabile) sau niciodat adevrate (nesatisfiabile). npractic este necesar ca, de fiecare dat, s putem spune crei clase i aparine o formuloarecare a p . nainte de toate ne intereseazsputem decide daco formula p este valid

sau nu.Definiie 1. A decide n p nseamn a gsi un procedeu efectiv prin care, ntr-un

numr finit de pai, sse poatstabili daco formularbitrara p este validsau nu.

Aa cum vom vedea mai jos, prin aplicarea oricruia din procedeele descrise vomputea stabili, n cazul n care formula este nevalid, dacformula respectiveste satisfiabilsau nu.

2.1.4.1. Procedeul matriceal

Procedeul matriceal este cel descris n paragraful 2.1.2.3. Decizia cu ajutorul acestuiprocedeu o facem n acord cu definiiile 1 3 ale acelui paragraf. S mai considerm unexemplu simplu.

Fie ( )[ ] rqp /: [ ( ) qrp ]n acord cu algoritmul prezentat n 2.1.2.3 matricea formulei este:

p q r q qp / ( ) rqp / r rp ( ) qrp

1 1 1 0 1 1 0 0 0 01 1 0 0 1 0 1 0 0 11 0 1 1 0 1 0 0 0 01 0 0 1 0 1 1 0 0 00 1 1 0 1 1 0 1 1 10 1 0 0 1 0 1 0 0 10 0 1 1 1 1 0 1 0 00 0 0 1 1 0 1 0 0 1

n acord cu definiia 3 formula este satisfiabil (realizabil), deoarece coloanafinal, care redvalorile logice ale formulei , pentru toate cele 8 interpretri ale variabilelorei, conine valori neomogenede adevr.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

22/33

22

2.1.4.2. Reductio test

Indiscutabil, procedeul matriceal devine inconvenabil atunci cnd numrul variabilelorpropoziionale crete. De aceea, pentru verificarea validitii unei formule a p , putem

proceda prin reducere la absurd, n urmtorul fel. Presupunem c formula dat, , estenevalid. Exist, aadar, o interpretare a variabilelor ei care falsific formula . Dac nncercarea de a gsi o astfel de interpretare ajungem la o contradicie, atunci formula nu poatefi falsificati deci este o formulvalid. n caz contrar, este nevalid. Acest procedeu senumete reductio test.

Exemplu.( ) ( ) ( )[ ]qrprqp :

Presupunem cpoate fi falsificat. Aceasta nseamnc ( ) 1= qp , ( ) 1=pr i( ) 0= qr . Din falsitatea formulei qr deducem 0=r i 0q= . Cum ( ) 1=pr iar 0=r ,rezult c 1p= . Dac transferm aceste valori logice n antecedentul implicaiei, qp ,rezult c implicaia qp este adevrat (n acord cu presupunerea fcut) atunci cnd

1=p i 0=q . Contradicie! i deci nu poate fi falsificat, echivalent este o formul

valida p .

Exerciii. Decidei cu ajutorul reductio testasupra urmtoarelor formule:( ) ( )[ ] ( )rprqqp :1 ( )[ ] ( )rprqp /:2

( ) rqqp +:3 ( )[ ] ( )rprqp :4

2.1.4.3. Procedeul Quine

Este un procedeu de decizie mai elegant dect cel matriceal, mai ales atunci cndnumrul variabilelor propoziionale este mare.

Procedeul Quine10se bazeazpe asignarea succesivde valori de adevr variabilelorformulei considerate i pe aplicarea regulilor de adevr ale operatorilor logici din formul. Deregul, pentru a simplifica ct mai mult formula care trebuie evaluat se alege mai ntivariabila care apare cel mai frecvent i i se atribuie, alternativ, valorile logice 1, respectiv 0.Dac n felul acesta nu se ajunge la o valoare de adevr determinat, procedeul continucuvariabila urmtoare, pn cnd se obin doar valori de adevr. Decizia o vom face similar

procedeului matriceal, adicpe baza definiiilor 1 3 din 2.1.2.3.

Formularea regulilor de adevr ale operatorilor logici o facem pe baza matriceioperatorului respectiv. Fiecare operator este explicitat prin dou reguli, una pentru cazul ncare un argument este adevrat iar cealaltpentru cazul n care un argument este fals. Prinaplicarea unei reguli asupra formulei care-l conine, formula se reduce fie la o valoare deadevr, fie la cellalt argument negat sau nenegat.

10Cf. W.v.O. Quine,Methods of Logic, Holt, Rinehort and Winston, Inc., 1972.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

23/33

23

Regulile de adevr ale operatorilor logici.

: ( ) . 1R . Dacntr-o conjuncie un argument este adevrat, atunci valoarealogica conjunciei se reduce la valoarea celuilalt argument.

2R . Dacntr-o conjuncie un argument estefals, atunci valoarea logica conjunciei se reduce la fals.

: ( ) (Exerciiu)

: ( ) 1R . Dac ntr-o implicaie un argument este adevrat, atunci valoarealogica implicaiei se reduce la valoarea consecventului.

2R . Dacntr-o implicaie un argument estefals, atunci valoarea logica implicaiei se reduce la valoarea negata antecedentului.

Formularea acestor reguli pentru implicaie o facem cu uurin comparnd, nmatricea implicaiei, valorile funciei cu valorile argumentelor ei. Pentru 1R , de exemplu,lum cazurile (i.e. liniile) n care (cel puin) un argument este adevrat, adicprimele trei linii.Observm c valorile funciei, pentru primele trei categorii de asignri, coincid cu valorileconsecventului. Pentru 2R procedm similar: lum liniile n care (cel puin) un argument estefals, adic liniile 2, 3 i 4, i observm c valorile funciei coincid cu valorile negate aleantecedentului. La fel procedm i n stabilirea regulilor operatorilor , i # (Exerciiu).

: ( ) 1R . Dacntr-o echivalenun argument este adevrat, atunci valoarealogica echivalenei se reduce la valoarea celuilalt argument.

2R . Dac ntr-o echivalen un argument este fals, atunci valoarealogica echivalenei se reduce la valoarea negata celuilalt argument.

:+ ( )+ (Exerciiu)

:/ ( )/ 1R . Dac ntr-o incompatibilitate un argument este adevrat, atuncivaloarea logica incompatibilitii se reduce la valoarea negata celuilalt argument.

2R . Dacntr-o incompatibilitate un argument este fals, atunci valoarealogica incompatibilitii se reduce la adevrat (de ce?)

: ( ) (Exerciiu)Remarc.Cele ase funcii din tabelul lui Wittgenstein ( ),,,,, qpqp rmn n afara

consideraiilor, deoarece ele nu coreleazn vreun fel valorile logice ale argumentelor lor.Exemplu. Fie ( )[ ] ( )qprqp /: .

1=p 0=p ( )[ ] ( )qrq /11 ( )[ ] ( )qrq /00

( ) qrq ( ) 10 r 1=q 0=q 11

( ) 11 r ( ) 00 r 11r 01

1 0

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

24/33

24

Exerciii. Decidei cu ajutorul procedeului Quine asupra urmtoarelor formule ale p :

( ) ( ) ( )[ ]rprqqp :1 ( ) ( )[ ] ( )rprqqp :2 ( )[ ] ( )[ ]tspqqp + //:3

:4 [ ( ) rqp ] ( )[ ]qpt ( ) ( )[ ] pqpqp :5 ( ) ( )[ ] ( )ssrrqp //:6 ( ) ( )[ ] ( ) ( )[ ]sqrpsrqp :7

Remarc. Artai c formula din 7 rmne o formul valid a p dacoperatorul

din consecventul implicaiei este nlocuit cu oricare din urmtorii operatori binari ai p :

+ ,/,,,,,, ,#.

2.1.4.4. Formele normale n p

Definiie 1. Formele normale sunt expresii a cror structursintacticne permite sdecidem asupra unei formule a p .

Aadar, atunci cnd decidem cu ajutorul formelor normale nu mai asignm valori deadevr variabilelor propoziionale, ci construim nite expresii, logic echivalente formuleiasupra creia vrem sdecidem, i decidem doar pe baza configuraiilor de simboluri. n toatetransformrile sintactice efectuate dimensiunea semantice una implicit.

n logic, n general, formele normale sunt de o mare varietate. Lucrarea de fa trateazdoar cazul n care n aceste construcii apar doar operatorii ,, , numii operatori

booleeni (motiv pentru care ele se mai numesc i forme normale booleene).Formele normale booleene se constituie n douclase distincte, dupcum operatorul

principal (cel care dnumele expresiei) este conjuncia sau disjuncia.

Definiie 2. O formula p este n forma normalconjunciv(abreviat: c) dac

are forma unei conjuncii n ...1 ( )1n , n care fiecare conjunct i ( )ni ,...,1= areforma unei disjuncii

mii ...

1( )1im , ai crei membri sunt variabile propoziionale

nenegate sau negate o singurdat.

Teorema 1. Orice formula p admite o formnormalconjunctivlogic echivalent

(i. e. c ).

Demonstraie. Demonstraia acestei teoreme o vom face, simplu, indicnd algoritmul

aducerii unei formule date la forma normalconjunctiv. Algoritmul are urmtorii pai:1. Se nlocuiesc toate subformulele care conin ali operatori dect operatorii ,, cuexpresii echivalente care conin doar aceti operatori. n felul acesta obinem o formul,echivalent formulei date, dar care conine numai operatori booleeni. De exemplu, dac este formula ( )[ ] ( )qqrqp / , atunci avem, corespunztor, subformulele qp i

qq / care trebuie transformate echivalent n qp i ( )qq . i obinem astfel formula( )[ ] ( )qqrqp :1 , echivalentformulei ; aadar 1 .

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

25/33

25

2. Se nlocuiesc toate subformulele n care negaia neago expresie care conine unoperator binar, cu expresii echivalente n care negaia neagnumai variabile propoziionale.

n 1 , ( )qq devine qq , i deci 1 devine, echivalent,( )[ ] ( )qqrqp :2 . i deci 21 .

3. Se nlocuiesc toate subformulele de forma ip , unde ip este o variabil

propoziional, cu ip . Firete, dacavem mai multe negaii, eliminarea lor se face astfel nctceea ce pstrm este o variabil propoziional nenegat sau negat o singur dat (cf.formulelor 1 i 2, 2.1.2.3). i obinem astfel ( )[ ] ( )qqrqp :3 , astfel c

32 .

4. Se nlocuiesc succesiv toate acele subformule de forma ( )321 cu expresiileechivalente corespunztoare, de forma ( ) ( )3121 . i n felul acesta din 3 obinemformula echivalentei: ( ) ( )qqrqqqpc : , i care este, n acord cu Def. 2,forma normal conjunctiv a formulei iniiale . i astfel c 3 . De unde, pe baza

tranzitivitii echivalenei obinem c .

Remarc. n aceste transformri echiveridice adesea aplicarea algoritmului nu esteobligatorie, deoarece se pot executa simultan mai muli pai ai algoritmului.

Teorema urmtoare ne spune cum stabilim cu ajutorul formelor normale conjunctivedaco formula p este validsau nu.

Teorema 2. O formul a p, aflat n forma normal conjunctiv, este o formul

valida p ddac fiecare conjunct conine cel puin o variabilpropoziionalatt negat

ct i nenegat.Demonstraie. Dac formula este valid, atunci ea este adevrat n orice

interpretare a variabilelor sale. Cum c i , rezultc c este o formulvalid, fapt

evident deoarece fiecare conjunct conine formula valid ii pp . Reciproc, dac fiecare

conjunct al formulei c are forma mii pppp ......1 , atunci, pe baza matriceioperatorului conchidem c un astfel de conjunct este ntotdeauna adevrat (i.e. valid),deoarece conine disjuncia valid ii pp . i astfel, indiferent de asignrile fcute celorlalte

variabile propoziionale din conjunct, el este unul valid. i astfel c este o formul valid.

nseste echivalentcu c . i deci este o formulvalid.

Dac, dimpotriv, c nu are forma menionatde teorem, adiccel puin un conjunct

nu conine o variabil propoziional att negat ct i nenegat, atunci este nevalid(argumentai).

Definiie 3. O formula p este n forma normalconjunctivperfect(abreviat:xc ) dac este n forma normal conjunctivi fiecare conjunct conine toate variabilele

propoziionale ale formulei, negate sau nenegate.Teorema 3. Orice formul a p admite o formnormal conjunctivperfect logic

echivalent(i.e. xc ).

Demonstraie. Vom proceda ca mai sus, la Th. 1, indicnd algoritmul aducerii uneiformule date la forma normalconjunctivperfect. Potrivit teoremei 1, formula admiteforma normal conjunctiv c . Dac unul dintre conjunci, i nu conine variabila

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

26/33

26

propoziional kp , atunci aceastvariabilse introduce n conjunctul i pe baza urmtoarei

transformri echivalente: ( )[ ] ( ) ( )[ ]kikikkii pppp . Pe baza acestorechivalene putem introduce, n fiecare conjunct, toate variabilele formulei . Forma normalconjunctivperfectastfel obinuteste echivalent cu c i deci cu (prin tranzitivitatea

). Aadar, o formula p este validddacforma ei normalconjunctivperfecteste

valid.n formula c , din exemplul de mai sus, n primul conjunct lipsete riar n al doilea q.

Introducem aceste variabile, corespunztor, n modul mai sus indicat.Primul conjunct, qqqp , devine, echivalent, ( ) ( )rrqqqp ,

respectiv ( ) ( )rqqqprqqqp . Al doilea, qqr , devine( ) ( )ppqqr , adic ( ) ( )pqqrpqqr . i astfel,

xc : ( ) ( )rqqqprqqqp ( ) ( )pqqrpqqr .

Definiie 4. O formula p este n forma normaldisjunctiv(abreviat: d ) dac

are forma unei disjuncii n ...1 ( )1n , n care fiecare disjunct i ( )ni ,...,1= are formaunei conjuncii

mii ...

1( )1im , ai crei membri sunt variabile propoziionale nenegate

sau negate o singurdat.Teorema 4. Orice formula p admite o formnormaldisjunctivlogic echivalent

(i.e. d ).

Demonstraie. Similar teoremei 1, vom indica algoritmul aducerii unei formule date laforma normaldisjunctiv. Primii 3 pai sunt cei menionai la teorema 1.

Pasul 4. Se nlocuiesc succesiv toate acele subformule de forma ( )321 cuexpresiile echivalente corespunztoare, de forma ( ) ( )3121 . n felul acesta obinemforma normaldisjunctiv, d , a formulei , astfel c d .

Din formula din exemplul precedent (din pasul 3) ( )[ ] ( )qqrqp obinemastfel, n pasul 4, ( ) ( ) qqrqrpd : .Dacprin intermediul formelor normale conjunctive putem decide daco formuleste

valid sau nu, cu ajutorul formelor normale disjunctive putem testa nesatisfiabilitateaformulei n cauz.

Teorema 5. O formul a p, aflat n forma normal disjunctiv, este o formul

nesatisfiabil a p ddac fiecare disjunct conine cel puin o variabilpropoziionalatt

negatct i nenegat.Demonstraie. Dac formula este nesatisfiabil, atunci ia valoarea logic fals

pentru orice interpretare a variabilelor sale. Cum d , rezult c i d este

nesatisfiabil. ns cum d este o disjuncie de conjunci, rezult c fiecare disjunct este

nesatisfiabil, fapt evident din construcia lui sintactic, deoarece este o conjuncie care conineconjuncia nesatisfiabil ii pp . Reciproc (similar).

Dac, dimpotriv, d nu are forma menionatde teorem, adiccel puin un disjunct

nu conine o variabil propoziional mpreun cu negaia ei, atunci formula nu estenesatisfiabil(de ce?).

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

27/33

27

Exemplu. ( )[ ] ( ) ( )[ ]rqrqqqp /: Aducem formula la forma normaldisjunctiv.1. ( )[ ] ( ) ( )[ ]{ }rqrqqqp ( ) ( ) ( )[ ]rqrqqqp 2. ( ) ( ) ( )[ ]rqrqqqp

3. ( ) ( ) ( )[ ]rqrqqqp 4. ( ) ( ) ( )[ ] drqrrqqqqp Aadar, formula este nesatisfiabil.Remarc 1. Dac o formul a p nu satisface nici teorema 2 i nici teorema 5,

atunci este o formulsatisfiabil.

Definiie 5. O formula p este n forma normaldisjunctivperfect(abreviat:xd ) dac este n forma normal disjunctivi fiecare disjunct conine toate variabilele

propoziionale ale formulei, negate sau nenegate.Teorema 6. Orice formul a p admite o formnormal disjunctiv perfect logic

echivalent(i.e. xd ).Demonstraie. Vom proceda similar demonstraiei teoremei 3 ndicnd algoritmul

construciei formulei xd . Potrivit teoremei 4, orice formul a p admite o form normal

disjunctivlogic echivalent. Dac, o datconstruit d , unul dintre conjunci, i , nu conine

o variabilpropoziional jp , atunci vom introduce aceastvariabiln disjunctul respectiv,

pe baza urmtoarelor echivalene: i [ )jji pp ] [ ) )jiji pp ]. n felulacesta putem introduce, n fiecare disjunct, variabilele care apar n formula , obinnd astfel

xc astfel nct

xc .

n exemplul de mai sus, fiecare dintre cei trei disjunci are o variabillips. n primuldisjunct, de exemplu, putem introduce variabila r astfel:

( )qqp ( ) ( )[ ] ( ) ( )[ ]rqqprqqprrqqp .Similar procedm cu ceilali disjunci i, n final, construim xd (exerciiu).

n fine, ncheiem acest paragraf cu cteva consideraii privitoare la relaia dintreformele normale perfecte i relaia de consecinsemantic.

Pe baza formelor normale perfecte putem determina:a) toate consecinele semantice ale unei formule date

b) toate premisele unei formule daten primul caz, construim mai ntiforma normalconjunctivperfect, xc , a formulei

date, . Consecinele semantice ale formulei vor fi:a) fiecare conjunct al xc

b) fiecare conjuncie de conjunci din xc c) formula ca atare, xc .n al doilea caz, construim mai nti forma normal disjunctiv perfect, xd , a

formulei date, . Vor fi premise ale formulei:a) fiecare disjunct al xd

b) fiecare disjuncie de disjunci din xd

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

28/33

28

c) formula ca atare, xd .Remarc2. O datconstruitmatricea unei formule, formele normale perfecte pot fi,

la rndul lor, construite direct de pe matrice. Fie, de exemplu, formula din 2.1.4.1. Dacdin matricea acestei formule alegem acele linii n care ia valoarea logicadevrat, atunciforma normaldisjunctivperfecta formulei se obine legnd conjunctiv variabilele fiecreilinii dintre cele alese (n raport cu valoarea logica variabilei respective) i, apoi, conectnddisjunctiv liniile. Pentru formula din 2.1.4.1. avem:

( ) ( ) ( ) ( )rqprqprqprqpxd : Pentru construireaformei normale conjunctive perfecteprocedm dupcum urmeaz.

Alegem acele linii n care ia valoarea logic fals, legm disjunctiv variabilelepropoziionale n raport invers cu valoarea lor logic, iar apoi conectm conjunctiv acestelinii. Pentru formula din 4.1 avem:

( ) ( ) ( ) ( )rqprqprqprqpxc :

Dacaducem formula la xd ixc vom obine, corespunztor, expresiile de mai sus

(exerciiu).

Exerciii.

a) Se dau urmtoarele formule ale p :

( ) ( ) ( )[ ]rqrpqp :1 ( )[ ] ( )rprqp + /:2 ( )[ ] ( )rrrqp :3 ( ) ( )qpqp :4 ( )[ ] prrp + /:5

1.

Decidei cu ajutorul procedeului matriceal asupra acestor formule.2. Pe baza matricelor astfel obinute construii formele normale perfecte alelor.

3. Verificai rezultatul astfel obinut, cu ajutorul procedeului formelornormale.

4. Determinai toate consecinele i toate premisele fiecrei formule.b) Ce corelaie existntre funciile hi h din 3.4 i formele normale perfecte?

2.1.5. Teoreme fundamentale ale p

Svedem, n fine, n acest paragraf, cteva teoreme importante ale p , altele dect

cele menionate n paragrafele anterioare.S lum mai nti un exemplu. Formula ( )pqp : este o formul valid a p

(verificai acest lucru). Dacn aceastformuln locul variabileip, n cele douocurene alesale, vom pune o formuloarecare a p , fie aceasta p/r, iar n locul variabilei qvom pune

rq , atunci vom obine urmtoarea formula p : ( ) ( ) ( )[ ]rprqrp // . Cum formula este o formul valid i formula obinutdin , prin substituiile menionate, este tot o

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

29/33

29

formulvalid(exerciiu). Aadar, orice formulde formaformulei este o formulvalid.Iar acest lucru este valabil nu numai despre formula de mai sus, ci despre oriceformulvalida p n care facem substituii.

Teorema substituiei. Fie ( )npp ,...,1 o formul a p care conine variabilele

propoziionale npp ,...,1 . Fie ( )nnpp /,...,/ 11

formula obinut din ( )npp ,...,1 prinsubstituia variabilelor npp ,...,1 n toate ocurenele lor, cu formule arbitrare n ,...,1 .

AtunciDac , atunci .

Demonstraie.Dac , atunci ia valoarea logicadevrat pentru orice interpretare a variabilelor

npp ,...,1 ; aadar, valoarea logic a formulei este independent de asignrile fcute

variabilelor ei. ns, n , n locul variabilelor npp ,...,1 intrformulele n ,...,1 care, pentru

orice interpretare a variabilelor care le conin, iausuccesivvalorile 1 i 0, adicvalorile logiceposibile ale celor nvariabile propoziionale din . i deci i formula este indiferent la

aceste valori logice ale formulelor n ,...,1 ; aadar

este o formulvalid.Remarci. 1. Conversa acestei teoreme nu este n general valabil. Formula

( ) ( )qpqp este o formul valid a p . Fie qp :1 iar qp:2 . Dac n locul

acestor formule punem, corespunztor, variabilele r i s, atunci, prin substituia fcut,obinem formula sr a p .

2. Enunul teoremei substituiei conine ideea substituiei simultane avariabilelor propoziionale npp ,...,1 cu formule arbitrare n ,...,1 . nsntr-o formulvalid

a p putem alege orice numr de variabile n vederea substituirii lor, nu neaparat toate. n

formula de mai sus puteam s-l substituim pepcup/ri att. qputea rmne q(de altfel, nacest din urmcaz, puteam considera substituia redundanta variabilei qcu ea nsi).

3. Prin substituie, dintr-o formul valid a p putem construi oinfinitate de formule ale p . Prin teorema substituiei i aceste formule vor fi valide, fra fi

nevoie sle testm validitatea.

S lum acum urmtorul exemplu. Fie ( ) ( )[ ] ( )qprqqp /: , o formula

p care conine subformula : q . Fie ( ) ( )[ ] ( )qprqqp /: formula demai sus n care n locul subformulei am pus formula : q . Atunci, cum este

echivalentcu , rezultc (exerciiu). Aceasta este teorema nlocuirii, pe care am

utilizat-o n cteva rnduri n paragrafele anterioare 11, chiar dacn-am menionat-o.

Teorema nlocuirii (echivalenilor).Dac este o subformula lui (simbolic )iar se obine din nlocuirea a zero sau mai multe ocurene ale subformulei n cu o

formul, atunci

Dac , atunci .

Demonstraie(inducie pe gradul formulei ).

11Comp. Formele normale n p .

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

30/33

30

n demonstraia acestei teoreme ne limitm la cazul n care n nlocuim o singurocurene a subformulei cu formula . n felul acesta nu se restrnge nicidecumgeneralitatea teoremei, deoarece, evident, n cazul n care nlocuim zero ocuren e alesubformulei cu , atunci este tocmai formula , iar dacvrem snlocuim mai multe

ocurena ale lui cu n formula , atunci repetm aplicarea teoremei n varianta pe care-o

demonstrm.1. nu conine nici un operator. este aadar o variabil propoziional, p,subformula este tot p, iar este . Cu ipoteza din enunul teoremei (i.e. ),

teorema nlocuirii are loc.2. Presupunem cteorema are loc pentru orice formulal crei grad este mai mic

dect n ( )1n i artm, n pasul inductiv, cteorema are loc i pentru o formulal creigrad este n.

n acord cu definiia conceptului de formul, are, n acest caz, una din urmtoareleforme: a) ; b) , unde denotorice operator binar menionat n definiie.

n toate aceste cazuri gradul formulelor i este mai mic dect ni potrivit ipotezeiinduciei, teorema are loc pentru formulele i ; aadar

Dac , atunci 1. i 2. n cazul a) are forma . i deci dac , atunci (prin ipoteza

induciei). ns ( ) ( ). i astfel, dac , atunci ,

adic .

n cazul b) are forma . Prin ipoteza induciei teorema are loc pentru i . iastfel obinem ) ) (prin Remarc 4.3), unde este ( ) , iar este ( ) .

Remarc. ntre substituie i nlocuire existurmtoarele deosebiri:a) Operaia substituiei nseamn substituia unei / unor variabile propoziionalecu formule

arbitrare ale p (nu substituim formule arbitrare cu formule arbitrare!). n cazul nlocuirii, ncazul unei subformule din formula dat punem o formul arbitrar a p (sub asumpia

echivalenei lor).b) Substituia unei variabile propoziionalepcu o formularbitrara p trebuie realizat n

toateocurenele variabileip; nlocuirea, n schimb, se poate realiza numeric arbitrar.

Teorema de normalitate. Pentru 1n : nn ,,..., 11 ddac 11,..., n n .

Demonstraie (reductio ad absurdum)a) Dac nn ,,..., 11 atunci 11,..., n n .

Presupunem 1. n ,...,1 i 2 non 11,..., n n . Din 1 deducem cpentru orice

interpretare a variabilelor propoziionale care apar n n ,...,1 , are loc: 3. dac

1...1 = n , atunci 1= (prin definiie). Din 2 deducem c exist o interpretare a

variabilelor formulelor date astfel c4. 1... 11 = n i 5. 0=n . Din 5 deducem 6.

1=n i 7. 0= . ns7 contrazice 3, cci dac 1=n , atunci 1...1 = n i deci 1= .

b) Dac 11,..., n n , atunci n ,...,1 .

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

31/33

31

Presupunem 1. 11,..., n n i 2. non n ,...,1 . Din 1 deducem c n orice

interpretare a variabilelor din formulele date avem: 3. dac 1... 11 = n atunci

1=n . Iar din 2 deducem cexisto interpretare astfel c4. 1...1 = n i 5. 0= .

ns, sub asumpia adevrului formulelor 11,..., n (din 3) am dedus 1=n . Cum

1=n (din 4) rezultc 1= , ceea ce contrazice 5.

Corolar. Pentru 1n : nn ,,..., 11 ddac ( )( )...... 11 nn .

Demonstraie (prin n aplicri succesive ale teoremei de normalitate). Semnificaiaacestui corolar rezid n aceea c problema referitoare la consecinele semantice ale uneimulimi de formule se reduce la problema ce formule sunt valide.

Teorema (*).Fie ( )npp ,...,1 o formula p, care conine variabilele propoziionale

npp ,...,1 negate sau nenegate. Fie formula care rezult din prin nlocuirea

operatorilor formulei cu dualii corespunztori i a variabilelor propoziionale npp ,...,1 cunegaiile lor. Atunci, (echivalent: ).

Demonstraie.Este suficient s demonstrm teorema pentru cazul n care singurii operatori binari

sunt i , cci utiliznd orice formul a p poate fi exprimatprintr-o formul care

conine doar aceti trei operatori (cf. Th. 2, 2.1.3.4). O datadusntr-o asemenea form, pebaza legilor lui De Morgan (15, 27)12negaia unei formule care conine operatori binari sedeplaseaz succesiv n interiorul formulei, permutnd reciproc operatori binari ai formulei.Utiliznd legile eliminrii negaiilor multiple (1, 2) simplificm formula astfel nct orice

variabilpropoziionala formulei va fi negatcel mult o dat.

Exemplu.Fie ( ) rqp : . Atunci ( ) rqp + /: .Transformm formula ntr-o formulechiveridic(i deci echivalent) care conine

doar operatorii , i .( ) rqp : eq ( ) ( )[ ]{ }rqpqp eq ( ) ( )[ ] rqpqp eq

( ) ( )[ ] rqpqp eq ( ) ( ) rqpqp eqeq ( ) ( ) rqpqp .

La fel procedm cu .

( ) rqp + /: eq ( ) ( )[ ]{ }rqpqp eq( ) ( )[ ] rqpqp eq ( ) ( )[ ] rqpqp eq

( ) ( )[ ] rqpqp eq ( ) ( )[ ] rqpqp

Aceastdin urm formulpoate fi mai departe transformat echiveridic, astfel nctnegnd formula , de mai sus, sobinem exact formula . Aadar,

12Cifrele indicformulele corespunztoare din lista paragrafului 2.1.2.3.

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

32/33

32

( ) ( )[ ] rqpqp eq ( ) ( ) ( ) ( )qqqpqppp r eq( ) ( )qpqp r .

Acum, dacnegm formula obinem: : ( ) ( )[ ]rqpqp eq ( ) ( )[ ]{ }rqpqp (prin 5) eq

eq ( ) ( )[ ] rqpqp eq ( ) ( ) rqpqp eqeq ( ) ( ) rqpqp eq ( ) ( ) rqpqp eq .

Teorema dualitii.Fie , formule ale p n care apar variabilele propoziionale npp ,...,1 , negate sau

nenegate. Fie i formulele care rezult din , respectiv , nlocuind operatoriilogici cu dualii corespunztori. Atunci:

1.Dac , atunci .2.Dac , atunci .3.Dac , atunci .

4.Dac , atunci

.

Demonstraie. Pentru considerentele menionate n demonstraia teoremei precedente,vom considera csingurii operatori binari ai formulelor , sunt i .

1. Presupunem . Prin Teorema (*) i exerciiul 3b din 2.1.2.4 rezult .ns dac n aceast formul valid, , substituim simultan variabilele propoziionale

npp ,...,1 cu negaiile lor, atunci obinem formula , de asemenea valid (prin teorema

substituiei). Iar dacn aceastformuleliminm negaiile multiple, obinem formula valid

. Aadar, .

Exemplu. Fie ( ) ( ) ( )[ ]rprqqp : ; atunci : ( ) ( ) ( )[ ]{ }rprqqp ; prin Th (*) i exerc. 3b (paragr.

2.1.2.4). : ( ) ( ) ( )[ ]{ }rprqqp ; prin Th substituiei : ( ) ( ) ( )[ ]{ }rprqqp ; prin eliminarea negaiilor multiple

(Verificarea validitii formulei : exerciiu).

2. (similar).

3. Presupunem antecedentul condiionalului . i astfel (prin

contrapoziia implicaiei). i deci (cci dacn formulele i nlocuimoperatorii cu dualii corespunztori i variabilele propoziionale cu negaiile lor, atunciobinem, prin Th (*), formulele echivalente i , adic i ; de unde, prin

exerc 3b, obinem ). i astfel (prin th. substituiei) i deci (eliminarea negaiilor multiple).

4. (similar).

7/13/2019 I.D.D. Psihologie Curs Logica Cap. 2 Logica Simbolica

33/33

Exerciii.

1. Construii, pe baza teoremei (*), corespunztoare urmtoarelor formule:( )[ ] rrqp /:1 ( )[ ] ( )qprqp +:2

:3 [ ( ) rqp

] ( )[ ]rqp

/( )[ ] rrqp :4

2. Artai c n fiecare caz n parte.

3. Fie ( ) ( )[ ]( )pprrqp /: . Aplicai teorema dualitii formulei iartai, cu ajutorul procedeului matriceal crelaia condiional: dac , atunci areloc.