DIKTAT PENDUKUNGMATEMATIKA DISKRIT K0144Drs. Sangadji, M.Sc., Ph.D.D1808F S TUNIVERSITAS BINA NUSANTARAJAKARTA1PERTEMUAN 1: LOGIKA PROPOSISIPendahuluanDalam 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.Contoh1. Contoh pernyataan:a. New York kota besarb. Paris ibukota negara Inggrisc. . 2 0 1 + 2. Contoh bukan pernyataan:a. Semoga kamu lekas sembuhb. Cepat lari!c. Ke mana dia pergi?d. Alangkah cantiknya gadis itu.e. Penduduk kota Jakarta kaya (tidak dilengkapi kuantor/pembatas penduduk)f. . 100 5 + x (untuk95 xbenar, untuk95 xsalah, disebut kalimat terbuka)Tabel kebenaranSuatu 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 2p qp qq p q p q p B B S S B B SB S S B S B BS B B S S B BS S B B S S Sp,q: pernyataan bagian.B: benar,S: salahpatau ~ p : ingkaran dari p,qatau ~ q: ingkaran dari q.q p : konjungsi darip dan q dibaca p dan q (pernyataan gabungan).q p : disjungsi dari p dan q dibaca p atau q (pernyataan gabungan).q p : bernilai benar hanya untuk keduanya benar.q p : bernilai salah hanya untuk keduanya salah.q p : exclusive or dari p dan q dibaca p exclusive or qImplikasip q p qB B BB S SS B BS S Bp: hipotesis, q: konklusi. : implikasi.p q: bila p maka q.p q: bernilai salah hanya untuk p benar dan q salah.p q: p disebut syarat cukup bagi q. q disebut syarat perlu bagi p.3Konvers, invers, dan kontrapositif dari implikasip q: implikasi mula mula.qp: konvers dari p q,p q: invers dari p q.q p : kontrapositif dari p q.p q p q qpp q q ppqB B B B B BSSB S S B B SSBS B B S S B B SS S B B B BBBBiimplikasip q: p bila dan hanya bila q.p q p q qp( ) ( ) p q q p q p B B B B B BB S S B S SS B B S S SS S B B B Bq p : bernilai benar untuk keduanya bernilai kebenaran yang sama,bernilai salah untuk keduanya bernilai kebenaran yang berlainan.PERTEMUAN 2: ALJABAR PROPOSISIProposisi mempunyai sifat fundamental yang disebut hukumatau formula. Beberapa hukum yang penting kita kelompokkan di bawah ini.1) Idempoten4samasamasamap p = p, p p = p 2) Asosiatif(p q) r = p (q r), (p q) r = p (q r)3) Komutatifp q = q p,p q = q p4) Distributifp (q r) = ( p q) ( p r)p (q r) = (p q) (p r) 5) DeMorganq p q p q p q p ,6) Identitasp F = p, p F = Fp T = T, p T = pT : Tautologi, F : Kontradiksi7) KomplemenF p p T p pT F F T p p ,, ,8) Absorpsip (p q) = p, p (p q) = p5Contoh1. Bukanpernyataan: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. 1 2 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)( )1 1, y x adalah sama dengan pasangan berurutan dari bilangan nyata( )2 2, y x bila 2 1x x dan 2 1y y .105. 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.7. Bilangan nyata r disebut rasional (terukur) bila nmr dengan m dan n bilangan bulat dan0 n .8. Suatu segitiga disebut siku- sikubila dua sisinya saling tegaklurus.Terminologi (istilah) matematika1. ProposisiSuatu pernyataan yang telah dibuktikan kebenarannya.2. TeoremaSuatu pernyataan yang sifatnya lebih umum dan lebih penting dari proposisi yang telah dibuktikan kebenarannya.3. CorollarySuatu pernyataan yang buktinya dengan mudah dapat diturunkan dari suatu teorema atau singkatnya suatu akibat.4. LemmaSuatu pernyataan yang telah dibuktikan kebenarannya dan digunakan untuk membuktikan teorema.5. AksiomaSuatu pernyataan yang dapat diterima kebenarannya tanpa bukti.Contoh1. Proposisi a) Jumlah sudut- sudut dalam segitiga sembarang adalah 180b) Akar-akar persamaan kuadrat02 + + c bx axakan sama dan bernilai real bila. 0 42 ac b2. Teorema 11a) Teorema Binomial : ( )( ) +nkk k n ny xk n kny x0,! !!di mana n bilangan 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. 2 3 2 5 5 3 2 2 60 3. Corollary a)( )( )+ + + +303 2 2 3 3 33 3! 3 !! 3kk ky xy y x x y xk ky x.b)( )( ) +nkn nk n kn0! !!2 1 14. Lemmaa) Untuk membuktikan Teorema Binomial diperlukan lemma :( )( ) ( ) ( ) ( ).! !!! 1 ! 1!! 1 !! 1k n knk n knk n kn++ ++b) Untuk membuktikan Teorema Fundamental Aritmatika diperlukan lemma:Bila p adalah bilangan prima dan p adalah pembagi dari hasil kali t c b a maka p adalah pembagi dari sekurang-kurangnya satu dari bilangan- bilangan t c b a , , , , 5. Aksiomaa) Garis lurus ditentukan oleh 2 titik.b) Bidang datar ditentukan oleh 3 titik.Soal1. Berikan definisi dari segitiga samakaki yang ekivalen dengan definisi di muka.2. Berikan dua definisi yang ekivalen dari segitiga samasisi.3. Berikan definisi-definisi dari fungsi genap dan fungsi ganjil.124. Berikan contoh-contoh yang lain dari proposisi, teorema, corollary, lemma, dan aksioma.13PERTEMUAN 4: ARGUMENTASI DAN KUANTORARGUMENTASIArgumentasi adalah penarikan kesimpulan dari sekelompok pernyataan nS S S , , ,2 1yangdisebutpremisyangmenghasilkanpernyataanlainSyangdisebut konklusi. Argumentasi sedemikian akan ditulis dengan notasi/simbol.__________21SSSSnPerludicatat bahwaargumentasi jugamerupakanpernyataansehinggamempunyaisatu nilai kebenaran. Bila suatu argumentasi benar, disebut valid dan bila salah disebut fallacy atau tidak valid.Hukum SilogismeArgumentasi ini valid: q p

r q __________

. r p Hukum modus ponens Argumentasi ini valid: q p

p _________

q Hukum modus tolens: Argumentasi ini valid: q p

q ~___________14p ~

Contoh1. Tentukan validitas dari argumentasi ini q p

p ~ __________

q ~ SolusiBila p maka q atau (~ p atau q) benar dengan ~ p benar maka dapat disimpulkan qbisa benar atausalah. Jadi ~ q bisa benar atau salah. Jadi argumentasi tersebut tidak valid.2. Tentukan validitas dari argumentasi ini q p

q __________p Solusi

q p 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.

rq rq p~ __________

p ~ 2. Tentukan validitas dari argumentasi di bawah ini.

q rq p~ __________

p r ~ 3. Tentukan validitas dari argumentasi di bawah ini.15

q rq p~ ~~ __________

r p ~ 4. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid.

qq p ~ 5. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid..

q rq p~ 6. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid..

r pq p~~

7. Untuk premis-premis yang diberikan tariklah suatu kesimpulan supaya argumentasinya valid..

qp rq p~~

