Echivalenta propozitiilor

Echivalenta propozitiilor

1. Definitie. Doua propozitii S(Q) se numesc echivalente si scriem daca pentru orice valorizare v pe S(Q) avem .

2. Propozitie. Doua propozitii S(Q) sunt echivalente daca si numai daca propozitia este tautologie.

Demonstratie. Tabelul de adevar al implicatiei prezentat in Sectiunea 4. arata ca, pentru orice valorizare v avem daca si numai daca ceea ce inseamna ca este tautologie daca si numai daca .

3. Corolar. Fie S(Q) astfel incat, n un numar intreg pozitiv, S(Q) si Q. Atunci .

Demonstratie. Conform lui 2., este tautologie si, conform Teoremei 3.8., este de asemenea tautologie. Deoarece = rezulta .

4.Exemple. Din lista de tautologii prezentata la sfarsitul Sectiunii 4., rezulta, conform Propozitiei 2., urmatoarele echivalente:

( legea identitatii), ( legea dublei negatii), ( legea contrapozitiei), ( legea negarii implicatiei),

si( legile lui De Morgan).

Alte echivalente importante care sunt usor de demonstrat sau le vom demonstra in diverse exemple sau exercitii sunt:

, , , ,

, ,

, .

O metoda simpla de a demonstra echivalenta a doua propozitii si este de a face simultan tablele lor de adevar; cele doua propozitii sunt echivalente daca si numai daca coloanele corespunzatoare lui si in aceste table sunt identice.

Exemplu. Demonstram ca astfel:

Echivalenta noastra rezulta din faptul ca coloanele 3 si 6 ale tablei de mai sus sunt identice.

6. Propozitie. Relatia pe multimea S(Q) este o relatie de echivalenta.

Demonstratie. Fie S(Q). Deoarece pentru orice valorizare v avem . Presupunem ; pentru orice valorizare v avem deci ceea ce arata ca . In fine presupunem si ; pentru orice valorizare v avem si deci ceea ce arata ca . Astfel relatia este reflexiva, simetrica si tranzitiva adica este o relatie de echivalenta.

7. Lema. Fie S(Q) astfel incat si . Avem, pentru orice , si .

Demonstratie. Pentru orice valorizare v avem si rezulta, evident,

, .

8. Teorema. Fie S(Q) astfel incat . Atunci .

Demonstratie. Vom aplica Teorema 2.10. pentru multimea de propozitii

PS(Q)}.

Fie Q . Daca avem iar daca avem =A; in ambele cazuri avem, evident, deci P. Astfel QP.Acum fie P deci si . Avem, conform Lemei 7.,

=

si daca ,

=

asatfel ca P. Conform Teoremei 2.10, avem PS(Q) ceea ce demonstreaza afirmatia din enunt.

9. Exemplu. Demonstram acum echivalenta cu ajutorul tablelor de adevar:

Echivalenta noastra rezulta din faptul ca coloanele 4 si 6 coincid.

10. Exemplu. Exemplificam acum modul in care se folosesc o parte din rezultatele precedentepentru a demonstra urmatoarea echivalenta:

.

in propozitia subpropozitia se inlocuieste cu si deoarece, conform lui , avem rezulta, conform Teoremei 8,

(1) .

conform lui 4, avem si, prin inlocuirea lui A cu si a lui B cu , rezulta, conform Corolarului 3,

(2) .

in propozitia se inlocuieste subpropozitia cu si subpropozitia cu ; deoarece, conform exemplului 9 avem si, evident, rezulta:

(3) .

avem, conform lui 4., si , conform simetriei din Propozitie 6., ; prin inlocuirea lui A cu rezulta si astfel:

(4) .

In final, aplicand tranzitivitatea din Propozitia 6., rezulta din (1),(2),(3) si (4):

.

In continuare procedeul descris mai sus se va scrie pe scurt, fara referire la rezultatele teoretice folosite dar cu denumirea de metoda echivalentelor. In cazul nostru vom scrie:

.

12. Exemplu. Vom demonstra legile lui De Morgan sub forma :

si .

Pentru prima dintre ele folosim metoda tablelor de adevar:

Echivalenta rezulta din faptul ca in tabela de mai sus coloanele 1 si 6 coincid. A doua lege a lui De Morgan rezulta din prima folosind metoda echivalentelor din Exemplul 10 :

.

( am folosit legea dublei negatii: si prima lege a lui De Morgan de mai sus).

12. Definitie. Fie o propozitie in a carei expresie apar numai conectorii . Propozitia care se obtine din prin inlocuirea fiecarei aparitii a lui cu si a fiecarei aparitii a lui cu se numeste duala propozitiei . Astfel daca atunci duala lui este propozitia . Evident, pentru orice propozitie , avem .

13. Teorema( Teorema de dualitate). Pentru orice doua propozitii avem:

(i) este tautologie daca si numai daca este tautologie;

