Vraciu - Logica 1 (Logica Propozitiilor).pdf

7/21/2019 Vraciu - Logica 1 (Logica Propozitiilor).pdf

1/135

Capitolul I

Logica propoziiilor

1. Introducere n sintaxa i semantica logicii propoziiilor

n logica clasic se consider acele propoziii(enunuri, expresii)care apar i n

vorbirea curent i care pot transmite o valoare de adevr. Astfel, n logic, nu vom

considera ca propoziii acele enunuri de tip exclamativ sau interogativ cum ar fi

Au m doare sau !um ai reuit"

#e asemenea definiiile nu sunt considerate propoziii. Astfel enunul$

%n numr ntreg divizibil cu & se numete numr par.

nu este o propoziie, dar$

'rice numr par este divizibil cu &.

este o propoziie i anume este o propoziie adevrat. Alte exemple de propozitii pe care

le putem considera n logic sunt$isica este un animal.,

ucureti este capitala *taliei.,

+ < ,

*n orice triung-i bisectoarea mparte latura opus n pari egale.

*ntuitiv putem spune c prima i a treia dintre enunurile de mai sus sunt propoziii

adevrate, iar celelelalte sunt propoziii false.

aloarea de adevr a unei propoziii poate fi$ este adevrat, este fals, este posibil

adevrat, este probabil fals, etc. i, evident, atribuirea valorii de adevr propoziiilor se

face ntr/un mod subiectiv. 0oi vom considera numai logica binar, adic vom considera

c singurele valori de adevr ale unei propoziii sunt$ este adevratrespectiv estefals.

1ubiectivismul atribuirii valorii de adevr nu poate fi evitat, ns, dec2t ntr/un mod

3


2/135

formal, aa cum vom proceda n seciunile urmtoare. e scurt se pleac cu o mulime de

propoziii 4elementare5 a cror valoare de adevr este dat i se formeaz apoi alte

propoziii 5compuse5. 6odul de formare al propoziiilor alctuiete ceea ce numim

sintax. aloarea de adevr a propoziiilor 4compuse4 se stabilete, n funcie de valoarea

de adevr a propoziiilor 4elementare5 date, dup nite reguli bine precizate. 1emnificaia

propoziiilor este dat de valoarea lor de adevr iar regulile de atrbuire a valorii de adevr

propozitiilor alctuiete ceea ce numim semantic.7ot procesul are un caracter formal,

ceea ce nseamn c se face abstracie de coninutul propoziiilor iar la baza sa vom pune

cele dou principii clasice ale lui Aristotel si anume$

legea terului exclus$ orice propoziie este sau adevrat, sau fals8

legea contradiciei$ o propoziie nu poate fi simultan i adevrat i fals.

om forma propoziii compuse cu a9utorul a cinci conectori logici si anume$

negaia,conjuncia, disjuncia,implicaia i echivalena.

3) Negaia. #aca este o propozitie atunci negaia sa este de asemenea o

propoziie. :ormal vom nota negaia propoziiei cu i o vom citi ;0u ; sau

eventual, 40on 5. n limba9 cotidian propoziia se poate citi$

0u este adevrat c

.sau, pe scurt prin adugarea con9unciei gramaticale 4nu5 , ntr/un mod adecvat, printre

cuvintele propoziiei . #e exemplu dac< este propoziia$

& este numr raional. ,

atunci este propoziia $

0u este adevrat c & este numr raional.

sau, pe scurt$

& nu este numr raional.#in punct de vedere semantic, propoziia este adevrat dac i numai dac

propoziia este fals. n exemplul de mai sus este clar c propoziia este fals i

deci, automat, propoziia este adevrat.

&) Conjuncia. #ac< i sunt dou propoziii atunci con9uncia lor este de

&


3/135

asemenea o propoziie care, formal, se notez cu i se citete folosind con9uncia

gramatical ;i; adic$ 4 i 5. 1emnificaia semantic a propoziiei este cea

uzual, adic, este o propoziie adevrat dac i numai dac ambele propoziii

i sunt adevrate.Astfel dac< este propoziia$

+ este numr prim.

i este propoziia$

= este numr par.

atunci este propoziia$

+ este numste clar c, n exemplul de mai sus, propoziia este adevrat n timp ce propoziia

este fals, astfel nc2t, propoziia este fals.

+) Disjuncia. #ac< i sunt dou propoziii atunci dis9uncia lor este de

asemenea o propoziie care, formal, se noteaz< cu i se citete folosind con9uncia

gramatical ;sau;adic$ 4 sau 5. n logica matematic semnificaia semantic a

propoziiei este urmtoarea$ este o propoziie fals dac i numai dac

ambele propoziii , sunt false, sau, ec-ivalent, este o propoziie adevrat

dac i numai dac cel puin una dintre propoziiile , este adevrat. n particular,

propoziia este adevrat i c2nd ambele propoziii , sunt adevrate. rin

aceasta dis9uncia, n logica matematic, are un caracrer inclusiv spre deosebire de

limba9ul cotidian unde, adesea, dis9uncia are un caracter excusiv. 1 considerm

urmtorul exemplu$ este propoziia$

1tau acas.

iar este propoziia$

6 duc la cinematograf.

ropoziia este

1tau acas sau m duc la restaurant.

#aca ambele propoziii i ar fi adevrate, n logica matematic propoziia

este adevrat n timp ce, n limba9ul cotidian, putem nelege c ea este fals deoarece nu

se poate s stau acas i n acelai timp s m duc la restaurant. ?a momentul oportun

vom intoduce un alt conector logic care s corespund unei dis9uncii 5 excusive5, care

+


4/135

are o anumit importan n logica matematic dar noi o vom folosi ntr/un mod limitat.

(#is9uncia exclusiv a propoziiilor i este adevrat dac i numai dac una i

numai una dintre propoziiile , este adevrat ceea ce nseamna c ea este fals daca

i sunt ambele adevrate.)

@)Implicaia. #ac< i sunt dou propoziii atunci implicaia lor, care se notez

formal cu i se citete 4 implic 5, 4 dac atunci 5 sau 4 din rezult

5 este, de asemenea, o propoziie. n logica matematic, semnificaia semantic a

propoziiei este urmtoarea$ propoziia este fals dac i numai dac

este adevrat i este fals. n particular, dac< este o propoziie fals atunci

propoziia este adevrat indiferent dac< propoziia este adevrat sau fals8 de

asemenea dac este o propoziie adevrat atunci propoziia este adevratindiferent dac propoziia este adevrat sau fals. n limba9ul cotidian ns, se poate

ntelege c dac propoziia este fals atunci propoziia este de asemenea fals

( eventual nu are sens). !a exemplu fie propozia $

!2inele doarme.

i propoziia

pada este alb.

#eoarece propoziia este adevrat rezult c i propoziia este adevrat. n

limba9ul cotidian faptul c 4!2inele doarme5 nu are cum s impice faptul c 4pada

este alb5, ns acest mod de a nelege implicaia nu poate fi definit n cadrul ce va fi

considerat de noi. 1emnificaia implicaiei apare nsa c2nd examinm regula modus

ponens$ dac propoziiile i sunt adevrate atunci i propoziia este

adevrat.

B)chivalena.#ac si sunt dou propoziii atunci ec-ivalena lor, care se

noteaz formal cu i se citeste 4 ec-ivalent 5 sau 4 dac i numai dac 5

este, de asemenea o propoziie. *n logica matematic semnificaia semantic a propoziiei

este urm


5/135


6/135

3& este numr par sau = se divide cu + dar,n acelai timp,3+ nu se divide cu B8

pentru ( )! " C merge

3& este numr par sau, pe de alt parte,= se divide cu + i3+ nu se divide cu B.

ns propoziia ( )! " C se poate citi n limba9 cotidian,n mod evident, astfel$

#ac 3& este numr par atunci = nu se divide cu + i 3+ se divide cu B.

utem considera c!si"sunt propozitii adevrate iar Ceaste o propozitie fals. Atunci

! " este adevrat, ( )! " C este adevrat, ( )! " C este de asemenea

adevrat iar ( )! " C este fals.

2.*ntuiia noastr nu ne spune nimic despre valoarea de adevr a propoziiilor

!,",C,Ddac nu cunoastem persoanele respective. 1 considerm totui c propozitiile

!,",Dsunt adevrate iar propozitia ! este fals. Atunci ! " este adevrat, C D este

fals, C D este adevrat, ( )! " C este adevrat, ( )" C D este fals,

( ) ( )! " C D este fals.

&. Alfabetul i sintaxa n logica propozitiilor

om prezenta logica propoziiilorca un lim#aj formal. %n limba9 formal este, n

general, format dintr/un alfa#etcare conine toate simbolurile limba9ului, o sintaxcare

stabilete modul n care sunt folosite simbolurile limba9ului pentru a forma cu ele

formule( aceste formule, n logica propoziiilor, se vor numi,propoziii) i osemantic

care stabilete interpretarea acestor formule( i n logica propoziiilor singura interpretarea propoziiilor este cea a atribuirii unei valori de adevr pentru fiacare propoziie).

l!a"etul. *n logica propoziiilor alfabetul este format din trei categorii de

simboluri$


7/135

a) 1imboluri propoziionale care se vor nota cu litere mari ale alfabetului latin,

eventual nsoite de indici$ 3 &, , , , , etc.! " ! C " om nota mulimea acestor simboluri

propoziionale cuQ.n general mulimea simbolurilor propoziionale Qeste o mulime

nevid oarecare. b) 1imboluri ale conectorilor logicicare sunt n numr de cinci i anume$

este simbolul negaiei8 este simbolul conjunciei8 este simbolul disjunctiei,

este simbolul implicaiei8 este simbolul echivalenei.

c) %n simbol, ( , numitparantez deschis i un simbol, ), numitparantez $nchis.

1imbolurile conectorilor logici i parantezele se numesc isim#oluri logice8 ele sunt

prezente n orice limba9 din logica propoziiilor. 1imbolurile propoziionale se numesc i

sim#oluri specificedeoarece ne putem imagina c2te un limba9 n logica propoziiilor

pentru fiecare mulime de simboluri propoziionale Q. n realitate noi vom face o teorie

general a logicii propoziiilor i, din acest motiv, vom considera de obicei o mulime Q

arbitrar dar suficient de mare. #e asemenea, dac nu se specific contrariul, vom

sub2nelege c litere disticte 3 &, , , , , etc! " ! C " desemneaz simboluri propoziionale

distincte.

#intaxa.'rice secven de simboluri ale alfabetului se numete expresie.Astfel

orice expresie se reprezint, n mod unic, sub forma$

3 &... m s s s=

unde meste un numr natural iar 3 &, ,..., ms s s sunt simboluri. *n particular, dou expresii$

3 &... m s s s= i 3 &... m s s s =

sunt egale i scriem = , dac m m= i 3 3s s= , & &s s= ,D, m ms s = . Cezult c

pentru orice expresie 3 &... m s s s= numxist o unic expresie de lungime Em = care se numete expresia vid%.

>xpresiile de lungime 3 sunt exact simbolurile alfabetului8 de exemplu$

, , , , ), etc.! C

sunt expresii de lungime3. !a exemple de expresii de lungime & avem$

F


8/135

, ), , , , etc.!" ! ! ! !

Alte exemple de expresii, de diverse lungimi , sunt$

, ( ) , , ( , , (G ) , etc.! " ! " C ! " ! " " ! " ! "

#ac< i sunt dou expresii atunci, evident,

( ), ( ), ( ), ( ), ( )

sunt de asemenea expresii.

2.1. $e!iniie. %n sistem ordonat 3 &H , ,..., In , unde neste un numr ntreg pozitiv

i 3 &, ,..., n sunt expresii se numete consrucie formativ dac pentru orice

J3,&,..., Ki n cel puin una din urmtoarele condiii este satisfcut$

3) i Q, adic i este un simbol propoziional8