KUANTOR Kuantor adalah notasi yang digunakan untuk menyatakan kuantitas suatu obyek dalam logika matematika.Contoh1)Kuantor unive rsal: , dibaca semua atau setiap.162) Kuantor eksistensial : , dibaca beberapa atau terdapat paling sedikit satu atau lebih singkat terdapat. ! , dibaca terdapat tepat satu.Contoh penggunaanMisalkan X suatu himpunan yang tidak kosong.BilaX x punya sifat/predikatP ditulis( ) x P .1) ( ) x P X x , dibaca Untuk setiapX x , x bersifatP , atau semuaX x bersifatP .2) ( ) x P X x , dibaca BeberapaX x bersifatP , atau Terdapat paling sedikit satuX x yang bersifatP .3) ! , digunakan pada 2) : ( ) x P X x ! , dibaca Terdapat tepat satuX x yang bersifatP .Contoh dalam negasi1)( ) ( ) . , DeMorgan Teorema x P X x x XP x 2)( ) ( ) . , DeMorgan Teorema x P X x x XP x 3)( ) ( ) ( ) y x P y x y x P y x , ~ , , , ~ di mana . ~ 4)( ) ( ) ( ). , ~ , , , ~ y x P y x y x P y x 5)( ) ( ) ( ). , ~ , , , ~ y x P y x y x P y x 6)( ) ( ) ( ). , ~ , , , ~ y x P y x y x P y x Contoh dalam definisi1) Bilangan bulat n adalah bilangan kuadrat bila terdapat bilangan bulat k sedemikian sehingga 2k n .2) Himpunan A tidak kosong bila terdapat elemen a sedemikian sehingga. A a .173) Himpunan S dikatakan himpunan bagian dari T bila T x S x x ,.4) Fungsi R R : f disebut genap bilaR x ,( ) ( ). x f x f 5) Fungsi R R : f disebut ganjil bila , R x( ) ( ). x f x f 6) Diketahui himpunan-himpunan , A B, danB A .Himpunan A disebut himpunan bagian sejati dari himpunan B bilaB b dan. A bInduksi matematikaSeringkali kita akan menentukan bahwa suatu proposisi tertentu( ) n Padalah benar untuk setiapN n ( ) N + + N , ,N N,N n , , , n dengan2 1 atau2 1 0 atau .Misalnya( ) ( ) ( ) 6 1 2 1 3 2 1 :2 2 2 2+ + + + + + n n n n n P atau ( )( )+ + nkn n n k126 1 2 1.Untuk membuktikannya, digunakan Prinsip Induksi Matematika.Prinsip induksi matematikaUntuk membuktikan bahwa( ) n Pbenar untukN n:1) Buktikan( ) 1 Pbenar.2) Asumsikan( ) n Pbenar, buktikan( ) 1 + n Pbenar.Contoh1. Buktikan ( ) , 2 11+ nkn n kSolusi( ) , 2 1 1 1 111+ kk, jadi ( ) 1 Pbenar atau untukkanan. ruas kiri ruas 1 n Asumsikan ( ) n P benar, yaitu ( )+ nkn n k12 1benar.Dibuktikan ( ) 1 + n P benar, yaitu ( ) ( )++ + 112 2 1nkn n k.18( ) ( ) ( )( ) ( ) ( )( ) benar 1 Jadi, 2 2 1 2 2 32 2 2 2 1 2 1 12211 1++ + + + + + + + + + + + + n Pn n n n nn n n n n n n k knknkCatatan: ( ) 1 Pbenar: pangkal,( ) 1 + n Pbenar : konklusi induksi, Asumsi( ) n Pbenar : hipotesis induksi.2. Buktikan ( ) ( )+ + nkn n n k12. 6 1 2 1Solusi( ) ( ) , 6 1 1 2 1 1 1 1 1112+ + kkjadi( ) 1 P benar. Asumsikan ( ) n P benar. ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) benar. 1 jadi , 6 3 2 2 13 2 2616 7 2611 6 1 2616 1 6 6 1 2 1 1 6 1 2 1122 212 2112+ + + + + ++ + ++ + + +++ + + + + + + + + +n P n n nn nnn nnn n nnn n n n n n n nn k knknk3. Buktikan ( ) ( )+ < nkn ka r r r a ar01, 1 , 1 1 RSolusi( ) ( ) ( ) benar. 0 jadi , 1 11 000P r r a a ar arkk Asumsikan ( ) n P benar.( )( )( )( )( )( )( ) ( ) ( ) benar. 1 jadi , 1 11 111121 2 11110 01+ + ++ ++ + ++++ + n P r r arr rrra arrraar ar arnn n nnnnknkn k k194. Buktikan Rumus DeMoivre :( ) ( ) ( ) N + + n n i n in, sin cos sin cos Solusi ( ) ( ) ( ), 1 sin 1 cos sin cos1 + + i ijadi ( ) 1 Pbenar. Asumsikan ( ) n P benar.Maka, ( ) ( ) ( )( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )( ) benar. 1 jadi, 1 sin 1 cos sin cossin cos cos sin sin sin cos coscos sin sin cos sin sin cos cossin cos sin cossin cos sin cos sin cos1 1++ + + + + + + + + + + + + + + ++n Pn i n n i nn n i n nn n i n i ni n i ni i in n Soal1)Buktikan( ) ,_

+ nknkn k n n k1212 2 3. , 4 1 N2)Buktikan ( ) , 4 , 3 , 2 ,! 1 11121111111 2 1 ,_

+ ,_

+ ,_

