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 (a1 ¹ a2 ¹ … ¹ ak) ,
maka solusi homogen dari relasi rekurensi yang dimaksud dinyatakan dalam bentuk
an(h) =
A1 a1n + A2 a2n +
… + 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.