&) exist J3,&,..., Kj n astfel nc2t j i< i ( )i j = 8

+) exist , J3,&,..., Kj & n astfel nc2t ,j i & i< < i avem ( )i j & = sau

( )i j & = sau ( )i j & = sau ( )i j & = . ( e scurt ( )i j & = o unde

o este unul dintre simbolurile propoziionale , , , .)

( n general un sistem ordonat de n elemente se noteaz 3 &( , ,..., )n dar n cazul

nostru nlocuim parantezele (, ) cu paranteze H, I pentru a evita confuzia cu simbolurilelimba9ului.)

2.2. $e!iniie. ' expresie se numetepropoziiedac exist un numr ntreg

pozitiv ni o construcie formativ 3 &H , ,..., In astfel nc2t n = . om nota cuS(Q)

sau simplu cuSmulimea tuturor propoziiilor care se pot forma folosind alfabetul Q.

2.%. &ropoziie.!vem$

3) orice sim#ol propoziional !Q este propoziiesau,altfel spus,QS'Q(8

&) dac% este o propoziie atunci ( ) este, de asemenea,o propoziie8

L


9/135

+) dac% , sunt dou% propoziii atunci ( ), ( ), ( ), ( ) sunt,de

asemenea,propoziii.

Demonstraie. 3) entru orice !Q, H I! este, evident, o construcie formativ i

deci! este o propoziie.

&) #eoarece este o propoziie, exist o constucie formativ 3 &H , ,..., In astfel

nc2t .n= Atunci 3 &H , ,..., , ( )In este de asemenea o constructie formativ ceeea

ce demonstreaz c ( ) este o propoziie.

+) #eoarece , sunt propoziii, exist construcii formative 3 &H , ,..., Im ,

3 &H , ,..., In' ' ' astfel nc2t m= i n'= . #ac< o este unul dintre simbolurile

, , , atunci, evident, 3 & 3 &H , ,..., , , ,..., , ( )Im n ' ' ' o este, de asemenea o

construcie formativ, ceea ce demonstreaz c ( ) o este o propoziie.

2.). $e!iniie. #in propoziia &.+. rezult, evident, c expresia vid nu este

propoziie. Cezult de asemenea c singurele propoziii de lungime 3 sunt simbolurile

propoziionale8 acestea se vor numi propoziii elementare,propoziii atomicesau simplu

atomi. n limba9ul cotidian propoziiile elementare ar corespunde acelor propoziii care nu

se pot exprima cu a9utorul altor propoziii folosind conectorii logici din sectiunea 3.

ropoziiile de lungime mai mare ca 3 se numesc i propoziii compuse. >vident,

orice propoziie compus este de forma ( ) , unde este o propoziie sau de forma

( ) o unde i sunt propoziii iar o este unul dintre simbolurile , , , .

!a si n 1eciuna 3, dac i sunt dou propoziii atunci propoziia ( ) se

numete negaia propoziiei iar propoziiile ( ), ( ), ( ), ( ) se

numesc respectiv, conjuncia,disjuncia,implicaia,echivalena propoziiilor i .

1imbolurile conectorilor logici se vor numi simplu conectori logici.

=


10/135

2.*. Exemplu.!onsiderm, n limba9ul cotidian, urmtoarele dou propoziii$

lou.

6erg la plimbare.

0otm prima dintre aceste dou propoziii cu!i a doua cu". utem considera alfabetul

Q J , K! "= . Atunci putem scrie propozitia$

#ac nu plou atunci merg la plimbare.

ntr/un mod formalizat, ca propoziie dinS(Q) , sub forma (( ) )! " . Cemarcm c, n

acest caz, nu avem nici o indicaie precis asupra valorilor de adevr ale propoziiilor

elementare!,"i, cu at2t mai mult, asupra valorii de adevr a propoziiei compuse =

(( ) )! " ns, putem analiza toate posibilitile, dup modelul urmtor$ dac! este

adevrat i " este adevrat atunci este adevrat8 dac! este adevrat i" este

fals atunci este adevrat8 dac!este fals i"adevrat atunci este adevrat8

daca!este fals si"este fals atunci este fals.

2.+.Exemplu. 0e propunem s demonstrm c expresia (( ) )! " , este

propoziie. entru aceasta putem folosi ropoziia &.+. parcurg2nd urmtorii pai astfel$

3. ! este un simbol propoziional i deci este propoziie.

&. #in 3 rezult c ( )! este propoziie.

+."este simbol propoziional i deci este propoziie.

@. #in & i + rezult c (( ) )! " este propoziie.

2.,.Exemplu.>xpresia nu este propoziie deoarece singurele expresii de lungime

3 sunt simbolurile propoziionale iar nu este un simbol propozitional. >xpresia ( )! ,

3E


11/135

de asemenea nu este propoziie. ntr/adevar conectorul logic pote apare ntr/o

propoziie numai c2nd n 4capetele5 sale apar alte dou propoziii pe care putem

eventual, s le numimsursai capatulimpicaiei acestor dou propoziii8 n cazul nostru

lipsete sursa implicaiei.

Reducerea numrului de paranteze. #eoarece abundena parantezelor poate

deveni la un moment dat greoaie, pentru scrierea i propoziiilor se introduc c2teva reguli

simple prin care, putem terge unele dintre pareanteze i considerm c expresia obinut

este tot propoziia dat i anume oform redusa sa oinut prin tregerea parantezelor.

Aceste reguli sunt$

6ai nt2i se terg perec-ile de paranteze exteiroare ale propoziiilor compuse(n

propoziiile elementare nu exist paranteze exterioare).

n al doilea r2nd conectorii logici se ordoneaz astfel$ , , , , ( aceasta

este ceea ce se numete ordinea de prioritate a conectorilor) i parantezele se terg dup

urmtoarea regul$ n primul r2nd conectorul s se aplice primei propoziii care

urmeaz dup el, n al doilea r2nd s se aplice celor dou propoziii mai apropiate de el

( obligatoriu este una n st2nga lui i una n dreapta lui), n al treilea r2nd s se aplicecelor dou propoziii mai apropiate de el i, similar, pentru i apoi .

n cazul c2nd dorim tergerea a c2t mai multe paranteze putem introduce o regul

i pentru cazul apariiei multiple a aceluiai conector i anume pentru apariia multipl a

fiecruia dintre conectorii , , , ordinea de prioritate a aplicrii va fi ntotdeauna de

la st2nga la dreapta n timp ce pentru apariia multipl a conectorului ordinea de

prioritate a aplicrii va fi ntotdeauna de la dreapta la st2nga.

entru ca sa nu avem dificulti n citirea corecta a propoziiei vom aplica parial

regulile de mai sus adic vom terge c2t mai multe paranteze dar nu ntotdeauna pe toate

cele ce pot fi terse conform regulilor de mai sus.

33


12/135

2.-.Exemplu.0e propunem s demonstrm c urmtoarea expresie este propoziie$

( )! " C

entru aceasta procedm ca i n >xemplul &) i parcurgem urmtorii pai$

3.!i"sunt simboluri propoziionale deci propoziii.

&. #in 3 rezult< c< ( )! " este propoziie.

+. #in & rezult< c< ( ( ))! " este propoziie i prin tergerea parantezelor

exterioare acest propoziie devine ( )! " .

@. Ceste simbol propoziional deci este propoziie.

B. #in + i @ rezult c ( ( ) )! " C este propoziie i prin tergerea

parantezelor exterioare aceast< propoziie devine ( )! " C .

:orma complet a propoziiei noastre este, evident$

(( ( )) )! " C .

Cemarcm de asemenea c, ! " C este forma redus a propoziiei$

((( ) ) )! " C ,

i deci este o propoziie diferit de propoziia anterioar8 pentru aceast propoziie putem

considera i alte forme reduse care se obin terg2nd numai anumite paranteze, cum ar fi$

( )! " C , ( )! " C sau (( ) ) .! " C

2..Exemplu. ropoziia ( (( ) ))! " C devine, prin reducerea parantezelor,

( )! " C n timp ce ! " C este o propoziie care, prin refacerea

parantezelor este (( ( )) )! " C i difer, evident, de propoziia precedent. #e

3&


13/135

asemenea propoziia " ! este, prin refacerea parantezelor, ( ( ( )))" ! .

entru propoziia ! " C ! refacerea parantezelor se poate face i parcurg2nd

urmtorii pai$

( )! " C ! , (( ) )! " C ! , ((( ) ) )! " C ! ,

( ((( ) ) )! " C ! .

ropoziia 3 & + @! ! ! ! este, prin refacerea parantezelor, 3 & + @((( ) ) )! ! ! ! .

2.1/.0eorem.' &rincipiul induciei pentru propoziii( 'ie P o mulime de

propoziii astfel $nc(t$

(a) QP8

(b).dac P atunci P8

(c) dac 3 &, P atunci 3 & o P unde o este oricare dintre sim#olurile

, , , .

)n aceste condiiiP=S.

Demonstraie.!onsiderm o propoziie oarecare Si fie nlungimea lui .omdemonstra, prin inducie dup n, c P. entru 3n= avem Q i, conform lui (a),

rezult P. resupunem 3n> i c orice propoziie de lungime mai mic ca naparine

luiP. n acest caz avem, conform #efiniiei &.@., = cu Ssau 3 & = o unde

3 &, S i J , , , K o . >vident 3 &, , au lungimea mai mic ca n i deci,

conform ipotezei de inducie, avem 3, , & P. n cazul = avem, conform lui (b),

Piar n cazul 3 & = o avem P, conform lui (c). Astfel, conform principiului

induciei matematice, avemP=S.

2.11. Corolar.'ie o propoziie. !tunci $n expresia lui num%rul de paranteze

3+


14/135

deschise este egal cu num%rul de paranteze $nchise i acelai lucru se $nt(mpl% $n orice

form% redus a lui .

Demonstraie. entru o propoziie oarecare S notm cu ( )n numrul de

paranteze desc-ise ale lui i cu ( )n num


15/135

>lementele mulimii ( )*p se numesc su#propoziii ale lui . ' subpropoziie +

( )*p se numetesu#propoziie propriea lui dac .

2.1).Exemplu..:ie = ! " i = ! " C . Avem$

( ) ( ) ( ) J K J K J K J K J K*p *p ! *p " ! " " = = = J , , , K! " " ,

( )*p = ( ) ( ) J K ( ) ( ) J K J K J K*p ! " *p C *p ! *p " ! " C = =

J , , , , , K! " " ! " C .

2.1*. $e!iniie. :ie S=S(Q) i !Q. #efinim inductiv, pentru orice propoziie

S, o propoziie notat ( )!*

, astfel$

(3) ( )!* !

= i dac " Q " ! atunci ( )!* " " = 8

(&) dac = atunci ( ) ( )! !* *

= i dac 3 & = o , unde J , , , K o ,

atunci 3 &( ) ( ) ( )! ! !* * *

= o .

ropoziia ( )!*

se numetesu#stituia lui ! cu $n . >vident propoziia ( )!*

se obine prin simpla nlocuire a tuturor apariiilor atomului!cu n expresia lui 8 n

particular, dac !nu apare n expresia lui atunci ( )!*

M . 6ai general, dac neste

un numr ntreg pozitiv, 3 &, ,..., n S(Q) i 3 &, ,..., n! ! ! Qatunci

3 & 3 &

3 & 3 &

, ,...,, ,... ( ) ( ...( ( )))

n n

n n! ! ! ! ! !* * * * =

iar propoziia 3 &3 &

, ,...,, ,... ( )

n

n! ! !* se obine prin nlocuirea tuturor apariiilor atomilor

3 &, ,..., n! ! ! n expresia lui N cu 3 &, ,..., n respectiv.

3B


16/135

!onceptul de substituie poate fi generalizat consider2nd n locul unui atom ! Q

o propoziie Sarbitrar. Astfel, dac , , Si este o subpropoziie a lui

atuncisu#stituia lui cu $n este propoziia notat cu ( )*

i care se obine prin

nlocuirea lui cu n expresia lui n toate apariiile lui n 8 dac nu este

subpropoziie a lui Atunci ( )*

= .

2.1+.Exemplu.Avem3

( ( ) ( ))! ! C!* ! " " C ! C 4

( ) ( ) (( ) ))! ! C " " C ! ! C C .

