Formulele lui De Morgan
identități în logica matematică / From Wikipedia, the free encyclopedia
Î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 .
Î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.
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.