Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

 
CATEGORII DOCUMENTE



AstronomieBiofizicaBiologieBotanicaCartiChimieCopii
Educatie civicaFabule ghicitoriFizicaGramaticaJocLiteratura romanaLogica
MatematicaPoeziiPsihologie psihiatrieSociologie


Echivalenta propozitiilor

Logica

+ Font mai mare | - Font mai mic


DOCUMENTE SIMILARE

Trimite pe Messenger
Alfabetul si sintaxa in logica propozitiilor
Conectori logici
Probleme glume
Concepte semantice in logica propozitiilor
Consistenta si consecinte (deductii din ipoteze)
Propozitii compuse
Termeni - logica
Propozitii categorice
LOGICA - Logica clasica, Logica matematica
LOGICA - Raporturi logice intre termeni

TERMENI importanti pentru acest document

: legile echivalentei 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

        1. 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.

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 392
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Distribuie URL

Adauga cod HTML in site

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2014. All rights reserved