Kakšni so zakoni De Morgana?

Matematična statistika včasih zahteva uporabo teorije množic. De Morganovi zakoni sta dve trditvi, ki opisujeta interakcije med različnimi operacijami teorije množic. Zakone veljajo za kateri koli dva sklopa A in B:

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

Po razlagi, kaj pomeni vsaka od teh trditev, bomo pogledali primer vsake od teh uporabljenih.

Da bi razumeli, kaj pravijo De Morganovi zakoni, se moramo spomniti nekaterih definicij operacij teorije množic. Konkretno moramo vedeti za zveza in križišče dveh sklopov in kompleta kompleta.

De Morganovi zakoni se nanašajo na interakcijo zveze, križišča in komplementa. Spomnimo se:

• Presečišče sklopov A in B je sestavljen iz vseh elementov, ki so skupni obema A in B. Križišče je označeno z A ∩ B.
• Zveza skupov A in B je sestavljen iz vseh elementov, ki so v katerem koli A ali B, vključno z elementi v obeh nizih. Križišče je označeno z A U B.
• Dopolnilo kompleta A je sestavljen iz vseh elementov, ki niso elementi A. To dopolnilo označujemo z A^C.

Zdaj, ko smo se spomnili teh osnovnih operacij, bomo videli izjavo De Morganovih zakonov. Za vsak par kompletov A in B imamo:

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

Ti dve trditvi lahko ponazorimo z uporabo Vennovih diagramov. Kot je razvidno spodaj, lahko dokažemo s primerom. Da bi dokazali, da so te izjave resnične, moramo jih dokazati z uporabo definicij operacij teorije množic.

Na primer, razmislite o nizu realne številke od 0 do 5. To zapišemo v intervacijski zapis [0, 5]. Znotraj tega sklopa, ki ga imamo A = [1, 3] in B = [2, 4]. Poleg tega po uporabi naših osnovnih operacij imamo:

• Dopolnilo A^C = [0, 1) U (3, 5]
• Dopolnilo B^C = [0, 2) U (4, 5]
• Zveza A U B = [1, 4]
• Križišče A ∩ B = [2, 3]

Začnemo z izračunom zveze A^C U B^C. Vidimo, da je zveza [0, 1) U (3, 5] z [0, 2) U (4, 5] enaka [0, 2) U (3, 5]. Križišče A ∩ B je [2, 3]. Vidimo, da je dopolnilo tega niza [2, 3] tudi [0, 2) U (3, 5]. Na ta način smo to dokazali A^C U B^C = (A ∩ B)^C.

Zdaj vidimo presečišče [0, 1) U (3, 5] z [0, 2) U (4, 5] je [0, 1) U (4, 5]. Vidimo tudi, da je dopolnilo [1, 4] tudi [0, 1) U (4, 5]. Na ta način smo to dokazali A^C ∩ B^C = (A U B)^C.

Skozi zgodovino logike so ljudje, kot so Aristotel in William iz Ockhama sta dala izjave, enakovredne De Morgan's Laws.

De Morganovi zakoni so poimenovani po Avgustu De Morganu, ki je živel od leta 1806–1871. Čeprav teh zakonov ni odkril, je bil prvi, ki je te trditve uradno predstavil z uporabo matematične formulacije v logiki predloga.