(ii) este tautologie daca si numai daca este tautologie;

(iii) daca atunci .

Demonstratie. (i) Daca este tautologie atunci, conform Corolarului 3., propozitia care se obtine din prin inlocuirea fiecarui atom A care apare in expresia lui cu negatia sa este de asemenea o tautologie. Pe de alta parte din legile lui De Morgan rezulta, evident, astfel ca este de asemenea tautologie. Pentru a demonstra afirmatia reciporoca, notam si observam ca deci . Astfel daca presupunem ca este tautologie rezulta, din cele de mai sus ca si deci este tautologie.

(ii) Avem, evident, si rezulta, conform Corolarului 3, . Astfel, conform lui (i), este tautologie daca si numai daca este tautologie. Pe de alta parte avem:

si afirmatia din enunt este evidenta.

(iii) Evident, este tautologie daca si numai daca si sunt tautologii. Deoarece rezulta ca este tautologie daca si numai daca si sunt tautologii adica, conform lui (ii), daca si numai daca este tautologie. Astfel este tautologie daca si numai daca este tautologie. Afirmatia rezulta acum din Propozitia 2.

14. Exemplu. Vom demonstra echivalentele:

, .

Prima rezulta din tablele de adevar de mai jos:

Pentru a doua procedam astfel: daca notam si avem si ; conform echivalentei precedente avem si, conform Teoremei 13., rezulta adica exact cea de a doua ecivalenta. Spunem ca a doua echivalenta rezullta din prima prin dualitate.

Exercitii

Fie S(Q). Aratati ca:

a) Daca este tautologie atunci si .

b) Daca este contradictie atunci si .

c) Daca este tautologie atunci .

2. Demonstrati urmatoarele echivalente (folosind diverse metode prezentate anterior):

a) , b) ,

c) , d) ,

e)

f) , g) , h) ,

i) , j) .

3. Aratati ca

.

4. Fie o propozitie. Demonstrati ca:

a) daca in expresia lui apare numai conectorul atunci este tautologie daca si numai daca fiecare atom AQ apare in expresia lui de un numar par de ori;

b) daca in expresia lui apar numai conectorii si atunci este tautologie daca si numai daca fiecare atom A Q precum si conectorul apar in expresia lui de un numar par de ori.

Rezolvari

1. Fie v o valorizare oarecare.

(a)   Deoarece este tautologie avem si rezulta:

,

.

(b) Deoarece este contradictie avem si rezulta:

,

.

(c) Deoarece este tautologie avem si rezulta:

.

2. a) Folosim metoda echivalentelor si avem:

.

b) Avem:

.

c) Rezulta din b) prin dualitate.

d) Avem:

.

e) Folosim Exemplu 1 si b) de si avem:

.

f) Folosim e) si avem:

.

g) Tablele de adevar sunt:

h) Rezulta din tabla de adevar de mai jos

i) Rezulta din h) prin dualitate.

j) Rezulta din tabla de adevar de mai jos:

3. Pentru mai multa claritate preferam ca propozitiile sa fie scrise sub forma completa( dar fara parantezele exterioare) si deci avem de aratat ca

.

Avem:

.

4. a) Din 2.f) si g) rezulta ca unde n este un numar intreg pozitiv si, pentru fiecare , care contine numai conectorul si toti atomii sai coincid sa zicem cu Q; evident, putem presupune ca atomii sunt distincti. Deoarece este tautologie rezulta ca, pentru fiecare , daca notam cu numarul de atomi ai lui atunci este tautologie in cazul cand este par iar in cazul impar avem ( vezi si 1.c)). Rezulta, in particular, ca daca este par pentru orice atunci este tautologie. In caz contrar avem

unde s este un numar intreg pozitiv si sunt atomi distincti; in aceasta situatie putem considera o valorizare v astfel incat si si avem, evident, .

b) Folosim 2.f), g) , j) si, in plus, tautologia . Rezulta

unde n este un numar intreg pozitiv si, pentru fiecare , este o propozitie a carei expresie contine numai conectorii si si acelasi atom sa zicem ; in plus atomii sunt distincti si numarul aparitiilor conectorului in expresia lui are aceiasi paritate cu numarul aparitiilor sale in expresia lui . Putem presupune . Pentru fiecare fie numarul aparitiilor atomului in expresia lui , egal cu numarul aparitiilor lui in expresia lui , si numarul aparitiilor conectorului in expresia lui . Avem

,

si Q. Avand in vedere ca este tautologie rezulta ca: daca si sunt pare atunci este tautologie; daca este impar si este par atunci , daca este par si este impar atunci iar daca si sunt impare atunci este o contradictie. Fie numarul indicilor astfel ca si sunt impare, numarul indicilor astfel ca par si impar sau impar si par, numarul indicilor astfel ca si sunt impare. Rezulta ca este tautologie daca si numai daca, pentru orice , si par, echivalent, daca si numai daca pentru orice , este par si este par.