Exerciii

1. #ecidei care dintre urmtoarele expresii este propoziie i care nu$

a) ( )! " , b) ( )! " C D , c) ( )! " C ,

d) ) ( )! " ! "

, e) ! " !

, f) 3 &( )! ! !

8

n caz afirmativ scriei forma complet a lor.

2.#emonstrai c urmtoarele expresii sunt propoziii$

a) ( ) ( ) ( )! " C ! " ! C , b) ( ) ( )! " C ! C , c) ( )! " C .

entru fiecare dintre ele scriei mai multe forme cu mai multe sau mai puine paranteze

n particular scriei forma complet i forma cea mai redus, adic cea care are cele mai

puine paranteze.

%. #eterminai forma cea mai redus pentru urmtoarele propoziii$

3


17/135

a) (( ( )) )" ! C , b) ( ( ))! " C , c) ((( ( )) ) )! " C D ,

d) (( ( )) ( ))" C ! " , e) (( ) ( ( )))! " C D ,

f) (( ( ( ( )))) ( ))" C " C , g) ( (( ( ( )) ( )))" C " C ,

-) (((( ) ( )) ( )) ))! " C D ! C .

).Cefacei parantezele pentru a gsi forma complet pentru urmtoarele propoziii$

a) C ! " , b) " ! C , c) ( )C ! C ! " ,

d) C ! ! ! "

*. !are dintre urmtoarele expresii sunt forme reduse ale unor propoziii$

a) ! ! " C , b) ( )! ! " C , c) ( )! " C D " ,

d) ( ) ( ( )))! ! " ! " C , e) ! " C D ! ! .

rezentai propoziiile respective sub form complet.

+. #eterminai mulimea subpropoziiilor propoziiei ! " C =

.

,.( 5otaia &olonez( entru orice dou propoziii , Svom scrie n loc de

( ) i o n loc de ( ) o unde o este oricare dintre conectorii logici , , , . n

acest mod rezult un mod de a scrie propoziiile care nu mai folosete paranteze i care se

numete notaia olonez.

a) 1criei propoziiile$

( )! " D , ( )C ! " , ( )C " D C

mai nt2i sub form complet i apoi n notaie olonez.

b) 1criei propoziiile care apar n exerciiul +. n notaie olonez.

3F


18/135

c) Cetranscriei urmtoarele propoziii scrise n notaia olonez n forma standard$

!" "C !C , ! "C !C C ! .

Rezolvri

1. (a) 0u este propoziie. (b) >ste propoziia ((( ) ( )) )! " C D . (c) 0u este

propoziie. (d) 0u este propoziie. (e) >ste propoziia (( ) )! " ! . (e) >ste propoziia

3 &(( ) ( ))! ! ! .

2. :orma complet este$

(( ( )) (( ) ( )))! " C ! " ! C ((( ) ) (( ) ))! " C ! C (( ) ( ))! " C

iar forma cea mai redus este$

( ) ( )! " C ! " ! C , ! " C ! C , ! " C .

%.(a) ( )" ! C

, (b) ( )! " C

, (c) ( )! " C D

,

(d) " C ! " , e) ( )! " C D , f) ( ) ( )" C " C ,

g) ( ( )) ( ))" C " C , -) ( ( )) ( )! " C D ! C

).(a) ( (( ) ))C ! " , (b) ( (( ( ( ))) ))" ! C ,

(c) (( (( ( )) )) )C ! C ! " , (d) ((( ) ) (( ) ))C ! ! ! " .

