Diskretna matematika

I DEO

ISKAZI

Definicija: Iskaz je recenica koja ima tacno jednu istinitosnu vrednost ( ili je tacna ili je netacna)
Iskaz obelezavamo sa malim slovima (p, q, r, s, ...)

Od bilo koja dva iskaza moze se oformiti novi iskaz koriscenjem veznika kakvi su ,,i“, ,,ili“, ,,ako. . .onda“ i ,,ako i samo ako“. Od jednog iskaza moze se saˇciniti novi ako mu na pocetku dodamo ,,nije tacno da“ (ili umetanjem negacije).

Da bi se izbegle dvosmislenosti i razlicita tumacenja, logickim analogijama ovih prirodno-jezickih veznika daju se precizna znacenja u vidu istinitosnih tablica koje tacno propisuju kako se istinitost nekog kompleksnog iskaza moze odrediti na osnovu tacnosti njegovih sastavnih delova. Za svaku od pet glavnih operacija na iskazima da cemo preciznu definiciju u obliku istinitosne tablice i priblizni prirodno-jezicki ekvivalent. 

SKUPOVI

Skupove obeležavamo velikim latiničnim slovima A,B,…,X,Y,… Elemente skupa obeležavamo najčešće malim latiničnim slovima a,b,…,x,y,…Ako element x pripada skupu X, onda to označavamo sa x∈X, dok ako element x ne pripada skupu X, to označavamo sa x∉X. Element skupa može biti bilo šta: broj, tačka, linija, jabuka, slovo, galaksija, pa čak i drugi skup. Sve elemente nekog skupa možemo predstaviti na različite načine. Jedan od tih načina je, da između dve vitičaste zagrade nabrojimo sve elemente odvajajući ih zarezom: X={x1,x2,x3,…,xn}. 

Ovaj način je zgodan kada skup ima mali broj elemenata, ali kod većih skupova javlja se potreba za sledećim obeležavanjem elemenata skupa: A={x∣S(x)}. Ovo znači da skup A sačinjavaju svi elementi koji imaju neko svojstvo S. 

Npr.: A={x∣2<x<3}, što znači da su elementi ovog skupa svi oni brojevi, manji od 3 a veći od 2. Naravno, sve elemente tog skupa ne možemo napisati, jer ih ima beskonačno. Često se mogući iksevi ograniče samo na neke elemente drugog skupa, pa tako W={x∈N∣2<x<6} označava sve prirodne brojeve veće od dva i manje od šest, tj. {3,4,5}  



. 

Treći način obeležavanja skupa je pomoću Vennovog dijagrama. Ovaj način je mnogo intuitivniji od prethodna dva. Crtanjem zatvorene krive linije (kružnice) mi definišemo skup, a elementi tog skupa predstavljaju sve tačke koje se nalaze unutar krive linije. Ova metoda je dobila ime po Englezu Džonu Venu (John Venn; 1834—1923), koji je 1880. prezentovao ovakav način obeležavanja.

Operacije sa skupovima

Kao što u aritmetici poznajemo operacije sabiranja, oduzimanja, množenja itd., a u logici poznajemo logičke operacije (veznike) implikacije, konjunkcije, disjunkcije itd, tako i pri radu sa skupovima možemo da definišemo neke osnovne operacije.

1. Unija skupova
Unija dva skupa se obeležava sa ∪ i označava skup čiji su elementi svi elementi oba skupa

                                                A∪B={x∣x∈A∨x∈B}

Venovim dijagramom predstavljeno:

2. Presek skupova

Presek dva skupa, u oznaci ∩, definišemo kao skup koji sadrži samo elemente koji se sadrže u oba skupa.           

                                                A∩B={x∣x∈A∧x∈B}

3. Razlika skupova

Razliku dva skupa u oznaci ∖ definišemo kao skup koji sadrži sve elemente prvog skupa ali ne sadrži nijedan element drugog skupa.

                                                

                                                
                                                A∖B={x∣x∈A∧x∉B}

                                                   

4. Simetrična razlika

