Matemtika Diskrit

Matemtika Diskrit merupakan cabang matematika yang mempelajari tentang obyek-obyek diskrit.Diskrit itu sendiri adalah sejumlah berhingga elemen yang berbeda atau elemen-elemen yang tidak bersambungan. Dimana data diskrit merupakan data yang satuannya selalu bulat dalam bilangan asli, tidak berbentuk pecahan, Contoh dari data diskrit misalnya manusia, pohon, bola dan lain-lain. trus mengapa belajar Matematika Diskrit ? .. 

1. Landasan berbagai bidang matematika: logika, teori bilangan, aljabar linier dan abstrak, kombinatorika, teori graf, teori peluang (diskrit).

2. Landasan ilmu komputer: struktur data, algoritma, teori database, bahasa formal, teori automata, teori compiler, sistem operasi, dan pengamanan komputer (computer security).

3. Mempelajari latar belakang matematis yang diperlukan untuk memecahkan masalah dalam riset operasi (optimasi diskrit), kimia, ilmu-ilmu teknik, biologi, telekomunikasi, dsb.

Sumber : http://jejakjari007.blogspot.com/2010/01/materi-matematika-diskrit.html

PROPOSISI, KOMBINASI, HUKUM PROPOSISI,DAN TABEL KEBENARAN

1. Pernyataan (Proposisi)

Di dalam matematika, tidak semua kalimat berhubungan dengan logika. Hanya kalimat yang bernilai benar atau salah saja yang digunakan dalam penalaran. Kalimat tersebut dinamakan proposisi (preposition).

Sebuah proposisi(proposition) atau statement ialah sebuah kalimat deklaratif yang memiliki tepat satu nilai kebenaran, yaitu: ”Benar”(B) atau ”Salah”(S).

Kalimat tanya atau kalimat perintah tidak dianggap sebagai pernyataan.

Berikut ini adalah beberapa contoh proposisi :

a. 1 + 2 = 3

b. Presiden RI tahun 2005 adalah SBY

c. 6 adalah bilangan prima

d. Warna bendera RI adalah biru dan merah

Kalimat-kalimat di atas adalah kalimat proposisi karena dapat diketahui benar/salahnya. Kalimat (a) dan (b) bernilai benar, sedangkan kalimat (c) dan (d) bernilai salah.

Kalimat-kalimat berikut bukan pernyataan :

1. x + 2 = 10.

2. Minumlah sirup ini dua kali sehari.

3. Alangkah cantiknya gadis itu!

2. Mengkombinasikan Proposisi

Kita dapat membentuk proposisi baru dengan cara mengkombinasikan satu atau lebih proposisi. Operator yang digunakan untuk mengkombinasikan proposisi disebut operator logika. Operator logika dasar yang digunakan adalah dan (and), atau (or), dan tidak (not). Dua operator pertama dinamakan operator biner karena operator tersebut mengoperasikan dua buah proposisi, sedangkan operator ketiga dinamakan operator uner karena ia hanya membutuhkan satu buah proposisi.

Proposisi baru yang diperoleh dari pengkombinasian tersebut dinamakan proposisi majemuk (compound proposition). Proposisi yang bukan merupakan kombinasi proposisi lain disebut proposisi atomik. Dengan kata lain, proposisi majemuk disusun dari proposisi-proposisi atomik. Metode pengkombinasian proposisi dibahas oleh matematikawan Inggris yang bernama George Boole pada tahun 1854 di dalam bukunya yang terkenal, The Laws of  Thought. Proposisi majemuk ada tiga macam, yaitu konjungsi, disjungsi, dan ingkaran.

Misalkan p dan q adalah proposisi.

Negasi:

Untuk sembarang proposisi, p, yang memiliki nilai kebenaran, B/S, maka negasinya ditulis sebagai, ~p, memiliki nilai kebenaran lawannya, S/B.

Berikut ini adalah contoh negasi :

p : Palembang adalah ibukota propinsi Sumatera Selatan.

~p : Tidak benar Palembang adalah ibukota propinsi Sumatera    Selatan.

atau

Palembang bukan ibukota propinsi Sumatera Selatan.

Di sini ~p salah karena p benar.

Sumber : http://xsan.brothers.blog.unsoed.ac.id/2011/09/18/matematika-distrik/

Terminologi (Istilah) Dasar Pada Graph

1. Bertetangga (adjacent)

Dua buah titik, titik u dan titik v pada graph tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u,v) adalah sebuah sisi pada graph G.

2. Bersisian (incident)

Misal sembarang sisi , sisi e dikatakan bersisian dengan titik u dan titik v.

3. Titik terpencil (isolated vertex)

Titik terpencil adalah titik yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dikatakan bahwa titik terpencil adalah titik yang tidak satupun bertetangga dengan titik-titik lainnya.

4. Jalan (walk)

