Prawa De Morgana
Prawa De Morgana – zestaw reguł w logice matematycznej i teorii mnogości wiążących ze sobą pary spójników, kwantyfikatorów lub działań na zbiorach za pomocą negacji lub funkcji dopełnienia zbioru. 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ł angielski matematyk Augustus De Morgan w XIX wieku.
Logika
- I prawo De Morgana
- Prawo zaprzeczania koniunkcji: negacja koniunkcji jest równoważna alternatywie negacji
gdzie i oznaczają zdania w sensie logiki.
- II prawo De Morgana
- Prawo 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
1 1 1 0 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 1 1 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[1]:
gdzie jest dowolnym zdaniem zależnym od zmiennej
Teoria mnogości
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/06/Demorganlaws.svg/220px-Demorganlaws.svg.png)
W teorii mnogości prawa De Morgana służą opisowi działania dopełnienia (lub dokładniej: 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 (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
- ↑ prawa logiczne, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-06-18] .
Bibliografia
- K. Kuratowski, A. Mostowski: Teoria mnogości. Wyd. 2. PWN, 1966.
- K. Kuratowski: Wstęp do teorii mnogości i topologii. Wyd. 7. PWN, 1977.
- H. Rasiowa: Wstęp do matematyki współczesnej. Wyd. 3. PWN, 1971.
Linki zewnętrzne
- Eric W.E.W. Weisstein Eric W.E.W., de Morgan’s Laws, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2023-06-18].
De Morgan laws (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
- p
- d
- e
działania |
| ||||||||
---|---|---|---|---|---|---|---|---|---|
własności działań |
| ||||||||
powiązane relacje |
| ||||||||
tworzone struktury algebraiczne |
| ||||||||
inne rodziny zdefiniowane działaniami |
| ||||||||
twierdzenia | |||||||||
powiązane nauki |
| ||||||||
badacze |
|
- Britannica: topic/De-Morgan-laws
- Catalana: 0021979
- DSDE: De_Morgans_love