Foundation of Computer Science 1 1 BAB I TEORI HIMPUNAN 1.1 Dasar – dasar Teori Himpunan Definisi : Himpunan adalah kumpulan objek – objek yang berbeda (Liu, 1986) Biasanya dinotasikan dengan huruf besar. Dan objek yang berada di dalamnya disebut elemen / anggota. 1.1.1 Menyatakan Himpunan Ada 2 cara untuk menyatakan himpunan, yaitu : a. Enumerasi yaitu menuliskan semua anggota himpunan di antara 2 kurung kurawal. b. Notasi pembentuk himpunan yaitu menuliskan sifat – sifat yang ada pada semua anggota himpunan di antara 2 kurung kurawal. Contoh : 1. A = Himpunan bilangan bulat antara 1 dan 5 2. B = Himpunan yang anggotanya adalah : kucing, meja, buku, air 3. C = Himpunan bilangan riil yang lebih besar daripada 1 Enumerasi Dengan sifat A = { 1, 2, 3 , 4 ,5} A = { x | x Z, 1 x 5 B = { kucing, meja, buku, air } B tidak dapat dinyatakan dengan cara menuliskan sifat – sifatnya karena tidak ada sifat yang sama di antara anggota – anggotanya C tidak bisa dinyatakan dengan menuliskan anggota – anggotanya karena jumlah anggota C yang tak berhingga banyaknya C = { x | x R, x > 1} Jika suatu objek x merupakan anggota dari himpunan A, maka dituliskan x A dan dibaca : “ x adalah anggota A”, atau x ada di dalam A”, atau “x adalah elemen A”. Sebaliknya jika x bukan anggota A, dituliskan x A.
56
Embed
BAB I TEORI HIMPUNAN - viper26.files.wordpress.com · Enumerasi yaitu menuliskan semua anggota himpunan di antara 2 kurung kurawal. b. Notasi pembentuk himpunan yaitu menuliskan sifat
This document is posted to help you gain knowledge. Please leave a comment to let me know what you think about it! Share it to your friends and learn new things together.
Transcript
Foundation of Computer Science 1 1
BAB I
TEORI HIMPUNAN
1.1 Dasar – dasar Teori Himpunan
Definisi : Himpunan adalah kumpulan objek – objek yang berbeda (Liu, 1986) Biasanya dinotasikan dengan huruf besar. Dan objek yang berada di dalamnya disebut elemen / anggota.
1.1.1 Menyatakan Himpunan
Ada 2 cara untuk menyatakan himpunan, yaitu : a. Enumerasi yaitu menuliskan semua anggota himpunan di antara 2 kurung
kurawal. b. Notasi pembentuk himpunan
yaitu menuliskan sifat – sifat yang ada pada semua anggota himpunan di antara 2 kurung kurawal.
Contoh : 1. A = Himpunan bilangan bulat antara 1 dan 5 2. B = Himpunan yang anggotanya adalah : kucing, meja, buku, air 3. C = Himpunan bilangan riil yang lebih besar daripada 1
Enumerasi Dengan sifat
A = { 1, 2, 3 , 4 ,5} A = { x | x Z, 1 x 5
B = { kucing, meja, buku, air } B tidak dapat dinyatakan dengan cara menuliskan sifat – sifatnya karena tidak ada sifat yang sama di antara anggota – anggotanya
C tidak bisa dinyatakan dengan
menuliskan anggota – anggotanya karena jumlah anggota C yang tak berhingga banyaknya
C = { x | x R, x > 1}
Jika suatu objek x merupakan anggota dari himpunan A, maka dituliskan
x A dan dibaca : “ x adalah anggota A”, atau x ada di dalam A”, atau “x adalah elemen A”. Sebaliknya jika x bukan anggota A, dituliskan x A.
Foundation of Computer Science 1 2
B
1.1.2 Diagram Venn
Diagram Venn adalah penyajian himpunan secara grafis. Yaitu suatu himpunan dinyatakan sebagai suatu lingkaran yang diberi nama himpunan
tersebut. Jika perlu anggota- anggota himpunan tersebut dinyatakan sebagai titik – titik di dalamnya. Himpunan A={ a, b }, dengan diagaram Venn disajikan sebagai berikut
Gambar 1. 1
1.1.3 Himpunan Bagian dan kesamaan Himpunan
Jika A dan B adalah himpunan – himpunan , maka A disebut himpunan bagian (subset) dari B bila hanya bila setiap anggota A juga merupakan anggota dari B. dalam hal ini B disebut superset dari A.
A B (( x) x A x B )
Gambar 1. 2
Himpunan A dikatakan sama dengan himpunan B ( ditulis A = B) bila hanya bila setiap elemen A adalah elemen B dan setiap elemen B adalah elemen A.
A = B A B dan B A
a
b
A
Foundation of Computer Science 1 3
S
1.1.4 Himpunan Saling Lepas
Dua himpunan A dan B dikatakan saling lepas (disjoint) jika keduanya tidak memiliki elemen yang sama.
Gambar 1.3
1.1.5 Semesta Pembicaraan dan Himpunan Kosong
Semesta pembicaraan (simbol S atau U) adalah himpunan semua objek yang dibicarakan. Suatu himpunan yang tidak mempunyai anggota disebut himpunan kosong, diberi simbol atau { }. Sifat himpunan kosong : 1. Himpunan kosong adalah himpunan bagian semua himpunan 2. Himpunan kosong adalah tunggal
1.1.6 Kardinalitas
Misalkan A adalah himpunan yang elemen – elemen nya berhingga banyaknya, maka jumlah elemen A disebut kardinal dari himpunan A.
Notasi : n(A) atau |A|
1.1.7 Himpunan yang Ekivalen
Himpunan A dikatakan ekivalen dengan himpunan B jika hanya jika kardinal dari kedua himpunan sama
Notasi : A ~ B |A| = |B |
A B
Foundation of Computer Science 1 4
S
A B
S
A B
1.2 Operasi – operasi terhadap Himpunan
o Gabungan (Union)
Gabungan dua buah himpunan A dan B (ditulis A B) adalah himpunan semua elemen anggota A atau anggota B
A B = { x | x S , x A atau x B }
Gambar 1.4
o Irisan ( Interseksi ) Irisan dua buah himpunan A dan B (ditulis A B) adalah himpunan semua elemen dalam S sedemikian hingga x adalah anggota A dan sekaligus anggota B
A B = { x | x S , x A dan x B }
Gambar 1.5
o Komplemen
Komplemen himpunan A (ditulis Ac atau _
A atau ~ A) adalah himpunan semua elemen x dalam S sedemikian hingga x bukan anggota A. Ac = { x | x S, x A }
Gambar 1.6
S A
Foundation of Computer Science 1 5
S
A B
S
A
B
o Selisih
Selisih himpunan B dari himpunan A (ditulis A - B) adalah himpunan semua elemen dalam S sedemikian hingga x adalah
anggota A tetapi bukan anggota B A - B = { x | x S , x A dan x B }
Gambar 1.7
o Beda Setangkup (Symmetric Difference)
Beda setangkup dari dua buah himpunan A dan B (ditulis A B)
adalah himpunan yang elemennya ada pada A atau B tetapi tidak pada keduanya.
A B = (A B) – ( A B) = (A – B) ( B – A)
Gambar 1.8
Misalkan S adalah semesta pembicaraan dan A, B, C adalah himpunan – himpunan dalam S, maka operasi himpunan memenuhi beberapa hukum berikut :
1. Hukum Komutatif
A B = B A ; A B = B A ; A B = B A
2. Hukum Asosiatif ( A B ) C = A ( B C ) ; ( A B ) A = A ( B A ) ;
( A B ) C = A ( B C )
3. Hukum Distributif ( A B ) C = ( A C ) ( B C ); ( A B ) C = ( A C ) ( B C ) ;
Foundation of Computer Science 1 6
4. Hukum Identitas
A = A ; A S = A ; A = A
5. Hukum Null
A S = S ; A = ; A A =
6. Hukum Komplemen A Ac = S ; A Ac = 7. Hukum Idempoten A A = A ; A A = A 8. Hukum Involusi ( Ac ) c = A 9. Hukum Absorbsi (penyerapan) A ( A B ) = A ; A ( A B) 10 Hukum de Morgan ( A B ) c = Ac Bc ; ( A B) c = Ac Bc 11. Hukum I / O
c = S ; S c =
1.3 Pembuktian – pembuktian Himpunan
Tidak ada metode tertentu yang secara umum dapat digunakan untuk membuktikan pernyataan – pernyataan yang melibatkan himpunan. Tetapi pembuktian dapat dilakukan dengan menggunakan hukum – hukum dalam operasi himpunan, logika atau persamaan – persamaan yang sudah terbukti. Diagram Venn dapat digambar tetapi tidak dapat diterima sebagai bukti.
1.4 Himpunan Kuasa
Misalkan A adalah sembarang himpunan. Himpunan kuasa A (simbol P(A)) adalah himpunan yang anggota – anggotanya adalah semua himpunan bagian A. Jika himpunan A mempunyai n anggota, maka P(A) mempunyai 2n
anggota
1.5 Prinsip Inklusi – Eksklusi
Jika kita ingin menghitung jumlah anggota dari A B ( simbol n(A B) atau |(A B) | maka
|(A B) | = |A| + |B| - |(A B) | sedangkan untuk beda setangkup adalah :
|(A B)| = |A| + |B| - 2|(A B)|
Foundation of Computer Science 1 7
Latihan Soal : 1. Jika A = {a, b, {a,c}, } dan B={a, {a}, d, e}, tentukan himpunan
berikut : a). A – b). A – { } c). {{a,c}} – A d). A B e). {a} – {A} f). P(A – B) g). – A h) B2 i) A (B A)
j). A P(A)
2. Misalkan A adalah himpunan mahasiswa tahun pertama, B adalah himpunan mahasiswa tahun kedua, C adalah himpunan mahasiswa jurusan Arsitektur, D adalah himpunan mahasiswa jurusan Ilmu Komputer, E adalah himpunan mahasiswa yang mengambil mata kuliah Matematika, F adalah himpunan mahasiswa yang pergi menonton film The Aviator, G adalah himpunan mahasiswa yang belajar sampai begadang pada Senin malam lalu.
Nyatakan pernyataan berikut dengan notasi himpunan :
a. Semua mahasiswa tahun kedua jurusan Ilmu Komputer yang mengambil mata kuliah Matematika
b. Hanya mereka yang mengambil mata kuliah Matematika atau yang pergi menonton film The Aviator yang begadang pada Senin malam lalu.
c. Semua mahasiswa tahun kedua yang bukan dari jurusan Arsitektur ataupun jurusan Ilmu Komputer pergi menonton film The Aviator.
3. Di antara bilangan bulat 1-300, berapa banyak yang tidak habis dibagi 3
atau 5 ? 4. Di antara bilangan bulat 1-300, berapa banyak yang habis dibagi 3 tetapi
tidak habis dibagi 5 maupun 7?
5. Di antara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang
mempelajari fisika, 45 orang mempelajari biologi, 15 orang mempelajari matematika dan biologi, 7 orang mempelajari matematika dan fisika, 10 orang mempelajari fisika dan biologi dan 30 orang yang tidak mempelajari satupun di atara ketiga bidang tersebut. a. Hitung banyaknya mahasiswa yang mempelajari ketiga bidang
tersebut. b. Hitung banyaknya mahasiswa yang mempelajari hanya satu di atara
ketiga bidang tersebut.
6. Misalkan A, B dan C adalah himpunan. Tunjukkan bahwa a. (A – B) – C = A – ( B C) b. A (B – C ) = (A B) – (A B)
c. A – (B – C) = (A – B) (A C) d. A – (A B) = A – B e. (A B) – C = (A – C) (B – C) f. (A B) – (A Bc ) = A g. A (B – A) = A B h. A – (B – C) = (A – C) – B i. A (A B)c = A Bc
Foundation of Computer Science 1 8
Bab 2
Induksi Matematika
Induksi matematika adalah cara standar dalam membuktikan bahwa sebuah
pernyataan tertentu berlaku untuk setiap bilangan asli. Pembuktian dengan cara
ini terdiri dari dua langkah, yaitu :
1. Menunjukkan bahwa pernyataan itu berlaku untuk bilangan 1
2. Menunjukkan bahwa jika pernyataan itu berlaku untuk bilangan n,
maka pernyataan berlaku juga untuk bilangan n + 1
Misalkan akan dibuktikan suatu pernyatan bahwa jumlah n bilangan asli pertama,
yaitu 1 + 2 + 3 + . . . + n adalah sama dengan 2
)1(nn. Untuk membuktikan
bahwa pernyataan itu berlaku untuk setiap bilangan asli, langkah – langkah yang
dilakukan adalah sebagai berikut :
1. Menunjukkan bahwa pernyataan tersebut benar untuk n = 1. Jelas
sekali bahwa jumlah 1 bilangan asli yang pertama adalah 2
)11(1 =
1. Jadi pernyataan tersebut adalah benar untuk n = 1.
2. Menunjukkan bahwa jika pernyataan tersebut benar untuk n = k,
maka pernyataan tersebut benar juga untuk n = k + 1. Hal ini bisa
dilakukan dengan cara :
- Mengasumsikan bahwa pernyataan tersebut benar untuk n =
k, yaitu
1 + 2 + 3 + . . . + k = 2
)1(kk
- Menambahkan satu suku pada ruas kiri dan mengganti k
dengan k+1 pada ruas kanan, sehingga
1 + 2 + 3 + . . . + k + (k + 1) = 2
)1)1)((1( kk
= 2
)2)(1( kk
- Substitusikan 2
)1(kk ke ruas kiri
Foundation of Computer Science 1 9
k...321 + (k + 1)
2
)1(kk + (k + 1)
2
)1(2)1( kkk
2
)2)(1( kk (sama dengan ruas kanan)
- Dengan demikian , terbukti
1 + 2 + 3 + . . . + k + (k + 1) = 2
)2)(1( kk
- Jadi pernyataan tersebut benar untuk n = k + 1
3. Dengan induksi matematika dapat disimpulkan bahwa pernyataan
tersebut berlaku untuk setiap bilangan asli n.
Secara formal, Induksi Matematika didefinisikan sebagai berikut :
Definisi 2.1
Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan p(n) yang bisa
benar atau salah. Misalkan
1. p(1) benar
2. Jika p(n) benar, maka p(n+1) benar
Sehingga p(n) benar untuk setiap bilangan asli n
Langkah 1 disebut Basis Induksi , sedangkan langkah 2 disebut Langkah Induksi
Jika pada langkah Induksi yang diasumsikan adalah pernyataan p(i) benar untuk
setiap bilangan i n, maka perumusan induksi matematika seperti ini disebut
Bentuk Kuat Induksi Matematika.
Contoh 2.1
Gunakan induksi matematika untuk membuktikan bahwa 5n – 1 dapat dibagi 4
untuk setiap n 1
Foundation of Computer Science 1 10
Jawab
1. Akan ditunjukkan bahwa 51 – 1 habis dibagi 4 untuk n = 1. Jelas sekali
bahwa 51 – 1 = 5 - 1 = 4 habis dibagi 4
2. Asumsikan bahwa 5n – 1 habis dibagi 4 untuk n = k, yaitu 5k – 1 habis
dibagi 4. Akan ditunjukkan bahwa 5n – 1 juga habis dibagi 4 untuk n =
k + 1, yaitu 5k+1 – 1 habis juga dibagi 4
5k+1 – 1 = 5. 5k – 1
= (1+4) 5k – 1
= 5k + 4.5k – 1
= 5k – 1 + 4.5k
= (5k – 1) + 4.5k
Berdasarkan asumsi, 5k – 1 habis dibagi 4. Sedangkan 4.5k juga habis
dibagi 4. Dengan demikian, 5k+1 – 1 habis dibagi 4. Karena Basis
Induksi dan Langkah Induksi terbukti, maka dapat disimpulkan bahwa 5n
– 1 dapat dibagi 4 untuk setiap n 1.
Foundation of Computer Science 1 11
Latihan
Gunakan induksi matematika untuk membuktikan pernyataan berikut ini benar
untuk setiap n 1
1. 1.2 + 2.3 + 3.4 + . . . + n(n+1) = 2
)2)(1( nnn
2. 12 – 22 + 32 - . . . + (-1)n+1n2 = 2
)1()1(1
nnn
3. 13 + 23 + 33 + . . . + n3 =
2
2
)1(nn
4. 1 + 3 + 5 + . . . + 2n -1 = n2
5. 12 + 22 + 32 + . . . + n2 = 6
)12)(1( nnn
6. 2.1
1 +
3.2
1 + . . . +
)1(
1
nn =
1n
n
7. 3.1
1 +
5.3
1 +
7.5
1+. . . +
)12)(12(
1
nn =
12 n
n
8. 4n – 1 habis dibagi 3
9. 23n – 1 habis dibagi 7
10. 11n – 6 habis dibagi 5
11. 6.7n – 2.3n habis dibagi 4
12. 3n + 7n – 2 habis dibagi 8
Reference:
1. R. Johnsonbaugh, Discrete Mathematics, Fourth Edition, 1997, Prentice
Hall
2. Liu, C.L, Discrete Mathematics, Second Edition, 1986, McGraw-Hill
3. Rinaldi Munir, Matematika Diskrit, Penerbit Informatika Bandung
4. Jong Jek Siang, Drs, Matematika Diskrit dan Aplikasinya pada Ilmu
Komputer, 2002, Penerbit Andi Yogyakarta.
Foundation of Computer Science 1 12
Bab 3
Prinsip Dasar Perhitungan
3.1 Prinsip - prinsip Dasar
Dalam kehidupan sehari-hari, kita sering dihadapkan dengan masalah per
hitungan. Sebagai contoh, sebuah Warung Tegal menyediakan menu yang terdiri
dari 4 jenis makanan, yaitu Nasi Rawon (R), Nasi Soto (S), Nasi Pecel (P) dan
Bakso (B) serta 3 jenis minuman, yaitu Es Jeruk (J), Es Teh (T) dan Es Degan
(D).
Masalahnya, berapa banyak macam hidangan yang berbeda jika dipilih
dari satu jenis makanan dan satu jenis minuman? Masalah di atas merupakan
salah satu contoh masalah diskrit yang biasa dipecahkan dengan cara mendata
semua kemungkinan hidangan yang berbeda yang terdiri dari satu jenis makanan
dan satu jenis minuman, yaitu:
RJ; RT; RD; SJ; ST; SD; PJ; PT; PD; BJ; BT; BD
Sehingga terdapat 12 macam hidangan yang berbeda.
Total jenis hidangan tersebut bisa diperoleh dengan cara mengalikan
banyaknya jenis makanan dengan banyaknya jenis minuman. Teknik perhitungan
yang demikian disebut dengan Prinsip Perkalian. Selain prinsip perkalian,
terdapat teknik perhitungan lain yang bisa digunakan untuk memecahkan
masalah - masalah diskrit, yaitu Prinsip Penambahan. Kedua prinsip ini akan
dijelaskan dalam Subbab berikut ini.
3.2 Prinsip Perkalian
Definisi 3.1
Jika terdapat aktivitas yang terdiri dari t langkah berurutan, dimana langkah 1
bisa dilakukan dalam n1 cara, langkah 2 bisa dilakukan dalam n2 cara, dan
seterusnya sampai langkah ke-t yang bisa dilakukan dalam nt cara; maka
banyaknya aktivitas yang berbeda adalah
n1.n2 … nt
Foundation of Computer Science 1 13
Contoh 3.1
Gunakan prinsip perkalian untuk menghitung masalah banyaknya macam
hidangan yang terdiri 1 jenis makanan dan 1 jenis minuman diatas.
Masalah perhitungan banyaknya macam hidangan yang terdiri satu jenis
makanan dan satu jenis minuman diatas merupakan aktivitas yang terdiri dari 2
langkah, dimana langkah pertama adalah memilih makanan yang bisa dilakukan
dalam 4 cara, dan langkah kedua adalah memilih minuman yang bisa dilakukan
dalam 3 cara, sehingga banyaknya macam hidangan adalah 4.3 = 12.
Contoh 3.2
Berapa banyak cara 3 huruf dapat disusun dari 5 huruf ABCDE ?
a) jika tidak boleh ada pengulangan?
b) jika huruf awalnya A dan tidak boleh ada pengulangan?
c) jika huruf awalnya bukan A dan tidak boleh ada pengulangan?
Jawab :
a) Ada 3 langkah yang harus dilakukan untuk menyusun 3 huruf dari 5 huruf
ABCDE jika tidak boleh ada pengulangan.
Langkah pertama adalah memilih huruf pertama yang bisa dilakukan dalam
5 cara,
Langkah kedua adalah memilih huruf kedua yang bisa dilakukan dalam 4
cara,
Langkah ketiga adalah memilih huruf ketiga yang bisa dilakukan dalam 3
cara. Sehingga banyaknya cara menyusun 3 huruf dari 5 huruf ABCDE jika
tidak boleh ada pengulangan adalah 5.4.3 = 60
b) Ada tiga langkah yang harus dilakukan untuk menyusun 3 huruf dari 5 huruf
ABCDE jika huruf awalnya A.
Langkah pertama adalah memilih huruf pertama yang bisa dilakukan dalam
1 cara,
Langkah kedua adalah memilih huruf kedua yang bisa dilakukan dalam 4
cara, Langkah ketiga adalah memilih huruf ketiga yang bisa dilakukan dalam
3 cara. Sehingga banyaknya cara menyusun 3 huruf dari 5 huruf ABCDE jika
huruf awalnya A adalah 1.4.3 = 12
c) Ada tiga langkah yang harus dilakukan untuk menyusun 3 huruf dari 5 huruf
ABCDE jika huruf awalnya bukan A.
Foundation of Computer Science 1 14
Langkah pertama adalah memilih huruf pertama yang bisa dilakukan dalam
4 cara,
Langkah kedua adalah memilih huruf kedua yang bisa dilakukan dalam 4
cara
Langkah ketiga adalah memilih huruf ketiga yang bisa dilakukan dalam 3
cara. Sehingga banyaknya cara menyusun 3 huruf dari 5 huruf ABCDE jika
huruf awalnya bukan A adalah 4.4.3 = 48
Cara lain adalah banyaknya cara menyusun 3 huruf dari 5 huruf ABCDE
dikurangi dengan banyaknya cara menyusun 3 huruf yang diawali dengan
huruf A, yaitu: 60 - 12 = 48
3.3. Prinsip Penambahan
Definisi 3.2
Misalkan terdapat t himpunan X1, X2, . . . , Xt yang masing-masing mempunyai
n1, n2, . . ., nt anggota. Jika himpunan-himpunan tersebut saling lepas, yaitu Xi
Xj = ; untuk i ≠ j, maka banyaknya anggota yang bisa dipilih dari masing-
masing himpunan tersebut adalah
n1 + n2 + . . . + nt
Contoh 3.3
Berapa banyak untai 4 bit yang diawali dengan digit 10 dan 11?
Jawab :
Untuk menyusun untai 4 bit yang diawali dengan 10 ada dua langkah.
Langkah pertama adalah memilih digit ketiga yang bisa dilakukan dalam 2 cara
(memilih 0 atau 1).
Langkah kedua adalah memilih digit yang keempat yang juga bisa dilakukan
dalam 2 cara. Sehingga banyaknya untai 4 bit yang diawali dengan digit 10
adalah 2.2 = 4. Dengan cara yang sama dapat diperoleh banyaknya untai 4 bit
yang diawali dengan digit 11, yaitu ada 4 untai. Jadi banyaknya untai 4 bit yang
diawali dengan digit 10 dan 11 adalah 4 + 4 = 8
Contoh 3.4
Misalkan dalam sebuah rak terdapat 4 buku Matematika yang berbeda, 3 buku
Biologi yang berbeda dan 2 buku Fisika yang berbeda Berapa banyak cara 2 buku
dengan bidang yang berbeda bisa dipilih dari rak tersebut?
Foundation of Computer Science 1 15
Jawab :
Ada tiga kemungkinan yang bisa terjadi, yaitu 2 buku yang terpilih terdiri dari :
satu buku bidang Matematika dan satu bidang Biologi,
satu bidang Matematika dan satu bidang Fisika; serta
satu bidang Biologi dan satu bidang Fisika.
Dengan menggunakan Prinsip Perkalian, terdapat 4.3 = 12
Cara untuk memilih 2 buku yang terdiri dari satu buku bidang Matematika
dan satu bidang Biologi, terdapat 4.2 = 8
Cara untuk memilih 2 buku yang terdiri dari satu buku bidang Matematika dan
satu bidang Fisika; serta
Terdapat 3.2 = 6 cara untuk memilih 2 buku yang terdiri dari satu buku bidang
Biologi dan satu bidang Fisika.
Karena pemilihan dua buku dari bidang yang berbeda tersebut saling lepas, maka
dengan menggunakan Prinsip Penambahan banyaknya cara 2 buku dengan
bidang yang berbeda bisa dipilih adalah 12 + 8 + 6 = 26
Latihan
3.1 Seorang mahasiswa mempunyai 9 kemeja, 5 celana panjang dan 3 pasang
sepatu. Berapa banyak setelan berbeda yang mungkin bisa dipakai oleh
mahasiswa tersebut?
3.2 Dua buah dadu (merah dan biru) digulirkan.
a) Berapa banyak hasil yang mungkin?
b) Berapa banyak hasil yang ganda (angkanya sama)?
c) Berapa banyak hasil yang tepat satu dadu menunjukkan angka 2?
d) Berapa banyak hasil yang paling sedikit satu dadu menunjukkan angka
2?
3.3. Sebuah panitia yang terdiri dari Ketua, Sekretaris dan Bendahara akan
dipilih dari 6 orang, yaitu Edi, Burhan, Amir, Cahyo, Rina dan Linda.
a) Berapa banyak pemilihan yang tidak melibatkan Linda?
b) Berapa banyak pemilihan yang baik Edi maupun Amir harus masuk
dalam kepanitiaan?
c) Berapa banyak pemilihan dengan Burhan sebagai Ketua?
d) Berapa banyak pemilihan dengan Rina harus masuk dalam kepanitian
dan Cahyo tidak?
Foundation of Computer Science 1 16
3.4. Misalkan terdapat 5 buku Matematika yang berbeda, 3 buku Biologi yang
berbeda dan 2 buku Fisika yang berbeda.
a) Berapa banyak cara buku-buku tersebut bisa diatur dalam sebuah rak?
b) Berapa banyak cara buku-buku tersebut bisa diatur dalam sebuah rak
jika semua buku dari bidang yang sama berada dalam satu kelompok?
c) Berapa banyak cara buku-buku tersebut bisa diatur dalam sebuah rak
jika kelima buku Matematika berada dalam di sebelah kiri?
d) Berapa banyak cara buku-buku tersebut bisa diatur dalam sebuah rak
jika kedua buku Fisika tidak dikumpulkan bersama-sama?
3.5. Berapa banyak cara, paling sedikit dua orang di antara lima orang bisa
mempunyai hari ulang tahun pada bulan yang sama?
Reference:
5. R. Johnsonbaugh, Discrete Mathematics, Fourth Edition, 1997, Prentice
Hall
6. Liu, C.L, Discrete Mathematics, Second Edition, 1986, McGraw-Hill
7. Rinaldi Munir, Matematika Diskrit, Penerbit Informatika Bandung
8. Jong Jek Siang, Drs, Matematika Diskrit dan Aplikasinya pada Ilmu
Komputer, 2002, Penerbit Andi Yogyakarta.
Foundation of Computer Science 1 17
Bab 4
Permutasi dan Kombinasi
Dalam kehidupan sehari-hari kita sering menghadapi masalah pengaturan suatu
obyek yang terdiri dari beberapa unsur, baik yang disusun dengan
mempertimbangkan urutan sesuai dengan posisi yang diinginkan maupun yang
tidak. Misalnya menyusun kepanitiaan yang terdiri dari Ketua, Sekretaris dan
Bendahara dimana urutan untuk posisi tersebut dipertimbangkan atau memilih
beberapa orang untuk mewakili sekelompok orang dalam mengikuti suatu
kegiatan yang dalam hal ini urutan tidak menjadi pertimbangan. Dalam
matematika, penyusunan obyek yang terdiri dari beberapa unsur dengan
mempertimbangkan urutan disebut dengan permutasi, sedangkan yang tidak
mempertimbangkan urutan disebut dengan kombinasi.
4.1. Permutasi Masalah penyusunan kepanitiaan yang terdiri dari Ketua, Sekretaris dan
Bendahara dimana urutan dipertimbangkan merupakan salah satu contoh
permutasi. Jika terdapat 3 orang (misalnya Amir, Budi dan Cindy) yang akan
dipilih untuk menduduki posisi tersebut, maka dengan menggunakan Prinsip
Perkalian kita dapat menentukan banyaknya susunan panitia yang mungkin,
yaitu:
- Pertama menentukan Ketua, yang dapat dilakukan dalam 3 cara.
- Begitu Ketua ditentukan, Sekretaris dapat ditentukan dalam 2 cara.
- Setelah Ketua dan Sekretaris ditentukan, Bendahara dapat ditentukan
dalam 1 cara.
- Sehingga banyaknya susunan panitia yang mungkin adalah 3.2.1 = 6.
Secara formal, permutasi dapat didefinisikan sebagai berikut.
Definisi 4.1
Permutasi dari n unsur yang berbeda x1, x2, . . . , xn adalah pengurutan dari n
unsur tersebut.
Foundation of Computer Science 1 18
Contoh 4.1
Tentukan permutasi dari 3 huruf yang berbeda, misalnya ABC !
Jawab :
Permutasi dari huruf ABC adalah ABC, ACB, BAC, BCA, CAB, CBA.
Sehingga terdapat 6 permutasi dari huruf ABC.
Teorema 3.1
Terdapat n! permutasi dari n unsur yang berbeda.
Bukti.
Asumsikan bahwa permutasi dari n unsur yang berbeda merupakan aktivitas
yang terdiri dari n langkah yang berurutan.
Langkah pertama adalah memilih unsur pertama yang bisa dilakukan dengan n
cara. Langkah kedua adalah memilih unsur kedua yang bisa dilakukan dengan n -
1 cara karena unsur pertama sudah terpilih. Lanjutkan langkah tersebut sampai
pada langkah ke-n yang bisa dilakukan dengan 1 cara. Berdasarkan Prinsip
Perkalian, terdapat n(n-1)(n-2) . . . 2.1 = n! permutasi dari n unsur yang
berbeda.
Contoh 4.2
Berapa banyak permutasi dari huruf ABC ?
Jawab :
Terdapat 3.2.1 = 6 permutasi dari huruf ABC.
Contoh 4.3
Berapa banyak permutasi dari huruf ABCDEF jika subuntai ABC harus selalu
muncul sebagai ABC?
Karena subuntai ABC harus selalu muncul sebagai ABC, maka subuntai ABC bisa
dinyatakan sebagai satu unsur. Dengan demikian terdapat 4 unsur yang
dipermutasikan, sehingga banyaknya permutasi adalah 4:3:2:1 = 24.
Foundation of Computer Science 1 19
Definisi 4.2
Permutasi r dari n unsur yang berbeda x1, x2, . . . , xn adalah pengurutan dari
sub-himpunan dengan r anggota dari himpunan {x1, x2 . . . , xn} . Banyaknya
permutasi r dari n unsur yang berbeda dinotasikan dengan P(n, r).
Contoh 4.4
Tentukan permutasi 3 dari 5 huruf yang berbeda, misalnya ABCDE.
Jawab :
Permutasi 3 dari huruf ABCDE adalah
ABC ABD ABE ACB ACD ACE ADB ADC ADE AEB AEC AED BAC BAD BAE BCA BCD BCE BDA BDC BDE BEA BEC BED CAB CAD CAE CBA CBD CBE CDA CDB CDE CEA CEB CED DAB DAC DAE DBA DBC DBE DCA DCB DCE DEA DEB DEC EAB EAC EAD EBA EBC EBD
ECA ECB ECD EDA EDB EDC Sehingga banyaknya permutasi 3 dari 5 huruf ABCDE adalah 60. Teorema 4.2
Banyaknya permutasi r dari n unsur yang berbeda adalah P(n, r) = )!(
!
rn
n
Bukti. Asumsikan bahwa permutasi r dari n unsur yang berbeda merupakan aktivitas
yang terdiri dari r langkah yang berurutan.
Langkah pertama adalah memilih unsur pertama yang bisa dilakukan dengan n
cara. Langkah kedua adalah memilih unsur kedua yang bisa dilakukan dengan n -
1 cara karena unsur pertama sudah terpilih. Lanjutkan langkah tersebut sampai
pada langkah ke-r yang bisa dilakukan dengan n _ r + 1 cara. Berdasarkan
Prinsip Perkalian, diperoleh
n(n - 1)(n - 2) . . .(n - r + 1) = 1.2...)1)((
1.2...)2)(1(
rnrn
nnn =
)!(
!
rn
n
Jadi P(n, r) = )!(
!
rn
n
Contoh 4.5
Foundation of Computer Science 1 20
Gunakan Teorema 4.2 untuk menentukan permutasi 3 dari 5 huruf yang berbeda,
misalnya ABCDE.
Jawab :
Karena r = 3 dan n = 5 maka permutasi-3 dari 5 huruf ABCDE adalah
P(5, 3) = )!35(
!5 =
!2
!5= 5.4.3 = 60
Jadi banyaknya permutasi 3 dari 5 huruf ABCDE adalah 60.
4.2. Kombinasi Berbeda dengan permutasi yang urutan menjadi pertimbangan, pada kombinasi
urutan tidak dipertimbangkan. Misalnya pemilihan 3 orang untuk mewakili
kelompak 5 orang (misalnya Dedi, Eka, Feri, Gani dan Hari) dalam mengikuti
suatu kegiatan. Dalam masalah ini, urutan tidak dipertimbangkan karena tidak
ada bedanya antara Dedi, Eka dan Feri dengan Eka, Dedi dan Feri. Dengan
mendata semua kemungkinan 3 orang yang akan dipilih dari 5 orang yang ada,
Gunakan Teorema 4.4 untuk menentukan banyaknya cara menyusun huruf - huruf dari kata KAKIKUKAKU Jawab : Diketahui n = 10, n1 = 5, n2 = 2, n3 = 2 dan n4 = 1. Dengan menggunakan Teorema 4.4, diperoleh
!1!2!2!5
!10=
2.2
10.9.8.7.6 = 7560
4.4. Generalisasi Kombinasi
Foundation of Computer Science 1 25
Generalisasi kombinasi merupakan perluasan dari kombinasi yang membolehkan
pengulangan suatu unsur. Misalnya kita ingin memilih 4 kelereng dari sebuah
kantong yang berisi paling sedikitnya 4 kelereng dari masing-masing warna yaitu
merah, biru dan kuning. Kemungkinan terpilihnya 4 kelereng tersebut adalah