Matematika Diskrit
Pohon Berakar (Rooted Tree)
• Pohon berakar adalah pohon yang sebuah simpulnya diperlakukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.
• Akar mempunyai derajat masuk nol dan simpul-simpul lainnya berderajat masuk sama dengan satu.
• Daun atau simpul terminal adalah simpul yang mempunyai derajat keluar sama dengan nol.
• Simpul dalam atau simpul cabang adalah simpul yang mempunyai derajat keluar tidak sama dengan nol.
Terminologi pada Pohon Berakar
• Child atau children (Anak) dan parent (orangtua)
• Path (lintasan)
• Descendant (Keturunan) dan ancestor (leluhur)
• Sibling (saudara kandung)
• Subtree (subpohon)
• Degree (derajat)
• Leaf (daun)
• Internal nodes (simpul dalam)
• Level (tingkat)
• Height (tinggi) atau depth (kedalaman)
Notasi Prefix,Infix, Dan Postfix
Dalam struktur data yang kita pelajari secara umum ada 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika,yaitu Prefix,Infix,dan postfix.Dan untuk mengetahui notasi-notasi yang diatas itu,sebelumnya kita harus mengenal dan mengetahui indikator yang ada di notasi itu tersebut.
Notasi ini terbentuk dari Operand dan Operator.
Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses.
contohnya:
A+B*C
2 + 5 * 3
Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.
+,* adalah Operator.
Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:
-( ) (Kurung).
- ^ (Pangkat).
- * / (Perkalian / Pembagian).
- + - (Penjumlahan / Pengurangan).
Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix yang seperti kita ketahui di atas:
1.Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.
contoh: A + B * C (infix).
maka notasi prefixnya adalah: +A*BC.
Pemecahannya:
A+B*C
Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.
Sehingga hasil sementara dari notasi prefix adalah:
A+*BC
Selanjutnya mencari prefix untuk operator yang berikutnya yaitu +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi :
+A*BC.
2.Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
Contoh :
- A + B * C
- (A + B) * C
- A - (B + C) * D ^ E
3.Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.
Pemecahannya:
A + B * C
Diketahui ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah * kemudian +.
Tanda * diapit oleh kedua operand yaitu B dan C yaitu B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*
Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2 operand, yaitu : A dan BC* gabungkan operand tersebut,sehingga menjadi ABC*,lalu pindahkan operator + kebelakang operand ABC*.
Sehingga hasil akhir menjadi : ABC*+.
contoh Notasi Huruf :
Contoh Notasi Angka:
Kamis, 07 Juni 2018
Rabu, 30 Mei 2018
POHON PADA MATEMATIKA DISKRIT
Definisi Pohon dan Hutan
Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.
Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative pemecahan.
Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :
~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).
~ Graph tersebut terhubung .
Contoh :
Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.
Ciri – ciri hutan :
banyaknya titik = n
banyaknya pohon = k
banyaknya rusuk = n-k
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.
2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.
5. Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidakmengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuatsatu sirkuit.
Spanning Tree
Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut.
Contoh :
T1, T2, T3, T4 merupakan spanning tree dari G
Minimal spanning tree dari labeled graph Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.
Contoh :
2.3 Rooted Tree ( Pohon Berakar )
Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :
1. Akar dinyatakan dengan lingkar-aN
2. Daun
3. Cabang
4. Tinggi / level / dept / dalamnya suatu vertex
Contoh :
Sifat utama Pohon Berakar
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling
5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :
2 (N) - 1
8. Banyaknya Simpul untuk setiap Level I adalah
N
∑ 2 (I -1)
(I-1)
Pohon Berurut Berakar (Ordered Rooted Tree) adalah pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.
Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.
Gambar pohon berurut berakar di atas disebut Lexicographic order.
Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic.
Contoh Soal Pohon
1. Spanning Tree
Perhatikan gambar suatu graf berikut :
Penyelesaian dengan Spanning Tree adalah
2. Rooted Tree
Diketahui suatu bentuk Pohon Berakar T sebagai berikut :
Pohon diatas mempunyai :
a. Simpul sebanyak = 8 dan edge = n - 1 = 8 – 1 = 7
b. Root pada Pohon T diatas adalah Simpul P
c. Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W
d. Level (tingkatan) Pohon = 4 yaitu :
Level 1 = Simpul P
Level 2 = Simpul Q dan T
Level 3 = Simpul R, S dan U
Level 4 = Simpul V dan W
e. Ketinggian atau kedalaman = jumlah level = 4
f. Weight atau berat atau bobot = jumlah daun = 4
Dalam gambar Pohon T diatas dapat dibentuk 2 buah hutan (forest), bila simpul P dihilangkan, yaitu :
Hutan 1 : Q,R,S
Hutan 2 : T,U,V,W
g. Banyaknya Simpul Maksimum yang dapat terbentuk sampai Level 4 (bila simpul pada pohon dianggap penuh) adalah
2(N) – 1
2(4) – 1 = 16 – 1 = 15
h. Banyaknya Simpul maksimum untuk setiap Level I(bila simpul pada pohondianggap penuh) adalah :
Maksimum Simpul pada level 2 = 2 ( I – 1)=
2 ( 2 - 1 ) = 2
Maksimum Simpul pada level 3 = 2 (3-1)= 4
Maksimum Simpul pada level 4 = 2 (4-1)= 2
3. Terdapat sebuah permainan sederhana sebagai berikut: Seseorang memikirkan
sebuah angka antara 1 sampai 31. Anda harus menebak angka dengan benar.
Anda bertanya, ”Apakah angkanya x?” kemudian orang tersebut menjawab
dengan ”Ya”,”Lebih kecil dari x”, atau ”Lebih besar dari x”. Tunjukkan bahwa Anda
mampu menebak angka tersebut tidak lebih dari 5 kali tebakan.
Penyelesaian :
Petunjuknya adalah dengan selalu menebak angka yang menjadi titik tengah dari
jangkauan angka yang tersisa. Kemudian, jika tebakan salah akan mengurangi
separuh angka, hingga akhirnya akan tersisa satu angka. Gambar 11.6
memperlihatkan bagaimana proses tebakan berlangsung,mulai dari 16.
Setiap verteks adalah titik yang memutuskan nilai benar atau salah, jika salah maka nilai
tersebut berada di salah satu subtree dari dua subtree. Subtree pada sisi kiri berisi
nilai yang lebih kecil, dan subtree pada sisi kanan berisi nilai yang lebih besar.
Tree yang terbentuk hanya empat level, maka diperlukan tidak lebih dari 5 kali
tebakan.
Definisi Pohon dan Hutan
Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia.Silsilah keluarga biasanya juga digambarkan pasa bentuk pohon.
Pohon (tree) adalah merupakan graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative pemecahan.
Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :
~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).
~ Graph tersebut terhubung .
Contoh :
Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.
Ciri – ciri hutan :
banyaknya titik = n
banyaknya pohon = k
banyaknya rusuk = n-k
Berikut adalah beberapa sifat pohon :
1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.
2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.
3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.
4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.
5. Misalkan G adalah graf sederhana dengan jumlah simpul n,jika G tidakmengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuatsatu sirkuit.
Spanning Tree
Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf tersebut.
Contoh :
T1, T2, T3, T4 merupakan spanning tree dari G
Minimal spanning tree dari labeled graph Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.
Contoh :
2.3 Rooted Tree ( Pohon Berakar )
Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :
1. Akar dinyatakan dengan lingkar-aN
2. Daun
3. Cabang
4. Tinggi / level / dept / dalamnya suatu vertex
Contoh :
Sifat utama Pohon Berakar
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling
5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :
2 (N) - 1
8. Banyaknya Simpul untuk setiap Level I adalah
N
∑ 2 (I -1)
(I-1)
Pohon Berurut Berakar (Ordered Rooted Tree) adalah pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.
Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.
Gambar pohon berurut berakar di atas disebut Lexicographic order.
Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic.
Contoh Soal Pohon
1. Spanning Tree
Perhatikan gambar suatu graf berikut :
Penyelesaian dengan Spanning Tree adalah
2. Rooted Tree
Diketahui suatu bentuk Pohon Berakar T sebagai berikut :
Pohon diatas mempunyai :
a. Simpul sebanyak = 8 dan edge = n - 1 = 8 – 1 = 7
b. Root pada Pohon T diatas adalah Simpul P
c. Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W
d. Level (tingkatan) Pohon = 4 yaitu :
Level 1 = Simpul P
Level 2 = Simpul Q dan T
Level 3 = Simpul R, S dan U
Level 4 = Simpul V dan W
e. Ketinggian atau kedalaman = jumlah level = 4
f. Weight atau berat atau bobot = jumlah daun = 4
Dalam gambar Pohon T diatas dapat dibentuk 2 buah hutan (forest), bila simpul P dihilangkan, yaitu :
Hutan 1 : Q,R,S
Hutan 2 : T,U,V,W
g. Banyaknya Simpul Maksimum yang dapat terbentuk sampai Level 4 (bila simpul pada pohon dianggap penuh) adalah
2(N) – 1
2(4) – 1 = 16 – 1 = 15
h. Banyaknya Simpul maksimum untuk setiap Level I(bila simpul pada pohondianggap penuh) adalah :
Maksimum Simpul pada level 2 = 2 ( I – 1)=
2 ( 2 - 1 ) = 2
Maksimum Simpul pada level 3 = 2 (3-1)= 4
Maksimum Simpul pada level 4 = 2 (4-1)= 2
3. Terdapat sebuah permainan sederhana sebagai berikut: Seseorang memikirkan
sebuah angka antara 1 sampai 31. Anda harus menebak angka dengan benar.
Anda bertanya, ”Apakah angkanya x?” kemudian orang tersebut menjawab
dengan ”Ya”,”Lebih kecil dari x”, atau ”Lebih besar dari x”. Tunjukkan bahwa Anda
mampu menebak angka tersebut tidak lebih dari 5 kali tebakan.
Penyelesaian :
Petunjuknya adalah dengan selalu menebak angka yang menjadi titik tengah dari
jangkauan angka yang tersisa. Kemudian, jika tebakan salah akan mengurangi
separuh angka, hingga akhirnya akan tersisa satu angka. Gambar 11.6
memperlihatkan bagaimana proses tebakan berlangsung,mulai dari 16.
Setiap verteks adalah titik yang memutuskan nilai benar atau salah, jika salah maka nilai
tersebut berada di salah satu subtree dari dua subtree. Subtree pada sisi kiri berisi
nilai yang lebih kecil, dan subtree pada sisi kanan berisi nilai yang lebih besar.
Tree yang terbentuk hanya empat level, maka diperlukan tidak lebih dari 5 kali
tebakan.
Jumat, 25 Mei 2018
MATEMATIKA DISKRIT
PEMBAHASAN
A. Kerangka Teoritis
1. Sejarah Graf
Tulisan pertama tentang teori graf adalah karya Leonard Euler pada tahun 1976. Tulisan tersebut menyajukan sebuah teori umum yang menyertakan sebuahh solusi yang sekarang disebut masalah jembatan Konisberg.
Dua pulau terhampar disungai Pregel yang terletak dikota Konisberg (sekarang kuliningrat di Rusia) saling terhubung oleh jembata-jembatan, seperti yang di perlihatkan pada gambar di bawah ini.
(a) Konigsberg in 1736
(b)Euler’s graphical representation
Gambar 2.1 dua pulau dan tujuh jembatan dikota Konisberg
Masalahnya pada gambar (a) adalah untuk memulai dari sembarang lokasi A,B,C dan D menyeberangi di setiap jembatan satu kali kemudian kembali lagi pada tempat semula. Orang-orang konisberg menuliskan kepada ahli matematika swiss, L.Euler mengenai peryanyaan ini. Euler membuktikan pada tahun 1736 bahwa perjalanan seperti itu adalah suatu yang tidak mungkin dilakukan.
Dia menempatkan kembali pulau-pulau dan dua sisi suangai dengan titik-titik, dan jembatan-jembatan dengan kurva seperti pada gambar (b). Konfigurasi jembatan dapat dimodelkan sebagai sebuah graf seperti yang di perlihatkan digambar (b). vertex-verteks mewakili lokasi dan rusuk-rusuk mewakili jembatan. Masalah jembatan kosisberg sekarang di sederhanakan untuk mencari di sebuah siklus dalam graf dari gambar (b) yang menyertakan semua rusuk dan semua vertex. Untuk menghormati Euler, sebuah siklus dalam sebuah graf G yang menyertakan semua rusuk dari G di sebut siklus Euler.
2. Konsep Dasar Graf
Menurut Rinaldi Munir (2003:291) dalam bukunya matematika Diskrit Graf G = (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1 , v2 , ... , vn }
E = himpunan sisi (edges) yang menghubungkan sepasang simpul.
= {e1 , e2 , ... , en }
V titak boleh kosong, sedangkan E boleh kosong. Se buah graf di mungkinkan ttidak mempunyai satu buah simpul (vertek) tanpa satu buah pun dinamakan graft rival. Simpul (vertex) pada graf dapat dinomori dengan huruf sepertia,b,c, … dengan bilangn asli 1,2,3 … atau gabungan keduanya. Sedangkan sisi (edge) yang menghubungkan simpul (vertex) dinyatakan pasangan atau dengan lambang e1 , e2 , ... , en
Secara Geometri graf dapat digambarkan sebagai kumpulan simpul (vertek) di dalam bidang yang menghubungkan dengan sekumpulan sisi (edge)
G1 G2 G3
Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu
Contoh 1. Pada Gambar 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6,e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7,e8}
• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda(multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
• Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.
3. Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.
(a) G4 (b) G5
Gambar 3 (a) graf berarah, (b) graf-ganda berarah
Tabel 1 Jenis-jenis graf [ROS99]
Jenis Sisi Sisi ganda dibolehkan? Sisi gelang dibolehkan?
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf-ganda berarah Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah Tidak
Ya
Ya
Tidak
Ya Tidak
Tidak
Ya
Ya
Y
4. Terminologi Graf
G1 G2 G3
Gambar 4. Graf yang digunakan untuk menjelaskan terminologi pada graf
1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan
e bersisian dengan simpul vj , atau
e bersisian dengan simpul vk
Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.
3. Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graf G1: simpul 5 adalah simpul terpencil.
4. Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5. Gambar 5
5. Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graf G1:
d(1) = d(4) = 2
d(2) = d(3) = 3
Tinjau graf G3: d(5) = 0 simpul terpencil
d(4) = 1 simpul anting-anting (pendant vertex)
Tinjau graf G2: d(1) = 3 bersisian dengan sisi ganda
d(2) = 4 bersisian dengan sisi gelang (loop)
Pada graf berarah,
din(v) = derajat-masuk (in-degree)
= jumlah busur yang masuk ke simpul v
dout(v) = derajat-keluar (out-degree)
= jumlah busur yang keluar dari simpul v
G4 G5
Gambar 6
d(v) = din(v) + dout(v)
Tinjau graf G4:
din(1) = 1; dout(1) = 1
din(2) = 1; dout(2) = 3
din(3) = 1; dout(3) = 1
din(4) = 2; dout(3) = 0
Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut.
Dengan kata lain, jika G = (V, E), maka
Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2 jumlah sisi = 2 5
Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2 jumlah sisi = 2 5
Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0 = 8
= 2 jumlah sisi = 2 4
Contoh 2. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya genap
(2 + 3 + 3 + 4 + 4 = 16).
6. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf Gialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1,e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1,vn) adalah sisi-sisi dari graf G.
Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).
Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atausiklus.
Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1memiliki panjang 3.
8. Terhubung (Connected)
Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1ke v2.
G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi danvj dalam himpunan V terdapat lintasan dari vi ke vj.
Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).
Contoh graf tak-terhubung:
Gambar 7: Gambar G tidak terhubung
Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya). Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.
Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, makau dan v dikatakan terhubung lemah (weakly coonected).
Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, Gdisebut graf terhubung lemah
(a) graf berarah terhubung lemah (b) graf berarah terhubung kuat
gambar 8
8. Upagraf (Subgraph) dan Komplemen Upagraf
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 V dan E1 E.
Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2bersisian dengannya.
(a) Graf G1 (b) Sebuah upagraf (c) komplemen dari upagraf (b)
Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
Graf G di bawah ini mempunyai 4 buah komponen.
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.
Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:
9. Upagraf Rentang (Spanning Subgraph)
Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaituG1 mengandung semua simpul dari G).
(a) graf G, (b) upagraf rentang dari G, (c) bukan upagraf rentang dariG
10. Cut-Set
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari Gmenyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.
Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyakcut-set pada sebuah graf terhubung.
Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set,
tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.
(a) (b)
11. Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
5. Representasi Graf
a. Matriks Ketetanggaan (adjacency matrix)
Matrik ketegangan adalah refresetasi graf yang paling umum. Misalkan G= (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan adalah G adalah matriks yang berukuran n x n. bila matriks tersebut di namakan A = [aij], maka aij = {1, jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain angka 0 dan 1, element matrik dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true menyantakan 1). Matriks ketetanggaan di dasarkan pada pngurutan nomor simpul.
Contoh:
(a) (b) (c)
Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetri, sedangkan untuk graf berarah matriks ketetanggannya belum tentu simetri (akan simetri jika berupa graf berarah lengkap). Selain itu diagonal utamanya selalu nol karena tidak ada sisi gelang. Refresentasi dengan matriks ketetanggaan adalah elemen matriksnya dapat diakses langsung melalui indeks. Selain itu, juga dapat di tentukan langsung apakah simpul i dan simpul j bertetangga. Dan derajat tiap simpuli dapat dihitung dari matriks ketetanggaan. Derajat tiap simpul i:
(a) Untuk graf tak-berarah,
d(vi) =
(b) Untuk graf berarah,
din (vj) = jumlah nilai pada kolom j =
dout (vi) = jumlah nilai pada baris i =
untuk graf berbobot, aij menyatakan bobot tiap sisi yang menghubungkan simpul idengan simpul j.
a b c d e
Gambar : graf berbobot dengan graf ketetanggaannya.
Tanda “∞” menyatakan bahwa tidak ada sisi dari simpul i kesimpul i sendiri, sehingga aij tapat di beri nilai tak berhingga.
2. Matriks Bersisian (incidency matrix)
Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalnya G=(V,E) adalah graf dengan n simpul m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut di namakan A = [aij], maka aij = 1, jika simpul i bersisian dengan sisi j maka aij = 0, jika simpul itidak bersisian dengan sisi j
Matriks bersisian dapat di gunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang. Derajat setiap simpul i dapat dihitung dengan menghitung jumlah seluruh elemen pada baris i ( kecuali pada graf yang mengandung gelang) jumlah elemen matriks bersisian adalah mn. Jika tiap elemen memputuhkan ruang memori sebesar p maka ruang memori yang di perlukan seluruhnya adalah pnm.
e1 e2 e3 e4 e5
6. Garaf Berarah
Definisi sebuah graf berarah. Sebuag graf berarah atau digraph G terdiri dari:
1. Sebuah himpunan V= V(G) yang elemen-elemennya di sebut vertex, titik atau node.
2. Suattu koleksi E= E(G) dari pasangan –pasangan vertex terurut yang di sebut busur atau edge. Graf berarah G dikatakan berhingga jika himpunan V dari vertex-verteksnya dan himpunan E dari busurnya (edge berarahnya) behingga.
7. Lintasan Terpendek
Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang di maksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf berbobot yaitu graf yang tiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan graf antara kota, waktu pengiriman pesan, onkos pembangunan dan sebagainya. Kata “terpendek” tidak boleh selalu diartikan secara fisik sebagai minimum, sebab kata terpendek berbeda maknanya bergantung pada tipikal soal yang diberikan untuk diselesaikan.
Namun secara umum terpendendek berarti meminimisasikan bobot pada suatu lintasan graf. Misalkan simpul pada graf merupakan kota sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek disini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A kekota B. dalam makalah ini, bobot yang dimaksud berupa jarak dan waktu kemacetan terjadi. Ada beberapa macam persoalan lintasan terpendek seperti:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path)
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path)
c. Lintasan terpendek dari simpul tertentu kesemua simpul yang lain (single source shourtest path)
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
PEMBAHASAN
A. Kerangka Teoritis
1. Sejarah Graf
Tulisan pertama tentang teori graf adalah karya Leonard Euler pada tahun 1976. Tulisan tersebut menyajukan sebuah teori umum yang menyertakan sebuahh solusi yang sekarang disebut masalah jembatan Konisberg.
Dua pulau terhampar disungai Pregel yang terletak dikota Konisberg (sekarang kuliningrat di Rusia) saling terhubung oleh jembata-jembatan, seperti yang di perlihatkan pada gambar di bawah ini.
(a) Konigsberg in 1736
(b)Euler’s graphical representation
Gambar 2.1 dua pulau dan tujuh jembatan dikota Konisberg
Masalahnya pada gambar (a) adalah untuk memulai dari sembarang lokasi A,B,C dan D menyeberangi di setiap jembatan satu kali kemudian kembali lagi pada tempat semula. Orang-orang konisberg menuliskan kepada ahli matematika swiss, L.Euler mengenai peryanyaan ini. Euler membuktikan pada tahun 1736 bahwa perjalanan seperti itu adalah suatu yang tidak mungkin dilakukan.
Dia menempatkan kembali pulau-pulau dan dua sisi suangai dengan titik-titik, dan jembatan-jembatan dengan kurva seperti pada gambar (b). Konfigurasi jembatan dapat dimodelkan sebagai sebuah graf seperti yang di perlihatkan digambar (b). vertex-verteks mewakili lokasi dan rusuk-rusuk mewakili jembatan. Masalah jembatan kosisberg sekarang di sederhanakan untuk mencari di sebuah siklus dalam graf dari gambar (b) yang menyertakan semua rusuk dan semua vertex. Untuk menghormati Euler, sebuah siklus dalam sebuah graf G yang menyertakan semua rusuk dari G di sebut siklus Euler.
2. Konsep Dasar Graf
Menurut Rinaldi Munir (2003:291) dalam bukunya matematika Diskrit Graf G = (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices)
= { v1 , v2 , ... , vn }
E = himpunan sisi (edges) yang menghubungkan sepasang simpul.
= {e1 , e2 , ... , en }
V titak boleh kosong, sedangkan E boleh kosong. Se buah graf di mungkinkan ttidak mempunyai satu buah simpul (vertek) tanpa satu buah pun dinamakan graft rival. Simpul (vertex) pada graf dapat dinomori dengan huruf sepertia,b,c, … dengan bilangn asli 1,2,3 … atau gabungan keduanya. Sedangkan sisi (edge) yang menghubungkan simpul (vertex) dinyatakan pasangan atau dengan lambang e1 , e2 , ... , en
Secara Geometri graf dapat digambarkan sebagai kumpulan simpul (vertek) di dalam bidang yang menghubungkan dengan sekumpulan sisi (edge)
G1 G2 G3
Gambar 2. (a) graf sederhana, (b) graf ganda, dan (c) graf semu
Contoh 1. Pada Gambar 2, G1 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
G2 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) } = { e1, e2, e3, e4, e5, e6,e7}
G3 adalah graf dengan
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
= { e1, e2, e3, e4, e5, e6, e7,e8}
• Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda(multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3.
• Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.
3. Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua buah graf pada Gambar 3 adalah graf berarah.
(a) G4 (b) G5
Gambar 3 (a) graf berarah, (b) graf-ganda berarah
Tabel 1 Jenis-jenis graf [ROS99]
Jenis Sisi Sisi ganda dibolehkan? Sisi gelang dibolehkan?
Graf sederhana
Graf ganda
Graf semu
Graf berarah
Graf-ganda berarah Tak-berarah
Tak-berarah
Tak-berarah
Bearah
Bearah Tidak
Ya
Ya
Tidak
Ya Tidak
Tidak
Ya
Ya
Y
4. Terminologi Graf
G1 G2 G3
Gambar 4. Graf yang digunakan untuk menjelaskan terminologi pada graf
1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan
e bersisian dengan simpul vj , atau
e bersisian dengan simpul vk
Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.
3. Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graf G1: simpul 5 adalah simpul terpencil.
4. Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5. Gambar 5
5. Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graf G1:
d(1) = d(4) = 2
d(2) = d(3) = 3
Tinjau graf G3: d(5) = 0 simpul terpencil
d(4) = 1 simpul anting-anting (pendant vertex)
Tinjau graf G2: d(1) = 3 bersisian dengan sisi ganda
d(2) = 4 bersisian dengan sisi gelang (loop)
Pada graf berarah,
din(v) = derajat-masuk (in-degree)
= jumlah busur yang masuk ke simpul v
dout(v) = derajat-keluar (out-degree)
= jumlah busur yang keluar dari simpul v
G4 G5
Gambar 6
d(v) = din(v) + dout(v)
Tinjau graf G4:
din(1) = 1; dout(1) = 1
din(2) = 1; dout(2) = 3
din(3) = 1; dout(3) = 1
din(4) = 2; dout(3) = 0
Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut.
Dengan kata lain, jika G = (V, E), maka
Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2 jumlah sisi = 2 5
Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2 jumlah sisi = 2 5
Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0 = 8
= 2 jumlah sisi = 2 4
Contoh 2. Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya genap
(2 + 3 + 3 + 4 + 4 = 16).
6. Lintasan (Path)
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf Gialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1,e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1,vn) adalah sisi-sisi dari graf G.
Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).
Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atausiklus.
Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1memiliki panjang 3.
8. Terhubung (Connected)
Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1ke v2.
G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi danvj dalam himpunan V terdapat lintasan dari vi ke vj.
Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).
Contoh graf tak-terhubung:
Gambar 7: Gambar G tidak terhubung
Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya). Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.
Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, makau dan v dikatakan terhubung lemah (weakly coonected).
Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, Gdisebut graf terhubung lemah
(a) graf berarah terhubung lemah (b) graf berarah terhubung kuat
gambar 8
8. Upagraf (Subgraph) dan Komplemen Upagraf
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 V dan E1 E.
Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2bersisian dengannya.
(a) Graf G1 (b) Sebuah upagraf (c) komplemen dari upagraf (b)
Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
Graf G di bawah ini mempunyai 4 buah komponen.
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.
Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:
9. Upagraf Rentang (Spanning Subgraph)
Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaituG1 mengandung semua simpul dari G).
(a) graf G, (b) upagraf rentang dari G, (c) bukan upagraf rentang dariG
10. Cut-Set
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari Gmenyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.
Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyakcut-set pada sebuah graf terhubung.
Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set,
tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.
(a) (b)
11. Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
5. Representasi Graf
a. Matriks Ketetanggaan (adjacency matrix)
Matrik ketegangan adalah refresetasi graf yang paling umum. Misalkan G= (V,E) adalah graf dengan n simpul, n ≥ 1. Matriks ketetanggaan adalah G adalah matriks yang berukuran n x n. bila matriks tersebut di namakan A = [aij], maka aij = {1, jika simpul i dan j bertetangga, sebaliknya aij = 0 jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain angka 0 dan 1, element matrik dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true menyantakan 1). Matriks ketetanggaan di dasarkan pada pngurutan nomor simpul.
Contoh:
(a) (b) (c)
Matriks ketetanggaan untuk graf sederhana dan tidak berarah selalu simetri, sedangkan untuk graf berarah matriks ketetanggannya belum tentu simetri (akan simetri jika berupa graf berarah lengkap). Selain itu diagonal utamanya selalu nol karena tidak ada sisi gelang. Refresentasi dengan matriks ketetanggaan adalah elemen matriksnya dapat diakses langsung melalui indeks. Selain itu, juga dapat di tentukan langsung apakah simpul i dan simpul j bertetangga. Dan derajat tiap simpuli dapat dihitung dari matriks ketetanggaan. Derajat tiap simpul i:
(a) Untuk graf tak-berarah,
d(vi) =
(b) Untuk graf berarah,
din (vj) = jumlah nilai pada kolom j =
dout (vi) = jumlah nilai pada baris i =
untuk graf berbobot, aij menyatakan bobot tiap sisi yang menghubungkan simpul idengan simpul j.
a b c d e
Gambar : graf berbobot dengan graf ketetanggaannya.
Tanda “∞” menyatakan bahwa tidak ada sisi dari simpul i kesimpul i sendiri, sehingga aij tapat di beri nilai tak berhingga.
2. Matriks Bersisian (incidency matrix)
Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalnya G=(V,E) adalah graf dengan n simpul m buah sisi. Matriks bersisian G adalah matriks dwimatra yang berukuran n × m. baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut di namakan A = [aij], maka aij = 1, jika simpul i bersisian dengan sisi j maka aij = 0, jika simpul itidak bersisian dengan sisi j
Matriks bersisian dapat di gunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang. Derajat setiap simpul i dapat dihitung dengan menghitung jumlah seluruh elemen pada baris i ( kecuali pada graf yang mengandung gelang) jumlah elemen matriks bersisian adalah mn. Jika tiap elemen memputuhkan ruang memori sebesar p maka ruang memori yang di perlukan seluruhnya adalah pnm.
e1 e2 e3 e4 e5
6. Garaf Berarah
Definisi sebuah graf berarah. Sebuag graf berarah atau digraph G terdiri dari:
1. Sebuah himpunan V= V(G) yang elemen-elemennya di sebut vertex, titik atau node.
2. Suattu koleksi E= E(G) dari pasangan –pasangan vertex terurut yang di sebut busur atau edge. Graf berarah G dikatakan berhingga jika himpunan V dari vertex-verteksnya dan himpunan E dari busurnya (edge berarahnya) behingga.
7. Lintasan Terpendek
Lintasan terpendek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang di maksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf berbobot yaitu graf yang tiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan graf antara kota, waktu pengiriman pesan, onkos pembangunan dan sebagainya. Kata “terpendek” tidak boleh selalu diartikan secara fisik sebagai minimum, sebab kata terpendek berbeda maknanya bergantung pada tipikal soal yang diberikan untuk diselesaikan.
Namun secara umum terpendendek berarti meminimisasikan bobot pada suatu lintasan graf. Misalkan simpul pada graf merupakan kota sedangkan sisi menyatakan jalan yang menghubungkan dua buah kota atau rata-rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu lintasan dari kota A ke kota B, maka persoalan lintasan terpendek disini adalah menentukan jarak terpendek atau waktu tersingkat dari kota A kekota B. dalam makalah ini, bobot yang dimaksud berupa jarak dan waktu kemacetan terjadi. Ada beberapa macam persoalan lintasan terpendek seperti:
a. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path)
b. Lintasan terpendek antara semua pasangan simpul (all pairs shortest path)
c. Lintasan terpendek dari simpul tertentu kesemua simpul yang lain (single source shourtest path)
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).
Sabtu, 19 Mei 2018
Matematika Diskrit
Penyederhanaan Fungsi Boolean
Contoh. f(x, y) = x’y + xy’ + y’
disederhanakan menjadi
f(x, y) = x’ + y’
Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:
Secara aljabar
Menggunakan Peta Karnaugh
Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
1. Penyederhanaan Secara Aljabar
Contoh:
f(x, y) = x + x’y
= (x + x’)(x + y)
= 1 × (x + y )
= x + y
= f(x, y, z) = x’y’z + x’yz + xy’
= x’z(y’ + y) + xy’
= x’z + xy’
= f(x, y, z) = xy + x’z + yz = xy + x’z + yz(x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y) = xy + x’z
x y z xy xy + x’z X’z X’yz xyz xy + x’z + xyz + x’yz yz Yz+x’z
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1
1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0
1 1 0 1 1 0 0 0 1 0 0
1 1 1 1 1 0 0 1 1 1 1
2. Peta Karnaugh
a. Peta Karnaugh dengan dua peubah
y
0 1
m0 m1 x 0 x’y’ x’y
m2 m3 1 xy’ xy
b. Peta dengan tiga peubah
yz
00
01
11
10
m0 m1 m3 m2 x 0 x’y’z’ x’y’z x’yz x’yz’
m4 m5 m7 m6 1 xy’z’ xy’z xyz xyz’
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
yz
00
01
11
10
x 0 0 0 0 1
1 0 0 1 1
b. Peta dengan empat peubah
yz
00
01
11
10
m0 m1 m3 m2 wx 00 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’
m4 m5 m7 m6 01 w’xy’z’ w’xy’z w’xyz w’xyz’
m12 m13 m15 m14 11 wxy’z’ wxy’z wxyz wxyz’
m8 m9 m11 m10 10 wx’y’z’ wx’y’z wx’yz wx’yz’
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
w x y z f(w, x, y, z)
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
yz
00
01
11
10
wx 00 0 1 0 1
01 0 0 1 1
11 0 0 0 1
10 0 0 0 0
Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh
1. Pasangan: dua buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 0 0 1 1
10 0 0 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’
Hasil Penyederhanaan: f(w, x, y, z) = wxy
Bukti secara aljabar:
f(w, x, y, z) = wxyz + wxyz’
= wxy(z + z’)
= wxy(1)
= wxy
2. Kuad: empat buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’
Hasil penyederhanaan: f(w, x, y, z) = wx
Bukti secara aljabar:
f(w, x, y, z) = wxy’ + wxy
= wx(z’ + z)
= wx(1)
= wx
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 0 0
Contoh lain:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 0 0
10 1 1 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z
Hasil penyederhanaan: f(w, x, y, z) = wy’
3. Oktet: delapan buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 1 1 1 1
Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ +
wx’y’z’ + wx’y’z + wx’yz + wx’yz’
Hasil penyederhanaan: f(w, x, y, z) = w
Bukti secara aljabar:
f(w, x, y, z) = wy’ + wy
= w(y’ + y)
= w
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 1 1 1 1
Contoh 5.11. Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’.
Jawab:
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
01
11
10
x 0 1
1 1 1 1
Hasil penyederhanaan: f(x, y, z) = yz + xz’
Contoh 5.12. Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin.
yz
00
01
11
10
wx 00 0 1 1 1
01 0 0 0 1
11 1 1 0 1
10 1 1 0 1
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = wy’ + yz’ + w’x’z
Contoh 5.13. Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 1 1 1 1
10 1 1 1 1
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z
Jika penyelesaian Contoh 5.13 adalah seperti di bawah ini:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 1 1 1 1
10 1 1 1 1
maka fungsi Boolean hasil penyederhanaan adalah
f(w, x, y, z) = w + w’xy’z (jumlah literal = 5)
yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z (jumlah literal = 4).
Contoh 5.14. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 1 0 0 1
11 1 0 0 1
10 0 0 0 0
Jawab: f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana
Penyelesaian yang lebih minimal:
yz
00
01
11
10
wx 00 0 0 0 0
01 1 0 0 1
11 1 0 0 1
10 0 0 0 0
f(w, x, y, z) = xz’ ===> lebih sederhana
Contoh 5.15: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 0 1 1 0
10 0 0 1 0
Jawab: f(w, x, y, z) = xy’z + wxz + wyz ® masih belum sederhana.
Penyelesaian yang lebih minimal:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 0 1 1 0
10 0 0 1 0
f(w, x, y, z) = xy’z + wyz ===> lebih sederhana
Contoh 5.16. Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
cd
00
01
11
10
ab 00 0 0 0 0
01 0 0 1 0
11 1 1 1 1
10 0 1 1 1
Jawab: (lihat Peta Karnaugh di atas) f(a, b, c, d) = ab + ad + ac + bcd
Contoh 5.17. Minimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yz
Jawab:
x’z = x’z(y + y’) = x’yz + x’y’z
x’y = x’y(z + z’) = x’yz + x’yz’
yz = yz(x + x’) = xyz + x’yz
f(x, y, z) = x’z + x’y + xy’z + yz
= x’yz + x’y’z + x’yz + x’yz’ + xy’z + xyz + x’yz
= x’yz + x’y’z + x’yz’ + xyz + xy’z
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
01
11
10
x 0 1 1 1
1 1 1
Hasil penyederhanaan: f(x, y, z) = z + x’yz’
Peta Karnaugh untuk lima peubah
000 001 011 010 110 111 101 100
00 m0 m1 m3 m2 m6 m7 m5 m4
01 m8 m9 m11 m10 m14 m15 m13 m12
11 m24 m25 m27 m26 m30 m31 m29 m28
10 m16 m17 m19 m18 m22 m23 m21 m20
Garis pencerminan
Contoh 5.21. (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(v, w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
Jawab:
Peta Karnaugh dari fungsi tersebut adalah:
xyz
000
001
011
010
110
111
101
100
vw 00
1
1
1
1
01
1
1
1
1
11
1
1
1
1
10
1
1
Jadi f(v, w, x, y, z) = wz + v’w’z’ + vy’z
Penyederhanaan Fungsi Boolean
Contoh. f(x, y) = x’y + xy’ + y’
disederhanakan menjadi
f(x, y) = x’ + y’
Penyederhanaan fungsi Boolean dapat dilakukan dengan 3 cara:
Secara aljabar
Menggunakan Peta Karnaugh
Menggunakan metode Quine Mc Cluskey (metode Tabulasi)
1. Penyederhanaan Secara Aljabar
Contoh:
f(x, y) = x + x’y
= (x + x’)(x + y)
= 1 × (x + y )
= x + y
= f(x, y, z) = x’y’z + x’yz + xy’
= x’z(y’ + y) + xy’
= x’z + xy’
= f(x, y, z) = xy + x’z + yz = xy + x’z + yz(x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y) = xy + x’z
x y z xy xy + x’z X’z X’yz xyz xy + x’z + xyz + x’yz yz Yz+x’z
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1
1 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0
1 1 0 1 1 0 0 0 1 0 0
1 1 1 1 1 0 0 1 1 1 1
2. Peta Karnaugh
a. Peta Karnaugh dengan dua peubah
y
0 1
m0 m1 x 0 x’y’ x’y
m2 m3 1 xy’ xy
b. Peta dengan tiga peubah
yz
00
01
11
10
m0 m1 m3 m2 x 0 x’y’z’ x’y’z x’yz x’yz’
m4 m5 m7 m6 1 xy’z’ xy’z xyz xyz’
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
x y z f(x, y, z)
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
yz
00
01
11
10
x 0 0 0 0 1
1 0 0 1 1
b. Peta dengan empat peubah
yz
00
01
11
10
m0 m1 m3 m2 wx 00 w’x’y’z’ w’x’y’z w’x’yz w’x’yz’
m4 m5 m7 m6 01 w’xy’z’ w’xy’z w’xyz w’xyz’
m12 m13 m15 m14 11 wxy’z’ wxy’z wxyz wxyz’
m8 m9 m11 m10 10 wx’y’z’ wx’y’z wx’yz wx’yz’
Contoh. Diberikan tabel kebenaran, gambarkan Peta Karnaugh.
w x y z f(w, x, y, z)
0 0 0 0 0
0 0 0 1 1
0 0 1 0 0
0 0 1 1 0
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 1
1 0 0 0 0
1 0 0 1 0
1 0 1 0 0
1 0 1 1 0
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
yz
00
01
11
10
wx 00 0 1 0 1
01 0 0 1 1
11 0 0 0 1
10 0 0 0 0
Teknik Minimisasi Fungsi Boolean dengan Peta Karnaugh
1. Pasangan: dua buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 0 0 1 1
10 0 0 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxyz + wxyz’
Hasil Penyederhanaan: f(w, x, y, z) = wxy
Bukti secara aljabar:
f(w, x, y, z) = wxyz + wxyz’
= wxy(z + z’)
= wxy(1)
= wxy
2. Kuad: empat buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wxyz + wxyz’
Hasil penyederhanaan: f(w, x, y, z) = wx
Bukti secara aljabar:
f(w, x, y, z) = wxy’ + wxy
= wx(z’ + z)
= wx(1)
= wx
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 0 0 0 0
Contoh lain:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 0 0
10 1 1 0 0
Sebelum disederhanakan: f(w, x, y, z) = wxy’z’ + wxy’z + wx’y’z’ + wx’y’z
Hasil penyederhanaan: f(w, x, y, z) = wy’
3. Oktet: delapan buah 1 yang bertetangga
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 1 1 1 1
Sebelum disederhanakan: f(a, b, c, d) = wxy’z’ + wxy’z + wxyz + wxyz’ +
wx’y’z’ + wx’y’z + wx’yz + wx’yz’
Hasil penyederhanaan: f(w, x, y, z) = w
Bukti secara aljabar:
f(w, x, y, z) = wy’ + wy
= w(y’ + y)
= w
yz
00
01
11
10
wx 00 0 0 0 0
01 0 0 0 0
11 1 1 1 1
10 1 1 1 1
Contoh 5.11. Sederhanakan fungsi Boolean f(x, y, z) = x’yz + xy’z’ + xyz + xyz’.
Jawab:
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
01
11
10
x 0 1
1 1 1 1
Hasil penyederhanaan: f(x, y, z) = yz + xz’
Contoh 5.12. Andaikan suatu tabel kebenaran telah diterjemahkan ke dalam Peta Karnaugh. Sederhanakan fungsi Boolean yang bersesuaian sesederhana mungkin.
yz
00
01
11
10
wx 00 0 1 1 1
01 0 0 0 1
11 1 1 0 1
10 1 1 0 1
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = wy’ + yz’ + w’x’z
Contoh 5.13. Minimisasi fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 1 1 1 1
10 1 1 1 1
Jawab: (lihat Peta Karnaugh) f(w, x, y, z) = w + xy’z
Jika penyelesaian Contoh 5.13 adalah seperti di bawah ini:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 1 1 1 1
10 1 1 1 1
maka fungsi Boolean hasil penyederhanaan adalah
f(w, x, y, z) = w + w’xy’z (jumlah literal = 5)
yang ternyata masih belum sederhana dibandingkan f(w, x, y, z) = w + xy’z (jumlah literal = 4).
Contoh 5.14. (Penggulungan/rolling) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 1 0 0 1
11 1 0 0 1
10 0 0 0 0
Jawab: f(w, x, y, z) = xy’z’ + xyz’ ==> belum sederhana
Penyelesaian yang lebih minimal:
yz
00
01
11
10
wx 00 0 0 0 0
01 1 0 0 1
11 1 0 0 1
10 0 0 0 0
f(w, x, y, z) = xz’ ===> lebih sederhana
Contoh 5.15: (Kelompok berlebihan) Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 0 1 1 0
10 0 0 1 0
Jawab: f(w, x, y, z) = xy’z + wxz + wyz ® masih belum sederhana.
Penyelesaian yang lebih minimal:
yz
00
01
11
10
wx 00 0 0 0 0
01 0 1 0 0
11 0 1 1 0
10 0 0 1 0
f(w, x, y, z) = xy’z + wyz ===> lebih sederhana
Contoh 5.16. Sederhanakan fungsi Boolean yang bersesuaian dengan Peta Karnaugh di bawah ini.
cd
00
01
11
10
ab 00 0 0 0 0
01 0 0 1 0
11 1 1 1 1
10 0 1 1 1
Jawab: (lihat Peta Karnaugh di atas) f(a, b, c, d) = ab + ad + ac + bcd
Contoh 5.17. Minimisasi fungsi Boolean f(x, y, z) = x’z + x’y + xy’z + yz
Jawab:
x’z = x’z(y + y’) = x’yz + x’y’z
x’y = x’y(z + z’) = x’yz + x’yz’
yz = yz(x + x’) = xyz + x’yz
f(x, y, z) = x’z + x’y + xy’z + yz
= x’yz + x’y’z + x’yz + x’yz’ + xy’z + xyz + x’yz
= x’yz + x’y’z + x’yz’ + xyz + xy’z
Peta Karnaugh untuk fungsi tersebut adalah:
yz
00
01
11
10
x 0 1 1 1
1 1 1
Hasil penyederhanaan: f(x, y, z) = z + x’yz’
Peta Karnaugh untuk lima peubah
000 001 011 010 110 111 101 100
00 m0 m1 m3 m2 m6 m7 m5 m4
01 m8 m9 m11 m10 m14 m15 m13 m12
11 m24 m25 m27 m26 m30 m31 m29 m28
10 m16 m17 m19 m18 m22 m23 m21 m20
Garis pencerminan
Contoh 5.21. (Contoh penggunaan Peta 5 peubah) Carilah fungsi sederhana dari f(v, w, x, y, z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
Jawab:
Peta Karnaugh dari fungsi tersebut adalah:
xyz
000
001
011
010
110
111
101
100
vw 00
1
1
1
1
01
1
1
1
1
11
1
1
1
1
10
1
1
Jadi f(v, w, x, y, z) = wz + v’w’z’ + vy’z
Jumat, 11 Mei 2018
MATEMATIKA DISKRIT "ALJABAR BOOLEAN"
ALJABAR BOOLEAN
DEFINISI
MISALKAN TERDAPAT
- DUA OPERATOR BINER: + DAN
- SEBUAH OPERATOR UNER: ’.
- B : HIMPUNAN YANG DIDEFINISIKAN PADA OPERATOR +, , DAN ’
- 0 DAN 1 ADALAH DUA ELEMEN YANG BERBEDA DARI B.
(B, +, , ’) DISEBUT ALJABAR BOOLEAN JIKA UNTUK SETIAP A, B, C B BERLAKU AKSIOMA-AKSIOMA ATAU POSTULAT HUNTINGTON BERIKUT:
1. CLOSURE: (I) A + B B
(II) A B B
2. IDENTITAS: (I) A + 0 = A
(II) A 1 = A
3. KOMUTATIF: (I) A + B = B + A
(II) A B = B . A
4. DISTRIBUTIF: (I) A (B + C) = (A B) + (A C)
(II) A + (B C) = (A + B) (A + C)
5. KOMPLEMEN[1]: (I) A + A’ = 1
(II) A A’ = 0
UNTUK MEMPUNYAI SEBUAH ALJABAR BOOLEAN, HARUS DIPERLIHATKAN:
1. ELEMEN-ELEMEN HIMPUNAN B,
2. KAIDAH OPERASI UNTUK OPERATOR BINER DAN
OPERATOR UNER,
3. MEMENUHI POSTULAT HUNTINGTON.
ALJABAR BOOLEAN DUA-NILAI
ALJABAR BOOLEAN DUA-NILAI:
- B = {0, 1}
- OPERATOR BINER, + DAN ×
- OPERATOR UNER, ’
- KAIDAH UNTUK OPERATOR BINER DAN OPERATOR UNER :
CEK APAKAH MEMENUHI POSTULAT HUNTINGTON:
1. CLOSURE : JELAS BERLAKU
2. IDENTITAS: JELAS BERLAKU KARENA DARI TABEL DAPAT KITA LIHAT BAHWA:
(I) 0 + 1 = 1 + 0 = 1
(II) 1 × 0 = 0 × 1 = 0
3. KOMUTATIF: JELAS BERLAKU DENGAN MELIHAT SIMETRI TABEL OPERATOR BINER.
4. DISTRIBUTIF: (I) A × (B + C) = (A × B) + (A × C) DAPAT DITUNJUKKAN BENAR DARI TABEL OPERATOR BINER DI ATAS DENGAN MEMBENTUK TABEL KEBENARAN:
(II) HUKUM DISTRIBUTIF A + (B × C) = (A + B) × (A + C) DAPAT DITUNJUKKAN BENAR DENGAN MEMBUAT TABEL KEBENARAN DENGAN CARA YANG SAMA SEPERTI (I).
5. KOMPLEMEN: JELAS BERLAKU KARENA TABEL 7.3 MEMPERLIHATKAN BAHWA:
(I) A + A‘ = 1, KARENA 0 + 0’= 0 + 1 = 1 DAN 1 + 1’= 1 + 0 = 1
(II) A × A = 0, KARENA 0 × 0’= 0 × 1 = 0 DAN 1 × 1’ = 1 × 0 = 0
KARENA KELIMA POSTULAT HUNTINGTON DIPENUHI, MAKA TERBUKTI BAHWA B = {0, 1} BERSAMA-SAMA DENGAN OPERATOR BINER + DAN × OPERATOR KOMPLEMEN ‘ MERUPAKAN ALJABAR BOOLEAN.
EKSPRESI BOOLEAN
MISALKAN (B, +, , ’) ADALAH SEBUAH ALJABAR BOOLEAN. SUATU EKSPRESI BOOLEAN DALAM (B, +, , ’) ADALAH:
(I) SETIAP ELEMEN DI DALAM B,
(II) SETIAP PEUBAH,
(III) JIKA E1 DAN E2 ADALAH EKSPRESI BOOLEAN, MAKA E1 + E2, E1 E2, E1’ ADALAH EKSPRESI BOOLEAN
CONTOH:
0
1
A
B
A + B
A × B
A’× (B + C)
A × B’ + A × B × C’ + B’, DAN SEBAGAINYA
MENGEVALUASI EKSPRESI BOOLEAN
CONTOH: A’× (B + C)
JIKA A = 0, B = 1, DAN C = 0, MAKA HASIL EVALUASI EKSPRESI:
0’× (1 + 0) = 1 × 1 = 1
DUA EKSPRESI BOOLEAN DIKATAKAN EKIVALEN (DILAMBANGKAN DENGAN ‘=’) JIKA KEDUANYA MEMPUNYAI NILAI YANG SAMA UNTUK SETIAP PEMBERIAN NILAI-NILAI KEPADA N PEUBAH.
CONTOH:
A × (B + C) = (A . B) + (A × C)
CONTOH. PERLIHATKAN BAHWA A + A’B = A + B .
PENYELESAIAN:
PERJANJIAN:
TANDA TITIK (×) DAPAT DIHILANGKAN DARI PENULISAN EKSPRESI BOOLEAN, KECUALI JIKA ADA PENEKANAN:
(I) A(B + C) = AB + AC
(II) A + BC = (A + B) (A + C)
(III) A × 0 , BUKAN A0
PRINSIP DUALITAS
MISALKAN S ADALAH KESAMAAN (IDENTITY) DI DALAM ALJABAR BOOLEAN YANG MELIBATKAN OPERATOR +, ×, DAN KOMPLEMEN, MAKA JIKA PERNYATAAN S* DIPEROLEH DENGAN CARA MENGGANTI
× DENGAN +
+ DENGAN ×
0 DENGAN 1
1 DENGAN 0
DAN MEMBIARKAN OPERATOR KOMPLEMEN TETAP APA ADANYA, MAKA KESAMAAN S* JUGA BENAR. S* DISEBUT SEBAGAI DUAL DARI S.
CONTOH.
(I) (A × 1)(0 + A’) = 0 DUALNYA (A + 0) + (1 × A’) = 1
(II) A(A‘ + B) = AB DUALNYA A + A‘B = A + B
HUKUM-HUKUM ALJABAR BOOLEAN
FUNGSI BOOLEAN
FUNGSI BOOLEAN (DISEBUT JUGA FUNGSI BINER) ADALAH PEMETAAN DARI BN KE B MELALUI EKSPRESI BOOLEAN, KITA MENULISKANNYA SEBAGAI
F : BN --> B
YANG DALAM HAL INI BN ADALAH HIMPUNAN YANG BERANGGOTAKAN PASANGAN TERURUT GANDA-N (ORDERED N-TUPLE) DI DALAM DAERAH ASAL B.
• SETIAP EKSPRESI BOOLEAN TIDAK LAIN MERUPAKAN FUNGSI BOOLEAN.
• MISALKAN SEBUAH FUNGSI BOOLEAN ADALAH F(X, Y, Z) = XYZ + X’Y + Y’
• FUNGSI F MEMETAKAN NILAI-NILAI PASANGAN TERURUT GANDA-3
(X, Y, Z) KE HIMPUNAN {0, 1}.
CONTOHNYA, (1, 0, 1) YANG BERARTI X = 1, Y = 0, DAN Z = 1
SEHINGGA F(1, 0, 1) = 1 × 0 × 1 + 1’ × 0 + 0’× 1 = 0 + 0 + 1 = 1 .
CONTOH-CONTOH FUNGSI BOOLEAN YANG LAIN:
1. F(X) = X
2. F(X, Y) = X’Y + XY’+ Y’
3. F(X, Y) = X’ Y’
4. F(X, Y) = (X + Y)’
5. F(X, Y, Z) = XYZ’
SETIAP PEUBAH DI DALAM FUNGSI BOOLEAN, TERMASUK DALAM BENTUK KOMPLEMENNYA, DISEBUT LITERAL.
CONTOH:
FUNGSI H(X, Y, Z) = XYZ’ PADA CONTOH DI ATAS TERDIRI DARI 3 BUAH LITERAL, YAITU X, Y, DAN Z’.
CONTOH. DIKETAHUI FUNGSI BOOELAN F(X, Y, Z) = XY Z’, NYATAKAN H DALAM TABEL KEBENARAN.
PENYELESAIAN
KOMPLEMEN FUNGSI
1. CARA PERTAMA:
MENGGUNAKAN HUKUM DE MORGAN
HUKUM DE MORGAN UNTUK DUA BUAH PEUBAH, X1 DAN X2, ADALAH
CONTOH. MISALKAN F(X, Y, Z) = X(Y’Z’ + YZ), MAKA
F ’(X, Y, Z) = (X(Y’Z’ + YZ))’
= X’ + (Y’Z’ + YZ)’
= X’ + (Y’Z’)’ (YZ)’
= X’ + (Y + Z) (Y’ + Z’)
2. 2. CARA KEDUA:
MENGGUNAKAN PRINSIP DUALITAS.
TENTUKAN DUAL DARI EKSPRESI BOOLEAN YANG MEREPRESENTASIKAN F, LALU KOMPLEMENKAN SETIAP LITERAL DI DALAM DUAL TERSEBUT.
CONTOH. MISALKAN F(X, Y, Z) = X(Y’Z’ + YZ), MAKA
DUAL DARI F: X + (Y’ + Z’) (Y + Z)
KOMPLEMENKAN TIAP LITERALNYA: X’ + (Y + Z) (Y’ + Z’) = F ’
JADI, F ‘(X, Y, Z) = X’ + (Y + Z)(Y’ + Z’)
BENTUK KANONIK
ADA DUA MACAM BENTUK KANONIK:
1. PENJUMLAHAN DARI HASIL KALI (SUM-OF-PRODUCT ATAU SOP)
2. PERKALIAN DARI HASIL JUMLAH (PRODUCT-OF-SUM ATAU POS)
CONTOH:
1. F(X, Y, Z) = X’Y’Z + XY’Z’ + XYZ --> SOP
SETIAP SUKU (TERM) DISEBUT MINTERM
2. G(X, Y, Z) = (X + Y + Z)(X + Y’ + Z)(X + Y’ + Z’) (X’ + Y + Z’)(X’ + Y’ + Z) --> POS
SETIAP SUKU (TERM) DISEBUT MAXTERM
SETIAP MINTERM/MAXTERM MENGANDUNG LITERAL LENGKAP
CONTOH:
NYATAKAN TABEL KEBENARAN DI BAWAH INI DALAM BENTUK KANONIK SOP DAN POS.
PENYELESAIAN :
(A) SOP
KOMBINASI NILAI-NILAI PEUBAH YANG MENGHASILKAN NILAI FUNGSI SAMA DENGAN 1 ADALAH 001, 100, DAN 111, MAKA FUNGSI BOOLEANNYA DALAM BENTUK KANONIK SOP ADALAH
F(X, Y, Z) = X’Y’Z + XY’Z’ + XYZ
ATAU (DENGAN MENGGUNAKAN LAMBANG MINTERM),
F(X, Y, Z) = M1 + M4 + M7 = Å (1, 4, 7)
(B) POS
KOMBINASI NILAI-NILAI PEUBAH YANG MENGHASILKAN NILAI FUNGSI SAMA DENGAN 0 ADALAH 000, 010, 011, 101, DAN 110, MAKA FUNGSI BOOLEANNYA DALAM BENTUK KANONIK POS ADALAH
F(X, Y, Z) = (X + Y + Z)(X + Y’+ Z)(X + Y’+ Z’)
(X’+ Y + Z’)(X’+ Y’+ Z)
ATAU DALAM BENTUK LAIN,
F(X, Y, Z) = M0 M2 M3 M5 M6 = Õ(0, 2, 3, 5, 6)
CONTOH :
NYATAKAN FUNGSI BOOLEAN F(X, Y, Z) = X + Y’Z DALAM BENTUK KANONIK SOP DAN POS.
PENYELESAIAN:
(A) SOP
X = X(Y + Y’)
= XY + XY’
= XY (Z + Z’) + XY’(Z + Z’)
= XYZ + XYZ’ + XY’Z + XY’Z’
Y’Z = Y’Z (X + X’)
= XY’Z + X’Y’Z
JADI F(X, Y, Z) = X + Y’Z
= XYZ + XYZ’ + XY’Z + XY’Z’ + XY’Z + X’Y’Z
= X’Y’Z + XY’Z’ + XY’Z + XYZ’ + XYZ
ATAU F(X, Y, Z) = M1 + M4 + M5 + M6 + M7 = S (1,4,5,6,7)
(B) POS
F(X, Y, Z) = X + Y’Z
= (X + Y’)(X + Z)
X + Y’ = X + Y’ + ZZ’
= (X + Y’ + Z)(X + Y’ + Z’)
X + Z = X + Z + YY’
= (X + Y + Z)(X + Y’ + Z)
JADI, F(X, Y, Z) = (X + Y’ + Z)(X + Y’ + Z’)(X + Y + Z)(X + Y’ + Z)
= (X + Y + Z)(X + Y’ + Z)(X + Y’ + Z’)
ATAU F(X, Y, Z) = M0M2M3 = Õ(0, 2, 3)
KONVERSI ANTAR BENTUK KANONIK
MISALKAN
F(X, Y, Z) = S (1, 4, 5, 6, 7)
DAN F ’ADALAH FUNGSI KOMPLEMEN DARI F,
F ’(X, Y, Z) = S (0, 2, 3) = M0+ M2 + M3
DENGAN MENGGUNAKAN HUKUM DE MORGAN, KITA DAPAT MEMPEROLEH FUNGSI F DALAM BENTUK POS:
F ’(X, Y, Z) = (F ’(X, Y, Z))’ = (M0 + M2 + M3)’
= M0’ . M2’ . M3’
= (X’Y’Z’)’ (X’Y Z’)’ (X’Y Z)’
= (X + Y + Z) (X + Y’ + Z) (X + Y’ + Z’)
= M0 M2 M3
= Õ (0,2,3)
JADI, F(X, Y, Z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).
KESIMPULAN: MJ’ = MJ
CONTOH. NYATAKAN
F(X, Y, Z)= Õ (0, 2, 4, 5) DAN
G(W, X, Y, Z) = S(1, 2, 5, 6, 10, 15)
DALAM BENTUK SOP DAN POS
PENYELESAIAN:
F(X, Y, Z) = S (1, 3, 6, 7)
G(W, X, Y, Z)= Õ (0, 3, 4, 7, 8, 9, 11, 12, 13, 14)
CONTOH.
CARILAH BENTUK KANONIK SOP DAN POS DARI F(X, Y, Z) = Y’ + XY + X’YZ’
PENYELESAIAN:
(A) SOP
F(X, Y, Z) = Y’ + XY + X’YZ’
= Y’ (X + X’) (Z + Z’) + XY (Z + Z’) + X’YZ’
= (XY’ + X’Y’) (Z + Z’) + XYZ + XYZ’ + X’YZ’
= XY’Z + XY’Z’ + X’Y’Z + X’Y’Z’ + XYZ + XYZ’ + X’YZ’
ATAU F(X, Y, Z) = M0+ M1 + M2+ M4+ M5+ M6+ M7
(B) POS
F(X, Y, Z) = M3 = X + Y’ + Z’
BENTUK BAKU
1. TIDAK HARUS MENGANDUNG LITERAL YANG LENGKAP.
CONTOHNYA,
F(X, Y, Z) = Y’ + XY + X’YZ (BENTUK BAKU SOP)
F(X, Y, Z) = X(Y’ + Z)(X’ + Y + Z’) (BENTUK BAKU POS)
APLIKASI ALJABAR BOOLEAN
1. JARINGAN PENSAKLARAN (SWITCHING NETWORK)
SAKLAR: OBJEK YANG MEMPUNYAI DUA BUAH KEADAAN: BUKA DAN TUTUP.
TIGA BENTUK GERBANG PALING SEDERHANA:
CONTOH RANGKAIAN PENSAKLARAN PADA RANGKAIAN LISTRIK:
1. SAKLAR DALAM HUBUNGAN SERI: LOGIKA AND
2. SAKLAR DALAM HUBUNGAN PARALEL: LOGIKA OR
2. RANGKAIAN LOGIKA
PENYEDERHANAAN FUNGSI BOOLEAN
CONTOH:
F(X, Y) = X’Y + XY’ + Y DISEDERHANAKAN MENJADI F(X, Y) = X’ + Y’
PENYEDERHANAAN FUNGSI BOOLEAN DAPAT DILAKUKAN DENGAN 3 CARA:
1. SECARA ALJABAR
2. MENGGUNAKAN PETA KARNAUGH
3. MENGGUNAKAN METODE QUINE MC CLUSKEY (METODE TABULASI)
1. PENYEDERHANAAN SECARA ALJABAR
CONTOH:
1. F(X, Y) = X + X’Y
= (X + X’)(X + Y)
= 1 × (X + Y )
= X + Y
2. F(X, Y, Z) = X’Y’Z + X’YZ + XY’
= X’Z(Y’ + Y) + XY’
= X’Z + XY’
3. F(X, Y, Z) = XY + X’Z + YZ = XY + X’Z + YZ(X + X’)
= XY + X’Z + XYZ + X’YZ
= XY(1 + Z) + X’Z(1 + Y) = XY + X’Z
2. PETA KARNAUGH
A. PETA KARNAUGH DENGAN DUA PEUBAH
B. PETA DENGAN TIGA PEUBAH
CONTOH. DIBERIKAN TABEL KEBENARAN, GAMBARKAN PETA KARNAUGH.
C. PETA DENGAN EMPAT PEUBAH
CONTOH. DIBERIKAN TABEL KEBENARAN, GAMBARKAN PETA KARNAUGH.
TEKNIK MINIMISASI FUNGSI BOOLEAN DENGAN PETA KARNAUGH
1. PASANGAN: DUA BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXYZ + WXYZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WXY
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WXYZ + WXYZ’
= WXY(Z + Z’)
= WXY(1)
= WXY
2. KUAD: EMPAT BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXY’Z’ + WXY’Z + WXYZ + WXYZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WX
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WXY’ + WXY
= WX(Z’ + Z)
= WX(1)
= WX
CONTOH LAIN:
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXY’Z’ + WXY’Z + WX’Y’Z’ + WX’Y’Z
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WY’
3. OKTET: DELAPAN BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(A, B, C, D) = WXY’Z’ + WXY’Z + WXYZ + WXYZ’ +
WX’Y’Z’ + WX’Y’Z + WX’YZ + WX’YZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = W
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WY’ + WY
= W(Y’ + Y)
= W
PETA KARNAUGH UNTUK LIMA PEUBAH
CONTOH:
(CONTOH PENGGUNAAN PETA 5 PEUBAH) CARILAH FUNGSI SEDERHANA DARI F(V, W, X, Y, Z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
JAWAB:
PETA KARNAUGH DARI FUNGSI TERSEBUT ADALAH:
`1
ALJABAR BOOLEAN
DEFINISI
MISALKAN TERDAPAT
- DUA OPERATOR BINER: + DAN
- SEBUAH OPERATOR UNER: ’.
- B : HIMPUNAN YANG DIDEFINISIKAN PADA OPERATOR +, , DAN ’
- 0 DAN 1 ADALAH DUA ELEMEN YANG BERBEDA DARI B.
(B, +, , ’) DISEBUT ALJABAR BOOLEAN JIKA UNTUK SETIAP A, B, C B BERLAKU AKSIOMA-AKSIOMA ATAU POSTULAT HUNTINGTON BERIKUT:
1. CLOSURE: (I) A + B B
(II) A B B
2. IDENTITAS: (I) A + 0 = A
(II) A 1 = A
3. KOMUTATIF: (I) A + B = B + A
(II) A B = B . A
4. DISTRIBUTIF: (I) A (B + C) = (A B) + (A C)
(II) A + (B C) = (A + B) (A + C)
5. KOMPLEMEN[1]: (I) A + A’ = 1
(II) A A’ = 0
UNTUK MEMPUNYAI SEBUAH ALJABAR BOOLEAN, HARUS DIPERLIHATKAN:
1. ELEMEN-ELEMEN HIMPUNAN B,
2. KAIDAH OPERASI UNTUK OPERATOR BINER DAN
OPERATOR UNER,
3. MEMENUHI POSTULAT HUNTINGTON.
ALJABAR BOOLEAN DUA-NILAI
ALJABAR BOOLEAN DUA-NILAI:
- B = {0, 1}
- OPERATOR BINER, + DAN ×
- OPERATOR UNER, ’
- KAIDAH UNTUK OPERATOR BINER DAN OPERATOR UNER :
CEK APAKAH MEMENUHI POSTULAT HUNTINGTON:
1. CLOSURE : JELAS BERLAKU
2. IDENTITAS: JELAS BERLAKU KARENA DARI TABEL DAPAT KITA LIHAT BAHWA:
(I) 0 + 1 = 1 + 0 = 1
(II) 1 × 0 = 0 × 1 = 0
3. KOMUTATIF: JELAS BERLAKU DENGAN MELIHAT SIMETRI TABEL OPERATOR BINER.
4. DISTRIBUTIF: (I) A × (B + C) = (A × B) + (A × C) DAPAT DITUNJUKKAN BENAR DARI TABEL OPERATOR BINER DI ATAS DENGAN MEMBENTUK TABEL KEBENARAN:
(II) HUKUM DISTRIBUTIF A + (B × C) = (A + B) × (A + C) DAPAT DITUNJUKKAN BENAR DENGAN MEMBUAT TABEL KEBENARAN DENGAN CARA YANG SAMA SEPERTI (I).
5. KOMPLEMEN: JELAS BERLAKU KARENA TABEL 7.3 MEMPERLIHATKAN BAHWA:
(I) A + A‘ = 1, KARENA 0 + 0’= 0 + 1 = 1 DAN 1 + 1’= 1 + 0 = 1
(II) A × A = 0, KARENA 0 × 0’= 0 × 1 = 0 DAN 1 × 1’ = 1 × 0 = 0
KARENA KELIMA POSTULAT HUNTINGTON DIPENUHI, MAKA TERBUKTI BAHWA B = {0, 1} BERSAMA-SAMA DENGAN OPERATOR BINER + DAN × OPERATOR KOMPLEMEN ‘ MERUPAKAN ALJABAR BOOLEAN.
EKSPRESI BOOLEAN
MISALKAN (B, +, , ’) ADALAH SEBUAH ALJABAR BOOLEAN. SUATU EKSPRESI BOOLEAN DALAM (B, +, , ’) ADALAH:
(I) SETIAP ELEMEN DI DALAM B,
(II) SETIAP PEUBAH,
(III) JIKA E1 DAN E2 ADALAH EKSPRESI BOOLEAN, MAKA E1 + E2, E1 E2, E1’ ADALAH EKSPRESI BOOLEAN
CONTOH:
0
1
A
B
A + B
A × B
A’× (B + C)
A × B’ + A × B × C’ + B’, DAN SEBAGAINYA
MENGEVALUASI EKSPRESI BOOLEAN
CONTOH: A’× (B + C)
JIKA A = 0, B = 1, DAN C = 0, MAKA HASIL EVALUASI EKSPRESI:
0’× (1 + 0) = 1 × 1 = 1
DUA EKSPRESI BOOLEAN DIKATAKAN EKIVALEN (DILAMBANGKAN DENGAN ‘=’) JIKA KEDUANYA MEMPUNYAI NILAI YANG SAMA UNTUK SETIAP PEMBERIAN NILAI-NILAI KEPADA N PEUBAH.
CONTOH:
A × (B + C) = (A . B) + (A × C)
CONTOH. PERLIHATKAN BAHWA A + A’B = A + B .
PENYELESAIAN:
PERJANJIAN:
TANDA TITIK (×) DAPAT DIHILANGKAN DARI PENULISAN EKSPRESI BOOLEAN, KECUALI JIKA ADA PENEKANAN:
(I) A(B + C) = AB + AC
(II) A + BC = (A + B) (A + C)
(III) A × 0 , BUKAN A0
PRINSIP DUALITAS
MISALKAN S ADALAH KESAMAAN (IDENTITY) DI DALAM ALJABAR BOOLEAN YANG MELIBATKAN OPERATOR +, ×, DAN KOMPLEMEN, MAKA JIKA PERNYATAAN S* DIPEROLEH DENGAN CARA MENGGANTI
× DENGAN +
+ DENGAN ×
0 DENGAN 1
1 DENGAN 0
DAN MEMBIARKAN OPERATOR KOMPLEMEN TETAP APA ADANYA, MAKA KESAMAAN S* JUGA BENAR. S* DISEBUT SEBAGAI DUAL DARI S.
CONTOH.
(I) (A × 1)(0 + A’) = 0 DUALNYA (A + 0) + (1 × A’) = 1
(II) A(A‘ + B) = AB DUALNYA A + A‘B = A + B
HUKUM-HUKUM ALJABAR BOOLEAN
FUNGSI BOOLEAN
FUNGSI BOOLEAN (DISEBUT JUGA FUNGSI BINER) ADALAH PEMETAAN DARI BN KE B MELALUI EKSPRESI BOOLEAN, KITA MENULISKANNYA SEBAGAI
F : BN --> B
YANG DALAM HAL INI BN ADALAH HIMPUNAN YANG BERANGGOTAKAN PASANGAN TERURUT GANDA-N (ORDERED N-TUPLE) DI DALAM DAERAH ASAL B.
• SETIAP EKSPRESI BOOLEAN TIDAK LAIN MERUPAKAN FUNGSI BOOLEAN.
• MISALKAN SEBUAH FUNGSI BOOLEAN ADALAH F(X, Y, Z) = XYZ + X’Y + Y’
• FUNGSI F MEMETAKAN NILAI-NILAI PASANGAN TERURUT GANDA-3
(X, Y, Z) KE HIMPUNAN {0, 1}.
CONTOHNYA, (1, 0, 1) YANG BERARTI X = 1, Y = 0, DAN Z = 1
SEHINGGA F(1, 0, 1) = 1 × 0 × 1 + 1’ × 0 + 0’× 1 = 0 + 0 + 1 = 1 .
CONTOH-CONTOH FUNGSI BOOLEAN YANG LAIN:
1. F(X) = X
2. F(X, Y) = X’Y + XY’+ Y’
3. F(X, Y) = X’ Y’
4. F(X, Y) = (X + Y)’
5. F(X, Y, Z) = XYZ’
SETIAP PEUBAH DI DALAM FUNGSI BOOLEAN, TERMASUK DALAM BENTUK KOMPLEMENNYA, DISEBUT LITERAL.
CONTOH:
FUNGSI H(X, Y, Z) = XYZ’ PADA CONTOH DI ATAS TERDIRI DARI 3 BUAH LITERAL, YAITU X, Y, DAN Z’.
CONTOH. DIKETAHUI FUNGSI BOOELAN F(X, Y, Z) = XY Z’, NYATAKAN H DALAM TABEL KEBENARAN.
PENYELESAIAN
KOMPLEMEN FUNGSI
1. CARA PERTAMA:
MENGGUNAKAN HUKUM DE MORGAN
HUKUM DE MORGAN UNTUK DUA BUAH PEUBAH, X1 DAN X2, ADALAH
CONTOH. MISALKAN F(X, Y, Z) = X(Y’Z’ + YZ), MAKA
F ’(X, Y, Z) = (X(Y’Z’ + YZ))’
= X’ + (Y’Z’ + YZ)’
= X’ + (Y’Z’)’ (YZ)’
= X’ + (Y + Z) (Y’ + Z’)
2. 2. CARA KEDUA:
MENGGUNAKAN PRINSIP DUALITAS.
TENTUKAN DUAL DARI EKSPRESI BOOLEAN YANG MEREPRESENTASIKAN F, LALU KOMPLEMENKAN SETIAP LITERAL DI DALAM DUAL TERSEBUT.
CONTOH. MISALKAN F(X, Y, Z) = X(Y’Z’ + YZ), MAKA
DUAL DARI F: X + (Y’ + Z’) (Y + Z)
KOMPLEMENKAN TIAP LITERALNYA: X’ + (Y + Z) (Y’ + Z’) = F ’
JADI, F ‘(X, Y, Z) = X’ + (Y + Z)(Y’ + Z’)
BENTUK KANONIK
ADA DUA MACAM BENTUK KANONIK:
1. PENJUMLAHAN DARI HASIL KALI (SUM-OF-PRODUCT ATAU SOP)
2. PERKALIAN DARI HASIL JUMLAH (PRODUCT-OF-SUM ATAU POS)
CONTOH:
1. F(X, Y, Z) = X’Y’Z + XY’Z’ + XYZ --> SOP
SETIAP SUKU (TERM) DISEBUT MINTERM
2. G(X, Y, Z) = (X + Y + Z)(X + Y’ + Z)(X + Y’ + Z’) (X’ + Y + Z’)(X’ + Y’ + Z) --> POS
SETIAP SUKU (TERM) DISEBUT MAXTERM
SETIAP MINTERM/MAXTERM MENGANDUNG LITERAL LENGKAP
CONTOH:
NYATAKAN TABEL KEBENARAN DI BAWAH INI DALAM BENTUK KANONIK SOP DAN POS.
PENYELESAIAN :
(A) SOP
KOMBINASI NILAI-NILAI PEUBAH YANG MENGHASILKAN NILAI FUNGSI SAMA DENGAN 1 ADALAH 001, 100, DAN 111, MAKA FUNGSI BOOLEANNYA DALAM BENTUK KANONIK SOP ADALAH
F(X, Y, Z) = X’Y’Z + XY’Z’ + XYZ
ATAU (DENGAN MENGGUNAKAN LAMBANG MINTERM),
F(X, Y, Z) = M1 + M4 + M7 = Å (1, 4, 7)
(B) POS
KOMBINASI NILAI-NILAI PEUBAH YANG MENGHASILKAN NILAI FUNGSI SAMA DENGAN 0 ADALAH 000, 010, 011, 101, DAN 110, MAKA FUNGSI BOOLEANNYA DALAM BENTUK KANONIK POS ADALAH
F(X, Y, Z) = (X + Y + Z)(X + Y’+ Z)(X + Y’+ Z’)
(X’+ Y + Z’)(X’+ Y’+ Z)
ATAU DALAM BENTUK LAIN,
F(X, Y, Z) = M0 M2 M3 M5 M6 = Õ(0, 2, 3, 5, 6)
CONTOH :
NYATAKAN FUNGSI BOOLEAN F(X, Y, Z) = X + Y’Z DALAM BENTUK KANONIK SOP DAN POS.
PENYELESAIAN:
(A) SOP
X = X(Y + Y’)
= XY + XY’
= XY (Z + Z’) + XY’(Z + Z’)
= XYZ + XYZ’ + XY’Z + XY’Z’
Y’Z = Y’Z (X + X’)
= XY’Z + X’Y’Z
JADI F(X, Y, Z) = X + Y’Z
= XYZ + XYZ’ + XY’Z + XY’Z’ + XY’Z + X’Y’Z
= X’Y’Z + XY’Z’ + XY’Z + XYZ’ + XYZ
ATAU F(X, Y, Z) = M1 + M4 + M5 + M6 + M7 = S (1,4,5,6,7)
(B) POS
F(X, Y, Z) = X + Y’Z
= (X + Y’)(X + Z)
X + Y’ = X + Y’ + ZZ’
= (X + Y’ + Z)(X + Y’ + Z’)
X + Z = X + Z + YY’
= (X + Y + Z)(X + Y’ + Z)
JADI, F(X, Y, Z) = (X + Y’ + Z)(X + Y’ + Z’)(X + Y + Z)(X + Y’ + Z)
= (X + Y + Z)(X + Y’ + Z)(X + Y’ + Z’)
ATAU F(X, Y, Z) = M0M2M3 = Õ(0, 2, 3)
KONVERSI ANTAR BENTUK KANONIK
MISALKAN
F(X, Y, Z) = S (1, 4, 5, 6, 7)
DAN F ’ADALAH FUNGSI KOMPLEMEN DARI F,
F ’(X, Y, Z) = S (0, 2, 3) = M0+ M2 + M3
DENGAN MENGGUNAKAN HUKUM DE MORGAN, KITA DAPAT MEMPEROLEH FUNGSI F DALAM BENTUK POS:
F ’(X, Y, Z) = (F ’(X, Y, Z))’ = (M0 + M2 + M3)’
= M0’ . M2’ . M3’
= (X’Y’Z’)’ (X’Y Z’)’ (X’Y Z)’
= (X + Y + Z) (X + Y’ + Z) (X + Y’ + Z’)
= M0 M2 M3
= Õ (0,2,3)
JADI, F(X, Y, Z) = S (1, 4, 5, 6, 7) = Õ (0,2,3).
KESIMPULAN: MJ’ = MJ
CONTOH. NYATAKAN
F(X, Y, Z)= Õ (0, 2, 4, 5) DAN
G(W, X, Y, Z) = S(1, 2, 5, 6, 10, 15)
DALAM BENTUK SOP DAN POS
PENYELESAIAN:
F(X, Y, Z) = S (1, 3, 6, 7)
G(W, X, Y, Z)= Õ (0, 3, 4, 7, 8, 9, 11, 12, 13, 14)
CONTOH.
CARILAH BENTUK KANONIK SOP DAN POS DARI F(X, Y, Z) = Y’ + XY + X’YZ’
PENYELESAIAN:
(A) SOP
F(X, Y, Z) = Y’ + XY + X’YZ’
= Y’ (X + X’) (Z + Z’) + XY (Z + Z’) + X’YZ’
= (XY’ + X’Y’) (Z + Z’) + XYZ + XYZ’ + X’YZ’
= XY’Z + XY’Z’ + X’Y’Z + X’Y’Z’ + XYZ + XYZ’ + X’YZ’
ATAU F(X, Y, Z) = M0+ M1 + M2+ M4+ M5+ M6+ M7
(B) POS
F(X, Y, Z) = M3 = X + Y’ + Z’
BENTUK BAKU
1. TIDAK HARUS MENGANDUNG LITERAL YANG LENGKAP.
CONTOHNYA,
F(X, Y, Z) = Y’ + XY + X’YZ (BENTUK BAKU SOP)
F(X, Y, Z) = X(Y’ + Z)(X’ + Y + Z’) (BENTUK BAKU POS)
APLIKASI ALJABAR BOOLEAN
1. JARINGAN PENSAKLARAN (SWITCHING NETWORK)
SAKLAR: OBJEK YANG MEMPUNYAI DUA BUAH KEADAAN: BUKA DAN TUTUP.
TIGA BENTUK GERBANG PALING SEDERHANA:
CONTOH RANGKAIAN PENSAKLARAN PADA RANGKAIAN LISTRIK:
1. SAKLAR DALAM HUBUNGAN SERI: LOGIKA AND
2. SAKLAR DALAM HUBUNGAN PARALEL: LOGIKA OR
2. RANGKAIAN LOGIKA
PENYEDERHANAAN FUNGSI BOOLEAN
CONTOH:
F(X, Y) = X’Y + XY’ + Y DISEDERHANAKAN MENJADI F(X, Y) = X’ + Y’
PENYEDERHANAAN FUNGSI BOOLEAN DAPAT DILAKUKAN DENGAN 3 CARA:
1. SECARA ALJABAR
2. MENGGUNAKAN PETA KARNAUGH
3. MENGGUNAKAN METODE QUINE MC CLUSKEY (METODE TABULASI)
1. PENYEDERHANAAN SECARA ALJABAR
CONTOH:
1. F(X, Y) = X + X’Y
= (X + X’)(X + Y)
= 1 × (X + Y )
= X + Y
2. F(X, Y, Z) = X’Y’Z + X’YZ + XY’
= X’Z(Y’ + Y) + XY’
= X’Z + XY’
3. F(X, Y, Z) = XY + X’Z + YZ = XY + X’Z + YZ(X + X’)
= XY + X’Z + XYZ + X’YZ
= XY(1 + Z) + X’Z(1 + Y) = XY + X’Z
2. PETA KARNAUGH
A. PETA KARNAUGH DENGAN DUA PEUBAH
B. PETA DENGAN TIGA PEUBAH
CONTOH. DIBERIKAN TABEL KEBENARAN, GAMBARKAN PETA KARNAUGH.
C. PETA DENGAN EMPAT PEUBAH
CONTOH. DIBERIKAN TABEL KEBENARAN, GAMBARKAN PETA KARNAUGH.
TEKNIK MINIMISASI FUNGSI BOOLEAN DENGAN PETA KARNAUGH
1. PASANGAN: DUA BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXYZ + WXYZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WXY
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WXYZ + WXYZ’
= WXY(Z + Z’)
= WXY(1)
= WXY
2. KUAD: EMPAT BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXY’Z’ + WXY’Z + WXYZ + WXYZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WX
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WXY’ + WXY
= WX(Z’ + Z)
= WX(1)
= WX
CONTOH LAIN:
SEBELUM DISEDERHANAKAN: F(W, X, Y, Z) = WXY’Z’ + WXY’Z + WX’Y’Z’ + WX’Y’Z
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = WY’
3. OKTET: DELAPAN BUAH 1 YANG BERTETANGGA
SEBELUM DISEDERHANAKAN: F(A, B, C, D) = WXY’Z’ + WXY’Z + WXYZ + WXYZ’ +
WX’Y’Z’ + WX’Y’Z + WX’YZ + WX’YZ’
HASIL PENYEDERHANAAN: F(W, X, Y, Z) = W
BUKTI SECARA ALJABAR:
F(W, X, Y, Z) = WY’ + WY
= W(Y’ + Y)
= W
PETA KARNAUGH UNTUK LIMA PEUBAH
CONTOH:
(CONTOH PENGGUNAAN PETA 5 PEUBAH) CARILAH FUNGSI SEDERHANA DARI F(V, W, X, Y, Z) = S (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
JAWAB:
PETA KARNAUGH DARI FUNGSI TERSEBUT ADALAH:
`1
Kamis, 12 April 2018
MATEMATIKA DISKRIT
KOMBINATORIAL dan PELUANG DISKRIT
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati
Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.
B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
- Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2: p q hasil
- Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2: p + q hasil
C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.
Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer :
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
A = 26 = 64,
B = 26 = 64,
A B = 24 = 16.
maka
A B = A + B – A B
= 26 + 26 – 16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer :
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1. C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:
{1, 2} = {2, 1}
{1, 3} = {3, 1} 3 buah atau
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
- ada n1! cara memasukkan bola berwarna 1
- ada n2! cara memasukkan bola berwarna 2
- ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:
Dengan cara lain :
- Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
- Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
- Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
- Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i. Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
ii. Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1 +x2+x3+x4=12, xi adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
- Kotak 1 diisi 3 buah bola (x1=3)
- Kotak 2 diisi 5 buah bola (x2=5)
- Kotak 3 diisi 2 buah bola (x3=2)
- Kotak 4 diisi 2 buah bola (x4=2)
sehingga, x1 +x2+x3+x4=3+5+2+2=12
I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
• Suku pertama xn, sedangkan suku terakhir adalah yn
• Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
• Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
= k=0nC(n,k)xn-kyk
J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.
example :
Misalkan terdapat banyak bola merah,bola putih,dan bola biru di dalam sebuah kotak.Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K. Peluang Diskrit
Peluang diskrit mempunyai sifat sebagai berikut:
a. 0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b. i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
• P A∩B=xi∈A∩Bp(xi)
• P A∪B=xi∈A∪Bp(xi)
• P A-B=xi∈A-Bp(xi)
• P A⨁B=xi∈A⨁Bp(xi)
• P(A)=1-P(A)
KOMBINATORIAL dan PELUANG DISKRIT
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati
Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.
B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
- Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2: p q hasil
- Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2: p + q hasil
C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.
Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer :
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
A = 26 = 64,
B = 26 = 64,
A B = 24 = 16.
maka
A B = A + B – A B
= 26 + 26 – 16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer :
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1. C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:
{1, 2} = {2, 1}
{1, 3} = {3, 1} 3 buah atau
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
- ada n1! cara memasukkan bola berwarna 1
- ada n2! cara memasukkan bola berwarna 2
- ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:
Dengan cara lain :
- Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
- Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
- Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
- Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i. Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
ii. Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1 +x2+x3+x4=12, xi adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
- Kotak 1 diisi 3 buah bola (x1=3)
- Kotak 2 diisi 5 buah bola (x2=5)
- Kotak 3 diisi 2 buah bola (x3=2)
- Kotak 4 diisi 2 buah bola (x4=2)
sehingga, x1 +x2+x3+x4=3+5+2+2=12
I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
• Suku pertama xn, sedangkan suku terakhir adalah yn
• Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
• Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
= k=0nC(n,k)xn-kyk
J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.
example :
Misalkan terdapat banyak bola merah,bola putih,dan bola biru di dalam sebuah kotak.Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa melihat kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K. Peluang Diskrit
Peluang diskrit mempunyai sifat sebagai berikut:
a. 0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b. i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
• P A∩B=xi∈A∩Bp(xi)
• P A∪B=xi∈A∪Bp(xi)
• P A-B=xi∈A-Bp(xi)
• P A⨁B=xi∈A⨁Bp(xi)
• P(A)=1-P(A)
Langganan:
Postingan (Atom)