HomebsŠta su De Morganovi zakoni?

Šta su De Morganovi zakoni?

Logika je grana matematike, a njen dio je teorija skupova. De Morganovi zakoni su dva postulata o interakciji između skupova. Ovi zakoni bilježe prethodnike kod Aristotela i Williama od Ockhama. Augustus De Morgan je živio između 1806. i 1871. godine i prvi je uključio zakone koje je postulirao u formalnu strukturu matematičke logike.

Operatori u teoriji skupova

Prije nego pređemo na De Morganove postulate, pogledajmo neke definicije teorije skupova.

Ako postoje bilo koja dva skupa elemenata, koje ćemo nazvati A i B, presjek ova dva skupa je skup elemenata zajednički za oba skupa. Presek dva skupa je označen simbolom ∩, i to je još jedan skup koji možemo nazvati C; C = A∩B, a C je skup elemenata koji se pojavljuju i u grupi A i u grupi B. Slično tome, unija dva skupa A i B je novi skup koji sadrži sve elemente iz A i B, a to je zabilježeno sa simbol U. Skup C, unija A i B, C = AUB, je skup koji je integriran sa svim elementima A i B. Treća definicija koju moramo zapamtiti je komplement skupa : ako imamo određeni univerzum elemenata i skup A ovog univerzuma, komplement od A je skup elemenata tog univerzuma koji ne pripadaju skupu A. Komplementarni skup od A označava se kao A C .

Ova tri operatora između skupova mogu se generalizirati na operaciju između nekoliko skupova, odnosno na presek, uniju i dopunu nekoliko skupova. Pogledajmo jednostavan primjer. Sljedeća slika prikazuje Vennov dijagram od tri skupa: ptice, predstavljene papagajem, nojom, patkicom i pingvinom; živa bića koja lete, koju predstavljaju papagaj, patka, leptir i leteća riba, i živa bića koja plivaju, predstavljena patka, pingvin, leteća riba i kit. Patka je presek tri seta: skup ptica i živih bića koja lete čine noj, papagaj, leptir, patka, pingvin i leteća riba. A dopuna živih bića koja lete i onih koja plivaju je komplet koji sadrži noja.

Venov dijagram od tri seta. Venov dijagram od tri seta.

De Morganovi zakoni

Sada možemo vidjeti postulate De Morganovih zakona. Prvi postulat kaže da je komplement skupa preseka dva skupa A i B jednak skupu uniji komplementa A i komplementa B. Koristeći operatore definisane u prethodnom paragrafu, De Morganov prvi zakon se može napisati na sledeći način:

(A∩B) C = A C UB C

De Morganov drugi zakon postulira da je komplement unijalnog skupa A i B jednak presjeku komplementarnog skupa A sa komplementarnim skupom B, a bilježi se kako slijedi:

(AUB) C = A C ∩ B C

Pogledajmo primjer. Razmotrimo skup cijelih brojeva od 0 do 5. Ovo se označava kao [0,1,2,3,4,5]. U ovom univerzumu definišemo dva skupa A i B. A je skup brojeva 1, 2 i 3; A = [1,2,3]. YB je skup brojeva 2, 3 i 4; B = [2,3,4]. De Morganov prvi zakon bi se primjenjivao na sljedeći način.

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

De Morganov prvi zakon: (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]

Rezultat primjene operatora na obje strane jednakosti pokazuje da je De Morganov prvi zakon verifikovan. Pogledajmo primjenu primjera na drugi postulat.

De Morganov drugi zakon: (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]

Kao i kod prvog postulata, u datom primjeru vrijedi i De Morganov drugi zakon.

Izvori

AG Hamilton. Logika za matematičare. Uredništvo Paraninfo, Madrid, 1981.

Carlos Ivorra Castillo. Logika i teorija skupova . Pristupljeno novembra 2021