Senin, 08 Oktober 2012

MATEMATIKA DISTKRIT



TUGAS
MATEMATIKA DISTKRIT



OLEH:
NAMA
:
JIBRAEL PADAMAI
NIM
:
1001030066
SEMESTER
:
V
PRODI
:
PEND. MATEMATIKA

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS NUSA CENDANA
KUPANG
2012









METODE PEMBUKTIAN

Definisi memainkan peranan penting di dalam matematika. Topik-topik baru matematika selalu diawali dengan membuat definisi baru. Sebagai contoh, teori fungsi kompleks diawali dengan mendefinisikan bilangan imajiner i, yaitu i2 = -1. Berangkat dari definisi dihasilkan sejumlah teorema beserta akibat-akibatnya. Teorema-teorema inilah yang perlu dibuktikan. Pada kasus sederhana, kadangkala teorema pada suatu buku ditetapkan sebagai definisi pada buku yang lain, begitu juga sebaliknya. Selanjutnya, untuk memahami materi selanjutnya dibutuhkan prasyarat pengetahuan logika matematika.

1.  Bukti langsung

Bukti langsung ini biasanya diterapkan untuk membuktikan teorema yang berbentuk implikasi pq. Di sini p sebagai hipotesis digunakan sebagai fakta yang diketahui atau sebagai asumsi. Selanjutnya, dengan menggunakan p kita harus menunjukkan berlaku q. Secara logika pembuktian langsung ini ekuivalen dengan membuktikan bahwa pernyataan pq benar dimana diketahui p benar.

Contoh  Buktikan, jika x bilangan ganjil maka x2 bilangan ganjil.
Bukti. Diketahui x ganjil, jadi dapat ditulis sebagai x = 2n - 1 untuk suatu bilangan
bulat n. Selanjutnya,
                                   x2 = (2n - 1)2 = 4n2 + 4n + 1 = 2 (2n2 + 2) +1 = 2m + 1:
 

                                                                                             m    
Karena m merupakan bilangan bulat maka disimpulkan x2 ganjil.

2.  Bukti taklangsung

Kita tahu bahwa nilai kebenaran suatu implikasi pq ekuivalen dengan nilai kebenaran kontraposisinya qp. Jadi pekerjaan membuktikan kebenaran pernyataan implikasi dibuktikan lewat kontraposisinya.

Contoh  Buktikan, jika x2 bilangan ganjil maka x bilangan ganjil.
Bukti. Pernyataan ini sangat sulit dibuktikan secara langsung. Mari kita coba saja. Karena x2 ganjil maka dapat ditulis x = 2m + 1 untuk suatu bilangan asli m. Selanjutnya x =  tidak dapat disimpulkan apakah ia ganjil atau tidak. Sehingga bukti langsung tidak dapat digunakan. Kontraposisi dari pernyataan ini adalah

”Jika x genap maka x2 genap”.

Selanjutnya diterapkan bukti langsung pada kontraposisinya. Diketahui x genap, jadi
dapat ditulis x = 2n untuk suatu bilangan bulat n. Selanjutnya,
x2 = (2n)2 = 2 (2n2) = 2m
 

                                     m
yang merupakan bilangan genap.
3.   Bukti kosong

Bila hipotesis p pada implikasi pq sudah bernilai salah maka implikasi pq selalu benar apapun nilai kebenaran dari q. Jadi jika kita dapat menunjukkan bahwa p salah maka kita telah berhasil membuktikan kebenaran pq.

Contoh  Didalam teori himpunan kita mengenal definisi berikut :

Diberikan dua himpunan A dan B. Himpunan A dikatakan himpunan bagian dari B, ditulis AB jika pernyataan berikut dipenuhi : ”jika x A maka xB”. Suatu himpunan dikatakan himpunan kosong jika ia tidak mempunyai anggota.

Buktikan, himpunan kosong merupakan himpunan bagian dari himpunan apapun.

