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

I prawo De Morgana 
Prawo zaprzeczania koniunkcji: negacja koniunkcji jest równoważna alternatywie negacji
\lnot (p \land q) \iff (\lnot p \lor \lnot q),

gdzie p i q oznaczają zdania w sensie logiki.

II prawo De Morgana 
Prawo zaprzeczenia alternatywy: negacja alternatywy jest równoważna koniunkcji negacji
\lnot (p \lor q) \iff (\lnot p \land \lnot q);

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ę:

p \lor q \iff \lnot (\lnot p \land\lnot q)

Tabele wartości logicznych[edytuj | edytuj kod]

\lnot(p \land q) \iff (\lnot p) \lor (\lnot q)
p q p \land q \lnot (p \land q) \lnot p \lnot q (\lnot p) \lor (\lnot q)
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
\lnot(p \lor q) \iff (\lnot p) \land (\lnot q)
p q p \lor q \lnot (p \lor q) \lnot p \lnot q (\lnot p) \land (\lnot q)
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ń

\lnot (p \land q) \iff (\lnot p) \lor (\lnot q) oraz
\lnot (p \lor q) \iff (\lnot p) \land (\lnot q)

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

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

\lnot\bigg(\forall_x\ p(x)\bigg) \iff \bigg(\exists_x\ \lnot p(x)\bigg),
\lnot\bigg(\exists_x\ p(x)\bigg) \iff \bigg(\forall_x\ \lnot p(x)\bigg),

gdzie p(x) jest dowolnym zdaniem zależnym od zmiennej x.

Teoria mnogości[edytuj | edytuj kod]

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ń,
    (A \cup B)^c = A^c \cap B^c,
  2. dopełnienie części wspólnej zbiorów jest równe sumie ich dopełnień,
    (A \cap B)^c = A^c \cup B^c

Z zasady indukcji matematycznej to samo prawo zachowane jest dla skończenie wielu zdarzeń:

\left(\bigcup_{i\in I}~A_i\right)^c = \bigcap_{i\in I}~A_i^c.,
\left(\bigcap_{i\in I}~A_i\right)^c = \bigcup_{i\in I}~A_i^c.,

gdzie I \subset \mathbb N

Analogicznie wysławia się i zapisuje prawa De Morgana dla nieskończonych rodzin zbiorów (w powyższych wzorach należy przyjąć, że I jest taką rodziną).

Algebry Boole'a[edytuj | edytuj kod]

Jeżeli (B, \cup, \cap, -, 0, 1) jest zupełną algebrą Boole'a, to dla a_i\in B,\, i\in I:

-\left(\bigcup_{i\in I}~a_i\right) = \bigcap_{i\in I}~-a_i,
-\left(\bigcap_{i\in I}~a_i\right) = \bigcup_{i\in I}~-a_i.

Bibliografia[edytuj | edytuj kod]

  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.