Prawa De Morgana

reguły w logice i teorii mnogości

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

edytuj
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

edytuj
 
             
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

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

 
 

gdzie   jest dowolnym zdaniem zależnym od zmiennej  

Teoria mnogości

edytuj
 
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 dokładniej: 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 (w powyższych wzorach należy przyjąć, że   jest taką rodziną).

Algebry Boole’a

edytuj

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

 
 

Przypisy

edytuj
  1. prawa logiczne, [w:] Encyklopedia PWN [dostęp 2023-06-18].

Bibliografia

edytuj
  • 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
  • Eric W. Weisstein, 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].