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

$\mathrm{\neg }(p\wedge q)⟺(\mathrm{\neg }p\vee \mathrm{\neg }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

$\mathrm{\neg }(p\vee q)⟺(\mathrm{\neg }p\wedge \mathrm{\neg }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\vee q⟺\mathrm{\neg }(\mathrm{\neg }p\wedge \mathrm{\neg }q).$

Tabele wartości logicznych

$\mathrm{\neg }(p\wedge q)⟺(\mathrm{\neg }p)\vee (\mathrm{\neg }q)$
$p$	$q$	$p\wedge q$	$\mathrm{\neg }(p\wedge q)$	$\mathrm{\neg }p$	$\mathrm{\neg }q$	$(\mathrm{\neg }p)\vee (\mathrm{\neg }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

$\mathrm{\neg }(p\vee q)⟺(\mathrm{\neg }p)\wedge (\mathrm{\neg }q)$
$p$	$q$	$p\vee q$	$\mathrm{\neg }(p\vee q)$	$\mathrm{\neg }p$	$\mathrm{\neg }q$	$(\mathrm{\neg }p)\wedge (\mathrm{\neg }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ń

$\mathrm{\neg }(p\wedge q)⟺(\mathrm{\neg }p)\vee (\mathrm{\neg }q)$ oraz

$\mathrm{\neg }(p\vee q)⟺(\mathrm{\neg }p)\wedge (\mathrm{\neg }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:

$\mathrm{\neg }({\mathrm{\forall }}_{x}p(x))⟺({\mathrm{\exists }}_x\mathrm{\neg }p(x)),$

$\mathrm{\neg }({\mathrm{\exists }}_{x}p(x))⟺({\mathrm{\forall }}_x\mathrm{\neg }p(x)),$

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

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

• Szablon:Cytuj książkę
• Szablon:Cytuj książkę
• Szablon:Cytuj książkę

Linki zewnętrzne

• Szablon:MathWorld [dostęp 2023-06-18].
• Szablon:Otwarty dostęp De Morgan laws Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].