DIKTAT PENDUKUNG MATEMATIKA DISKRIT
Ir. Hasanuddin Sirait, MT.
Displin Ilmu Teknik STMIK PARNA RAYA MANADO MANADO
1
PERTEMUAN 1: LOGIKA PROPOSISI Pendahuluan Dalam logika matematika, yang dibicarakan hanyalah proposisi atau pernyataan atau kalimat deklaratif yang artinya kalimat yang bernilai benar atau salah dan tidak sekaligus kedua-duanya. Yang tidak termasuk pernyataan misalnya kalimat harapan, kalimat perintah, kalimat seru dan sebagainya. Beberapa pernyataan merupakan susunan atau gabungan dari pernyataan-pernyataan bagiannya yang dihubungkan oleh beberapa macam konektif (kata hubung logika) misalnya ”dan”, ”atau” dll. dan disebut pernyataan gabungan. Contoh 1. Contoh pernyataan: a. ”New York kota besar” b. ”Paris ibukota negara Inggris” c. ” 1 + 0 = 2. ” 2. Contoh bukan pernyataan: a. ”Semoga kamu lekas sembuh” b. ”Cepat lari!” c. ”Ke mana dia pergi?” d. ”Alangkah cantiknya gadis itu.” e. ”Penduduk kota Jakarta kaya” (tidak dilengkapi kuantor/pembatas penduduk) f. ” x + 5 = 100. ” (untuk x = 95 benar, untuk x ≠ 95 salah, disebut kalimat terbuka) Tabel kebenaran Suatu definisi yang berbentuk tabel yang menunjukkan hubungan antara nilai kebenaran dari setiap pernyataan bagian yang menyusun pernyataan gabungan dengan nilai kebenaran pernyataan gabungan tersebut. Negasi (ingkaran), konjungsi dan disjungsi
q
p
q
p∧q
p∨q
p∨q
B
B
S
S
B
B
S
B
S
S
B
S
B
B
S
B
B
S
S
B
B
S
S
B
B
S
S
S
p
p,q
: pernyataan bagian .
B: benar,
S: salah
2
: ingkaran dari p, q atau ~ q: ingkaran dari q. p atau ~ p p ∧ q : konjungsi dari p dan q dibaca ”p dan q” (pernyataan gabungan). p ∨ q : disjungsi dari p dan q dibaca ”p atau q” (pernyataan gabungan). p ∧ q : bernilai benar hanya untuk keduanya benar. p ∨ q : bernilai salah hanya untuk keduanya salah. p ∨ q : exclusive or dari p dan q dibaca ”p exclusive or q” Implikasi p
q
p→ q
B
B
B
B
S
S
S
B
B
S
S
B
: hipotesis, q : konklusi. : implikasi. : bila p maka q. : bernilai salah hanya untuk p benar dan q salah. : p disebut syarat cukup bagi q. q disebut syarat perlu bagi p.
p → p→ q p→ q p→ q
Konvers, invers, dan kontrapositif dari implikasi : implikasi mula – mula. p→ q
q→ p
: konvers dari p → q , p → q : invers dari p → q .
q→ p
: kontrapositif dari p → q .
p
q
p→ q
q→ p
p→ q
q→ p
p
q
B
B
B
B
B
B
S
S
B
S
S
B
B
S
S
B
S S
B S
B B
S B
S B
B B
B B
S B
sama sama
3
Biimplikasi p↔q
: p bila dan hanya bila q.
q
p→ q
q→ p
( p → q ) ∧ (q → p )
p↔q
B
B
B
B
B
B
B
S
S
B
S
S
S S
B S
B B
S B
S B
S B
p
sama p↔q
: bernilai benar untuk keduanya bernilai kebenaran yang sama, bernilai salah untuk keduanya bernilai kebenaran yang berlainan.
4
PERTEMUAN 2: ALJABAR PROPOSISI Proposisi mempunyai sifat fundamental yang disebut hukum atau formula. Beberapa hukum yang penting kita kelompokkan di bawah ini. 1) Idempoten p ∨ p = p, p ∧ p = p 2) Asosiatif (p ∨ q) ∨ r = p ∨ (q ∨ r), (p ∧ q) ∧ r = p ∧ (q ∧ r) 3) Komutatif p ∨ q = q ∨ p, p ∧ q = q ∧ p 4) Distributif p ∨ (q ∧ r) = ( p ∨ q) ∧ ( p ∨ r) p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r) 5) DeMorgan p ∨ q = p ∧ q, p ∧ q = p ∨ q 6) Identitas p ∨ F = p, p ∧ F = F p ∨ T = T, p ∧ T = p T : Tautologi, F : Kontradiksi 7) Komplemen
p = p, T = F , F = T 8)
p ∨ p = T, p ∧ p = F Absorpsi p ∨ (p ∧ q) = p, p ∧ (p ∨ q) = p
Contoh
1. Bukan pernyataan: a. “Kemana kamu mudik ?”, b. “Semoga dia lekas sadar.”, c. “Cepat keluar!”, d. “Alangkah kayanya saudagar itu.”, e. “Penduduk kota Medan kaya.” f. “x + 2 = 10”. 2. Termasuk pernyataan: a. “Jakarta kota kecil.”, b. “ 2 < 1 dan New York kota besar.”, c. “1 + 0 = 2.”, d. “New Mexico negara bagian dari Amerika Serikat.”
5
3. p : Ali pandai, q : Badu malas. a. p ∧ q : Ali pandai dan Badu malas. b. p ∨ q : Ali pandai atau Badu malas. c. p ∧ q = p ∨ q : Ali tidak pandai atau Badu tidak malas. d. p ∨ q = p ∧ q : Ali tidak pandai dan Badu tidak malas. 4. Buktikan bahwa p → q = p ∨ q dengan membuat tabel kebenaran untuk p → q dan p ∨ q .
6
Solusi p
p
q
p→ q
p ∨q
B
S
B
B
B
B
S
S
S
S
S
B
B
B
B
S
B
S
B
B
5. Buktikan hukum absorpsi, yaitu p ∨ (p ∧ q) = p, p ∧ (p ∨ q) = p dengan membuat tabel kebenaran. Solusi p
q
p∧q
p∨q
p ∨ (p ∧ q)
p ∧ (p ∨ q)
B
B
B
B
B
B
B
S
S
B
B
B
S
B
S
B
S
S
S
S
S
S
S
S
6. Tulislah ingkaran dari pernyataan : a) Ali pandai dan malas. b) Badu kaya atau malas. c) Bila Amir belajar maka dia lulus. d) Mawar berwarna merah bila dan hanya bila violet berwarna biru. Solusi a) Ali tidak pandai atau tidak malas. b) Badu tidak kaya dan tidak malas. c) Amir belajar dan tidak lulus. d) Mawar berwarna merah dan violet tidak berwarna biru atau violet berwarna biru dan mawar tidak berwarna merah. 7. Tulislah konvers, invers, dan kontrapositif dari implikasi : Bila Anna pandai dan rajin maka dia lulus. Solusi Konvers : Bila Anna lulus maka dia pandai dan rajin. Invers : Bila Anna tidak pandai atau tidak rajin maka dia tidak lulus. Kontrapositif : Bila Anna tidak lulus maka dia tidak pandai atau tidak rajin.
7
8. Sederhanakanlah : a) ( p ∨ q) ∧ p , b) Solusi
(p ∨ q )∨ (p ∧ q )
a)
( p ∨ q ) ∧ p = p ∧ ( p ∨ q ) = ( p ∧ p )∨ ( p ∧ q )
b)
(p ∨ q ) ∨ ( p ∧ q ) = ( p ∧ q ) ∨ (p ∧ q ) = p ∧ (q ∨ q )
(
)
= F ∨ p ∧ q = p ∧ q. = p ∧ T = p.
Soal Tentukan tabel kebenaran dari : a) p → ( p ∨ q ), b) ( p ∧ q ) → ( p ∨ q ), c) ( p ∧ q ) ∧ ( q ∨ r ), d) ( p → q ) ∧ ( q → r). 1. Tentukan nilai kebenaran dari : a) Bila 5 < 3 maka -3 < -5. b) ( 2 + 7 = 9 ) ↔ ( 2 + 1 = 5 → 5 + 5 = 8 ). 2. Tulislah konvers, invers, dan kontrapositif dari implikasi : Bila pandai dan sehat maka kaya atau tidak sakit-sakitan. 3. Sederhanakan:
( ( ))
a) p ∧ p ∨ q ∨ q, b) ( p → r ) ∨ (q → r ),
c) ( p → q ) ∧ p.
8
PERTEMUAN 3: PERNYATAAN Proposisi (pernyataan, kalimat deklaratif) Proposisi dapat berarti kalimat yang bernilai benar atau salah dan tidak sekaligus kedua-duanya.Bergantung dengan konteksnya, proposisi dapat berarti suatu pernyataan yang telah dibuktikan kebenarannya, yang tingkatnya lebih rendah dari teorema. Pernyataan gabungan disusun oleh pernyataan-pernyataan bagiannya yang dihubungkan dengan konektif atau kata hubung logika. Dalam logika sehari-hari atau logika di masyarakat, biasanya ada hubungan antara pernyataan-bagian yang menyusun pernyataan gabungan. Tetapi dalam logika matematika antara pernyataan-pernyataan bagian tersebut boleh ada hubungan atau tidak.Pada tabel kebenaran sudah didefinisikan negasi, konjungsi, disjungsi, implikasi dll. sehingga pada umumnya suatu pernyataan yang benar dalam logika sehari-hari juga benar dalam logika matematika, dan suatu pernyataan yang salah dalam logika sehari-hari juga salah dalam logika matematika. Dalam hal ini boleh dikatakan logika matematika lebih luas dari logika sehari-hari. Tautologi dan kontradiksi Tautologi : pernyataan yang selalu bernilai benar. Kontradiksi : pernyataan yang selalu bernilai salah. Ekivalen logis (logical equivalence) Dua pernyataan disebut ekivalen logis atau ekivalen bila tabel-tabel kebenaran dari keduanya sama. Definisi Suatu pernyataan yang disetujui bersama oleh semua pihak yang terlibat. Contoh 1. Bilangan bulat n disebut pembagi dari bilangan bulat m bila m = kn untuk suatu bilangan bulat k. 2. Bilangan bulat positif p > 1 disebut prima bila pembagi positif dari p hanyalah 1dan p. 3. Suatu segitiga disebut samakaki bila dua sisinya panjangnya sama. 4. Pasangan berurutan dari bilangan nyata (real) ( x1 , y1 ) adalah sama dengan pasangan berurutan dari bilangan nyata ( x 2 , y 2 ) bila x1 = x 2 dan y1 = y 2 . 5. Bilangan bulat n disebut genap bila 2 adalah pembagi dari n. 6. Bilangan bulat n disebut ganjil bila n = 2k +1 untuk suatu bilangan bulat k. m 7. Bilangan nyata r disebut rasional (terukur) bila r = dengan m dan n bilangan n bulat dan n ≠ 0 . 8. Suatu segitiga disebut siku- siku bila dua sisinya saling tegaklurus. Terminologi (istilah) matematika 1. Proposisi Suatu pernyataan yang telah dibuktikan kebenarannya.
9
2. Teorema Suatu pernyataan yang sifatnya lebih umum dan lebih penting dari proposisi yang telah dibuktikan kebenarannya. 3. Corollary Suatu pernyataan yang buktinya dengan mudah dapat diturunkan dari suatu teorema atau singkatnya suatu akibat. 4. Lemma Suatu pernyataan yang telah dibuktikan kebenarannya dan digunakan untuk membuktikan teorema. 5. Aksioma Suatu pernyataan yang dapat diterima kebenarannya tanpa bukti. Contoh 1.
2.
Proposisi a) Jumlah sudut- sudut dalam segitiga sembarang adalah 180 o b) Akar-akar persamaan kuadrat ax 2 + bx + c = 0 akan sama dan bernilai real bila b 2 − 4ac = 0. Teorema n
a) Teorema Binomial : ( x + y ) = ∑ n
n! x n − k y k , di mana n bilangan ( ) k ! n − k ! k =0
bulat positif. b) Teorema Fundamental Aritmatika : Setiap bilangan bulat yang lebih besar dari 1 adalah prima atau sebagai hasil kali dari bilangan-bilangan prima. Tanpa memerhatikan urutan, penyajian hasil kali tersebut adalah tunggal (unique). Misalnya 60 = 2 ⋅ 2 ⋅ 3 ⋅ 5 = 5 ⋅ 2 ⋅ 3 ⋅ 2. 3.
Corollary 3
(x + y )3 = ∑
3! x 3− k y k = x 3 + 3 x 2 y + 3 xy 2 + y 3 . k = 0 k !(3 − k )! n n! b) (1 + 1)n = 2 n = ∑ k = 0 k !(n − k )!
a)
4.
Lemma a) Untuk membuktikan Teorema Binomial diperlukan lemma : (n + 1)! = n! n! + . k!(n + 1 − k )! (k − 1)!(n − k + 1)! k!(n − k )! b) Untuk membuktikan Teorema Fundamental Aritmatika diperlukan lemma:
10
Bila p adalah bilangan prima dan p adalah pembagi dari hasil kali a ⋅ b ⋅ c Lt maka p adalah pembagi dari sekurang-kurangnya satu dari bilangan- bilangan a, b, c, L , t 5.
Soal 1. 2. 3. 4.
Aksioma a) Garis lurus ditentukan oleh 2 titik. b) Bidang datar ditentukan oleh 3 titik.
Berikan definisi dari segitiga samakaki yang ekivalen dengan definisi di muka. Berikan dua definisi yang ekivalen dari segitiga samasisi. Berikan definisi-definisi dari fungsi genap dan fungsi ganjil. Berikan contoh-contoh yang lain dari proposisi, teorema, corollary, lemma, dan aksioma.
11
PERTEMUAN 4: ARGUMENTASI DAN KUANTOR ARGUMENTASI Argumentasi adalah penarikan kesimpulan dari sekelompok pernyataan S1 , S 2 , K, S n yang disebut premis yang menghasilkan pernyataan lain S yang disebut konklusi. Argumentasi sedemikian akan ditulis dengan notasi/simbol S1 S2 M Sn __________ ∴ S. Perlu dicatat bahwa argumentasi juga merupakan pernyataan sehingga mempunyai satu nilai kebenaran. Bila suatu argumentasi benar, disebut valid dan bila salah disebut fallacy atau tidak valid. Hukum Silogisme Argumentasi ini valid: p→q q→r __________ ∴ p → r. Hukum modus ponens Argumentasi ini valid: p→q p _________ ∴q Hukum modus tolens: Argumentasi ini valid: p→q ~q ___________ ∴~ p
12
Contoh 1. Tentukan validitas dari argumentasi ini p→q ~ p __________ ∴~ q Solusi Bila p maka q atau (~ p atau q) benar dengan ~ p benar maka dapat disimpulkan q bisa benar atau salah. Jadi ~ q bisa benar atau salah. Jadi argumentasi tersebut tidak valid. 2. Tentukan validitas dari argumentasi ini p↔q q __________ ∴p Solusi p ↔ q benar bila kedua p dan q benar atau salah. Karena q benar maka p juga benar. Jadi argumentasi tersebut valid.
Soal 1. Buktikan bahwa argumentasi di bawah ini valid. p →~ q r→q r __________ ∴~ p
2. Tentukan validitas dari argumentasi di bawah ini. p →q r →~ q __________ ∴r →~ p 3. Tentukan validitas dari argumentasi di bawah ini. p →~ q ~ r →~q __________ ∴ p →~ r
13
4. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid. p →~ q q 5. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid.. p →~ q r→q 6. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid.. p →~ q ~ p→r 7. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid.. p →~ q
~r→ p q
KUANTOR Kuantor adalah notasi yang digunakan untuk menyatakan kuantitas suatu obyek dalam logika matematika. Contoh 1) Kuantor universal : “ ∀ ”, dibaca “semua” atau “setiap”. 2) Kuantor eksistensial : “ ∃ ”, dibaca “beberapa” atau “terdapat paling sedikit satu” atau lebih singkat “terdapat”. “ ∃! “, dibaca “terdapat tepat satu”. Contoh penggunaan Misalkan X suatu himpunan yang tidak kosong. Bila x ∈ X punya sifat/predikat P ditulis P( x ) . 1) “ ∀x ∈ X P( x ) ” , dibaca “Untuk setiap x ∈ X , x bersifat P ”, atau “semua x ∈ X bersifat P ”. 2) “ ∃x ∈ X P(x ) ” , dibaca “ Beberapa x ∈ X bersifat P ”, atau “Terdapat paling sedikit satu x ∈ X yang bersifat P ”. 3) “ ∃! ”, digunakan pada 2) : “ ∃! x ∈ X P(x ) ”, dibaca “Terdapat tepat satu x ∈ X yang bersifat P ”.
14
Contoh dalam negasi 1) ∀x ∈ XP ( x ) = ∃x ∈ X P ( x ), Teorema DeMorgan. 2) 3) 4) 5) 6)
∃x ∈ XP ( x ) = ∀x ∈ X P ( x ), Teorema DeMorgan. ~ (∃x∀y, P( x, y )) = ∀x∃y, ~ P( x, y ) di mana ~ = −. ~ (∀x∃y, P( x, y )) = ∃x∀y, ~ P( x, y ). ~ (∀x∀y, P( x, y )) = ∃x∃y, ~ P( x, y ). ~ (∃x∃y, P( x, y )) = ∀x∀y, ~ P( x, y ).
Contoh dalam definisi 1) Bilangan bulat n adalah bilangan kuadrat bila terdapat bilangan bulat k sedemikian sehingga n = k 2 . 2) Himpunan A tidak kosong bila terdapat elemen a sedemikian sehingga a ∈ A. . 3) Himpunan S dikatakan himpunan bagian dari T bila ∀x, x ∈ S → x ∈ T . 4) Fungsi f : R → R disebut genap bila ∀x ∈ R , f (− x ) = f (x ). 5) Fungsi f : R → R disebut ganjil bila ∀x ∈ R , f (− x ) = − f ( x ). 6) Diketahui himpunan-himpunan A ≠ φ , B ≠ φ , dan A ⊂ B . Himpunan A disebut himpunan bagian sejati dari himpunan B bila ∃b ∈ B dan b ∉ A. Induksi matematika Seringkali kita akan menentukan bahwa suatu proposisi tertentu P(n) adalah benar untuk setiap n ∈ N (atau n = 0,1,2,K atau n = N,N + 1,N + 2,K dengan N ∈ N ) . Misalnya P(n ) : 12 + 2 2 + 3 2 + K + n 2 = n(n + 1)(2n + 1) 6 atau
n
∑k
2
k =1
= n(n + 1)(2n + 1) 6 . Untuk membuktikannya, digunakan Prinsip Induksi
Matematika. Prinsip induksi matematika Untuk membuktikan bahwa P(n ) benar untuk n ∈ N : 1) Buktikan P(1) benar. 2) Asumsikan P(n ) benar, buktikan P(n + 1) benar. Contoh n
1. Buktikan
∑ k = n (n + 1) 2, k =1
Solusi •
1
∑ k = 1 = 1(1 + 1) 2, , jadi P(1) benar atau untuk n = 1 ruas kiri = ruas kanan. k =1
15
•
Asumsikan P(n ) benar, yaitu
n
∑ k = n(n + 1) 2 benar.
Dibuktikan P(n + 1)
k =1
n +1
benar, yaitu
∑ k = (n + 1)(n + 2) 2 . k =1
∑ k = ∑ k + n + 1 = n (n + 1) 2 + n + 1 = (n n +1
n
k =1
k =1
(
2
)
+ n 2 + (2n + 2 ) 2
)
= n 2 + 3n + 2 2 = (n + 1)n (n + 2) 2 , Jadi P(n + 1) benar Catatan: P(1) benar: pangkal, P(n + 1) benar : konklusi induksi, Asumsi P(n ) benar : hipotesis induksi. n
2. Buktikan
∑k
2
= n(n + 1)(2n + 1) 6 .
2
= 1 = 1 = 1(1 + 1)(2 ⋅ 1 + 1) 6, jadi P(1) benar.
k =1
Solusi •
1
∑k k =1
•
Asumsikan P(n ) benar. n +1
n
k =1
k =1
∑ k 2 =∑ k 2 + (n + 1)
2
= n(n + 1)(2n + 1) 6 (n + 1) = n(n + 1)(2n + 1) 6 + 6 (n + 1) 6 2
2
n +1 (n(2n + 1) + 6(n + 1)) = n + 1 2n 2 + 7n + 6 = n + 1 (n + 2)(2n + 3) 6 6 6 = (n + 1)(n + 2)(2n + 3) 6 , jadi P(n + 1) benar.
(
=
k
= a (r n +1 − 1) (r − 1), r < 1, a ∈ R
k
=ar 0 = a = a r 1 − 1 (r − 1) , jadi P (0) benar.
n
3. Buktikan
∑ ar
)
k =0
Solusi •
0
∑ ar k =0
(
)
n +1
∑ ar k =0
•
Asumsikan P(n ) benar. = a
(r
n
k
= ∑ ar k + ar n +1 k =0
− 1) ( r n +1 − 1) (r n + 2 − r n +1 ) n +1 + ar = a + (r − 1) (r − 1) (r − 1) n +1
= a (r n + 2 − 1) (r − 1), jadi P(n + 1) benar. 4. Buktikan Rumus DeMoivre : (cos α + i sin α )n = cos (nα ) + i sin (nα ), n ∈ N
16
Solusi • •
(cos α + i sin α )1 = cos(1 ⋅ α ) + i sin (1 ⋅ α ), jadi P(1) benar. Asumsikan P(n ) benar. Maka, (cos α + i sin α )n+1 = (cos α + i sin α )n (cos α + i sin α )1 = (cos(nα ) + i sin (nα ))(cos α + i sin α ) = (cos(nα ) cos α + i sin (nα ) sin α ) + i(cos(nα ) sin α + sin (nα ) cos α ) = (cos(nα ) cos α − sin (nα ) sin α ) + i(sin (nα ) cos α + cos(nα )sin α ) = cos(nα + α ) + i sin (nα + α ) = cos((n + 1)α ) + i sin ((n + 1)α ), jadi P(n + 1) benar.
Soal n
1) Buktikan
∑k
= n (n + 1)
3
2
k =1
2
2
n 4 = ∑ k , n ∈ N. k =1 n −1
1 n n −1 1 1 2) Buktikan 1 + 1 + L 1 + , n = 2,3,4,K = (n − 1)! 1 2 n −1 3) Buktikan 1 ⋅ 2 + 2 ⋅ 3 + 3 ⋅ 4 + K + n(n + 1) = n(n + 1)(n + 2) 3 , n ∈ N. 1
2
n−k
n
4) Buktikan Rumus Binomial : ( x + y ) = ∑
n! xy k , n ∈ N. ( ) k ! n − k ! k =0 Sesuai pada Teorema Binomial, buktikan dulu lemma: (n + 1)! = n! n! + . k!(n + 1 − k )! (k − 1)!(n − k + 1)! k!(n − k )! 5) Diketahui fungsi f : N → N dengan sifat ∀x, y ∈ N, f ( xy ) = f ( x ) + f ( y ). n
Buktikan bahwa ∀a ∈ N ∀n ∈ N f (a n ) = nf (a ).
6) Diketahui fungsi f : N → N dengan sifat ∀x, y ∈ N, f ( x + y ) = f ( x ) f ( y ). Buktikan bahwa f (n ) = ( f (1)) , ∀n ∈ N . n
7) Buktikan bahwa ∀n ∈ N ∀x ≠ 1
) (
)
n +1
2 (1 + x ) 1 + x 1 + x L 1 + x = 1 − x . 1− x 8) Buktikan bahwa ∀n ∈ N ∀x, y ∈ R : x − y adalah pembagi dari x n − y n
(
2
)(
4
2n
9) Buktikan bahwa ∀n ∈ N 6 adalah pembagi dari n 3 − n . 10) 11)
Buktikan bahwa ∀n ∈ N 9 adalah pembagi dari n 3 + (n + 1)3 + (n + 2 )3 . Buktikan bahwa untuk n = 5,6,7, K : 2 n > n + 20 .
12)
Buktikan bahwa ∀n ∈ N :
n
∑k k =1
4
(
)
= n(n + 1) 6n 2 + 9n 2 + n − 1 30.
17
PERTEMUAN 5: HIMPUNAN Suatu himpunan adalah suatu kumpulan dari obyek-obyek. Obyek-obyek tersebut dinamakan anggota-anggota atau elemen-elemen dari himpunan. Bila A adalah suatu himpunan dan x adalah suatu elemen dari A, ditulis x ∈ A . Bila x bukan elemen dari A, ditulis x ∉ A . Himpunan yang elemen-elemennya hanya a, b, c ditulis {a, b, c}. Himpunan dari semua x yang punya sifat P ditulis {x x punya sifat P}.
Dua himpunan A dan B sama, ditulis A = B, bila : ∀x x ∈ A ↔ x ∈ B . Himpunan A disebut himpunan bagian dari B, ditulis A ⊂ B , bila setiap anggota dari A adalah juga anggota dari B. Himpunan yang tidak punya anggota, ditulis φ atau { }, adalah himpunan bagian dari himpunan sebarang. φ disebut juga himpunan kosong. Definisi 1) Produk (kartesius) dari A dan B, ditulis A × B, adalah :
A × B = {(a, b ) a ∈ A dan b ∈ B}
2) Gabungan atau union dari A dan B, ditulis A ∪ B, adalah : A ∪ B = {x x ∈ A atau x ∈ B}. 3) Irisan atau intersection dari A dan B, ditulis A ∩ B , adalah : A ∩ B = {x x ∈ A dan x ∈ B}. 4) Selisih dari A dan B, ditulis A \ B adalah : A \ B = {x | x ∈ A dan x ∉ B}. 5) Himpunan kuasa dari A, ditulis P( A) , adalah :
P( A) = {x adalah himpunan bagian dari A}.
Contoh Misalkan A = {1, 2}, B = {1, 2, 3}, maka : A × B = {(1,1), (1,2), (1,3), (2,1), (2,2 ), (2,3)},
A × B = {(2,1), (2,2 ), (2,3), (1,1), (1,2), (1,3)};
1) A × A = {(1,1), (1,2), (2,1), (2,2 )}; A × φ = φ , φ × A = φ ;
B × A = {(1,1), (1,2), (2,1), (2,2 ), (3,1), (3,2)}; B × B = {(1,1), (1,2), (1,3), (2,1), (2,2 ), (2,3), (3,1), (3,2 ), (3,3)} 2) A ∪ B = {1,2,3}, A ∩ B = {1,2}, A ∪ φ = A, B ∩ φ = φ . 3) A − B = φ , B − A = {3}, A − φ = A, φ − B = φ . 4) P( A) = {φ , {1}, {2}, {1,2}}, P(φ ) = {φ }.
18
Aljabar dari himpunan, dualitas Untuk U adalah himpunan semesta, φ adalah himpunan kosong, A, B, C adalah himpunan sembarang, berlakulah huku-hukum di bawah ini.
1a.
A∪ A = A
Hukum Idempoten 1b. A ∩ A = A
Hukum Asosiatif 2a. ( A ∪ B) ∪ C = A ∪ ( B ∪ C ) 2b. ( A ∩ B) ∩ C = A ∩ ( B ∩ C ) 3a. A ∪ B = B ∪ A
Hukum Komutatif 3b. A ∩ B = B ∩ A
Hukum Distributif 4a. A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ) 4b. A ∩ ( B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) Hukum Identitas 5b. A ∩ U = A 6b. A ∩ φ = φ
5a. A ∪ φ = A 6a. A ∪ U = U
Hukum Involusi 7. ( A c ) c = A
8a. A ∪ A = U 9a. U c = φ c
10a. ( A ∪ B) c = A c ∩ B c
Hukum Komplemen 8b. A ∩ A c = φ 9b. φ c = U Hukum DeMorgan 10b. ( A ∩ B) c = A c ∪ B c
Bukti Sebagaicontoh, kta buktikan Hukum DeMorgan ( A ∪ B) c = A c ∩ B c : x ∈ ( A ∪ B ) c bhb x ∉ ( A ∪ B bhb tidak benar bahwa ( x ∈ A atau x ∈ B )bhb ( x ∉ A
dan x ∉ B ) bhb ( x ∈ A c dan x ∈ B c )bhb x ∈ ( A c ∩ B c ) . Soal 1. Buktikan 2. Buktikan
3. Buktikan 4. Buktikan
a. A ∪ B = B ∪ ( A \ B) b. B ∩ ( A \ B) = φ . a. A = ( A \ B) ∪ ( A ∩ B ) b. ( A \ B) ∩ ( A ∩ B) = φ . c a. A ⊂ B bhb A ∩ B = φ b. A ⊂ B bhb A c ∪ B = U . a. A ⊂ B bhb B c ⊂ A c b. A ⊂ B bhb A \ B = φ .
19
5. Formula A \ B = A ∩ B c memberikan definisi operasi beda dinyatakan dengan operasi interseksi dan komplemen. Carilah formula yang memberikan definisi A ∪ B dinyatakan dengan operasi interseksi dan komplemen. 6. Suatu survei dari 100 mahasiswa, diperoleh data statistik sebagai berikut: 22 belajar matematika, 20 belajar fisika, 45 belajar biologi, 15 belajar matematika dan biologi, 7 belajar matematika dan fisika, 10 belajar fisika dan biologi, 40 tidak belajar apa-apa. a. Tentukan banyaknya mahasiswa yang belajar ketiga pelajaran tersebut. b. Tentukan banyaknya mahasiswa yang hanya belajar satu pelajaran saja. 7. Yang dimaksud dengan beda simetrik dari himpunan-himpunan A dan B adalah himpunan A∆B = ( A ∪ B) \ ( A ∩ B). a. Buktikan sifat asosiatif dari beda simetrik, yaitu A∆( B∆C ) = ( A∆B)∆C. b. Buktikan sifat kanselasi dari beda simetrik, yaitu bila A ≠ φ dan A∆B = A∆C maka B = C. c. Buktikan sifat distributif dari beda simetrik, yaitu A ∩ ( B∆C ) = ( A ∩ B )∆( A ∩ C ). 8. Buktikan bahwa A ∩ ( B \ C ) = ( A ∩ B ) \ ( A ∩ C ) 9. Carilah contoh yang menunjukkan bahwa A ∪ ( B \ C ) ≠ ( A ∪ B) \ ( A ∪ C ) . 10. Dari 60 mahasiswa yang belajar bahasa Inggris diketahui bahwa: 30 mahasiswa pernah belajar bahasa Perancis, 48 mahasiswa pernah belajar bahasa Jerman, 20 mahasiswa pernah belajar bahasa Latin, 22 mahasiswa pernah belajar bahasa Perancis dan bahasa Jerman, 18 mahasiswa pernah belajar bahasa Jerman dan bahasa Latin, 10 mahasiswa pernah belajar ketiga bahasa tersebut, dan 6 mahasiswa tak pernah belajar satu pun dari ketiga bahasa tersebut. Tunjukkan bahwa terdapat kesalahan pada data di atas.
20
PERTEMUAN 6: RELASI Relasi Bila A dan B adalah himpunan, yang dimaksud relasi dari A ke B adalah suatu himpunan bagian dari A × B . Fungsi Fungsi A ke B adalah suatu relasi dari A ke B sedemikian sehingga untuk setiap a ∈ A terdapat satu dan hanya satu b ∈ B dimana (a, b) ∈ f. Bila untuk setiap a ∈ A terdapat paling banyak satu b ∈ B dimana (a, b) ∈ f, f disebut fungsi parsial. Himpunan A disebut domain dari fungsi f dan himpunan B disebut range dari fungsi f. Bila (a, b) ∈ f, b = f(a) yaitu nilai dari f di a. Definisi 1) Fungsi f : A → B disebut surjektif atau onto bila : ∀b ∈ B∃a ∈ A ∋ f (a ) = b. 2) Fungsi f : A → B disebut injektif atau satu-ke-satu bila : ∀a, a ' ∈ A a ≠ a ' → f (a ) ≠ f a ' atau ∀a, a ' ∈ A f (a ) = f a ' → a = a ' . . 3) Fungsi f : A → B disebut bijektif bila : f surjektif dan sekaligus injektif. 4) Image dari fungsi f : A → B adalah : f ( A) = { f ( x ) : x ∈ A}.
[
( )]
[
( )
]
Contoh Misalkan A = {a, b, c}dan B = {a, b, c, d }, maka : 1) f = {(a, b ), (b, b ), (c, d )} ⊆ A × B adalah fungsi dari A ke B , dengan f (a ) = b, f (b ) = b, f (c ) = α . . f ( A) = image dari fungsi f = {b, d } ⊆ B. 2) f = {(a, b ), (b, b ), (c, d )} ⊆ B × B hanyalah relasi dari B ke B dan bukan fungsi dari B ke B . Relasi f ini merupakan fungsi parsial dari B ke B . 3) Fungsi P : A → {B, S }disebut predikat pada himpunan A. Misalnya ω (omega) = {0,1,2, K}, dapat didefinisikan fungsi P : ω → {B, S }sebagai predikat pada ω dengan BENAR bila n ganjil P(n ) = SALAH bila n genap. Soal 1)
Diketahui A = {1,2}, B = {2,3,4},V = {a, b, c}, W = {b, c, d }. a) Carilah : A × B, A × V , A ∪ V , B ∩ W , A × φ , P(V ). b) Carilah : A − B, B − A, A − A, V − W , P(B − A), P(V − φ )
21
Yang manakah relasi-relasi dari A ke B di bawah ini merupakan fungsi ? A = {1,2}, B = {2,3,4}. a) {(1,3), (2,4)} b) {(1,3), (1,4)} c) {(1,3), (1,3)}, {(2,2), (1,4)}
2)
Apakah {(1,2), (2,3)} merupakan fungsi : a) dari {(1,2) ke (2,3)}? b) dari N ke N ? c) dari {(1,2)} ke N ? d) dari {(1,2,3)} ke {(2,3)} ?
3)
Relasi sebagai graph Relasi R dari A ke B adalah himpunan bagian dari A × B . Relasi R dapat disajikan dengan diagram sebagai berikut : Tulis elemen-elemen dari A pada satu garis dan tulis juga elemen-elemen dari B pada satu garis lain. Untuk setiap (a, b ) ∈ R , gambar panah dari titik a ke titik b. Penyajian ini disebut bipartite graph representation dari R, dengan contoh sebagai berikut : a
x
b
y
c
z
A = {a, b, c, d }, B = {x, y, z} R = {(a, x ), (a, y ), (b, y ), (c, x ), (c, z ), (d , z )}.
d Bila A = B dapat digunakan penyajian lain dari R yang lebih menarik. Penyajian ini disebut directed graph representation. Untuk menyajikan R ⊆ A × A , gambar diagram dengan satu titik untuk setiap elemen dari A; untuk setiap ( x, y ) ∈ R gambar panah dari titik x ke titik y. Titik-titik disebut nodes atau vertices, sedang panah-panah disebut edges. Hal ini digambarkan sebagai berikut :
22
a
b
d
b a
c
c
d A = {a, b, c, d }
R = {(a, b ), (b, c ), (b, d ), (b, a ), (c, c ), (d , a )}.
A = {a, b, c, d }
R = {(a, a ), (a, b ), (a, c ), (b, c ), (d , d )}.
Bila x suatu node, banyaknya panah yang menuju x disebut in-degree ; sedangkan banyaknya panah yang berasalah dari x disebut out-degree. Definisi 1) 2) 3)
Relasi R pada A disebut refleksif bila ∀a ∈ A, (a, a ) ∈ R Relasi R pada A disebut simetrik bila : ∀x, y ∈ A[( x, y ) ∈ R → ( y, x ) ∈ R] Relasi R pada A disebut transitif bila : ∀x, y ∈ A[( x, y )( y, z ) ∈ R → ( x, z ) ∈ R]
Bila relasi R simetrik, dapat digambarkan penyajian ke tiga dari R yang tidak memerlukan arah panah, disebut undirected graph representation.
23
Relasi R refleksif
Relasi R simetrik
Relasi R tidak refleksif
Relasi R tidak simetrik
Relasi R transitif
24
Undirected grah representation dari relasi simetrik R diatas
Relasi R : refleksif, simetrik dan transitif
Misalkan relasi R pada A adalah transitif dan (a1 , a 2 ), (a 2 , a3 ), (a3 , a 4 ) adalah panah-panah
dalam R . Dengan sifat transitif, didapat : (a1 , a 3 ) ∈ R , sehingga juga didapat (a1 , a 4 ) ∈ R .
Definisi Misalkan R ⊆ A × A adalah suatu relasi. Yang dimaksud dengan path dari a ke b dalam R adalah barisan a0 , a1 , K, a n sedemikian sehingga,
n ≥1 ∀i, ai ∈ A dengan i = 0,1,K, n (iii) a 0 = a, a n = b (iv) ∀i, (ai , ai +1 ) ∈ R dengan i = 0,1, K , n − 1 Bila a 0 = a n , path di atas disebut cycle. Bilangan n disebut panjang dari path di atas. Suatu graph tanpa cycles disebut acyclic. (i) (ii)
Proposisi Relasi R transitif bhb untuk setiap path dari a ke b berada di dalam R maka terdapat edge (a, b ) yang berada di dalam R . 1)
2)
3)
Misalkan A = {a, b, c, d , e}dan relasi R pada A adalah : R = {(a, b ), (a, c ), (b, a ), (c, a ), (c, d ), (c, e ), (d , c ), (e, c )}. a. Gambarkan bipartite graph representation dari R . b. Gambarkan directed graph representation dari R . c. Cek apakah R refleksif, simetrik atau transitif. Misalkan R = {(a, a )}, A = {a}, B = {a, b}. Apakah R ⊆ A × A refleksif ? Apakah R ⊆ B × B refleksif ? Gambarkan kedua relasi tersebut sebagai bepartite graphs dan directed graphs. Pandang undirected graph ini :
25
Sajikan graph ini sebagai suatu relasi. 4) Gambarlah suatu directed graph yang simetrik dan transitif, tetapi tidak refleksif. 5) Suatu relasi yang refleksif, simetrik dan transitif disebut relasi ekivalen. Berikan deskripsi dari directed graph dari relasi ekivalen. 6) Misalkan A = {a}, B = {a, b}. a. Daftar semua relasi R ⊆ A × A . b. Daftar semua relasi R ⊆ B × B . c. Dari relasi-relasi dalam a. dan b. , mana yang refleksif, simetrik, transitif?
Relasi ekivalen Suatu relasi yang refleksif, simetrik dan transitif disebut relasi ekivalen. Definisi Misalkan R ⊆ A × A adalah suatu relasi ekivalen dan misalkan a ∈ A . Klasekivalen dari a terhadap R, ditulis [a]R , adalah
[a]R
{
(
) }
= a ' ∈ A a, a ' ∈ R , disingkat [a] .
Teorema Bila R adalah relasi ekivalen pada A , dan a, b ∈ A , maka : (i) bila (a, b ) ∈ R maka [a] = [b] . (ii) bila (a, b ) ∉ R maka [a ] ∩ [b] = φ . (iii) [a] = [b] atau [a] ∩ [b] = φ .
Graph dari relasi ekivalen
26
Definisi Bila R adalah relasi ekivalen pada A, maka yang disebut quotient set A R adalah A R = {[a]R | a ∈ A}. Definisi Misalkan A adalah suatu himpunan. Himpunan bagian ∏ dari P(A) disebut partisi dari A bila setiap S ∈ ∏ adalah tidak kosong dan untuk setiap a ∈ A , terdapat tepat satu S ∈ ∏ sedemikian sehingga a ∈ S .
∏ 1 = {{1}, {4}, {2,3}} ⊆ P( A)
= partisi dari A dimana A = {1,2,3,4}
4
∏ 2 = {{1}, {2}, {3}, {4}} ⊆ P ( A) = partisi dari A.
3
2
Teorema Himpunan bagian ∏ dari P(A) merupakan partisi pada A bhb ∏ = A R untuk suatu relasi ekivalen R pada A. 1 2
A = {1,2,3} R = {{1,1}, {1,2}, {2,1}, {2,2}, {3,3}} [1]R = {1,2}, [3]R = {3}
[2]R = {1,2}, A R = {{1,2}, {3}} 3 Soal 1)
Diketahui A = {x ∈ ω 1 ≤ x ≤ 6}dan R suatu relasi dari pada A di mana
R = {(x, y ) x − y kelipatan dari 3}.
Buktikan bahwa R adalah relasi ekivalen dan carilah A R . 2)
Diketahui A = {x ∈ ω 1 ≤ x ≤ 8}dan R suatu relasi dari pada A di mana
{
}
R = ( x, y ) x = 2 i k dan y = 2 i k ' , dan k, k ' ganjil .
Buktikan bahwa R adalah relasi ekivalen dan carilah A R .
27
3)
Misalkan A dan B adalah himpunan dan f : A → B suatu fungsi. Didefinisikan : Ker( f ) = kernel dari f = {( x, y ) x, y ∈ A dan f ( x ) = f ( y )}.
Buktikan bahwa untuk f sebarang, Ker( f ) adalah relasi ekivalen.
4) Buktikan : Bila R adalah relasi ekivalen pada A, terdapatlah himpunan B dan fungsi f : A → B sedemikian sehingga R = Ker( f ). Komposisi relasi Misalkan A, B, dan C adalah himpunan-himpunan. Misalkan juga R adalah relasi dari A ke B dan S adalah relasi dari B ke C. Jadi dari definisi relasi, R adalah himpunan bagian dari A × B dan S adalah himpunan bagian dari B × C. Dibentuk relasi komposisi dari R dan S, yaitu (R o S ) dari A ke C yang didefinisikan sebagai R o S = {(a, c) : ∃ b ∈ B aRb & bSc} ⊆ A × C. Kadang-kadang relasi R o S dasingkat RS. Contoh 1. Misalkan A = {1, 2, 3, 4}, B = {a, b, c, d } , dan C = {x, y, z} . Misalkan juga R = {(1, a ), (2, d ), (3, a ), (3, b), (3, d )}, S = {(b, x), (b, z ), (c, y ), (d , z )}.
Maka 2( R o S ) z & 3( R o S ) x, karena 2 Rd dan dSz, serta 3Rb & bSx. Juga didapat 3( R o S ) z karena 3Rd & dSz. Dapat disimpulkan R o S = {(2, z ), (3, x), (3, z )}. Teorema Misalkan A, B, C, D adalah himpunan-himpunan. Misalkan juga R adalah relasi dari A ke B, S relasi dari B ke C, dan T relasi dari C ke D. Maka ( R o S ) o T = R o ( S o T ). Invers relasi Misalkan R adalah relasi dari A ke B. Yang dimaksud dengan invers relasi dari R, ditulis R −1 adalah relasi dari B ke A dengan R −1 = {(b, a ) : (a, b) ∈ R}. Contoh 1. Misalkan A = {1,2,3} dan R adalah relasi pada A di mana R = {(1,2), (1,3), (2,3)}, maka
R −1 adalah juga relasi pada A dengan R −1 = {(2,1), (3,1), (3,2)}.
2. Invers dari relasi ”x adalah suami y” adalah relasi ”y adalah isteri x”.
28
PERTEMUAN 7 : FUZZY SET Pendahuluan Misalkan X merupakan himpunan semesta. Yang dimaksud dengan himpunan kabur atau fuzzy set A adalah dikarakterisir dengan fungsi karakteristik yang diperumum atau fungsi keanggotaan µ A dari X ke selang tertutup [0,1]. Contoh 1. Misalkan X adalah himpunan dari semua pabrik mobil. Himpunan kabur A dikarakterisir dengan fungsi keanggotaan di mana µ A : X → [0,1] ∀x ∈ X µ A (x) adalah prosentase mobil x digunakan di Jakarta. 2. Misalkan himpunan semesta X adalah himpunan dari semua mahasiswa yang mengambil mata kuliah Matematika Diskrit K0144. Himpunan kabur B dikarakterisir dengan fungsi keanggotaan µ B : X → [0,1] di mana ∀x ∈ X µ A (x) adalah IPK x dibagi 4. 3. Misalkan X adalah himpunan semesta. Himpunan biasa atau crisp set C dapat dikarakterisir dengan fungsi keanggotaan fungsi karakteristik biasa pada C. Ingat bahwa fungsi karakteristik biasa pada C atau χ C adalah fungsi dari X ke selang 1, x ∈ C tertutup [0, 1] dengan χ C ( x) = 0, x ∉ C.
Dua himpunan kabur A dan B disebut sama, ditulis A = B, bila dan hanya bila µ A = µ B . Bila himpunan semesta U = {u1 , u 2 , u 3 , K, u n } berhingga, himpunan kabur D, misalnya dapat ditulis sebagai u1 u2 u3 Kun D: a1 a2 atau sebagai “jumlah”
a3 K an
D = ∑ µ D (u ) / u u∈U
atau dengan notasi D = a1 / u1 + a 2 / u 2 + a3 / u 3 L + a n / u n
Himpunan (kabur) kosong dan himpunan(kabur) semesta Misalkan X adalah himpunan semesta.Himpunan kabur kosong φ dikarakterisir dengan fungsi keanggotaan fungsi nol dari X yaitu ∀x ∈ X : µ φ ( x) = 0, sedangkan himpunan
kabur semesta dikarakterisir dngan fungsi keanggotaan µ X ( x) = 1∀x ∈ X .
29
Support dari himpunan kabur Misalkan X adalah himpunan semesta. Support dari himpunan kabur A: supp ( A) = {x ∈ X | µ A ( x) > 0}. Untuk himpunan kabur A dengan penulisan x1 x 2 x3 x 4 x5 x6 x 7 x8 A: 0,1 0,2 0 0,4 0,6 0,8 0,9 1 maka supp ( A) = {x1 , x 2 , x4 , x5 , x6 , x7 , x8 } = X − {x3 }. α cut dari himpunan kabur Misalkan X adalah himpunan semesta. Untuk α ∈ [0,1], yang dimaksud dengan α − cut dari himpunan kabur A adalah Aα = {x ∈ X | µ A ( x) ≥ α .} Untuk himpunan kabur A dengan penulisan x1 x 2 x3 x 4 x5 x6 x 7 x8
A: 0,1 0,2 0 0,4 0,6 0,8 0,9 1 maka 0,4 − cut dari himpunan kabur A adalah {x 4 , x5 , x6 , x7 , x8 }. Inklusi untuk himpunan kabur Diberikan dua himpunan kabur A dan B dari himpunan semesta X. Himpunan A disebut himpunan bagian dari himpunan B ditulis A ⊂ B bila µ A ( x) ≤ µ B ( x) ∀x ∈ X . Operasi himpunan kabur Diberikan dua himpunan kabur A dan B dari himpunan semesta X. Gabungan A ∪ B dari himpunan-himpunan kabur A dan B dikarakterisir dengan fungsi keanggotaan µ A∪ B ( x) = maks {µ A ( x), µ B ( x)}∀x ∈ X , sedangkan irisan A ∩ B dari himpunan-himpunan kabur A dan B dikarakterisir dengan fungsi keanggotaan µ A∩ B ( x) = min{µ A ( x), µ B ( x)}∀x ∈ X . Untuk komplemen A c dari himpunan kabur A dikarakterisir dengan fungsi keanggotaan µ Ac ( x) = 1 − µ A ( x) ∀x ∈ X . Soal Misalkan himpunan semesta adalah X = [0,1] = {x ∈ R | 0 ≤ x ≤ 1.} Himpunan-himpunan kabur A, B dan C berturut-turut dikarakterisir oleh fungsi-fungsi keanggotaan µ A ( x) = x ∀x ∈ X , µ B ( x) =| x − 0,5 | ∀x ∈ X , µ B ( x) = 1− | x − 0,5 | ∀x ∈ X . Dengan menggambarkan kurva fungsi keanggotaannya, 1. Tentukan himpunan kabur A ∪ B. 2. Tentukan himpunan kabur A ∩ B. 3. Tentukan himpunan kabur A c . 4. Tentukan himpunan kabur A ∩ C.
30
5. Tentukan himpunan kabur 6. Tentukan himpunan kabur 7. Tentukan himpunan kabur 8. Tentukan himpunan kabur
B ∩ C. Bc. B ∪ C. Cc.
31
PERTEMUAN 12: POSET (PARTIALLY ORDERED SET) Definisi Poset Relasi R pada himpunan S disebut partial order atau urutan parsial pada S bila R adalah: (1) refleksif, yaitu: aRa untuk setiap a di dalam S. (2) Antisimetrik, yaitu: ∀a,b∈S, bila aRb dan bRa maka a = b. (3) Transitif, yaitu: ∀a,b,c ∈S, bila aRb dan bRc maka aRc. Suatu himpunan S bersama partial order atau urutan parsial disebut suatu partially ordered set (himpunan terurut parsial) atau poset. Biasanya kita menggunakan relasi urutan parsial dengan simbol ≤, dan a ≤ b dibaca a mendahului b atau b melampaui a.
Contoh a. Misalkan S adalah himpunan dari himpunan-himpunan atau keluarga dari himpunanhimpunan. Diadakan relasi inklusi (termuat) ⊂ pada S. 1. Jelas bahwa A ⊂ A untuk setiap anggota dari S, sehingga relasi inklusi ⊂ merupakan relasi refleksif pada S. 2.Bila A ⊂ B & B ⊂ A maka. A = B, sehingga relasi inklusi ⊂ merupakan relasi anti simetrik pada S. 3. Bila A ⊂ B & B ⊂ C maka. A ⊂ C , sehingga relasi inklusi ⊂ merupakan relasi transitif pada S. Jadi, berdasarkan definisi poset di atas, S bersama relasi inklusi ⊂ atau ditulis ( S , ⊂) merupakan poset. b. Pandang himpunan N , yaitu himpunan dari semua bilangan-bilangan bulat positif. Pada N diadakan relasi habis membagi atau membagi. Bila a, b ∈ N dan a membagi b, maka aRb ditulis a | b. Ingat bahwa bila a, b ∈ N dengan a | b, artinya ∃c ∈ N ∋ a ⋅ c = b. 1. Jelas bahwa a | a untuk setiap anggota a dari N, sehingga relasi membagi | merupakan relasi refleksif. 2.Bila a | b & b | a maka. a = b sehingga relasi membagi | merupakan relasi anti simetrik. 3. Bila a | b & b | c maka. a | c, sehingga relasi membagi | merupakan relasi transitif pada N. Jadi, berdasarkan definisi poset di atas, N bersama relasi membagi | atau ( N, | ) merupakan poset. Supremum dan infimum Misalkan A merupakan himpunan bagian dari poset S. Suatu elemen M di dalam S disebut batas atas dari A bila M melampaui setiap elemen x di dalam A, atau ∀x ∈ A berlaku x ≤ M . Bila suatu batas atas dari A mendahului semua batas atas yang lain dari A maka elemen tersebut disebut supremum dari A dan ditulis sup(A) atau batas atas terkecil dari A dan ditulis lub (A).
32
Secara analog, suatu elemen m di dalam S disebut batas bawah dari A bila m mendahului setiap elemen x di dalam A, atau ∀x ∈ A berlaku m ≤ x. Bila suatu batas bawah dari A melampaui semua batas bawah yang lain dari A maka elemen tersebut disebut infimum dari A dan ditulis inf(A) atau batas bawah terbesar dari A dan ditulis glb (A). Contoh a. Himpunan N diurutkan secara parsial dengan relasi membagi |. Misalkan a, b ∈ N. Pembagi persekutuan terbesar dari a dan b ditulis dengan gcd( a, b) adalah bilangan bulat positif terbesar yang membagi kedua a dan b. Kelipatan persekutuan terkecil dari a dan b ditulis dengan lcm(a, b) adalah bilangan bulat positif terkecil yang dapat dibagi oleh kedua a dan b. Dari teori bilangan diperoleh sifat bahwa setiap pembagi persekutuan dari a dan b juga membagi gcd( a, b) serta lcm(a, b) membagi setiap kelipatan persekutuan dari a dan b. Jadi, gcd(a, b) = inf(a, b) = glb(a, b) lcm(a, b) = sup(a, b) = lub(a, b). b. Untuk setiap bilangan bulat positif m, misalkan Dm menunjukkan himpunan dari semua pembagi-pembagi dari m terurut dengan relasi habis membagi. Maka, D36 = {1,2,3,4,6,9,12,18,36}. Terlihat bahwa gcd(a, b) = inf(a, b) = glb(a, b) dan lcm(a, b) = sup(a, b) = lub(a, b) eksis untuk semua a dan b di dalam D36 . Soal 1. Relasi R adalah relasi habis membagi yang didefinisikan atas himpunan A = {1,2,3,4,6,8,9,12,16,18,24,27,36,48,54,72,81,108,144,162,216,324,432,648,1296}. Gambarkan poset ( A, R ) di atas dalam diagram Hess. Carilah ub, lub, lb dan glb dari himpunan{6,12,36,72}.
33
PERTEMUAN 13: ALJABAR BOOLE Definisi dasar Baik himpunan-himpunan maupun pernyataan-pernyataan, keduanya mempunyai sifatsifat yang mirip, yang disebut hukum-hukum identikal. Hukum-hukum ini digunakan untuk mendefinisikan struktur matematika yang abstrak yang disebut aljabar Boole.Nama tersebut diambil dari matematikawan Inggris Geoge Boole (1815-1864). Misalkan B adalah himpunan tidak kosong dengan dua operasi biner + dan ∗ , satu operasi unari ‘, dan dua elemen yang berbeda 0 dan 1. Himpunan B disebut aljabar Boole, bila aksioma-aksioma di bawah ini dipenuhi, di mana a, b, c adalah lemen-elemen sembarang dalam B. (B1) Hukum-hukum komutatif: (1a ) a + b = b + a (1b) a ∗ b = b ∗ a
(B2) Hukum-hukum distributif: (2a ) a + (b ∗ c) = (a + b) ∗ (a + c)
(2b) a ∗ (b + c) = a ∗ b + (a ∗ c)
(B3) Hukum-hukum identiti: (3a ) a + 0 = a (3b) a ∗ 1 = a (B4) Hukum-hukum komplemen: ( 4a ) a + a ' = 1 (4b) a ∗ a ' = 0. Kadang-kadang aljabar Boole ditulis dengan notasi ( B, +, ∗, ' , 0,1). di mana 0 disebut elemen nol, 1 disebut elemen satuan dan a ' disebut komplemen dari a. Sebagaimana pada hasilkali biasa pada bilangan-bilangan real, tanda ∗ tidak akan dituliskan. Misalnya ab artinya a ∗ b. Operasi-operasi +,∗ dan ‘ berturut-turut disebut jumlah, hasilkali dan komplemen.Kita mengikuti aturan a + b ∗ c yang berarti a + (b ∗ c), a ∗ b' yang berarti a ∗ (b' ). Contoh 1. Misalkan B = {0,1}dengan dua operasi biner + dan ∗ yang didefinisikan sebagai + 1 0 1 1 1 0 1 0
∗ 1 0
1 1 0
0 0 0
dan operasi unari ‘ didefinisikan sebagai 0' = 1 dan 1' = 0. Maka B merupakan aljabar Boole. 34
2. Misalkan C koleksi dari himpunan yang tertutup terhadap union, interseksi dan komplemen. Maka C merupakan aljabar Boole dengan himpunan kosong φ sebagai elemen nol dan himpunan semesta U sebagai elemen 1. 3. Misalkan D70 adalah himpunan dari pembagi-pembagi 70 yaitu D70 = {1, 2,5,7,10,14, 35,70}. Didefinisikan +,∗ dan ‘ pada D70 sebagai a + b = kelipatan persekutuan terkecil dari a dan b, a ∗ b = pembagi persekutuan terbesar dari a, a' = 70 / a. Maka D70 merupakan aljabar Boole dengan 1 sebagai elemen nol dan 70 sebagai elemen satuan.
Dualitas Dual dari pernyataan sembarang dalam suatu aljabar Boole B adalah pernyataan yang diperoleh dengan menukar operasi-operasi + dan ∗ dan menukar elemen-elemen 0 dan 1 dalam pernyataan semula. Sebagai contoh, dual dari (1 + a) ∗ (b + 0) = b adalah (0 ∗ a ) + (b ∗ 1) = b.
Perhatikan sifat simetri dalam aksioma-aksioma dari aljabar Boole B.Yaitu, dual dari aksioma juga aksioma dalam aljabar Boole B. Berdasarkan hal tersebut, diperoleh hasil Prinsip Dualitas yang penting, yang dinyatakan sebagai Teorema 1 (Prinsip Dualitas): Dual dari teorema sembarang dalam dalam aljabar Boole juga merupakan suatu teorema. Menggunakan aksioma-aksioma (B1) sampai dengan (B4) dalam aljabar Boole B, diperoleh Teorema 2 Misalkan a, b, c adalah elemen-elemen sembarang dalam aljabar Boole B. Maka berlaku (i) Hukum-hukum idempoten: a + a = a, a∗a = a Hukum-hukum keterbatasan: a + 1 = 1, (ii) a∗0 = 0 (iii) Hukum-hukum absorpsi: a + (a ∗ b) = a, a ∗ ( a + b) = a (iv) Hukum-hukum asosiatif: (a + b) + c = a + (b + c ), a ∗ b) ∗ c = a ∗ (b ∗ c ). Teorema 3 Misalkan a adalah elemen sembarang dalam aljabar Boole B.Maka berlaku Hukum Ketunggalan Komplemen: Bila a + x = 1 & a ∗ x = 0 maka x = a'. (i) (ii) Hukum Involusi: (a ' )' = a, a∗0 = 0 (iii) 0' = 1, 1' = 0 Teorema 4 (Hukum-hukum DeMorgan) Misalkan a, b adalah elemen-elemen sembarang dalam aljabar Boole B.Maka berlaku (i) (a + b)' = a '∗b' , (a ∗ b)' = a'+b'.
35
Disain rangkaian skakelar listrik (rangkaian logika) Misalkan A, B, K merupakan skakelar listrik, dan misalkan untuk skakelar A, A’ menunjukkan skakelar listrik bila A hidup A’mati dan bila A mati A’ hidup. A dan B dapat dihubungkan seri, ditulis A ∧ B, atau paralel ditulis A ∨ B. Disain rangkaian skakelar listrik Boole adalah susunan dari kawat dan skakelar yang disusun dengan penggunaan berulang-ulang dari kombinasi seri dan paralel. Jadi rangkaian tersebut dapat dapat ditulis dengan notasi ∧ dan ∨ . Teorema 5 Aljabar dari rangkaian skakelar listrik Boole merupakan aljabar Boole. Soal 1. Gambarkan ungkapan (ekspresi) Boole ( A ∧ B' ) ∨ [( A'∨C ) ∧ B ]. Sederhanakan ungkapan (ekspresi) Boole ( A ∧ B' ) ∨ [( A'∨C ) ∧ B ] dan kemudian gambarkan hasilnya. 2. Gambarkan ungkapan (ekspresi) Boole [ A ∧ ( B ∨ B ' )] ∨ ( A'∧ B' ) Sederhanakan ungkapan (ekspresi) Boole A ∧ [(B ∨ B ')] ∨ ( A'∧ B') dan kemudian gambarkan hasilnya.
36
PERTEMUAN 15: DNF (Disjunction Normal Form)
Pandang himpunan dari peubah-peubah (huruf atau simbol), misalkan x1 , x 2 ,K , x n . Yang dimaksud dengan ekspresi Boole E dalam peubah-peubah ini, biasanya ditulis sebagai E ( x1 , x2 , K, x n ) , adalah peubah sembarang atau ekspresi sembarang yang dibangun oleh peubah-peubah tersebut menggunakan operasi-operasi Boole +,∗ dan ‘. Sebagai contoh, E = ( x + y ' z )'+ ( xyz '+ x' y )' dan F = (( xy ' z '+ y )'+ x' z )' merupakan ekspresi Boole dalam peubah x, y, z.
Yang dimaksud dengan literal adalah peubah atau komplemen dari peubah, misalnya x, x' , y, y ' dsb. Produk Fundamental Yang dimaksud dengan produk fundamental adalah literal atau produk dari dua atau lebih literal di mana tidak ada dua literal yang mengandung peubah yang sama. Misalnya, xz ' , xy ' z , x, y ' , yz ' , x' yz
semuanya merupakan produk fundamental. Tetapi xyx' z dan xyzy keduanya bukan produk fundamental.
Produk fundamental P1 dikatakan termuat dalam produkfundamental lain P2 bila literalliteral dari P1 juga iteral-literal dari P2 . Sebagai contoh x' z termuat dalam x' y z tetapi tidak dalam xy ' z , karena x’ bukan literal dari produk fundamental kedua. Bila produk fundamental P1 termuat dalam produk fundamental P2 , maka dengan hukum absorpsi P1 + P2 = P1 . Misalnya ac' termuat dalam ac'∗b, diperoleh ac'+ (ac'∗b) = ac'. DNF & Metodanya Ekspresi Boolean E merupakan disjunctive normal form (dnf) bila E adalah produk fundamental atau jumlah dari dua atau lebih produk fundamental di mana tak ada produk fundamental yang termuat dalam produk fundamental yang lain. Sebagai contoh, E1 = x z '+ y ' z + x y z ' dan E 2 = x z '+ x' y z '+ x y ' z '.
Yang pertama bukan dnf karena x z ' termuat dalam x y z ' , sedang yang kedua juga bukan dnf karena xz ' termuat dalam xy ' z '. Menggunakan hukum-hukum aljabar Boole, kita dapat mengkonstruksikan algoritma untuk mengubah ekspresi Boole sembarang E ke bentuk dnf, dengan cara sbb. (1) Menggunakan hukum-hukum de Morgan dan involusi, kita dapat menjalankan operasi komplemen ke dalam kurung sembarang sampai akhirnya hanya terdapat
37
komplemen dari peubah-peubah. Kemudian E hanya mengandung jumlahan dan produk dari literal saja. (2) Menggunakan hukum distributif, kita dapat terus mengubah E ke dalam jumlahan dari produk-produk, lalu menggunakan hukum-hukum komutatif, idempoten dan absorpsi, kita akhirnya dapat mengubah E dalam dnf. Sebagai contoh, dengan (1) E = ((ab)' c)' ((a '+ c)(b'+c' ))' = ((ab)' '+c' )((a'+c)'+(b'+c' )' )
= (ab + c' )(ac'+bc). Kemudian dengan (2), E = abac'+ abbc + ac' c'+bcc' = abc'+ abc + ac'+0 = ac'+ abc, yang berbentuk dnf.
Full DNF Ekspresi Boole E ( x1 , x 2 ,K , x n ) disebut full disjunctive normal form bila E ( x1 , x 2 ,K , x n ) merupakan dnf dan setiap produk fundamental mengandung semua peubah. Kita dengan mudah dapat mengubah dnf ke dalam full dnf dengan mengalikan setiap produk fundamental P dari E dengan xi + xi ' bila P tidak mengandung xi . Sebagai contoh, kita dapat mengubah E = E (a, b, c) di atas ke dalam full dnf dengan E = ac '+ abc = ac ' (b + b' ) + abc = abc'+ ab' c'+ abc. Perlu dicatat bahwa xi + xi ' = 1, sehingga mengalikan P dengan xi + xi ' dibolehkan. Teorema Setiap ekspresi Boole E ( x1 , x 2 ,K , x n ) yang tidak sama dengan nol dapat dituliskan dalam full dnf dengan tunggal. Contoh 1. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf E1 = E1 ( x, y, z ) = x( y ' z )'. Solusi E1 = x( y ' z )' = x( y + z ' ) = xy + xz ' , dalam dnf. Juga, E1 = xy + xz ' = xy( z + z ' ) + x( y + y ' ) z ' = xyz + xyz '+ xyz '+ xy ' z ' = xyz + xyz '+ xy ' z ' , dalam full dnf.
2. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf E 2 = E 2 ( x, y, z ) = z ( x'+ y ) + y '.
Solusi
38
E 2 = z ( x'+ y ) + y ' = x' z + yz + y ' , dalam dnf. Juga, E 2 = z ( x'+ y ) + y ' = x' z ( y + y ' ) + yz ( x + x' ) + y ' ( x + x' )( z + z ' ) = x' yz + x' y ' z + xyz + x' yz + xy ' z + + xy ' z '+ + x' y ' z + x' y ' z ' = xyz + xy ' z + xy ' z '+ x' yz + x' y ' z + x' y ' z ' , dalam full dnf. 3. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf E3 = E3 ( x, y, z ) = ( x'+ y )'+ x' y. Solusi E3 = ( x'+ y )'+ x' y = xy '+ x' y, dalam dnf. Bentuk terakhir ini bisa dipandang sebagai dalam bentuk full dnf bila peubah-peubahnya hanya x dan y. Tetapi dalam soal jelas bahwa peubah-peubahnya diketahui dalam x, y, z. Jadi E3 = ( x'+ y )'+ x' y = xy'+ x' y = xy' ( z + z ' ) + x' y ( z + z ' ) = xy ' z + xy' z '+ x' yz + x' yz ' ,
dalam full dnf.
39
PERTEMUAN 16: TEORI GRAPH Pengertian dan konsep dasar Graph G terdiri dari dua bagian: (i) Himpunan V yang elemen-elemennya disebut titik-titik atau nodes. (ii) Himpunan E dari pasangan-pasangan tak berurutan dari titik-titik yang berlainan yang disebut rusuk-rusuk atau edges. Kita menulis graph sedemikian dengan G (V , E ) untuk menekankan dua bagian dari graph G tersebut. Titik-titik u dan v disebut bersebelahan atau adjacent bila terdapat rusuk {u, v}. Kita menggambarkan graph dengan diagram secara alami. Dalam hal ini setiap titik v dalam V disajikan dengan lingkaran kecil atau dot, dan setiap rusuk e = {v1 , v 2 } disajikan dengan kurva yang menghubungkan titik-titik ujung v1 dan v 2 . Pada graph G (V , E ) biasanya tidak dibolehkan adanya rusuk ganda atau multiple edges, yaitu adanya lebih dari satu rusuk yang menghubungkan dua titik pada graph tersebut. Pada graph G (V , E ) juga tidak dibolehkan adanya loop, yaitu rusuk yang titik-titik ujungnya sama. Graph G (V , E ) dengan dua sifat ini disebut multigraph. Yang dimaksud dengan walk adalah multigraph yang terdiri dari barisan yang bergantian dari titik dan rusuk dengan bentuk v0 , e1 , v1 , e2 , v2 , K, en −1 , v n −1 , en , v n .
Sedangkan path adalah walk di mana semua titik-titiknya berlainan. Misalkan G (V , E ) adalah graph. Misalkan juga V’ himpunan bagian dari V , dan E’ adalah himpunan bagian dari E yang memuat semua rusuk dari E yang titik-titik ujungnya merupakan elemen dari V’. Dalam hal ini G (V ' , E ' ) merupakan subgraph dari graph G (V , E ). Komponen dari graph Graph G (V , E ) disebut terhubung atau connected bila antara dua titik sembarang terdapat suatu path yang menghubungkan dua titik tersebut. Subgraph terhubung dari graph G (V , E ) disebut komponen terhubung dari G (V , E ) bila dia tidak termuat dalam subgraph terhubung sembarang yang lebih besar. Secara intuitif jelas bahwa setiap graph dapat dipartisi ke dalam komponen-komponen terhubungnya.
Jarak antara dua titik dan diameter Jarak antara dua titik u dan v dari graph terhubung G, ditulis d (u , v ) , adalah panjang dari path terpendek antara u dan v. Diameter dari graph terhubung G adalah jarak maksimum dari dua titik sembarang dari G. Misalkan v adalah titik dari graph G. Yang dimaksud dengan G − v adalah adalah graph yang diperoleh dari G dengan menghilangkan v dan semua rusuk-rusuk yang berinsiden dengan v. Titik v dalam graph terhubung G disebut titik potong atau cut point bila G − v menjadi tak terhubung. 40
PERTEMUAN 20: PEWARNAAN GRAPH Pewarnaan titik Pewarnaan titik dari graph G adalah penentuan warna pada titik-titik G, sedemikian sehingga titik-titik yang bersebelahan mempunyai warna-warna berlainan. Banyaknya warna minimum yang diperlukan untuk mewarnai G disebut bilangan kromatik atau chromatic number dari G dan ditulis dengan simbol κ (G ). Kita berikan algoritma Welch dan Powell untuk mewarnai graph G. Langkah pertama adalah mengurutkan titik-titik dari G berdasarkan degreenya yang menurun (urutan ini tidak tunggal karena ada titik-titik yang punya degree sama). Langkah kedua adalah memberikan warna pertama untuk titik pertama. Untuk mewarnai selanjutnya adalah secara barisan, warnai setiap titik yang tidak bersebelahan dengan titik yang diwarnai sebelumnya dengan warna yang sama. Ulangi proses yang sama menggunakan warna kedua dan barisan bagian dari titik-titik yang belum diwarnai. Lanjutkan prosesnya dengan warna ketiga, dst. sampai semua titik-titik terwarnai. Kita memakai algoritma Welch-Powell untuk mewarnai graph G pada Gambar 6-5. Mengurutkan titik-titik menurut degreenya yang menurun diperoleh barisan A5 , A3 , A7 , A1 , A2 , A4 , A6 , A8 .
Warna pertama digunakan untuk mewarnai titik-titik A5 dan A1 . Warna kedua dipakai untuk mewarnai titik-titik A3 , A4 , A8 . Warna ketiga dipakai untuk mewarnai titik-titik A7 , A2 dan A6 , sehingga κ (G ) ≤ 3. Perlu dicatat bahwa κ (G ) > 2, karena A1 , A2 dan A3 harus diwarnai berlainan. Jadi κ (G ) = 3. Juga, graph komplit atau lengkap K n dengan n titik simpul memerlukan n warna dalam pewarnaan sembarang, karena setiap titik simpul bersebelahan dengan setiap titik simpul lainnya. Contoh 1. Perhatikan Gambar 6-18. Gunakan algoritma Welch-Powell untuk mewarnai (pewarnaan titik) graph pada gambar tersebut. Solusi Dikerjakan secara barisan, kita pakai warna pertama untuk mewarnai titik-titik simpul H, B, dan lalu G.( Kita tidak dapat mewarnai A, D, atau F dengan warna pertama karena masing-masing terhubung dengan H. Kerjakan terus secara barisan dengan titik-titik simpul yang belum diwarnai, kita pakai warna kedua untuk titik-titik simpul A dan D. Titik-titik simpul sisanya F, C dan E dapat diwarnai dengan warna ketiga. Jadi bilangan kromatik n tidak dapat melebihi 3. Pada setiap pewarnaan, H, D, dan E harus diwarnai berlainan, karena mereka terhubung satu sama lain. Jadi n = 3. Pewarnaan rusuk Pewarnaan rusuk dari graph G adalah penentuan warna pada rusuk-rusuk G, sedemikian sehingga rusuk-rusuk yang bersebelahan mempunyai warna-warna berlainan. Banyaknya warna yang diperlukan dibuat minimum.
41
Contoh 1. Perhatikan graph pada halaman 149. Pewarnaan rusuk graph tersebut dikerjakan sebagai berikut: a) e1 kita beri warna pertama. b) e4 dan e9 kita beri warna pertama juga, karena e1 , e4 dan e9 tidak saling terhubung langsung oleh sebuah titik. c) e2 kita beri warna kedua. d) e5 dan e7 dapat diberi warna kedua juga, karena e2 , e5 dan e7 juga tidak saling terhubung melalui sebuah titik. e) e3 dan e8 dapat diberi warna ketiga. f) Terakhir, e6 kita beri warna keempat. Jadi bilangan kromatik (pewarnaan rusuk) dari graph di atas adalah empat, atau κ (G ) = 4. 2. Pada pewarnaan rusuk untuk graph lengkap κ n , bilangan kromatik dari κ n memenuhi rumus: n, bila n ganjil κ (κ n ) = n − 1, bila n genap. Pewarnaan daerah Pandang suatu map M, yaitu representasi planar dari multigraph planar yang berhingga. Dua daerah dari M dikatakan bersebelahan bila mereka mempunyai suatu rusuk berserikat. Yang dimaksud dengan pewarnaan daerah dari M adalah penentuan warna pada setiap daerah dari M sedemikian sehingga daerah-daerah yang bersebelahan mempunyai warna yang berlainan. HAL 149
Contoh 1. Sebagai contoh, pada Gambar 6-6 (a) daerah-daerah r2 dan r5 bersebelahan, sedangkan r3 dan r5 tidak. Map pada Gambar 6-6 (a) mempunyai bilangan kromatik tiga,
42
yaitu banyaknya warna minimum untuk pewarnaan daerah dari map tersebut. Hal ini mengingat: r1 diberi warna merah, r2 putih, r3 merah, r4 putih, r5 merah dan r6 biru. 2. Gambar 6-7 memperlihatkan map yang sangat sederhana, yang memerlukan empat warna pada pewarnaan (daerah) sembarang. Soal 1. Carilah bilangan kromatik untuk pewarnaan daerah pada setiap map pada Gambar 6-30.
43
PERTEMUAN 21: TREE GRAPH
Suatu graph terhubung tanpa cycle disebut tree atau pohon. Pada Gambar 5-11 diperlihatkan enam pohon masing-masing dengan enam titik simpul. Subgraph T dari graph G disebut spanning tree dari G bila T merupakan tree dan memuat semua titik simpul dari G. Gambar 6-8 memperlihatkan graph G dengan spanning trees T1 ,T2 dan T3 dari G. Bila G adalah suatu graph yang rusuk-rusuknya mempunyai panjang, maka yang dimaksud dengan minimal spanning tree dari G adalah spanning tree dari G di mana jumlah panjang dari rusuk-rusuknya minimal di antara semua spanning tree dari G. Pandang graph G yang merupakan graph terhubung berlabel berhingga dengan m titiktitik simpul. Di bawah ini kita berikan dua algoritma untuk mendapatkan minimal spanning tree dari G. Algoritma I.
Pertama, urutkan rusuk-rusuk dari G sesuai dengan panjangnya secara menurun. Kerjakan secara barisan, hilangkan setiap rusuk yang tidak memutus (membuat tidak terhubung) graph G sampai tinggal m − 1 rusuk. Rusuk-rusuk ini membentuk minimal spanning tree dari G. Algoritma ini bergantung pada diketahuinya graphnya terhubung, yang pada umumnya tidak mudah dibuat programnya. Algoritma II. Dimulai dengan mengurutkan rusuk-rusuk dari G sesuai dengan panjangnya secara menaik. Kemudian, dimulai dengan hanya titik-titik simpul dari G, kita tambahkan rusuk satu persatu di mana setiap rusuk punya panjang minimal dan tidak membentuk cycle manapun. Setelah menambahkan m − 1 rusuk, kita dapatkan minimal spanning tree dari G. Gambar 6-9 memberikan graph terhubung berlabel G dan minimal spanning tree M. Contoh 1. Tentukan semua spanning trees dari graph G pada Gambar 6-20. Solusi Terdapat delapan spanning trees dari graph G sebagaimana diperlihatkan pada Gambar 621. Setiap spanning tree mempunyai tiga rusuk. Jadi setiap spanning tree dapat diperoleh dengan menghilangkan dua dari lima rusuk G. Ini dapat dikerjakan dalam sepuluh cara, kecuali dua di antaranya menjadi graph tak terhubung. Jadi delapan spanning trees di atas merupakan semua spanning trees dari G.
2. Carilah minimum spanning tree untuk graph dengan rusuk-rusuk Gambar 6-22.
berlabel pada
Solusi Terus hilangkan rusuk-rusuk dengan panjang maksimum tanpa membuat graph menjadi tidak terhubung. Cara lain, mulai dengan sembilan titik simpul, terus tambahkan
44
rusukcrusuk dengan panjang minimum tanpa membuat cycle manapun. Kedua cara menghasilkan minimum spanning tree sebagaimana ditunjukkan pada Gambar 6-23.
45
PERTEMUAN 23: FINITE AUTOMATA Kita bisa memandang suatu komputer digital sebagai suatu mesin yang berada di dalam “internal state” tertentu pada waktu yang diberikan sembarang. Komputer tersebut “membaca” input symbol , dan kemudian “mencetak” output symbol dan mengubah “state”nya. Output symbol bergantung hanya pada input symbol dan internal state dari mesin, dan internal state dari mesin bergantung hanya pada state sebelumnya dan input symbol sebelumnya. Gagasan ini diformalisasikan pada definisi berikut. Definisi Suatu finite state machine M terdiri dari lima bagian: (1) Himpunan berhingga A dari input symbols. (2) Himpunan berhingga S dari internal states. (3) Himpunan berhingga Z dari output symbols. (4) Next-state function f dari S × A ke S. (5) Output function g dari S × A ke Z. Mesin M ini ditulis dengan M = A, S , Z , f ,.g sewaktu kita ingin menekankan lima bagiannya. Kadang-kadang diberikan juga initial state atau state awal q0 di dalam S, dan mesin M ditulis dengan M = A, S , Z , q 0 , f ,.g .
Contoh Di bawah inidiberikan finite state machine M dengan dua input symbols, tiga internal states dan tiga output symbols: (1) A = {a, b} (2) S = {q 0 , q1 , q 2 } (3) Z = {x, y, z} (4) Next-state function f dari S × A ke S didefinisikan dengan f (q 0 , a ) = q1 f (q1 , a ) = q 2 f (q 2 , a ) = q 0
f (q 0 , b) = q 2 f (q1 , b) = q1 f (q 2 , b) = q1 . (5) Output function g dari S × A ke Z didefinisikan dengan g (q 0 , a ) = x g (q1 , a ) = x g (q 2 , a ) = z g (q 0 , b) = y g (q1 , b) = z g (q 2 , b) = y. Menurut tradisi, untuk menunjukkan states digunakan simbol q dan untuk menunjukkan initial state digunakan simbol q0 . Finite Automata Finite automaton adalah mirip finite state machine kecuali bahwa automaton mempunyai “accepting” dan “rejecting” states. Secara spesifik, finite automaton M terdiri dari lima bagian, yaitu: (1) Himpunan berhingga A dari input symbols. (2) Himpunan berhingga S dari internal states. (3) Himpunan bagian T dari S ( yang elemen-elemennya disebut accepting states) 46
(4) Initial state q0 di dalam S. (5) Next-state function f dari S × A ke S. Automaton M ini ditulis dengan M = A, S , T , q0 ,. f sewaktu kita ingin menekankan lima bagiannya. Contoh 1. Di bawah ini mendefinisikan suatu finite automaton dengan dua input symbols dan tiga states: (1) A = {a, b} , input symbols (2) S = {q 0 , q1 , q 2 }, states
(3) T = {q 0 , q1 } , accepting states (4) q0 , initial state. (5) Next-state function f dari S × A ke S didefinisikan dengan f (q 0 , a ) = q 0 f (q1 , a ) = q 0 f (q 2 , a ) = q 2 f (q 0 , b) = q1
f (q1 , b) = q 2
f (q 2 , b) = q 2 .
Kita dengan ringkas dapat mendiskripsikan finite automaton M dengan state diagramnya sebagaimana dikerjakan dengan finite state machine, kecuali bahwa di sini kita menggunakan lingkaran dobel untuk accepting states dan setiap rusuk dilabel hanya dengan input symbol. Secara spesifik, state diagram D dari M adalah graph berarah yang dilabel yang titik-titiknya adalah states dari S di mana accepting states dilabel menggunakan lingkaran dobel; dan bila f (q j , a i ) = q k , maka terdapat busur dari q j ke q k yang dilabel dengan ai . Juga initial state q0 ditunjukkan dengan panah menuju titik q 0 . Sebagai contoh, state diagram dari automaton M dari contoh di atas diberikan dalam Gambar 7-9. Diberikan string berhingga W = a1 a 2 a3 L a n dari input symbols dari automaton M, kita peroleh
barisan dari states s 0 s1 s 2 L s n di mana s 0 adalah initial state dan
s i = f ( s i −1 , ai ) untuk i > 0. Kita katakan bahwa M mengenal atau menerima string W bila final state s n adalah accepting state, yaitu bila s n ∈ T . Kita gunakan L( M ) untuk menunjukkan himpunan semua string yang dikenal oleh M. Sebagai contoh, kita dapat memperlihatkan bahwa automaton M dalam contoh di atas akan mengenal semua string yang tidak mempunyai dua b yang berurutan . Jadi M akan menerima aababaaba, aaa, baab, abaaababab dan akan menolak aabaabba, bbaaa, ababbaab, bb, abbbaa
47