Misalkan G adalah sebuah graph. Sebuah jalan (walk) di G adalah sebuah barisan berhingga (tak kosong) yang suku-sukunya bergantian titik dan sisi, sedemikian hingga dan adalah titik-titik akhir sisi ei, untuk . Katakan W adalah sebuah jalan dari titik (titik awal) ke titik (titik akhir), sedangkan titik-titik disebut titik-titik internal W dan k disebut panjang jalan W. Dengan kata lain, jalan (walk) ialah dimana sisi dan titiknya boleh berulang.

5. Jejak (trail)

Jejak adalah jalan yang sisi-sisinya tidak ada yang sama, tetapi titiknya boleh ada yang sama.

6. Lintasan (path)

Lintasan adalah jejak yang semua titiknya berbeda (sisi dan titiknya tidak ada yang sama).

7. Sirkit

Sirkit adalah Jejak tertutup.

8. Siklus/lintasan tertutup (sikel)

Sikel adalah sebuah sirkit yang titik awal dan semua titik internalnya berbeda (titik awal dan titik akhirnya sama dimana titik dan sisinya tidak ada yang berulang).

9. Terhubung dan tidak terhubung

Suatu graph G dikatakan terhubung jika dan hanya jika setiap 2 titik dalam G terhubung (gambar a), sedangkan suatu graph G dikatakan tidak terhubung jika dan hanya jika ada 2 titik dalam G yang tidak terhubung (gambar b).

10. Komplemen

Misalkan G sebuah graph sederhana. Komplemen G dilambangkan dengan , adalah graph sederhana yang himpunan titiknya sama dengan himpunan titik G dan dua titik u dan v di berhubungan langsung jika dan hanya jika di G titik u dan v tidak berhubungan langsung.

11. Isomorfik

Dua graph G dan H dikatakan isomorfik ditulis , jika:

(i) Terdapat korespondensi satu-satu antara V(G) dan E(G),

(ii) Banyaknya sisi yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang menghubungkan dua titik di H yang korespondensi dengan titik u dan titik v.

Graph G1 isomorfik dengan graph G2, sedangkan graph G1 tidak isomorfik dengan graph G3.

Sumber : http://noviarni23gmailcom.blogspot.com/2010/02/tugas-kuliah-semester-ii.html#!/2010/02/tugas-kuliah-semester-ii.html

Graph

Sebuah graph G berisikan dua himpunan yaitu himpunan berhingga tak kosong V(G) dari obyek-obyek yang disebut titik (vertex) dan himpunan berhingga (mungkin kosong) E(G) yang elemen-elemennya disebut sisi (edge) sedemikian hingga setiap elemen e dalam E(G) merupakan pasangan tak berurutan dari titik-titik di V(G). Himpunan V(G) disebut himpunan titik G, dan himpunan E(G) disebut himpunan sisi G.

Sebuah graph G dapat dipresentasikan dalam bentuk diagram (gambar) dimana setiap titik G digambarkan dengan sebuh noktah dan setiap sisi yang menghubungkan dua titik di G digambarkan dengan sebuah kurva sederhana (ruas garis) dengan titik-titik akhir di kedua titik tersebut.

Sebuah sisi graph yang menghubungkan sebuah titik dengan dirinya sendiri disebut gelung (loop). Jika terdapat lebih dari satu sisi yang menghubungkan dua titik u dan v pada suatu graph, maka sisi-sisi tersebut disebut sisi-rangkap/sisi-ganda (multiple-edges).

C. Jenis-jenis Graph

1. Graph sederhana

Graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung disebut graph sederhana.

2. Graph tidak sederhana

a. Graph rangkap

Sebuah graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi-graph).

b. Graph semu

Sebuah graph yang memilki sisi rangkap dan memiliki gelung disebut graph semu (pseudograph).

3. Graph komplit

Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi.

Sebuah graph lengkap sering juga disebut sebagai graph universal. Kerena tiap titik dalam grap lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graph lengkap G dengan n titik adalah n-1. Dengan demikian, banyaknya sisi dalam graph lengkap G adalah .

4. Graph bagian (subgraph)

Sebuah graph H disebut graph bagian (subgraph) dari graph G

5. Graph teratur

Sebuah graph disebut graph teratur jika semua titiknya berderajat sama. Misal graph teratur berderajat tiga.

6. Graph lingkaran

Graph sederhana yang setiap titiknya berderajat dua disebut graph lingkaran. Graph lingkaran dengan n titik dilambangkan dengan Cn. Graph lingkaran ini disebut juga graph teratur berderajat dua.

7. Graph kosong atau graph nol

Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn. Graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Misal graph kosong dengan tiga titik (N3).

8. Graph bipartisi

Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Kita notasikan (X,Y) bipartisi dari G.

Apabila G sederhana dan bipartisi dengan partisi (X,Y) sedemikian sehingga setiap titik di X berhubungan langsung dengan setiap titik di Y, maka G disebut graf bipartisi lengkap, dinotasikan dengan Km,n dengan m dan n adalah banyaknya titik dikedua partisi tersebut.

9. Graph berbobot

Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga.

Sumber : http://noviarni23gmailcom.blogspot.com/2010/02/tugas-kuliah-semester-ii.html#!/2010/02/tugas-kuliah-semester-ii.html