Przejdź do zawartości

Prawa De Morgana

Z Wikipedii, wolnej encyklopedii

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[1]. 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ń

[edytuj | edytuj kod]
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

[edytuj | edytuj kod]
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

[edytuj | edytuj kod]

Do praw De Morgana należą też reguły zaprzeczania kwantyfikatorom[2][1]:

gdzie jest dowolnym zdaniem zależnym od zmiennej

Teoria mnogości

[edytuj | edytuj kod]
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[1] lub szerzej różnicy zbiorów:

  1. dopełnienie sumy zbiorów jest równe części wspólnej ich dopełnień
  2. 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

[edytuj | edytuj kod]

Jeżeli jest zupełną algebrą Boole’a, to dla

Przypisy

[edytuj | edytuj kod]
  1. a b c publikacja w otwartym dostępie – możesz ją przeczytać 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].
  2. prawa logiczne, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-06-18].

Bibliografia

[edytuj | edytuj kod]
  • 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

[edytuj | edytuj kod]