Prawa De Morgana

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

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

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

\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

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

\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

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

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

Przypisy

↑ prawa logiczne, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-06-18] .

Bibliografia

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

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

[epwn-1] prawa logiczne, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2023-06-18] .

[1]

Fahrer / Team für die Suche eingeben: