Prawa de Morgana

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

Spis treści

Rachunek zdań

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

I prawo de Morgana

\(\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”.

II prawo de Morgana

\(\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”.

Przykłady

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 rachunku zbiorów

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ń.

Prawa de Morgana rachunku kwantyfikatorów

\(\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:

  1. 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.
  2. 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.

Przykład

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ń.

Dowód I prawa de Morgana

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)\)
0001
0101
1001
1110

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

\(p\)\(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)\)
00111
01101
10011
11000

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)\).

Dowód II prawa de Morgana

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)\)
0001
0110
1010
1110

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

\(p\)\(q\) Negujemy zdania p i q. \( \sim p\) \( \sim q\) Wyznaczamy iloczyn logiczny negacji zdań p i q i otrzymujemy wynik.\((\sim p)\land (\sim q)\)
00111
01100
10010
11000

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)\).





Inne zagadnienia z tej lekcji


© medianauka.pl, 2023-02-09, A-4693



©® Media Nauka 2008-2023 r.