*. (a) 1e obine, prin refacerea parantazelor (( ( ) ( ( ))! ! " C i, evident,

este o propoziie. (b) (( (( ) )) ( ))! ! " C . (c) ((( ( )) ( )) )! " C D " .

(d) nu este propoziie deoarece numrul de paranteze interioare nu este egal cu numrul

de paranteze exterioare. (e) ((( ) ( ( ))) ( ( )))! " C D ! ! .

3L


19/135

+.:orma complet este ( (( ) ))! " C= i avem$

( ) ( ) ( ) J K J K ( ) J K*p *p ! *p " C ! *p " C = = J K J K" C

J , , , , , K! " " C " C =

,.(a) :orma complet este$

(( ) ( ( )))! " D , (( ( )) )C ! " , ( (( ( ) ))C " D C

iar scrierea n notaie polonez este$

! " D , C !" , C " DC .

(b) (a) " !C , (b) ,! "C (c) ! "C , (d) " C !" ,

(e) !" CD , (f) "C "C , (g) "C "C ,

(-) !" CD !C .

(c) ( ) (( ) ( ))! " " C ! C , (( ) ) (( ) ( ))! " C ! C C ! .

3=


20/135

%. Concepte semantice n logica propoziiilor.

e mulimea cu dou elemente JE,3Kconsiderm o lege de compoziie unar

$JE,3K JE,3K

i patru legi de compoziie binare

, , , $JE,3K JE,3K JE,3K

a cror definiie o prezentm pe scurt cu a9utorul urmtoarelor tabele$

( )

E 3

3 E

x x

,

( , ) ( , ) ( , ) ( , )

E E E E 3 3

E 3 E 3 3 E

3 E E 3 E E

3 3 3 3 3 3

x - x - x - x - x -

.

entru aplicaia $JE,3K JE,3K folosim notaia ( )x x = , JE,3Kx i deciconform tabelului de mai sus avem$

E 3 = , 3 E = .

entru oricare dintre legile de compoziie { }, , , o folosim notaia standard

( , )x - x -=o o , , JE,3Kx - , i rezult$

E E E, E 3 E, 3 E E, 3 3 3 = = = = 8

E E E, E 3 3, 3 E 3, 3 3 3 = = = = 8

E E 3, E 3 3, 3 E E, 3 3 3 = = = = 8

&E


21/135

E E 3, E 3 E, 3 E E, 3 3 3 = = = = .

%.1. $e!iniie. ' valoare de adevr( sau valorizare) peS(Q) este o aplicaie

v$S(Q) JE,3K

care satisface urmtoarele condiii$ pentru orice dou propoziii , S(Q) avem$

( ) ( )v v = , ( ) ( ) ( )v v v = , ( ) ( ) ( )v v v = ,

( ) ( ) ( )v v v = , ( ) ( ) ( )v v v = .

%.2. 0eorem. Dac , $v v S'Q( JE,3K sunt dou valorizri astfel $nc(t

( ) ( )v ! v != pentru orice !Q atunci v v= .

Demonstraie. :ieP= J S ( ) ( )v v = K . #ac Q atunci, prin ipotez,

( ) ( )v v = i P. resupunem acum c Pdeci ( ) ( )v v = . Cezult

( ) ( ) ( ) ( )v v v v = = =

ceea ce implic P. Acum fie 3 &, P. Avem 3 3( ) ( )v v = i & &( ) ( ).v v = i

rezult ca mai sus 3 & 3 &( ) ( )v v =o o deci 3 & o Ppentru orice J , , , K o 8

astfel de exemplu$

3 & 3 & 3 & 3 &( ) ( ) ( ) ( ) ( ) ( )v v v v v v = = = .

Astfel mulimea de propoziiiP satisface condiiile (a),(b),(c) ale 7eoremei &.B. ceea ce

demonstreaz c ( ) ( )v v = pentru orice propoziie S(Q) i deci v v= .

&3


22/135

%.% Corolar.'ie , $v v S'Q( JE,3K dou valorizri, S'Q(i 3 &J , ,..., Kn! ! !

mulimea tuturor sim#olurilor propoziionale care apar $n expresia lui . Dac pentru

orice J3, &,..., Ki n avem ( ) ( )i iv ! v != atunci ( ) ( )v v = .

Demonstraie.!onsiderm alfabetul 3 &J , ,..., Kn! ! != . #eoarece Q avem,

evidentS() S(Q) i, n plus, S(). Cestriciile /i / ale lui vi respectiv v la

S() sunt, evident, valorizri pe S() i, prin ipotez, avem, pentru orice !,

( ) ( ) ( ) ( )/ ! v ! v ! / ! = = = . !onform 7eoremei +.&., avem ( ) ( )/ / = pentru orice

S() i n particular ( ) ( ) ( ) ( )v / / v = = = .

%.). 0eorem. 0entru orice aplicaie $/ Q JE,3K exist i este unic o

valorizare

v$S(Q) JE,3K

astfel $nc(t restricia lui v la coincide cu /.

Demonstraie.Afirmaia de unicitate din enun rezult din 7eorema +.&.. entru a

demonstra afirmaia de existena construim v$ S(Q) JE,3K recursiv astfel$

( ) ( )v ! / != pentru orice !Q8 dac , S(Q) i ( )v , ( )v au fost definite atunci

lum

( ) ( )v v = , ( ) ( ) ( )v v v = , ( ) ( ) ( )v v v = ,

( ) ( ) ( )v v v = , ( ) ( ) ( )v v v = .

Aplicaia v astfel constuit este, evident, o valorizare pe S(Q) care satisface condiia din

enun.

&&


23/135

"servaie. 7eorema +.@. ne permite, evident, s identificm valorizrile $v S(Q)

JE,3K cu aplicaiile /$ Q JE,3K motiv pentru care astfel de aplicaii se vor numi

tot valorizri pe S(Q)8 mai mult ne putem permite s notm o valorizare pe S(Q) i

restricia sa la Qcu aceiai liter.

#e asemenea este clar c ne putem permite, prin abuz de notaie , s scriem n loc

de , n loc de , n loc de , n loc de i n loc de i s

meninem pentru legile de compoziie , , , , acelea reguli de reducere a

parantezelor ca i pentru conectorii logici corespunztori.

%.*. $e!initie. :ie v o valorizare peS(Q) i S(Q). #ac ( ) Ev = spunem c

propoziia estefalsn raport cu valorizarea vi dac ( ) 3v = spunem c propoziia

adevratn raport cu v8 n general ( )v se numete valoarea de adevr a lui N n

raport cu v.

%.+.Exemplu. ?um QJ , K! "=

i definim valorizarea vpe S(Q) lu2nd( ) 3v ! =

i( ) Ev " = . Avem$

( ) ( ) ( ) 3 E Ev ! " v ! v " = = = ,

( ) ( ) ( ) 3 E 3v ! " v ! v " = = = ,

( ) ( ) ( ) 3 E Ev ! " " v ! " v " = = = .

Astfel, n raport cu valorizarea v dat , propoziiile ! " i ! " " sunt false n

timp ce propoziia ! " este adevrat.

%.,. $e!iniie.' propoziie S(Q) se numete logic adevrat sau tautologie

dac este adevrat n raport cu orice valorizare vpeS(Q)8 propoziia se numete

&+


24/135

logic falssau contradiciedac este fals n raport cu orice valorizare peS(Q)8 notm

faptul c este tautologie cu == .

%.-.0eorem.'ie S'Q(o tautologie,n un numr $ntreg pozitiv, 3 &, , ..., n

S(Q) i 3 &, ,..., n! ! ! Q.!tunci3 &

3 &

, ,...,, ,... ( )

n

n! ! !* este de asemenea o tautologie.

Demonstraie.:ie vo valorizare oarecare pe S'Q(. utem defini o valorizare /pe

S'Q(astfel nc2t ( ) ( )i i/ ! v = pentru orice J3,&,..., Ki n i ( ) ( )/ " v "= pentru

orice" Q 3 &OJ , ,..., Kn! ! ! .Atunci, deoarece este tautologie, avem ( ) 3/ = 8 pe de alt

parte avem, evident, v( 3 &3 &

, ,...,, ,... ( )

n

n! ! !* ) ( )/ = deci v( 3 &

3 &

, ,...,, ,... ( )

n

n! ! !* ) 3= .

%..Exemplu.ropoziia ! ! este o contradicie iar propoziia ! ! este o

tautologie. entru a demonstra aceasta observm c

E E E 3 E = = , 3 3 3 E E = = , E E E 3 3 = = , 3 3 3 E 3 = =

i astfel pentru orice JE,3Kx avem Ex x = , 3x x = . ntru orice valorizare vpe

S(Q) dac notm ( )v ! x= rezult

( ) ( ) ( ) Ev ! ! v ! v ! x x = = = ,

( ) ( ) () 3v ! ! v ! v x x = = = .

Astfel ! ! este fals n raport cu valorizarea vn timp ce ! ! este adevrat.

%.1/.Exemplu. :ie Q J , , , K! " C D= i ( )! " C D= S(Q). !onsiderm

valorizarea vpeS(Q) astfel nc2t ( ) 3, ( ) 3, ( ) E, ( ) E.v ! v " v C v D= = = = Avem $

&@


25/135

( ) ( ) 3 Ev ! v ! = = = , ( ) ( ) ( ) E 3 Ev ! " v ! v " = = = ,

( ) ( ) ( ) E E 3v ! " C v ! " v C = = = ,

( ) ( ) ( ) E 3 3v v ! " C v D = = =

astfel c propoziia este adevrat n raport cu valorizarea v.

e de alt parte putem considera valorizarea / pe S(Q) astfel nc2t ( ) E,/ ! =

( ) 3/ " = , ( ) E/ C = , ( ) E./ D = Avem$

( ) ( ) E 3/ ! / ! = = = , ( ) ( ) ( ) 3 E E/ ! " / ! / " = = = ,

( ) ( ) ( ) E E 3/ ! " C / ! " / C = = = ,

( ) ( ) ( ) E E E/ / ! " C / D = = =

astfel nc2t propoziia este fals n raport cu valorizarea /i n particular N nu este

tautologie.

%.11.Exemplu. #eoarece

E E E E E 3 = = , E 3 E E E 3 = = , 3 E 3 E 3 3 = = , 3 3 3 3 3 3 = =

rezult c propoziia = ! " ! este o tautologie. !onform 7eoremei +.L, propoziia

( )C D " C D care se obine din prin nlocuirea lui ! cu C D este de

asemenea tautologie.

Exerciii

1.!onsiderm, n limba9ul cotidian, urmtoarele propoziii$

B este numr prim, 3B se divide cu +, & se divide cu +, 3& se divide cu B,

&B


26/135

notm aceste propoziii respectiv cu , , ,! " C D i lum Q J , , , K! " C D= .

(a) #efinii o valorizare vpeS(Q) care, eventual, s corespund intuiiei noastre.

(b) n raport cu valorizarea v definit la punctul (a) calculai valoarea de adevr apropoziiei ! " C D = S(Q).

2.:ie v o valorizare peS(Q) astfel nc2t ( ) 3, ( ) 3, ( ) E.v ! v " v C = = = n raport cu

aceast valorizare determinai valoarea de adevr pentru urmtoarele propoziii$

(a)! C , (b)! C , (c) ! C , (d)! " C ,

(e)" C ! , (f)! " " C , (g) ( )" ! ! C

(-) ( ) ( )" ! ! C C " .

%.Artai c propoziia (( ) )! " ! != este tautologie.

).Artai c urmtoarele propoziii sunt tautologii$

(a) ! ! , (b) ( ) ( )! " ! " .

*.(a)Artai c legile de compoziie i pe JE,3Ksunt comutative, asociative i

c au element neutru. !e tautologii rezult din aceste proprietti"

(b) 1tudiai comutativitatea i asociativitatea i pentru legile de compoziie i

pe JE,3K.

+.Artai c propoziia ( )! " C D nu este tautologie i nici contradicie

Rezolvri

1. (a) ?um ( ) 3, ( ) 3, ( ) E, ( ) Ev ! v " v C v D= = = = .

(b) Avem$ ( ) ( ) ( ) ( ) ( ) 3 3 E E 3 E Ev v ! v " v C v D = = = = .

&


27/135

2. ( ) 3 E 3v ! C = = , ( ) 3 E Ev ! C = = , ( ) 3 E E 3 Ev ! C = = = ,

( ) 3 3 E 3 E E 3 E Ev ! " C = = = = ,

( ) 3 E 3 3 3 3 3 3 3v " C ! = = = = ,( ) 3 3 3 E 3 3 3 3 3 3v ! " " C = = = = ,

(( ) ) (3 3) 3 E (3 E) E E E 3v " ! ! C = = = = ,

(( ) ( ) ) (3 3) (3 E) E 3 3v " ! ! C C " = = .

%. :ie v o valorizare oarecare peS(Q). 0otm ( )v ! x= i ( )v " -= . >ste suficient

s artm c pentru orice , JE,3Kx - avem (( ) ) 3x - x x = . 1unt exact patru

posibiliti i anume$

Ex= i E- = 8 n acest caz avem ((E E) E) E (3 E) E E E 3 = = = ,

Ex= i 3- = 8 n acest caz avem ((E 3) E) E (3 E) E E E 3 = = = ,

3x= i E- = 8 n acest caz avem ((3 E) 3) 3 (E 3) 3 3 3 3 = = = ,

3x= i 3- = 8 n acest caz avem ((3 3) 3) 3 (3 3) 3 3 3 3 = = = .

).(a). :ie vo valorizare oarecare peS(Q) i ( )v ! x= . #ac Ex= atunci$

E E E 3 E E 3 = = =

iar dac 3x = atunci$

3 3 3 E 3 3 3 = = = .

(b) :ie vo valorizare oarecare peS(Q) i ( ) , ( )v ! x v " -= = .#ac Ex = atunci,pentru orice JE,3K- , avem$

(E ) (E ) 3 3 3- - = = .

#ac 3, Ex -= = atunci$

&F


28/135

(3 E) (3 E) E (3 3) E 3 3 = = =

iar dac 3, 3x -= = atunci

(3 3) (3 3) 3 (3 E) 3 = = .

*. a) !omutativitatea lui rezult din

E E E E

E E 3 E

3 E E E

3 3 3 3

x - - x

iar asociativitatea din

( ) ( )

E E E E E E E

E E E E 3 E E

E E 3 E E E E

E E 3 E 3 E 3

3 E E E E E E

3 E E E 3 E E

3 3 3 E E E E

3 3 3 3 3 3 3

x - z x - z

( mai precis asociativitatea rezult din faptul c n tabla de mai sus coloanele @ i

coincid). >lementul neutru pentru este, evident,3. Analog se arat c este

comutativ i asociativ8 elementul neutru pentru este E. !omutativitatea lui i

implic tautologiiile

! " " ! ,! " " ! 8

asociativitatea implic tautologiile

( ) ( )! " C ! " C , ( ) ( )! " C ! " C

&L


29/135

iar elementul neutru implic tautologiile

( ) , ( )! " " ! ! " " .

b) #eoarece 3 E E =

i E 3 3 =

legea de compoziie

nu este comutativ. #easemenea nu este asociativ deoarece

(E E) E 3 E E = = , E (E E) E 3 3 = = .

?egea de compoziie este comutativ i asociativ i rezult c propoziiile$

( ) ( )! " " ! , (( ) ) ( ( ))! " C ! " C

sunt tautologii.

+. ( )! " C D= . !onsiderm o valorizare vastfel nc2t ( ) Ev ! = , ( ) 3v " =

, ( ) Ev C = , ( ) Ev D = i o valorizare / astfel nc2t ( ) 3/ ! = , ( ) 3/ " = , ( ) E/ C = ,

( ) E/ D = . Avem$

( ) ( E 3 E) E E 3 E 3 3 E 3 E Ev = = = = =

astfel c

nu este adevrat n raport cu vi

nu este tautologie. #e asemenea$

( ) ( 3 3 E) E 3 3 E E 3 E E E E/ = = = = =

astfel c este adevrat n raport cu /i nu este contradicie.

&=


30/135

). 0a"ele i ta"le de adevr

om considera o valorizare oarecare v pe S(Q) i vom sub2ntelege c opropoziie S(Q) este adevrat sau fals daup cum este adevrat sau fals n raport

cu aceast valorizare. 7abelele legilor de compoziie , , , , pe mulimea JE,3K

prezentate n 1eciunea +. devin atunci ta#ele de adevr pentru conectorii logici

, , , , n modul urmtor$

E 33 E

,

E E E E 3 3

E 3 E 3 3 E3 E E 3 E E

3 3 3 3 3 3

.

Celum explicit tabelul de adevr pentru fiecare conector logic. Astfel , pentru

S(Q)

E 33 E

se numete ta#elul de adevr al negaiei. 1emnificaia sa este evident cea prezentat n

1eciunea 3.$ este adevrat dac i numai este fals. entru , S(Q),

E E E

E 3 E

3 E E

3 3 3

.

se numete ta#elul de adevr al conjunciei i el arat c este o propoziie

adevrat dac i numai dac i sunt ambele adevrate8

+E


31/135

E E E

E 3 3

3 E 3

3 3 3

se numete ta#elul de adevr al disjuncieii el arat c este fals dac i numai

dac i +sunt ambele false8

E E 3

E 3 3

3 E E

3 3 3

se numete ta#elul de adevr al implicaieii el arat c este fals dac i numai

dac este adevrat i +este fals8

E E 3

E 3 E

3 E E3 3 3

se numete ta#elul de adevr al echivalenei i el arat c este adevrat dac i

numai dac i +au aceai valoare de adevr.

).1.0eorema. 'ie , S'Q(. Dac i + sunt tautologii atunci + este

tautologie.

Demonstraie. :ie vo valorizare peS'6( astfel nc2t ( ) 3v = i ( ) 3v = .

7abelul de adevr al implicaiei arat c, n aceast situaie, singura posibilitate este

( ) 3v = .

+3


32/135

e de alt parte putem construi ta#la de adevr pentru o propoziie oarecare

S(Q)$ n moul urmtor$ dac 3 &J , ,..., Kn! ! ! este mulimea atomilor care apar n expresia

lui considerm toate valorizrile vpeS 3 &(J , ,..., K)n! ! ! ( care, evident, sunt n numr de

&n ) i calculm, pentru fiecare, valoarea de adevr ( )v . 7abla conine o linie de

indexare i &n linii care corespund cu valorizrile vde mai sus8 ea conine n coloane

corespunztoare atomilor 3 &, ,..., n! ! ! , obligatoriu o coloan corespunztoare lui i( dar

nu neaprat) un numr neprecizat de coloane care corespund unor subpropoziii ale lui

i care a9ut la calculul lui ( )v . #up c2teva exemple construcia unei astfel de table

devine evident.

).2.Exemplu.7abla de adevr a propoziiei ! " ! " este $

E E 3 3 3 3

E 3 3 3 3 3

3 E E E E 3

3 3 3 E 3 3

! " ! " ! ! " ! " ! "

%ltima coloan arat c propoziia dat este adevrat n raport cu orice valorizare vpe

S(Q) i deci ea este tautologie.

).%. Exemplu. 7abla de adevr a propoziiei ! " C este$

+&


33/135

E E E E 3

E E 3 E 3

E 3 E E 3

E 3 3 E 33 E E E 3

3 E 3 E 3

3 3 E 3 E

3 3 3 3 3

! " C ! " ! " C

Aceast tabl se poate prezenta i sub o form prescurtat astfel$

E E E 3 EE E E 3 3

E E 3 3 E

E E 3 3 3

3 E E 3 E

3 E E 3 3

3 3 3 E E

3 3 3 3 3

! " C

Acum pe coloana a doua apare valoarea de adevr a lui ! " i pe coloana a patra

