miniatura| Formulele lui De Morgan reprezentate cu diagrame Venn. În fiecare caz, mulțimea rezultată este mulțimea tuturor punctelor în orice nuanță de albastru. În și algebra booleană, formulele lui De Morgan, cunoscute și ca legile sau teoremele lui De Morgan,DeMorgan's [sic] Theorem sunt o pereche de reguli de transformare care sunt reguli valide de inferență. Ele sunt numite după Augustus De Morgan, un matematician britanic din secolul al XIX-lea. Regulile permit exprimarea și disjuncțiilor între ele prin aplicarea .
Regulile pot fi exprimate în limbaj natural sub forma:
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 .
dreapta|miniatura|400x400px| Echivalența lui ¬φ ∨ ¬ψ și ¬(φ ∧ ψ) este afișată în această tabelă de adevăr. În limbajul formal, regulile se scriu ca
și
Unde
P și Q sunt propoziții, este operatorul logic negație (NON), este operatorul logic conjuncție (ȘI), este operatorul logic disjuncție (SAU), este un simbol metalogic care înseamnă „poate fi înlocuit într-o 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.
miniatura| Formulele lui De Morgan cu operația de scădere între mulțimi. 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 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ă Regula de negație a conjuncției poate fi scrisă în notație :
,
și
.
Regula de negație a disjuncției poate fi scrisă astfel:
,
și
.
Sub formă de regulă de inferență: negarea conjuncției
și negarea disjuncției
și exprimată ca (pe baza funcționalelor de adevăr) sau teoremă a logicii propoziționale:
Unde și sunt propoziții exprimate într-un sistem formal.
Forma de substituție 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ă În teoria mulțimilor și algebra booleană, este adesea menționat ca „interschimbarea de reuniunii și intersecției în raport cu complementarea”,Boolean Algebra by R. L. Goodstein. care poate fi exprimată formal ca:
Unde:
este negația lui , fiind scrisă deasupra termenilor de negat, este operatorul intersecție (ȘI), este operatorul reuniune (SAU).
Reuniuni și intersecții de orice număr de mulțimi Forma generalizată este
unde este o mulțime de indexare, care poate fi infinită numărabilă sau nenumărabilă.
În notația mulțimilor, legile lui De Morgan pot fi amintite folosind „elimin bara, schimb semnul”.2000 Solved Problems in Digital Electronics by S. P. Bali
Inginerie În ingineria electrică și a calculatoarelor, legile lui De Morgan se notează de regulă ca:
și
Unde:
este ȘI logic, este SAU logic, înseamnă negația logică a ceea ce este sub bară.
Căutarea în texte 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 Formulele sunt denumite după Augustus De Morgan (1806–1871),DeMorgan's Theorems at mtsu.edu care a introdus o versiune formală a lor în 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. O observație similară se întâlnește totuși și la Aristotel și era cunoscută de logicienii greci și medievali.Bocheński's History of Formal Logic De exemplu, în secolul al XIV-lea, William de Ockham dădea o expresie în cuvinte citirii legilor.William of Ockham, Summa Logicae, part II, sections 32 and 33. Jean Buridan, în , descrie și regulile de conversie care urmează liniile formulelor lui De Morgan.Jean Buridan, Summula de Dialectica. Trans. Gyula Klima. New Haven: Yale University Press, 2001. See especially Treatise 1, Chapter 7, Section 5. Lui De Morgan i se acordă însă credit pentru enunțarea lor în termenii logicii formale moderne și încorporarea lor în limbajul logicii. Formulele lui De Morgan pot fi demonstrate cu ușurință și pot părea chiar banale.Augustus De Morgan (1806–1871) by Robert H. Orr Cu toate acestea, aceste formule sunt utile pentru a face inferențe valide în demonstrații și argumente deductive.
Demonstrație pentru algebra booleană Teorema lui De Morgan se poate aplica negației unei disjuncții sau negației unei într-o formulă sau într-o parte a unei formule.
Negarea unei disjuncții Î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:
Stabilindu-se că niciuna dintre A și B nu sunt adevărate este echivalent cu A nu este adevărat, 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ă „dacă două enunțuri sunt ambele false, este fals și că cel puțin unul 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 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 este exprimată ca „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 pentru algebra mulțimilor Aici, cu se notează complementul lui A. Demonstrația se realizează în 2 pași, în care se demonstrează că și .
Partea 1 Fie . Atunci .
Întrucât , atunci sau .
Dacă , atunci , și deci .
Analog, dacă , atunci , și deci .
Astfel, ;
adică .
Partea 2 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 Dacă și , atunci ; astfel se demonstrează legea lui De Morgan.
Cealaltă lege a lui De Morgan, , se demonstrează similar.
Generalizarea dualității De Morgan miniatura|Formulele lui De Morgan reprezentate ca circuite cu porți logice (diagrame International Electrotechnical Commission). Î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 , anume existența : 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 , unde este folosită pentru a manipula tipurile de porți logice, și în logica formală, unde se caută și a unei formule. Programatorii le folosesc pe acestea pentru a simplifica sau a nega corect 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
Extindere la logica predicatelor și modală Această dualitate se poate generaliza și la cuantificatori, astfel că, de exemplu, cuantificatorul universal și sunt duali:
Pentru a pune în legătură aceste dualități de cuantificatori cu relațiile De Morgan, se alcătuiește un 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
se ajunge la dualitatea cuantificatorilor în acest model.
Apoi, dualitățile cuantificatorilor pot fi extinse mai departe în , punând în legătură operatorii pătrat ("este necesar ca") și caro ("este posibil ca"):
În aplicarea lor asupra de necesitate și posibilitate, Aristotel a observat acest caz, și în cazul , relațiile acestor operatori modali cu cuantificarea pot fi înțelese prin alcătuirea de modele folosind .
În logica intuiționistă Trei din cele patru implicații ale legilor lui De Morgan sunt valabile în . Anume:
și