Diskretne matematičke metode - matematika

Maturski, Seminarski , Maturalni i diplomski radovi iz matematike.

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.

Skupovi, Funkcije, Relacije
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}

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