Bukti. Misalkan A =  suatu himpunan kosong dan B himpunan sebarang. Kita akan tunjukkan bahwa pernyataan ”jika x A maka xB” bernilai benar. Karena A himpunan kosong maka pernyataan p yaitu x 2 A selalu bernilai salah karena tidak mungkin ada x yang menjadi anggota himpunan kosong. Karena p salah maka terbuktilah kebenaran pernyataan ”jika xA maka xB”, yaitu AB. Karena B himpunan sebarang maka bukti selesai.


Contoh soal Metode pembuktian langsung
Pembuktian bahwa jumlah 2 bilangan genap adalah genap
Penyelesaian
Pembuktian akan dilakukan secara umum, yaitu dengan mengambil sembaran 2 bilangan genap dan buktikan bahwa jumlah kedua bilangan tersebut adalah genap. Sembarang di sini berarti kita tidak boleh mengambil bilangan genap tertentu, misal 4 dan 10. Akan tetapi kita harus menggunakan 2 variabel untuk menyatakan bahwa pengambilan tersebut dilakukan secara sembarang.

Bukti
Ambil sembarang 2 bilangan genap, misal m dan n.
Akan dibuktikan bahwa (m+n) juga bilangan genap.
Oleh karena a dan b adalah bilangan-bilangan genap, maka   dan   untuk bilangan-bilangan bulat r dan s sehingga
m + n = 2r + 2s
          = 2 (r+s)              (sifat distributif)

Misal k = r + s

Oleh karena r dan s adalah bilangan-bilangan bulat, maka k adalah bilangan bulat juga sehingga m + n = 2k untuk suatu bilangan bulat k.
Menurut defenisi bilangan genap, (m+n) adalah bilangan genap karena merupakan hasil kali 2 bilangan bulat.

Terbukti bahwa jumlah 2 bilangan genap adalah bilangan genap juga.

Relasi, dalam  ”MATEMATIKA” adalah hubungan antara dua buah elemen himpunan. Hubungan ini bersifat abstrak, dan tidak perlu memiliki arti apapun baik secara konkrit maupun secara matematis. Relasi biner R antara A dan B adalah himpunan bagian dari A x B. Himpunan A disebut daerah asal (domain) dari R dan himpunan B disebut daerah hasil (range) dari R. Relasi pada himpunan A adalah relasi dari A x A.

Relasi rekursif sering juga disebut relasi berulang . Relasi ini mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang dikaitkan dengan suku-suku sebelumnya . Untuk mendefinisikan sebuah barisan, relasi berulang memerlukan nilai awal yang sudah ditentukan. Secara formal relasi berulang ini didefinisikan sebagai berikut:
Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1. Syarat awal untuk barisan a0, a1, a2, . . . adalah nilai nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

Contohnya:
Barisan 3, 7 , 11, 15, . . . didefinisikan dengan relasi berulang an = an-1 + 4 untuk n ≥ 1 dengan syarat awal a0 = 3.
Contoh 2
Carilah relasi berulang dengan syarat awal dari barisan 1, 1, 2, 4, 16, 128, 4096, . . .
Penyelesaian
Bentuk rumusan setiap suku dengan menggunakan suku sebelumnya
1 = 1
1 = 1 X 1
2 = 2 X 1 X 1
4 = 2 X 2 X 1
16 = 2 X 4 X 2
128 = 2 X 16 X 4
4096 = 2 X 128 X 16 X 4
Dengan demikian relasi yang berulang yang diperoleh adalah an = 2 X an-1 X 2 X an-2 untuk n≥2
Dengan syarat awal a0 = 1 dan a1 = 1
Relasi rekursif sering juga disebut relasi berulang . relasi ini mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang dikaitkan dengan suku-suku sebelumnya. Untuk mendefinisikan sebuah barisan, relasi berulang memerlukan nilai awal yang sudah ditentukan.

Secara formal relasi berulang ini didefinisikan sebagai berikut:
Definisi sebuah relasi berulang untuk barisan a0, a1, a2, . . . merupakan sebuah persamaan yng mengkaitkan an dengan 0, a1, a2, . . . , an-1. Syarat awal untuk barisan a0, a1, a2, . . .
adalah nilai nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

