Čo sú De Morganove zákony?

Matematická štatistika niekedy vyžaduje použitie teórie množín. De Morganove zákony sú dve tvrdenia, ktoré opisujú interakcie medzi rôznymi operáciami teórie množín. Zákony platia pre všetky dve sady a B:

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

Po vysvetlení, čo každé z týchto tvrdení znamená, sa pozrieme na príklad každého z nich.

Aby sme pochopili, čo hovoria De Morganove zákony, musíme si spomenúť na niektoré definície operácií teórie množín. Konkrétne musíme vedieť o zväz a križovatka dvoch súprav a doplnku súpravy.

De Morganove zákony sa týkajú interakcie únie, križovatky a doplnkov. Pripomeňme si, že:

• Priesečník súprav a B pozostáva zo všetkých prvkov, ktoré sú spoločné obom a B. Križovatka je označená ∩ B.
• Spojenie súprav a B pozostáva zo všetkých prvkov, ktoré v jednom alebo B, vrátane prvkov v oboch sadách. Križovatka je označená A U B.
• Doplnok sady pozostáva zo všetkých prvkov, ktoré nie sú prvkami . Tento doplnok je označený ako A^C.

Teraz, keď sme si pripomenuli tieto základné operácie, uvidíme vyhlásenie zákonov De Morgan. Pre každú dvojicu sád

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

Tieto dve výroky je možné ilustrovať pomocou Vennových diagramov. Ako vidno nižšie, môžeme demonštrovať pomocou príkladu. Aby sme dokázali, že tieto vyhlásenia sú pravdivé, musíme dokázať ich pomocou definícií operácií teórie množín.

Napríklad, zvážte súbor skutočné čísla od 0 do 5. Píšeme to v intervalovom zápise [0, 5]. V rámci tohto súboru máme = [1, 3] a B = [2, 4]. Ďalej po uplatnení našich základných operácií máme:

• Doplnok ^C = [0, 1) U (3, 5]
• Doplnok B^C = [0, 2) U (4, 5]
• Únia U B = [1, 4]
• Križovatka ∩ B = [2, 3]

Začneme výpočtom únie ^C U B^C. Vidíme, že spojenie [0, 1] U (3, 5] s [0, 2) U (4, 5] je [0, 2) U (3, 5]. Križovatka ∩ B je [2, 3]. Vidíme, že doplnok tejto množiny [2, 3] je tiež [0, 2) U (3, 5]. Týmto spôsobom sme to dokázali ^C U B^C = ( ∩ B)^C.

Teraz vidíme priesečník [0, 1) U (3, 5] s [0, 2) U (4, 5] je [0, 1) U (4, 5]. Vidíme tiež, že doplnok [1, 4] je tiež [0, 1) U (4, 5]. Týmto spôsobom sme to dokázali ^C ∩ B^C = ( U B)^C.

V celej histórii logiky ľudia ako Aristoteles a William z Ockham urobili vyhlásenia rovnocenné s De Morganovými zákonmi.

De Morganove zákony sú pomenované po Augustovi De Morganovi, ktorý žil v rokoch 1806 - 1871. Hoci tieto zákony neobjavil, bol prvým, kto formálne uviedol tieto výroky pomocou matematickej formulácie v výrokovej logike.