valoarea de adevr a propoziiei date n timp ce coloanele 3,+,B corespund atomilor

, ,! " C. edem c n raport cu valorizrile v pentru ( ) 3, ( ) E, ( ) 3v ! v " v C = = = (linia a

asea) propoziia noastr este adevrat iar n raport cu valorizrile v pentru care

( ) 3, ( ) 3, ( ) Ev ! v " v C = = = (linia a aptea) ea este fals.

).).Exemplu.7abla de adevr a propoziiei ! " C este$

++


34/135

E E E 3 3 E

E E 3 3 3 3

E 3 E 3 3 E

E 3 3 3 3 33 E E E E 3

3 E 3 E E 3

3 3 E E 3 E

3 3 3 E 3 3

! " C ! ! " ! " C

iar tabla de adevr prescurtat este

3 E 3 E E E3 E 3 E 3 3

3 E 3 3 E E

3 E 3 3 3 3

E 3 E E 3 E

E 3 E E 3 3

E 3 3 3 E E

E 3 3 3 3 3

! " C

#m mai 9os o list de tautologii mai importante. >le se verific uor folosind una

dintre metodele prezentate n 1eciunea +., 1eciunea @. sau n seciunile urmtoare.

%nele dintre acestea fac obiectul unor exemple sau exerciii.

(3) legea necontradiciei$ ( )! ! 8

(&) legea terului exclus$ ! ! 8

(+) legea identitii$ ! ! 8

(@) legea dublei negaii$ ! ! 8

(B) legea contrapoziiei$ ! " " ! 8

+@


35/135

() legea negrii implicaiei$ ( )! " ! " 8

(F) legile lui #e 6organ$ ( )! " ! " , ( )! " ! " 8

(L) tautologia modus ponens$ ( )! ! " " 8

(=) tautologia modus tolens$ ( )! " " ! 8

(3E) legile silogismului$ ( ) (( ) ( ))" C ! " ! C ,

( ) (( ) ( ))! " " C ! C

(33) lege transportului$ ( ( )) ( )! " C ! " C .

Exerciii

1. #ac propoziiiile! i"sunt adevrate i propoziia Ceste fals decidei care

din urmtoarele propoziii este adevrat i care este fals$

(a) ! C , (b) ! C , (c) ! C , (d) ! " C , (e) " C ! ,

(f) ( )! " " C , (g) ( )" ! ! C ,

(-) ( ( ))" ! ! C C " .

2.!ompletai urmtoarea tabl de adevr$

E E

E 3

3 E

3 3

! " ! " ! ! " ! " ! "

%.!onstruii tabla de adevr pentru propoziia ( )! " ! "

).!onstruii tablele de adevr pentru propoziiile ( )! " ! i ! C " .

+B


36/135

*. 1criei prescurtat tablele de adevr pentru propoziiile ( )! " ! i

! C " .

+.#eterminai care dintre urmtoarele propoziii este tautologie sau contradicie $

(a)! ! ! , (b) ( )! " " ! , (c) ! ! " ,

( ) ( ( ))d ! " " C ! C , (e) ( )! ! " , (f) ! " ! " ,

(g) ( )! " ! " , (-) ( )! ! " " .

Rezolvri

1. (a) adevrat8 (b), (c),(d) false8 (e),(f),(g), (-) adevrate$

(a)3 3 E

! C , (b)

3 E E

! C , (c)

E 3 E 3 E

! C , (d)

3 E E 3 E E

! " C ,

(d)3 E E 3 E E

! " C , (e)

3 3 3 E 3 3

" C ! ,

(f)( )

3 3 3 3 3 3 3 E

! " " C , (g)

( )

3 E E 3 3 3 E E

" ! ! C ,

(-)( ( ) )

3 3 3 3 3 3 3 E 3 3 E 3 3

" ! ! C C " .

2.

E E 3 3 E E

E 3 3 3 3 3

3 E E E E 3

3 3 3 E E E

! " ! " ! ! " ! " ! "

.

+


37/135

%.

E E 3 3 E

E 3 E 3 33 E E E E

3 3 3 E E

! " ! " ! ! "

.

).

( )E E 3 3 3

E 3 3 3 3

3 E E E E

3 3 3 E 3

! " ! " ! ! " !

,

E E E 3 3 E

E E 3 E E 3E 3 E 3 3 3

E 3 3 E E E

3 E E 3 3 E

3 E 3 E 3 E

3 3 E 3 3 3

3 3 3 E 3 3

! " C C ! C ! C "

.

*.

( )

E 3 E E E

E 3 3 E E

3 E E E 3

3 3 3 3 3

! " !

,

E 3 3 E E E

E E E 3 3 E

E 3 3 E 3 3

E E E 3 E 3

3 3 3 E E E

3 3 E 3 E E

3 3 3 E 3 3

3 3 E 3 3 3

! C "

+F


38/135

+. (a) >ste tautologie$

E E 3

3 3 3

! ! ! ! ! !

(b) ropoziia nu este contradicie nici tautologie8 acest lucru se vede pe coloana F a

tablei de adevr( prescurtate) de mai 9os$

( )

E 3 E E E 3 E

E 3 3 3 3 E E

3 E E E E 3 3

3 3 3 3 3 3 3

! " " !

(c) 0u este nici tautologie i nici contradicie

E E 3 E E

E 3 3 E E

3 E E E 3

3 3 E 3 3

! " ! ! " ! ! "

(d) ropoziia este tautologie i acest lucru se vede pe coloana @ a tablei de adevr

de mai 9os$

( ( ))

E 3 E 3 E 3 E 3 E 3 E

E 3 E 3 E 3 3 3 E 3 3

E 3 3 3 3 E E 3 E 3 E

E 3 3 3 3 3 3 3 E 3 33 E E 3 E 3 E E 3 E E

3 E E 3 E 3 3 3 3 3 3

3 3 3 3 3 E E 3 3 E E

3 3 3 3 3 3 3 3 3 3 3

! " " C ! C

+L


39/135

(e) ropoziia este contradicie$

( ) ( )

E E E 3 E

E 3 3 E E3 E 3 E E

3 3 3 E E

! " ! " ! " ! ! "

(f) >ste tautologie$

( )

E 3 E 3 3 E E 3 E

E 3 3 3 3 E E E 3

3 E E 3 E 3 3 3 E3 3 3 3 3 3 E E 3

! " ! "

(g) >ste tautologie$

( )

E E E 3 E 3 E

E E E 3 3 3 3

3 E 3 E E 3 E

3 3 3 3 3 3 3

! ! " "

+=


40/135

*. Ec7ivalena propoziiilor

*.1. $e!iniie. #ou propoziii , S(Q) se numesc ec-ivalente i scriem

dac pentru orice valorizare vpeS(Q) avem ( ) ( )v v = .

*.2. &ropoziie.Dou propoziii , S(Q)sunt echivalente dac i numai dac

propoziia este tautologie.

Demonstraie.7abelul de adevr al implicaiei prezentat n 1eciunea @. arat c,

pentru orice valorizare v avem ( ) 3v = dac i numai dac ( ) ( )v v = ceea ce

nseamn c este tautologie dac i numai dac .