Sebuah relasi rekurensi linier berkoefisien konstan dapat dinyatakan dalam bentuk  C0 an + C1 an-1 + … + Ck an-k = f(n). Bila nilai  f(n) = 0, maka diperoleh relasi rekurensi yang memenuhi
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0.
Relasi rekurensi demikian disebut dengan relasi rekurensi homogen dan solusi dari relasi rekurensi homogen ini dinamakan solusi homogen atau jawab homogen.
Dalam usaha mencari solusi dari sebuah relasi rekurensi perlu dicari dua macam solusi, yaitu :
1.      Solusi homogen (jawab homogen) yang diperoleh dari relasi rekurensi linier dengan mengambil harga f(n) = 0.
2.      Solusi khusus/partikuler (jawab khusus) yang memenuhi relasi rekurensi sebenarnya.

Solusi homogen dari sebuah relasi rekurensi linier dapat dicari dengan mengambil harga  f(n) = 0. Solusi homogen dari sebuah persamaan diferensial linier dengan koefisien konstan dinyatakan dalam bentuk  Aan , dimana a adalah akar karakteristik  dan A adalah konstanta yang harganya akan ditentukan kemudian untuk memenuhi syarat batas yang diberikan. Dengan substitusi bentuk Aan  kepada  an   pada persamaan homogen   
C0 an + C1 an-1 + C2 an-2 + … + Ck an-k = 0 , maka diperoleh
C0 Aan   + C1 Aan-1 + C2 Aan-2 + … + Ck Aan-k = 0.
Dengan penyederhanaan pada persamaan tersebut, maka diperoleh
C0 an   + C1 an-1 + C2 an-2 + … + Ck an-k = 0
Persamaan ini merupakan persamaan karakteristik dari persamaan diferensial yang diberikan.  Apabila akar karakteristik dari persamaan karakteristik ini, maka Aan akan memenuhi persamaan homogen. Jadi, solusi homogen yang dicari akan berbentuk Aan.Bila persamaan karakteristik memiliki sebanyak  k akar karakteristik berbeda   (a¹ a2 ¹ … ¹ ak) , maka solusi homogen dari relasi rekurensi yang dimaksud dinyatakan dalam bentuk
an(h) = A1 a1n + Aa2n + … + Ak akn
dimana  ai  adalah akar karakteristik dari persamaan karakeristik yang diperoleh, sedangkan  Ai  adalah konstanta yang akan dicari untuk memenuhi kondisi batas yang ditentukan.

















FUNGSI PEMBANGKIT



1.      Fungsi pembangkit satu peubah
Definisi: misal x adalah satu peubah acak dengan distribusi peluang P ( x = k ) =  ; k = 1, 2, 3, ....  dan  = 1
2.      Fungsi pembangkit dua peubah
Misalkan x1 dan x2 adalah dua peubah acak dengan distribusi peluang :
P ( x1 = k1 , x2 = k2 ) = pk1 k2,  pk1 , pk2 = 1, 2, 3, ......
Dan      = 1, maka fungsi pembangkit dari peubah acak x1 dan x2 didefinisikan:
G (s1, s2)  =    

Fungsi pembangkit terdiri dari beberapa deret kuasa yaitu fungsi pembangkit biasa dan fungsi pembangkit eksponensial.
Fungsi pembangkit (generating function)  dari sebuah fungsi numerik an=(a0, a1, a2,., ak, … )
adalah sebuah deret tak hingga  
barisan  yang kadang-kadang disebut sebagai Fungsi Pembangkit bebas dari barisan  ini yang membedakannya dari tipe Fungsi Pembangkit lainnya untuk barisan ini.
Dapat didefinisikan untuk barisan bilangan real terbatas dengan memperluas barisan terbatas (a0, a1, a2,., ak, … )  ke dalam barisan tak terbatas dengan aturan   dan selanjutnya. Fungsi Pembangkit G(x) pada barisan
tak hingga merupakan polinomial dengan n degree, yaitu