+nnnnnn3)Buktikan( ) ( ) ( ) . , 3 2 1 1 4 3 3 2 2 1 N + + + + + + + n n n n n n 4)Buktikan Rumus Binomial :( )( ) +nkkk nnn xyk n kny x0. ,! !!NSesuai pada Teorema Binomial, buktikan dulu lemma:( )( ) ( ) ( ) ( ).! !!! 1 ! 1!! 1 !! 1k n knk n knk n kn++ ++5)Diketahui fungsi N N : f dengan sifat( ) ( ) ( ). , , y f x f xy f y x + NBuktikan bahwa( ) ( ). a nf a f n an N N6)Diketahui fungsi N N : f dengan sifat( ) ( ) ( ). , , y f x f y x f y x + NBuktikan bahwa( ) ( ) ( ) N n f n fn, 1 .7)Buktikan bahwa1 x n N20( ) ( )( ) ( ) .111 1 1 1122 4 2xxx x x xnn + + + ++8)Buktikan bahwa : , R N y x n y x adalah pembagi dari n ny x 9)Buktikan bahwaN n6 adalah pembagi darin n 3.10)Buktikan bahwaN n9 adalah pembagi dari( ) ( ) . 2 13 3 3+ + + + n n n11)Buktikan bahwa untuk20 2 : , 7 , 6 , 5 + > n nn .12)Buktikan bahwa N n : ( ) ( ) + + + nkn n n n n k12 2 4. 30 1 9 6 121PERTEMUAN 5: HIMPUNANSuatu himpunanadalah 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, ditulisA x .Bila x bukan elemen dari A, ditulisA x .Himpunan yang elemen-elemennya hanya a, b, c ditulis{ } c b a , , .Himpunan dari semua x yang punya sifatPditulis { } P x x sifatpunya.Dua himpunan A dan B sama, ditulis A = B, bila :x B x A x .Himpunan A disebut himpunan bagian dari B, ditulis B A , 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.Definisi1) Produk (kartesius) dari A dan B, ditulis , B Aadalah :( ) { } B b A a b a B A dan,2) Gabungan atau union dari A dan B, ditulis A B, adalah :{ }. atauB x A x x B A 3) Irisan atau intersection dari A dan B, ditulis B A , adalah :{ }. danB x A x x B A 4) Selisih dari A dan B, ditulisB A \adalah :A x x B A | { \dan}. B x 5) Himpunan kuasa dari A , ditulis( ) A P , adalah :( ) { }. dari bagianhimpunanadalahA x A P ContohMisalkan A = {1, 2}, B = {1, 2, 3}, maka :221)( ) ( ) ( ) ( ) ( ) ( ) { }( ) ( ) ( ) ( ) ( ) ( ) { }( ) ( ) ( ) ( ) { }( ) ( ) ( ) ( ) ( ) ( ) { }( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) { } 3 , 3 , 2 , 3 , 1 , 3 , 3 , 2 , 2 , 2 , 1 , 2 , 3 , 1 , 2 , 1 , 1 , 1; 2 , 3 , 1 , 3 , 2 , 2 , 1 , 2 , 2 , 1 , 1 , 1; , ; 2 , 2 , 1 , 2 , 2 , 1 , 1 , 1; 3 , 1 , 2 , 1 , 1 , 1 , 3 , 2 , 2 , 2 , 1 , 2, 3 , 2 , 2 , 2 , 1 , 2 , 3 , 1 , 2 , 1 , 1 , 1 B BA BA A A AB AB A 2) { } { } . , , 2 , 1 , 3 , 2 , 1 B A A B A B A3) { } . , , 3 , B A A A B B A4) ( ) { } { } { } { } ( ) { }. , 2 , 1 , 2 , 1 , P A PAljabar dari himpunan, dualitas Untuk U adalah himpunan semesta, adalah himpunan kosong, A, B, C adalah himpunan sembarang, berlakulah huku-hukum di bawah ini.Hukum Idempoten1a. A A A 1b.A A A Hukum Asosiatif2a.) ( ) ( C B A C B A 2b.) ( ) ( C B A C B A Hukum Komutatif3a.A B B A 3b. A B B A Hukum Distributif4a.) ( ) ( ) ( C A B A C B A 4b.) ( ) ( ) ( C A B A C B A Hukum Identitas5a. A A 5b. A U A 6a. U U A 6b. AHukum Involusi7.A Ac c ) (Hukum Komplemen8a.U A Ac 8b. cA A9a. cU 9b. Uc 23Hukum DeMorgan10a. c c cB A B A ) ( 10b.c c cB A B A ) (BuktiSebagaicontoh, kta buktikan Hukum DeMorgan c c cB A B A ) ( : cB A x ) ( bhbB A x (bhb tidak benar bahwa ( A x atauB x )bhb ( A x dan) B x bhb(cA x dan cB x )bhb ) (c cB A x .Soal1. Buktikana.) \ ( B A B B A b. . ) \ ( B A B2. Buktikana. ) ( ) \ ( B A B A A b. . ) ( ) \ ( B A B A3. Buktikana.B A bhb cB Ab. B A bhb. U B Ac 4. Buktikana. B A bhb c cA B b.B A bhb. \ B A5. Formula cB A B A \memberikan definisi operasi beda dinyatakan dengan operasi interseksi dan komplemen. Carilah formula yang memberikan definisiB Adinyatakan 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, 30 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 ). ( \ ) ( B A B A B A a. Buktikan sifat asosiatif dari beda simetrik, yaitu . ) ( ) ( C B A C B A b. Buktikan sifat kanselasi dari beda simetrik, yaitu bila A danC A B A maka . C B c. Buktikan sifat distributif dari beda simetrik, yaitu ). ( ) ( ) ( C A B A C B A 8. Buktikan bahwa ) ( \ ) ( ) \ ( C A B A C B A 9, Carilah contoh yang menunjukkan bahwa ) ( \ ) ( ) \ ( C A B A C B A .2410.Dari 60 mahasiswa yang belajar bahasa Inggrisdiketahui 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.25PERTEMUAN 6: RELASIRelasiBila A dan B adalah himpunan, yang dimaksud relasi dari A ke B adalah suatu himpunan bagian dariB A .FungsiFungsi A ke B adalah suatu relasi dari A ke B sedemikian sehingga untuk setiap A a terdapat satu dan hanya satuB b dimana (a, b) f.Bila untuk setiapA 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. Definisi1) Fungsi B A f : disebut surjektif atau onto bila :( ) . b a f A a B b 2) Fungsi B A f : disebut injektif atau satu-ke-satu bila :( ) ( ) [ ]' ' ', a f a f a a A a a atau( ) ( ) [ ]. ,' ' 'a a a f a f A a a .3) Fungsi B A f : disebut bijektif bila : f surjektif dan sekaligus injektif.4) Image dari fungsi B A f : adalah :( ) ( ) { }. : A x x f A f ContohMisalkan{ } c b a A , , dan{ }, , , , d c b a B maka :1) ( ) ( ) ( ) { } B A d c b b b a f , , , , , adalah fungsi dariA keB , dengan ( ) ( ) ( ) . , , c f b b f b a f . ( ) A f image dari fungsi{ } . , B d b f 2) ( ) ( ) ( ) { } B B d c b b b a f , , , , ,hanyalah relasi dari B keB dan bukan fungsi dari BkeB .Relasi f ini merupakan fungsi parsial dariB keB .3) Fungsi{ } S B A P , : disebut predikat pada himpunan A. Misalnya { }, , 2 , 1 , 0 (omega) dapat didefinisikan fungsi{ } S B P , : sebagai predikat pada dengan 26a( )'genap. bilaganjil bilan SALAHn BENARn PSoal1) Diketahui{ } { } { } { }. , , , , , , 4 , 3 , 2 , 2 , 1 d c b W c b a V B A a) Carilah :( ). , , , , , V P A W B V A V A B A b) Carilah :( ) ( ) V P A B P W V A A A B B A , , , , ,2) Yang manakah relasi-relasi dariB A ke di bawah ini merupakan fungsi ?{ } { } 4 , 3 , 2 , 2 , 1 B A .a)( ) ( ) { } 4 , 2 , 3 , 1b)( ) ( ) { } 4 , 1 , 3 , 1c)( ) ( ) { } ( ) ( ) { } 4 , 1 , 2 , 2 , 3 , 1 , 3 , 13) Apakah( ) ( ) { } 3 , 2 , 2 , 1merupakan fungsi :a) dari( ) ( ) { } ? 3 , 2 ke 2 , 1b) dari? ke N Nc) dari( ) { } ? ke 2 , 1 Nd) dari( ) { } ( ) { } 3 , 2 ke 3 , 2 , 1 ?Relasi sebagai graphRelasi R dari A ke B adalah himpunan bagian dariB A .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( ) R b a , , gambar panah dari titik a ke titik b.Penyajian ini disebut bipartite graph representation dari R, dengan contoh sebagai berikut :

