Tekst źródłowy strony Prawa De Morgana

'''Prawa De Morgana''' – zestaw reguł w [[Logika matematyczna|logice matematycznej]] i [[teoria mnogości|teorii mnogości]] wiążących ze sobą pary [[Funktor zdaniotwórczy|spójników]], [[kwantyfikator]]ów lub działań na zbiorach za pomocą [[Negacja|negacji]] lub funkcji [[Dopełnienie zbioru|dopełnienia zbioru]]. Prawa te są [[Twierdzenie|twierdzeniami]] w niektórych [[Teoria (logika)|teoriach formalnych]], np. w [[Logika klasyczna|logice klasycznej]], lub [[aksjomat]]ami definiującymi niektóre struktury jak [[Algebra De Morgana|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''
: <math>\lnot (p \land q) \iff (\lnot p \lor \lnot q),</math>

gdzie <math>p</math> i <math>q</math> oznaczają zdania w sensie [[logika|logiki]].

; II prawo De Morgana: Prawo zaprzeczenia alternatywy: ''[[negacja]] [[alternatywa|alternatywy]] jest równoważna [[Koniunkcja (logika)|koniunkcji]] negacji''
: <math>\lnot (p \lor q) \iff (\lnot p \land \lnot q).</math>

Prawa umożliwiają definiowanie jednych [[Funktor zdaniotwórczy|spójników zdaniowych]] za pomocą innych. Na przykład korzystając z koniunkcji i negacji, za pomocą [[prawo podwójnej negacji|prawa podwójnej negacji]] można określić alternatywę:
: <math>p \lor q \iff \lnot (\lnot p \land\lnot q).</math>

=== Tabele wartości logicznych ===
: {| class="wikitable"
|- style="text-align:center"
!colspan="10"| <math>\lnot(p \land q) \iff (\lnot p) \lor (\lnot q)</math>
|- style="text-align:center"
!<math>p</math> !! <math>q</math> !! <math>p \land q</math> !! <math>\lnot (p \land q)</math> !! <math>\lnot p</math> !! <math>\lnot q</math> !! <math>(\lnot p) \lor (\lnot q)</math>
|- style="text-align:center"
|1 || 1 || 1 ||style="background: #FFFFF0"| 0 || 0 || 0 ||style="background: #FFFFF0"| 0
|- style="text-align:center"
|1 || 0 || 0 ||style="background: #FFFFF0"| 1 || 0 || 1 ||style="background: #FFFFF0"| 1
|- style="text-align:center"
|0 || 1 || 0 ||style="background: #FFFFF0"| 1 || 1 || 0 ||style="background: #FFFFF0"| 1
|- style="text-align:center"
|0 || 0 || 0 ||style="background: #FFFFF0"| 1 || 1 || 1 ||style="background: #FFFFF0"| 1
|}

: {| class="wikitable"
|- style="text-align:center"
!colspan="10"| <math>\lnot(p \lor q) \iff (\lnot p) \land (\lnot q)</math>
|- style="text-align:center"
!width="*"| <math>p</math> !!width="*"| <math>q</math> !!width="*"| <math>p \lor q</math> !!width="*"| <math>\lnot (p \lor q)</math> !!width="*"| <math>\lnot p</math> !!width="*"| <math>\lnot q</math> !!width="*"| <math>(\lnot p) \land (\lnot q)</math>
|- style="text-align:center"
|1 || 1 || 1 ||style="background: #FFFFF0"| 0 || 0 || 0 ||style="background: #FFFFF0"| 0
|- style="text-align:center"
|1 || 0 || 1 ||style="background: #FFFFF0"| 0 || 0 || 1 ||style="background: #FFFFF0"| 0
|- style="text-align:center"
|0 || 1 || 1 ||style="background: #FFFFF0"| 0 || 1 || 0 ||style="background: #FFFFF0"| 0
|- style="text-align:center"
|0 || 0 || 0 ||style="background: #FFFFF0"| 1 || 1 || 1 ||style="background: #FFFFF0"| 1
|}

Porównanie wartości w czwartej i siódmej kolumnie ostatniego wiersza obu tabel (oznaczonych kolorem <span style="background: #FFFFF0">żółtym</span>) daje przekonanie o prawdziwości wyrażeń
: <math>\lnot (p \land q) \iff (\lnot p) \lor (\lnot q)</math> oraz
: <math>\lnot (p \lor q) \iff (\lnot p) \land (\lnot q)</math>

bez względu na wartościowanie zmiennych <math>p</math> i <math>q</math> (ma ono zawsze [[Wartość logiczna|wartość logiczną]] równą 1). Zdania takie jak nazywa się [[Tautologia (logika)|tautologiami]].

== Rachunek kwantyfikatorów ==
Do praw De Morgana należą też reguły zaprzeczania [[kwantyfikator]]om<ref name="epwn">{{Encyklopedia PWN | id = 3961798 | tytuł = prawa logiczne | data dostępu = 2023-06-18}}</ref>:
: <math>\lnot\bigg(\forall_x\ p(x)\bigg) \iff \bigg(\exists_x\ \lnot p(x)\bigg),</math>
: <math>\lnot\bigg(\exists_x\ p(x)\bigg) \iff \bigg(\forall_x\ \lnot p(x)\bigg),</math>

gdzie <math>p(x)</math> jest dowolnym zdaniem zależnym od zmiennej <math>x.</math>

== Teoria mnogości ==
[[Plik:Demorganlaws.svg|mały|Ilustracja mnogościowych praw De Morgana – obie strony równości zaznaczono na niebiesko.]]

W [[teoria mnogości|teorii mnogości]] prawa De Morgana służą opisowi działania [[dopełnienie zbioru|dopełnienia]] (lub dokładniej: [[różnica zbiorów|różnicy zbiorów]]):
# dopełnienie [[suma zbiorów|sumy zbiorów]] jest równe [[Część wspólna|części wspólnej]] ich dopełnień
#: <math>(A \cup B)^c = A^c \cap B^c,</math>
# dopełnienie części wspólnej zbiorów jest równe sumie ich dopełnień
#: <math>(A \cap B)^c = A^c \cup B^c.</math>

Z zasady [[indukcja matematyczna|indukcji matematycznej]] to samo prawo zachowane jest dla skończenie wielu zdarzeń:
: <math>\left(\bigcup_{i\in I}~A_i\right)^c = \bigcap_{i\in I}~A_i^c,</math>
: <math>\left(\bigcap_{i\in I}~A_i\right)^c = \bigcup_{i\in I}~A_i^c,</math>

gdzie <math>I \subset \mathbb N.</math>

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

== Algebry Boole’a ==
Jeżeli <math>(B, \cup, \cap, -, 0, 1)</math> jest zupełną [[algebra Boole’a|algebrą Boole’a]], to dla <math>a_i\in B,\, i\in I{:}</math>
: <math>-\left(\bigcup_{i\in I}~a_i\right) = \bigcap_{i\in I}~-a_i,</math>
: <math>-\left(\bigcap_{i\in I}~a_i\right) = \bigcup_{i\in I}~-a_i.</math>

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{cytuj książkę |autor = K. Kuratowski |autor2 = A. Mostowski |autor link = Kazimierz Kuratowski |autor link2 = Andrzej Mostowski |tytuł = Teoria mnogości |url = |wydawca = [[Wydawnictwo Naukowe PWN|PWN]] |strony = |wydanie = 2 |rok = 1966 |isbn = |data dostępu =}}
* {{cytuj książkę |autor = K. Kuratowski |tytuł = Wstęp do teorii mnogości i topologii |url = |wydawca = PWN |strony = |wydanie = 7 |rok = 1977 |isbn = |data dostępu =}}
* {{cytuj książkę |autor = H. Rasiowa |autor link = Helena Rasiowa |tytuł = Wstęp do matematyki współczesnej |url = |wydawca = PWN |strony = |wydanie = 3 |rok = 1971 |isbn = |data dostępu =}}

== Linki zewnętrzne ==
* {{MathWorld | adres = deMorgansLaws | tytuł = de Morgan’s Laws}} [dostęp 2023-06-18].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/De_Morgan_laws De Morgan laws]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].

{{Klasyczny rachunek zdań}}
{{Algebra zbiorów}}

{{Kontrola autorytatywna}}

[[Kategoria:Prawa rachunku zdań|De Morgana]]
[[Kategoria:Algebra zbiorów]]