Contoh soal
Diketahui suatu fungsi ak = 3k , .
Dicari deretnya dengan cara :
ak = 3k , .
untuk k = 0 diperoleh 30 = 1,
untuk k = 1 diperoleh 31 = 3,
untuk k = 2 diperoleh 32 = 9,
untuk k = 3 diperoleh 33 = 27, dst
sehingga diperoleh barisan {} = (1,3,9,27,…)
Sehingga dapat diperoleh fungsi pembangkit dari fungsi ak tersebut adalah
G(x) = 1 + 3 x + 9 x2 + 27 x3 + … 3k xk + …

Diperlukannya kontruksi dengan fungsi pembangkit untuk barisan
Fibonacci, sebagai berikut :
G(x) = 1 + 3 x + 32 x2 + 33 x3 + … 3k xk + … (a)
3xG(x) = 3 x + 32 x2 + 33 x3 + … 3k xk + … (b)
Dari persamaan (a) dikurangi persamaan (b), diperoleh : (1-3x) G(x) = 1
dibentuk ke dalam bentuk tertutup dapat ditulis sebagai G(x) =


TEORI GRAF
Secara sederhana, suatu graf merupakan suatu koleksi titik-titik (vertices), bersama-sama dengan beberapa sisi (edges) yang menghubungkan beberapa titik tersebut.
Setiap garis berhubungan dengan satu atau dua titik. Titik-titik tersebut dinamakan Titik Ujung. Garis yang hanya berhubungan dengan satu titik ujung disebut Loop. Dua garis berbeda yang menghubungkan titik yang sama disebut Garis Paralel. Dua titik dikatakan berhubungan (adjacent) jika ada garis yang menghubungkan keduanya. Titik yang tidak mempunyai garis yang berhubungan dengannya disebut Titik Terasing (Isolating Point). Graf yang tidak mempunyai titik (sehingga tidak mempunyai garis) disebut Graf Kosong. Jika semua garisnya berarah maka graf-nya disebut Graf Berarah (Directed Graph, atau sering disingkat Digraph). Jika semua garisnya tidak berarah, maka graf-nya disebut Graf Tak Berarah (Undirected Graph). Dalam materi ini, jika hanya disebutkan graf saja, maka yang dimaksud adalah graf tak berarah.
Kadang-kadang suatu graf dinyatakan dengan gambar. Gambar suatu graf G terdiri dari himpunan titik-tilik V(G), himpunan garis-garis E(G) yang menghubungkan titik-titik tersebut (beserta arah garis pada graf berarah), dan label pada garisnya (jika ada). Panjang garis, kelengkungan garis, dan letak titik tidak berpengaruh dalam suatu graf.

Contoh;

Ada 7 kota (A,...,G) yang beberapa di antaranya dapat dihubungkan secara langsung dengan jalan darat. Hubungan-hubungan langsung yang dapat dilakukan adalah sebagai berikut:
 A dengan B dan D
  B dengan D
            C dengan B
            E dengan F
Buatlah graf yang menunjukkan keadaan transportasi di 7 kota tersebut.
Penyelesaian ;
Misalkan kota-kota dianggap sebagai titik-titik. Dua titik/kota dihubungkan dengan garis bila dan hanya bila ada jalan yang menghubungkan langsung kedua kota tersebut. Dengan demikian, keadaan transportasi di 7 kota dapat dinyatakan dalam Gambar berikut ini






Dalam graf tersebut e1 berhubungan dengan titik A dan B (keduanya disebut titik ujung e1). Titik A dan B dikatakan berhubungan, sedangkan titik A dan C tidak berhubungan karena tidak ada garis yang menghubungkannya secara langsung.
Titik G adalah titik terasing karena tidak ada garis yang berhubungan dengan G. Dalam interpretasinya, kota G merupakan kota yang terasing karena tidak dapat dikunjungi dari kota-kota lain dengan jalan darat.

