Prawa De Morgana
Z Wikipedii
Prawa de Morgana - twierdzenia w logice matematycznej i teorii mnogości. Od nazwiska Augusta De Morgana, angielskiego matematyka.
Spis treści |
[edytuj] Logika
1. Negacja alternatywy jest równoważna koniunkcji negacji:
2. Negacja koniunkcji jest równoważna alternatywie negacji:
gdzie p i q oznaczają zdania w sensie logiki.
Prawa de Morgana są tautologiami. Pozwalają też definiować jedne spójniki zdaniowe za pomocą innych. Na przykład, korzystając z koniunkcji i negacji, za pomocą prawa podwójnej negacji można określić alternatywę:
[edytuj] Tabele Prawdy
 |
|||||||||
| p | q |  |
 |
 |
 |
 |
|||
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | |||
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | |||
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||
 |
|||||||||
| p | q |  |
 |
|
|
 |
|||
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | |||
| 0 | 1 | 1 | 0 | 1 | 0 | 0 | |||
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | |||
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | |||
[edytuj] Rachunek kwantyfikatorów
W rachunku kwantyfikatorów prawa De Morgana opisują reguły zaprzeczania kwantyfikatorom:
[edytuj] Teoria mnogości
1. Dopełnienie sumy zbiorów jest równe części wspólnej ich dopełnień:
- (A ∪ B)c=Ac ∩ Bc
2. Dopełnienie części wspólnej zbiorów jest równe sumie ich dopełnień:
- (A ∩ B)c=Ac ∪ Bc
Analogicznie wysławia się prawa De Morgana dla nieskończonych rodzin zbiorów – poniżej ich zapis symboliczny:
