Prawa de morgana

PRAWA DE MORGANA

Prawa De Morgana to dwa twierdzenia (tautologie) w logice matematycznej stworzone przez Augustusa De Morgana.

Tautologia to zdanie, które zawsze jest prawdziwe; przyjmuje wartość logiczną 1.

Wyróżniamy dwa prawa:
I Prawo De Morgana
II Prawo De Morgana

I Prawo De Morgana
Negacja koniunkcji dwóch zdań jest równoważna alternatywie negacji zdania pierwszego i negacji zdania drugiego :

Do dowodu, że to twierdzenie jest prawdziwe, wykorzystujemy metodę zero-jedynkową:

W ostatniej kolumnie wpisujemy same 1, co oznacza, że dla wszystkich wartości logicznych zdań p i q, 1 Prawo De Morgana ma wartość logiczną 1; jest prawdziwe; jest tautologią.

II Prawo De Morgana

Negacja alternatywy dwóch zdań jest równoważna koniunkcji negacji pierwszego zdania i negacji drugiego zdania :

Do dowodu, że to twierdzenie jest prawdziwe, wykorzystujemy metodę zero-jedynkową:

W ostatniej kolumnie wpisujemy same 1, co oznacza, że dla wszystkich wartości logicznych zdań p i q, 2 Prawo De Morgana ma wartość logiczną 1; jest prawdziwe; jest tautologią.

Zastosowania Praw De Morgana

Prawa De Morgana wykorzystywane są w teorii mnogości i w rachunku kwantyfikatorów.

Prawo rachunku kwantyfikatorów – mówi o zdaniach z kwantyfikatorami i jest prawdziwe zawsze, bez uwagi na formę.

Kwantyfikatory to zwroty „dla każdego” oraz „istnieje taki”.

Prawa De Morgana opisują zasady zaprzeczania kwantyfikatorom.

Negacja „dla każdego „x” zdanie p zależne od x” jest równoważna „istnieje taki „x”, dla którego negacja zdania p od „x””.

Negacja „istnieje taki „x”, dla którego zdanie p od „x”” jest równoważna „dla każdego x negacja zdania p od „x””.

Teoria mnogości – jest to jeden z działów logiki matematycznej, który zajmuje się własnościami zbiorów, nie patrząc na elementy, z które te zbiory się składają.

Prawa De Morgana opisują, jak działa dopełnienie zbioru.



kolor ciemny niebieski – kolor niebieski –
kolor jasny niebieski – kolor żółty –
kolor zielony –

stąd wynika, że:

kolor różowy – kolor różowy (znajduje się również pod fioletowym) – A’
kolor fioletowy – kolor fioletowy – B’
kolor różowofioletowy –

kolor różowy – kolor niebieski –
kolor fioletowy –

stąd wynika, że:


kolor różowy – kolor różowy – A’
kolor fioletowy – kolor fioletowy – B’
kolor różowy i fioletowy razem –

Występują one jeszcze w indukcji matematycznej. Zachodzą również w algebrze Boole’a.