*.%. Corolar. 'ie , S'Q( astfel $nc(t , n un numr $ntreg pozitiv,

3 &, ,..., n S(Q) i 3 &, ,..., n! ! ! Q.!tunci3 &

3 &

, ,...,, ,... ( )

n

n! ! !* 3 &

3 &

, ,. .. ,

, ,.. . ( )nn! ! !

*

.

Demonstraie. !onform lui B.&., este tautologie i, conform 7eoremei +.L.,

3 &

3 &

, ,...,, ,... ( )

n

n! ! !* este de asemenea tautologie. #eoarece 3 &

3 &

, ,...,, ,... ( )

n

n! ! !* M

3 &

3 &

, ,...,, ,... ( )

n

n! ! !* 3 &

3 &

, ,...,, ,... ( )

n

n! ! !* rezult 3 &

3 &

, ,...,, ,... ( )

n

n! ! !* 3 &

3 &

, ,...,, ,... ( )

n

n! ! !* .

*.).Exemple.#in lista de tautologii prezentat la sf2ritul 1eciunii @., rezult,

conform ropoziiei B.&., urmtoarele ec-ivalene$

! ! ( legea identitii), ! ! ( legea dublei negaii), ! " " ! ( legea

contrapoziiei), ( )! " ! " ( legea negrii implicaiei),

( )! " ! " i ( )! " ! " ( legile lui #e 6organ).

@E


41/135

Alte ec-ivalene importante care sunt uor de demonstrat sau le vom demonstra n

diverse exemple sau exerciii sunt$

! ! ! , ! ! ! , ! " " ! , ! ! ! ,

( ) ( )! " C ! " C , ( ) ( )! " C ! " C ,

( ) ( ) ( )! " C ! " ! C , ( ) ( ) ( )! " C ! " ! C .

' metod simpl de a demonstra ec-ivalena a dou propoziii i este de a face

simultan tablele lor de adevr8 cele dou propoziii sunt ec-ivalente dac i numai dac

coloanele corespunztoare lui i n aceste table sunt identice.

*.*. Exemplu. #emonstrm c ( ) ( )! " ! " " ! astfel$

( ) ( )

E E 3 3 3 3

E 3 E 3 E E

3 E E E 3 E

3 3 3 3 3 3

! " ! " ! " " ! ! " " !

>c-ivalena noastr rezult din faptul c coloanele + i ale tablei de mai sus sunt

identice.

*.+. &ropoziie.1elaia pe mulimeaS(Q) este o relaie de echivalen.

Demonstraie.:ie , , S(Q). #eoarece ( ) ( )v v = pentru orice valorizare v

avem . resupunem 8 pentru orice valorizare v avem ( ) ( )v v = deci

( ) ( )v v = ceea ce arat c . n fine presupunem i 8 pentru orice

@3


42/135

valorizare vavem ( ) ( )v v = i ( ) ( )v v = deci ( ) ( )v v = ceea ce arat c .

Astfel relaia este reflexiv, simetric i tranzitiv adic este o relaie de ec-ivalen.

*.,. Lem.'ie 3 3, , , S2Q3 astfel $nc(t 3 i 3 . !vem, pentru orice

J , , , K o , 3 i 3 3 o o .

Demonstraie.entru orice valorizare vavem 3 3( ) ( ), ( ) ( )v v v v = = i rezult,

evident,

3 3( ) ( ) ( ) ( )v v v v = = = , 3 3 3 3( ) ( ) ( ) ( ) ( ) ( )v v v v v v = = =o o o o .

*.-. 0eorem.'ie , , S(Q) astfel $nc(t . !tunci ( )*

.

Demonstraie.om aplica 7eorema &.3E. pentru mulimea de propoziii

P J= S'Q( ( )*

K.

:ie !Q . #ac != avem ( )* ! !

= = iar dac ! avem ( )* !

M!8 n

ambele cazuri avem, evident, ! ( )* !

deci !P. Astfel QP.Acum fie ,

Pdeci ( )*

i ( )*

. Avem, conform ?emei B.F.,

( )*

M ( )*

i dac J , , , K o

,

o ( )* o ( )*

M ( )*

o

asatfel c , o P. !onform 7eoremei &.3E, avemP=S'Q(ceea ce demonstreaz

afirmaia din enun.

@&


43/135

*.. Exemplu. #emonstrm acum ec-ivalena ( )! " ! " cu a9utorul

tablelor de adevr$

( )

E E 3 E 3 E

E 3 3 E E E

3 E E 3 3 3

3 3 3 E E E

! " ! " ! " " ! "

>c-ivalena noastr rezult din faptul c coloanele @ i coincid.

*.1/. Exemplu.>xemplificm acum modul n care se folosesc o parte din rezultatele

precedentepentru a demonstra urmtoarea ec-ivalen$

( )! " ( ) ( )! " ! " .

n propoziia ( )! " subpropoziia ! " se nlocuiete cu

( ) ( )! " " ! i deoarece, conform lui B.B., avem ( ) ( )! " ! " " !

rezult, conform 7eoremei B.L,

(3) ( )! " (( ) ( )! " " ! .

conform lui B.@, avem ( )! " ! " i, prin nlocuirea lui ! cu

! "= i a lui" cu " != , rezult, conform !orolarului B.+,

(&)(( ) ( )) ( ) ( )! " " ! ! " " !

.

n propoziia ( ) ( )! " " ! se nlocuiete subpropoziia ( )! " cu

! " i subpropoziia ( )" ! cu " ! 8 deoarece, conform exemplului B.= avem

( )! " ! " i, evident, ( )" ! " ! rezult$

@+


44/135

(+) ( ) ( )! " " ! ( ) ( )! " " ! .

avem, conform lui B.@., ! " " ! i , conform simetriei din ropoziie B..,

" ! ! " 8 prin nlocuirea lui!cu ! rezult " ! ! " i astfel$

(@) ( ) ( )! " " ! ( ) ( )! " ! " .

n final, aplic2nd tranzitivitatea din ropoziia B.., rezult din (3),(&),(+) i (@)$

( )! " ( ) ( )! " ! " .

n continuare procedeul descris mai sus se va scrie pe scurt, fr referire la

rezultatele teoretice folosite dar cu denumirea de metoda echivalenelor. n cazul nostru

vom scrie$

( )! " (( ) ( )! " " ! ( ) ( )! " " !

( ) ( )! " " ! ( ) ( )! " ! " .

*.12. Exemplu. om demonstra legile lui #e 6organ sub forma $

( )! " ! " i ( )! " ! " .

entru prima dintre ele folosim metoda tablelor de adevr$

( )

3 E E E 3 3 3

3 E E 3 3 3 E

3 3 E E E 3 3

E 3 3 3 E E E

! " ! "

>c-ivalena ( )! " ! " rezult din faptul ca n tabela de mai sus coloanele 3 i

coincid. A doua lege a lui #e 6organ rezult din prima folosind metoda ec-ivalenelor

din >xemplul B.3E $

@@


45/135

( ) ( ) ( )! " ! " ! " ! " .

( am folosit legea dublei negaii$ ! ! i prima lege a lui #e 6organ de mai sus).

*.12. $e!iniie. :ie o propoziie n a crei expresie apar numai conectorii , , .

ropoziia care se obine din prin nlocuirea fiecrei apariii a lui cu i a

fiecrei apariii a lui cu se numete duala propoziiei . Astfel dac

( )! " C= atunci duala lui este propoziia ( )! " C = . >vident, pentru

orice propoziie , avem ( ) = .

*.1%. 0eorem' 0eorema de dualitate(.0entru orice dou propoziii , avem$

(i) este tautologie dac i numai dac este tautologie8

(ii) este tautologie dac i numai dac este tautologie8

(iii)dac atunci .

Demonstraie. (i) #ac este tautologie atunci, conform !orolarului B.+.,

propoziia P care se obine din prin nlocuirea fiecrui atom!care apare n expresia

lui cu negaia sa ! este de asemenea o tautologie. e de alt parte din legile lui #e

6organ rezult, evident, P astfel c este de asemenea tautologie. entru a

demonstra afirmaia reciporoc, notm = i observm c

( ) ( ) = = = deci = . Astfel dac presupunem c =

este tautologie rezult, din cele de mai sus c i deci este tautologie.

(ii) Avem, evident, ! " ! " i rezult, conform !orolarului B.+,

. Astfel, conform lui (i), este tautologie dac i numai dac

( ) este tautologie. e de alt parte avem$

( ) ( ) =

@B


46/135

i afirmaia din enun este evident.

(iii) >vident, este tautologie dac i numai dac i sunt tautologii.

#eoarece ( ) ( ) rezult c este tautologie dac i numai

dac i sunt tautologii adic, conform lui (ii), dac i numai dac

( ) ( ) este tautologie. Astfel este tautologie dac i numai dac

este tautologie. Afirmaia rezult acum din ropoziia B.&.

*.1). Exemplu. om demonstra ec-ivalenele$

( ) ( ) ( )! " C ! " ! C

, ( ) ( ) ( )! " C ! " ! C

.

rima rezult din tablele de adevr de mai 9os$

( ) ( ) ( )

E E E E E E E E

E E E 3 3 E E E

E E 3 3 E E E E

E E 3 3 3 E E E

3 E E E E E E E3 3 E 3 3 E 3 3

3 3 3 3 E 3 3 E

3 3 3 3 3 3 3 3

! " C ! " ! C

entru a doua procedm astfel$ dac notm = ( )! " C i = ( ) ( )! " ! C

avem = ( )! " C i = ( ) ( )! " ! C 8 conform ec-ivalenei precedente avem

i, conform 7eoremei B.3+., rezult adic exact cea de a doua ecivalen.

1punem c a doua ec-ivalen rezullt din prima prin dualitate.

Exerciii

@


47/135

1. :ie , S(Q). Artai c$

a) #ac este tautologie atunci i .

b) #ac este contradicie atunci i .

c) #ac este tautologie atunci .

2. #emonstrai urmtoarele ec-ivalene (folosind diverse metode prezentate

anterior)$

a) ( )! " C ! " C , b) ( )! " " ! " ,

c)( )! " " ! "

, d)! " " !

,

e)! " ( ) ( )! " ! "

f) ! " " ! , g) ( ) ( )! " C ! " C , -) ( )! ! " ! ,

i) ( )! ! " ! , 9) ( )! " ! " .

%. Artai c

( )! " C ! " ! C " .

). :ie o propoziie. #emonstrai c$

a) dac n expresia lui apare numai conectorul atunci este tautologie dac i

numai dac fiecare atom!Qapare n expresia lui de un numr par de ori8

b) dac n expresia lui apar numai conectorii i atunci este tautologie

dac i numai dac fiecare atom!Q precum i conectorul apar n expresia lui

de un numr par de ori.

Rezolvri

1. :ie vo valorizare oarecare.

(a) #eoarece este tautologie avem ( ) 3v = i rezult$

( ) ( ) ( ) 3 ( ) ( )v v v v v = = = ,

@F


48/135

( ) ( ) ( ) 3 ( ) 3 ( )v v v v v = = = = .

(b) #eoarece este contradicie avem ( ) Ev = i rezult$

( ) ( ) ( ) E ( ) E ( )v v v v v = = = = ,

( ) ( ) ( ) E ( ) ( )v v v v v = = = .

(c) #eoarece este tautologie avem ( ) 3v = i rezult$

( ) ( ) ( ) 3 ( ) ( )v v v v v = = = .

2. a) :olosim metoda ec-ivalenelor i avem$

( ) ( ) ( )! " C ! " C ! " C

( )! " C ( )! " C ! " C .

b) Avem$

( )! " " " ( )! " ( ) ( )" ! " " " ! ! " .

c) Cezult din b) prin dualitate.

d) Avem$

! " ! " " ! " ! " ! .

e) :olosim >xemplu B.3B. i b) de i avem$

( ) ( ) ( ) ( )! " ! " " ! ! " " ! (( ) ) ( ( ))! " " " " !

( ) ( )! " " ! ( ) ( )! " ! " .

f) :olosim e) i avem$

! " ( ) ( )! " ! " ( ) ( )" ! " ! " ! .

@L


49/135

g) 7ablele de adevr sunt$

( ) ( )

E 3 E E E E 3

E 3 E 3 3 3 EE E 3 3 E 3 E

E E 3 E 3 E 3

3 E E 3 E 3 3

3 E E E 3 E E

3 3 3 E E E E

3 3 3 3 3 3 3

! " C ! " C

-) Cezult din tabla de adevr de mai 9os

( )

E E E E

E E 3 3

3 3 3 E

3 3 3 3

! ! "

i) Cezult din -) prin dualitate.

9) Cezult din tabla de adevr de mai 9os$

( )

E E 3 E E 3

3 E E 3 3 E

3 3 E E 3 3

E 3 3 3 E E

! " ! "

%. entru mai mult claritate preferm ca propoziiile sa fie scrise sub form

complet( dar fr parantezele exterioare) i deci avem de artat c

( ) (( ) ) ( )! " C ! " ! C " .

Avem$

( ) (( ) ) (( ) ( )) (( ) ))! " C ! " ! " C ! ! " "

@=


50/135

(( ) ( )) (( ) ( )) (( ) ( )) ( )! " C ! ! " " " ! " C ! ! "

(( ) ( )) ( ) ((( ) ) )) ( )! " ! C ! " ! " ! C ! "

( ) ( ) ( )! C ! " ! C " .

). a) #in &.f) i g) rezult c 3 & ... n unde neste un numr ntreg

pozitiv i, pentru fiecare J3,&,..., Ki n , i care conine numai conectorul i toi

atomii si coincid s zicem cu i! Q8 evident, putem presupune c atomii 3 &, , ..., n! ! !

sunt distinci. #eoarece ! ! este tautologie rezult c, pentru fiecare J3,&,..., Ki n ,

dac notm cu in numrul de atomi ai lui i atunci i este tautologie n cazul c2nd in

este par iar n cazul in impar avem i i! ( vezi i 3.c)). Cezult, n particular, c dac

in este par pentru orice J3,&,..., Ki n atunci i este tautologie. n caz contrar avem

3 &...

si i i! ! !

undeseste un numr ntreg pozitiv i3 &, ,...,

si i i! ! ! sunt atomi distinci8 n aceast situaie

putem considera o valorizare vastfel nc2t3

( ) Eiv ! = i &( ) ... ( )si iv ! v != = 3= i avem,

evident, ( ) Ev = .

b) :olosim &.f), g) , 9) i, n plus, tautologia ! ! . Cezult

3 &

... n

unde neste un numr ntreg pozitiv i, pentru fiecare J3,&,..., Ki n , i este o propoziie a

carei expresie conine numai conectorii i i acelai atom s zicem i! 8 n plus

atomii 3 &, ,..., n! ! ! sunt distinci i numrul apariiilor conectorului n expresia lui

are aceiai paritate cu numrul apariiilor sale n expresia lui 3 & ... n . utem

presupune = 3 & ... n . entru fiecare J3, &,..., Ki n fie ir numrul

BE


51/135

apariiilor atomului i! n expresia lui , egal cu numrul apariiilor lui i! n expresia lui

i , i i4 numrul apariiilor conectorului n expresia lui i . Avem

3 & , 3 , & ,... ...

i i i i ii i i ip i p i p i p 4! ! ! ! ! ! + + + ,

i i ir p 4= + i 3 & ,... i ii i i p 4 i! ! ! !+= = = = Q. Av2nd n vedere c i i! ! este

tautologie rezult c$ dac ip i i4 sunt pare atunci i este tautologie8 dac ip este

impar i i4 este par atunci i i! , dac ip este par i i4 este impar atunci i i! iar

dac ip i i4 sunt impare atunci i i i! ! este o contradicie. :ie a numrul

indicilor J3,&,..., Ki n astfel ca ip i i4 sunt impare, # numrul indicilor J3,&,..., Ki n

astfel ca ip par i i4 impar sau ip impar i i4 par, c numrul indicilor J3,&,..., Ki n astfel

ca ip i i4 sunt impare. Cezult c este tautologie dac i numai dac, pentru orice

J3,&,..., Ki n , E#= i c par, ec-ivalent, dac i numai dac pentru orice J3,&,..., Ki n ,

i i ir p 4= + este par i 3 & ... n4 4 4+ + + este par.

+. Conectori logici

n afara conectorilor logici uzuali anume , , , , puem defini i alte tipuri de

conectori logici astfel$

+.1. $e!iniie.:ie nun numr ntreg pozitiv. ' aplicaie $JE,3K JE,3Knf se

numetefuncie de adevr. #at funcia de adevr $JE,3K JE,3Knf o aplicaie

