Prawa De Morgana

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

Logika

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

$\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

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

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

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

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.