Prawa De Morgana

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Prawa De Morganatwierdzenia w logice matematycznej i teorii mnogości. Od nazwiska Augustusa De Morgana, angielskiego matematyka.

Logika[edytuj]

I prawo De Morgana 
Prawo zaprzeczania koniunkcji: negacja koniunkcji jest równoważna alternatywie negacji
,

gdzie p i q 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]

0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Porównanie wartości w czwartej i siódmej kolumny ostatniego wiersza obu tabel (oznaczonych kolorem żółtym) daje przekonanie o prawdziwości wyrażeń

oraz

bez względu na wartościowanie zmiennych p i q (ma ono zawsze wartość logiczną równą 1). Zdania takie jak nazywa się tautologiami.

Rachunek kwantyfikatorów[edytuj]

W rachunku kwantyfikatorów prawa De Morgana opisują reguły zaprzeczania kwantyfikatorom:

,
,

gdzie jest dowolnym zdaniem zależnym od zmiennej .

Teoria mnogości[edytuj]

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 :

,
.

Bibliografia[edytuj]

  1. K. Kuratowski, A. Mostowski: Teoria mnogości. Wyd. 2. PWN, 1966.
  2. K. Kuratowski: Wstęp do teorii mnogości i topologii. Wyd. 7. PWN, 1977.
  3. H. Rasiowa: Wstęp do matematyki współczesnej. Wyd. 3. PWN, 1971.