B3


52/135

$' S'Q( n S'Q(

astfel nc2t pentru orice valorizare v i orice 3 &( , ,..., )n S'Q( n s avem

3 & 3 &( ( , ,..., )) ( ( ), ( ),..., ( ))n nv ' f v v v =

se numete un conector logic n ar corespunztorfunctiei de adevr f. >vident, doi

conectori logici n ari corespunztori aceleiai funcii de adevr fau proprietatea c

pentru orice 3 &( , ,..., )n S'Q( n avem

3 & 3 &( , ..., ) ( , ..., )n n' ' .

n ceea ce urmeaz vom analiza numai cazurile 3n = i &n = i deci vom vorbidespre conectori logici unari i binari.

>vident, negaia este un conector logic unar. entru a descrie toi conectorii unari

vom descrie mai nt2i toate aplicaiile $JE,3K JE,3Kf . Acestea sunt n numr de

&& @= , le notm cu 3 & + @, , ,f f f f i putem s le descriem, pe scurt, folosind urmtoarele

tabele$

3 & + @( ) ( ) ( ) ( )

E E E 3 3

3 E 3 E 3

x f x f x f x f x

!onectori logici corespunztori funciilor de adevr 3 & + @, , ,f f f f de mai sus sunt ,evident,

apicaiile 3 & + @, , , $' ' ' ' S'Q( S'Q(definite respectiv prin$

3( )' = , & ( )' = , + ( )' = , @ ( )' =

!onectorii 3 & @, ,' ' ' sunt, evident triviali$ 3' i @' corespund unor funcii de adevr

constante iar &' corespunde funciei identice8 reinem ca conector logic unar i netrivial

numai pe +' = .

B&


53/135

entru descrierea conectorilor logici binari procedm n mod asemntor$ numrul

funciilor de adevr &$JE,3K JE,3Kf este @& 3= i anume $

3 & + @ B F L( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )

E E E E E E 3 E E 3

E 3 E E E 3 E E 3 E

3 E E E 3 E E 3 E E

3 3 E 3 E E E 3 3 3

x - f x - f x - f x - f x - f x - f x - f x - f x -

= 3E 33 3& 3+ 3@ 3B 3( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , ) ( , )

E E E 3 3 E 3 3 3 3

E 3 3 E 3 3 E 3 3 3

3 E 3 3 E 3 3 E 3 3

3 3 E E E 3 3 3 E 3

x - f x - f x - f x - f x - f x - f x - f x - f x -

!onectori logici corespunztori funciilor de adevr 3 3( )i if de mai sus sunt

aplicaiile $i' S'Q( & S'Q(,3 3i ,definite prin$

3( , )' = , & ( , )' = , + ( , ) ( )' = , @ ( , ) ( ),' =

B ( , ) ( )' = , ( , )' = , F ( , )' = , L ( , )' = ,

=( , ) ( )' = , 3E ( , )' = , 33( , )' = , 3& ( , )' = ,

3+( , )' = , 3@ ( , )' = , 3B ( , ) ( )' = , 3 ( , )' = .

#intre conectorii logici binari de mai sus am luat n consideraie p2n acum numai

pe &' = , 3&' = , 3@' = , L' = . 3'i 3' sunt ntrun anumit sens constani i deci

triviali iar F 3E 33, , i' ' ' ' sunt practic conectori unari( n sensul c ei acioneaz numai

pe o singur component). 3B B + =, , i' ' ' ' sunt respectiv negaii pentru , , i .

B+


54/135

3+' este un conector dual cu iar @' este negaia sa. !onectorul =' se mai noteaz i

cu i se numete ;dis9uncie excusiv;( vezi 1eciunea 3)$ ( ) = iar 3+'

se mai noteaz i $ = . %n rol special n logic l au conectorii 3B'

( negaia con9unciei) i B' ( negaia dis9unciei). !onectorul 3B' se noteaz cu $

( ) = iar conectorul 3B' se noteaz cu $ ( ) = 8 tabelele de

adevr ale acestor conectori sunt, evident$

E E 3

E 3 E

3 E E3 3 E

.

E E 3

E 3 3

3 E 33 3 E

.

#in aceste tabele de adevr razult c este o propoziie adevrat dac i numai

dac i sunt ambele false iar este o propoziie fals dac si numai dac i

sunt ambele adevrate. n particular avem$

( ) i ( ) .

+.2. $e!iniie. ' mulime Cde conectori logici se numete adecvat( sausuficient)

dac pentru orice propoziie S'Q(exist o propoziie S'Q(n a crei expresie

apar numai conectori din Castfel nc2t .

%rmtorea propoziie ofer c2teva exemple de mulimi adecvate de conectori logici.

Acestea sunt importante deoarece exprimarea propoziiilor numai cu conectori logici

dintr/o mulime adecvat de conectori Cpoate conduce, dup cum vom vedea la noi

metode de a studia propoziiile respective.

+.%. &ropoziie. 5rmtoarele mulimi sunt mulimi adecvate de conectori$

(a) J , K , (b) J , K , (c) J , K .

B@


55/135

Demonstarie.(a) entru orice dou propoziii atomice ,! " Qavem, conform

uneia dintre legile lui #e 6organ i legii dublei negaii,

(3) ( )! " ! " .

#e asemenea o ec-ivalen bine cunoscut este$

(&) ! " ! " .

#in cele dou ec-ivalene de mai sus rezult$

( ) ( ) ( ( ) ( )) ( ( ) ( ))! " ! " " ! ! " " ! ! " " !

i reinem

(+) ( ( ) ( ))! " ! " " ! .

Acum faptul c J , K este o mulime adecvat de conectori rezult aplic2nd principiul

de inducie pentru propozitii. ntr/adevr fie

P= J S(Q) Q exist S'Q(astfel nc2t i n expresia lui apar

numai conectorii i K.

>vident, avem QP. :ie P, i n expresia lui apar numai conectorii i

. !onform ?emei B.F, avem i, evident, n expresia lui apar numai

conectorii i astfel c P. Acum fie , P, , , i n expresiile

lui i apar numai conectorii i . !onform ?emei B.F, avem i,

evident, n expresa lui apar numai conectorii i astfel c P. !onform

lui (3) , ?emei B.F i !orolarului B.+, avem ( ) i, evident, n

expresa lui ( ) apar numai conectorii i astfel c P. n mod

asemntor, dar folosind (&) i respectiv (+), deducem P i P.

!onform principiului de inducie pentru propoziii, avemP=S(Q) ceea/ce nu nseamn

altceva dec2t c J , K este o mulime adecvat de conectori.

BB


56/135

(b) #in legea lui #e 6organ i legea dublei negaii rezult$

( )! " ! " .

Avem

( ) ( )! " ! " ! " ! "

i reinem

( )! " ! " .

n fine

( ) ( ) ( ) ( )! " ! " " ! ! " " !

deci

( ) ( )! " ! " " ! .

:aptul c J , K este o mulime adecvat de conectori rezult acum aplic2nd principiul

de inducie pentru propozitii ca n demonstraia lui (a).

(c) Avem

( ) ( )! " ! " ! " ! "

i reinem

( )! " ! " .

#e asemenea

( ) ( )! " ! " ! " ! "

deci

! " ! " .

B


57/135

n fine

( ) ( )! " ! " " ! .

+.).&ropoziie.6ulimile J K i J K sunt mulimi adecvate de conectori.

Demonstraie.Ceamintim c, pentru , S'Q( avem$

( ) = i ( ) = .

n particular, pentru ,! " Q, avem

( )! ! ! ! ! = , ( )! ! ! ! ! =

( ) ( ) (( ) ( )) ( )! ! " " ! ! " " ! " ! " ! " ,

( ) ( ) (( ) ( )) ( )! ! " " ! ! " " ! " ! " ! " .

:aptul c J K este o mulime adecvat de conectori rezult acum din ropoziia .@.(a)

iar faptul c J K este o mulime adecvat de conectori rezult din ropoziia .@. (b).

+.*. &ropoziie. 'ie o un conector logic #inar astfel $nc(t J Ko este o mulime

adecvat de conectori. !tunci avem o pentru orice , S(Q) sau

o pentru orice , S(Q).

Demonstaraie. !onectorul o corespunde unei funcii de adevr

$JE,3K JE,3K JE,3K g

i, conform #efiniiei .3., pentru orice dou propoziii , S'Q( i pentru orive

valorizare vavem

BF


58/135

(P) ( ) ( ) ( )v v v =o g .

resupunem E E E=g sau 3 3 3=g :ie !Q. !onform #efiniiei .&., exist o propoziie

S'Q( n a crei expresie apare numai conectorul o astfel nct ! i fie

3 &, ,..., n! ! ! atomii care apar n aceast expresie. n cazul E E E=g considerm o

valorizare vastfel nct 3 &( ) ( ) ( ) ... ( ) Env ! v ! v ! v != = = = = 8 din (P) rezult ( ) Ev = i

deci

3 E ( ) ( ) ( ) Ev ! v ! v = = = = =

ceea ce este o contradicie. Analog, n cazul 3 3 3=g considerm o valorizare vastfel nc2t

3 &( ) ( ) ( ) ... ( ) 3nv ! v ! v ! v != = = = =

i rezult$

E 3 ( ) ( ) ( ) 3v ! v ! v = = = = =

ceea ce este de asemenea o contradicie. rin urmare avem E E 3=g i 3 3 E=g . Acum

presupunem E 3 E=g i 3 E 3=g sau E 3 3=g i 3 E 3=g . 7abelul de adevr pentru conectorul

o

este

E E 3

E 3 E

3 E 3

3 3 E

o

sau

E E 3

E 3 3

3 E E

3 3 E

o

i arat c n primul c pentru orice dou propoziii , S'Q(avem, n primul caz

o i n al doilea caz o . #eoarece J Ko este o mulime adecvat de

conectori logici rezult, n ambele cazuri, c J K este de asemenea o mulime adecvat i

vom arta acum c acest lucru este imposibil. ntr/adevar dac J K este mulime adecvat

atunci avem, pentru un atom !Q, ! ! unde este o propoziie n expresia

creia apare numai conectorul 8 evident, exist o valorizare vastfel nc2t ( ) Ev = n

BL


59/135

timp ce ( ) 3v ! ! = . Am demonstrat astfel c tabelul de adevr pentru conectorul o

este

E E 3E 3 E

3 E E

3 3 E

o

sauE E 3E 3 3

3 E 3

3 3 E

o

adic o pentru orice , S'Q(sau o pentru orice , S'Q(.

Exerciii

1.#emonstrai urmtoarele ec-ivalene$

a) ! ! ! ! ! 8

b) ! " " ! i ! " " ! 8

c)! " " ! 8

d) ( ) ( )! " C ! " C 8

e) ( ) ( )! " ! " " ! .

2.#emonstrai c J , K nu este o mulime adecvat de conectori.

%. Artai c nici una dintre propozitiile$

a) ! " , b) ! " , c) ! "

nu poate fi ec-ivalent cu o propoziie n expresia creia apare numai conectorul .

B=


60/135

). #emonstrai c aplicaia $7 S'Q( + S'Q( definit,pentru orice , , S'Q(

prin ( , , )7 = este un conector logic ternar i c J K7 este o mulime

adecvat de conectori.

Rezolvri

1.a) Avem ! ! ( )! ! != , ! ! ( )! ! != .

b) ( ) ( )! " ! " " ! " ! = = . Analog ! " " ! .

c) ( ) ( )! " ! " " ! " ! = = .

d) Avem, conform >xerciiului B.&.9)$

( ) ( ( ) ) ( ) ( )! " C ! " C ! " C ! " C = ,

( ) ( ( )) ( ) ( )! " C ! " C ! " C ! " C =

i afirmaia rezult deoarece ( ) ( )! " C ! " C .

e) :olosim tablele de adevr$

E E E

E 3 3

3 3 E

3 E 3

! "

