Prawa de Morgana

Spis treści

Rachunek zdań

Prawa de Morgana dla rachunku zbiorów

Prawa de Morgana rachunku kwantyfikatorów

Dowód I prawa de Morgana

Dowód II prawa de Morgana

I prawo de Morgana

II prawo de Morgana

Przykłady

Przykład

Prawa de Morgana dotyczą rachunku zdań, a także rachunku zbiorów oraz kwantyfikatorów.

Rachunek zdań.
Prawa de Morgana rachunku zbiorów.
Prawa de Morgana rachunku kwantyfikatorów.

Dla rachunku zdań logicznych mamy określone następujące prawa:

\(\sim (p\land q)\Leftrightarrow (\sim p)\lor (\sim q)\)

Powyższe prawo można słownie wyrazić poprzez zdanie:

Zaprzeczenie koniunkcji dwóch zdań logicznych jest równoważne alternatywie zaprzeczeń tych zdań.

Innymi słowy, zdanie: „nieprawda, że p i q” ma taką samą wartość logiczną co: „nieprawda, że p lub nieprawda, że q”.

\(\sim (p\lor q)\Leftrightarrow (\sim p)\land (\sim q)\)

Prawo to można słownie wyrazić poprzez zdanie:

Zaprzeczenie alternatywy dwóch zdań logicznych jest równoważne koniunkcji zaprzeczeń tych zdań.

Innymi słowy, zdanie: „nieprawda, że p lub q” ma taką samą wartość logiczną co: „nieprawda, że p i nieprawda, że q”.

Oto przykład zastosowania pierwszego prawa de Morgana.

Zamiast zdania: „nieprawda, że Słońce jest planetą i jest osiem razy większe od Jowisza” możemy powiedzieć: „nieprawda, że Słońce jest planetą lub nieprawda, że Słońce jest osiem razy większe od Jowisza”.

Oto przykład zastosowania drugiego prawa de Morgana.

Zamiast zdania: „nieprawda, że Słońce jest planetą lub jest osiem razy większe od Jowisza” możemy powiedzieć: „nieprawda, że Słońce jest planetą i nieprawda, że Słońce jest osiem razy większe od Jowisza”.

Prawa de Morgana dla zbiorów są następujące.

Zakładamy, że zbiory A i B są podzbiorami pewnego zbioru Y, A', B' są dopełnieniami odpowiednio zbiorów A i B względem Y. Wówczas:

\( (A\cup B)'=A'\cap B'\)

Powyższe prawo można przeczytać w następujący sposób: dopełnienie sumy zbiorów jest równe części wspólnej ich dopełnień.

\((A\cap B)'=A'\cup B'\)

Powyższe prawo można przeczytać w następujący sposób: dopełnienie części wspólnej zbiorów jest równe sumie ich dopełnień.

\(\sim \underset{x}{\exists}\ {p(x)}\Leftrightarrow \underset{x}{\forall} \sim p(x) \)

\(\sim \underset{x}{\forall}\ {p(x)}\Leftrightarrow \underset{x}{\exists} \sim p(x) \)

Prawa te kolejno możemy przeczytać w następujący sposób:

Nieprawda, że istnieje x, który spełnia warunek p(x), jest równoważne z tym, że dla każdego x warunek p(x) nie jest spełniony.
Nieprawda, że dla każdego x spełniony jest warunek p(x), jest równoważne z tym, że istnieje takie x, dla którego warunek p(x) nie jest spełniony.

Wykorzystamy powyższe przy udowodnieniu, że zdanie \(\underset{x}{\forall}\ {(x-1=0)}\) jest fałszywe. Wystarczy udowodnić, że zaprzeczenie tego zdania, czyli \(\sim \underset{x}{\forall}\ {(x-1=0)}\), jest prawdziwe. Skorzystamy z prawa de Morgana, na podstawie którego wystarczy udowodnić prawdziwość zdania \(\underset{x}{\exists}\ \sim {(x-1=0)}\), czyli \(\underset{x}{\exists}\ {(x-1\neq 0)}\). Wystarczy teraz wskazać, że istnieje takie x (np. x = 0), że (x-1 ≠ 0), na czym kończymy dowód.

Kwantyfikatory są bardzo często stosowane w matematyce, ale równie często pomija się je w notacji dla uproszczenia sformułowań.

Aby udowodnić pierwsze prawo de Morgana, należy wykazać, że zdania \(\sim (p\land q)\) oraz \((\sim p)\lor (\sim q)\) są równoważne (mają takie same wartości logiczne). Przeprowadzimy dowód dla wszystkich możliwych wartości logicznych.

Obliczymy najpierw wartości logiczne zdania \(\sim (p\land q)\):

\(p\)	\(q\)	Wyznaczamy wartości iloczynu logicznego zdań p i q.	\(p\land q\)	Negujemy wyniki z poprzedniej kolumny i otrzymujemy wynik.	\(\sim (p\land q)\)
0	0		0		1
0	1		0		1
1	0		0		1
1	1		1		0

Obliczymy teraz wartości logiczne zdania \((\sim p)\lor (\sim p)\):

Widać, że wartości logiczne w ostatnich kolumnach obu tabel są takie same, a zatem wykazaliśmy równoważność zdań \(\sim (p\land q)\) oraz \((\sim p)\lor (\sim q)\).

Negujemy zdania p i q.

\(\sim p\)

\(\sim q\)

Sumujemy logicznie zaprzeczenia zdań p i q i otrzymujemy wynik.

\((\sim p)\lor (\sim q)\)

Aby udowodnić drugie prawo de Morgana, należy wykazać, że zdania \(\sim (p\lor q)\), \((\sim p)\land (\sim q)\) są równoważne (mają takie same wartości logiczne). Przeprowadzimy dowód dla wszystkich możliwych wartości logicznych.

Obliczymy najpierw wartości logiczne zdania \(\sim (p\lor q)\):

\(p\)	\(q\)	Wyznaczamy wartości sumy logicznej zdań p i q.	\(p \lor q\)	Negujemy wyniki z poprzedniej kolumny i otrzymujemy wynik.	\(\sim (p\lor q)\)
0	0		0		1
0	1		1		0
1	0		1		0
1	1		1		0

Obliczymy teraz wartości logiczne zdania \((\sim p)\land (\sim q)\):

Widać, że wartości logiczne w ostatnich kolumnach obu tabel są takie same, a zatem wykazaliśmy równoważność zdań: \(\sim (p\lor q)\), \((\sim p)\land (\sim q)\).