27yzdcbx{ } { }( ) ( ) ( ) ( ) ( ) ( ) { }. , , , , , , , , , , ,, , , , , ,z d z c x c y b y a x a Rz y x B d c b a A Bila A = B dapat digunakan penyajian lain dari R yang lebih menarik.Penyajian ini disebut directed graph representation.Untuk menyajikanA A R , gambar diagram dengan satu titik untuk setiap elemen dari A; untuk setiap( ) R y x ,gambar panah dari titik x ke titik y.Titik-titik disebut nodes atau vertices, sedang panah-panah disebut edges.Hal ini digambarkan sebagai berikut : { }( ) ( ) ( ) ( ) ( ) ( ) { }. , , , , , , , , , , ,, , ,a d c c a b d b c b b a Rd c b a A { }( ) ( ) ( ) ( ) ( ) { }. , , , , , , , , ,, , ,d d c b c a b a a a Rd c b a ABila x suatu node, banyaknya panah yang menuju x disebut in-degree ; sedangkan banyaknya panah yang berasalah dari x disebut out-degree. Definisi1) Relasi R pada A disebut refleksif bila( ) R a a A a , ,b adcdabc282) Relasi R pada A disebut simetrik bila :( ) ( ) [ ] R x y R y x A y x , , ,3) Relasi R pada A disebut transitif bila :( )( ) ( ) [ ] R z x R z y y x A y x , , , ,Bila relasi R simetrik, dapat digambarkan penyajian ke tiga dari R yang tidak memerlukan arah panah, disebut undirected graph representation.Relasi R refleksif Relasi R tidak refleksifRelasi R simetrik Relasi R tidak simetrikRelasi R transitif29Undirected grah representation dari relasi simetrik R diatasRelasi R : refleksif, simetrik dan transitifMisalkan relasi R pada A adalah transitif dan ( ) ( ) ( )4 3 3 2 2 1, , , , , a a a a a aadalah panah-panah dalamR .Dengan sifat transitif, didapat :( ) R a a 3 1,, sehingga juga didapat ( ) R a a 4 1, .DefinisiMisalkanA A R adalah suatu relasi.Yang dimaksud dengan path dari akebdalamRadalah barisan na a a , , ,1 0 sedemikian sehingga,(i)1 n(ii) n i A a ii, , 1 , 0 dengan, (iii)b a a an ,0(iv)( ) 1 , , 1 , 0 dengan, ,1 +n i R a a ii iBila na a 0, path di atas disebut cycle.Bilangan n disebut panjang dari path di atas.Suatu graph tanpa cycles disebut acyclic.ProposisiRelasiRtransitif bhb untuk setiap path darib a ke berada di dalamRmaka terdapat edge( ) b a,yang berada di dalamR .301) Misalkan{ } e d c b a A , , , , dan relasiR pada A adalah : ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) { }. , , , , , , , , , , , , , , , c e c d e c d c a c a b c a b a R a. Gambarkan bipartite graph representation dariR .b. Gambarkan directed graph representation dariR .c. Cek apakah Rrefleksif, simetrik atau transitif.2) Misalkan( ) { } { } { }. , , , , b a B a A a a R ApakahA A R refleksif ? Apakah B B R refleksif ? Gambarkan kedua relasi tersebut sebagai bepartite graphs dan directed graphs.3) Pandang undirected graph ini : 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{ } { }. , , b a B a A a. Daftar semua relasiA A R .b. Daftar semua relasiB B R .c. Dari relasi-relasi dalam a. dan b. , mana yang refleksif, simetrik, transitif? Relasi ekivalenSuatu relasi yang refleksif, simetrik dan transitif disebut relasi ekivalen.Definisi31MisalkanA A R adalah suatu relasi ekivalen dan misalkanA a . Klasekivalendari a terhadap R, ditulis[ ]Ra , adalah [ ] ( ) { } R a a A a aR ' ',, disingkat[ ] a .TeoremaBila Radalah relasi ekivalen padaA, dan A b a ,, maka :(i) bila( ) [ ] [ ] b a R b a maka , .(ii) bila( ) [ ] [ ] b a R b a maka , .(iii) [ ] [ ] [ ] [ ] b a b a atau.Graph dari relasi ekivalenDefinisiBila R adalah relasi ekivalen pada A, maka yang disebut quotient setR Aadalah[ ] { }. | A a a R AR DefinisiMisalkan A adalah suatu himpunan.Himpunan bagiandari P(A) disebut partisi dari A bila setiap Sadalah tidak kosong dan untuk setiapA a , terdapat tepat satu Ssedemikian sehinggaS a .324x2x3x132{ } { } { } { } ( ){ }{ } { } { } { } { } ( ). dari partisi4 , 3 , 2 , 14 3 2 1 dimana dari partisi3 , 2 , 4 , 121AA P, , , A AA P TeoremaHimpunan bagiandari P(A) merupakan partisi pada A bhbR A untuk suatu relasi ekivalen R pada A.