,

( ) ( )

E E 3 E E E E 3 E

E E 3 3 3 3 3 E E

3 3 E E 3 E E 3 3

E 3 3 3 E E 3 3 3

! " " !

2. resupunem, prin absurd, c J , K este o mulime adecvat de conectori iconsiderm propoziia ! " . Atunci exist o propoziie n a crei expresie apar

numai conectorii i astfel nc2t ! " . !onsiderm o valorizare vastfel nc2t

( ) ( ) 3v ! v "= = i avem, evident, ( ) Ev ! " = i ( ) 3v = ceea ce este o contradicie.

E


61/135

%. a) resupunem c ! " unde este o propoziie n expresia creia apare

numai conectorul i fie 3 &, ,..., n! ! ! atomii distinci care apar n expresia lui .

utem considera o valorizare vastfel nc2t 3 &( ) ( ) ( ) ( ) ... ( ) Env ! v " v ! v ! v != = = = = = .

n raport cu aceast valorizare avem, evident, ( ) Ev ! " = i ( ) 3v = ceea ce este o

contradicie.

b) 1e repet raionamentul de la a).

c) resupunem c ! " unde este o propoziie n expresia creia apare

numai conectorul . om demonstra, prin inducie dup lungimea lui , c exist o

valorizare v astfel nc2t ( ) Ev ! " = i ( ) 3v = ceea ce, evident contrazice ipoteza.

entru 3n= propoziia este un atom. #ac ! = lum ( ) 3v ! = i ( ) Ev " = 8 dac

" = lum ( ) Ev ! = i ( ) 3v " = . #ac J , KC ! "= lum ( ) 3v ! = , ( ) Ev " = i

( ) 3v C = . resupunem 3n> . Atunci 3 & = unde 3 &, sunt propoziii n expresia

creia apare numai conectorul i care au lungimea strict mai mic dec2t n. !onform

ipotezei de inducie exist o valorizare v astfel nc2t ( ) Ev ! " = i &( ) 3v = . #ar

&( ) 3v = implic, evident, 3 &( ) ( ) 3v v = = .

). Avem$ ( , , )7 ! ! ! ! ! ! ! ! != iar ( , , )7 ! ! ! ! ! ! =

este o tautologie8 notm aceast tautologie cu 8i avem$

( , , ) ( )7 ! " 8 ! " 8 ! "= deci

( , , ) ( ( , , ), ( , , ), ( , , ))! " 7 ! " 8 7 7 ! " 8 7 ! " 8 7 ! " 8

( ( , , ( , , )), ( , , ( , , )), ( , , ( , , )))7 7 ! " 7 ! ! ! 7 ! " 7 ! ! ! 7 ! " 7 ! ! ! .

Afirmaia rezult acum deoarece J , K este o mulime adecvat de conectori.

3


62/135

,. Consisten i consecine' deducii din ipoteze(

,.1. $e!iniie. ' mulime de propoziii *S'Q(se numete consistentdac exist

o valorizare vpe S'Q( astfel nc2t orice propoziie * s fie adevrat n raport cu v8

n caz contrar * se numete inconsistent.. n particular, dac * J K= atunci spunem c

, n loc de J K , este consistent respectiv inconsistent. ' valorizare v se numete

interpretarea lui *dac orice propoziie * este adevrat n raport cu v. 0otm cu

Int(*Kmulimea tuturor interpretrilor lui *. Astfel * este consistent dac i numai dac

Int(*K i inconsistent dac i numai dacInt(*K = .

6ulimea de propoziii *se numetefalsifica#ildac exist o valorizare vastfel

nc2t orice propoziie * s fie fals n raport cu v8 n particular o propoziie se

numete falsificabil dac J K este falsificabil.

,.2. 0eorem.'ie S'Q(o propoziie.

(a) este consistent dac i numai dac este falsifica#il.

(#) este tautologie dac i numai dac este contradicie.

Demonstraie. :ie vo valorizare arbitrar. Avem ( ) ( )v v = i, deoarece

E 3 = i 3 E = , rezult ( ) 3v = dac i numai dac ( ) Ev = ceea ce demonstreaz

afirmaia de la (a). Afirmaia de la (b) este de asemenea evident.

,.%. $e!iniie. 7eorema F.&. furnizeaz o metod de dmonstraie n logic numi

demonstraie prin respingere i anume n loc s se demonstreze c o propoziie este

consistent sau tautologie se demonstreaz c este falsificabil respectiv

&


63/135

contradicie. n acest moment metoda poate prea pueril dar se va dovedi c n practic

ea este foarte eficient.

,.). Exemplu. 6ulimea de propoziii J , K! " ! " este inconsistent. ntr/

adevr, fie vo valorizare oarecare. resupunem ( ) 3v ! " = . Atunci

3 ( ) ( ) ( )v ! " v ! v "= =

ceea ce implic ( ) ( ) 3v ! v "= = deci ( ) 3v ! = i ( ) Ev " = . Cezult$

( ) ( ) ( ) 3 E Ev ! " v ! v " = = = .

Astfel nu exist nici o valorizare v n raport cu care toate propoziiile din

J , K! " ! " s fie adevrate.

ropoziia urmtoare d o lis de proprieti ale entitilor definite mai sus care sunt

evidente motiv pentru care nu vom mai expune i demonstraia lor .

,.*. &ropoziie.'ie * o mulime de propozii i S'Q(.Avem$

(a) Dac * este consistent atunci mulimea OJ K* este de asemenea consistent.

(b)Dac * este consistent i este tautologie atunci mulimea J K* este de

asemenea consistent.

(c) #ac * este inconsistent atunci J K* este de asemenea inconsistent.

(d) Dac * este inconsistent atunci OJ K* este de asemenea inconsistent.

+


64/135

,.+. $e!iniie. :ie * S'Q(o mulime de propoziii. ' propoziie oarecare

S'Q(se numete consecin a lui *dac pentru orice interpretare va lui *avem ( ) 3v =

( adic dac toate propoziiile din * sunt adevrate n raport cu v atunci i este

adevrat n raport cu v i n aceast situaie scriem *Q==

. utem privi *ca o mulimede ipoteze i consecinele ale lui * ca propoziii care pot fi deduse din aceste ipoteze.

6ulimea tuturor consecinelor lui * se va nota cu Con(*).

,.,. &ropoziie.'ie { }3 &, ,..., n* = S(Q)o mulime finit de propoziii. !vem

3 &J , ,..., K Qn == dac i numai dac 3 &J ... K Qn == .

Demonstraie. Afirmaia rezult deoarece pentru orice valorizare v avem

3 &( ) ( ) ( ) 3nv v v = = = dac i numai dac ( )3 & ... 3nv = .

,.-. Exemple triviale. #ac *= mulimea vid, atunci, evident, o propoziie

este consecin a lui * dac i numai dac este tautologie. Astfel dac notm cu 8aut

mulimea tuturor tautologiilor dinS'Q( avem$ ( )Con 8aut = sau altfel spus pentru o

propoziie * avem$

Q == dac i numai dac este tautologie.

#e obicei n loc de Q == scriem Q == . #e asemenea este evident c pentru orice

mulime de propoziii *i orice tautologie avem *Q== sau, altfel spus, pentru orice

mulime de propoziii * avem ( )8aut Con * . !a un alt exemplu trivial menionm c

pentru orice mulime de propoziii *avem ( )* Con * sau,altfel spus, dac * atunci

*Q== .

,.. Exemplu. Avem$

@


65/135

J , K! " " C Q== C.

ntr/adevr fie vo valorizare astefel nc2t ( ) ( ) 3v ! " v " C = = . #eoarece propoziia

! " este adevrat n raport cu valorizarea vrezult c! i"sunt ambele adevrate n

raport cu vadic ( ) ( ) 3v ! v "= = . #ac presupunem, prin absurd, ( ) Ev C = , rezult

3 ( ) ( ) ( ) 3 E Ev " C v " v C = = = = ,

o contradicie. Astfel ( ) 3v C = i C este o consecin a celor dou propoziii ! " i

" C .

,.1/. &ropoziie.'ie 3 &, ,* * * S'Q(. Avem$

(a) #ac 3 &* * atunci & 3( ) ( )Int * Int * i 3 &( ) ( )Con * Con * .

(b) ( ) ( ( ))Con * Con Con * = .

(c) ( ) JCon * = S'Q( Q ( ) 3v = pentru orice ( )Kv Int * .

Demonstraie. (a) :ie &( )v Int * . entru orice 3* avem, deoarece 3 &* * ,

&* deci ( ) 3v = 8 astfel 3( )v Int * . Acum fie 3( )Con * . :ie vo interpretare a lui

&* . Atunci, pentru orice 3 &* * , avem ( ) 3v = i, n particular, ( ) 3v = 8 astfel

&( )Con * .

(b) #eoarece ( )* Con * avem, conform lui (a), ( ) ( ( ))Con * Con Con * .

Ceciproc, fie ( ( ))Con Con * i v o interpretare a lui *$ ( )v Int * 8 atunci ( ) 3v =

pentru orice ( )Con * ceea ce implic ( ) 3v = . Astfel ( )Con * i deci

( ) ( ( ))Con * Con Con * i ( ) ( ( ))Con * Con Con * = .

(c) >vident.

B


66/135

,.11. 0eorem' 0eorema $educiei pentru consecine(. 'ie * o mulime de

propoziii i , S'Q(. !vem $

* J K Q == dac i numai dac *Q == .

Demonstraie.resupunem c * J K Q == i fie vo valorizare astfel nc2t ( ) 3v =

pentru orice * . #ac ( ) 3v = atunci veste o interpretare a lui * J K i, conform

ipotezei, ( ) 3v = . Astfel

( ) ( ) ( ) 3 3 3v v v = = = 8

i *Q = .

Ceciproc presupunem c *Q = i fie vo interpretare a lui * J K . Atunci n

particular, v este o interpretare a lui * i deci ( ) 3v = . #ac presupunem c

( ) 3v = rezult

3 ( ) ( ) ( ) 3 ( )v v v v = = =

ceea ce implic, ( ) 3v = i concluzia * J KQ = este evident.

,.12. Corolar.'ie n un numr $ntreg pozitiv i 3 &, ,..., ,n S'Q(.

5rmtoarele afirmaii sunt echivalente$

a) 3 &J , ,... K Qn == 8

b)0ropoziia 3 &( ... ( )...)n este o tautologie8

c)0ropoziia 3 & ... n este o tautologie.


67/135

Demonstraie. a) b) *nducie dup n. entru 3n = avem, conform 7eoremei F.3E,

3 3J K J KQ = = dac i numai dac 3Q = i deci 3J KQ = dac i numai

dac 3 este o tautologie. resupunem &n . !onform 7eoremei F.3E.,

3 & 3 3 & 3J , ,..., K J K J , ,..., , K Qn n n n = ==

dac i numai dac

3 3J ,..., Kn Q== n

i, conform ipotezei de inducie, 3 3J ,..., Kn Q== n dac i numai dac

3 &( ... ( )...)n este tautologie.

b) c) !onform ropoziiei F.F, avem 3 &J , ,..., K Qn == dac i numai dac

3 &J ... K Qn == i, conform 7eoremei F.33., 3 &J ... K Qn == dac i

numai dacpropoziia 3 & ... n este o tautologie.

Exerciii.

1. #emonstrai , folosind metoda tablelor de adevr, c mulimea de propoziii

*= J ( ), K! " C ! C

este consistent i determinai toate interpretrile lui *.

2. #emonsrai c J , K Q! " ! C " C == .

%.:ie * J , , ( ) ( )K! C " D ! " C D= .Artai c propoziia

( ) ( )! " C D

nu este consecin a lui *.

F


68/135

). :ie *3 , *&

Vraciu - Logica 1 (Logica Propozitiilor).pdf

Documents

Transcript of Vraciu - Logica 1 (Logica Propozitiilor).pdf