Co jsou De Morganovy zákony?

Matematická statistika někdy vyžaduje použití teorie množin. De Morganovy zákony jsou dvě tvrzení, která popisují interakce mezi různými operacemi teorie množin. Zákony platí pro všechny dvě sady A a B:

1. (A ∩ B)^C = A^C U B^C.
2. (A U B)^C = A^C ∩ B^C.

Po vysvětlení, co každé z těchto tvrzení znamená, se podíváme na příklad každého z těchto použitých.

Abychom pochopili, co říkají De Morganovy zákony, musíme si vzpomenout na některé definice operací teorie množin. Konkrétně musíme vědět o unie a průsečík dvou sad a doplňku sady.

De Morganovy zákony se týkají interakce spojení, průniku a doplňku. Odvolej to:

• Průnik sad A a B sestává ze všech prvků společných pro oba A a B. Průsečík je označen A ∩ B.
• Spojení setů A a B sestává ze všech prvků, které v jednom A nebo B, včetně prvků v obou sadách. Průsečík je označen A U B.
• Doplněk sady A sestává ze všech prvků, které nejsou prvky A. Tento doplněk je označen A^C.

Nyní, když jsme si vzpomněli na tyto základní operace, uvidíme prohlášení De Morganových zákonů. Pro každou dvojici sad A a B my máme:

1. (A ∩ B)^C = A^C U B^C
2. (A U B)^C = A^C ∩ B^C

Tato dvě tvrzení lze ilustrovat pomocí Vennových diagramů. Jak je vidět níže, můžeme to ukázat pomocí příkladu. Abychom prokázali, že tato prohlášení jsou pravdivá, musíme dokázat je pomocí definic operací teorie množin.

Zvažte například sadu reálná čísla od 0 do 5. Píšeme to v intervalové notaci [0, 5]. V této sadě máme A = [1, 3] a B = [2, 4]. Po uplatnění našich základních operací navíc máme:

• Doplněk A^C = [0, 1) U (3, 5]
• Doplněk B^C = [0, 2) U (4, 5]
• Unie A U B = [1, 4]
• Křižovatka A ∩ B = [2, 3]

Začneme výpočtem unie A^C U B^C. Vidíme, že spojení [0, 1) U (3, 5] s [0, 2) U (4, 5] je [0, 2) U (3, 5]. Křižovatka A ∩ B je [2, 3]. Vidíme, že doplněk této sady [2, 3] je také [0, 2) U (3, 5]. Tímto způsobem jsme to dokázali A^C U B^C = (A ∩ B)^C.

Nyní vidíme průnik [0, 1) U (3, 5] s [0, 2) U (4, 5] je [0, 1) U (4, 5]. Vidíme také, že doplněk [1, 4] je také [0, 1) U (4, 5]. Tímto způsobem jsme to dokázali A^C ∩ B^C = (A U B)^C.

V celé historii logiky lidé jako Aristoteles a William z Ockhamu učinili prohlášení rovnocenné De Morganovým zákonům.

De Morganovy zákony jsou pojmenovány po Augustovi De Morganovi, který žil v letech 1806–1871. Ačkoli tyto zákony neobjevil, jako první zavedl tato tvrzení formálně pomocí matematické formulace v výrokové logice.