Diskretne matematičke strukture

SADRŽAJ

l.UVOD…………...……………...………………………………...…………………… 3
1.1. Skupovi, Funkcije, Relacije…………..……………………………………….. 3
1.1.1 Skupovi…...............…...……………………………………………………. 3
1.1.2 Definicija funkcije…………..…...…………………………………………… 4
1.1.3 Definicija relacije……………………………………………………………. 4
2. MATEMATIČKA LOGIKA..……….……………………………………………... 5
2.1 O matematičkoj logici ....………………………………………………………… 5
2.2 Iskazni račun ……………..…………………………………………………….. 5
2.2.1. Iskazna algebra……………...…….....……………………………………………. 5
2.2.2. Iskazna formula i njena vrijednost……………………………………………… 5
2.2.3. Prekidačke mreže…………………..………………………………………… 8
2.2.4. Bool-ove funkcije……….………………………………………………………….. 9
3. PREDIKATSKI RAČUN (KVANTIFIKATORSKI RAČUN)………...... ...……11
3.1. Predikatske formule……………………………………………………...….………. 11
3.2. Pojavljivanje promenljivih u predikatskoj formuli…………………………………. 12
3.3. Interpretacija predikatske formule…………………………………………………. 12
3.4. Istinitosna vrednost predikatske formule…………………...………………….. 13
4. ALGEBARSKE STRUKTURE I PROSTORI …………………………………... 14
5. RELACIJSKE STRUKTURE ……………………………………………………. 20
5.1 Parcijalno uređeni skup……………………………………………………………… 20
5.2 Supremum. infimum. rešetka …………………………..……………………… 21
6. OSNOVNI POJMOVI U TEORIJI GRAFOVA………………………………… 22
6.1. Najkraće udaljenosti u grafu……………………………………………………………... 26
6.2. Razapinjajuća stabla………………………………………………………………………. 26
7. TEORIJA KONAČNIH AUTOMATA …………………………………………... 27
7.1.Konačna mašina…………………………………………………………………………… 28
7.2 Konačni automat…………………………………………………………………………… 31
8. FORMALNI JEZICI GRAMATIKE…………………………………………….. 34
8.1 Fornlalni jezici …………………………………………………………………………….. 34
8.2 Gramatike…………………………………………………………………………………... 34
8.3 Veza između automata i regularnih gramatika……………….………………………. 37


l.UVOD


Pod diskretnom matematikom se podrazumjevaju oblasti matematike, kao što su logika, algebra, kombinatorika, teorija grafova ili određeni djelovi vjerovatnoće; u opštem slučaju, to su sve oblasti matematike čiji se predmet proučavanje ne može opisati pomoću neprekidnosti funkcija, odnosno pojmova izvoda i integrala.

1.1. Skupovi, Funkcije, Relacije
1.1.1 Skupovi

Osnovni matematički objekat je SKUP. Skup se zapisuje navođenjem njegovih elemenata između vitičastih zagrada{i}. Skup koji sadrži brojeve 1, 3 i 5 (i nijedan više) zapisuje se kao {1, 3, 5}. Ovaj skup se može zapisati i kao {1, 3, 5}, ali i kao {3, 1, 5} , jer se višestruko ponavljanje istog elementa ne uzima u obzir. Tri tačke (...) u {2,4,6,8,...} znače "i tako dalje, po istom obrascu" t.j. ovaj zapis označava skup svih parnih prirodnih brojeva. Odgovarajući obrazac treba da bude očigledan. Na primjer {21, 22, 23} je lako razumljivo kao skup svih stepena broja 2, dok je zapis {2, 4, 8,…} manje očigledan.
Skupovi se obično označavaju velikim slovima, s tim što je za najvažniji skup matematike i čovječanstva uopšte, skup prirodnih brojeva {1, 2, 3, ...}, za koji je rezervisano slovo N. Još jedan važan skup je skup bez elemenata. Postoji samo jedan takav skup, označava se sa { } i naziva prazan skup. Primjetimo da prazan skup može da bude element drugog skupa. Na prirmjer, { } je skup koji sadrži prazan skup kao svoj element, pa nije isto što i !
Činjenica da skup X sadrži elemenat x zapisuje se pomoću simbola . Zapis x X se čita kao "x je element X", "x pripada X", "X sadrži x", i.t.d. U slučaju da element x ne pripada skupu X pišemo x X.
Složeniji i interesantniji skupovi obično se dobivaju od poznatih skupova pomoću nekih pravila i osobina. Takvi skupovi se zapisuju u sledećem obliku:
A = {x : x ima osobinu P}
Na primjer, skup svih kvadrata prirodnih brojeva može da se zapiše kao:
{n N: postoji k N tako da je n = k2}
ili kraće kao:
{k2 : k N}
Operacije sa skupovima
Najvažnije i najčešće operacije sa skupovima su unija, presjek, razlika, simetrična razlika i komplement. Za skupove X i Y ove operacije se definišu na sledeći način:

Unija: X U Y = {z : z X ili z Y};
Presjek: X Y = {z : z X i z Y};
Razlika: X \ Y = {z : z X i z Y};
Simetrična razlika: X Y = ( X \ Y) U (Y \ X).

1.1.2 Definicija funkcije

Pod funkcijom se podrazumjeva uređena trojka ( A, B, f), gdje je f AxB, pri čemu za svako x A postoji tačno jedno y B tako da ( x, y) f. Skup A se naziva domen, skup B se naziva kodomen, a f je pravi preslikavanja. Činjenica da funkcija preslikava elemente domena A u elemente kodomena B pomoću pravila preslikavanja f sa zapisuje pomoću f: A B, a za (x,y) f ravnopravno (i češće) pišemo f(x) = y. Samo pravilo preslikavanja f se zadaje formulom ili navođenjem parova elemenata (x,y) koji pripadaju f.

1.1.3 Definicija relacije

Relacija u najkraćem predstavlja odnos između elemenata nekih skupova. Ako su dati skupovi Al, A2, ...,Ak, k N, tada se pod relacijom dužine k između elemenata A1, A2,...,Ak, podrazumjeva podskup p A1xA2x...Ak. Ako, (x1, x2, ....x) p tada kažemo da su elementi x1, x2, ...xk u relacij p. S druge strane, ako je A1=A2=...Ak=A, tada kažemo da je p relacija dužine k na skupu A.