Prawa De Morgana

 

Augustus De Morgan (ur. 27 czerwca 1806r. w Maduraju, zm. 18 marca 1871r. w Londynie) – angielski matematyk i logik. Zajmował sę głównie logiką formalną i teorią szeregów. Badał podstawową problematykę algebry logiki i teorii relacji.

Zwrócił uwagę na nazwane od Jego nazwiska Prawa De Morgana.

 

I prawo De Morgana
(Prawo zaprzeczania koniunkcji)

[latex] \neg ( p \wedge q) \Leftrightarrow ( \neg p \vee \neg q) [/latex]

negacja koniunkcji jest równoważna alternatywie negacji

 

II prawo De Morgana
(Prawo zaprzeczania alternatywy)

[latex] \neg( p \vee q) \Leftrightarrow ( \neg p \wedge \neg q) [/latex]

negacja alternatywy jest równoważna koniunkcji negacji

 

Dowód Igo prawa De Morgana:

Udowodnimy za pomocą tabeli wartości logicznych. Wystarczy doprowadzenie do takich samych wartości logicznych, dla obu stron równania.

I-prawo-de-morgana

Widzimy zatem, że lewa strona równoważności (czwarta kolumna w tabeli), zawiera takie same wartości logiczne, jak jej prawa strona (ostatnia kolumna w tabeli).
To dowodzi prawdziwości Igo Prawa De Morgana.

 

Dowód IIgo prawa De Morgana:

Stosując tą samą zasadę, dowodzimy prawdziwości IIgo Prawa De Morgana.
II-prawo-de-morgana

 

A teraz Prawa De Morgana w sposób bardziej zrozumiały, czyli z życia wzięte :)

Niech zdanie p i q oznaczają:

p = „pójdę do sklepu”, q = „odwiedzę sąsiadkę”

 

Stosując I prawo De Morgana:

Koniunkcja p [latex] \wedge [/latex] q oznacza: „pójdę do sklepu i odwiedzę sąsiadkę”

Aby została ona spełniona, obie czynności muszą zostać wykonane.

Zaprzeczając całej koniunkcji, otrzymuję

[latex] \neg ( [/latex] p [latex] \wedge [/latex] q ) ,

a zatem nieprawdą jest, że „pójdę do sklepu i odwiedzę sąsiadkę”.

Z tego wynika, że nieprawdą jest, że „pójdę do sklepu i odwiedzę sąsiadkę”, wtedy i tylko wtedy, gdy „nie pójdę do sklepu” lub „nie odwiedzę sąsiadki” (wystarczy, że jedno ze zdań koniunkcji nie zostanie spełnione).

Zapisując za pomocą symboli, otrzymujemy:

[latex] \neg ( p \wedge q) \Leftrightarrow ( \neg p \vee \neg q) [/latex]

 

Stosując II prawo De Morgana:

Alternatywa p [latex] \vee [/latex] q oznacza: „pójdę do sklepu lub odwiedzę sąsiadkę”, czyli jedna z czynności musi zostać wykonana.

Zaprzeczając całej alternatywie, otrzymuję

[latex] \neg ( [/latex] p [latex] \vee [/latex] q ) ,

a zatem nieprawdą jest, że „pójdę do sklepu lub odwiedzę sąsiadkę”.

Z tego wynika, że nieprawdą jest, że „pójdę do sklepu lub odwiedzę sąsiadkę”, wtedy i tylko wtedy, gdy „nie pójdę do sklepu” i również „nie odwiedzę sąsiadki” (musi nastąpić jednoczesne zaprzeczenie obu zdań występujących w alternatywie).

Zapisując za pomocą symboli, otrzymujemy:

[latex] \neg( p \vee q) \Leftrightarrow ( \neg p \wedge \neg q) [/latex]