{ }{ } { } { } { } { } { }[ ] { } [ ] { }[ ] { } { } { } { } 3 , 2 , 1 , 2 , 1 23 3 , 2 , 1 13 , 3 , 2 , 2 , 1 , 2 , 2 , 1 , 1 , 13 , 2 , 1 R ARARR RSoal1) Diketahui { } 6 1 x x A dan R suatu relasi dari pada A di mana ( ) { }. 3 dari kelipatan, y x y x R Buktikan bahwa R adalah relasi ekivalen dan carilahR A . 2) Diketahui { } 8 1 x x A dan R suatu relasi dari pada A di mana( ) { }. ganjil k, dan, 2 dan2 ,' 'k k y k x y x Ri i Buktikan bahwa R adalah relasi ekivalen dan carilah R A .3) Misalkan A dan B adalah himpunan dan B A f :suatu fungsi. Didefinisikan :33( ) f Kerkernel dari ( ) ( ) ( ) { }. dan, , y f x f A y x y x f Buktikan bahwa untuk f sebarang,( ) f Ker adalah relasi ekivalen.4) Buktikan :Bila R adalah relasi ekivalen pada A,terdapatlah himpunan B dan fungsi B A f :sedemikian sehingga( ). f Ker R 34KomposisirelasiMisalkan A, B, dan C adalah himpunan-himpunan. Misalkan juga Radalah relasi dari A ke B dan S adalah relasi dari B ke C. Jadi dari definisi relasi, R adalah himpunan bagian dariB Adan S adalah himpunan bagian dari. C BDibentuk relasi komposisi dari R dan S, yaitu( ) S R dari A ke C yang didefinisikan sebagai{ } . & : ) , ( C A bSc aRb B b c a S R Kadang-kadang relasiS R dasingkat RS.Contoh1. Misalkan{ }, 4 , 3 , 2 , 1 A { } d c b a B , , , , dan{ } z y x C , , . Misalkan juga{ } { }. ) , ( ), , ( ), , ( ), , ( , ) , 3 ( ), , 3 ( ), , 3 ( ), , 2 ( ), , 1 ( z d y c z b x b S d b a d a R Maka, ) ( 3 & ) ( 2 x S R z S R karenaRd 2 dan , dSz serta . & 3 bSx Rb Juga didapatz S R ) ( 3 karena . & 3 dSz RdDapat disimpulkan { }. ) , 3 ( ), , 3 ( ), , 2 ( z x z S R TeoremaMisalkan 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). ( ) ( T S R T S R Invers relasiMisalkan R adalah relasi dari A ke B. Yang dimaksud dengan invers relasidari R, ditulis 1 R adalah relasi dari B ke A dengan { }. ) , ( : ) , (1R b a a b R Contoh1. Misalkan{ } 3 , 2 , 1 Adan R adalah relasi pada A di mana{ }, ) 3 , 2 ( ), 3 , 1 ( ), 2 , 1 ( R maka1 R adalah juga relasi pada A dengan{ }. ) 2 , 3 ( ), 1 , 3 ( ), 1 , 2 (1R2. Invers dari relasi x adalah suami y adalah relasi y adalah isteri x.35PERTEMUAN 7 : FUZZY SETPendahuluanMisalkan X merupakan himpunan semesta. Yang dimaksud dengan himpunan kabur ataufuzzysetAadalahdikarakterisirdenganfungsi karakteristikyangdiperumumatau fungsi keanggotaanA dari Xke selang tertutup ]. 1 , 0 [Contoh1.Misalkan Xadalah himpunan dari semua pabrik mobil. Himpunan kabur Adikarakterisir denganfungsi keanggotaan ] 1 , 0 [ : XA di mana X x ) (xA adalah prosentase mobil x digunakan di Jakarta.2. Misalkan himpunan semesta X adalah himpunan dari semua mahasiswa yang mengambil mata kuliah Matematika DiskritK0144. Himpunan kaburB dikarakterisirdengan fungsi keanggotaan] 1 , 0 [ : XBdi manaX x ) (xA adalah IPK x dibagi 4.3.MisalkanXadalah himpunan semesta. Himpunan biasa ataucrisp setCdapat dikarakterisirdengan fungsi keanggotaan fungsi karakteristik biasapada C. Ingat bahwa fungsi karakteristik biasa pada Catau Cadalah fungsi dariXke selang tertutup ] 1 , 0 [dengan '. , 0, 1) (C xC xxCDua himpunan kabur A dan B disebut sama, ditulis , B A bila dan hanya bila.B A Bila himpunan semesta{ }nu u u u U , , , ,3 2 1 berhingga, himpunan kaburD, misalnya dapat ditulis sebagainna a a aDu u u u3 2 13 2 1:atau sebagai jumlahu u DU uD/ ) ( atau dengan notasi36n nu a u a u a u a D / / / /3 3 2 2 1 1+ + + Himpunan (kabur) kosong dan himpunan(kabur) semestaMisalkan X adalah himpunan semesta.Himpunan kabur kosong dikarakterisir dengan fungsi keanggotaan fungsi nol dari X yaitu , 0 ) ( : x X xsedangkan himpunan kabur semesta dikarakterisir dngan fungsi keanggotaan. 1 ) ( X x xX Support dari himpunan kaburMisalkan X adalah himpunan semesta.Support dari himpunan kabur A:supp { }. 0 ) ( | ) ( > x X x AAUntuk himpunan kabur A dengan penulisan1 9 , 0 8 , 0 6 , 0 4 , 0 0 2 , 0 1 , 0:8 7 6 5 4 3 2 1Ax x x x x x x xmaka supp{ } { }. , , , , , , ) (3 8 7 6 5 4 2 1x X x x x x x x x A cut dari himpunan kaburMisalkan X adalah himpunan semesta. Untuk[ ], 1 , 0 yang dimaksud dengan cut dari himpunan kabur A adalah{ } . ) ( | x X x AA Untuk himpunan kabur A dengan penulisan1 9 , 0 8 , 0 6 , 0 4 , 0 0 2 , 0 1 , 0:8 7 6 5 4 3 2 1Ax x x x x x x xmaka cut 4 , 0 dari himpunan kabur A adalah { }. , , , ,8 7 6 5 4x x x x xInklusi untuk himpunan kaburDiberikan dua himpunan kabur A dan B dari himpunan semesta X. Himpunan A disebut himpunan bagian dari himpunan B ditulisB A bila. ) ( ) ( X x x xB A 37Operasi himpunan kaburDiberikanduahimpunankaburAdanBdari himpunansemestaX. Gabungan B Adari himpunan-himpunan kaburA dan B dikarakterisir dengan fungsi keanggotaan { } , ) ( ), ( ) ( X x x x maks xB A B A sedangkanirisan B A dari himpunan-himpunan kabur A dan B dikarakterisir dengan fungsi keanggotaan{ } . ) ( ), ( min ) ( X x x x xB A B A Untuk komplemen cA dari himpunan kabur A dikarakterisir dengan fungsi keanggotaan . ) ( 1 ) ( X x x xAAc SoalMisalkan himpunan semesta adalah [ ] { } . 1 0 | 1 , 0 x x X R Himpunan-himpunan kabur A, B dan Cberturut-turut dikarakterisir oleh fungsi-fungsi keanggotaan . | 5 , 0 | 1 ) ( , | 5 , 0 | ) ( , ) ( X x x x X x x x X x x xB B A Dengan menggambarkan kurva fungsi keanggotaannya, 1. Tentukan himpunan kabur. B A2. Tentukan himpunan kabur. B A3. Tentukan himpunan kabur.cA4. Tentukan himpunan kabur. C A5. Tentukan himpunan kabur. C B 6. Tentukan himpunan kabur.cB7. Tentukan himpunan kabur. C B 8. Tentukan himpunan kabur.cC38PERTEMUAN 13: ALJABAR BOOLEDefinisi dasarBaikhimpunan-himpunanmaupunpernyataan-pernyataan, keduanyamempunyai sifat-sifat 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 operasiunari , dan dua elemen yang berbeda 0 dan 1. Himpunan B disebut aljabar Boole, bila aksioma-aksioma di bawah ini dipenuhi, di manaa,b,cadalah lemen-elemen sembarang dalam B. (B1) Hukum-hukum komutatif:a b b a b a b b a a + + ) 1 ( ) 1 ((B2) Hukum-hukum distributif:) ( ) ( ) 2 ( ) ( ) ( ) ( ) 2 ( c a b a c b a b c a b a c b a a + + + + +(B3) Hukum-hukum identiti:a a b a a a + 1 ) 3 ( 0 ) 3 ((B4) Hukum-hukum komplemen:. 0 ' ) 4 ( 1 ' ) 4 ( + a a b a a aKadang-kadang aljabar Boole ditulis dengan notasi ). 1 , 0 , ' , , , ( + Bdi mana 0 disebut elemen nol, 1 disebut elemen satuan dan' adisebut komplemen dari a. Sebagaimana pada hasilkali biasa pada bilangan-bilangan real, tandatidak akan dituliskan. Misalnyaab artinya. b a 39Operasi-operasi +, dan berturut-turut disebut jumlah, hasilkali dan komplemen.Kita mengikuti aturan c b a + yangberarti), ( c b a + ' b a yangberarti ). ' (b a Contoh1. Misalkan{ } 1 , 0 B dengan dua operasi biner + danyang didefinisikan sebagai + 1 01 1 10 1 0 1 01 1 00 0 0danoperasi unari didefinisikansebagai 1 ' 0 dan . 0 ' 1 MakaBmerupakanaljabar Boole.2. MisalkanCkoleksi 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 70D adalah himpunan dari pembagi-pembagi 70 yaitu{ }. 70 , 35 , 14 , 10 , 7 , 5 , 2 , 170 DDidefinisikan +,dan pada70Dsebagai + b a kelipatan persekutuan terkecil dari a dan b, b apembagi persekutuan terbesar dari a,. / 70 ' a a Maka 70Dmerupakan aljabar Boole dengan 1 sebagai elemen nol dan 70 sebagai elemen satuan.DualitasDualdaripernyataansembarang dalam suatu aljabar BooleBadalah pernyataan yang diperoleh dengan menukar operasi-operasi + dan dan menukar elemen-elemen 0 dan 1 dalam pernyataan semula. Sebagai contoh, dual dari b b a + + ) 0 ( ) 1 ( adalah. ) 1 ( ) 0 ( b b a + 40Perhatikansifat simetri dalamaksioma-aksiomadari aljabar BooleB.Yaitu, dual dari aksiomajugaaksiomadalamaljabarBooleB.Berdasarkanhaltersebut,diperoleh hasil Prinsip Dualitas yang penting, yang dinyatakan sebagaiTeorema 1 (Prinsip Dualitas):Dualdari teorema sembarang dalam dalam aljabar Boole juga merupakan suatu teorema. Menggunakan aksioma-aksioma (B1) sampai dengan (B4) dalamaljabar BooleB, diperolehTeorema 2Misalkan c b a , , adalah elemen-elemen sembarang dalam aljabar Boole B. Maka berlaku(i) Hukum-hukum idempoten:a a a a a a + ,(ii) Hukum-hukum keterbatasan: 0 0 , 1 1 + a a(iii) Hukum-hukum absorpsi: a b a a a b a a + + ) ( , ) ((iv) Hukum-hukum asosiatif: ). ( ) ), ( ) ( c b a c b a c b a c b a + + + +Teorema 3 Misalkan a adalah elemen sembarang dalam aljabar Boole B.Maka berlaku(i) Hukum Ketunggalan Komplemen: Bila 0 & 1 + x a x a maka'. a x (ii) Hukum Involusi: 0 0 , )' ' ( a a a(iii)0 ' 1 , 1 ' 0 Teorema 4 (Hukum-hukum DeMorgan)Misalkan b a, adalah elemen-elemen sembarang dalam aljabar Boole B.Maka berlaku(i)'. ' )' ( , ' ' )' ( b a b a b a b a + +Disain rangkaian skakelar listrik (rangkaian logika)Misalkan , , B Amerupakan skakelar listrik, danmisalkanuntuk skakelarA,A menunjukkan skakelar listrik bila A hidup Amati dan bila A mati A hidup. A dan B dapat dihubungkanseri, ditulis, B Aatauparalel ditulis . B A Disainrangkaianskakelar listrikBooleadalahsusunandarikawat danskakelaryangdisusundenganpenggunaan berulang-ulang dari kombinasi seri dan paralel. Jadi rangkaian tersebut dapat dapat ditulis dengan notasi dan . Teorema 541Aljabar dari rangkaian skakelar listrik Boole merupakan aljabar Boole.Soal1.Gambarkan ungkapan (ekspresi) Boole ( ) [ ]. ' ) ' ( B C A B A Sederhanakan ungkapan (ekspresi) Boole( ) [ ] B C A B A ' ) ' (dan kemudian gambarkan hasilnya.2.Gambarkan ungkapan (ekspresi) Boole) ' ' ( )] ' ( [ B A B B A Sederhanakan ungkapan (ekspresi) Boole( ) [ ] ( ) ' ' ' B A B B A dan kemudian gambarkan hasilnya.PERTEMUAN 15: DNF (Disjunction Normal Form)Pandang himpunan dari peubah-peubah (huruf atau simbol), misalkan . , , ,2 1 nx x x Yangdimaksud denganekspresi BooleEdalampeubah-peubah ini, biasanya ditulis sebagai) , , , (2 1 nx x x E , adalah peubah sembarang atau ekspresi sembarang yang dibangunolehpeubah-peubahtersebut menggunakanoperasi-operasi Boole +,dan. Sebagai contoh, )' ' ' ( )' ' ( y x xyz z y x E + + + dan)' ' )' ' ' (( z x y z xy F + + merupakan ekspresi Boole dalam peubah x, y, z.Yang dimaksud denganliteraladalah peubah atau komplemen dari peubah, misalnya ' , , ' , y y x xdsb. 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,yz x yz y x z xy xz ' , ' , ' , , ' , 'semuanya merupakan produk fundamental. Tetapi z xyx'dan xyzykeduanya bukan produk fundamental.Produk fundamental1P dikatakantermuat dalamprodukfundamental lain2P bila literal-literal dari1P juga iteral-literal dari .2P Sebagai contohz x' termuat dalam z y x'tetapi tidak dalam , ' z xy karena x bukan literal dariproduk fundamental kedua.42Bila produk fundamental1P termuat dalam produk fundamental ,2P maka dengan hukum absorpsi.1 2 1P P P + Misalnya' actermuat dalam , ' b ac diperoleh'. ) ' ( ' ac b ac ac +DNF & MetodanyaEkspresi BooleanEmerupakandisjunctive normal form(dnf)bilaEadalah 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, ' ' '1z y x z y z x E + + dan'. ' ' ' '2z y x z y x z x E + + Yang pertama bukan dnf karena ' z x termuat dalam , ' z y xsedang yang kedua juga bukan dnf karena' xztermuat dalam '. ' z xyMenggunakan hukum-hukum aljabar Boole, kita dapat mengkonstruksikan algoritma untuk mengubah ekspresi Boole sembarang E ke bentuk dnf, dengan cara sbb.(1) Menggunakanhukum-hukumdeMorgandaninvolusi, kitadapat menjalankan operasi komplemen ke dalam kurung sembarang sampai akhirnya hanya terdapat komplemendaripeubah-peubah. KemudianEhanyamengandungjumlahandan produk dari literal saja.(2)Menggunakan hukum distributif, kita dapat terus mengubah E ke dalam jumlahan dariproduk-produk, lalumenggunakanhukum-hukum komutatif,idempoten dan absorpsi, kita akhirnya dapat mengubah E dalam dnf.Sebagai contoh, dengan (1) ). ' )( ' () )' ' ' ( )' ' )(( ' ' )' (( ))' ' ' )( ' (( )' )' ((bc ac c abc b c a c ab c b c a c ab E+ + + + + + + + Kemudian dengan (2),, ' 0 ' ' ' ' ' ' abc ac ac abc abc bcc c ac abbc abac E + + + + + + + yang berbentuk dnf.Full DNFEkspresi Boole) , , , (2 1 nx x x E disebut full disjunctive normal form bila ) , , , (2 1 nx x x E 43merupakan dnf dan setiap produk fundamental mengandung semua peubah. Kita dengan mudah dapat mengubah dnf ke dalamfull dnf dengan mengalikan setiap produk fundamentalPdariE dengan 'i ix x +bila Ptidak mengandung .ixSebagai contoh, kita dapat mengubah ) , , ( c b a E E di atas ke dalam full dnf dengan. ' ' ' ) ' ( ' ' abc c ab abc abc b b ac abc ac E + + + + + Perlu dicatat bahwa , 1 ' +i ix xsehingga mengalikanPdengan 'i ix x + dibolehkan.TeoremaSetiap ekspresi Boole ) , , , (2 1 nx x x E yang tidak sama dengan nol dapat dituliskan dalam full dnf dengan tunggal.Contoh1. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf)'. ' ( ) , , (1 1z y x z y x E E Solusi, ' ) ' ( )' ' (1xz xy z y x z y x E + + dalam dnf.Juga, , ' ' ' ' ' ' '' ) ' ( ) ' ( '1z xy xyz xyz z xy xyz xyz xyzz y y x z z xy xz xy E+ + + + + + + + + dalam full dnf.2. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf '. ) ' ( ) , , (2 2y y x z z y x E E + + Solusi, ' ' ' ) ' (2y yz z x y y x z E + + + + dalam dnf. Juga,, ' ' ' ' ' ' ' ' '' ' ' ' ' ' ' ' ' ' ' ') ' )( ' ( ' ) ' ( ) ' ( ' ' ) ' (2z y x z y x yz x z xy z xy xyzz y x z y x z xy z xy yz x xyz z y x yz xz z x x y x x yz y y z x y y x z E+ + + + + + + + + + + + + + + + + + + + + + dalam full dnf.3. Nyatakan ekspresi Boolean berikut dalam dnf dan dalam full dnf44

. ' )' ' ( ) , , (3 3y x y x z y x E E + + Solusi, ' ' ' )' ' (3y x xy y x y x E + + + dalam dnf. Bentuk terakhir ini bisa dipandang sebagai dalam bentukfull dnf bilapeubah-peubahnyahanyaxdany. Tetapi dalamsoal jelasbahwa peubah-peubahnya diketahui dalam x, y, z. Jadi, ' ' ' ' ' ') ' ( ' ) ' ( ' ' ' ' )' ' (3yz x yz x z xy z xyz z y x z z xy y x xy y x y x E+ + + + + + + + + dalam full dnf. PERTEMUAN 16: TEORI GRAPHPengertian dan konsep dasarGraph G terdiri dari dua bagian:(i) Himpunan Vyang elemen-elemennya disebut titik-titik atau nodes.(ii) HimpunanEdari pasangan-pasangan tak berurutan dari titik-titik yang berlainan yang disebut rusuk-rusuk atau edges.Kita menulis graph sedemikian dengan ) , ( E V Guntuk menekankan dua bagian dari graph G tersebut. Titik-titik u dan v disebut bersebelahan atau adjacent bila terdapat rusuk }. , { v u Kitamenggambarkangraphdengandiagramsecaraalami. Dalamhal ini setiaptitikv dalam Vdisajikan dengan lingkaran kecil atau dot, dan setiap rusuk} , {2 1v v e disajikan dengan kurva yang menghubungkan titik-titik ujung 1vdan.2vPadagraph) , ( E V Gbiasanyatidak dibolehkan adanya rusuk ganda ataumultiple edges, yaitu adanya lebih dari satu rusuk yang menghubungkan dua titik pada graph tersebut. Pada graph ) , ( E V Gjuga tidak dibolehkan adanyaloop, yaitu rusuk yang titik-titik ujungnya sama. Graph) , ( E V Gdenganduasifat ini disebutmultigraph. Yangdimaksuddengan walkadalahmultigraphyangterdiri dari barisanyangbergantiandari titikdanrusuk dengan bentuk. , , , , , , , , ,1 1 2 2 1 1 0 n n n nv e v e v e v e v Sedangkan path adalah walk di mana semua titik-titiknya berlainan. 45Misalkan ) , ( E V G adalah graph. Misalkan juga V himpunan bagian dari V , dan E adalah himpunanbagian dariEyangmemuat semua rusukdariEyangtitik-titikujungnya merupakanelemendariV. Dalamhal ini) ' , ' ( E V Gmerupakansubgraphdari graph ). , ( E V GKomponen darigraphGraph ) , ( E V Gdisebut terhubung atau connected bila antara dua titik sembarang terdapat suatupathyang menghubungkan dua titik tersebut. Subgraph terhubung dari graph ) , ( E V Gdisebut komponen terhubung dari ) , ( E V Gbila dia tidak termuat dalam subgraph terhubungsembarangyanglebihbesar. Secaraintuitif jelasbahwasetiapgraphdapat dipartisi ke dalam komponen-komponen terhubungnya.Jarak antara dua titik dan diameterJarak antara dua titik u dan v dari graph terhubung G, ditulis ) , ( v u d, adalah panjangdari pathterpendek antara udan v. Diameter dari graph terhubung Gadalah jarak maksimum dari dua titik sembarang dari G.Misalkan v adalah titik dari graph G. Yang dimaksud denganv G adalah adalah graph yang diperoleh dariGdengan menghilangkan vdan semua rusuk-rusuk yang berinsiden dengan v. Titik v dalam graph terhubung G disebut titik potong atau cut point bilav G menjadi tak terhubung.46PERTEMUAN 20: PEWARNAAN GRAPHPewarnaan titikPewarnaan titik dari graphGadalah penentuan warna pada titik-titikG, sedemikian sehingga titik-titik yang bersebelahan mempunyai warna-warna berlainan.Banyaknya warna minimum yang diperlukan untuk mewarnai G disebut bilangan kromatik atau chromatic numberdariGdan 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 degreesama). Langkah kedua adalah memberikan warna pertama untuk titik pertama. Untuk mewarnai selanjutnya adalah secara barisan, warnai setiap titik yang tidakbersebelahandengantitikyangdiwarnai sebelumnyadenganwarnayangsama. Ulangi prosesyangsamamenggunakanwarnakeduadanbarisanbagiandari titik-titik yang belum diwarnai. Lanjutkan prosesnya dengan warna ketiga, dst. sampai semua titik-titikterwarnai. Kitamemakai algoritmaWelch-Powell untukmewarnai graphGpada Gambar 6-5. Mengurutkan titik-titik menurut degreenya yang menurun diperoleh barisan. , , , , , , ,8 6 4 2 1 7 3 5A A A A A A A AWarnapertamadigunakanuntukmewarnai titik-titik5Adan .1A Warnakeduadipakai untukmewarnai titik-titik. , ,8 4 3A A AWarna ketiga dipakai untuk mewarnai titik-titik 472 7, A Adan ,6Asehingga . 3 ) ( G Perlu dicatat bahwa , 2 ) ( > G karena 2 1, A A dan 3A harus diwarnai berlainan. Jadi. 3 ) ( G Juga, graph komplit atau lengkap nKdengan n titik simpul memerlukan nwarna dalam pewarnaan sembarang, karena setiap titik simpul bersebelahan dengan setiap titik simpul lainnya. Contoh1. Perhatikan Gambar 6-18. Gunakan algoritma Welch-Powell untuk mewarnai (pewarnaan titik) graph pada gambar tersebut.SolusiDikerjakan secara barisan, kita pakai warna pertama untuk mewarnai titik-titik simpul H, B, dan lalu G.( Kita tidak dapat mewarnaiA,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,Cdan E dapat diwarnai dengan warna ketiga. Jadi bilangan kromatik ntidak dapat melebihi 3. Pada setiap pewarnaan,H,D, dan E harus diwarnai berlainan, karena mereka terhubung satu sama lain. Jadi. 3 nPewarnaan rusukPewarnaan rusuk dari graph G adalah penentuan warna pada rusuk-rusuk G, sedemikian sehinggarusuk-rusuk yangbersebelahan mempunyai warna-warna berlainan. Banyaknya warna yang diperlukan dibuat minimum.Contoh1. Perhatikan graph pada halaman 149. Pewarnaan rusuk graph tersebut dikerjakan sebagai berikut:1) 1e kita beri warna pertama.2)4e dan9ekitaberi warnapertamajuga, karena4 1, e e dan9etidaksalingterhubung langsung oleh sebuah titik.3) 2ekita beri warna kedua. 4) 5e dan 7edapat diberi warna kedua juga, karena 5 2, e edan 7ejuga tidak saling terhubung melalui sebuah titik.5) 3e dan 8e dapat diberi warna ketiga.486) Terakhir, 6e kita beri warna keempat. Jadi bilangan kromatik (pewarnaan rusuk) dari graph di atas adalah empat, atau . 4 ) ( G 2.Pada pewarnaan rusuk untuk graph lengkap ,nbilangan kromatik dari nmemenuhi rumus:'. , 1,) (genap n bila nganjil n bila nn Pewarnaan daerahPandang 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 149Contoh1. Sebagai contoh, pada Gambar 6-6 (a) daerah-daerah 2rdan 5r bersebelahan, sedangkan 3rdan5rtidak. MappadaGambar 6-6(a) mempunyai bilangankromatiktiga, yaitu banyaknya warna minimum untuk pewarnaan daerah dari map tersebut. Hal ini mengingat: 1rdiberi warna merah, 2r putih, 3r merah, 4r putih, 5r merah dan6r biru. 2. Gambar 6-7memperlihatkanmapyangsangat sederhana, yangmemerlukanempat warna pada pewarnaan (daerah) sembarang.Soal491. Carilah bilangan kromatik untuk pewarnaan daerah pada setiap map pada Gambar 6-30. PERTEMUAN 21: TREE GRAPHSuatu graph terhubung tanpacycledisebuttreeatau pohon. Pada Gambar 5-11 diperlihatkanenampohonmasing-masingdenganenamtitiksimpul. SubgraphTdari graphGdisebutspanningtreedari GbilaTmerupakantreedanmemuat semuatitik simpul dari G. Gambar 6-8 memperlihatkan graph G dengan spanning trees 2 1,T Tdan 3TdariG. Bila G adalah suatu graph yang rusuk-rusuknya mempunyai panjang, maka yang dimaksuddenganminimal spanningtreedari Gadalahspanningtreedari G di mana jumlahpanjangdari rusuk-rusuknyaminimal di antara semuaspanningtree dari G. Pandang graph G yang merupakan graph terhubung berlabel berhingga dengan m titik-titik simpul. Di bawah ini kita berikan dua algoritma untuk mendapatkan minimal spanning tree dari G.Algoritma I.Pertama, urutkanrusuk-rusuk dariG sesuaidenganpanjangnya secara menurun. Kerjakansecara barisan, hilangkansetiaprusukyangtidakmemutus (membuat tidak 50terhubung)graphGsampaitinggal 1 m rusuk.Rusuk-rusuk ini membentukminimalspanningtreedariG.Algoritmaini 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 denganhanya titik-titik simpul dari G, kita tambahkan rusuk satupersatudi manasetiaprusukpunyapanjangminimal dantidakmembentukcycle manapun. Setelah menambahkan 1 mrusuk, kita dapatkanminimal spanning tree dariG. Gambar 6-9 memberikan graph terhubung berlabel G dan minimal spanning tree M.Contoh1.Tentukan semua spanning trees dari graph G pada Gambar 6-20.Solusi Terdapat delapan spanning trees dari graph G sebagaimana diperlihatkan pada Gambar 6-21. 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-rusukberlabel pada Gambar 6-22.Solusi Terus hilangkan rusuk-rusuk dengan panjang maksimum tanpa membuat graph menjadi tidak terhubung. Cara lain, mulai dengan sembilan titik simpul, terus tambahkan rusuk-rusuk dengan panjang minimum tanpa membuat cycle manapun. Kedua cara menghasilkan minimum spanning tree sebagaimana ditunjukkan pada Gambar 6-23. 51PERTEMUAN 23: FINITEAUTOMATAKita bisa memandang suatu komputer digital sebagai suatu mesin yang berada di dalam internal state tertentu pada waktu yang diberikan sembarang. Komputer tersebut membacainput symbol, dankemudianmencetakoutput symboldanmengubah statenya.Output symbolbergantunghanyapadainput symboldaninternal statedari mesin, dan internal statedari mesin bergantung hanya pada statesebelumnya dan input symbol sebelumnya. Gagasan ini diformalisasikan pada definisi berikut.DefinisiSuatu 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 fdariA S ke S.(5) Output function g dariA S ke Z.52MesinMini ditulis dengang f Z S A M ,. , , , sewaktu kita ingin menekankan lima bagiannya. Kadang-kadang diberikan juga initial stateatau state awal0qdi dalam S, dan mesin M ditulis dengan . ,. , , , ,0g f q Z S A MContohDi bawah inidiberikan finite state machine M dengan dua input symbols, tiga internal states dan tiga output symbols:(1) } , { b a A (2)} , , {2 1 0q q q S (3)} , , { z y x Z (4) Next-state function fdariA S ke S didefinisikan dengan ( ). ) , ( ) , ( ) , (, ) , ( ) , (1 2 1 1 2 00 2 2 1 1 0q b q f q b q f q b q fq a q f q a q f q a q f (5) Output function g dariA S ke Z didefinisikan dengan ( ). ) , ( ) , ( ) , (, ) , ( ) , (2 1 02 1 0y b q g z b q g y b q gz a q g x a q g x a q g Menurut tradisi,untuk menunjukkan statesdigunakan simbolqdan untuk menunjukkan initial state digunakan simbol .0qFinite AutomataFinite automatonadalah 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)(4)Initial state 0qdi dalam S.(5) Next-state function f dariA S ke S.AutomatonM ini ditulis dengan f q T S A M ,. , , ,0sewaktu kita ingin menekankan lima bagiannya. Contoh531. Di bawah ini mendefinisikan suatu finite automaton dengan dua input symbols dan tiga states:(1) } , { b a A , input symbols(2) states q q q S }, , , {2 1 0(2)} , {1 0q q T , accepting states(4)0q, initial state.(5) Next-state function fdariA S ke S didefinisikan dengan ( ). ) , ( ) , ( ) , (, ) , ( ) , (2 2 2 1 1 02 2 0 1 0 0q b q f q b q f q b q fq a q f q a q f q a q f Kita denganringkas dapat mendiskripsikanfiniteautomatonMdenganstate diagramnya sebagaimanadikerjakan denganfinite state machine, kecuali bahwa di sini kita menggunakan lingkaran dobel untuk accepting statesdan setiap rusuk dilabel hanya dengan input symbol. Secara spesifik,statediagram DdariMadalah graph berarah yang dilabel yang titik-titiknya adalahstatesdariSdi manaaccepting statesdilabel menggunakan lingkaran dobel; dan bila , ) , (k i jq a q f maka terdapat busur dari jq ke kqyangdilabeldengan.iaJugainitial state 0qditunjukkan dengan panah menuju titik .0qSebagai contoh,statediagramdari automatonM dari contohdi atasdiberikandalam Gambar 7-9.Diberikan string berhingga na a a a W 3 2 1dari input symbols dari automaton M, kita peroleh barisan daristates ns s s s 2 1 0di mana0sadalah initial state dan ) , (1 i i ia s f suntuk. 0 > i Kita katakan bahwa M mengenal atau menerima string Wbila final state nsadalahaccepting state,yaitu bila. T sn Kita gunakan) (M Luntuk menunjukkanhimpunansemuastringyangdikenal olehM.Sebagai contoh, kitadapat memperlihatkan bahwaautomatonM dalam contoh di atas akan mengenal semuastring yang tidak mempunyai dua b yang berurutan . Jadi M akan menerima abaaababab baab aaa aababaaba , , ,dan akan menolak abbbaa bb ababbaab bbaaa aabaabba , , , ,5455