HomeltKokie yra De Morgano dėsniai?

Kokie yra De Morgano dėsniai?

Logika yra matematikos šaka, o dalis jos yra aibių teorija. De Morgano dėsniai yra du postulatai apie aibių sąveiką. Šie dėsniai užfiksuoja Aristotelio ir Viljamo Ockamo pirmtakus. Augustas De Morganas gyveno 1806–1871 m. ir pirmasis įtraukė savo postuluotus dėsnius į formalią matematinės logikos struktūrą.

Operatoriai aibių teorijoje

Prieš pereidami prie De Morgano postulatų, pažvelkime į kai kuriuos aibių teorijos apibrėžimus.

Jei yra dvi elementų rinkiniai, kuriuos vadinsime A ir B, šių dviejų aibių sankirta yra elementų rinkinys, bendras abiem aibėms. Dviejų aibių sankirta žymima simboliu ∩ ir yra kita aibė, kurią galime vadinti C; C = A∩B, o C yra elementų, esančių ir A, ir B grupėje, rinkinys. Panašiai dviejų aibių A ir B sąjunga yra nauja aibė, kurioje yra visi A ir B elementai, ir ji pažymima su simbolis U. Aibė C, A ir B sąjunga, C = AUB, yra aibė, integruota su visais A ir B elementais. Trečiasis apibrėžimas, kurį turime atsiminti , yra aibės papildinys : jei turime tam tikrą elementų visatą ir šios visatos aibę A, tai A komplementas yra tos visatos elementų, kurie nepriklauso aibei A, aibė. A komplemento aibė žymima kaip A C .

Šiuos tris operatorius tarp aibių galima apibendrinti į operaciją tarp kelių aibių, tai yra į kelių aibių sankirtą, sąjungą ir papildymą. Pažiūrėkime į paprastą pavyzdį. Toliau pateiktame paveikslėlyje pavaizduota trijų rinkinių Venno diagrama: paukščiai, pavaizduoti papūga, strutis, antis ir pingvinas; gyvos būtybės, kurios skraido, atstovaujamos papūga, antis, drugelis ir skraidančios žuvys, ir gyvos būtybės, kurios plaukia, atstovaujamos antis, pingvino, skraidančios žuvies ir banginio. Antis yra trijų rinkinių sankirtos rinkinys: skraidančių paukščių ir gyvų būtybių sąjungą sudaro strutis, papūga, drugelis, antis, pingvinas ir skraidančios žuvys. O skraidančių ir plaukiančių gyvų būtybių papildymas yra rinkinys, kuriame yra strutis.

Trijų rinkinių Venno diagrama. Trijų rinkinių Venno diagrama.

De Morgano dėsniai

Dabar matome De Morgano dėsnių postulatus. Pirmasis postulatas sako, kad dviejų aibių A ir B aibės sankirtos papildinys yra lygus A ir B papildinio aibių sąjungai. Naudojant ankstesnėje pastraipoje apibrėžtus operatorius, galima parašyti pirmąjį De Morgano dėsnį. tokiu būdu:

(A∩B) C = A C UB C

Antrasis De Morgano dėsnis teigia, kad A ir B sąjungos aibės komplementas yra lygus A komplemento aibės sankirtai su B komplementų aibe, ir pažymima taip:

(AUB) C = A C ∩ B C

Pažiūrėkime pavyzdį. Apsvarstykite sveikųjų skaičių aibę nuo 0 iki 5. Tai žymima kaip [0,1,2,3,4,5]. Šioje visatoje mes apibrėžiame dvi aibes A ir B. A yra skaičių 1, 2 ir 3 aibė; A = [1,2,3]. YB yra skaičių 2, 3 ir 4 aibė; B = [2,3,4]. Pirmasis De Morgano dėsnis būtų taikomas taip.

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

Pirmasis De Morgano dėsnis: (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]

Abiejų lygybės pusių operatorių taikymo rezultatas rodo, kad pirmasis De Morgano dėsnis yra patikrintas. Pažiūrėkime, kaip pavyzdys taikomas antrajam postulatui.

Antrasis De Morgano dėsnis: (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]

Kaip ir pirmajame postulate, pateiktame pavyzdyje taip pat galioja antrasis De Morgano dėsnis.

Šaltiniai

AG Hamiltonas. Logika matematikams. Redakcija „Paraninfo“, Madridas, 1981 m.

Carlosas Ivorra Castillo. Logika ir aibių teorija . Žiūrėta 2021 m. lapkričio mėn