A.    Graf Tak Berarah
1.      Graf Sederhana adalah graf yang tidak memiliki Loop ataupun Garis Paralel.
2.      Graf Lengkap dengan n titik (simbol Kn) adalah graf sederhana dengan n titik di mana setiap 2 titik yang berbeda selalu dihubungkan dengan suatu garis.
3.      Graf Bipartite adalah graf G yang himpunan. Titiknya V(G) dapat dibagi menjadi 2 himpunan yaitu Va dan Vb. Setiap garis dalam G menghubungkan titik di Va dengan titik di Vb. Semua titik dalam Va atau Vb tidak saling berhubungan. Apabila setiap titik di Va berhubungan dengan setiap titik di Vb maka disebut Graf Bipartite Lengkap
4.      Komplemen Graf       
Komplemen suatu graf G (simbol    ) dengan n titik adalah suatu graf dengan :
a.       Titik-titik      sama dengan titik-titik G.
b.      Garis-garis       adalah komplemen garis-garis G terhadap Graf Lengkapnya (Kn)
Titik-titik yang dihubungkan dengan garis pada G menjadi tidak terhubung dalam
Sebaliknya, tiitik-titik yang tidak terhubung pada G menjadi terhubung dalam
5.      Sub Graf
Misalkan G adalah graf. Graf H dikatakan subgraf dari G bila dan hanya bila :      
1.      V(H) Í V(G)
2.      E(H) Í E(G)
3.      Setiap garis dalam H memiliki titik ujung yang sama dengan garis tersebut dalam G
6.      Derajat
Misalkan titik v adalah suatu titik dalam graf G. Derajat titik v (simbol d(v)) adalah jumlah garis yang berhubungan dengan titik v dan garis suatu loop dihitung dua kali. Derajat total suatu graf G adalah jumlah derajat semua titik dalam G.
a.       Derajat total suatu graf selalu genap.
b.      Dalam sembarang graf jumlah titik yang berderajat ganjil selalu genap.
7.      Path dan Sirkuit
Misalkan G adalah suatu graf, v dan w adalah 2 titik di dalam G.
a.       Walk  dari titik v0 ke titik vn adalah barisan titik-titik berhubungan dan garis secara berselang-seling diawali dari titik v0 dan diakhiri pada titik vn.
b.      Path  dari titik v0 ke titik vn adalah walk  dari titik v0 ke titik vn yang semua garisnya berbeda.
c.       Panjang walk atau path = jumlah garis yang dilalui
d.      Path sederhana dari titik v0 ke titik vn adalah path dari titik v0 ke titik vn yang semua titiknya berbeda.
e.       Sirkuit adalah path  yang dimulai dan diakhiri pada titik yang sama.
f.       Sirkuit sederhana adalah sirkuit semua titiknya berbeda kecuali untuk titik awal dan titik akhir.
8.      Sirkuit Euler adalah sirkuit di mana setiap titik dalam  graf G muncul paling sedikit satu kali dan setiap garis muncul tepat satu kali.
Graf G memiliki Sirkuit Euler bila dan hanya bila G adalah graf yang terhubung dan semua titik dalam G mempunyai derajat genap.
9.      Graf Terhubung dan Tidak Terhubung
Misalkan G adalah suatu graf
a.       2 titik dalam G ,v dan w terhubung bila ada walk dari v ke w.
b.      Graf G dikatakan
ü  Terhubung ó setiap 2 titik dalam G terhubung.
ü  Tidak terhubung ó ada 2 titik dalam G yang tidak terhubung.

DAFTAR PUSTAKA
1.      Jong Je Siang. 2006. Matematika Distrit Aplikasinya Ilmu Komputer, penerbit Andi; Yogyakarta.
2.      Suryadi H. S., "Pengantar Struktur Diskrit", Jakarta : Universitas Gunadarma, 1994.
3.      Munir, R. 2003. Matematika Diskrit. Bandung. Informatika.
4.      www.google.com//teorigraf.doc
5.      Sunni, Ismail. “Fungsi Pembangkit”,Prodi TI,ITB,ismailsunni@yahoo.co.id
6.      http://www.informatika.org/~rinaldi/Matdis/2008-2009/strukdis08-09.htm.