Skup (A∖B)∪(B∖A) nazivamo simetrična razlika i obeležavamo sa A△B.

Simetrična razlika se može definisati i kao: A△B=(A∪B)∖(A∩B)

RELACIJE

Relacija ρ dužine n je neprazan podskup Dekartovog proizvoda n skupova. Kada je n = 2 tada govorimo o binarnoj relaciji, dakle o relaciji između elementa x sa elementom y, odnosno o uređenom paru (x, y) iz Dekartovog proizvoda ${\displaystyle A\times B.}$ Ako je ${\displaystyle (x,y)\in \rho }$ tada kažemo da je element ${\displaystyle x\,}$ u relaciji sa elementom ${\displaystyle y\,}$ i pišemo ${\displaystyle x\rho y\,}$.

Za binarnu relaciju ${\displaystyle \rho \subset A\times B}$ moguće je definisati sledeće izraze:

• Domen, tj. oblast definisanosti ${\displaystyle {\mathcal {D(\rho )}}=\{x\in A|(\exists y\in B)x\rho y)\};}$
• kodomen, tj. oblast vrednosti ${\displaystyle {\mathcal {K(\rho )}}=\{y\in B|(\exists x\in A)x\rho y\};}$
• inverzna relacija ${\displaystyle \rho ^{-1}=\{(y,x)\};\,}$
• komplement ${\displaystyle {\bar {\rho }}=(A\times B)\backslash \rho ;}$
• kompozicija relacija ${\displaystyle \rho \circ \sigma :}$

ako je ${\displaystyle \sigma \subset A\times B}$ i ${\displaystyle \rho \subset B\times C,}$ tada relaciju ${\displaystyle \rho \circ \sigma \subset A\times C,}$ datu sa ${\displaystyle \rho \circ \sigma =\{(x,y)|(\exists z\in B)x\rho z\wedge z\rho y\}}$ nazivamo kompozicija relacija ${\displaystyle \rho \,}$ i ${\displaystyle \sigma \,.}$

Osobine relacija:

Osnovne četiri osobine su:

Graf relacije

• Refleksivnost: ${\displaystyle (\forall x)(x\in X)x\rho x}$. Drugim rečima, data relacija je refleksivna ako i samo ako je svaki element u relaciji sa sobom.
• Simetričnost: ${\displaystyle (\forall x,y)(x,y\in X)\;x\rho y\Rightarrow y\rho x.}$ Drugim rečima, ako za svaki uređeni par elemenata koji je u relaciji postoji i par sa obrnutim poretkom.
• Antisimetričnost: ${\displaystyle (\forall x,y)(x,y\in X)\;x\rho y\land y\rho x\Rightarrow x=y.\,}$ Drugim rečima, ako u datoj relaciji imamo oba poretka jednog para elemenata, onda ih ne možemo imati na način da to mora biti samo jedan element (taj je u relaciji sam sa sobom).
• Tranzitivnost: ${\displaystyle (\forall x,y,z)(x,y,z\in X)\;x\rho y\land y\rho z\Rightarrow x\rho z.}$ Ako je prvi element u relaciji sa drugim, drugi sa trećim, onda mora biti i prvi sa trećim!

Algebarske strukture

Definicija: Ako za bilo koja dva elementa (a,b) koja pripadaj skupu G po nekom postupku dobijemo element C tada kazemo da je na skupu G definisana binarna operacija *. a,b pripadaju G, * c pripada G ( a*b = c) .. 

* -> moze oznacavati bilo koju koju operaciju.

Osobine operacija: 

• Zatvorenost ( za svako a,b koje pripadaju skupu G) a * b pripada skupu G
• Asocijativnost ( za svako a,b,c koje priadaju skupu G) a*(b*c)=(a*b)*c
• Neutralni element (ukoliko postoji neutralni element e koji pripadaju skupu i za svako a koje pripada skupu G) -> a*e=e*a=a
• Inverzni element (za svako a koje pripada skupu G i ukoliko postoji inverzni element nadvuceno a koje takodje pripada skupu G) a* nadvuceno a= nadvuceno a *a= e.