Transcript: Formule de calcul propozițional. Legile De Morgan

Maria nu are stilou, dar scrie frumos.
Să vedem cum putem să transcriem această propoziție în limbaj matematic.
Dacă notăm propoziția Maria are stilou cu P,
atunci propoziția Maria nu are stilou va fi non P.
Haideți să notăm propoziția scrie frumos cu Q.
Atunci această propoziție, Maria nu are stilou, dar scrie frumos,
se poate citi și astfel, Maria nu are stilou și scrie frumos.
Deci putem să punem o conjuncție între propozițiile non P și Q.
Un alt exemplu, dacă Maria câștigă concursul și merge în excursie,
atunci ea este fericită.
O să notăm cu P propoziția Maria câștigă concursul
Notez cu Q propoziția merge în excursie
și cu R propoziția ea este fericită.
Observăm că între propozițiile P și Q avem o conjuncție
și de asemenea regăsim sintagma Dacă, Atunci.
Înseamnă că avem o implicație,
deci putem să scriem astfel,
propoziția P și Q implică R.
Aceste formule pe care le-am găsit,
non P și Q, respectiv P și Q implică R,
se numesc formule de calcul propozițional
și despre acestea vreau să discutăm în filmul acesta.
Formulele de calcul propozițional se notează de obicei cu litere grecești,
alfa, beta, gamma și așa mai departe,
iar literele P, Q, R care apar în cadrul acestora
se numesc variabile propoziționale.
Formulele propoziționale se pot nota și scriend în paranteză
variabilele care apar,
deci putem să scriem alfa și în paranteză P și Q,
respectiv beta și în paranteză să scriem propozițiile P, Q, R
care apar în cadrul acestei formule.
Prin urmare, o formulă propozițională este o expresie obținută din propoziții simple
cu ajutorul operatorilor logici.
Două formule, alfa și beta, se numesc echivalente
și o să scriem astfel
dacă pentru orice valor de adevăr ale variabilelor propoziționale
expresiile au aceeași valoare de adevăr.
O să vedem imediat câteva exemple de formule echivalente,
dar mai întâi aș vrea să facem o scurtă recapitulare a operațiilor cu propoziții
pe care le-am văzut în lecțiile trecute.
Operațiile pe care le-am învățat în acest capitol au fost negația,
conjuncția, disjuncția, implicația și echivalența.
Aceste simboluri se mai numesc și operatori logici.
Negația se poate nota așa sau se mai notează și cu o vară deasupra.
Deci notația non P, scrisă așa, este același lucru cu un P barat
sau notația aceasta non P și Q
înseamnă același lucru cu P și Q barat.
Vom ține cont de ordinea în care am scris acești operatori
pentru că aceasta este și regula de prioritate a operațiilor
într-o formulă propozițională.
Deci mai întâi o să facem negația,
apoi conjuncția, disjuncția, implicația și echivalența.
În cazul în care într-o formulă apar și paranteze,
o să ținem cont și de acestea.
Și acum să dăm un exemplu de două formule echivalente.
De exemplu, negația propoziției P sau Q
este logic echivalentă cu non P și non Q.
Și o să demonstrăm imediat această relație.
O altă relație de echivalență,
negația propoziției P și Q
este logic echivalentă cu negația propoziției P
sau negația propoziției Q.
Vom demonstra mai întâi prima relație.
Pentru aceasta vom face un tabel pentru valorile de adevăr.
Avem propoziția P, propoziția Q,
propoziția P sau Q.
Urmează negația propoziției P sau Q
pe care am notat-o cu alfa.
În continuare avem negația propoziției P,
negația propoziției Q
și conjuncția dintre cele două negații,
iar această formulă am notat-o cu beta.
Ne propunem să arătăm că alfa este echivalentă cu beta.
Pe primele două coloane vom scrie
valorile de adevăr pentru propozițiile P și Q.
În cazul în care sunt două propoziții într-o formulă
avem 2 la 2-a combinații posibile, adică 4,
iar dacă sunt trei propoziții P, Q, R
avem 2 la 3-a combinații posibile, adică 8.
Acum ne propunem să scriem valoarea de adevăr
pentru propoziția P sau Q.
Vă reamintesc că disjuncția este adevărată
dacă cel puțin una dintre cele două propoziții
este adevărată.
Prin urmare o să avem 0, 1, 1, 1.
Acum urmează negația acestei propoziții,
1, 0, 0, 0.
În continuare o să scriem negația propoziției P.
Deci ne uităm pe prima coloană.
Dacă P este falsă, negația este adevărată
și dacă P este adevărată, negația acesteia este falsă.
Urmează negația propoziției Q,
ne uităm pe această coloană
și avem 1, 0, 1, 0.
Conjuncția dintre aceste două propoziții,
conjuncția este adevărată dacă ambele propoziții
sunt adevărate.
În caz contrar este falsă.
Deci o să avem 1, 0, 0, 0.
Acum dacă ne uităm în aceste coloane
în care avem formulele alpha și beta,
observăm că ele au aceleași valori de adevăr.
Prin urmare vom spune că cele două formule sunt echivalente.
În continuare ne propunem să demonstrăm
a doua relație de echivalență.
Pentru aceasta vom face un alt tabel.
Avem propoziția P, Q, P și Q.
Urmează negația propoziției P și Q
pe care o să o notăm cu alpha.
Non-P, non-Q și disjuncția propozițiilor non-P, non-Q
pe care am notat-o cu beta.
Să verificăm dacă alpha este logic echivalentă cu beta.
Scriem din nou valorile de adevăr pentru P și Q.
0, 0, 1, 1, 0, 1, 0, 1.
P și Q este adevărată dacă ambele sunt adevărate.
În caz contrariu este falsă.
Negația propoziției P și Q, 1, 1, 1, 0.
Urmează non-P, deci ne uităm pe prima coloană
și scriem negația acestei propoziții.
Avem 1, 1, 0, 0.
Urmează non-Q, 1, 0, 1, 0.
Și acum facem disjuncția dintre aceste două propoziții.
Disjuncția este adevărată dacă cel puțin una dintre propoziții este adevărată.
Prin urmare o să avem 1, 1, 1, 0.
Dacă ne uităm la valorile de adevăr pentru formulele alpha și beta,
observăm că acestea au aceeași valoare de adevăr.
Prin urmare alpha este echivalentă cu beta.
Aceste două relații pe care tocmai le-am demonstrat
se numesc formulele lui De Morgan sau legile lui De Morgan.
Să reținem așadar aceste două legi ale lui De Morgan
și să vedem acum concret cum putem să le aplicăm.
Dacă avem următoarea propoziție,
triunghiul este isoscel sau echilateral
și dorim să scriem negația acestei propoziții,
o să folosim prima formulă
având în vedere că avem aici o disjuncție.
Negația disjuncției este logic echivalentă
cu conjuncția negațiilor celor două propoziții.
Prin urmare trebuie să negăm propoziția triunghiul este isoscel.
Am folosit aici această negație.
Negăm și a doua propoziție,
triunghiul nu este echilateral
iar disjuncția se transformă în conjuncție.
Și atunci negația acestei propoziții sună astfel,
triunghiul nu este isoscel și nu este echilateral.
Un alt exemplu, avem următoarea propoziție,
triunghiul este isoscel și are un ung drept.
Observăm că avem aici o conjuncție,
prin urmare trebuie să aplicăm a doua formulă.
Negația unei conjuncții este echivalentă cu disjuncția negațiilor.
Așadar negăm cele două propoziții.
Negația primei propoziții va fi triunghiul nu este isoscel.
Negația propoziției are un ung drept este
propoziția nu are un ung drept
iar cuvântul și devine sau.
Și atunci negația va fi următoarea propoziție,
triunghiul nu este isoscel sau nu are un ung drept.
Acestea sunt legile lui de Morgan pentru calculul propozițiilor,
însă aceste două formule pot fi aplicate și în cazul în care avem operații cu mulțimi.
Vă reamintesc că fiecare operație cu propoziții a fost asociată cu o operație cu mulțimi.
Dacă vă mai amintiți, negația a fost asociată cu complementarea unei mulțimi,
disjuncția a fost asociată cu reuniunea mulțimilor
și conjuncția a fost asociată cu intersecția mulțimilor.
Prin urmare, haideți să vedem cum putem să transcriem aceste formule folosind operații cu mulțimi.
Fie A și B două sunt mulțimi ale unei mulțimi D,
atunci disjuncția propozițiilor P și Q poate fi asociată cu reuniunea celor două mulțimi,
deci avem A reunit cu B,
însă aici avem negația disjuncției,
prin urmare trebuie să aplicăm complementarea acestei mulțimi în raport cu D.
Egal, mai departe,
non P poate fi asociată cu complementarea mulțimii A în raport cu D,
conjuncția înseamnă intersecție de mulțimi,
iar negația propoziției Q este asociată cu complementarea mulțimii B în raport cu D.
Și atunci această relație se citește astfel,
complementarea reuniunii a două mulțimi este egală cu intersecția complementarelor.
Să vedem acum cum putem să transcriem a doua formulă folosind operații cu mulțimi,
avem aici o conjuncție de propoziții,
conjuncția se transcrie ca intersecție de mulțimi,
A intersectată cu B,
avem și aici negația conjuncției,
prin urmare o să avem complementarea acestei mulțimi în raport cu D,
egal, negația lui P este asociată cu complementarea mulțimii A în raport cu D,
iar disjuncția propozițiilor înseamnă, de fapt, reuniune de mulțimi,
reunită cu complementarea mulțimii B în raport cu D.
Citim astfel, complementarea intersecției a două mulțimi este egală cu reuniunea complementarelor.
Acestea sunt formulele lui de Morgan în cazul operațiilor cu mulțimi,
iar în continuare o să facem câteva exerciții în care o să stabilim valorile de adevăr ale unor formule propoziționale.
Avem următoarea formulă propozițională pe care am notat-o cu gama P implică Q sau Q implică P.
Pentru a stabili valorile de adevăr pentru formula în gama am realizat un tabel
în care vom trece valorile de adevăr posibile pentru propozițiile P și Q.
Avem 0011, 0101.
Din moment ce avem aici paranteze vom ține cont de acestea.
Prin urmare mai trebuie să trecem în tabel implicația P implică Q, apoi Q implică P,
iar pe ultima coloană avem dizjungția dintre cele două implicații, mai exact formula în gama.
Să stabilim acum valoarea de adevăr pentru propoziția P implică Q.
Aceasta este falsă numai în condiția în care P este adevărată și Q este falsă.
Deci pe această linie avem 0, în rest peste tot o să avem 1.
Q implică P este falsă dacă Q este adevărată și P este falsă.
Aici avem 0, în rest peste tot 1.
În continuare trebuie să facem dizjungția dintre aceste două propoziții.
Aceasta este adevărată dacă cel puțin una dintre propoziții este adevărată.
O să avem 1, 1, 1, 1.
Observăm că formula în gama are numai valoarea 1 indiferent de valorile de adevăr ale propozițiilor P și Q.
O astfel de expresie se numește tautologie.
Să reținem deci că o tautologie este o expresie adevărată indiferent de valorile de adevăr ale variabilelor propoziționale.
Eu zic că sunt distractive aceste exerciții. Ce ziceți? Mai facem unul!
Am auzit un da colectiv, așa că o să mai fac un exercițiu.
Avem următoarea formulă propozițională pe care am notat-o cu delta.
P implică Q sau P, echivalent cu Q și P.
După cum observăm în această formulă nu avem paranteze, dar trebuie să ținem cont de ordinea în care aplicăm operatorii logici.
Avem o implicație și o dizjungție. Prioritară va fi dizjungția.
Dacă doriți putem să punem o paranteză ca să fie mai clar acest lucru.
Apoi avem o echivalență și o conjunție. Prioritară va fi conjunția.
Acum, între implicație și echivalență, prioritară este implicația, deci putem să punem aici o paranteză dreaptă.
Trecem mai întâi valorile de adevăr pentru P și Q. Urmează Q sau P, adică această paranteză rotundă.
După aceea am scris paranteza dreaptă P implică Q sau P.
După aceea o să scriem valoarea de adevăr pentru această paranteză rotundă Q și P.
Și la final echivalența dintre cele două paranteze, adică formula delta.
0011, 0101. Q sau P este adevărată dacă cel puțin una dintre propoziții este adevărată. 0111.
P implică Q sau P. Ne uităm pe această coloană și pe coloana cu propoziția Q sau P.
Trebuie să scriem valoarea de adevăr pentru implicația acestora.
Implicația este falsă dacă prima propoziție este adevărată și a doua propoziție este falsă.
Însă nu avem această situație aici. Prin urmare această implicație va fi adevărată.
Acum să scriem valoarea de adevăr pentru propoziția Q și P.
Conjuncția este adevărată dacă ambele propoziții sunt adevărate.
Ne uităm pe primele două coloane. Observăm că în ultimul caz avem o conjuncție adevărată, în rest este falsă.
Și acum trebuie să stabilim valoarea de adevăr pentru echivalența dintre aceste două propoziții.
Echivalența este adevărată numai atunci când cele două propoziții au aceeași valoare de adevăr, adică aici.
În rest avem peste tot zero.
Acestea au fost exercițiile cu formule de calcul propozițional.
Vă rămâne ca temă să arătați că negația propoziției NON P este logic echivalentă cu propoziția P, adică dubla negație a unei propoziții coincide cu propoziția inițială.
Și mai puteți să arătați că propoziția P sau NON P este o tautologie.
O scurtă observație aș vrea să mai facem. Această lege a dublei negații nu se aplică întotdeauna și în gramatica limbii române.
De exemplu, dacă avem propoziția NU AM NICIO PROBLEMĂ, aici avem o dublă negație.
Dacă tăiem aceste negații, rămâne propoziția AM O PROBLEMĂ, însă propoziția NU AM NICIO PROBLEMĂ nu este același lucru cu propoziția AM O PROBLEMĂ.
Prin urmare, putem trage concluzia că gramatica nu are logică.
Dar oare matematica are logică din moment ce este adevărată propoziția Dacă 1 plus 1 egal 5, atunci elefantul zboară?