Prawa De Morgana – zestaw reguł w logice matematycznej i teorii mnogości, konkretniej w klasycznym rachunku zdań, rachunku kwantyfikatorów i algebry zbiorów. Prawa De Morgana wiążą ze sobą pary spójników, kwantyfikatorów lub działań na zbiorach za pomocą negacji lub funkcji dopełnienia zbioru Słownik teorio-mnogościowy, Katedra Podstaw Informatyki – Wydział Informatyki i Telekomunikacji Politechniki Wrocławskiej (WIT PWr), cs.pwr.edu.pl [dostęp 2025-05-13].. Prawa te są twierdzeniami w niektórych teoriach formalnych, np. w logice klasycznej, lub aksjomatami definiującymi niektóre struktury jak algebry De Morgana.
Prawa te sformułował Augustus De Morgan – angielski matematyk z XIX wieku.
Rachunek zdań I prawo De Morgana – zaprzeczania koniunkcji negacja koniunkcji jest równoważna alternatywie negacji
gdzie i oznaczają zdania w sensie logiki.
II prawo De Morgana – zaprzeczenia alternatywy negacja alternatywy jest równoważna koniunkcji negacji
Prawa umożliwiają definiowanie jednych spójników zdaniowych za pomocą innych. Na przykład korzystając z koniunkcji i negacji, za pomocą prawa podwójnej negacji można określić alternatywę:
Tabele wartości logicznych {| class="wikitable" |- style="text-align:center" !colspan="10"| |- style="text-align:center" ! !! !! !! !! !! !! |- style="text-align:center" |1 || 1 || 1 ||style="background: #FFFFF0"| 0 || 0 || 0 ||style="background: #FFFFF0"| 0 |- style="text-align:center" |1 || 0 || 0 ||style="background: #FFFFF0"| 1 || 0 || 1 ||style="background: #FFFFF0"| 1 |- style="text-align:center" |0 || 1 || 0 ||style="background: #FFFFF0"| 1 || 1 || 0 ||style="background: #FFFFF0"| 1 |- style="text-align:center" |0 || 0 || 0 ||style="background: #FFFFF0"| 1 || 1 || 1 ||style="background: #FFFFF0"| 1
{| class="wikitable" |- style="text-align:center" !colspan="10"| |- style="text-align:center" !width="*"| !!width="*"| !!width="*"| !!width="*"| !!width="*"| !!width="*"| !!width="*"| |- style="text-align:center" |1 || 1 || 1 ||style="background: #FFFFF0"| 0 || 0 || 0 ||style="background: #FFFFF0"| 0 |- style="text-align:center" |1 || 0 || 1 ||style="background: #FFFFF0"| 0 || 0 || 1 ||style="background: #FFFFF0"| 0 |- style="text-align:center" |0 || 1 || 1 ||style="background: #FFFFF0"| 0 || 1 || 0 ||style="background: #FFFFF0"| 0 |- style="text-align:center" |0 || 0 || 0 ||style="background: #FFFFF0"| 1 || 1 || 1 ||style="background: #FFFFF0"| 1
Porównanie wartości w czwartej i siódmej kolumnie ostatniego wiersza obu tabel (oznaczonych kolorem żółtym) daje przekonanie o prawdziwości wyrażeń oraz
bez względu na wartościowanie zmiennych i (ma ono zawsze wartość logiczną równą 1). Zdania takie jak nazywa się tautologiami.
Rachunek kwantyfikatorów Do praw De Morgana należą też reguły zaprzeczania kwantyfikatorom:
gdzie jest dowolnym zdaniem zależnym od zmiennej
Teoria mnogości mały|Ilustracja mnogościowych praw De Morgana – obie strony równości zaznaczono na niebiesko
W teorii mnogości prawa De Morgana służą opisowi działania dopełnienia lub szerzej różnicy zbiorów: dopełnienie sumy zbiorów jest równe części wspólnej ich dopełnień
dopełnienie części wspólnej zbiorów jest równe sumie ich dopełnień
Z zasady indukcji matematycznej to samo prawo zachowane jest dla skończenie wielu zdarzeń:
gdzie
Analogicznie wysławia się i zapisuje prawa De Morgana dla nieskończonych rodzin zbiorów. Wtedy w powyższych wzorach należy przyjąć, że jest taką rodziną.
Algebry Boole’a Jeżeli jest zupełną algebrą Boole’a, to dla
Przypisy
Bibliografia
Linki zewnętrzne [dostęp 2023-06-18]. De Morgan laws , Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
De Morgana Kategoria:Algebra zbiorów