Prawa de Morgana

Pierwsze prawo de Morgana

Inne zagadnienia z tej lekcji

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

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

I prawo de Morgana:

~(p∧q)⇔(~p)∨(~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

Przykład

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

Dowód

Aby udowodnić pierwsze prawo de Morgana należy wykazać, że zdania ~(p∧q) oraz (~p)∨(~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\wedge q)$

p	q	Wyznaczamy wartości iloczynu logicznego zdań p i q	p∧q	Negujemy wyniki z poprzedniej kolumny i otrzymujemy wynik	~(p∧q)
0	0		0		1
0	1		0		1
1	0		0		1
1	1		1		0

Obliczymy teraz wartości logiczne zdania (~p)∨(~p):

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

Negujemy zdania p i q

Sumujemy logicznie zaprzeczenia zdań p i q i otrzymujemy wynik

(~p)∨(~p)

Alternatywa

Zdanie p lub q to alternatywa lub suma logiczna.

Równoważność zdań

Równoważność zdań p i q jest to zdanie orzekające, że zdania p i q mają tę samą wartość logiczną.

II prawo de Morgana

II prawo de Morgana - zaprzeczenie alternatywy dwóch zdań logicznych jest równoważne koniunkcji zaprzeczeń tych zdań.

Test wiedzy

Sprawdź swoje umiejętności z materiału zawartego w tej lekcji.