Daftar Isi Kata Pengantar ...................................................................
iii
Daftar Isi ...........................................................................
v
Apakah Matematika Diskrit Itu ? ..........................................
xi
1.
Logika ........................................................................................
1
1.1 Proposisi ............................................................................. 1.2 Mengkombinasikan Proposisi ............................................... 1.3 Tabel kebenaran .................................................................. 1.4 Disjungsi Eksklusif ............................................................. 1.5 Hukum-hukum Logika Proposisi........................................... 1.6 Operasi Logika di dalam Komputer ...................................... 1.7 Proposisi Bersyarat (Implikasi) ............................................ 1.8 Varian Proposisi Bersyarat ................................................... 1.9 Bikondisional (Bi-implikasi) ................................................. 1.10 Inferensi ............................................................................. 1.11 Argumen ............................................................................ 1.12 Aksioma, Teorema, Lemma, dan Colollary ........................... 1.13 Ragam Contoh Soal dan Penyelesaian ................................... Soal Latihan .................................................................................
2 4 6 9 10 12 15 21 22 26 30 35 35 42
Daftar Isi
v
2.
3.
Himpunan .................................................................................
47
2.1 Definisi Himpunan .............................................................. 2.2 Penyajian Himpunan ........................................................... 2.3 Kardinalitas ........................................................................ 2.4 Himpunan Kosong .............................................................. 2.5 Himpunan Bagian (Subset) ................................................... 2.6 Himpunan yang Sama ......................................................... 2.7 Himpunan yang Ekivalen .................................................... 2.8 Himpunan Saling Lepas ....................................................... 2.9 Himpunan Kuasa ................................................................. 2.10 Operasi Terhadap Himpunan ................................................ 2.11 Perampatan Operasi Himpunan ............................................. 2.12 Hukum-hukum Himpunan ................................................... 2.13 Prinsip Dualitas ................................................................... 2.14 Prinsip Inklusi-Eksklusi ....................................................... 2.15 Partisi ................................................................................. 2.16 Pembuktian Proposisi Himpunan .......................................... 2.17 Himpunan Ganda ................................................................. 2.18 Tipe Set dalam Bahasa Pascal ............................................... 2.19 Pengantar Logika dan Himpunan Fuzzy ................................ 2.20 Ragam Contoh Soal dan Penyelesaian ................................... Soal Latihan .................................................................................
48 48 53 54 54 57 57 58 59 60 66 67 68 70 72 73 78 79 80 87 92
Matriks, Relasi dan Fungsi .....................................................
97
3.1 3.2 3.3
3.4 3.5 3.6 3.7 3.8 3.9
vi
Matriks ............................................................................... Relasi ................................................................................. Representasi Relasi .............................................................
98 103 105
3.3.1 Representasi Relasi dengan Tabel ............................................. 3.3.2 Representasi Relasi dengan Matriks ......................................... 3.3.3 Representasi Relasi dengan Graf Berarah ................................
105 106 107
Relasi Inversi....................................................................... Mengkombinasikan Relasi.................................................... Komposisi Relasi ................................................................. Sifat-sifat Relasi .................................................................. Relasi Kesetaraan ................................................................ Relasi Pengurutan Parsial......................................................
108 109 110 112 118 119
Matematika Diskrit
4.
5.
3.10 Klosur Relasi ...................................................................... 3.11 Relasi n-ary ......................................................................... 3.12 Fungsi ................................................................................. 3.13 Fungsi Inversi ..................................................................... 3.14 Komposisi Fungsi ................................................................ 3.15 Beberapa Fungsi Khusus ...................................................... 3.16 Fungsi Rekursif ................................................................... 3.17 Ragam Soal dan Penyelesaian .............................................. Soal Latihan ..................................................................................
120 124 128 134 135 136 138 141 144
Induksi Matematik ...................................................................
149
4.1 Pernyataan Perihal Bilangan Bulat ........................................ 4.2 Prinsip Induksi Sederhana .................................................... 4.3 Prinsip Induksi yang Dirampatkan ........................................ 4.4 Prinsip Induksi Kuat ............................................................ 4.5 Bentuk Induksi Secara Umum .............................................. 4.6 Ragam Soal dan Penyelesaian .............................................. Soal Latihan .................................................................................
150 151 156 160 163 165 170
Algoritma dan Bilangan Bulat ................................................
175
5.1 Algoritma ............................................................................ 5.2 Notasi untuk Algoritma ....................................................... 5.3 Beberapa Contoh Algoritma ................................................. 5.4 Bilangan Bulat ..................................................................... 5.5 Sifat Pembagian pada Bilangan Bulat .................................... 5.6 Pembagi Bersama Terbesar .................................................. 5.7 Algoritma Euclidean ............................................................ 5.8 Aritmetika Modulo .............................................................. 5.9 Bilangan Prima .................................................................... 5.10 Kriptografi .......................................................................... 5.11 Fungsi Hash ........................................................................ 5.12 International Standard Book Number (ISBN) ........................ 5.13 Pembangkit Bilangan Acak Semu ......................................... 5.14 Ragam Soal dan Penyelesaian ............................................... Soal Latihan ..................................................................................
176 177 180 183 183 185 187 191 200 203 214 215 217 218 222
Daftar Isi
vii
6.
7.
viii
Kombinatorial dan Peluang Diksrit ........................................
225
6.1 Percobaan ........................................................................... 6.2 Kaidah Dasar Menghitung .................................................... 6.3 Perluasan Kaidah Menghitung .............................................. 6.4 Prinsip Inklusi-Eksklusi........................................................ 6.5 Permutasi ............................................................................ 6.6 Kombinasi ........................................................................... 6.7 Permutasi dan Kombinasi Bentuk Umum .............................. 6.8 Kombinasi dengan Pengulangan ........................................... 6.9 Koefisien Binomial ............................................................. 6.10 Prinsip Sarang Merpati ........................................................ 6.11 Peluang Diskrit ................................................................... 6.12 Ragam Soal dan Penyelesaian ............................................... Soal Latihan .................................................................................
226 227 230 236 236 244 251 254 256 258 260 268 277
Aljabar Boolean ........................................................................
281
7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 7.10 7.11 7.12
Definisi Aljabar Boolean ...................................................... Aljabar Boolean Dua-Nilai ................................................... Ekspresi Boolean ................................................................. Prinsip Dualitas ................................................................... Hukum-hukum Aljabar Boolean ........................................... Fungsi Boolean .................................................................... Penjumlahan dan Perkalian Dua Fungsi ................................ Komplemen Fungs i Boolean ................................................. Bentuk Kanonik ................................................................... Konversi Antar Bentuk Kanonik ........................................... Bentuk Baku ....................................................................... Aplikasi Aljabar Boolean .....................................................
282 285 286 288 289 293 295 296 298 303 304 305
7.12.1 Jaringan Pensaklaran (Switching Network) .............................. 7.12.2 Sirkuit Elektronik .......................................................................
305 306
7.13 Penyederhanaan Fungsi Boolean ...........................................
308
7.13.1 Penyederhanaan Fungsi Boolean Secara Aljabar ..................... 7.13.2 Metode Peta Karnaugh ............................................................... 7.13.3 Contoh-contoh Penyederhanaan Fungsi Boolean .................... 7.13.4 Peta Karnaugh untuk Lima Peubah ........................................... 7.13.5 Keadaan Don’t Care ..................................................................
309 310 324 329 330
7.14 Penyederhanaan Rangkaian Logika .......................................
333
Matematika Diskrit
8.
9.
7.15 Metode Quine-McCluskey .................................................... 7.16 Ragam Soal dan Penyelesaian .............................................. Soal Latihan .................................................................................
334 338 348
Graf ............................................................................................
353
8.1 Sejarah Graf ........................................................................ 8.2 Definisi Graf ....................................................................... 8.3 Jenis-jenis Graf ................................................................... 8.4 Contoh Terapan Graf ........................................................... 8.5 Terminologi Dasar .............................................................. 8.6 Beberapa Graf Sederhana Khusus ......................................... 8.7 Representasi Graf ................................................................ 8.8 Graf Isomorfik (Isomorphic Graph) ...................................... 8.9 Graf Planar dan Graf Bidang................................................. 8.10 Graf Dual (Dual Graph) ....................................................... 8.11 Lintasan dan Sirkuit Euler .................................................... 8.12 Lintasan dan Sirkuit Hamilton .............................................. 8.13 Lintasan Terpendek (Shortest Path) ...................................... 8.14 Persoalan Pedagang Keliling ................................................ 8.15 Persoalan Tukang Pos Cina .................................................. 8.16 Pewarnaan Graf ................................................................... 8.17 Ragam Soal dan Penyelesaian ............................................... Soal Latihan ..................................................................................
354 356 357 359 364 377 381 386 392 402 404 408 412 421 424 425 430 437
Pohon .........................................................................................
443
9.1 9.2 9.3 9.4 9.5 9.6 9.7 9.8 9.9 9.10 9.11
444 446 447 447 457 458 461 463 467 469 475
Daftar Isi
Definisi Pohon ...................................................................... Sifat-sifat Pohon .................................................................... Pewarnaan Pohon .................................................................. Pohon Merentang .................................................................. Pohon Berakar ...................................................................... Terminologi Pada Pohon Berakar ........................................... Pohon Berakar Terurut .......................................................... Pohon m-ary ......................................................................... Pohon Biner .......................................................................... Pohon Ekspresi ..................................................................... Pohon Keputusan ..................................................................
ix
9.12 Kode Awalan ....................................................................... 9.13 Kode Huffman ...................................................................... 9.14 Pohon Pencarian ................................................................... 9.15 Traversal Pohon Biner ........................................................... 9.16 Ragam Soal dan Pembahasan ................................................ Soal Latihan ..................................................................................
476 477 481 483 487 491
10. Kompleksitas Algoritma ...........................................................
495
10.1 Kemangkusan Algoritma ....................................................... 10.2 Mengapa Kita Memerlukan Algoritma yang Mangkus? ........... 10.3 Kebutuhan Waktu dan Ruang ................................................. 10.4 Kompleksitas Waktu dan Ruang .............................................. 10.5 Kompleksitas Waktu Asimptotik ........................................... 10.6 Ragam Soal dan Penyelesaian ................................................ Soal Latihan .................................................................................
496 496 498 499 510 538 541
Daftar Pustaka ...................................................................
457
x
Matematika Diskrit
