Formulele lui De Morgan
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/06/Demorganlaws.svg/220px-Demorganlaws.svg.png)
În logica propozițională(d) și algebra booleană, formulele lui De Morgan,[1][2][3] cunoscute și ca legile sau teoremele lui De Morgan,[4] sunt o pereche de reguli de transformare care sunt reguli valide inferență(d). Ele sunt numite după Augustus De Morgan, un matematician britanic din secolul al XIX-lea. Regulile permit exprimarea conjuncțiilor(d) și disjuncțiilor în termeni reciproci prin negare(d).
Regulile pot fi exprimate în limbaj natural drept:
- Negația unei disjuncții este conjuncția negațiilor
- Negația unei conjuncții este disjuncția negațiilor
sau
- Complementul reuniunii a două mulțimi este același cu intersecția complementelor lor
- Complementul intersecției a două mulțimi este același cu reuniunea complementelor lor
sau
- non (A sau B) = (non A) și (non B)
- non (A și B) = (non A) sau (non B)
unde „A sau B” este „sau inclusiv” care înseamnă cel puțin unul dintre A sau B, și nu un „sau exclusiv” care înseamnă exact unul dintre A sau B.
În teoria mulțimilor și algebra booleană, acestea se scriu formal ca
Unde
- și sunt mulțimi,
- este complementul lui ,
- este intersecția și
- este reuniunea .
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/83/In_Quest_of_Univeral_Logic_Morgan.png/400px-In_Quest_of_Univeral_Logic_Morgan.png)
În limbajul formal, regulile se scriu ca
și
Unde
- P și Q sunt propoziții,
- (d) este operatorul logic de negație (NON),
- (d) este operatorul logic de conjuncție (ȘI),
- este operatorul logic de disjuncție (SAU),
- este un simbol metalogic care înseamnă „poate fi înlocuit într-o demonstrație logică(d) cu”, adesea citit ca „dacă și numai dacă” sau „este echivalent cu”. Pentru orice combinație de valori adevărat/fals pentru P și Q, părțile din stânga și din dreapta ale săgeții vor păstra aceeași valoare de adevăr după evaluare.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5e/De_Morgan%27s_law_with_set_subtraction_operation.png/220px-De_Morgan%27s_law_with_set_subtraction_operation.png)
O altă formă a legilor lui De Morgan este următoarea, așa cum se vede în figura din dreapta.
Printre aplicațiile acestor formule se numără simplificarea expresiilor(d) logice în programe de calculator și proiecte de circuite digitale. Legile lui De Morgan sunt un exemplu de concept mai general al dualității matematice.
Notație formală
[modificare | modificare sursă]Regula de negație a conjuncției poate fi scrisă în notație succesivă(d):
- ,
și
- .
Regula de negație a disjuncției poate fi scrisă astfel:
- ,
și
- .
Sub formă de regulă de inferență(d): negarea conjuncției
și negarea disjuncției
și exprimată ca tautologie(d) de adevăr funcțional sau teoremă a logicii propoziționale:
Unde și sunt propoziții exprimate într-un sistem formal.
Forma de substituție
[modificare | modificare sursă]Legile lui De Morgan sunt prezentate în mod normal în forma compactă de mai sus, cu negarea rezultatului în stânga și negarea termenilor în dreapta. O formă mai clară de substituție poate fi enunțată astfel:
Aceasta subliniază nevoia de a inversa atât intrările, cât și ieșirea, precum și de a schimba operatorul atunci când se efectuează o substituție.
Teoria mulțimilor și algebra booleană
[modificare | modificare sursă]În teoria mulțimilor și algebra booleană, este adesea menționat ca „interschimbarea de reuniunii și intersecției în raport cu complementarea”,[6] care poate fi exprimată formal ca:
Unde:
- este negația lui , bara superioară(d) fiind scrisă deasupra termenilor de negat,
- este operatorul de intersecție (ȘI),
- este operatorul de reuniune (SAU).
Reuniuni și intersecții de orice număr de mulțimi
[modificare | modificare sursă]Forma generalizată este
unde I este o mulțime de indexare, care poate fi numărabil sau nenumărabil infinită.
În notația mulțimilor, legile lui De Morgan pot fi amintite folosind mnemonica(d) „rup bara, schimb semnul”.[7]
Inginerie
[modificare | modificare sursă]În ingineria electrică și a calculatoarelor, legile lui De Morgan se scriu de regulă ca:
și
Unde:
- este ȘI logic,
- este SAU logic,
- bara superioară înseamnă negația logică a ceea ce este sub bară.
Căutarea în texte
[modificare | modificare sursă]Legile lui De Morgan se aplică în mod obișnuit în căutarea de texte folosind operatori booleeni AND, OR și NOT. Fie o mulțime de documente care conțin cuvintele „pisici” și „câini”. Legile lui De Morgan susțin că aceste două căutări vor returna aceeași mulțime de documente:
- Căutare A: NOT (pisici OR câini)
- Căutare B: (NOT pisici) AND (NOT câini)
Corpul de documente care conțin „pisici” sau „câini” poate fi reprezentat prin patru documente:
- Documentul 1: Conține doar cuvântul „pisici”.
- Documentul 2: Conține doar „câini”.
- Documentul 3: Conține atât „pisici” cât și „câini”.
- Documentul 4: Nu conține nici „pisici”, nici „câini”.
La evaluarea căutarii A, „(pisici SAU câini)”, în mod cert va returna documentele 1, 2 și 3. Deci, negarea acelei căutări (care este căutarea A) va returna orice altceva, adică documentul 4.
Evaluarea căutarii B „(NU pisici)” va returna documentele care nu conțin „pisici”, adică documentele 2 și 4. În mod similar, căutarea „(NU câini)” va returna documentele 1 și 4. Aplicarea operatorului ȘI pe aceste două căutări (Căutarea B) va returna documentele care sunt comune acestor două căutări, anume documentul 4.
O evaluare similară poate fi aplicată pentru a arăta că următoarele două căutări vor returna documentele 1, 2 și 4:
- Căutarea C: NU (pisici ȘI câini),
- Căutarea D: (NU pisici) SAU (NU câini).
Istorie
[modificare | modificare sursă]Formulele sunt denumite după Augustus De Morgan (1806–1871),[8] care a introdus o versiune formală a lor în logica propozițională(d) clasică. Enunțul lui De Morgan a fost influențat de algebrizarea logicii întreprinsă de George Boole, care mai târziu a întărit meritul lui De Morgan pentru descoperirea lor. Cu toate acestea, o observație similară fusese făcută și de Aristotel și era cunoscută de logicienii greci și medievali.[9] De exemplu, în secolul al XIV-lea, William de Ockham a notat cuvintele care ar rezulta din citirea legilor.[10] Jean Buridan, în Summulae de Dialectica, descrie și regulile de conversie care urmează liniile formulelor lui De Morgan.[11] Lui De Morgan i se acordă însă credit pentru enunțarea lor în termenii logicii formale moderne și încorporarea lor în limbajul logicii. Legile lui De Morgan pot fi demonstrate cu ușurință și pot părea chiar banale.[12] Cu toate acestea, aceste legi sunt utile pentru a face inferențe valide în demonstrații și argumente deductive.
Demonstrație informală
[modificare | modificare sursă]Teorema lui De Morgan se poate aplica negației unei disjuncții sau negației unei conjuncții(d) într-o formulă sau într-o parte a unei formule.
Negarea unei disjuncții
[modificare | modificare sursă]În cazul aplicării acesteia la o disjuncție, fie următoarea afirmație: „este fals că oricare dintre A sau B este adevărat”, ceea ce se scrie astfel:
Prin faptul că s-a stabilit că niciuna dintre A și B nu sunt adevărate, atunci trebuie să rezulte că A nu este adevărat, și(d) B nu este adevărat, ceea ce se poate scrie direct ca:
Dacă A sau B ar fi adevărate, atunci disjuncția dintre A și B ar fi adevărată, făcând ca negația să fie falsă. În limbaj natural, de aici rezultă logica că „din moment ce două lucruri sunt ambele false, este și fals că oricare dintre ele este adevărat”.
Lucrând în direcția opusă, a doua expresie afirmă că A este fals și B este fals (sau echivalent că „nu A” și „nu B” sunt adevărate). Știind acest lucru, o disjuncție a lui A și B trebuie să fie și ea falsă. Negația disjuncției menționate trebuie astfel să fie adevărată, iar rezultatul este identic cu prima afirmație.
Negarea unei conjuncții
[modificare | modificare sursă]Aplicarea teoremei lui De Morgan la conjuncție este foarte asemănătoare cu aplicarea ei la o disjuncție atât ca formă, cât și ca rațiune. Fie următoarea afirmație: „este fals că A și B sunt ambele adevărate”, care se scrie:
Pentru ca această afirmație să fie adevărată, una sau ambele dintre A sau B trebuie să fie false, pentru că dacă ambele ar fi adevărate, atunci conjuncția dintre A și B ar fi adevărată, făcând ca negația să fie falsă. Astfel, unul (cel puțin) sau mai multe dintre A și B trebuie să fie false (sau echivalent, unul sau mai multe dintre „nu A” și „nu B” trebuie să fie adevărate). Aceasta se poate scrie direct:
În limbaj natural, aceasta urmează logica că „din moment ce este fals că două lucruri sunt ambele adevărate, cel puțin unul dintre ele trebuie să fie fals”.
Lucrând din nou în direcția opusă, a doua expresie afirmă că cel puțin unul dintre „nu A” și „nu B” trebuie să fie adevărat sau, în mod echivalent, că cel puțin unul dintre A și B trebuie să fie fals. Deoarece cel puțin unul dintre ele trebuie să fie fals, atunci conjuncția lor este și ea falsă. Negarea conjuncției menționate are ca rezultat o expresie adevărată, iar această expresie este identică cu prima afirmație.
Demonstrație formală
[modificare | modificare sursă]Aici, cu se notează complementul lui A. Demonstrația se realizează în 2 pași, în care se demonstrează că și .
Partea 1
[modificare | modificare sursă]Fie . Atunci .
Întrucât , atunci sau .
Dacă , atunci , și deci .
Analog, dacă , atunci , și deci .
Astfel, ;
adică .
Partea 2
[modificare | modificare sursă]Pentru a demonstra reciproca, fie , și, prin reducere la absurd, vom presupune că .
În această ipoteză, ,
de unde rezultă că și , și deci și .
Aceasta înseamnă însă că , ceea ce contrazice presupunerea că .
Din acest motiv, înseamnă că presupunerea că este falsă, și deci .
Prin urmare, ,
adică .
Concluzie
[modificare | modificare sursă]Dacă și , atunci ; astfel se demonstrează legea lui De Morgan.
Cealaltă lege a lui De Morgan, , se demonstrează similar.
Generalizarea dualității De Morgan
[modificare | modificare sursă]![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/DeMorgan_Logic_Circuit_diagram_DIN.svg/220px-DeMorgan_Logic_Circuit_diagram_DIN.svg.png)
În extensii ale logicii propoziționale clasice, dualitatea rămâne valabilă (adică oricărui operator logic i se poate găsi oricând dualul), întrucât în prezența identităților ce guvernează negarea, întotdeauna se poate introduce un care este dualul De Morgan al altuia. Aceasta conduce la o importantă proprietate a logicilor bazate pe logica clasică(d), anume existența formelor normale de negație(d): orice formulă este echivalentă cu altă formulă în care apar negații doar ca aplicate atomilor nelogici ai formulei. Existența formelor normale de negație susține multe aplicații, de exemplu în proiectarea circuitelor digitale(d), unde este folosită pentru a manipula tipurile de porți logice, și în logica formală, unde se caută forma normală conjunctivă(d) și forma normală disjunctivă(d) a unei formule. Programatorii le folosesc pe acestea pentru a simplifica sau a nega corect condiții logice(d) complicate. Adesea, ele sunt utilizate la calculele din teoria probabilității.
Dualul oricărui operator propozițional P(p, q, ...) ca funcție de propozițiile elementare p, q, ... se definește ca operatorul definit prin
Extensia la logica modală și cu predicate
[modificare | modificare sursă]Această dualitate se poate generaliza și la cuantificatori, astfel că, de exemplu, cuantificatorul universal(d) și cuantificatorul existențial(d) sunt duali:
Pentru a pune în legătură aceste dualități de cuantificatori cu relațiile De Morgan, se alcătuiește un model(d) cu un număr mic de elemente în domeniul său D, astfel încât
- D = {a, b, c}.
Atunci
și
Dar, folosind legile lui De Morgan,
și
ceea ce confirmă dualitatea cuantificatorilor în acest model.
Apoi, dualitățile cuantificatorilor pot fi extinse mai departe în logica modală(d), punând în legătură operatorii pătrat ("este necesar ca") și caro ("este posibil ca"):
În aplicarea lor asupra modalitaților aletice(d) de necesitate și posibilitate, Aristotel a observat acest caz, și în cazul logicii modale normale(d), relațiile acestor operatori modali cu cuantificarea pot fi înțelese prin alcătuirea de modele folosind semantica Kripke(d).
În logica intuiționistă
[modificare | modificare sursă]Trei din cele patru implicații ale legilor lui De Morgan sunt valabile în logica intuiționistă(d). Anume:
și
Reciproca ultimei implicații nu este valabilă în logica intuiționistă pură. Valoarea "fals" de adevăr a propoziției nu poate fi neapărat rezolvată prin găsirea acelui termen al conjuncției care este fals. De exemplu, dacă se știe că la întâlnirea dintre Alice și Bob nu au venit amândoi, nu se știe care dintre ei nu a venit. Acest din urmă principiu este echivalent cu principiul mijlocului exclus(d) slab ,
Această formă slabă poate fi folosită ca fundamnet pentru o logică intermediară(d). Pentru versiunea rafinată a legii privind afirmațiile existențiale, vezi principiul limitat mic al omniscienței(d) , care este însă diferit de principiul limitat slab al omniscienței .
Celelalte trei legi ale lui De Morgan rămân valabile dacă negația este înlocuită cu implicația pentru un predicat arbitrar constant C, ceea ce înseamnă că legile de mai sus rămân valabile și în logica minimală(d).
Analog celor mai de sus, legile cuantificatorilor:
și
sunt tautologii chiar și în logica minimală în care negația este înlocuită cu implicația unui fix, în vreme ce reciproca ultimei legi nu trebuie în general să fie adevărată.
Mai mult, avem:
dar reciproca lor implică mijlocul exclus(d), .
În ingineria calculatoarelor
[modificare | modificare sursă]Legile lui De Morgan sunt folosite pe scară largă în ingineria calculatoarelor și în logica digitală pentru simplificarea proiectării circuitelor.[13]
Note
[modificare | modificare sursă]- ^ Copi, Irving M.; Cohen, Carl; McMahon, Kenneth. Introduction to Logic. doi:10.4324/9781315510897.
- ^ Hurley, Patrick J. (), A Concise Introduction to Logic (ed. 12th), Cengage Learning, ISBN 978-1-285-19654-1
- ^ Moore, Brooke Noel (). Critical thinking. Richard Parker (ed. 10th). New York: McGraw-Hill. ISBN 978-0-07-803828-0. OCLC 689858599.
- ^ DeMorgan's [sic] Theorem
- ^ Kashef, Arman. (), In Quest of Univeral Logic: A brief overview of formal logic's evolution, doi:10.13140/RG.2.2.24043.82724/1
- ^ Boolean Algebra by R. L. Goodstein. ISBN: 0-486-45894-6
- ^ 2000 Solved Problems in Digital Electronics by S. P. Bali
- ^ DeMorgan's Theorems Arhivat în , la Wayback Machine. at mtsu.edu
- ^ Bocheński's History of Formal Logic
- ^ William of Ockham, Summa Logicae, part II, sections 32 and 33.
- ^ Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5. ISBN: 0-300-08425-0
- ^ Augustus De Morgan (1806–1871) Arhivat în , la Wayback Machine. by Robert H. Orr
- ^ „De Morgan's Theorems | GATE Notes”. BYJUS. Accesat în .