HomeeoKio estas la leĝoj de De Morgan?

Kio estas la leĝoj de De Morgan?

Logiko estas branĉo de matematiko, kaj parto de ĝi estas aroteorio. La leĝoj de De Morgan estas du postulatoj pri la interago inter aroj. Tiuj leĝoj registras precedencojn en Aristotelo kaj Vilhelmo de Ockham. Augustus De Morgan vivis inter 1806 kaj 1871 kaj estis la unua se temas pri inkludi la leĝojn kiujn li postulis en la formala strukturo de matematika logiko.

Operatoroj en aroteorio

Antaŭ ol pluiri al la postulatoj de De Morgan, ni rigardu kelkajn difinojn de aroteorio.

Se estas iuj du aroj de elementoj, kiujn ni nomos A kaj B, la intersekco de ĉi tiuj du aroj estas la aro de elementoj komuna al ambaŭ aroj. La intersekco de du aroj estas indikita per la simbolo ∩, kaj estas alia aro kiun ni povas nomi C; C = A∩B, kaj C estas la aro de elementoj kiuj aperas en kaj grupo A kaj grupo B. Simile, la kuniĝo de du aroj A kaj B estas nova aro enhavanta ĉiujn elementojn de A kaj B, kaj ĝi notiĝas per la simbolo U. La aro C, kuniĝo de A kaj B, C = AUB, estas aro, kiu estas integrita kun ĉiuj elementoj de A kaj B. La tria difino, kiun ni devas memori, estas la komplemento de aro.: se ni havas certan universon de elementoj kaj aron A de ĉi tiu universo, la komplemento de A estas la aro de elementoj de tiu universo kiuj ne apartenas al la aro A. La komplementaro de A estas signata kiel A C .

Tiuj tri funkciigistoj inter aroj povas esti ĝeneraligitaj al la operacio inter pluraj aroj, tio estas, al la intersekco, kuniĝo kaj komplemento de pluraj aroj. Ni rigardu simplan ekzemplon. La sekva figuro montras la Venn-diagramon de tri aroj: la birdoj, reprezentitaj per la papago, la struto, la anaso kaj la pingveno; la vivantaj estaĵoj kiuj flugas, reprezentitaj per la papago, la anaso, la papilio kaj la flugfiŝo, kaj la vivantaj estaĵoj kiuj naĝas, reprezentitaj per la anaso, la pingveno, la flugfiŝo kaj la baleno. La anaso estas la intersekciĝo de la tri aroj: la unio de birdoj kaj vivestaĵoj kiuj flugas konsistas el la struto, la papago, la papilio, la anaso, la pingveno kaj la flugfiŝo. Kaj la komplemento de la vivantaj estaĵoj, kiuj flugas kaj tiuj, kiuj naĝas, estas la aro, kiu enhavas la struton.

Diagramo de Venn de tri aroj. Diagramo de Venn de tri aroj.

La Leĝoj de De Morgan

Nun ni povas vidi la postulatojn de la leĝoj de De Morgan. La unua postulato diras ke la komplemento de la aro-intersekco de du aroj A kaj B estas egala al la aro-unio de la komplemento de A kaj la komplemento de B. Uzante la funkciigistojn difinitajn en la antaŭa paragrafo, la unua leĝo de De Morgan povas esti skribita jene:

(A∩B) C = A C UB C

La dua leĝo de De Morgan postulas ke la komplemento de la uniaro de A kaj B estas egala al la intersekco de la komplementaro de A kun la komplementaro de B, kaj ĝi notiĝas jene:

(AUB) C = A C ∩ B C

Ni vidu ekzemplon. Konsideru la aron de entjeroj de 0 ĝis 5. Ĉi tio estas signata kiel [0,1,2,3,4,5]. En ĉi tiu universo ni difinas du arojn A kaj B. A estas la aro de nombroj 1, 2 kaj 3; A = [1,2,3]. YB estas la aro de nombroj 2, 3 kaj 4; B = [2,3,4]. La unua leĝo de De Morgan validus jene.

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

La unua leĝo de 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]

La rezulto de la aplikado de la operatoroj ambaŭflanke de la egaleco montras, ke la unua leĝo de De Morgan estas kontrolita. Ni vidu la aplikon de la ekzemplo al la dua postulato.

Dua leĝo de 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]

Kiel ĉe la unua postulato, en la donita ekzemplo ankaŭ validas la dua leĝo de De Morgan.

Fontoj

AG Hamilton. Logiko por Matematikistoj. Eldonejo Paraninfo, Madrido, 1981.

Carlos Ivorra Castillo. Logiko kaj aroteorio . Alirita novembron 2021