Mitkä ovat De Morganin lait?

Artículo revisado y aprobado por nuestro equipo editorial, siguiendo los criterios de redacción y edición de YuBrain.


Logiikka on matematiikan haara, ja osa siitä on joukkoteoriaa. De Morganin lait ovat kaksi postulaattia joukkojen välisestä vuorovaikutuksesta. Nämä lait tallentavat edeltäjiä Aristoteles ja William of Ockham. Augustus De Morgan eli vuosien 1806 ja 1871 välillä ja oli ensimmäinen, joka sisällytti postuloimansa lait matemaattisen logiikan muodolliseen rakenteeseen.

Operaattorit joukkoteoriassa

Ennen kuin siirrymme De Morganin postulaatteihin, katsotaanpa joitain joukkoteorian määritelmiä.

Jos on olemassa kaksi elementtijoukkoa, joita kutsutaan nimellä A ja B, näiden kahden joukon leikkauspiste on molemmille joukoille yhteinen elementtijoukko. Kahden joukon leikkauskohta on merkitty symbolilla ∩, ja se on toinen joukko, jota voimme kutsua C:ksi; C = A∩B, ja C on joukko elementtejä, jotka esiintyvät sekä ryhmässä A että ryhmässä B. Samoin kahden joukon A ja B liitto on uusi joukko, joka sisältää kaikki A:n ja B:n alkiot, ja se merkitään symboli U. Joukko C, A:n ja B:n liitto, C = AUB, on joukko, joka on integroitu kaikkiin A:n ja B:n elementteihin. Kolmas määritelmä, joka meidän on muistettava, on joukon komplementti : jos meillä on tietty elementtien universumi ja tämän universumin joukko A, A:n komplementti on joukko tämän universumin elementtejä, jotka eivät kuulu joukkoon A. A:n komplementtijoukkoa merkitään A C .

Nämä kolme joukkojen välistä operaattoria voidaan yleistää useiden joukkojen väliseksi operaatioksi eli useiden joukkojen leikkauspisteeksi, liitoksi ja komplementiksi. Katsotaanpa yksinkertaista esimerkkiä. Seuraavassa kuvassa on Venn-kaavio kolmesta sarjasta: linnut, joita edustavat papukaija, strutsi, ankka ja pingviini; elävät olennot, jotka lentävät, joita edustavat papukaija, ankka, perhonen ja lentävät kalat, ja elävät olennot, jotka uivat, joita edustavat ankka, pingviini, lentävä kala ja valas. Ankka on kolmen sarjan leikkausjoukko: lentävien lintujen ja elävien olentojen liitto koostuu strutista, papukaijasta, perhosesta, ankasta, pingviinistä ja lentävästä kalasta. Ja lentävien ja uivien elävien olentojen täydennys on sarja, joka sisältää strutsin.

Kolmen sarjan Venn-kaavio.
Kolmen sarjan Venn-kaavio.

De Morganin lait

Nyt voimme nähdä De Morganin lakien postulaatit. Ensimmäinen postulaatti sanoo, että kahden joukon A ja B joukon leikkauspisteen komplementti on yhtä suuri kuin A:n ja B:n komplementin joukkoliitto. Edellisessä kappaleessa määriteltyjä operaattoreita käyttämällä voidaan kirjoittaa De Morganin ensimmäinen laki seuraavalla tavalla:

(A∩B) C = A C UB C

De Morganin toinen laki olettaa, että A:n ja B:n liitosjoukon komplementti on yhtä suuri kuin A:n komplementtijoukon ja B:n komplementtijoukon leikkauspiste, ja se merkitään seuraavasti:

(AUB) C = A C ∩ B C

Katsotaanpa esimerkkiä. Tarkastellaan kokonaislukujen joukkoa 0-5. Tätä merkitään [0,1,2,3,4,5]. Tässä universumissa määrittelemme kaksi joukkoa A ja B. A on joukko numeroita 1, 2 ja 3; A = [1,2,3]. YB on joukko numeroita 2, 3 ja 4; B = [2,3,4]. De Morganin ensimmäinen laki pätee seuraavasti.

A = [1,2,3]; B = [2,3,4]

De Morganin ensimmäinen laki: (A∩B) C = A C UB C

(A∩B) C

A∩B = [1,2,3]∩[2,3,4] = [2,3]

(A∩B) C = [2,3] C = [0,1,4,5]

A C UB C

A C = [1,2,3] C = [0,4,5]

B C = [2,3,4] C = [0,1,5]

A C UB C = [0,4,5]U[0,1,5] = [0,1,4,5]

Tasa-arvon molemmin puolin olevien operaattoreiden soveltamisen tulos osoittaa, että De Morganin ensimmäinen laki on todennettu. Katsotaanpa esimerkin soveltamista toiseen postulaattiin.

De Morganin toinen laki: (AUB) C = A C ∩ B C

(AUB) C

AUB = [1,2,3]U[2,3,4] = [1,2,3,4]

(AUB) C = [1,2,3,4] C = [0,5]

A C ∩ B C

A C = [1,2,3] C = [0,4,5]

B C = [2,3,4] C = [0,1,5]

A C ∩ B C = [0,4,5] ∩[0,1,5] = [0,5]

Kuten ensimmäisessä postulaatissa, annetussa esimerkissä De Morganin toinen laki pätee myös.

Lähteet

AG Hamilton. Logiikka matemaatikoille. Pääkirjoitus Paraninfo, Madrid, 1981.

Carlos Ivorra Castillo. Logiikka ja joukkoteoria . Käytetty marraskuussa 2021

-Mainos-

mm
Sergio Ribeiro Guevara (Ph.D.)
(Doctor en Ingeniería) - COLABORADOR. Divulgador científico. Ingeniero físico nuclear.

Artículos relacionados