Mitkä ovat De Morganin lait?

Matemaattiset tilastot vaativat joskus joukkoteorian käytön. De Morganin lait ovat kaksi lausetta, jotka kuvaavat vuorovaikutusta eri joukkoteorian toimintojen välillä. Lait ovat kaikki kaksi sarjaa koskevat ja B:

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

Tutkittuaan, mitä kukin näistä lauseista tarkoittaa, tarkastelemme esimerkkiä näiden käyttämisestä.

Ymmärtääksemme mitä De Morganin lakit sanovat, meidän on muistettava joitain määritelmiä teoriaoperaatioista. Erityisesti meidän on tiedettävä liitto ja Risteys kahdesta sarjasta ja sarjan komplementti.

De Morganin lait liittyvät yhdistymisen, leikkauksen ja komplementaation vuorovaikutukseen. Muista tuo:

• Sarjojen leikkauspiste ja B koostuu kaikista elementeistä, jotka ovat yhteisiä molemmille ja B. Risteystä merkitään ∩ B.
• Sarjojen liitto ja B koostuu kaikista elementeistä, jotka molemmissa tai B, mukaan lukien molempien sarjojen elementit. Risteystä merkitään merkinnällä A U B.
• Sarjan täydennys koostuu kaikista elementeistä, jotka eivät ole . Tätä komplementtia merkitään tähdellä A^C.

Nyt kun olemme muistuttaneet nämä perusoperaatiot, näemme De Morganin lakien lausunnon. Jokaiselle sarjoille ja B meillä on:

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

Näitä kahta lausumaa voidaan havainnollistaa käyttämällä Venn-kaavioita. Kuten jäljempänä nähdään, voimme osoittaa esimerkkiä käyttämällä. Meidän on osoitettava, että nämä väitteet ovat totta todista heille käyttämällä joukon teoriaoperaatioiden määritelmiä.

Harkitse esimerkiksi joukkoa todelliset luvut välillä 0 - 5. Me kirjoitamme tämän intervallimerkinnällä [0, 5]. Tässä joukossa meillä on = [1, 3] ja B = [2, 4]. Lisäksi perusoperaatioiden soveltamisen jälkeen meillä on:

• Täydennys ^C = [0, 1) U (3, 5]
• Täydennys B^C = [0, 2) U (4, 5]
• Unioni U B = [1, 4]
• Risteys ∩ B = [2, 3]

Aloitamme laskemalla liitto ^C U B^C. Näemme, että [0, 1) U (3, 5]: n ja [0, 2) U (4, 5]: n yhdistelmä on [0, 2) U (3, 5]. Risteys ∩ B on [2, 3]. Näemme, että tämän joukon [2, 3] komplementti on myös [0, 2) U (3, 5]. Tällä tavalla olemme osoittaneet sen ^C U B^C = ( ∩ B)^C.

Nyt näemme [0, 1) U (3, 5]: n ja [0, 2) U: n (4, 5] leikkauspisteen [0, 1) U (4, 5]. Näemme myös, että [1, 4]: n komplementti on myös [0, 1) U (4, 5]. Tällä tavalla olemme osoittaneet sen ^C ∩ B^C = ( U B)^C.

Koko logiikan historian ajan ihmiset, kuten Aristoteles ja William of Ockham ovat antaneet lausuntoja, jotka vastaavat De Morganin lakeja.

De Morganin lait on nimetty Augustus De Morganin mukaan, joka asui vuosina 1806–1871. Vaikka hän ei löytänyt näitä lakeja, hän oli ensimmäinen, joka esitti nämä lausunnot muodollisesti käyttämällä matemaattista muotoilua ehdotuslogiikassa.