HomeisHver eru lögmál De Morgan?

Hver eru lögmál De Morgan?

Rökfræði er grein stærðfræðinnar og hluti hennar er mengjafræði. Lögmál De Morgan eru tvær staðsetningar um samspil mengi. Þessi lög skrá fordæmi í Aristótelesi og Vilhjálmi frá Ockham. Augustus De Morgan var uppi á árunum 1806 til 1871 og var fyrstur til að setja lögin sem hann setti fram í formlegri uppbyggingu stærðfræðilegrar rökfræði.

Rekstraraðilar í mengjafræði

Áður en við förum yfir í staðsetningar De Morgan skulum við skoða nokkrar skilgreiningar á mengjafræði.

Ef það eru einhver tvö mengi staka, sem við köllum A og B, eru skurðpunktur þessara tveggja menga mengi staka sem eru sameiginleg fyrir báðum mengunum. Skurðpunktur tveggja menga er táknaður með tákninu ∩, og er annað mengi sem við getum kallað C; C = A∩B, og C er mengi staka sem koma fyrir bæði í hópi A og hópi B. Á sama hátt er sameining tveggja menga A og B nýtt mengi sem inniheldur alla þætti A og B, og það er tekið fram með táknið U. Mengið C, sameining A og B, C = AUB, er mengi sem er samþætt öllum þáttum A og B. Þriðja skilgreiningin sem við verðum að muna er fylling mengis: ef við erum með ákveðinn alheim af frumefnum og mengi A af þessum alheimi, þá er complement af A mengi frumefna þess alheims sem tilheyra ekki menginu A. Complement mengi A er táknað sem A C .

Hægt er að alhæfa þessa þrjá rekstraraðila á milli menga yfir í aðgerð milli nokkurra menga, það er að segja að skurðpunktur, sameining og viðbót nokkurra menga. Við skulum líta á einfalt dæmi. Eftirfarandi mynd sýnir Venn skýringarmyndina af þremur settum: fuglunum, táknaðir með páfagauknum, strútnum, öndinni og mörgæsinni; lífverurnar sem fljúga, táknaðar með páfagauknum, öndinni, fiðrildinu og fljúgandi fiskunum, og lífverurnar sem synda, táknaðar með öndinni, mörgæsinni, flugfiskinum og hvalnum. Öndin er skurðarmengi settanna þriggja: sameining fugla og lífvera sem fljúga samanstendur af strútnum, páfagauknum, fiðrildinu, öndinni, mörgæsinni og fljúgandi fiskinum. Og viðbót lífveranna sem fljúga og þeirra sem synda er settið sem inniheldur strútinn.

Venn skýringarmynd af þremur settum. Venn skýringarmynd af þremur settum.

Lög De Morgan

Nú getum við séð forsendur laga De Morgan. Fyrsta staðsetningin segir að fylling mengunarskurðar tveggja menga A og B sé jöfn mengisambandi samhliða A og complements B. Með því að nota rekstrartölurnar sem skilgreindar eru í fyrri málsgrein er hægt að skrifa fyrsta lögmál De Morgan. sem eftirfarandi leið:

(A∩B) C = A C UB C

Annað lögmál De Morgan gerir ráð fyrir því að fylling sameiningarmengis A og B sé jöfn skurðpunkti fyllingarmengis A við fyllingarmengis B, og það er tekið fram sem hér segir:

(AUB) C = A C ∩ B C

Við skulum sjá dæmi. Lítum á mengi heiltalna frá 0 til 5. Þetta er táknað sem [0,1,2,3,4,5]. Í þessum alheimi skilgreinum við tvö mengi A og B. A er mengi númeranna 1, 2 og 3; A = [1,2,3]. YB er mengi númeranna 2, 3 og 4; B = [2,3,4]. Fyrstu lög De Morgan myndu gilda sem hér segir.

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

Fyrsta lögmál De Morgan: (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]

Niðurstaðan af beitingu rekstraraðila beggja vegna jafnræðisins sýnir að fyrsta lögmál De Morgan er staðfest. Við skulum sjá hvernig dæmið er beitt á seinni setninguna.

Annað lögmál De Morgan: (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]

Eins og með fyrstu forsendu, í tilgreindu dæmi á annað lögmál De Morgan einnig við.

Heimildir

AG Hamilton. Rökfræði fyrir stærðfræðinga. Ritstjórn Paraninfo, Madrid, 1981.

Carlos Ivorra Castillo. Rökfræði og mengjafræði . Skoðað í nóvember 2021