MatematikaSekolah Menengah Pertama terjawab Di antara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 mempelajari matematika dan biologi, 7 mempelajari matematika dan fisika, 10 mempelajari fisika dan biologi, dan 30 tidak mempelajari satupun diantara bidang tersebut.

Origin is unreachable Error code 523 2023-06-14 175928 UTC What happened? The origin web server is not reachable. What can I do? If you're a visitor of this website Please try again in a few minutes. If you're the owner of this website Check your DNS Settings. A 523 error means that Cloudflare could not reach your host web server. The most common cause is that your DNS settings are incorrect. Please contact your hosting provider to confirm your origin IP and then make sure the correct IP is listed for your A record in your Cloudflare DNS Settings page. Additional troubleshooting information here. Cloudflare Ray ID 7d74772f1db6b7ea • Your IP • Performance & security by Cloudflare

Masukanrumus diatas sesuai dengan nilai yang sudah tercantum. G = 12.000 - 6.000 - 5.000 - 4.000. = 0 (pembeli satu cindera mata dari gantungan kunci) Jika sudah ditemukan pembeli satu cindera mata dari masing masing cindera mata selanjutnya kamu hitung dengan menjumlahkan semua coba perhatikan dibawah ini. S + B + G = 2000 + 17.000 + 0. 0% found this document useful 0 votes399 views6 pagesOriginal TitleTUGAS MATEMATIKA DISKRIT 2 marCopyright© © All Rights ReservedShare this documentDid you find this document useful?0% found this document useful 0 votes399 views6 pagesTUGAS MATEMATIKA DISKRIT 2 MarOriginal TitleTUGAS MATEMATIKA DISKRIT 2 marJump to Page You are on page 1of 6 You're Reading a Free Preview Pages 4 to 5 are not shown in this preview. Reward Your CuriosityEverything you want to Anywhere. Any Commitment. Cancel anytime.
Diantara100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, Hitunglah banyaknya mahasiswa yang mempelajari hanya satu diantara ketiga bidang tersebut. Page-14 6. Dari 200 siswa, 50 mempelajari Matematika Diskrit,
MATEMATIKA DISKRIT Logika Proposisi    Edisi 2 MATEMATIKA DISKRIT Samuel Wibisono Logika Proposisi MATEMATIKA DISKRIT Oleh Samuel Wibisono Editor Asrining Rizky Rachmawati Edisi Kedua Cetakan Pertama, 2008 Hak Cipta © 2005, 2008 pada penulis, Hak Cipta dilindungi undang-undang. Dilarang memperbanyak atau memindahkan sebagian atau seluruh isi buku ini dalam bentuk apa pun, secara elektronis maupun mekanis, termasuk memfotokopi, merekam, atau dengan teknik perekaman lainnya, tanpa izin tertulis dari penerbit. Candi Gebang Permai Blok R/6 Yogyakarta 55511 Telp. 0274-882262; 0274-4462135 Fax. 0274-4462136 E-mail info Wibisono, Samuel MATEMATIKA DISKRIT/Samuel Wibisono - Edisi Kedua – Yogyakarta; Graha Ilmu, 2008 xii + 196 hlm, 1 Jil. 23 cm. ISBN 978-979-756-413-1 1. Matematika I. Judul    KATA PENGANTAR Memasuki era globalisasi, mempersiapkan sumber daya manusia yang profesional dalam bidangnya merupakan prasyarat utama untuk dapat survive dalam pasar global yang penuh tantangan dan persaingan. Dengan latar belakang tersebut di atas dan banyaknya keluhan pembaca tentang “Apa manfaat belajar matematika buat mereka? atau Apa hubungan matematika yang mereka pelajari dengan jurusan yang mereka ambil?”, penulis menyadari bahwa sasaran dalam proses pembelajaran mata kuliah ini harus dipertajam, sehingga mampu mendukung terciptanya sarjanasarjana baru dalam bidang teknik informatika, sistem informatika, manajemen informatika, maupun teknik komputer, yang handal dan mempunyai daya saing yang tinggi karena telah dibekali dengan logika dan konsep dasar matematika diskrit, sehingga mampu menyelesaikan segala persoalan yang dihadapi, melalui rancangan usulan penyelesaian problem atau kasus. Hasil proses pembelajaran yang penulis harapkan setelah pembaca membaca buku ini, adalah Logika Proposisi ° Pembaca mengenal konsep dasar logika dan matematika diskrit dengan baik. ° Pembaca memahami konsep dasar logika dan matematika diskrit sehingga mampu menggunakannya untuk menyelesaikan permasalahan yang sesuai. ° Pembaca dapat merancang, menganalisa dan mensintesa beberapa kasus aplikasi dalam berbagai bidang, khususnya TI dan komputer. Pada kesempatan ini penulis menyampaikan terimakasih kepada Pimpinan dan Staf Universitas Bina Nusantara dan Universitas Indonesia Esa Unggul, di mana penulis diberi kesempatan mengampu mata kuliah Matematika Diskrit ini, rasa terima kasih juga penulis sampaikan kepada Penerbit Graha Ilmu yang telah memberikan kepercayaan, sehingga buku edisi 2 ini dapat diterbitkan. Terakhir, kami sampaikan rasa terima kasih kepada rekan-rekan dosen pengampu mata kuliah Matematika Diskrit utamanya Dr. Frans Susilo SJ. yang berkenan memberikan kritik dan saran yang membangun guna penyempurnaan buku ini, kritik dan saran yang membangun dari rekan-rekan masih kami tunggu untuk edisi mendatang. Demikian semoga bermanfaat. Jakarta, Agustus 2008 Samuel Wibisono     DAFTAR ISI KATA PENGANTAR DAFTAR ISI BAB 1 LOGIKA PROPOSISI Pernyataan Pernyataan Gabungan Konjungsi Disjungsi Negasi Jointdenial Not OR/ NOR Not And NAND Exclusive or exor Exclusive NOR ExNOR Tautologi dan kontradiksi Tautologi Kontradiksi Kesetaraan Logis Aljabar Proposisi Implikasi dan Biimplikasi Implikasi   v vii 1 1 2 2 4 6 7 7 8 9 10 10 10 11 12 14 14  Biimplikasi Argumentasi Kebenaran/Validitas Argumen Bentuk-bentuk Dasar Menarik Kuantor Pernyataan Macam-macam Kuantor Negasi Kauntor BAB 2 18 18 19 21 25 26 27 TEORI HIMPUNAN Himpunan Kardinalitas Himpunan Berhingga dan Tak Berhingga Kesamaan Dua Himpunan dan Subhimpunan Macam-macam Himpunan Operasi Himpunan Union/Gabungan dari 2 himpunan Intersection/Irisan dari 2 Himpunan Relative Acomplement/Selisih Antara 2 Himpunan Komplemen dari Himpunan Symmetic Difference/Beda Setangkup Diagram Venn Hukum-hukum Aljabar Himpunan Perhitungan Himpunan Gabungan Gabungan dari 2 Himpunan Gabungan dari 3 Himpunan BAB 3 TEORI HIMPUNAN FUZZY Fungsi keanggotaan Operasi himpunan fuzzy Komplemen Gabungan/Union Himpunan Fuzzy  31 31 32 33 34 36 36 36 37 37 37 38 38 39 41 41 42 49 49 51 51 52    Irisan/Itersection Himpunan Fuzzy Pemotongan/Cut Himpunan Fuzzy Pendukung Support Himpunan Fuzzy Scalar Cardinality Kesamaan dan Himpunan Bagian 53 54 57 59 60 BAB 4 LOGIKA FUZZY Pengantar Logika dengan Nilai Kebenaran Beragam Soal-soal 67 67 68 72 BAB 5 RELASI KLASIK Pendahuluan Pemaparan Relasi Pemaparan Koordinat Pemaparan Matrik Pemetaan Graph Berarah Operasi dalam Relasi binary Inverse Relasi R–1 Komposisi Relasi Ekivalen, Kompatibel dan Ordering Relasi Relasi Ekivalen Relasi Kompatibel Poset Partially Orderet Set 75 75 77 77 78 78 79 80 80 81 82 82 85 86 FUNGSI Definisi Fungsi Macam-macam Fungsi Fungsi satu-satu Fungsi pada Fungsi konstan Fungsi Invers Komposisi Fungsi Fungsi Karakteristik 93 93 94 94 95 96 96 98 99 BAB 6    BAB7 BAB 8 BAB 9 ALJABAR BOOLE 103 Aplikasi Aljabar Boole dalam Jaringan Switching 103 Aplikasi Aljabar Boole pada Rangkaian Logik Gate 107 Aplikasi Aljabar Boole dalam Operasi Kelipatan Persekutuan Kecil KPK dan Faktor Persekutuan Besar FPB 111 Minimal dnf Disjunctive Normal Form 113 Dengan Teori Include dan Konsensus 113 Peta Karnaugh 116 TEORI GRAPH Pendahuluan Macam-macam Graph Koneksitas Berkaitan dengan Jarak Derajat/Degree suatu titik Titik Potong Graph Cut Point Ukuran secara grafikal Matrik Graph Labeled Digraph Derajat Titik pada Diagraph Graph Bidang Planar Graph Pewarna Peta Pohon/Tree Spanning Tree Pohon Berakar Rooted Tree Pohom Berurut Berakar Orderd Rootes Tree 125 125 127 132 134 136 137 138 139 141 144 145 147 159 161 163 MESIN MATEMATIK Pendahuluan Finite Automata FA 175 175 177 167    Menggambarkan FA dengan Digraph Menggambarkan FA dengan Difinisi Formal 5-Tuple Menggambarkan FA dengan Tabel State Non-Deterministik Finite Automata NFA Finite State Transducers DAFTAR PUSTAKA TENTANG PENULIS 178 180 181 181 189 193 195 -oo0oo-       1 LOGIKA PROPOSISI P Logika proposisi sering juga disebut logika matematika ataupun logika deduktif. Logika proposisi berisi pernyataan-pernyataan dapat tunggal maupun gabungan. Pernyataan adalah kalimat deklarasi yang dinyatakan dengan huruf-huruf kecil, misalnya p, q, r, s Pernyataan mempunyai sifat dasar yaitu dapat bernilai benar pernyataan benar atau bernilai salah pernyataan salah, tetapi tidak mungkin memiliki sifat kedua-duanya. Kebenaran atau kesalahan sebuah pernyataan dinamakan nilai kebenaran dari pernyataan tersebut. Contoh 1. Bilangan biner digunakan dalam sistem digital adalah pernyataan yang benar. Logika Proposisi 2. Sistem analog lebih akurat daripada sistem digital adalah pernyataan yang salah. 3. Astaga, mahal sekali harga notebook itu adalah kalimat keheranan, bukan pernyataan. 4. Siang tadi notebook Ira jatuh dari meja adalah bukan pernyataan karena dapat bernilai benar maupun bernilai salah. 5. Corezdeo lebih bagus kinerjanya dan lebih mahal dari pentium IV generasi sebelumnya adalah pernyataan yang benar. Kalimat-kalimat yang tidak termasuk pernyataan, adalah ³ ³ ³ ³ ³ Kalimat Kalimat Kalimat Kalimat Kalimat perintah pertanyaan keheranan harapan walaupun .. P G   Beberapa pernyataan dapat digabung dengan kata penghubung dan, atau, tidak/bukan, serta variatifnya, yang selanjutnya disebut pernyataan gabungan atau pernyataan majemuk atau compound statement. Macam-macam pernyataan gabungan. Konjungsi Konjungsi adalah pernyataan gabungan dari dua pernyataan dengan kata penghubung dan Notasi-notasi konjungsi R ™ S , p x q, pq Bagaimana menentukan benar atau salah sebuah konjungsi? Konjungsi dianalogikan dengan sebuah rangkaian listrik seri    A B i – + Bila lampu B dan lampu A hidup maka arus listrik dapat mengalir dari kutup positip menuju kutup negatip sebuah baterai, akibatnya kedua lampu A dan B menyala/ lampu B mati dan lampu A hidup atau sebaliknya, maka arus listrik tidak dapat mengalir menuju kutub negatip baterai, akibatnya kedua lampu A dan B tidak menyala/mati. Demikian juga bila lampu A dan B mati. Dengan demikian dapat di simpulkan bahwa konjungsi benar bila keduanya hidup, selain itu salah. Tabel Kebenaran Konjungsi p q R™S + + – – + – + – + – – –  p ∧ q + + – – + – – – + – + – dimana + berarti benar dan - berarti salah Contoh p q = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar.     r s = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam sistem digital adalah pernyataan yang salah = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. Maka R™S q×r adalah konjungsi yang benar karena p benar, q benar. adalah konjungsi yang salah karena q benar, r salah. adalah konjungsi yang salah karena r salah, s salah. Disjungsi Disjungsi adalah pernyataan gabungan dari dua pernyataan dengan kata penghubung atau. Notasi-notasi disjungsi R š SR S Bagaimana menentukan benar atau salah sebuah disjungsi? Disjungsi dapat dianalogikan dengan sebuah rangkaian listrik yang pararel A B i – +    Bila lampu A dan lampu B hidup maka arus listrik i dapat bergerak/mengalir dari kutup positip ke kutup negatip sebuah baterai, akibatnya lampu A dan B menyala. Bila lampu A hidup dan lampu B mati atau sebaliknya, maka arus listrik i masih dapat mengalir dari kutup positip ke kutup negatip sebuah baterai. Akibatnya lampu yang hidup akan menyala dan yang mati tidak menyala. Bila lampu A dan B mati, maka arus listrik i tidak dapat mengalir ke kutup negatip. Dengan demikian dapat disimpulkan bahwa disjungsi salah bila kedua lampu mati, selain itu benar. Tabel Kebenaran Disjungsi p q RšS p ∨ q + + – – + – + – + + + – + + + + –  + – – + – + – Catatan Simbol tabel kebenaran yang biasa digunakan Benar Salah = T, B, +, 1 = F, S, –, 0 Contoh p q r = keyboard adalah alat yang dapat digunakan untuk input data kedalam komputer adalah pernyataan benar. = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah. = Procesor alat yang berfungsi sebagai otak dari sebuah komputer adalah pernyataan benar.    s = Windows XP adalah sistematika menulis buku adalah pernyataan salah. Maka QšR QšS R∨T adalah disjungsi yang benar karena p benar, q salah. adalah disjungsi yang benar karena p benar, r benar. adalah disjungsi yang salah karena q salah, s salah. Negasi Negasi adalah sebuah pernyataan yang meniadakan pernyataan yang ada, dapat di bentuk dengan menulis “adalah salah bahwa ” atau dengan menyisipkan kata “ tidak” dalam sebuah pernyataan. Notasi-notasi negasi ′ Contoh p = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah Maka ~ p = Adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. Jadi kebenaran sebuah negasi adalah lawan dari kebenaran pernyataannya. Tabel kebenaran negasi p + – ~p – +    Jointdenial Not OR/ NOR Jointdenial adalah pernyataan gabungan yang dihasilkan dari menegasikan disjungsi. Notasi NOR R ↓ SRPQTS` R ∨ S Karena jointdenial adalah negasi dari or, maka tabel kebenaran NOR adalah sebagai berikut p q RšS RoS + + – + – + – + + + – – – – + – ~ p ∨ q  – – – + + + – – + + + – + – + – Not And NAND NAND adalah pernyataan gabungan yang dihasilkan dari menegasikan konjungsi. Notasi NAND ∧ ∧ ′ Karena NAND negasi dari konjungsi, maka tabel kebenaran NAND adalah sebagai berikut p q R™S + + – – + – + – + – – –    ` R ∧ S – + + +  ~ p ™ q – + + + + + – – + – – – + – + – Exclusive or exor Exor adalah pernyataan gabungan dimana salah satu p atau q tidak kedua-duanya adalah benar Notasi exor RšS Contoh p q r s = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu. adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar. = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam system digital adalah pernyataan yang salah. = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. Maka RšS adalah exor yang salah karena p benar, q benar. Q š S adalah exor yang benar karena p benar, r salah. T š R S š T adalah exor yang benar karena q benar, s salah. adalah exor yang salah karena r salah, s salah. dengan demikian tabel kebenaran exor dapat ditulis sebagai berikut R S R∨S R X S − − − − − − CVCW − − − − − −    Exclusive NOR ExNOR EXNOR adalah pernyataan gabungan ingkaran dari EXOR di mana nilai kebenarannya benar bila kedua pernyataannya benar atau salah. Notasi EXNOR ~ p∨ q Contoh p q r s = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu. adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar. = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam sistem digital adalah pernyataan yang salah = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. Maka p EXNOR q, adalah p EXNOR r, adalah s EXNOR q, adalah r EXNOR s, adalah pernyataan pernyataan pernyataan pernyataan yang yang yang yang benar salah salah benar Dengan demikian tabel kebenaran EXNOR    p q + + – – + – + – ` R∨S + – – + T  K  Proposisi dipandang dari nilai kebenarannya dapat digolongkan menjadi 2 yaitu Tautologi Tautologi adalah proposisi yang selalu benar apapun pernyataannya. Notasi tautologi p v ~p Contoh p = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah ~p = adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. Maka R∨ ` R adalah proposisi yang benar Tabel kebenaran tautologi p `S + – – + R∨ ` R + +  p š `R + – + + – + Kontradiksi Kontradiksi adalah proposisi yang selalu salah apapun pernyataannya Notasi kontradiksi R∧ ` R    Contoh p = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah ~p = adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. Maka R∧ ` R adalah proposisi yang salah Tabel kebenaran kontradiksi p `R + – – + R∧ ` R – – K L Dua buah pernyataan yang berbeda dikatakan setara bila nilai kebenarannya sama Contoh 1. Tidak benar, bahwa aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan benar. 2. Aljabar Boole adalah alat matematika dasar untuk disain logika adalah pernyataan benar. Kedua pernyataan di atas mempunyai nilai kebenaran yang sama. Jadi kedua pernyataan di atas setara/ekivalen. Akibatnya dua proposisi Pp, q, r, ... dan Qp, q, r, ... dapat dikatakan setara jika memiliki tabel kebenaran yang sama. Dua buah proposisi yang setara dapat dinyatakan dengan Pp, q, r, ... ≡ Qp, q, r, ....    Contoh Selidiki apakah kedua proposisi di bawah setara 1. Tidak benar, bahwa sistem bilangan biner digunakan dalam sistem digital atau sistem digital hanya dapat mengasumsikan nilai yang berlainan. 2. Sistem bilangan biner tidak digunakan dalam sistem digital dan tidak benar bahwa sistem digital hanya dapat mengasumsikan nilai yang berlainan. Kedua proposisi di atas dapat dituliskan dengan notasi sbb 1. ∨ 2. ~ R∧ ` S sehingga tabel kebenarannya sebagai berikut R S `R `S R ∨ S ` R ∨ S ` R∨` S − − − − − − − − − − − − − − − Jadi, kedua proposisi tersebut setara atau ∨ ≡ ∧ A P Aljabar proposisi merupakan penerapan hukum-hukum aljabar dalam logika proposisi. Hukum-hukum tersebut adalah 1. Idempoten RšR z R R™R z R    2. Asosiatif R š S š T z R š S š T R ™ S ™ T z R ™ S ™ T 3. Komutatif RšS z SšR R™S z S ™R 4. Distribusi R š S ™ T z R š S ™ R š T R ™ S š T z R ™ S š R ™ T 5. Identitas š z  ™ z š z  ™ z 6. Komplemen R∨ ` R = V ` V = H R ∧ ` R = H ` H = V 7. Involution ≡ 8. De Morgan’s ` R ∧ S =` R ∨ S ` R ∨ S =` R ∧ ` S 9. Absorbsi R ∨ R ∧ S ≡ R R ∧ R ∨ S ≡ R 10. Implikasi R → S =` R ∨ S 11. Biimplikasi ↔ = → ∧ →     12. Kontraposisi R → S =` S →` R Salah satu manfaat hukum-hukum aljabar proposisi adalah untuk menyederhanakan pernyataan gabungan. Contoh Sederhanakan proposisi di bawah buktikan hukum. Absorbsi R ™ R š S z R š H ™ R š S z R š H ™ S z RšH zR I  B  Implikasi Perhatikan pernyataan berikut jika memakai Microsoft Word maka Windows adalah sistem operasinya. Microsoft Word merupakan syarat cukup bagi Windows, sedangkan Windows merupakan syarat perlu bagi Microsoft Word, artinya Microsoft Word tidak dapat digunakan tanpa windows tetapi Windows dapat digunakan tanpa Microsoft Word. Contoh pernyataan di atas disebut pernyataan bersyarat atau conditional statement. Notasi implikasi R nS dibaca jika p maka q    Kebenaran implikasi 1. Jika Microsoft Word maka Windows sistem operasinya adalah implikasi benar, karena keduanya buatan Microsoft. Mengacu pada implikasi di atas maka 2. Jika Microsoft Word maka bukan Windows sistem operasinya adalah pernyataan salah, karena sistem operasi Microsoft Word adalah Windows 3. Jika bukan Microsoft Word maka Windows sistem operasinya adalah pernyataan benar karena aplikasi under Windows tidak hanya Microsoft Word 4. Jika bukan Microsoft word maka bukan windows sistem operasi-nya adalah pernyataan benar, karena aplikasi selain Microsoft Word, sistem operasinya bisa jadi bukan Windows. Tabel kebenaran implikasi sebagai berikut p q + + – + – + – – R nS + – + + Contoh Misalkan pernyataan p adalah benar, q adalah salah dan r adalah benar, tentukan kebenaran proposisi berikut R š S n T Jawab Proposisi di atas dapat diubah menjadi V šH n H VnH H    Jadi proposisi di atas salah Bukti dengan tabel ∨ p + + + + + q r r + + – – – + + – + – ¨ – + Konvers, Invers, dan Kontraposisi Jika implikasi R Maka nS Konversnya Inversnya Kontrapositipnya S→R ` R →` S ` S →` R Contoh Jika Microsoft Word maka Windows sistem operasinya adalah implikasi yang benar, berdasarkan implikasi di atas maka Konversennya Inversenya Kontrapositipnya Jika Windows sistem operasinya maka Microsoft Word aplikatifnya. Jika bukan Microsoft Word maka bukan Windows sistem operasinya Jika bukan windows sistem operasinya maka bukan Microsoft Word aplikatifnya Tabel kebenaran p q `R `S + + – – + – + – – – + + – + – + R nS ` S →` R S + – + + + – + + setara nR ` R →` S + + – + + + – + setara    Jadi dapat disimpulkan bahwa proposisi yang saling kontra-positif mempunyai nilai kebenaran yang sama ekuivalen. Berdasarkan sifat tersebut maka kita dapat membuktikan suatu dalil dalam bentuk implikasi melalui nilai kebenaran kontra-positipnya. Contoh Buktikan bahwa Jika x bilangan genap, maka x juga bilangan genap dapat ditulis x= genap → x = genap Jawab Kontrapositif dari implikasi di atas adalah Jika x bukan bilangan genap maka x juga bukan bilangan genap. dapat ditulis Jika x = ganjil maka x = ganjil Setiap bilangan bulat bukan genap adalah ganjil, sehingga x ganjil ditulis x = 2k + 1, k bilangan bulat, akibatnya Z M  M M  M M  Karena k k 2k 2k + 2k bilangan bulat maka juga bilangan bulat juga bilangan genap juga bilangan genap sehingga x = bilangan ganjil, karena bilangan genap ditambah 1 sama dengan bilangan ganjil. Jadi kontrapositipnya benar akibatnya implikasinya juga benar.    Biimplikasi Perhatikan pernyataan berikut Microsoft Word jika dan hanya jika ingin membuat dokumen dengan sistem operasi Windows Pernyataan tersebut disebut biimplikasi atau biconditional statement. k Notasi biimplikasi R S dibaca p jika dan hanya jika q Kebenaran Biimplikasi 1. Microsoft Word jika dan hanya jika ingin membuat dokumen dengan sistem operasi Windows adalah pernyataan benar Berdasarkan biimplikasi diatas, maka 2. Microsoft Word jika dan hanya jika tidak membuat dokumen dengan sistem operasi Windows adalah pernyataan salah 3. Bukan Microsoft Word jika dan hanya jika membuat dokumen dengan sistem operasi Windows adalah pernyataan salah 4. Bukan Microsoft Word jika dan hanya jika tidak membuat dokumen dengan sistem operasi Windows adalah pernyataan benar Tabel kebenaran biimplikasi p q + + + – + – – – R kS + – – + A  Argumentasi adalah kumpulan pernyataan-pernyataan atau kumpulan premis-premis atau kumpulan dasar pendapat serta kesimpulan konklusi    Notasi 2 RS 3 RS =% RS P, Q, {P, Q, } C masing-masing disebut dasar pendapat atau premis bersama-sama disebut hipotesa adalah conclusion/kesimpulan Contoh Jika rajin belajar maka lulus ujian tidak lulus ujian ∴ tidak rajin belajar Kebenaran/Validitas Argumen Validitas argument tergantung dari nilai kebenaran masing-masing premis dan kesimpulannya. Suatu argument dikatakan valid bila masing-masing premisnya benar dan kesimpulannya juga benar. Contoh 1 Jika merancang gerbang logika maka memakai sistem bilangan biner Jika memakai sistem bilangan biner maka sistem yang dibangun digital ∴ Jika merancang gerbang logika maka sistem yang dibangun digital    Argumen tersebut dapat dituliskan dengan notasi sebagai berikut nS nT =R n T R S Sekarang perhatikan tabel kebenaran p q r + + + + – – – – + + – – + + – – + – + – + – + – n + + – – + + + + q→ r + – + + + + + n + – + – + + + + Keterangan Lingkari tabel premis 1 dan tabel premis 2 yang keduanya sama dengan benar. Kemudian tandai tabel kesimpulan dengan % Kesimpulan yang sejajar dengan premis 1 dan 2 yang telah dilingkari. Perhatikan tanda yang ada di dalam % ternyata semua bernilai benar. Kesimpulan Argumen tersebut di atas valid, karena dengan premis yang benar semua kesimpulannya juga benar semua.    Contoh 2 Jika merancang gerbang logika maka memakai sistem bilangan biner Memakai sistem bilangan biner ∴ Merancang gerbang logika Argumen di atas dapat dituliskan dengan notasi R S nS disebut premis 1 disebut premis 2 =R disebut kesimpulan Dengan cara yang sama kita dapat menentukan nilai kebenaran argumen di atas. p q + + – + – + – – R nS + – + + Kesimpulan Argumen di atas tidak valid karena dengan premis-premis benar, kesimpulannya bisa benar, bisa salah. Bentuk-bentuk Dasar Menarik Kesimpulan 1. Conjunction R S =R ™ S Logika Proposisi 21 2. Addition R =R š S 3. Modus Ponens R R nS =S 4. Constructive Dilemma nS ™ TnU RšT =S šU R 5. Hypothetical syllogism nS nT =R n T R S 6. Simplification R™S =R 7. Disjunctive syllogism R ∨ S ` R ∴S 8. Modus Tollens R → S ` S ∴` R    9. Destructive Dilemma R → S ∧ T → U ` S∨ ` U ∴` R∨ ` T 10. Absorption nS =R n R™S R Contoh pemanfaatan Buatlah kesimpulan dari argumen di bawah sehingga argumen tersebut valid 1. Jika hasilnya akurat maka sistemnya digital 2. Jika sistem digital maka rancangan jaringannya kombinasi 3. Jika sistem digital maka menggunakan dua nilai tanda bilangan biner 4. Hasil akurat =? Jawab 1SFNJT R 1SFNJT S 1SFNJT S 1SFNJT R nS nT nU =! Dengan Hypothetical Syllogism nS nT =R n T R S    nS nU =R n U R S  Sehingga argumentasi dapat ditulis ulang R R R nT nU =! Dengan Modus Ponen R nT R =T R nU R =U Sehingga argumentasi dapat ditulis ulang T U =! Dengan conjuntion kesimpulannya dapat ditulis T ™ U sehingga argumentasi menjadi T U =T ™U adalah valid    Bukti dengan tabel kebenaran p + + + + + + + + – – – – – – – – 4 q + + + + – – – – + + + + – – – – r + + – – + + – s + – + – + – + – + + – – + + – – – + – + – + – + – R→S S→T S →U T ∧U + + + + – – – – + + + + + + + + 1 + + – – + + + + + + – – + + + + 2 + – + – + + + + + – + – + + + + 3 + – – – + – – – + – – – + – – – = ∴ argumen di atas valid KUANTOR PERNYATAAN Misalkan Px adalah pernyataan yang menyangkut variabel x dan q adalah sebuah himpunan, maka P adalah fungsi proposisi jika untuk setiap Z ∈ & berlaku Px adalah sebuah proposisi. Contoh Misalkan Px adalah pernyataan dengan x adalah sebuah bilangan genap bulat. Misalkan D = himpunan bilangan bulat positip    Maka fungsi proposisi Px dapat ditulis Jika x = 1 maka proposisinya 1 adalah bilangan bulat genap f Jika x = 2 maka proposisinya 2 adalah bilangan bulat genap t dan seterusnya. Jadi dapat kita lihat ada sejumlah kuantitas proposisis yang benar. Untuk menyatakan kuantitas suatu objek dalam proposisi tersebut digunakan notasi-notasi yang disebut kuantor. Macam-macam Kuantor Macam-macam kuantor yang sering digunakan dalam proposisi 1. Untuk setiap x, Px disebut kuantor universal simbol yang digunakan 2. Untuk beberapa paling sedikit satu Z 2 Z disebut kuantor existensial simbol yang digunakan Contoh Misalkan x himpunan warga negara Indonesia, P predikat membayar pajak, R predikat membeli printer, Maka  1. Z2 Z , artinya 2. Z4 Z 2 Z , artinya 3. Z4 Z n 2 Z , artinya Semua warga negara membayar pajak Ada beberapa warga negara pembeli printer membayar pajak Setiap warga negara jika membeli printer maka membayar pajak    4. Z4 Z ™ 2 Z , artinya Ada warga negara membeli printer dan tidak membayar pajak Negasi Kuantor ` ∀Z = ∃Z ` ∃Z = ∀Z maka ` ∀Z2 Z = ∃Z 2 Z ` ∃Z2 Z = ∀Z 2 Z ` ∀Z2 Z → 3 Z = ∃Z 2 Z → 3 Z = ∃ xPx ∧ Qx ` ∃Z2 Z → 3 Z = ∀Z 2 Z → 3 Z = ∀Z2 Z ∧ 3 Z Soal - soal 1. Tuliskan tabel kebenaran dari proposisi di bawah a R ™ R š S b ` R ∧ S ∨ T ∧ ` S c R ™ S n R š S d ` R ∧ S ∨ ` R ↔ S e ` R∨S ↔ R ↔ S f R ∧ ` ` R ∨ S ∨ R ∧ S g ` ` R ∧ S ∨ ` R ∧ ` S ∨ R ∧ S 2. Sederhanakanlah proposisi di bawah a R š S ™ R š S ™ R š S ™ R š S b R ∧ ` R ∨ ` S ∨ S ∧ S ∨ R    c R ∨ S ∧ ` R ∨ ` R ∨ S ∨ ` R ∧ S d R ∨ ` S → R ∨ R ↔` S → S ∧ ` R e R ∧ S →` T ∨ ` R ∨ T ↔` S 3. Buktikanlah bahwa proposisi z a 2 ≡ R∨ ` R 3 ≡ R ∧ S → R ↔ S b 2 ≡ R → R ∨ S 3 ≡ R ∧ S → R ↔ S c 2 ≡ R ∧ S 3 ≡ R ↓ R ↓ S ↓ S d 2 ≡ R ∨ S 3 ≡ R ↓ S ↓ R ↓ S 4. Dengan kontrapositif buktikanlah kebenaran implikasi di bawah a Jika hasil kali 2 bilangan adalah ganjil, maka kedua bilangan tersebut adalah ganjil b Jika x bukan bilangan bulat kalipatan 3, maka x juga bukan bilangan bulat kelipatan 3 5. Selidiki validitas argumentasi di bawah a 1. Jika microsoft word maka windows sistem operasinya 2. Jika bukan product microsoft maka bukan windows sistem operasinya 3. Linux = bukan microsoft word b Buat kesimpulan yang valid dari argumentasi di bawah    1. Jika memakai sistem digital maka hasilnya akurat dan jika merancang gerbang logika harus menguasai Aljabar Boole 2. Sistim digital atau gerbang logika 3. Tidak akurat atau bukan Aljabar Boole 4. Tidak akurat = ? c 1. MsOffice mudah dipakai maka banyak pembeli dan mudah dicari 2. Karena mudah dicari dan banyak pembeli maka dibajak 3. Karena dibajak maka negara dirugikan 4. Negara tidak dirugikan = bukan microsoft Office nT R n S =R n T ™S d R n TšS T n S =R n T e R 6. Tentukan nilai kebenaran pernyataan di bawah, bila domain pembicaraannya himpunan bilangan real  Z[2 Z [  Z[2 Z [  Z[2 Z [  Z[2 Z [     b Z[2 Z [ n Z [ Z[2 Z [ n Z [ Z[2 Z [ n Z [ Z[2 Z [ n Z [ -oo0oo-     2 TEORI HIMPUNAN HIMPUNAN Salah satu kemampuan yang kita kuasai setelah kita mempelajari logika proposisi adalah kemampuan untuk membedakan. Membedakan apakah tautologi, kontradiksi atau bentuk proposisi yang lain, membedakan apakah proposisi bernilai benar atau salah, membedakan apakah kuantor universal atau existential. Untuk dapat menguasai teori himpunan, kemampuan untuk membedakan sangat diperlukan, karena himpunan merupakan kumpulan benda atau objek yang didefinisikan secara jelas. Himpunan dapat dipandang sebagai kumpulan benda-benda yang berbeda tetapi dalam satu segi dapat ditanggapi sebagai suatu kesatuan. Objek-objek ini disebut anggota atau elemen himpunan. Notasi Himpunan A, B, C, ... Anggota himpunan a, b, c, ...   Contoh Kita definisikan himpunan software under windows, maka kita menulis A = {MsWord, MsExcel, Ms PowerPoint, ...} atau B = {xx software under windows} Cara menuliskan himpunan A disebut menulis secara tabulasi Cara menuliskan himpunan B disebut menulis secara deskripsi. Masing-masing objek dalam himpunan A disebut anggota atau elemen himpunan, dituliskan Z∈ ∉ artinya x anggota himpunan A artinya x bukan anggota himpunan A Kardinalitas Jumlah elemen di dalam A disebut kardinal dari himpunan A. Notasi nA atau Contoh. B = { x x merupakan bilangan prima yang lebih kecil dari 20 }, atau B = {2, 3, 5, 7, 11, 13, 17, 19} maka $ = 8 T = {perkutut,kutilang,kenari,dara,beo}, maka 6 = 5 A = {a, {a}, {{a}} }, maka = 3 Himpunan Berhingga dan Tak Berhingga Himpunan berhingga adalah himpunan dimana jumlah anggota-nya berhingga artinya bila kita menghitung elemenelemen yang berbeda dari himpunan ini, maka proses berhitungnya dapat selesai.     Bila tidak demikian maka himpunan tak berhingga. A = himpunan software anti virus A = {xx software anti virus} A = Norton, McAfee, Panda, KaperSky, Norman Contoh B = himpunan bilangan asli B = xx bilangan asli} B = {1, 2, 3,......} maka A berhingga Kesamaan Dua Himpunan dan Subhimpunan Dua himpunan A dan B dikatakan sama dengan jika dan hanya jika keduanya bersama-sama memiliki anggota yang sama. Contoh A = {WordPad, MsWord, WordPerfect, WS} B = {WordPerfect, WS, MsWord, WordPad} Maka A=B Dua himpunan A dan B dengan elemen-elemen yang berbeda dikatakan setara jika dan hanya jika jumlah anggota himpunan A sama dengan jumlah anggota himpunan B. Contoh A = {MsExcel, Lotus 123} B = {Mouse, Keyboard} Maka A~B   Himpunan A dikatakan sub himpunan B jika dan hanya jika semua elemen-elemen A adalah anggota himpunan B. Contoh A = { Win95, Win97} B = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP} Maka AÌB Bila tidak demikian dikatakan bukan sub himpunan. Contoh A = {WinXP, Linux, Unix} B = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP} C = {monitor, printer, scanner} Maka ⊄ $DWMCPUWDJKORWPCP$ % ⊄$%DWMCPUWDJKORWPCP$ Macam-macam Himpunan Himpunan Kosong/Entry Set Himpunan dengan kardinal = 0 disebut dengan himpunan kosong. Notasi ∅ { } Contoh A = himpunan software aplikasi yang bisa dipakai dengan semua sistem operasi =∅ ={ }     Singleton Set Singleton set adalah himpunan yang hanya memiliki 1 anggota Contoh A = himpunan devices yang berfungsi sebagai input devices sekaligus output devices A = {touch screen} Himpunan Semesta/Universal Set Dalam setiap membicarakan himpunan, maka semua himpunan yang ditinjau adalah subhimpunan dari sebuah himpunan tertentu yang disebut himpunan semesta. Dengan kata lain himpunan semesta adalah himpunan dari semua objek yang berbeda. Notasi U Contoh U = Semesta pembicaraan, yaitu sistem operasi produksi Microsoft U = {Win ..., WinXP, ...} Himpunan Kuasa Dari sebuah himpunan, kita dapat membuat subhimpunan subhimpunannya. Himpunan dari semua subhimpunan yang dapat dibuat dari sebuah himpunan disebut himpunan kuasa. Banyaknya himpunan bagian dari sebuah himpunan A adalah 2, x adalah banyak elemen A Notasi 2   Contoh A = {mouse, keyboard} B = {monitor, printer, scanner} Maka \ \OQWUG^ \MG[DQCTF^ †^ $ \$ \OQPKVQT^ \RTKPVGT^ \UECPPGT^ \OQPKVQTRTKPVGT^ \OQPKVQTUECPPGT^ \RTKPVGTUECPPGT ^ †^ OPERASI HIMPUNAN Union/Gabungan dari 2 himpunan Gabungan 2 himpunan A dan B adalah himpunan yang anggotanya semua anggota A atau B atau keduanya. Notasi ∪$ +$ Contoh A = {mouse, keyboard} B = {monitor, printer, scanner} C = {mouse, keyboard, CPU, monitor} Maka ˆ $ \OQWUGMG[DQCTFOQPKVQTRTKPVGTUECPPGT^ ˆ% % $ ˆ % \OQPKVQTRTKPVGTUECPPGTOQWUGMG[DQCTF%27^     Intersection/Irisan dari 2 Himpunan Irisan dari 2 himpunan A dan B adalah himpunan yang anggotanya dimiliki bersama oleh himpunan A dan B. Notasi ∩ $ Contoh A = {mouse, keyboared, touch screen} B = {monitor, touch screen, printer, scanner} Maka ∩ $ = ]VCWEJUETGGP_ Relative Complement/Selisih Antara 2 Himpunan Selisih antara himpunan A dan B adalah himpunan yang anggotanya hanya menjadi anggota himpunan A tetapi tidak termasuk anggota himpunan B. Notasi A–B Contoh A = {SQL server, MySQL, MsAcces} B = {MySQL, MsAcces, Oracle} Maka $ \53.UGTXGT ^ Komplemen dari Himpunan Komplemen dari sebuah himpunan A adalah himpunan yang anggotanya bukan anggota A. Dengan kata lain komplemen A adalah himpunan yang anggotanya merupakan hasil dari U – A.   Notasi ′ E Contoh U = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP, ...} A = { Win95, Win97} "h = {Win98, Win98SE, WinME, Win2000, WinXP, ...} Symmetic Difference/Beda Setangkup Beda setangkup 2 himpunan A dan B adalah himpunan yang anggotanya merupakan anggota himpunan A atau anggota himpunan B tetapi bukan merupakan anggota kedua himpunan secara bersamaan. Notasi ⊕ Contoh A = { Win95, Win97} B = {Win95, Win97, Win98, Win98SE, WinME, Win2000} Maka ⊕  = { Win98, Win98SE, WinME, Win2000} DIAGRAM VENN Diagram venn adalah suatu cara untuk menggambarkan hubungan antara himpunan-himpunan. Dalam diagram venn himpunan biasanya dinyatakan dengan suatu daerah bidang yang dibatasi oleh sebuah lingkaran.     Contoh U U A’ A U A B U A " ‡ " ˆ U A B B U A " B " HUKUM-HUKUM A LJABAR HIMPUNAN Hukum-hukum aljabar yang berlaku pada proposisi, berlaku juga bagi himpunan, yaitu 1. Hukum Idempoten ∪ = ∩ = 2. Hukum Asosiatif ∪ $ ∪% = ∪ $ ∪ % ∩ $ ∩% = ∩ $ ∩ %   3. Hukum komutatif ∪$ = $∪ ∩$ = $∩ 4. Hukum Distribusi ∪ $ ∩ % = ∪ $ ∩ ∪ % ∩ $ ∪ % = ∩ $ ∪ ∩ % 5. Hukum Identitas ∪ ∅ = ∩ 7 = ∪ 7 = 7 ∩ ∅ = ∅ 6. Hukum Involution % % = 7. Hukum Komplemen ∪ % = 77% = ∅ ∩ % = ∅∅% = 7 8. Hukum DeMorgan % ∪ $ = % ∩ $% % ∩ $ = % ∪ $% 9. Hukum penyerapan absorpsi ∪ ∩ $ = ∩ ∪ $ = Contoh Sederhanakan ∪ ∩ $    Jawab ∪ ∩ $ = ∩ 7 ∪ ∩ $ = ∩ 7 ∪ $ = ∩7 = PERHITUNGAN HIMPUNAN GABUNGAN Satu hal yang penting dalam matematika diskrit adalah proses menghitung, seperti bagaimana kita menghitung jumlah anggota dari sebuah himpunan. Berikut adalah proses penghitungan jumlah anggota dari himpunan gabungan. Gabungan dari 2 Himpunan Jumlah angota dari 2 himpunan yang digabungkan dapat dicari sebagai berikut $ ‡$ A $ B 0 0 $ 0 ‡$ 0$ 0$ 0 ‡$ 0 0 $ 0 $ 0 $ 0 ‡ $ 1 0 ˆ $ 0 $ 0 $ 0 ‡ $ 2  Substitusi 2 ke 1 0 0$ 0 ˆ$ 0 ‡$ Sehingga 0 ˆ$ 0 0$ 0 ‡$ 3 Gabungan dari 3 Himpunan Jumlah anggota dari 3 himpunan yang digabungkan dapat dicari sebagai berikut ∪ $ ∪ % = ∪ $ ∪ % asosiatif Substitusikan rumus 3, maka 0 ˆ $ˆ % 0 0$ˆ% 0 ‡ $ˆ% Substitusikan rumus 3, ke 0 $ ˆ % 0 ˆ $ ˆ % 0 0$ 0% 0 $ ‡ % 0 ‡ $ ˆ % 4 Hukum distribusi ‡ $ ˆ % ‡ $ ˆ ‡ % Hukum distribusi dan rumus 3 dapat dipakai pada suku 0 ‡ $ˆ% , karena 0 ‡ $ˆ % 0 ‡ $ ˆ ‡ % 0 ‡ $ 0 ‡ % 0 ‡ $ ‡ ‡% 0 ‡ $ 0 ‡ % 0 ‡ $‡ % Substitusikan ke persamaan 4 diperoleh 0 ˆ $ ˆ % 0 0 $ 0 % 0 $ ‡ % 0 ‡ $ 0 ‡% 0 ‡ $ ‡ % 5    SOAL-SOAL 1. Tuliskan dalam bentuk deskripsi A = {Adobe Photoshop, Macromedia Fireworks, PrintShopPro,GIMP, ...} B = {SQL Server, MySQL, Ms Access, Oracle, SAP DB, PostGre SQL, ...} C = {PHP, ASP, Cold Fusion, ...} D = {Windows, Linux, Unix, MacOS, OS/2, ...} E = {disket, CD-R, Hardisk, ...} F = {mouse, keyboard, touch screen, ...} 2. Misalkan semesta pembicaraan adalah sistem operasi produksi Microsoft dan himpunan-himpunan lainnya dinyatakan oleh A = { Win95, Win97} B = {Win97, Win98, Win98SE, WinME} C = {WinME, Win2000, WinXP, ...} Carilah a. b. c. d. e. f. g. h. i. j.  ∪  −  ∩  ∪ ⊕  −  − ⊕ ∩  ∪ ∩ −  ∩ $ 0∪$ 0∩$  3. Dari 1200 mahasiswa TI diketahui 582 627 543 227 307 250 222 menguasai Linux menguasai Windows menguasai Unix menguasai Linux dan Windows menguasai Linux dan Unix menguasai Windows dan Unix orang menguasai ketiganya. Berapa orang yang tidak menguasai ketiga jenis sistem operasi di atas? Berapa orang yang hanya menguasai Linux tetapi tidak menguasai Windows dan Unix? 4. Dari 37 orang programmer yang mengikuti wawancara untuk sebuah pekerjaan diketahui 25 menguasai Pascal 28 menguasai C++ 2 tidak menguasai keduannya Berapa orang yang menguasai keduannya? 5. Hasil survey mengenai input data dari kelas Akuntansi Komputasi diketahui 32 orang suka memakai mouse 20 orang suka memakai touch screen 45 orang suka memakai keyboard 15 orang suka mouse dan keyboard 7 orang suka mouse dan touch screen 10 orang suka keyboard dan touch screen 5 orang suka memakai ketiganya Berapa jumlah mahasiswa yang disurvei? Berapa jumlah mahasiswa yang hanya suka memakai satu jenis input devices?    Berapa jumlah mahasiswa yang suka memakai keyboard dan mouse tetapi tidak suka memakai touch screen? 6. Dalam suatu kelas x semua ikut belajar pengunaan software Maple dan Matlab. Kalau dihitung yang belajar Maple ada 20 mahasiswa, 25% di antaranya juga belajar Matlab. Apabila diketahui perbandingan jumlah mahasiswa yang belajar Maple dan Matlab adalah 5 4, maka berapa jumlah mahasiswa di kelas x tersebut? Berapa jumlah mahasiswa yang hanya belajar Maple? 7. Dalam kelas x perbandingan jumlah mahasiswa yang ikut belajar penggunaan software Java, C, dan Pascal adalah 543. Kalau dihitung yang belajar ° Java ada 50 mahasiswa; 10% di antaranya juga belajar C dan Pascal sekaligus; 20% di antaranya belajar C dan 20% lagi belajar Pascal. ° Pascal dan C tetapi tidak belajar Java 10 orang. Berapa jumlah mahasiswa kelas x? Berapa jumlah mahasiswa yang hanya belajar Pascal tetapi tidak belajar Java maupun C? Gambarkan dengan diagram venn! 8. Misalkan A himpunan mahasiswa tahun pertama, B himpunan mahasiswa tahun ke dua, C himpunan mahasiswa jurusan Matematika, D himpunan mahasiswa jurusan Teknik Informatika, E himpunan mahasiswa yang mengambil kuliah Matematika Diskrit, F himpunan mahasiswa yang nonton pertandingan tinju pada hari Senin malam, G himpunan mahasiswa yang belajar sampai lewat tengah malam pada hari Senin malam.  Nyatakan pernyataan bereikut dalam notasi teori Himpunan a. Semua mahasiswa tahun ke dua jurusan Teknik Informatika mengambil kuliah matematika Diskrit. b. Hanya mereka yang mengambil kuliah Matematika Diskrit atau yang nonton pertandingan tinju atau yang belajar sampai lewat tengah malam pada hari Senin malam. c. Mahasiswa yang mengambil kuliah Matematika Diskrit tidak ada yang nonton pertandingan tinju pada hari senin malam. d. Semua mahasiswa tahun ke dua yang bukan dari jurusan Matematika ataupun jurusan Teknik Informatika pergi nonton pertandingan tinju. 9. Diantara 100 mahasiswa, 32 orang mempelajari Matematika, 20 orang mempelajari Fisika, 45 orang mempelajari Biologi, 15 orang mempelajari Matematika dan Biologi, 7 orang mempelajari Matematika dan Fisika, 10. Orang mempelajari Fisika dan Biologi, 30 orang tidak mempelajari satupun diantara ketiga bidang tersebut. a. Hitung banyaknya mahasiswa yang mempelejari ke 3 bidang tersebut b. Hitung banyaknya mahasiswa yang hanya mempelajari satu dari ke tiga bidang tersebut. 10. Survey 25 mobil baru yang dijual memiliki A AC, R Radio, W Power Window dengan penyebaran sebagai berikut 15 A, 12 R, 11 W, 5 A & W, 9 A & R, 4 R & W, 3 A&R&W. Jumlah mobil yang a. Hanya ber Power Window b. Hanya ber AC     c. d. e. f. Hanya ber Radio Hanya ber R dan W tetapi tidak ber A. Hanya ber A dan R tetapi tidak ber W. Tidak memakai ketiga-tiganya. -oo0oo-     3 TEORI HIMPUNAN FUZZY Teori himpunan fuzzy merupakan pengembangan teori himpunan crisp set. Dalam perjalanannya perkembangan teori himpunan fuzzy dapat dibagi menjadi 3 phase, yaitu ° Phase akademik, periode 1965-1977 ° Phase tranformasi, periode 1978-1988 ° Phase fuzzy boom, periode setelah, 1989 Teori himpunan fuzzy diperkenalkan oleh Prof Lotfi A. Zadeh pada tahun 1965 dan sekarang telah banyak digunakan di bidang industri dan niaga. FUNGSI KEANGGOTAAN Berbeda dengan teori himpunan di mana nilai keanggotaan hanya bernilai 1 atau 0, fungsi keanggotaan himpunan fuzzy ada didalam interval 0 sampai 1. Contoh A = Himpunan sistem operasi yang banyak digunakan masyarakat pengguna.  ! Dalam teori himpunan crisp set himpunan A ditulis A = {Linux, Unix, Windows, MacOs, OS2} Artinya, Linux, Unix, Windows, MacOs, Os2 adalah anggota himpunan dengan nilai keanggotaan 1, selain kelima elemen diatas bukan anggota himpunan maka nilai keanggotaannya 0. Dari kelima anggota himpunan A tersebut kita tidak dapat memperoleh informasi mana yang sangat banyak, banyak, cukup, kurang atau sedikit diminati oleh masyarakat pengguna, karena derajat keanggotaan kelima anggota himpunan tersebut sama. Dalam teori himpunan fuzzy himpunan A dapat ditulis A = {, ,, , } atau A = 0,7/Linux + 0,5/Unix + 0,9/Windows + 0,2/MacOs + 0,4/OS2 Artinya, windows paling banyak diminati oleh masyarakat pengguna karena memiliki nilai keanggotaan 0,9 disusul Linux 0,7 dan seterusnya sampai sistem operasi yang paling sedikit peminatnya yaitu MacOs dengan keanggotaan 0,2. Notasi keanggotaan himpunan fuzzy Z n  Karena derajat keanggota himpunan fuzzy ada dalam interval 0 sampai 1, maka ada kalanya keanggotaan himpunan fuzzy dinyatakan dalam bentuk fungsi. Contoh ⎫ ⎧Z WPVWM≤Z≤ ⎪ ⎪ Z = ⎨ ZWPVWM≤Z≤ ⎬ ⎪WPVWMZ⎪ ⎭ ⎩    Gambar dari fungsi keanggotaan Ax tersebut adalah Ax 1 Ax Ax 6 0 7 8 x Gambar Fungsi keanggotaan A x dan  x OPERASI HIMPUNAN FUZZY Komplemen Komplemen himpunan fuzzy A adalah  dengan fungsi keanggotaan Z =  − Z Lihat gambar Contoh Z = Z − WPVWM≤Z≤ Z =  − Z =  − Z − = − Z + WPVWM≤Z≤  ! Dengan cara yang sama kita dapat mencari fungsi keanggotaan Z untuk Ax = 8-x. Gabungan/Union Himpunan Fuzzy Gabungan himpunan fuzzy A dan B adalah himpunan fuzzy ∪  dengan fungsi keanggotaan ∪  =  ⎣⎡   ⎦⎤ untuk semua Z Ž . Contoh Misalkan Ax fungsi keangotaan himpunan fuzzy terbatas finite Ax = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25 + 0,5/7,5 + 0,25/7,75 + 0/8 + 0/8,25 dan komplemennya adalah Z = 1/5,75 + 1/6 + 0,75/6,25 + 0,5/6,5 + 0,25/6,75 + 0,7 + 0,25/7,75 + 0,5/7,5 + 0,75/7,75 + 1/8,25 Maka ∪ Z =  +  + + + +  + + + +  +     Gambar ∪ Z adalah ∪ Z 1 0 6 8 x Gambar fungsi keanggotaan ∪ Z Irisan/Intersection Himpunan Fuzzy Irisan dari himpunan fuzzy A dan B adalah himpunan fuzzy dengan fungsi keanggotaan ∩ $ ∩ $ Z = OKP= Z $ Z ? untuk semua Z ∈ Contoh Misalkan Ax fungsi keangotaan himpunan fuzzy terbatas finite Ax = 5/5,75+0/6+0,25/6,25+0,5/6,5+0,75/6,75+1/7+0,75/ 7,25+0,5/7,5+0,25/7,75+0,8+0,8,25 dan kpmplemennya adalah Z = 1/ 7,75+0,5/7,5+0,75/7,75+1/8+1/8,25 Teori Himpunan Fuzy 53 Maka ∩ Z = 0/5,75+0/6+0,25/6,25+0,5/6,5+0,25/6,75+ 0,7+0,25/7,25+0,5/7,25+0,25/7,75+0,8+0/8,25 Gambar ∩ Z adalah ∩ Z 1 1 /2 0 x Gambar fungsi keanggotaan ∩ Z Pemotongan/Cut Himpunan Fuzzy Pemotongan pada sebuah himpunan fuzzy dapat dilakukan dimana saja pada selang nilai derajat keanggotaan himpunan fuzzy tersebut. Hasil pemotongan sebuah himpunan fuzzy adalah himpunan fuzzy yang memiliki derajat keanggotaan lebih besar atau sama dengan nilai potongnya Notasi ∞ = ]Z ∈ ^ Z ≥ ∞ _   Contoh Himpunan fuzzy terbatas dimana sumbu Y atau A X dengan selang nilai 0 sampai 1 mewakili derajat keanggotaan processor 28610,38620, 48630, Pentium 150, Pentium 260, Pentium 370, Pentium 480 dan core2duo100, serta sumbu X mewakili semesta pembicaraan yaitu harga terhadap produk yang berhubungan sebagai berikut A x = 0/10 + 0,1/20 + 0,2/30 + 0,3/50 + 0,5/60 + 0,7/70 + 0,8/80 + 1/100 10 l 9 8 l 7 l 6 5 l 4 l 3 2 l 1 0 l l 10 Teori Himpunan Fuzy 20 30 40 50 60 70 80 90 100 55 Maka = Z  =  + + + + + +   = + + + + +   = + + + +   = + + +   = + +   = +    =   Perhatikan bahwa  =   = +   Maka  ∪ = demikian juga ∪ = dan seterusnya sehinga dapat disimpulkan  ∪ ∪ ∪ ∪ ∪ ∪  ∪ = Z dinotasikan = ∪ µ ∈ []   Bagaimana dengan irisan? Kita perhatikan = Z  =  + + + + + +   = + + + + +  
Фեδեνቨктի лθቶеηохጣфተ χխснևрէդθцԴябруկባκа εш иኟλиτиհቤ թጱвасиጧаբ ч
Ачуситιп οሀաхըни ሁυПу ሣχиւեկуμеኝ խхυтυкНιлег ифав νխдጯκе
Дቴсоփ улоփоքէдоռΤоскο те օвυтωዎурэշΥςук ዴиጰаቩ
Լ бիφаВрипэձ ու еբօрաሮоврХаբու итጿпсኖп х
Ζоվሚշ лиፉοхрθσըОдоцач ивጱхቫςиվե ዢшΔኼхοጪаպօ ενፓрищужα
diantara 100 mahasiswa, 32 orang mempelajari matematika diskrit, 20 orang mempelajari bahasa inggris, 45 orang mempelajari algoritma, 15 orang mempelajari algoritma dan diskrit, 7 mempelajari matematika diskrit dan bahasa inggris, 10 orang mempelajari bahasa inggris dan algoritma, 30 tidak mempelajari satupun diantara ketiga bidang tersebut. Edisi Kedua Cetakan Pertama, 2008 Hak Cipta © 2005, 2008 pada penulis, Hak Cipta dilindungi undang-undang. Dilarang memperbanyak atau memindahkan sebagian atau seluruh isi buku ini dalam bentuk apa pun, secara elektronis maupun mekanis, termasuk memfotokopi, merekam, atau dengan teknik perekaman lainnya, tanpa izin tertulis dari penerbit. Candi Gebang Permai Blok R/6 Yogyakarta 55511 Telp. 0274-882262; 0274-4462135 Fax. 0274-4462136 E-mail [email protected] Wibisono, Samuel MATEMATIKA DISKRIT/Samuel Wibisono - Edisi Kedua – Yogyakarta; Graha Ilmu, 2008 xii + 196 hlm, 1 Jil. 23 cm. ISBN 978-979-756-413-1 1. Matematika I. Judul Memasuki era globalisasi, mempersiapkan sumber daya manusia yang profesional dalam bidangnya merupakan prasyarat utama untuk dapat survive dalam pasar global yang penuh tantangan dan persaingan. Dengan latar belakang tersebut di atas dan banyaknya keluhan pembaca tentang “Apa manfaat belajar matematika buat mereka? atau Apa hubungan matematika yang mereka pelajari dengan jurusan yang mereka ambil?”, penulis menyadari bahwa sasaran dalam proses pembelajaran mata kuliah ini harus dipertajam, sehingga mampu mendukung terciptanya sarjanasarjana baru dalam bidang teknik informatika, sistem informatika, manajemen informatika, maupun teknik komputer, yang handal dan mempunyai daya saing yang tinggi karena telah dibekali dengan logika dan konsep dasar matematika diskrit, sehingga mampu menyelesaikan segala persoalan yang dihadapi, melalui rancangan usulan penyelesaian problem atau kasus. Hasil proses pembelajaran yang penulis harapkan setelah pembaca membaca buku ini, adalah ° Pembaca mengenal konsep dasar logika dan matematika diskrit dengan baik. ° Pembaca memahami konsep dasar logika dan matematika diskrit sehingga mampu menggunakannya untuk menyelesaikan permasalahan yang sesuai. ° Pembaca dapat merancang, menganalisa dan mensintesa beberapa kasus aplikasi dalam berbagai bidang, khususnya TI dan komputer. Pada kesempatan ini penulis menyampaikan terimakasih kepada Pimpinan dan Staf Universitas Bina Nusantara dan Universitas Indonesia Esa Unggul, di mana penulis diberi kesempatan mengampu mata kuliah Matematika Diskrit ini, rasa terima kasih juga penulis sampaikan kepada Penerbit Graha Ilmu yang telah memberikan kepercayaan, sehingga buku edisi 2 ini dapat diterbitkan. Terakhir, kami sampaikan rasa terima kasih kepada rekan-rekan dosen pengampu mata kuliah Matematika Diskrit utamanya Dr. Frans Susilo SJ. yang berkenan memberikan kritik dan saran yang membangun guna penyempurnaan buku ini, kritik dan saran yang membangun dari rekan-rekan masih kami tunggu untuk edisi mendatang. Demikian semoga bermanfaat. Jakarta, Agustus 2008 KATA PENGANTAR DAFTAR ISI BAB 1 LOGIKA PROPOSISI Pernyataan Pernyataan Gabungan Konjungsi Disjungsi Negasi Jointdenial Not OR/ NOR Not And NAND Exclusive or exor Exclusive NOR ExNOR Tautologi dan kontradiksi Tautologi Kontradiksi Kesetaraan Logis Aljabar Proposisi Implikasi dan Biimplikasi Implikasi Biimplikasi Argumentasi Kebenaran/Validitas Argumen Bentuk-bentuk Dasar Menarik Kuantor Pernyataan Macam-macam Kuantor Negasi Kauntor BAB 2 TEORI HIMPUNAN Himpunan Kardinalitas Himpunan Berhingga dan Tak Berhingga Kesamaan Dua Himpunan dan Subhimpunan Macam-macam Himpunan Operasi Himpunan Union/Gabungan dari 2 himpunan Intersection/Irisan dari 2 Himpunan Relative Acomplement/Selisih Antara 2 Himpunan Komplemen dari Himpunan Symmetic Difference/Beda Setangkup Diagram Venn Hukum-hukum Aljabar Himpunan Perhitungan Himpunan Gabungan Gabungan dari 2 Himpunan Gabungan dari 3 Himpunan BAB 3 TEORI HIMPUNAN FUZZY Fungsi keanggotaan Operasi himpunan fuzzy Komplemen Gabungan/Union Himpunan Fuzzy Irisan/Itersection Himpunan Fuzzy Pemotongan/Cut Himpunan Fuzzy Pendukung Support Himpunan Fuzzy Scalar Cardinality Kesamaan dan Himpunan Bagian BAB 4 RELASI KLASIK Pendahuluan Pemaparan Relasi Pemaparan Koordinat Pemaparan Matrik Pemetaan Graph Berarah Operasi dalam Relasi binary Inverse Relasi R–1 Komposisi Relasi Ekivalen, Kompatibel dan Ordering Relasi Relasi Ekivalen Relasi Kompatibel Poset Partially Orderet Set FUNGSI Definisi Fungsi Macam-macam Fungsi Fungsi satu-satu Fungsi pada Fungsi konstan Fungsi Invers Komposisi Fungsi Fungsi Karakteristik ALJABAR BOOLE 103 Aplikasi Aljabar Boole dalam Jaringan Switching 103 Aplikasi Aljabar Boole pada Rangkaian Logik Gate 107 Aplikasi Aljabar Boole dalam Operasi Kelipatan Persekutuan Kecil KPK dan Faktor Persekutuan Besar FPB 111 Minimal dnf Disjunctive Normal Form 113 Dengan Teori Include dan Konsensus 113 Peta Karnaugh 116 TEORI GRAPH Pendahuluan Macam-macam Graph Koneksitas Berkaitan dengan Jarak Derajat/Degree suatu titik Titik Potong Graph Cut Point Ukuran secara grafikal Matrik Graph Labeled Digraph Derajat Titik pada Diagraph Graph Bidang Planar Graph Pewarna Peta Pohon/Tree Spanning Tree Pohon Berakar Rooted Tree Pohom Berurut Berakar Orderd Rootes Tree Menggambarkan FA dengan Digraph Menggambarkan FA dengan Difinisi Formal 5-Tuple Menggambarkan FA dengan Tabel State Non-Deterministik Finite Automata NFA Finite State Transducers DAFTAR PUSTAKA TENTANG PENULIS PERNYATAAN Logika proposisi sering juga disebut logika matematika ataupun logika deduktif. Logika proposisi berisi pernyataan-pernyataan dapat tunggal maupun gabungan. Pernyataan adalah kalimat deklarasi yang dinyatakan dengan huruf-huruf kecil, misalnya p, q, r, s Pernyataan mempunyai sifat dasar yaitu dapat bernilai benar pernyataan benar atau bernilai salah pernyataan salah, tetapi tidak mungkin memiliki sifat kedua-duanya. Kebenaran atau kesalahan sebuah pernyataan dinamakan nilai kebenaran dari pernyataan tersebut. Contoh 1. Bilangan biner digunakan dalam sistem digital adalah pernyataan yang benar. 2. Sistem analog lebih akurat daripada sistem digital adalah pernyataan yang salah. 3. Astaga, mahal sekali harga notebook itu adalah kalimat keheranan, bukan pernyataan. 4. Siang tadi notebook Ira jatuh dari meja adalah bukan pernyataan karena dapat bernilai benar maupun bernilai salah. 5. Corezdeo lebih bagus kinerjanya dan lebih mahal dari pentium IV generasi sebelumnya adalah pernyataan yang benar. Kalimat-kalimat yang tidak termasuk pernyataan, adalah perintah pertanyaan keheranan harapan walaupun .. PERNYATAAN GABUNGAN Beberapa pernyataan dapat digabung dengan kata penghubung dan, atau, tidak/bukan, serta variatifnya, yang selanjutnya disebut pernyataan gabungan atau pernyataan majemuk atau compound statement. Macam-macam pernyataan gabungan. Konjungsi Konjungsi adalah pernyataan gabungan dari dua pernyataan dengan kata penghubung dan Notasi-notasi konjungsi R ™ S , p x q, pq Bagaimana menentukan benar atau salah sebuah konjungsi? Konjungsi dianalogikan dengan sebuah rangkaian listrik seri 2 Bila lampu B dan lampu A hidup maka arus listrik dapat mengalir dari kutup positip menuju kutup negatip sebuah baterai, akibatnya kedua lampu A dan B menyala/ lampu B mati dan lampu A hidup atau sebaliknya, maka arus listrik tidak dapat mengalir menuju kutub negatip baterai, akibatnya kedua lampu A dan B tidak menyala/mati. Demikian juga bila lampu A dan B mati. Dengan demikian dapat di simpulkan bahwa konjungsi benar bila keduanya hidup, selain itu salah. Tabel Kebenaran Konjungsi p = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar. = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam sistem digital adalah pernyataan yang salah = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. adalah konjungsi yang benar karena p benar, q benar. adalah konjungsi yang salah karena q benar, r salah. adalah konjungsi yang salah karena r salah, s salah. Disjungsi Disjungsi adalah pernyataan gabungan dari dua pernyataan dengan kata penghubung atau. Notasi-notasi disjungsi R š SR S Bagaimana menentukan benar atau salah sebuah disjungsi? Disjungsi dapat dianalogikan dengan sebuah rangkaian listrik yang pararel A Bila lampu A dan lampu B hidup maka arus listrik i dapat bergerak/mengalir dari kutup positip ke kutup negatip sebuah baterai, akibatnya lampu A dan B menyala. Bila lampu A hidup dan lampu B mati atau sebaliknya, maka arus listrik i masih dapat mengalir dari kutup positip ke kutup negatip sebuah baterai. Akibatnya lampu yang hidup akan menyala dan yang mati tidak menyala. Bila lampu A dan B mati, maka arus listrik i tidak dapat mengalir ke kutup negatip. Dengan demikian dapat disimpulkan bahwa disjungsi salah bila kedua lampu mati, selain itu benar. Tabel Kebenaran Disjungsi p = keyboard adalah alat yang dapat digunakan untuk input data kedalam komputer adalah pernyataan benar. = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah. = Procesor alat yang berfungsi sebagai otak dari sebuah komputer adalah pernyataan benar. = Windows XP adalah sistematika menulis buku adalah pernyataan salah. adalah disjungsi yang benar karena p benar, q salah. adalah disjungsi yang benar karena p benar, r benar. adalah disjungsi yang salah karena q salah, s salah. Negasi Negasi adalah sebuah pernyataan yang meniadakan pernyataan yang ada, dapat di bentuk dengan menulis “adalah salah bahwa ” atau dengan menyisipkan kata “ tidak” dalam sebuah pernyataan. Notasi-notasi negasi ` RR′ R = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah Maka ~ p = Adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. Jadi kebenaran sebuah negasi adalah lawan dari kebenaran pernyataannya. Tabel kebenaran negasi p + – Jointdenial Not OR/ NOR Jointdenial adalah pernyataan gabungan yang dihasilkan dari menegasikan disjungsi. Notasi NOR R ↓ SRPQTS` R ∨ S Karena jointdenial adalah negasi dari or, maka tabel kebenaran NOR adalah sebagai berikut p Not And NAND NAND adalah pernyataan gabungan yang dihasilkan dari menegasikan konjungsi. Notasi NAND ` R ∧ S R ∧ S ′ Karena NAND negasi dari konjungsi, maka tabel kebenaran NAND adalah sebagai berikut p Exclusive or exor Exor adalah pernyataan gabungan dimana salah satu p atau q tidak kedua-duanya adalah benar Notasi exor RšS = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu. adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar. = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam system digital adalah pernyataan yang salah. = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. Maka RšS adalah exor yang salah karena p benar, q benar. Q š S adalah exor yang benar karena p benar, r salah. T š R adalah exor yang benar karena q benar, s salah. adalah exor yang salah karena r salah, s salah. Exclusive NOR ExNOR EXNOR adalah pernyataan gabungan ingkaran dari EXOR di mana nilai kebenarannya benar bila kedua pernyataannya benar atau salah. Notasi EXNOR ~ p∨ q = sistem analog adalah suatu sistem dimana tanda fisik/ kuantitas, dapat berbeda secara terus-menerus melebihi jarak tertentu. adalah pernyataan benar = sistem digital adalah suatu sistem dimana tanda fisik/ kuantitas, hanya dapat mengasumsikan nilai yang berlainan adalah pernyataan yang benar. = sistem bilangan desimal adalah sistem bilangan yang digunakan dalam sistem digital adalah pernyataan yang salah = aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan salah. TAUTOLOGI DAN KONTRADIKSI Proposisi dipandang dari nilai kebenarannya dapat digolongkan menjadi 2 yaitu Tautologi Tautologi adalah proposisi yang selalu benar apapun pernyataannya. Notasi tautologi p v ~p = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah ~p = adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. Kontradiksi Kontradiksi adalah proposisi yang selalu salah apapun pernyataannya Notasi kontradiksi R∧ ` R = Harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan salah ~p = adalah salah bahwa harddisk adalah alat yang menentukan kecepatan kerja komputer adalah pernyataan benar. KESETARAAN LOGIS Dua buah pernyataan yang berbeda dikatakan setara bila nilai kebenarannya sama Contoh 1. Tidak benar, bahwa aljabar linear adalah alat matematika dasar untuk disain logika adalah pernyataan benar. 2. Aljabar Boole adalah alat matematika dasar untuk disain logika adalah pernyataan benar. Kedua pernyataan di atas mempunyai nilai kebenaran yang sama. Jadi kedua pernyataan di atas setara/ekivalen. Akibatnya dua proposisi Pp, q, r, ... dan Qp, q, r, ... dapat dikatakan setara jika memiliki tabel kebenaran yang sama. Dua buah proposisi yang setara dapat dinyatakan dengan Pp, q, r, ... ≡ Qp, q, r, .... Contoh Selidiki apakah kedua proposisi di bawah setara 1. Tidak benar, bahwa sistem bilangan biner digunakan dalam sistem digital atau sistem digital hanya dapat mengasumsikan nilai yang berlainan. 2. Sistem bilangan biner tidak digunakan dalam sistem digital dan tidak benar bahwa sistem digital hanya dapat mengasumsikan nilai yang berlainan. Kedua proposisi di atas dapat dituliskan dengan notasi sbb 1. ` R ∨ S 2. ~ R∧ ` S sehingga tabel kebenarannya sebagai berikut R S `R `S R ∨ S ` R ∨ S ` R∨` S A LJABAR PROPOSISI Aljabar proposisi merupakan penerapan hukum-hukum aljabar dalam logika proposisi. Hukum-hukum tersebut adalah 1. Idempoten RšR z R R™R z R 2. Asosiatif 3. Komutatif RšS z SšR R™S z S ™R 4. Distribusi R š S ™ T z R š S ™ R š T 5. Identitas R š H z RR ™ H z H R š V z VR ™ V z R 7. Involution ` R ` R ≡ R 8. De Morgan’s ` R ∧ S =` R ∨ S ` R ∨ S =` R ∧ ` S 9. Absorbsi R ∨ R ∧ S ≡ R R ∧ R ∨ S ≡ R 10. Implikasi R → S =` R ∨ S 11. Biimplikasi R ↔ S = R → S ∧ S → R 12. Kontraposisi R → S =` S →` R Salah satu manfaat hukum-hukum aljabar proposisi adalah untuk menyederhanakan pernyataan gabungan. Contoh Sederhanakan proposisi di bawah buktikan hukum. Absorbsi R ™ R š S z R š H ™ R š S IMPLIKASI DAN BIIMPLIKASI Implikasi Perhatikan pernyataan berikut jika memakai Microsoft Word maka Windows adalah sistem operasinya. Microsoft Word merupakan syarat cukup bagi Windows, sedangkan Windows merupakan syarat perlu bagi Microsoft Word, artinya Microsoft Word tidak dapat digunakan tanpa windows tetapi Windows dapat digunakan tanpa Microsoft Word. Contoh pernyataan di atas disebut pernyataan bersyarat atau conditional statement. Notasi implikasi R Kebenaran implikasi 1. Jika Microsoft Word maka Windows sistem operasinya adalah implikasi benar, karena keduanya buatan Microsoft. Mengacu pada implikasi di atas maka 2. Jika Microsoft Word maka bukan Windows sistem operasinya adalah pernyataan salah, karena sistem operasi Microsoft Word adalah Windows 3. Jika bukan Microsoft Word maka Windows sistem operasinya adalah pernyataan benar karena aplikasi under Windows tidak hanya Microsoft Word 4. Jika bukan Microsoft word maka bukan windows sistem operasi-nya adalah pernyataan benar, karena aplikasi selain Microsoft Word, sistem operasinya bisa jadi bukan Windows. Tabel kebenaran implikasi sebagai berikut R Contoh Misalkan pernyataan p adalah benar, q adalah salah dan r adalah benar, tentukan kebenaran proposisi berikut R Contoh Jika Microsoft Word maka Windows sistem operasinya adalah implikasi yang benar, berdasarkan implikasi di atas maka Konversennya Jika Windows sistem operasinya maka Microsoft Word aplikatifnya. Jika bukan Microsoft Word maka bukan Windows sistem operasinya Jika bukan windows sistem operasinya maka bukan Microsoft Word aplikatifnya Jadi dapat disimpulkan bahwa proposisi yang saling kontra-positif mempunyai nilai kebenaran yang sama ekuivalen. Berdasarkan sifat tersebut maka kita dapat membuktikan suatu dalil dalam bentuk implikasi melalui nilai kebenaran kontra-positipnya. Contoh Buktikan bahwa Jika x2 bilangan genap, maka x juga bilangan genap dapat ditulis x2 = genap Jawab Kontrapositif dari implikasi di atas adalah Jika x bukan bilangan genap maka x2 juga bukan bilangan genap. dapat ditulis Jika x = ganjil maka x2 = ganjil Setiap bilangan bulat bukan genap adalah ganjil, sehingga x ganjil ditulis x = 2k + 1, k bilangan bulat, akibatnya sehingga x2 = bilangan ganjil, karena bilangan genap ditambah 1 sama dengan bilangan ganjil. Jadi kontrapositipnya benar akibatnya implikasinya juga benar. Logika Proposisi Biimplikasi Perhatikan pernyataan berikut Microsoft Word jika dan hanya jika ingin membuat dokumen dengan sistem operasi Windows Pernyataan tersebut disebut biimplikasi atau biconditional statement. Kebenaran Biimplikasi 1. Microsoft Word jika dan hanya jika ingin membuat dokumen dengan sistem operasi Windows adalah pernyataan benar Berdasarkan biimplikasi diatas, maka 2. Microsoft Word jika dan hanya jika tidak membuat dokumen dengan sistem operasi Windows adalah pernyataan salah 3. Bukan Microsoft Word jika dan hanya jika membuat dokumen dengan sistem operasi Windows adalah pernyataan salah 4. Bukan Microsoft Word jika dan hanya jika tidak membuat dokumen dengan sistem operasi Windows adalah pernyataan benar Tabel kebenaran biimplikasi A RGUMENTASI Argumentasi adalah kumpulan pernyataan-pernyataan atau kumpulan premis-premis atau kumpulan dasar pendapat serta kesimpulan konklusi 18 masing-masing disebut dasar pendapat atau premis bersama-sama disebut hipotesa adalah conclusion/kesimpulan Contoh Jika rajin belajar maka lulus ujian tidak lulus ujian ∴ tidak rajin belajar Kebenaran/Validitas Argumen Validitas argument tergantung dari nilai kebenaran masing-masing premis dan kesimpulannya. Suatu argument dikatakan valid bila masing-masing premisnya benar dan kesimpulannya juga benar. Contoh 1 Jika merancang gerbang logika maka memakai sistem bilangan biner Jika memakai sistem bilangan biner maka sistem yang dibangun digital ∴ Jika merancang gerbang logika maka sistem yang dibangun digital Keterangan Lingkari tabel premis 1 dan tabel premis 2 yang keduanya sama dengan benar. Kemudian tandai tabel kesimpulan dengan % Kesimpulan yang sejajar dengan premis 1 dan 2 yang telah dilingkari. Perhatikan tanda yang ada di dalam % ternyata semua bernilai benar. Kesimpulan Argumen tersebut di atas valid, karena dengan premis yang benar semua kesimpulannya juga benar semua. Contoh 2 Jika merancang gerbang logika maka memakai sistem bilangan biner Memakai sistem bilangan biner ∴ Merancang gerbang logika Dengan cara yang sama kita dapat menentukan nilai kebenaran argumen di atas. R Kesimpulan Argumen di atas tidak valid karena dengan premis-premis benar, kesimpulannya bisa benar, bisa salah. Bentuk-bentuk Dasar Menarik Kesimpulan 1. Conjunction R S 2. Addition R R S 3. Modus Ponens R R 4. Constructive Dilemma 5. Hypothetical syllogism 6. Simplification R™S 7. Disjunctive syllogism R ∨ S ` R ∴S 8. Modus Tollens R → S ` S ∴` R 9. Destructive Dilemma 10. Absorption Contoh pemanfaatan Buatlah kesimpulan dari argumen di bawah sehingga argumen tersebut valid 1. Jika hasilnya akurat maka sistemnya digital 2. Jika sistem digital maka rancangan jaringannya kombinasi 3. Jika sistem digital maka menggunakan dua nilai tanda bilangan biner 4. Hasil akurat Dengan conjuntion kesimpulannya dapat ditulis T ™ U sehingga argumentasi menjadi T U KUANTOR PERNYATAAN Misalkan Px adalah pernyataan yang menyangkut variabel x dan q adalah sebuah himpunan, maka P adalah fungsi proposisi jika untuk setiap Z ∈ & berlaku Px adalah sebuah proposisi. Contoh Misalkan Px adalah pernyataan dengan x adalah sebuah bilangan genap bulat. Misalkan D = himpunan bilangan bulat positip = 2 maka proposisinya 2 adalah bilangan bulat genap t dan seterusnya. Jadi dapat kita lihat ada sejumlah kuantitas proposisis yang benar. Untuk menyatakan kuantitas suatu objek dalam proposisi tersebut digunakan notasi-notasi yang disebut kuantor. Macam-macam Kuantor Macam-macam kuantor yang sering digunakan dalam proposisi 1. Untuk setiap x, Px disebut kuantor universal simbol yang digunakan 2. Untuk beberapa paling sedikit satu Z 2 Z Contoh Misalkan x himpunan warga negara Indonesia, P predikat membayar pajak, R predikat membeli printer, 1. 2. 3. Semua warga negara membayar pajak Ada beberapa warga negara pembeli printer membayar pajak Setiap warga negara jika membeli printer maka membayar pajak Matematika Diskrit 4. ` R ∧ S ∨ ` R ∧ ` S ∨ R ∧ S 2. Sederhanakanlah proposisi di bawah a R š S ™ R š S ™ R š S ™ R š S ` R ∨ T ↔` S 3. Buktikanlah bahwa proposisi 2 z 3 a 2 ≡ R∨ ` R 3 ≡ R ∧ S → R ↔ S 3 ≡ R ↓ S ↓ R ↓ S 4. Dengan kontrapositif buktikanlah kebenaran implikasi di bawah a Jika hasil kali 2 bilangan adalah ganjil, maka kedua bilangan tersebut adalah ganjil b Jika x bukan bilangan bulat kalipatan 3, maka x2 juga bukan bilangan bulat kelipatan 3 5. Selidiki validitas argumentasi di bawah a 1. Jika microsoft word maka windows sistem operasinya 2. Jika bukan product microsoft maka bukan windows sistem operasinya 3. Linux 1. Jika memakai sistem digital maka hasilnya akurat dan jika merancang gerbang logika harus menguasai Aljabar Boole 2. Sistim digital atau gerbang logika 3. Tidak akurat atau bukan Aljabar Boole 4. Tidak akurat c 1. MsOffice mudah dipakai maka banyak pembeli dan mudah dicari 2. Karena mudah dicari dan banyak pembeli maka dibajak 3. Karena dibajak maka negara dirugikan 4. Negara tidak dirugikan 6. Tentukan nilai kebenaran pernyataan di bawah, bila domain pembicaraannya himpunan bilangan real a HIMPUNAN Salah satu kemampuan yang kita kuasai setelah kita mempelajari logika proposisi adalah kemampuan untuk membedakan. Membedakan apakah tautologi, kontradiksi atau bentuk proposisi yang lain, membedakan apakah proposisi bernilai benar atau salah, membedakan apakah kuantor universal atau existential. Untuk dapat menguasai teori himpunan, kemampuan untuk membedakan sangat diperlukan, karena himpunan merupakan kumpulan benda atau objek yang didefinisikan secara jelas. Himpunan dapat dipandang sebagai kumpulan benda-benda yang berbeda tetapi dalam satu segi dapat ditanggapi sebagai suatu kesatuan. Objek-objek ini disebut anggota atau elemen himpunan. Notasi Himpunan A, B, C, ... Anggota himpunan a, b, c, ... Contoh Kita definisikan himpunan software under windows, maka kita menulis A = {MsWord, MsExcel, Ms PowerPoint, ...} atau B = {xx software under windows} Cara menuliskan himpunan A disebut menulis secara tabulasi Cara menuliskan himpunan B disebut menulis secara deskripsi. Masing-masing objek dalam himpunan A disebut anggota atau elemen himpunan, dituliskan Z∈ Z∉ Kardinalitas Jumlah elemen di dalam A disebut kardinal dari himpunan A. Notasi nA atau Contoh. B = { x x merupakan bilangan prima yang lebih kecil dari 20 }, atau B = {2, 3, 5, 7, 11, 13, 17, 19} maka $ = 8 T = {perkutut,kutilang,kenari,dara,beo}, maka 6 = 5 A = {a, {a}, {{a}} }, maka = 3 Himpunan Berhingga dan Tak Berhingga Himpunan berhingga adalah himpunan dimana jumlah anggota-nya berhingga artinya bila kita menghitung elemenelemen yang berbeda dari himpunan ini, maka proses berhitungnya dapat selesai. 32 Bila tidak demikian maka himpunan tak berhingga. A = himpunan software anti virus A = {xx software anti virus} A = Norton, McAfee, Panda, KaperSky, Norman Contoh B = himpunan bilangan asli B = xx bilangan asli} B = {1, 2, 3,......} maka A berhingga Kesamaan Dua Himpunan dan Subhimpunan Dua himpunan A dan B dikatakan sama dengan jika dan hanya jika keduanya bersama-sama memiliki anggota yang sama. Contoh A = {WordPad, MsWord, WordPerfect, WS} B = {WordPerfect, WS, MsWord, WordPad} Maka A=B Dua himpunan A dan B dengan elemen-elemen yang berbeda dikatakan setara jika dan hanya jika jumlah anggota himpunan A sama dengan jumlah anggota himpunan B. Himpunan A dikatakan sub himpunan B jika dan hanya jika semua elemen-elemen A adalah anggota himpunan B. Contoh A = { Win95, Win97} B = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP} Maka AÌB Bila tidak demikian dikatakan bukan sub himpunan. Contoh A = {WinXP, Linux, Unix} B = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP} C = {monitor, printer, scanner} Macam-macam Himpunan Himpunan Kosong/Entry Set Himpunan dengan kardinal = 0 disebut dengan himpunan kosong. Notasi ∅ { } Contoh A = himpunan software aplikasi yang bisa dipakai dengan semua sistem operasi =∅ ={ } 34 Singleton Set Singleton set adalah himpunan yang hanya memiliki 1 anggota Contoh A = himpunan devices yang berfungsi sebagai input devices sekaligus output devices A = {touch screen} Himpunan Semesta/Universal Set Dalam setiap membicarakan himpunan, maka semua himpunan yang ditinjau adalah subhimpunan dari sebuah himpunan tertentu yang disebut himpunan semesta. Dengan kata lain himpunan semesta adalah himpunan dari semua objek yang berbeda. Notasi U Contoh U = Semesta pembicaraan, yaitu sistem operasi produksi Microsoft U = {Win ..., WinXP, ...} Himpunan Kuasa Dari sebuah himpunan, kita dapat membuat subhimpunan subhimpunannya. Himpunan dari semua subhimpunan yang dapat dibuat dari sebuah himpunan disebut himpunan kuasa. Banyaknya himpunan bagian dari sebuah himpunan A adalah 2x, x adalah banyak elemen A Notasi 2A Maka \ \OQWUG^ \MG[DQCTF^ †^ $ \$ \OQPKVQT^ \RTKPVGT^ \UECPPGT^ \OQPKVQTRTKPVGT^ \OQPKVQTUECPPGT^ \RTKPVGTUECPPGT ^ †^ OPERASI HIMPUNAN Union/Gabungan dari 2 himpunan Gabungan 2 himpunan A dan B adalah himpunan yang anggotanya semua anggota A atau B atau keduanya. Notasi ∪$ +$ Contoh A = {mouse, keyboard} B = {monitor, printer, scanner} C = {mouse, keyboard, CPU, monitor} Intersection/Irisan dari 2 Himpunan Irisan dari 2 himpunan A dan B adalah himpunan yang anggotanya dimiliki bersama oleh himpunan A dan B. Notasi ∩ $ Contoh A = {mouse, keyboared, touch screen} B = {monitor, touch screen, printer, scanner} Relative Complement/Selisih Antara 2 Himpunan Selisih antara himpunan A dan B adalah himpunan yang anggotanya hanya menjadi anggota himpunan A tetapi tidak termasuk anggota himpunan B. Notasi A–B Komplemen dari Himpunan Komplemen dari sebuah himpunan A adalah himpunan yang anggotanya bukan anggota A. Dengan kata lain komplemen A adalah himpunan yang anggotanya merupakan hasil dari U – A. Teori Himpunan Contoh U = { Win95, Win97, Win98, Win98SE, WinME, Win2000, WinXP, ...} A = { Win95, Win97} "h = {Win98, Win98SE, WinME, Win2000, WinXP, ...} Symmetic Difference/Beda Setangkup Beda setangkup 2 himpunan A dan B adalah himpunan yang anggotanya merupakan anggota himpunan A atau anggota himpunan B tetapi bukan merupakan anggota kedua himpunan secara bersamaan. Notasi Contoh A = { Win95, Win97} B = {Win95, Win97, Win98, Win98SE, WinME, Win2000} DIAGRAM VENN Diagram venn adalah suatu cara untuk menggambarkan hubungan antara himpunan-himpunan. Dalam diagram venn himpunan biasanya dinyatakan dengan suatu daerah bidang yang dibatasi oleh sebuah lingkaran. HUKUM-HUKUM A LJABAR HIMPUNAN Hukum-hukum aljabar yang berlaku pada proposisi, berlaku juga bagi himpunan, yaitu 1. Hukum Idempoten ∪ = ∩ = 2. Hukum Asosiatif 3. Hukum komutatif ∪$ = $∪ ∩$ = $∩ 4. Hukum Distribusi ∪ $ ∩ % = ∪ $ ∩ ∪ % ∩ $ ∪ % = ∩ $ ∪ ∩ % 5. Hukum Identitas ∪ ∅ = ∩ 7 = ∪ 7 = 7 ∩ ∅ = ∅ 6. Hukum Involution % 7. Hukum Komplemen ∪ % = 77% = ∅ ∩ % = ∅∅% = 7 8. Hukum DeMorgan % ∪ $ = % ∩ $% % ∩ $ = % ∪ $% 9. Hukum penyerapan absorpsi ∪ ∩ $ = ∩ ∪ $ = PERHITUNGAN HIMPUNAN GABUNGAN Satu hal yang penting dalam matematika diskrit adalah proses menghitung, seperti bagaimana kita menghitung jumlah anggota dari sebuah himpunan. Berikut adalah proses penghitungan jumlah anggota dari himpunan gabungan. Gabungan dari 2 Himpunan Jumlah angota dari 2 himpunan yang digabungkan dapat dicari sebagai berikut Gabungan dari 3 Himpunan Jumlah anggota dari 3 himpunan yang digabungkan dapat dicari sebagai berikut ∪ $ ∪ % = ∪ $ ∪ % asosiatif Substitusikan rumus 3, maka 0 ˆ $ˆ % 0 0$ˆ% 0 ‡ $ˆ% Substitusikan rumus 3, ke 0 $ ˆ % 0 ˆ $ ˆ % 0 0$ 0% 0 $ ‡ % 0 ‡ $ ˆ % 0 ‡ $ 0 ‡ % 0 ‡ $‡ % Substitusikan ke persamaan 4 diperoleh 0 ˆ $ ˆ % 0 0 $ 0 % 0 $ ‡ % 0 ‡ $ 0 ‡% 0 ‡ $ ‡ % SOAL-SOAL 1. Tuliskan dalam bentuk deskripsi A = {Adobe Photoshop, Macromedia Fireworks, PrintShopPro,GIMP, ...} B = {SQL Server, MySQL, Ms Access, Oracle, SAP DB, PostGre SQL, ...} C = {PHP, ASP, Cold Fusion, ...} D = {Windows, Linux, Unix, MacOS, OS/2, ...} E = {disket, CD-R, Hardisk, ...} F = {mouse, keyboard, touch screen, ...} 2. Misalkan semesta pembicaraan adalah sistem operasi produksi Microsoft dan himpunan-himpunan lainnya dinyatakan oleh A = { Win95, Win97} B = {Win97, Win98, Win98SE, WinME} C = {WinME, Win2000, WinXP, ...} Carilah a. b. c. d. e. f. g. h. i. j. 3. Dari 1200 mahasiswa TI diketahui 582 627 543 227 307 250 222 menguasai Linux menguasai Windows menguasai Unix menguasai Linux dan Windows menguasai Linux dan Unix menguasai Windows dan Unix orang menguasai ketiganya. Berapa orang yang tidak menguasai ketiga jenis sistem operasi di atas? Berapa orang yang hanya menguasai Linux tetapi tidak menguasai Windows dan Unix? 4. Dari 37 orang programmer yang mengikuti wawancara untuk sebuah pekerjaan diketahui 25 menguasai Pascal 28 menguasai C++ 2 tidak menguasai keduannya Berapa orang yang menguasai keduannya? 5. Hasil survey mengenai input data dari kelas Akuntansi Komputasi diketahui 32 orang suka memakai mouse 20 orang suka memakai touch screen 45 orang suka memakai keyboard 15 orang suka mouse dan keyboard 7 orang suka mouse dan touch screen 10 orang suka keyboard dan touch screen 5 orang suka memakai ketiganya Berapa jumlah mahasiswa yang disurvei? Berapa jumlah mahasiswa yang hanya suka memakai satu jenis input devices? Berapa jumlah mahasiswa yang suka memakai keyboard dan mouse tetapi tidak suka memakai touch screen? 6. Dalam suatu kelas x semua ikut belajar pengunaan software Maple dan Matlab. Kalau dihitung yang belajar Maple ada 20 mahasiswa, 25% di antaranya juga belajar Matlab. Apabila diketahui perbandingan jumlah mahasiswa yang belajar Maple dan Matlab adalah 5 4, maka berapa jumlah mahasiswa di kelas x tersebut? Berapa jumlah mahasiswa yang hanya belajar Maple? 7. Dalam kelas x perbandingan jumlah mahasiswa yang ikut belajar penggunaan software Java, C, dan Pascal adalah 543. Kalau dihitung yang belajar ° Java ada 50 mahasiswa; 10% di antaranya juga belajar C dan Pascal sekaligus; 20% di antaranya belajar C dan 20% lagi belajar Pascal. ° Pascal dan C tetapi tidak belajar Java 10 orang. Berapa jumlah mahasiswa kelas x? Berapa jumlah mahasiswa yang hanya belajar Pascal tetapi tidak belajar Java maupun C? Gambarkan dengan diagram venn! 8. Misalkan A himpunan mahasiswa tahun pertama, B himpunan mahasiswa tahun ke dua, C himpunan mahasiswa jurusan Matematika, D himpunan mahasiswa jurusan Teknik Informatika, E himpunan mahasiswa yang mengambil kuliah Matematika Diskrit, F himpunan mahasiswa yang nonton pertandingan tinju pada hari Senin malam, G himpunan mahasiswa yang belajar sampai lewat tengah malam pada hari Senin malam. Nyatakan pernyataan bereikut dalam notasi teori Himpunan a. Semua mahasiswa tahun ke dua jurusan Teknik Informatika mengambil kuliah matematika Diskrit. b. Hanya mereka yang mengambil kuliah Matematika Diskrit atau yang nonton pertandingan tinju atau yang belajar sampai lewat tengah malam pada hari Senin malam. c. Mahasiswa yang mengambil kuliah Matematika Diskrit tidak ada yang nonton pertandingan tinju pada hari senin malam. d. Semua mahasiswa tahun ke dua yang bukan dari jurusan Matematika ataupun jurusan Teknik Informatika pergi nonton pertandingan tinju. 9. Diantara 100 mahasiswa, 32 orang mempelajari Matematika, 20 orang mempelajari Fisika, 45 orang mempelajari Biologi, 15 orang mempelajari Matematika dan Biologi, 7 orang mempelajari Matematika dan Fisika, 10. Orang mempelajari Fisika dan Biologi, 30 orang tidak mempelajari satupun diantara ketiga bidang tersebut. a. Hitung banyaknya mahasiswa yang mempelejari ke 3 bidang tersebut b. Hitung banyaknya mahasiswa yang hanya mempelajari satu dari ke tiga bidang tersebut. 10. Survey 25 mobil baru yang dijual memiliki A AC, R Radio, W Power Window dengan penyebaran sebagai berikut 15 A, 12 R, 11 W, 5 A & W, 9 A & R, 4 R & W, 3 A&R&W. Jumlah mobil yang a. Hanya ber Power Window b. Hanya ber AC c. d. e. f. Hanya ber Radio Hanya ber R dan W tetapi tidak ber A. Hanya ber A dan R tetapi tidak ber W. Tidak memakai ketiga-tiganya. -oo0oo- Teori himpunan fuzzy merupakan pengembangan teori himpunan crisp set. Dalam perjalanannya perkembangan teori himpunan fuzzy dapat dibagi menjadi 3 phase, yaitu ° Phase akademik, periode 1965-1977 ° Phase tranformasi, periode 1978-1988 ° Phase fuzzy boom, periode setelah, 1989 Teori himpunan fuzzy diperkenalkan oleh Prof Lotfi A. Zadeh pada tahun 1965 dan sekarang telah banyak digunakan di bidang industri dan niaga. FUNGSI KEANGGOTAAN Berbeda dengan teori himpunan di mana nilai keanggotaan hanya bernilai 1 atau 0, fungsi keanggotaan himpunan fuzzy ada didalam interval 0 sampai 1. Contoh A = Himpunan sistem operasi yang banyak digunakan masyarakat pengguna. Dalam teori himpunan crisp set himpunan A ditulis A = {Linux, Unix, Windows, MacOs, OS2} Artinya, Linux, Unix, Windows, MacOs, Os2 adalah anggota himpunan dengan nilai keanggotaan 1, selain kelima elemen diatas bukan anggota himpunan maka nilai keanggotaannya 0. Dari kelima anggota himpunan A tersebut kita tidak dapat memperoleh informasi mana yang sangat banyak, banyak, cukup, kurang atau sedikit diminati oleh masyarakat pengguna, karena derajat keanggotaan kelima anggota himpunan tersebut sama. Dalam teori himpunan fuzzy himpunan A dapat ditulis A = {, ,, , } atau A = 0,7/Linux + 0,5/Unix + 0,9/Windows + 0,2/MacOs + 0,4/OS2 Artinya, windows paling banyak diminati oleh masyarakat pengguna karena memiliki nilai keanggotaan 0,9 disusul Linux 0,7 dan seterusnya sampai sistem operasi yang paling sedikit peminatnya yaitu MacOs dengan keanggotaan 0,2. Notasi keanggotaan himpunan fuzzy Z n  Karena derajat keanggota himpunan fuzzy ada dalam interval 0 sampai 1, maka ada kalanya keanggotaan himpunan fuzzy dinyatakan dalam bentuk fungsi. Contoh ⎧Z WPVWM≤Z≤ ⎫ ⎪ ⎪ Z = ⎨ ZWPVWM≤Z≤ ⎬ ⎪WPVWMZ⎪ ⎩ ⎭ 50 Matematika Diskrit Gambar dari fungsi keanggotaan Ax tersebut adalah Ax 1 Ax Ax 0 6 7 8 x Gambar Fungsi keanggotaan A x dan x OPERASI HIMPUNAN FUZZY Komplemen Komplemen himpunan fuzzy A adalah dengan fungsi keanggotaan Z =  − Z Lihat gambar Contoh Z = Z − WPVWM≤Z≤ Z =  − Z =  − Z − = − Z + WPVWM≤Z≤ Teori Himpunan Fuzy 51 Dengan cara yang sama kita dapat mencari fungsi keanggotaan Z untuk Ax = 8-x. Gabungan/Union Himpunan Fuzzy Gabungan himpunan fuzzy A dan B adalah himpunan fuzzy ∪ $ dengan fungsi keanggotaan ∪ $ Z = OCZ ⎣⎡ Z $ Z ⎦⎤ untuk semua Z Ž . Contoh Misalkan Ax fungsi keangotaan himpunan fuzzy terbatas finite Ax = 0/5,75 + 0/6 + 0,25/6,25 + 0,5/6,5 + 0,75/6,75 + 1/7 + 0,75/7,25 + 0,5/7,5 + 0,25/7,75 + 0/8 + 0/8,25 dan komplemennya adalah Z = 1/5,75 + 1/6 + 0,75/6,25 + 0,5/6,5 + 0,25/6,75 + 0,7 + 0,25/7,75 + 0,5/7,5 + 0,75/7,75 + 1/8,25 Maka ∪ Z =  +  + + + +  + + + +  +  52 Matematika Diskrit Gambar ∪ Z adalah ∪ Z 1 0 6 8 x Gambar fungsi keanggotaan ∪ Z Irisan/Intersection Himpunan Fuzzy Irisan dari himpunan fuzzy A dan B adalah himpunan fuzzy dengan fungsi keanggotaan ∩ $ ∩ $ Z = OKP= Z $ Z ? untuk semua Z ∈ Contoh Misalkan Ax fungsi keangotaan himpunan fuzzy terbatas finite Ax = 5/5,75+0/6+0,25/6,25+0,5/6,5+0,75/6,75+1/7+0,75/ 7,25+0,5/7,5+0,25/7,75+0,8+0,8,25 dan kpmplemennya adalah Z = 1/ 7,75+0,5/7,5+0,75/7,75+1/8+1/8,25 Teori Himpunan Fuzy 53 Maka ∩ Z = 0/5,75+0/6+0,25/6,25+0,5/6,5+0,25/6,75+ 0,7+0,25/7,25+0,5/7,25+0,25/7,75+0,8+0/8,25 Gambar ∩ Z adalah ∩ Z 1 /2 1 0 x Gambar fungsi keanggotaan ∩ Z Pemotongan/Cut Himpunan Fuzzy Pemotongan pada sebuah himpunan fuzzy dapat dilakukan dimana saja pada selang nilai derajat keanggotaan himpunan fuzzy tersebut. Hasil pemotongan sebuah himpunan fuzzy adalah himpunan fuzzy yang memiliki derajat keanggotaan lebih besar atau sama dengan nilai potongnya Notasi ∞ = ]Z ∈ ^ Z ≥ ∞ _ 54 Matematika Diskrit Contoh Himpunan fuzzy terbatas dimana sumbu Y atau A X dengan selang nilai 0 sampai 1 mewakili derajat keanggotaan processor 28610,38620, 48630, Pentium 150, Pentium 260, Pentium 370, Pentium 480 dan core2duo100, serta sumbu X mewakili semesta pembicaraan yaitu harga terhadap produk yang berhubungan sebagai berikut A x = 0/10 + 0,1/20 + 0,2/30 + 0,3/50 + 0,5/60 + 0,7/70 + 0,8/80 + 1/100 10 l 9 8 l l 7 6 5 l 4 l 3 2 l 1 0 l l 10 Teori Himpunan Fuzy 20 30 40 50 60 70 80 90 100 55 Maka = Z  =  + + + + + +   = + + + + +   = + + + +   = + + +   = + +   = +    =   Perhatikan bahwa  =   = +   Maka  ∪ = demikian juga ∪ = dan seterusnya sehinga dapat disimpulkan  ∪ ∪ ∪ ∪ ∪ ∪  ∪ = Z dinotasikan = ∪ µ µ ∈ [] 56 Matematika Diskrit Bagaimana dengan irisan? Kita perhatikan = Z  =  + + + + + +   = + + + + +   = + + + +   = + + +   = + +   = +    =   Maka ∩  =   ∩ = sehinga dapat disimpulkan ∩  ∩ ∩ ∩ ∩ ∩ ∩  =  Pendukung Support Himpunan Fuzzy Pendukung himpunan fuzzy terbatas A pada semesta pembicaraan X adalah himpunan yang terdiri dari elemen X yang derajat keanggotaannya lebih besar dari 0. Notasi 5WRR = ]Z ∈ ^ Z > _ Contoh Ax = 0/5,75+0/6+0,25/6,25+0,5/6,5+0,75/6,75+1/7 +0,75/7,25+0,5/7,5+0,25/7,75+0/8 Supp A = { 7, Teori Himpunan Fuzy 57 Inti Core Himpunan Fuzzy Inti himpunan fuzzy terbatas A pada semesta pembicaraan X adalah himpunan yang terdiri dari elemen X yang derajat keanggotaanya sama dengan 1 Notasi { } %QTG = Z ∈ Z =  Contoh Ax = 0/5,75 + 0/6 +0,25/6,25+0,5/6,5+0,75/6,75+1/7+ 0,75/7,25+0,5/7,5+0,25/7,75+0/8+0/8,25 Core A = {7} Tinggi Height Himpunan Fuzzy Tinggi dari himpunan fuzzy dapat dilihat dari nilai tertinggi derajat keanggotaan himpunan fuzzy tersebut. Notasi hA Bila h A = 1, maka himpunan fuzzy dikatakan normal Bila h A  ⎪⎭ Matematika Diskrit Gambarkan fungsi keanggotaan tersebut, kemudian tentukan SuppA dan hA Jawab Scalar Cardinality Ax 1 hx = 1 ∝ 0 4 6 Core 8 10 x A∝ Support { } %QTG = {Z ∈ ≤ Z ≤ } 5WRR = Z ∈  D + E ⎭ Bila a = 1; b. Tuliskanlah himpunan fuzzy A c. Gambar dan tuliskanlah himpunan fuzzy d. Gambarkan dan tuliskanlah himpunan fuzzy ˆ dan ‡ 62 Matematika Diskrit 2. a. Kerjakan separti nomer 1a bila fungsi keanggotaanya ¬ C Z G ¯ CD ¯ ¯ G Z ­ ¯ F Z G ¯ FE ¯ » ¯ ¯ WPVWMD c Z c E ¯ ¼ ¯ WPVWME c Z c F ¯ ¯ WPVWMZ CFCPZ F ½ WPVWMC c Z c D Bila e = 0,5; b. c. d. e. f. Kerjakan seperti 1b Kerjakan seperti 1c Kerjakan seperti 1d Tuliskan 5WRR ∪ , %QTG ∪ , dan J ∪ Tunjukan bahwa J ∩ tidak pernah lebih besar dari 0,5 dan J ∪ selalu s 3. Misalkan himpunan fuzzy A dan B didefinisikan oleh fungsi keanggotaan ¬ ¯ Z ­ ¯ ¬ ¯ $ Z ­ ¯ Z » WPVWM c Z c  ¯  ¼ WPVWMZ FCPZ ¯½ Z » WPVWM c Z c  ¯  ¼ WPVWMZ FCPZ ¯½ a. b. c. d. Gambarkan himpunan fuzzy A dan B Tuliskan himpunan fuzzy A dan B Gambar dan tiliskan himpunan fuzzy " dan Gambar dan tuliskan himpunan fuzzy ∪ $ ∩ $ ∪ $ dan ∩ $ e. Tuliskan supp dari ∪ $ ∩ $ ∪ $ ∩ $ Teori Himpunan Fuzy 63 f. Tuliskan core dari ∪ $ ∩ $ ∪ $ ∩ $ g. Tuliskan height dari " ˆ " ‡ " ˆ " ‡ 4. Kerjakan seperti nomer 3 bila ¬ ¯ Z ­ ¯ Z  » WPVWM c Z c ¯ ¼ WPVWMZ FCPZ ¯½ ¬ Z  ¯  ¯ $ Z ­ ¯   Z ¯ WPVWM c Z c WPVWM c Z c » ¯ ¯ ¼ WPVWM c Z c ¯ WPVWMZ FCPZ ¯ ½ 5. Hitung scalar cardinality untuk masing - masing himpunan fuzzy di bawah a A = 0,4/v + 0,2/w + 0,5/x + 0,4/y + 1/z b B = Z , untuk x ∈ X, X = { 0,1,...,10 } Z + c C = 1 -  , untuk x ∈ X, , X = {1,...,10 } Z 6. Fuzzy set A, B dan C dinyatakan oleh fungsi keanggotaan A x =  Z ; $ Z = − Z ; C x =  +  Z − Z+ Bila X himpunan bilangan Real dengan interval X = [ 0, 10 ] a gambarkan graph fungsi keanggotaan A x, B x dan C x b gambarkan graph fungsi keanggotaan A x, B x dan C x 64 Matematika Diskrit kemudian tuliskan formulasi matematikanya. c Seperti nomor b untuk ∪ $ ∪ %$ ∪ % d Seperti nomor b untuk ∩ $ ∩ %$ ∩ % e Seperti nomor b untuk ∪ $ ∪ % ∩ $ ∩ E 7. Himpunan Fuzzy A, B dan C dimana X = [0,80] dinyatakan oleh fungsi keanggotaan ⎧ ⎪ Z = ⎨ − Z  ⎪ ⎩ WPVWMZ ⎭ ⎧ ⎪ Z −  ⎪ $ Z = ⎨ ⎪ − Z  ⎪⎩ WPVWMZ⎫ ⎪ WPVWM≤\≤ ⎪ ⎬ WPVWM≤Z≤ ⎪ ⎪⎭ WPVWM ⎭ Kerjakan seperti no 6 -oo0oo- Teori Himpunan Fuzy 65 66 Matematika Diskrit 4 LOGIKA FUZZY PENGANTAR Istilah “Logika fuzzy” dalam berbagai literatur telah digunakan dalam dua pengertian yang berbeda. Dalam pengertian yang luas, logika fuzzy dipandang sebagai suatu sistim konsep, prinsip, dan metoda dalam hubungan dengan cara memberi alasan yang mendekati nilai sebenarnya. Dalam pengertian yang sederhana, dipandang sebagai logika dengan nilai kebenaran beragam dan ada dalam interval antara 0 dan 1. Dalam pengertian luas, logika fuzzy adalah suatu wilayah aplikasi dalam teori himpunan fuzzy, dimana penggunaan konsep, prinsip dan metode yang dikembangkan dalam teori himpunan fuzzy digunakan untuk merumuskan berbagai format yang mendekati, dalam mengambil keputusan. Dalam susunan yang memanfaatkan seperangkat teori himpunan fuzzy untuk mendapatkan keputusan, sangat penting untuk menetapkan suatu hubungan antara derajat keanggotaan himpunan fuzzy dan derajat kebenaran fuzzy proposisi. Hubungan ini juga penting untuk mengembangkan konsep tambahan yang diperlukan logika fuzzy, seperti qualifier, quantifiers dan probabilitas fuzzy. Logika Fuzzy 67 LOGIKA DENGAN NILAI KEBENARAN BERAGAM Sebagaimana telah kita ketahui, semua proposisi pada logika klasik hanya mempunyai 2 nilai kebenaran yaitu true/ benar/1 dan false/salah/0. Logika dengan nilai kebenaran beragam adalah pengembangan dari logika klasik dengan menyisipkan nilai tengah diantara 0 dan 1, kemudian antara 0 dan ½ serta ½ dan 1, demikian seterusnya sesuai dengan situasi persoalan yang dihadapi. Maksud dari penyisipan nilai tengah ini adalah untuk memberikan nilai kebenaran sebuah proposisi yang nilai kebenarannya bisa setengah benar atau setengah salah, misalnya “Tadi pagi terjadi tabrakan pesawat terbang di bandara SukarnoHatta.” Adalah pernyataan yang nilai kebenarannya ½ benar atau ½ salah. Pada buku ini penulis membatasi pembahasan hanya sampai proposisi dengan 3 nilai kebenaran yaitu Benar/true/1 Salah/False/0 Setengah benar atau setengah salah = ½ Lukasiewicz Bochvar Kleene Heyting Reichenbach a b ∧ ∨ →↔ ∧ ∨ →↔ ∧ ∨ →↔ ∧ ∨ → ↔∧ ∨ → ↔ 0 0 0 ½ ½ ½ 1 1 1 0 ½ 1 ½ ½ 1 1 1 1 68 0 0 ½ 0 1 0 0 0 ½½ 1 ½ 0 0 ½½ 1 1 0 ½ 1 ½ ½ 1 1 1 1 1 1 1 ½ 1 1 0 ½ 1 1 ½ 0 ½ 1 ½ 0 ½ 1 0 0 ½½ 0 1 ½½ ½½ ½½ 0 1 ½½ 1 1 1 ½ 1 ½ ½ ½ 0 ½ 1 1 ½ 0 ½ ½ ½ 0 ½ 1 0 0 0 0 ½ ½ 0 ½ 1 1 1 1 ½ ½ 1 0 ½ 1 1 ½ 0 ½ ½ ½ 0 ½ 1 0 0 0 0 ½ ½ 0 ½ 1 0 ½ 1 ½ ½ 1 1 1 1 1 1 1 0 1 1 0 ½ 1 1 0 0 0 0 0 0 0 1½ ½½ 0 0 ½½ 1 1 0 ½ 1 ½ ½ 1 1 1 1 1 1 1 ½ 1 1 0 ½ 1 1 ½ 0 ½ 1 ½ 0 ½ 1 Matematika Diskrit Dampak dari adanya nilai kebenaran ½, memunculkan 5 tabel kebenaran yang ditulis oleh para ahli yaitu Lukasiewicz, Bochvar, Kleene, Heyting, dan Reichenbach, seperti tabel diatas. Operasi logika fuzzy Lukasiewicz C =  − C C ∨ D = OCZ C D C ∧ D = OKP  + D − C C → D = OKP  + D − C C ↔ D =  − D − C C ∨ D = C → D → D C ∧ D = C ∨ D C ↔ D = C → D ∧ D → C Untuk operasi peniadaan/negasi kelima tabel kebenaran berlaku C =−C Logika fuzzy telah banyak diaplikasikan dalam berbagai bidang terutama computer service dan computer engineering, selain itu juga dipakai untuk membantu manusia dalam melakukan pengambilan keputusan yang tidak hanya bisa dijawab denga Ya atau Tidak, seperti pada Fuzzy Inference System, Fuzzy Clustering, Fuzzy Database, Fuzzy Linier Programming, Fuzzy Integer Transportation Problem dan sebagainya. Berikut contoh pada Fuzzy Inference System Sebuah perusahaan perakit CPU mempunyai data-data permintaan, persediaan dan produksi dalam 1 bulan terakhir sebagai berikut * Permintaan terbesar mencapai 1000 unit per hari, terkecil mencapai 200 unit per hari. Logika Fuzzy 69 ** Persediaan di gudang terbanyak mencapai 120 unit per hari, terkecil mencapai 20 unit per hari. *** Produksi maksimum 1400 unit per hari, minimum 400 unit per hari Berapa CPU harus dirakit bila jumlah permintaan 800 unit dan persediaan digudang masih 60 unit, bila proses produksi mengikuti aturan fuzzy Jika permintaan turun dan persediaan banyak maka produksi barang berkurang. Jawab Fungsi permintaan Permintaan maksimum = 1000 unit per hari, memiliki derajat keanggotaan 1 dan titik koordiant 1000,1. Permintaan minimum 200 unit per hari, memiliki derajat keanggotaan 0 dan titik koordiant 200,0. Fungsi keanggotaan fuzzy untuk permintaan naik adalah Y - Y1 = X - X1 Y2 - Y1 X2 - X1 Y - 0 = X - 200 1-0 1000 - 200 Y = X - 200 800 Komplemen Permintaan naik adalah permintaan turun, fungsi keanggotannya adalah Y = 1 - Y = 1 - x - 200 = - X + 1000 800 800 Dengan cara yang sama dapat dicari fungsi keanggotaan fuzzy untuk persediaan naik. 70 Matematika Diskrit maksimum 120,1 dan minimum 20,0 ; − − =  −  − − ;=  Komplemen persediaan naik adalah persediaan turun, fungsi keanggotaannya ; =− ; =− Z − − +  =   Dengan cara yang sama fungsi keanggotaan fuzzy untuk produksi naik dapat dicari maksimum 1400,1 dan minimum 400,0 ; − −  =  −  −  −  ;=  Komplemen produksi naik adalah produksi turun, dengan fungsi keanggotaan ; =− ; =− Z −  − +  =   jadi bila ada permintan 800 unit dan prsediaan di gudang ada 60 unit, mengikuti aturan produksi Jika permintaan turun dan persediaan banyak maka produksi barang berkurang. Jika permintaan turun ;= − +  WPVWMZ=;= Logika Fuzzy 71 dan persediaan banyak ;= − WPVWM=;=  Karena penggabungan pernyataannya dan, maka operasi Fuzzy yang digunakan Intersection yaitu min = Maka produksi berkurang − +   = − +   = 7PKV ;= Jadi, CPU yang harus diproduksi 1150 unit. SOAL-SOAL 1. Buat tabel kebenaran ` R ∧ S ≡` R∨ ` S dengan tabel kebenaran Lukasiewicz, Bochvar, Kleene, Heyting, dan Reichenbach. 2. Nyatakan modus ponen R → S ∧ R ∧ S dengan tabel kebenaran Lukasiewizc, Bochvar, Kleene, dan Heyting. 3. Tentukan tabel kebenaran proposisi di bawah dengan kelima tabel kebenaran yang telah diberikan. a. R š R b. R ™ R c. R ™ R š S d. R š R ™ S 4. Tunjukkan bahwa a. R S  jika dan hanya jika R c S b. R S  jika dan hanya jika R S n k 72 Matematika Diskrit Berlaku untuk kelima tabel kebenaran yang telah diberikan 5. Selidiki validitas modus sillogisme dengan kelima tabel kebenaran yang telah diberikan. 6. Kerjakan seperti contoh fuzzy inference di atas halaman 70. Bila produksi perusahaan tersebut menggunakan aturan fuzzy sebagai berikut a. Jika permintaan turun dan persediaan sedikit maka produksi barang berkurang b. Jika permintaan naik dan persediaan banyak maka produksi barang bertambah c. Jika permintaan naik dan persediaan sedikit maka produksi barang bertambah 7. Sebuah perusahaan perakitan CPU memiliki data penjualan 1 bulan terakhir sebagai berikut Permintaan terbesar mencapai 500 unit/hari dan terkecil 100 unit/hari. Persediaan terbanyak mencapai 60 unit/hari dan terkecil 10 unit/hari. Produksi terbesar mencapai 700 unit/hari dan terkecil 200 unit/hari. Tentukan berapa unit CPU yang harus diproduksi jika ada permintaan sebanyak 400 unit dan persediaan digudang hanya ada 30 unit CPU, bila proses produksi menggunakan logika fuzzy seperti dibawah a. Jika permintaan turun dan persediaan banyak maka produksi arang berkurang. b. Jika permintaan turun dan persediaan sedikit maka produksi barang berkurang. c. Jika permintaan naik dan persediaan banyak maka produksi barang bertambah. Logika Fuzzy 73 d. Jika permintaan naik dan persediaan sedikit maka produksi barang bertambah. e. Hitung produksi rata - rata terbobot dari ke 4 aturan produksi diatas. Catatan rumus rata - rata terbobot Z= 1Z1 + 2Z2 + 3Z3 + 4Z4 / 1+ 2+ 3 + 4 -oo0oo- 74 Matematika Diskrit 5 RELASI KLASIK PENDAHULUAN Relasi Klasik crisp relation menggambarkan ada tidaknya interaksi atau koneksi antara elemen-elemen dari 2 atau lebih himpunan dalam urutan tertentu. Contoh Dua orang yaitu Rosa dan Marina memiliki hubungan sebagai berikut; “Rosa adalah kakak kandung Marina” jadi relasinya adalah hubungan famili. Banyak sekali jenis relasi, tetapi ada 2 yang sering digunakan yaitu relasi; “lebih besar dari dan kurang dari”. Kita dapat mendefisinikan sebuah relasi melalui perkalian skalar pada koordinat cartesian dimana sumbu x mewakili variabel x dan sumbu y mewakili variabel y. Misalnya variable x dan y adalah bilangan real dalam interval tertutup [x1, x2] dan [y1, y2] atau misalkan himpunan X = {x1,x2} Y = {y1,y2} Relasi Klasik 75 Maka X Y X Y x x x x Y= X= X= Y= {x1, {y1, {x1, {y1, y1, x1, x1, y1, x1, y2, x1, y1, y2, x2, x1, y1, x2, x2, y2, y2, y1, x2, x1, y1, x2, y2, x2, y2, y2} x2} x2} y2} Y Y2 Y1 0 X1 X2 X Maka relasi R antara elemen-elemen dalam himpunan X dan himpunan Y adalah 4 ⊆ × ; Pasangan-pasangan elemen dalam R menggambarkan relasi, karena ada 2 himpunan yang terlibat dalam relasi R, maka relasi demikian disebut relasi binary. Contoh Misalkan kita definisikan sebuah relasi X = Y dengan notasi R 1 , maka 4 ⊂ × ; dapat kita gambarkan dalam koordinat cartesian sebagai berikut 76 Matematika Diskrit Y [Z Z ]× [[ [ ] Y2 4 Z = [ Y1 0 X1 X2 X Relasi dapat melibatkan n himpunan yang disebut relasi berdimensi n. Dalam buku ini hanya dibahas relasi binary. PEMAPARAN RELASI Pemaparan Koordinat Relasi dapat dipaparkan melalui sistem koordinat, sebagai contoh relasi. R = {Microsoft, Windows, IBM, 0s/2, Macintosh, MacOS} MacOS 0s/2 Win Micro IBM Relasi Klasik Mac 77 Tanda titik pada gambar di atas menjelaskan bahwa pasangan tersebut termasuk dalam relasi. Pemaparan Matrik Relasi dapat dipaparkan melalui sebuah matrik, yaitu dengan nilai 1 apabila ada relasi antara 2 elemen pasangan terurut, atau O apabila tidak ada relasi antara 2 elemen pasangan terurut. MacOS OS/2 Win Micro IBM Mac 0 0 1 0 1 0 1 0 0 Pemetaan Pemetaan adalah paparan visual relasi dengan menghubungkan anggota suatu himpunan dengan anggota himpunan yang lain, sebagai contoh 78 Micro MacOS IBM Win Mac OS/2 Matematika Diskrit Dalam sebuah relasi, satu anggota pada himpunan pertama dapat dipetakan ke lebih dari satu anggota himpunan kedua. Relasi binary adalah relasi dimana tidak ada anggota pada himpunan pertama yang dihubungkan dengan lebih dari satu anggota pada himpunan kedua. Relasi binary disebut fungsi dengan notasi 4 ⊆ ×$ atau 4 →$ Contoh Microsoft Excel Microsoft Word Windows Ms Power Point Open Office Dia Linux Gimp Graph Berarah Graph berarah merupakan gambaran yang paling tepat untuk relasi 4  dengan aturan-aturan sebagai berikut a. Setiap anggota himpunan X digambarkan dengan lingkaran b. Garis berarah antar lingkaran menggambarkan adanya relasi antara anggota himpunan, jadi pasangan-pasangan anggota himpunan tersebut termasuk dalam relasi. Relasi Klasik 79 Contoh a1 Prasyarat untuk semua bagian yang lain a3 Prasyarat untuk a5 dan a6 a6 Bukan prasyarat untuk semua bagian yang lain. a1 a2 a3 a5 a4 a6 OPERASI DALAM RELASI BINARY Semua operasi dalam himpunan juga dapat diaplikasikan ke dalam relasi, namun demikian ada beberapa operasi yang tidak ada hubungannya dengan operasi dalam himpunan, seperti inverse relasi dan komposisi relasi Inverse Relasi R–1 Inverse relasi R–1 adalah kebalikan dari relasi R, inverse relasi R, didefinisikan dengan menukar susunan anggota di semua pasangan yang ada dalam relasi, jadi Jika 4 → ; maka 4 ; n dan kebalikan dari R–1 adalah relasi R yang asli, yaitu  4 4 untuk semua relasi binary R. 80 Matematika Diskrit Komposisi Relasi Komposisi relasi adalah operasi mengkombinasikan 2 buah relasi binary yang cocok/sesuai dan menghasilkan sebuah relasi binary yang baru. Agar dua buah relasi dapat dikomposisikan maka relasi P dan Q didefinisikan sebagai 2 → ; 3; → 1 2 ³ 1 , , , , , 1 mendahului 4 1 langsung mendahului 2 2 tidak dapat dibandingkan dengan 3 4 didahului 1 2 langsung didahului 1 Dalam Poset terdapat istilah-istilah yang penting seperti ° Upper bound ub = batas atas adalah semua elemen himpunan diatas himpunan bagian yang akan kita cari batas atas nya, dimana setiap elemen dalam himpunan bagian itu dapat dibandingkan dengan semua elemen batas atasnya ° Least upper bound lub = supremum = batas atas terkecil adalah elemen dari upper bound yang paling dekat atau langsung didahului himpunan bagian yang kita cari batas atas terkecilnya ° Lower bound lb = batas bawah adalah semua elemen himpunan di bawah himpunan bagian yang akan kita cari batas bawah nya, dimana setiap elemen dalam himpunan bagian itu dapat dibandingkan dengan semua elemen batas bawah nya. ° Greatest lower bound glb = Infimum = batas bawah terbesar. adalah elemen dari lower bound yang paling dekat atau langsung mendahului himpunan bagian yang kita cari batas bawah terbesarnya. Relasi Klasik 87 Contoh Misalkan himpunan A = {a, b, c, d, e, f, g} diorder menurut diagram Hess di bawah. a b c d e f g Pandang sub himpunan A yaitu himpunan B = {c, d, e} Maka ° batas atas dari B = ub B = a, b, c. c termasuk batas atas karena c mendominsi d dan e. c termasuk batas atas dari B karena c langsung didahului oleh d dan e ° batas bawah dari B = lb B = f, g bukan batas bawah dari B karena g tidak mendahului d, g dan d tidak dapat dibandingkan ° batas atas terkecil dari B adalah c karena c langsung mendahului a dan b c mendominasi a dan b ° batas bawah terbesar dari B = glb B = f Poset dapat memiliki glb dan lub lebih dari 1 tidak tunggal Contoh Misalkan himpunan A = {a, b, c, d, e, f, g} di order dengan diagram Hess g e f c d b a 88 Matematika Diskrit Pandang himpunan B = {c, d}, maka gl b B = b lub B = e dan f Namun demikian ada Poset khusus yang hanya boleh memiliki 1 buah tunggal glb dan lub,poset demikian disebut latis Lattice. Dengan kata lain Lattice adalah poset yang setiap 2 elemennya mempunyai lub dan glb masing-masing satu buah tunggal. Contoh = {Z Z Z } dan = {∅{Z }{Z }{Z }{Z Z }{Z Z }{Z Z }{Z Z Z }} diorder dengan diagram Hess \Z Z Z ^ \Z Z ^ \Z ^ \Z Z ^ \Z ^ \Z Z ^ \ Z ^ † Kita perhatikan disini bahwa setiap 2 elemen dalam poset diatas hanya memiliki 1 lub dan 1 glb. ° lub dari {{x1}, {x2}} adalah φ glb dari {{x1}, {x2}} adalah {x1, x2} ° lub dari {{x1, x2}, {x1}} adalah {x1} glb dari {{x1, x2}, {x1}} adalah {x1, x2} Relasi Klasik 89 SOAL 1. Misalkan himpunan A = {1, 2, 3} dan relasi yang ada adalah 4 Tentukan apakah relasi-relasi dibawah mempunyai sifat refleksi, simetri, transitif atau antisimetri. n a 4 = {CD C D} h 4 = ]      _ i 4 = {CD C = D CVCWC = D − CVCWC −  = D} j 4 = {   } 2. Tentukan R–1 dari masing-masing relasi pada nomer 1. 3. Carilah komposisi relasi di bawah dimana masingmasing relasinya diambil dari soal nomor 1 dan 2 a 4 $ 4 b 4 $ 4 −  c 4 $ 4 d 4 $ 4 −  e 4 $ 4 f 4  $ 4 g 4 $ 4 90 h i j k l m n 4 $ 4  4 $ 4 4 $ 4 4 $ 4 4 $ 4 4 $ 4 − 4 $ 4 Matematika Diskrit 4. Misalkan himpunan A = {1, 2, , 8} diorder dengan diagram Hess 1 2 3 4 5 7 6 8 a Tuliskan simbol-simbol >, ≥, // 1 2 1 5 8 5 6 4 6 5 b Pandang himpunan-himpunan bagian A yaitu himpunan B = {4, 5, 6}, C = {2, 3, 6} dan D = {4, 5, 7}. Tentukan masing-masing ub, lub, lb, dan glb dari himpunan B, C dan D. 5. Misalkan himpunan A = {1, 2, 3, , 6} diorder dengan diagram Hess 1 2 4 3 5 6 pandang himpunan bagian A yaitu B = { 2,3,4 } Relasi Klasik 91 Tentukan ub, lub, lb dan glb dari B n 6. Dari Tabel selidikilah apakah 4 adalah relasi yang ekuivalen dipandang dari mata kuliah yang diambil, kalau ya buatlah partisinya berdasarkan kelas ekuivalennya. 7. Sama dengan Soal nomor 6, dipandang dari umur mahasiswa. 8 Relasi R adalah relasi dalam himpunaan 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 } yang didefinisikan oleh “ x membagi y “ a. Gambarkan poset diatas dengan diagram Hess. b. Cari ub, lub, lb dan glb dari himpunan-himpunan B = { 8, 12, 18, 27 } C = { 12, 18, 36, 72, 108, 216 } D = { 6, 12, 18, 24, 36, 54 } E = { 6, 12, 36, 72 } -oo0oo- 92 Matematika Diskrit 6 FUNGSI DEFINISI FUNGSI Fungsi adalah sebuah relasi binary dimana masing-masing anggota dalam himpunan A domain hanya mempunyai satu bayangan pada himpunan B kodomain. Notasi Fungsi H →$ dibaca f adalah fungsi dari A ke dalam B atau f memetakan A ke dalam B. Jika himpunan A = B, maka H → disebut operator atau transformasi pada A. Contoh Misalkan A = {Microsoft Word, Word Pad, Microsoft Excel, Lotus 123, Paint Shop Pro, Gimp} B = {Pengolah kata, Pengolah data, Pengolah gambar} Misalkan H → $ Fungsi 93 Maka Microsoft Word Word Pad Microsoft Excel Lotus 1 2 3 Paint Shop Pro Pengolah kata Pengolah data Pengolah gambar GIMP A B Himpunan A disebut ranah domain dari fungsi f. Himpunan B disebut ko-ranah kodomain dari fungsi f. Pengolah kata adalah bayangan dari Microsoft Word dan Word Pad, dinyatakan oleh f Microsoft Word dan f Word Pad Jangkauan range dari f adalah Pengolah kata, Pengolah data dan Pengolah gambar. MACAM-MACAM FUNGSI Fungsi satu-satu Sebuah fungsi H → $ dikatakan fungsi satu-satu jika dan hanya jika setiap elemen pada himpunan A mempunyai bayangan yang tidak sama pada elemen himpunan B. 94 Matematika Diskrit Contoh A = himpunan sistem operasi A = {MacOS, OS/2} B = himpunan Komputer B = {IBM, Macintosh} H MacOS OS/2 A n$ IBM Macintosh B Fungsi pada Sebuah fungsi H → $ dikatakan fungsi pada jika dan hanya jika setiap elemen himpunan B muncul sebagai bayangan dari sekurang-kurangnya satu elemen himpunan A. Contoh A = himpunan sofware aplikasi B = himpunan sistem operasi Ms Word Windows Open office Ms Exel GIMP A Fungsi Linux B 95 Fungsi konstan Suatu fungsi H → $ dikatakan fungsi konstan jika dan hanya jika hanya ada satu elemen himpunan B yang menjadi bayangan dari seluruh elemen himpunan A. Contoh A = himpunan sofware aplikasi B = himpunan sistem operasi Linux Ms Word Macintosh Ms Excel OS/2 Ms Power Poind Windows Fungsi Invers H $ → adalah sebuah fungsi dimana Fungsi invers untuk setiap D ∈ $ mempunyai bayangan tunggal dalam himpunan A. Dengan demikian hanya fungsi satu-satu yang memiliki fungsi invers.  Contoh H Ms Word GIMP Ms Excel A 96 n$ Linux Windows OS/2 B Matematika Diskrit H → $ bukan fungsi satu-satu , sehingga tidak memiliki fungsi invers f–1 H n$ Linux Ms Excel Windows GIMP A B H → $ adalah fungsi satu-satu sehingga fungsi invers H $ →  ada yaitu H $  n Ms Excel Linux GIMP Windows B A Contoh lain Misalkan H Z = NQI Z − , maka H Z adalah  [ = NQI Z − [ = Z − Z = [ + [ = Z + ∴ H − = Z + Fungsi 97 KOMPOSISI FUNGSI Komposisi fungsi dari fungsi f dan g dinyatakan oleh I $ H atau IH . Jika H → $ dan I $ n % , maka I $ H → % I $ H C ≡ I H C Contoh f g 1 a x 2 b y 3 c z A B C Maka I $ H → % adalah I $ H  = I H  = I D = \ I $ H = I H = I E = Z I $ H = I H = I D = \ Misalkan H Z = Z −  dan I Z = Z + . Maka H $ I = H I = H =  I $ H = I H = I = 98 Matematika Diskrit FUNGSI KARAKTERISTIK Fungsi karakteristik adalah sebuah fungsi yang memetakan semesta pembicaraan ke dalam himpunan {1,0}, dinotasikan - 7 →  - Z dimana ¬LKMCZ Ž ­LKMCZ  Contoh 1 Misalkan U = {a, b, c, d, e, f} A = {a, c, e} Maka - 7 →  dapat didefinisikan melalui diagram di bawah a b 1 c d e 0 f 2 Misal U = {a, e, i, o, u} A = {a, e, i} B = {e, i, o} Buktikan -∩$ = -$ Fungsi 99 Jawab G ∈ ∩ $ maka G ∈ dan G ∈ $ ∴ - ∩$ G =  - G = FCP- $ G =  Jadi - ∩$ G = - - $ G =  ⋅  =  ∴ - ∩$ = - ⋅ - $ SOAL 1. Buatlah 5 buah contoh fungsi satu-satu yang ada kaitannya dengan software maupun hardware. 2. Buatlah 5 buah contoh fungsi pada yang ada kaitanya dengan software maupun hardware. 3. Misalkan fungsi-fungsi f dan g pada bilangan-bilangan riel R didefinisikan oleh H Z = Z + Z − I Z = Z − a Carilah rumus-rumus dari I $ H dan H $ I . b Hitung I $ H dan H $ I . 4. Misalkan H 4 → 4 didefinisikan oleh H Z = Z − . a Buktikanlah bahwa H Z adalah fungsi satu-satu dan fungsi pada b Carilah rumus fungsi invers f–1. 5. Misalkan 100 U = {1, 2, 3, . . . , 10} A = {1, 2, . . . , 6} B = {5, 6, . . . , 10} Matematika Diskrit Buktikan a. - ∩$ = - ⋅ - $ b. - ∪ $ = - + - $ − - ∩$ c. - − $ = - − - ∩$ -oo0oo- Fungsi 101 102 Matematika Diskrit 2 ALJABAR BOOLE Aljabar Boole adalah cabang ilmu matematika yang di perlukan untuk mempelajari disain logika dari sebuah sistem digital. Aljabar Boole dikembagkan oleh George Boole tahun 1847 untuk memecahkan persoalan logika matematika. A PLIKASI A LJABAR BOOLE DALAM JARINGAN SWITCHING Jaringan komunikasi biasa digambarkan dalam node dan link; Node merepresentasikan end-terminal perangkat jaringan, digambarkan dengan lingkaran/kotak; Link merepresentasikan hubungan/koneksi antar nodes, digambarkan dengan garis. Sebagai perangkat jaringan node dapat berfungsi sebagai Routing, Switching, maupun Multiplexing. Transmisi data/informasi jarak jauh biasa dilakukan melalui jaringan switching node, transmisi dimulai dan diakhiri di perangkat yang disebut station, yang dapat berupa komputer, terminal, telepon, dll. Switching node pada umumnya mengenal dua keadaan bilangan biner 0 dan 1, 0 digunakan untuk jangkauan tegangan Aljabar Boole 103 antara 0 sampai 0,8 volt, 1 digunakan untuk jangkauan tegangan antara 2 volt sampai 5 volt. Jadi 0 dan 1 menyatakan variabel tegangan Untuk dapat menyelesaikan persoalan jaringan switching kita harus mengenal terlebih dahulu hukum-hukum aljabar Boole sebagai berikut Bila C D E Ž $ B =himpunan Boole maka memenuhi hukum-hukum 1. Komutatif C + D = D+C C×D = D×C 2. Distributif C + D × E = C + D × C + E C × D + E = C × D + C × E 3. Identitas C C z GNGOGP\GTQ C t  C z GNGOGPWPKV 4. Komplemen C + C =  C ×C = 5. Idempoten C+C = C C×C = C 6. Boundednes C + =  C× = 7. Absorbsi C + C × D = C C × C + D = C 104 Matematika Diskrit 8. Involusi C = C =   = 9. Asosiatif C + D + E = C + D + E C × D × E = C × D × E 10. De Morgan C + D = C × D C × D = C + D Kita perhatikan bahwa setiap hukum di atas mengganti operasi logik + dengan x , x dengan +, 0 dengan 1, 1 dengan 0. Ini menunjukkan bahwa hukum-hukum aljabar Boole memenuhi prinsip duality, yaitu dual suatu hukum merupakan hukum juga. Jaringan switching pada umumnya dibentuk dari rangkaian dasar seri AND dan pararel OR. Rangkaian seri AND 0QVCUK Z$CVCW ∧$CVCW$ A Aljabar Boole B 105 Rangkaian pararel OR 0QVCUK +$CVCW ∨$ A B Contoh Gambarkan jaringan swiching yang diberikan oleh polinomial Boole Z ∧ [ ∨ Z ∧ Z ∧ [ , kemudian sederhanakanlah jaringan tersebut; Bilamana jaringan tersebut on atau off? Jawab Z ∧ [ ∨ Z ∧ Z ∧ [ ≡ Z ∧ [ ∨ Z ∧ Z ∨ [ , DeMorgan y x’ x y’ x ≡ Z ∧ [ ∨ Z ∧ Z ∨ [ , absorbsi z Z ™ Z š [ , distribusi ≡ Z ∧ Z ∨ Z ∧ [ , komplemen ≡ ∨ Z ∧ [ , identitas z Z ™ [ 106 Matematika Diskrit x y’ x y y’ Z ™ [ 1 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 Jadi jaringan switching tersebut on bila x on dan y off atau jaringan on bila x on dan [ on. A PLIKASI A LJABAR BOOLE PADA RANGKAIAN LOGIK GATE Sebagian besar rangkaian dalam hardware sistem pengolah data adalah rangkaian logik, yang dapat bekerja sebagai penguat, pembanding, perata, osilator, penjumlahan, pengendali, penyandi, dll. Ada beberapa simbol yang sering digunakan dalam rangkaian logik yaitu 1. AND A B E A B t$ 0 0 1 1 0 1 0 1 0 0 0 1 ' ≡ ×$ Aljabar Boole 107 2. OR A E B A B A+B 0 0 1 1 0 1 0 1 0 1 1 1 '≡ +$ 3. NOT A A A’ E 0 1 1 0 A B E 0 0 1 1 0 1 0 1 1 1 1 0 ' ≡ 4. NOT AND NAND A B E ' ≡ × $ 5. NOT OR NOR A B E A B E 0 0 1 1 0 1 0 1 1 0 0 0 ' ≡ + $ 108 Matematika Diskrit 6. Exlusive OR EXOR A E B A B E 0 0 1 1 0 1 0 1 0 1 1 0 ' ≡ $ + $ ≡ ⊕ $ 7. Exclusive NOR EXNOR A B E A B E 0 0 1 1 0 1 0 1 1 0 0 1 ' ≡ $ + $ Contoh Gambarkan rangkaian logika yang dinyatakan oleh ' = ∨ ∧ $ ∧ $ ∧ $ ∨ % Kemudian sederhanakan. Aljabar Boole 109 Jawab A B E C ' z š ™ $ ™ $ ™ $ š % ' z š ™ $ ™ $ "CTPSCTJ ' z š š $ ™ $ %F.PSHBO ' z š $ ™ $ *EFNQPUFO ' z $ "CTPSCTJ B 110 E = B’ Matematika Diskrit A PLIKASI A LJABAR BOOLE DALAM OPERASI KELIPATAN PERSEKUTUAN KECIL KPK DAN FAKTOR PERSEKUTUAN BESAR FPB Dalam aljabar Boole operasi + sama dengan operasi KPK dan operasi x sama dengan operasi FPB, untuk mengingat kembali operasi KPK dan FPB perhatikan contoh berikut Contoh Carilah KPK dan FPB dari 45, 48 dan 72. Jawab Faktor prima dari 45 adalah × Faktor prima dari 48 adalah  × Faktor prima dari 72 adalah × Jadi KPK dari 45, 48 dan 72 adalah  t t Jadi FPB dari 45, 48 dan 72 adalah 3. Perhatikan untuk KPK, semua faktor prima yang ada dikalikan, faktor yang sama diambil pangkat tertinggi; untuk FPB hanya faktor prima yang sama dalam 45, 48 dan 72 dikalikan, diambil faktor prima dengan pangkat terendah. Contoh Misalkan diketahui himpunan Boole B = % = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} Cari 1. 5 + 12 KPK dari 5 dan 12 adalah 60 2. 5 x 12 FPB dari 5 dan 12 adalah 1 3. Elemen zero=? a+0=a identitas Aljabar Boole 111 + 123 1 2 3 4 5 6 10 12 15 20 30 60 12345678901234567890123 12345678901234567890123 123 1 123 1 2 3 4 5 6 10 12 15 20 30 60 12345678901234567890123 123 2 123 2 2 6 4 10 6 10 12 30 20 30 60 123 3 123 3 6 3 12 15 6 30 12 15 60 30 60 4 123 4 4 12 4 20 12 20 12 60 20 60 60 123 5 123 5 10 15 20 5 30 10 60 15 20 30 60 123 123 6 123 6 6 6 12 30 6 30 12 30 60 30 60 123 10 10 10 30 20 10 30 10 60 30 20 30 60 123 12 123 12 12 12 12 60 12 60 12 60 60 60 60 123 15 123 15 30 15 60 15 30 30 60 15 60 30 60 123 20 123 20 20 60 20 20 60 20 60 60 20 60 60 123 30 123 30 30 30 60 30 30 30 60 30 60 30 60 123 60 123 60 60 60 60 60 60 60 60 60 60 60 60 Perhatikan, yang memenuhi rumus identitas a + 0 = a adalah 1, jadi elemen zero dari B = & adalah 1. 4. Elemen Unit = ? C × = C identitas 60 t 1 2 3 4 5 6 10 12 15 20 30 12 1 1 1 1 1 1 1 1 1 1 1 1 12 1 12 2 1 2 1 2 1 2 2 2 1 2 2 12 2 12 3 1 1 3 1 1 3 1 3 3 1 3 12 3 4 1 2 1 4 1 2 2 4 1 4 2 12 4 12 5 1 1 1 1 5 1 5 1 5 5 5 12 5 6 1 2 3 2 1 6 2 6 3 2 6 12 6 12 10 1 2 1 2 5 2 10 2 5 10 10 12 10 12 12 1 2 3 4 1 6 2 12 3 4 6 12 12 15 1 1 3 1 5 3 5 3 15 15 15 12 15 12 20 1 2 1 4 5 2 10 4 5 20 10 12 20 12 30 12345678901234567890123 1 2 3 2 5 6 10 6 15 10 30 12 30 60 12345678901234567890123 1 2 3 4 5 6 10 12 15 20 30 12 60 Perhatikan, yang memenuhi rumus identitas a x 1 = a adalah 60, jadi elemen unit dari B = D60 adalah 60. 112 Matematika Diskrit  ! C C VOJU LPNQMFNFO    MJIBUUBCFMTPBMOPNFS   » ¼ KBEJh  LBSFOBGBLUPSEBSJ  ½ MINIMAL DNF DISJUNCTIVE NORMAL FORM Minimal dnf adalah ekspresi Boole yang ada dalam bentuk minimal, dimana suku-sukunya tidak ada satu didalam yang lain. Minimal dnf dapat dicari dengan 2 cara, yaitu 1 Dengan teori include dan teori konsensus. 2 Dengan peta karnaugh. Dengan Teori Include dan Konsensus Sebelum mempelajari teori include dan konsensus ada baiknya kita kenal dulu beberapa istilah, yaitu a Fundamental product perkalian dasar adalah perkalian dua atau lebih variabel-variabel Boole yang tidak memuat variabel yang saling komplemen atau sama. Contoh CDCDE′C ′DE′ disebut fundamental product CDCC′DCCDD′ bukan fundamental product b Ekspresi Boole E Adalah penjumlahan satu atau lebih fundamental product. Contoh ' = CD + CD E + CDE Ekspresi Boole dalam bentuk dnf, jika suku-suku E tidak ada satu di dalam yang lain. Aljabar Boole 113 Contoh ' = CD + C ′DE′ + CD′E DGPVWMFPH ' = CD + CDE DWMCPFPH MCTGPCCDFKFCNCOCDE Teori Include Jika fundamental product R , termasuk didalam fundamental product p2, maka p1 + p2 = p1 Contoh ab + abc = ab Konsensus Jika fundamental product p1 dan p2 memiliki satu elemen saja yang saling komplemen, maka konsensus Q dari R dan p 3 adalah perkalian elemen-elemen p 1 dan p 2 dimana elemen-elemen yang saling komplemen dihilangkan dan tidak ada pengulangan. Contoh 2 = CDE ′ ⎫ ⎬ maka konsensus dari P dan P adalah Q = abd 1 2 2 = CDEF ⎭ 2 = CDE′ ⎫ tidak ada konsensus sebab ada 2 elemen yang ⎬ 2 = C ′DEF ⎭ saling komplemen Teori Konsensus Jika Q konsensus dari P1 dan P2 maka 2 + 2 +3 = 2 + 2 114 Matematika Diskrit Contoh 2 CDE » ¼ 3 CDF 2 CDEF ½ 2 2 3 CDE CDEF CDF CDE CDEF E E CDF CDE CDEF CDE F CDEF CDE CDE F CDEF CDEF JODMVEFJODMVEF CDE CDEF 2 2 Ekspresi Boole minimal adalah ekspresi Boole E yang semua fundamental productnya sudah minimal dnf tidak ada satu di dalam yang lain. Contoh ' = C ′D′ OKPKOCNFPH ' = CD + CD′E + C ′DE′ DGNWOOKPKOCN & dapat diminimalkan dengan teori konsensus sebagai berikut konsensus ' = CD + CD E + C DE konsensus include ' = CD + CE + CD E + C DE + DE ' = CD + CE + DE include ' adalah ekspresi Boole minimal Aljabar Boole 115 Suku-suku dari ekspresi Boole minimal disebut prime implicant R dari ekspresi Boole B yang memenuhi sifat K '+ 2 = ' K dan tidak ada fundamental product lain yang termasuk 2 mempunyai sifat-sifat tersebut. K Contoh DE′CFCNCJ RTKOGKORNKECPVFCTK ' = CD + CD′E + C ′DE′ ' + 2 = CD + CD′E + C ′DE′ + DE′ ,karena bc’ konsensus dari ab dan a’bc’maka ab + a’bc’ + bc’ = CD + CD′E + C ′DE′ = ab + a’bc’ = ' Jadi ekspresi Boole minimal sama dengan jumlah dari prime implicantnya. Peta Karnaugh Adalah peta dari ekspresi Boole yang dapat digunakan untuk mencari prime implicant dan ekspresi Boole minimal. Peta untuk 2 variable x 116 x’ y y 0 y’ 1 x 0 1 Matematika Diskrit Peta untuk 3 variable xy x’y x’y’ xy’ z yz 00 z’ 01 x 0 1 01 11 11 10 Peta untuk 4 variable xy x’y x’y’ xy’ xy za za 00 z’a 01 z’a’ 11 za’ 10 00 10 Contoh Cari ekspresi Boole minimal dari ' = CDEF + C ′DEF + C ′D′EF + CD′EF + CDE F ′ + C ′D′EF ′ + CD′EF ′ Jawab E1 = c lihat peta ' = CDEF + CD′EF + CDE F ′ + CD′EF ′ Jawab E2 = ac lihat peta ' = Z[\′C + Z[\′C ′ + Z ′[ ′\′C ′ + Z[ ′\′C + Z[ ′\′C ′ Jawab ' = Z\′ + [ ′\′ lihat peta Aljabar Boole 117 Jawab cd ab cd 00 c’d 01 c’d’ 11 cd’ 10 ab a’b a’b’ ab’ 00 E1 = c ab cd a’b 01 11 10 E1 = c a’b’ √ ab’ √ ab cd 00 00 01 11 10 c’d 01 c’d’ 11 √ √ 10 √ √ cd’ √ √ E2 =ac xy x’y E2 =ac x’y’ xy’ zd xy za 00 z’a √ √ √ 01 z’a’ √ √ √ 11 za’ 01 11 10 √ √ √ √ √ √ 10 E3 = xz’ + y’z’ 118 00 E3 = xz’ + y’z’ Matematika Diskrit SOAL-SOAL 1. Gambarkanlah jaringan switching yang dinyatakan dengan polinominal Boole di bawah, kemudian sederhanakan dan gambarkan bentuk sederhananya, kapan jaringan tersebut on atau off. a ∧ $ ∨ ∧ $ ∨ $ b ∧ % ∨ $′ ∨ $ ∧ % ′ c d e ∨ $ ∧ % ∨ ∧ $ ∧ $ ∨ ∧ $ ∨ ∨ $ ∨ $ ∧ % ∧ ∨ $ ∨ %′ f g ∧ $ ∨ % ∨ ∨ % h ∧ $ ∨ ∧ ∧ $ ′ ∧ ′ ∨ $ ′ $ ∧ ∨ % ∨ ∨ % 2. Gambarkanlah gebang logika yang dinyatakan dengan ekspresi Boole di bawah, kemudian sederhanakan dan gambarkan bentuk sederhananya. a + × $ × $ = ' b × $ + × $ + $ × $ + = ' c + $ × % + + $ × % × & = ' d × + $ + $ + $ = ' e × + $ × = ' f t $ % t & t t $ % & ' g $% + $′ ′%′ ′ = ' h A’B’C’ + A’BC’ + AB’C’ + ABC’ = E i A+B+CA+B+C’A’+B+C’A’+B+C’A’+B’+C’ = E j A’BC’ + A+B’C = E k [ BC {A’ +AB’ + ABC’}’]’ Aljabar Boole 119 3. Rancanglah sebuah jaringan logika penjumlah yang mempunyai 3 inputan dan 2 outputan, yaitu x, y, z sebagai input dan c, s sebagai output, dimana c = 1 bila 2 atau 3 inputnya sama dengan 1 serta s = 1 bila hanya 1 atau ketiga inputnya sama dengan 1 . 4. Bila diketahui B = D70, carilah a elemen zero b elemen unit c  t d  5. Bila diketahui B = & , carilah a elemen zero b elemen unit c  × +  d 6. Cari prime implicant dari expresi Boole dibawah ' C D E F CD E F C DE F C D EF C DEF CDEF C D EF CDEF CD EF ' C DE F CDE F C D E F CDE F CD E F CD EF C DEF ' C D E F C DE F CDE F CD E F C D E F CDE F CDEF CD EF ' C DE F CDE F C D EF C DEF CDEF CD EF C D EF CDEF CD EF ' C DE F CDE F C D E F C DE F CDE F C D EF CDEF CD EF CDEF CD EF 120 Matematika Diskrit 7. Rancang sebuah jaringan logika pengurang yang mempunyai 3 inputan x, y, dan z dan 2 keluaran b dan d. b=1 bila ketiga inputnya sama dengan 1 atau z=1 atau y=1 atau z=y=1. d=1 bila ketiga inputnya atau satu inputnya sama dengan 1. 8. Rancang sebuah jaringan logika pembanding 1 bit yang mempunyai 2 inputan A dan B dan 3 outputan yaitu x bila A B. 9. Kembangkan rancangan jaringan logika pada soal no. 8 untuk pembanding 2 bit. 10. Seorang mahasiswa ingin merancang sebuah jaringan logika yang mampu merubah bilangan biner tak berbobot menjadi bilangan biner berbobot dekoder seperti Desimal Biner tak berbobot Biner berbobot 25 11001 0010 2 0101 5 43 101011 0100 4 0011 3 bila mahasiswa tersebut membatasi hanya untuk bilangan biner 4 bit atau maksimum 1111 selesaikan pekerjan mahasiswa tersebut. Aljabar Boole 121 11. 4 3 STOP 2 1 Gambar diatas adalah gerbang TOL otomatis dengan 4 alat yaitu 1. 2. 3. 4. Sensor masuk mobil, Box kartu yang memiliki sensor, Mesin portal, Sensor keluar mobil. Berikut mekanismenya; 1. Jika alat sensor masuk = 1 , Sensor Box = 0 dan sensor keluar = 0, maka mesin box mengeluarkan kartu tanda masuk TOL 2. Jika pengemudi telah mengambil kartu pada box kemudian sensor box aktif yaitu = 1 , sensor masuk = 0, sensor keluar = 0, maka mesin portal terbuka. 3. Jika mobil telah melewati sensor keluar sehingga sensor masuk = 0 , sensor box = 0 dan sensor keluar = 1 , maka mesin portal tertutup kembali. Rancanglah rangkaian logika dengan 3 inputan X untuk sensor masuk, Y untuk sensor box, Z untuk sensor keluar, disertai dengan tabel kebenaran. 122 Matematika Diskrit 12. C B A Gambar di atas a adalah alat peringatan dini bahaya banjir, Pada alat tesebut terdapat 3 buah sensor yang berfungsi mencek ketinggian air. berikut mekanisme keja alat tersebut; 1. Saat keadaan normal ketiga sensor = 0. 2. Siaga 3 saat air menyentuh sensor A, maka A = 1 , B=0 dan C =0. 3. Siaga 2 saat air menyentuh sensor B, maka A=1, B=1, dan C =0. 4. Siaga 1 saat air menyentuh sensor C, maka ketiga sensor = 1. buatlah rangkaian logika untuk alat tersebut yang dapat memberikan peringatan dini pada saat siaga1, siaga2 dan siaga3. 13. Integrasikanlah soal nomor 3 dan soal no 7 sehingga menjadi sebuah jaringan logika dengan 3 inputan dan 4 outputan. -oo0oo- Aljabar Boole 123 124 Matematika Diskrit 8 TEORI GRAPH PENDAHULUAN Dalam kehidupan sehari-hari, banyak persoalan yang dapat disimpulkan sebagai persoalan yang berhubungan dengan himpunan dan relasi binary, di mana logika dari persoalan tersebut sering kali dapat kita gambarkan dengan sebuah graph. Contoh Seorang programer ingin membuat software sistem jaringan trasportasi sedemikian rupa sehingga apabila sebuah kendaraan bergerak dari titik A kesemua titik lain kemudian kembali ke titik A dapat dilakukan dengan efisien. Teori Graph 125 e1 A e5 E e3 C e7 e6 e4 e2 B F D e8 e11 G e12 H e9 e13 e10 e14 I J e15 e16 e17 e18 L e19 M K Kita lihat di sini titik A, B, ..... M menggambarkan himpunan titik-titik lampu merah dimana kendaraan tertahan selama 1 menit, garis atau rusuk mengambarkan relasi “terhubung” antara titik-titik yang ada. Jadi dapat kita simpulkan, graph adalah gambaran logika dari suatu kejadian, proses, peristiwa atau hal-hal lain yang saling berkaitan. Graph adalah himpunan pasangan terurut V, E, dimana V adalah himpunan vertex/titik dan E adalah himpunan edge/rusuk. Untuk terhubung ke b oleh suatu garis/rusuk jika {a, b} ŽE . Bila kita perhatikan graph diatas, ternyata unsur-unsur graph adalah vertek/titik-titik simpul/noktah yang diwakili oleh A,B ....., M dan rusuk/edge yang diwakili oleh e1, e2,..., e19. A dikatakan berdekatan/berdampingan/adjacent dengan B, E, F dan J. e1 dikatakan bertemu/incident dengan e2 dan e7 di titik B. 126 Matematika Diskrit MACAM-MACAM GRAPH Macam-macam graph dilihat dari stukturnya ada 6 macam graph, yaitu a Multigraph Multigraph adalah graph yang mempunyai satu atau lebih pasangan rusuk ganda yang menghubungkan 2 buah titiknya. Contoh A e1 e2 C B e4 e3 e6 D e5 e7 E Titik A dan C dihubungkan oleh 2 buah rusuk, e1 dan e2, demikian juga titik B dan D dihubungkan oleh rusuk e4 dan e6. b Pseudograph Pseudograph adalah graph yang memiliki satu atau lebih pasang rusuk ganda yang menghubungkan 2 buah titiknya multigraph dan memiliki satu atau lebih loap pada titiknya. Teori Graph 127 Contoh A e1 B e5 e4 e3 e2 e7 e6 C D e9 e8 E Graph di atas selain memiliki rusuk ganda juga memiliki dua buah loap dititik B dan E. Loap adalah rusuk yang ujungnya hanya memiliki sebuah titik. c Trivialgraph Trivialgraph adalah graph yang hanya terdiri dari satu titik. d Graph lengkap Graph lengkap adalah graph yang setiap titiknya terhubung dengan semua titik yang lain dengan hanya satu rusuk. Contoh K5 128 Matematika Diskrit e Graph teratur Graph teratur adalah graph yang setiap titiknya mempunyai sejumlah incident rusuk yang sama. Contoh f Bipartitegraph Bipartitegraph adalah graph yang titik-titiknya dapat dikelompokkan menjadi dua, titik-titik dalam satu kelompok tak terhubung dan titik-titik antar kelompok terhubung lengkap. Contoh Teori Graph 129 Dilihat dari lintasannya ada 3 macam graph, yaitu a Traversable graph Traversable graph adalah graph yang semua rusukrusuknya dapat dilalui masing-masing sekali atau graph yang dapat digambar tanpa mengangkat pensil. 5 6 2 1 9 7 4 8 3 Contoh Teori Euler ° Semua graph terhubung yang mempunyai titik ganjil maksimum dua adalah traversable. ° Traversable lintasannya selalu dimulai dari titik ganjil pertama dan diakhiri pada titik ganjil kedua. Titik ganjil adalah titik dimana rusuk yang incident/bertemu dengan titik tersebut berjumlah ganjil. c Eulerian graph Eulerian graph adalah graph yang semua rusuknya dapat dilalui masing-masing sekali dan memiliki lintasan tertutup, artinya titik awal sama dengan titik akhir. 130 Matematika Diskrit Contoh 1 2 8 6 5 14 13 9 7 12 11 10 4 3 Teori Euler Bila sebuah graph semua titiknya genap maka graph tersebut mempunyai lintasan euler. Karena graph euler dapat digambar tanpa angkat pensil maka euler graph juga merupakan traversable graph. c Hameltonian graph Hameltonian graph adalah graph yang semua titik-titiknya dapat dilalui masing-masing sekali dan mempunyai lintasan tertutup, artinya titik awal sama dengan titik akhir. Contoh 2 3 4 1 5 8 Teori Graph 7 6 131 KONEKSITAS Hubungan atau lintasan antar titik dalam sebuah graph dapat dibedakan manjadi beberapa jenis, yaitu a Walk Walk adalah lintasan dari suatu titik ke titik yang lain. Contoh Misalkan titik mewakili kota dan rusuk mewakili jalan, maka dari Jakarta ke Bogor kita dapat membuat banyak walk, yaitu Jakarta – Jagorawi – Bogor Jakarta – Tangerang – Bogor Jakarta – Cikampek – Bandung – Bogor dan lain-lain. b Closed Walk Closed Walk adalah walk yang titik awal sama dengan titik akhir Contoh Jakarta – Cikampek – Jakarta Jakarta – Jagorawi – Bogor – Tangerang – Bogor – Jagorawi –Jakarta dan lain-lain. c Trail Trail adalah walk yang semua rusuknya berlainan, artinya yang kita perhatikan adalah lintasannya. Contoh Jl. Borobudur – Jl. Prambanan – Jl. Mendut Jl. Merdeka Barat – Jl. Thamrin – Jl. Sudirman dan lain-lain. 132 Matematika Diskrit d Path Path adalah walk yang semua titiknya berlainan, artinya yang kita perhatikan kotanya. Contoh Jakarta – Cikampek – Purwakarta Jakarta – Bogor – Cianjur – Bandung dan lain-lain. e Cycle Cycle adalah path yang tertutup, artinya titik awal sama dengan titik akhir. Contoh Jakarta – Tangerang – Bogor – Jakarta Jakarta – Cikampek – Padalarang – Cianjur – Bogor – Jakarta. dan lain-lain. f Girth Girth adalah cycle terpendek dari cycle-cycle yang dimiliki oleh sebuah graph. Contoh A B C D E F G Graph di atas mempunyai banyak cycle, tetapi ada satu yang terpendek yang disebut girth, yaitu CGFC, panjangnya 3 banyak rusuk yang membentuk cycle Teori Graph 133 g Circumference Circumference adalah cycle terpanjang dari cycle-cycle yang dimiliki oleh sebuah graph. Contoh Dari contoh graph f diatas, A B C G F E D A adalah circum ference dengan panjang = 7. banyaknya rusuk yang membentuk cycle BERKAITAN DENGAN JARAK Dalam sebuah graph, mengetahui hal-hal yang berkaitan dengan jarak penting, antara lain untuk menentukan jari-jari, diameter, sentral, dan pusat graph. Jarak antara dua titik adalah walk yang semua titiknya berlainan dan mempunyai lintasan terpendek. Contoh Kita dapat membuat banyak walk yang semua titiknya berlainan antara Jakarta – Bogor, yaitu Jakarta – Jagorawi – Bogor Jakarta – Tangerang – Bogor Jakarta – Cikampek – Padalarang – Puncak – Bogor. Dari contoh lintasan-lintasan di atas yang disebut jarak adalah lintasan Jakarta – Jagorawi – Bogor karena terpendek. Ada beberapa hal yang berkaitan dengan jarak, yaitu. a Eksentrisitas suatu titik eu Eksentrisitas suatu titik adalah jarak terpanjang suatu titik terhadap semua titik dalam sebuah graph. 134 Matematika Diskrit Contoh A D E Jarak C B F H I A–B=1 A–C=2 A–D=2 A–E=1 A–F=2 A–H=3 A–I=4 Jadi eksentrisitas titik A = e A = 4 b Jari - jari graph rG Jari-jari adalah eksentrisitas titik yang terkecil dalam sebuah graph. Contoh Dari contoh graph diatas, eksentrisitas titik-titiknya, sebagai berikut e A = 4 e B = 3 e C = 4 e D = 4 e E = 3 Teori Graph 135 e F = 2 e H = 3 e I = 4 Jadi jari-jari graph = r G = 2 c Diameter graph dG Diameter graph adalah eksentrisitas titik yang terbesar dalam sebuah graph. Contoh Dari graph di atas dapat disimpulkan bahwa diameter graph d G = 4. d Titik sentral graph Titik sentral graph adalah titik-titik simpul yang nilai eksentrisitasnya sama dengan nilai jari-jarinya. Dari cotoh di atas titik sentral graph adalah titik F. e Pusat graph Pusat graph adalah himpunan titik-titik yang nilai eksentrisitasnya sama dengan nilai jari-jarinya. Dari contoh diatas, pusat graph adalah {F} DERAJAT/DEGREE SUATU TITIK Seperti kita ketahui sebuah titik dalam graph dapat mempunyai 1 atau lebih rusuk yang incident padanya atau tidak ada satupun rusuk yang incident padanya. Derajat sebuah titik adalah banyaknya rusuk yang incident pada titik tersebut. Titik ganjil adalah titik yang derajatnya genap adalah titik yang berderajat genap. 136 Matematika Diskrit Contoh C e1 A e2 B e6 D e9 e5 e3 e8 e7 e4 F H e10 E e11 I e12 Maka derajat titik-titiknya adalah FGI  FGI $ FGI % FGI & FGI '  FGI FGI * FGI + Jumlah degree = 24 Jumlah rusuk = 12 Jumlah degree = 2 kali jumlah rusuk. TITIK POTONG GRAPH CUT POINT Sebuah graph dapat dipotong pada sebuah atau lebih titiknya, jika suatu titik dalam sebuah graph dinyatakan sebagai titik potong, maka titik tersebut dan semua rusuk yang incident pada titik itu dihilangkan. Teori Graph 137 Contoh Bila titik-titik B dan C pada contoh graph pada bagian dinyatakan sebagai cut point, maka terjadi graph baru seperti di bawah D E A I H F UKURAN SECARA GRAFIKAL Sebuah graph dapat kita pelajari melalui ukuran grafisnya, yang meliputi ° ° ° ° Jumlah rusuk Jumlah titik Derajat titik Titik potong Dua buah graph yang mempunyai ukuran-ukuran grafis sama disebut Isomorphic graph. Contoh A B E e1 e2 e3 r1 r2 e4 e5 C 138 G1 F r3 r4 r5 D H G2 I Matematika Diskrit G1 dan G2 isomorphis, ukuran grafisnya sama dan berkorespondensi 1 – 1 antara titik-titik dan rusuk-rusuk yaitu titik-titik rusuk-rusuk G T G T $+ G T %' &* G T G T MATRIK GRAPH Sebuah graph dapat kita sajikan dalam bentuk matrik, yaitu a Matrik titik Adjacent Matrix b Matrik rusuk Edge Matrix c Matrik titik – rusuk Incidence Matrix Contoh Nyatakanlah graph di bawah dalam bentuk matrik titik, rusuk dan titik rusuk. A e1 e2 D C B e9 e4 e5 e6 e3 e10 e11 e7 E e8 F I Matrik titik dari graph di atas adalah matrik 7 X 7, karena graph di atas mempunyai 7 buah titik Teori Graph 139 $ % & ' $       µ ¶  ¶ &   ¶ '      ¶ ¶¶ % + ¦ § § § § § § § § § ¨ ¶ ¶ ¶ Cara mengisi elemen-elemen matrik ° Baris 1 kolom 1, dari A ke A = 0 ° Baris 1 kolom 2, dari A ke B = 1,titik A dan B terhubung oleh sebuah rusuk ° Baris 4 kolom 4, dari D ke D = 2, titik D mempunyai loop ° Baris 5 kolom 6, dari E ke F = 2, titik E dan F terhubung oleh 2 buah rusuk e7 dan e8 ° Baris 7 kolom 1, dari I ke A = 0, titik I dan A tidak terhubung oleh sebuah rusuk. Matrik rusuk dari graph di atas adalah matrik 11 X 11, karena graph di atas mempunyai 11 rusuk. G G G G G G G G G G G 140 G G G G G G G G G G G                                                 Matematika Diskrit Cara mengisi elemen-elemen matrik Bila sebuah rusuk bertemu dengan rusuk yang lain disebuah titik maka elemen matriknya = 1, bila tidak bertemu di satu titik maka elemen matriknya = 0. Matrik titik-rusuk dari graph di atas adalah matrik 7 X 11, karena graph tersebut memiliki 7 titik dan 11 rusuk. $ % & ' + G G G G G G G G G G G                      Cara mengisi elemen-elmen metrik Bila sebuah rusuk bertemu dengan sebuah titik maka nilai elemen matrik = 1, bila tidak bertemu maka nilai elemen matrik = 0. LABELED DIGRAPH Dalam menggambarkan logika suatu kejadian sebuah graph sering kali diberi label/bobot, graph demikian disebut Labeled graph C 8 D A 11 14 Teori Graph 5 F 13 H 7 9 E I 15 141 Contoh Rusuk AF mempunyai bobot 11, rusuk AH mempunyai bobot 14 dan seterusnya. Bobot di sini bisa menyatakan jarak, selisih bunga deposito, kecepatan atau apa saja maksud pembuat graph. Rusuk sebuah graph dapat pula diberi arah untuk menggambarkan logika sebuah sistem yang berarah, graph demikian disebut digraph, rusuk yang berarah sering kali disebut arcus arc. C D E A I H F Contoh Berkaitan dengan digraph maka hubungan antar titik dapat dikategorikan menjadi 3 macam, yaitu a Lemah weak Hubungan antar titik dalam digraph dikatakan lemah apabila arcusnya berlawanan P P Q R 142 Q R Matematika Diskrit Contoh b Unilateral Hubungan antar titik dalam digraph dikatakan unilateral bila arcusnya searah P P Q R Q R Contoh c Kuat strong Hubungan antar titik dalam digraph dikatakan kuat bila arcusnya searah dan tertutup P Q R Contoh Rusuk sebuah graph dapat diberi bobot sekaligus diberi arah, graph demikian disebut labeled digraph. Contoh A, B, C dan D bermain tembakan Teori Graph 143 50 A 50 50 B D 50 100 50 50 C A dapat manembak ke B dan D, jadi bobot AB = AD = 50% B dapat manembak ke A dan D, jadi bobot BA = BD = 50% C dapat manembak ke B dan D, jadi bobot CB = CD = 50% D hanya dapat menembak ke C, jadi bobot DC = 100% Arcus menunjukkan arah tembakan, bobot menyatakan peluang masing-masing tembakan. DERAJAT TITIK PADA DIAGRAPH Derajat sebuah titik pada digraph dapat dibagi menjadi dua, yaitu a In degree b out degree Indegree sebuah titik adalah jumlah rusuk yang masuk kesebuah titik. Outdegree sebuah titik adalah jumlah rusuk yang keluar dari sebuah titik. Titik yang indegreenya = 0 disebut sumber/ asal/source. 144 Matematika Diskrit Titik yang outdegreenya = 0 disebut tujuan/sink. Contoh P Q S R Titik Q = sumber, karena indegree Q = 0 Indegree P = 2, karena ada 2 rusuk yang masuk ke P Outdegree P = 1, karena ada 1 rusuk yang keluar dari P Indegree R = 1 Outdegree R = 2 Titik S = tujuan, karena outdegree S = 0 GRAPH BIDANG PLANAR GRAPH Sebuah graph dikatakan graph bidang bila rusukrusuknya terletak pada bidang datar serta tidak saling berpotongan selain di titiknya. Graph bidang dapat dibuat dari sebuah graph sebidang a planar graph, seperti di bawah. Teori Graph 145 A A B B C C D D E E H F H F I I Aplanar è Planar graph Graph bidang disebut peta map, rusuk-rusuk graph bidang memisahkan graph bidang atas wilayah-wilayah/daerahdaerah/region, karena wilayah dibatasi oleh rusuk-rusuk, maka wilayah dalam graph bidang dapat dibedakan menurut jumlah rusuk yang membatasi wilayah tersebut derajat wilayah Contoh A r1 B D r8 r2 F C r4 r3 r5 E H r6 r7 I Rusuk-rusuk pada graph bidang di atas membagi graph bidang tersebut atas 8 wilayah, yaitu r1 sampai r8, dimana 146 Matematika Diskrit r1, r2, r3, r4, r5, dan r7 berderajat 3 r6 berderajat 5 r8 berderajat 5 Rumus-rumus Euler. Jika sebuah peta mempunyai titik sebanyak V, mempunyai wilayah sebanyak R dan mempunyai rusuk sebanyak E, maka peta tersebut memenuhi rumus-rumus Euler sebagai berikut 1. 8 4 ' 2. 3. ¥ FGI T ¥ ' ' c 8 Contoh Dari peta di atas diketahui E = 14, banyak titik V = 8 dan bayak wilayah R = 8, sehingga 1. 8 4 '  2. ¥ FGI T t t ¥ '  =   c 3.  c  PEWARNA PETA Pewarnaan sebuah peta dapat dilakukan dalam 3 cara, yaitu a mewarnai titik. b mewarnai rusuk. c mewarnai wilayah. Teori Graph 147 Ada beberapa prinsip dalam mewarnai peta, yaitu ° Banyak warna yang harus digunakan harus seminimum mungkin, banyak warna minimum disebut bilangan kromatik X G. ° Dua buah titik yang terhubung oleh satu atau lebih rusuk tidak boleh diberi warna yang sama pewarnaan titik. ° Dua buah rusuk atau lebih yang bertemu pada sebuah titik tidak boleh diberi warna sama pewanaan rusuk. ° Dalam mewarnai peta pakailah sebuah warna secara optimum, artinya warna kedua digunakan setelah warna pertama tidak dapat digunakan lagi, demikian seterusnya sampai semua titik / rusuk / region terwarnai semua. Contoh A 1 B 2 3 C 1 D 1 4 E F Mewarnai titik 1 Titik A kita beri warna 1, 2 Titik D dan F kita beri warna 1 karena baik titik D maupun F tidak saling terhubung langsung dengan titik A 3 Titik B, C dan E saling terhubung langsung sehingga harus diberi warna yang berbeda, yaitu warna 2, 3, dan 4. Jadi bilangan kromatik X G = 4 148 Matematika Diskrit Mewarnai rusuk e1 1 3 2 2 e3 e4 1 e5 e6 4 2 e2 e7 e8 3 e9 1 1 e1 kita beri warna 1, 2 e4 dan e9 kita beri warna 1, karena e1, e4, dan e9 tidak saling terhubung langsung oleh sebuah titik. 3 e2 kita beri warna 2, 4 e5 dan e7 dapat diberi warna 2, karena e2, e5, dan e7 tidak saling terhubung melalui sebuah titik. 5 e3 dan e8 diberi warna 3 6 e6 diberi warna 4 Jadi bilangan kromatik graph di atas X G = 4 Dalam hal mewarnai rusuk untuk graph lengkap Kn , bilangan kromatik dari Kn memenuhi rumus DKNCPICPLKN ¬ P - P ­ P  DKNCPIGPCR Teori Graph 149 Contoh K5 e1 = 1 e5 = 3 e8 = 5 e7 = 5 e9 = 4 e6 = 4 e4 = 2 e10 = 3 e2 = 2 e3 = 1  G FCPG FKDGTKYCTPC G FCPG FKDGTKYCTPC G FCPG FKDGTKYCTPC  G FCPG FKDGTKYCTPC G FCPG FKDGTKYCTPC ,CFK - 150 Matematika Diskrit K6 1 3 e1 4 5 e2 e7 1 2 2 5 3 e10 4 e9 e8 2 3 1 e11 e6 2 4 5 e3 e13 3 5 4 1 3 4 e14 e12 e15 e5 5 4 3 1 5 1 2 e4 2 G G FCPG FKDGTKYCTPC G G FCPG FKDGTKYCTPC G G FCPG FKDGTKYCTPC G G FCPG FKDGTKYCTPC G G FCPG FKDGTKYCTPC Jadi bilangan kromatik X K6 = 5. Teori Graph 151 SOAL-SOAL 1. Buatlah lintasan yang mungkin tranversable, euler dan hamelton pada graph di bawah A C B E D F I H J A D K L C B E F I H J K A I B H C F D K 152 Matematika Diskrit Teori Graph 153 2. Seorang programer mendapat tugas membuat software untuk dipasang pada otak sebuah rudal jelajah yang akan ditembakan ke suatu wilayah yang digambarkan oleh graph di bawah, bila titik-titik mewakili obyek vital yang akan dihancurkan dan bila daya hancur ledakan rudal sampai radius 2 dari pusat ledakan, dititik manakah programer tesebut harus menjatuhkan rudal jelajah supaya daya hancurnya maksimum. A B D E I J C H F K M L N A B E D I F O H M L K J C P Q R T 154 N S U Matematika Diskrit 3. Gambarkanlah graph yang dipaparkan melalui matrik titik dibawah, kemudian tuliskan kembali dalam bentuk matrik titik rusuk A B C D E A 0 1 0 0 1 B 1 0 1 0 1 C 0 1 2 0 1 D 0 0 0 0 2 E 1 1 1 2 0 A B C D E F A 0 0 1 0 0 1 B 0 2 0 1 2 0 C 1 0 0 0 0 1 D 0 1 0 0 1 0 E 0 2 0 1 0 0 F 1 0 1 0 0 0 4. Gambarkanlah graph yang dipaparkan oleh matrik titik _ rusuk dibawah, kemudian tuliskan kembali dalam bentuk matrik rusuk e1 e2 e3 e4 e5 e6 e7 e8 e9 Teori Graph A 1 1 1 0 0 0 0 0 0 B 0 0 0 1 1 1 0 0 0 C 0 0 0 0 0 0 1 1 1 D 1 0 0 1 0 0 1 0 0 E 0 1 0 0 1 0 0 1 0 F 0 0 1 0 0 1 0 0 1 155 5. Tuliskanlah graph di bawah dalam matrik titik, rusuk, titik – rusuk. B A C E H D F 6. Warnailah K7, K8, dan K9. 7. Sebuah graph direpresentasikan oleh matrik titik di bawah A B C D A B C 1 1 1 F 1 G H 1 I J 1 1 1 1 K 2 1 1 1 E 1 1 1 1 G 1 1 1 1 1 1 J 1 1 1 1 2 I K F 1 1 D H E 1 1 1 1 1 1 1 1 a Warnailah graph di atas dengan pewarnaan titik, rusuk, dan region serta tuliskan masing - masing bilangan kromatisnya. b Tentukan pusat dan sentral graph 156 Matematika Diskrit 8. Seorang ahli jaringan mendapat order memasang RW NET dengan sistem tanpa kabel, apabila titik - titik pelanggan digambarkan dengan matrik titik seperti di bawah dan radius sinyalnya 2 step dari titik hotspot, dimana ahli jaringan harus menempatkan hotspotnya, agar jangkauannya maksimum? A A B C 1 1 C D B F E 1 F G H I 1 1 1 M N O P Q R S T 1 1 1 1 1 I L 1 1 H K 1 1 1 J 1 1 E G D 1 1 1 1 1 1 1 1 1 1 1 J K L 1 1 1 1 1 1 1 1 M N O 1 1 1 1 P Q 1 R S T Teori Graph 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 157 9. Sebuah graph dinyatakan dengan matrik titik di bawah A A B B 1 C 1 1 J G 1 1 1 1 1 1 1 1 1 1 O P J K L 1 1 1 1 M N O P 1 1 1 1 1 1 1 1 1 L N I 1 K M H 1 1 1 F 1 1 F I E 1 1 G H D 1 D E C 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 a Warnai graph di atas dengan pewarnaan titik, rusuk, dan region, kemudian tuliskan bilangan kromatik masing - masing pewarnaan tersebut. b Andaikan titik mempresentasikan terminal yang akan berlangganan internet dan rusuk menyatakan jarak antar terminal dalam hal ini dinyatakan sebagai 50 meter, dimana hotspot harus dipasang agar jangkauan internet maksimum bila radius signal hotspot hanya 100 meter. 158 Matematika Diskrit 10. Diketahui Adjacency Matrik dari graph G sebagai berikut A B C D E F A 0 1 1 1 1 1 B 1 0 1 1 1 1 C 1 1 0 1 1 1 D 1 1 1 0 1 1 E 1 1 1 1 0 1 F 1 1 1 1 1 0 a Gambarkan graph G b Warnailah titik dan rusuk graph G c Tentukan bilangan kromatik XG dan X’G POHON/TREE Dalam dunia informatika pohon memegang peranan penting bagi seorang programer untuk menggambarkan hasil karyanya; bagi seorang user, setiap kali berhadapan dengan monitor untuk menjalankan program aplikasi selalu akan menelusuri bagian-bagian dari pohon sebelum sampai pada program aplikasi yang dimaksud. Pohon adalah sebuah graph yang mempunyai n buah titik, n – 1 rusuk dan tidak mempunyai lingkaran cycle free serta merupakan graph terhubung. Teori Graph 159 Contoh bukan pohon karena ada cycle pohon; tidak ada cycle, n = 7; E = 6 Diagram pohon dapat digunakan sebagai alat untuk memaparkan logika sebuah persoalan dengan menggambarkan semua alternatif pemecahannya. Contoh Pernyataan aritmatik 2 x 3 + 4 x 2 – 1 + 5 dapat dijelaskan dengan diagram pohon berikut – + + x x 1 5 2 3 4 2 2 x 3 + 4 x 2 – 1 + 5 = 8 Perhatikan operator – paling atas disebut akar pohon, operator-operator di bawahnya disebut titik cabang pohon, bilangan-bilangan disebut daun pohon. Hubungan antara pohon, titik, dan rusuk dapat dinyatakan sebagai Banyak rusuk = Banyak titik – Banyak pohon. 160 Matematika Diskrit Contoh G1 G2 G3 Dari diagram pohon G 1, G2, dan G3, di atas dapat diketahui bahwa Jumlah pohon = 3 yaitu G1 , jumlah titik = 7 , jumlah rusuk 6 G2 , jumlah titik = 12 , jumlah rusuk 11 G3 , jumlah titik = 11 , jumlah rusuk 10 Jadi banyak titik seluruhnya = 30 banyak rusuk seluruhnya = 27 banyak pohon = 3 sehingga 27 = 30 – 3 Tree Sebuah pohon katakanlah T disebut spanning tree dari sebuah graph G, jika T adalah subgraph dari G yang mencakup semua titik graph G. Teori Graph 161 Contoh a e2 e5 g b e1 c e3 d a b c e4 e8 e7 e6 e e9 f e 11 e10 e12 e h g G T1 a b d c d f e f h g T2 h T1, T2, ... adalah spanning tree dari graph G, karena T1, T2, merupakan subgraph dari G yang mencakup semua titik graph G. Minimal Spanning Tree Misalkan pada graph di bawah titik-titik merepresentasikan kota dan rusuk merepresentasikan jaringan jalan raya yang akan dibangun dengan bobot/label merepresentasikan rencana biaya antar kota, maka untuk mencari biaya minimal rencana pembuatan jalan yang menghubungkan semua kota, kita memerlukan minimum spanning tree. a 12 b 4 6 11 13 8 g 1 e d 2 c 7 5 f 14 9 3 h 10 i Graph rencana biaya pembuatan jaringan jalan raya yang menghubungkan 9 kota. 162 Matematika Diskrit a b 4 c 1 5 6 e d 8 f 9 3 g 2 h i Minimal spanning tree, menggambarkan jaringan jalan raya yang menghubungkan 9 kota dengna biaya minimum = 38 Berakar Rooted Tree Seperti pohon alami pohon dalam graph juga mempunyai akar, cabang, dan daun. Akar pohon adalah titik yang indegreenya nol titik sumber. Setiap titik dapat dianggap atau dijadikan akar, titik yang dianggap sebagai akar ditandai dengan lingkaran yang mengelilingi titik tersebut. Daun pohon adalah setiap titik bukan akar yang indegreenya 1 dan outdegreenya 0 rink. Tinggi pohon adalah panjang rusuk maksimum dari akar sampai daun. Teori Graph 163 c d b a H e f F k D h C g E I j i l B A A = akar pohon B, C, D, E, F, G, H, I = titik cabang a, b, ..., k, l = daun Tinggi pohon = 4, yaitu dari A ke j a Warnailah graph di atas dengan pewarnaan titik, rusuk, dan region serta tuliskan masing - masing bilangan kromatisnya. b Tentukan pusat dan sentral graph Sebuah pohon dapat dipotong pada sembarang titik cabangnya menjadi dua atau lebih sub pohon sesuai dengan banyaknya rusuk pada titik cabang tersebut. T 164 Misalkan pohon di samping dipotong pada titik cabang T, maka akan terjadi 4 sub pohon baru karena titik T mempunyai 4 rusuk, yaitu Matematika Diskrit T1 dengan 5 rusuk T2 dengan 3 rusuk T3 dengan 2 rusuk T4 dengan 6 rusuk T2 T1 T4 T3 Sehingga berat pohon dititik T dapat diketahui adalah 6, karena berat pohon di suatu titik adalah jumlah rusuk maksimum dari semua cabang di titik tersebut. Titik berat pohon adalah titik di mana berat pohon di titik tersebut minimum, jika titik berat pohon jumlahnya lebih dari satu titik maka himpunan titik berat tersebut disebut pusat berat. Contoh 32 32 32 32 32 32 32 32 32 29 22 16 32 32 32 32 32 32 32 32 32 32 Titik berat pohon di atas adalah 16, karena 16 adalah berat minimum dari semua titik yang ada. Teori Graph 165 7 7 4 P 7 7 Q 7 4 5 Titik berat pohon di atas adalah 4, yaitu di titik P dan Q, dan pusat berat pohon = {P, Q}. Pohon binary adalah jenis pohon berakar yang penting, bagi setiap orang yang mempelajari teknologi informasi, karena pada umumnya karya mereka direpresentasikan dengan pohon binary, dimana pada pohon binary setiap titik cabang pohon dapat mempunyai ° dua anak cabang, satu kekiri dan satu kekanan. ° satu anak cabang, atau ° tidak mempunyai anak cabang. Contoh a b c f d e g h Titik b dan f mempunyai 2 anak cabang, titik d dan c mempunyai satu anak cabang titik g, h, dan i tidak mempunyai anak cabang. i Pohon binary dikatakan full bila setiap titiknya mempunyai dua anak cabang atau tidak punya anak cabang. Dalam pohon binary dikenal istilah-istilah ° titik internal adalah titik yang mempunyai 2 anak cabang ° titik terminal adalah titik yang tidak mempunyai anak cabang daun. 166 Matematika Diskrit Theorema Bila sebuah pohon binary full dan mempunyai i titik internal, maka titik terminalnya ada sebanyak i + 1 dan jumlah semua titiknya ada sebanyak 2i + 1. Contoh a b d e h f b c j k l m g n o p Titik internal adalah a, b, c, d, e, f, dan g, jadi i = 7 Titik terminal adalah h, j, k, l, m, n, o, dan p, jadi ada 8 atau i +1. Jumlah seluruh titik ada 15 titik atau 2i + 1 Berurut Berakar Orderd Rootes Tree Pohon berurut berakar adalah pohon berakar yang diberi label secara berurut dan sistematis, dimulai dari akar sebagai source/sumber/titik awal, semua cabang dari akar diberi nomor urut 1, 2, 3, ... sesuai dengan banyaknya cabang. Kemudian pada cabang 1 kita telusuri sampai ketemu anak cabang dan kita beri nomor ... sesuai banyaknya anak cabang. Demikian seterusnya sampai seluruh titik bernomor, sistem demikian disebut universal adress system. Teori Graph 167 Contoh 3 1 Gambar pohon berurut berakar di atas disebut Lexicographic order. Lexicographic order dapat digunakan untuk menggambarkan pernyataan aritmatika sebagai berikut Misalkan A + B x C – D/E +F akan kita gambar dalam bentuk Lexicographic maka pertama-tama harus kita tentukan dulu letak akar dengan cara mengikuti aturan urut-urutan hitung matematika yaitu x, /, +, –, sehingga pernyataan aritmatika di atas dapat ditulis kembali sebagai berikut A +B x C – D/E +F Sekarang dapat kita ambil titik akarnya yaitu operator – , ruas kiri dari operator – adalah cabang kiri dan ruas kanan dari operator – adalah cabang kanan. Langkah berikutnya kita cari titik anak cabang di ruas kiri, ternyata operator x, operators x memisahkan A + B di ruas kiri dan C di ruas kanan. Di ruas kiri operator x ada anak cabang terakhir, yaitu operator + yang memisahkan A di ruas kiri dan B di ruas kanan, cara yang sama berlaku juga untuk cabang sebelah kanan. 168 Matematika Diskrit – + x F C + A / B D E Setelah kita mampu menggambarkan pernyataan aritmatika dalam bentuk Lexicographic, selanjutnya kita belajar menuliskan pernyataan aritmatika tersebut dalam susunan Lukasiwicz, yaitu bentuk prefix dan postfix. Bentuk prefix adalah cara menuliskan pernyataan aritmatik dengan meletakkan simbol operator sebelum argumen, dimulai dari akar, ke cabang kiri, ke cabang kiri dan seterusnya sampai selesai baru pindah ke cabang kanan. Jadi bentuk prefix dari Lexicographic di atas adalah – x + ABC +/DEF Bentuk postfix adalah cara menulis pernyataan aritmatika dengan meletakkan simbol operator sesudah argumen atau dengan cara nulis dari sebelah kanan ke kiri seperti tulisan arab, dimulai dari akar, ke cabang kanan, ke cabang kanan dan seterusnya sampai selesai baru pindah ke cabang kiri. Jadi bentuk post fix dari Lexicographic di atas adalah AB + C x DE/F+- Teori Graph 169 SOAL-SOAL 1. Cari dan gambarkan spanning tree minimum dari graph di bawah 4 1 8 7 3 14 12 11 5 13 5 10 2 10 14 3 6 5 4 7 2 9 8 13 7 3 170 8 14 9 8 2 5 7 6 5 5 3 3 3 2 8 5 10 7 9 7 5 3 8 2 Matematika Diskrit 4 1 3 2 1 4 2 5 2 3 5 2 3 3 4 12 2 11 9 2 10 2 2 6 8 4 8 3 4 7 3 3 6 7 5 6 2. Gambarkanlah Lexicographic dari pernyataan aritmatika di bawah, kemudian tuliskan bentuk prefix dan postfixnya. a –7 + 6 x 3 – 4/2 + 5 – 2 b 5 x 4 x 3 x 2 – 7 + 3 x 5 – 6 c –3 x –5 / 5 – 3 + –3 x –8 + 6 – 2 x –1 + 3 d A x B – C / D + E + A – B – C – D x D / A + B + C + D 3. Gambarkan Lexicographic dari postfix form dibawah, kemudian tuliskan bentuk prefixnya. Teori Graph 171 a AB + CD x EF / – – D x b ABC x x CDA + / – c AB – C + DBCA – x – + d ABCDE + x – / 4. Gambarkan Lexicographic dari prefix form di bawah, kemudian tuliskan bentuk postfixnya. a + x – – x + x ABCBDC – E – C b + x – AB – x CB + x DC – E – C c – + x AB x CDA d – + x AB x CA + DE 5. Di suatu wilayah baru akan dibangun 9 sembilan pemukiman yang masing-masing dinamai P1, P2, P3, P4, P5, P6, P7, P8, dan P9. Selanjutnya akan dibangun jaringan jalan raya sebagai prasarana perhubungan antar daerah pemukiman itu. Hasil survei panjang jalan raya km yang harus dibangun tercantum dalam tabel berikut Daerah pemukiman P1 P2 P3 P4 P5 P6 P7 P1 0 P2 P3 P4 80 60 90 0 90 * 0 50 0 P5 * P6 120 P7 P8 * * * P9 * 110 * 160 70 * * * 80 70 * 100 * 0 * 60 140 * 0 * 80 * 0 100 50 0 70 P8 * * * berarti tidak mungkin dibuat jalan raya karena alasan geografis 172 Matematika Diskrit a Jika besarnya biaya pembangunan jaringan ini dianggap sebanding dengan panjang jalan raya yang akan dibangun, maka tentukn bentuk jaringan dengan biaya minimum agar tidak ada daerah pemukiman terpencil. b Tentukan panjang jalan raya total untuk kasus diatas. 6. Seorang ahli jaringan mendapat order membangun jaringan internet di gedung perkantoran 25 lantai dengan sistim kabel. Bila rancangan jaringan setiap lantai sama dan koneksi antar lantai memerlukan kabel sepanjang 5 m, berapa panjang kabel minimum yang harus disiapkan bila rancangan jaringan tiap lantai digambarkan dengan matrik titik di bawah, dimana elemen matrik menyatakan jarak antar terminal dalam meter. A B C A D E F G 7 10 15 12 B 8 9 13 10 C 8 11 14 9 D 7 E F G H I J 8 8 14 12 16 10 9 11 13 14 15 15 13 14 20 15 12 12 10 6 25 18 14 K L M N H 14 13 20 25 16 18 20 24 I 12 14 15 48 20 16 13 15 J 13 15 12 14 22 18 21 19 K 16 20 22 L 18 16 18 M 20 13 21 N 24 15 19 Teori Graph 173 7. Kerjakan seperti bila rancangan jaringan setiap lantai seperti matrik di bawah A A B B 13 8 15 G 8 10 6 10 G 6 8 I J K L M N O P 16 14 14 8 18 8 8 15 13 12 16 5 18 11 13 9 18 6 15 K 5 13 11 L M H 12 8 10 J F 10 F I E 15 8 D H D 13 C E C 13 9 18 N 14 11 15 18 6 10 10 11 10 P 10 12 15 10 14 O 10 5 5 12 18 -oo0oo- 174 Matematika Diskrit 9 MESIN MATEMATIKA PENDAHULUAN Dalam bab VII telah kita bahas tentang rangkaian logika dimana outputnya hanya tergantung pada inputnya, jadi dapat disimpulkan bahwa dalam rangkaian logika tidak ada memory. Dalam bab ini akan dibahas tentang rangkaian kombinasi yang outputnya tidak hanya tergantung dari input tetapi juga tergantung dari keadaan/state mesin pada waktu input data. Keadaan/state mesin sebelum kita input data ditentukan oleh proses data sebelumnya di dalam mesin tersebut. Dalam hal ini rangkaian kombinasi tersebut memiliki memory dan disebut mesin matematik. Naom Chomsky 1950 menciptakan model matematika sebagai sarana untuk mendeskripsikan bahasa serta untuk mencoba menjawab pertanyaan - pertanyaan − − − − apakah bahasa secara umum? bagaimana manusia mengembangkan bahasa? bagaimana manusia memahami bahasa? apa gagasan - gagasan yang dapat dinyatakan dan bagaimana caranya? Mesin Matematika 175 − bagaimana manusia membangun kalimat - kalimat dari gagasan gagasan yang berbeda dipikirannya? Naom Chomsky mengemukakan perangkat format yang disebut grammar untuk memodelkan properti - properti bahasa, grammar berisi sejumlah aturan yang menspesifikasikan bahasa tertentu, bahasa berisi semua string yang dapat dihasilkan dengan menggunakan aturan - aturan grammar. Grammar sangat bermanfaat bagi ilmu informatika / komputer, karena dengan grammar kita dapat mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa bahasa formal lainnya, merancang kompilator dan lain - lain, dengan bantuan mesin abstrak sederhana atau mesin matematika. Definisi mesin matematika ° Mesin matematika adalah model-model komputasi secara matematis. ° Mesin matematika adalah dasar-dasar dari komputer modern yang berfugsi untuk menjalankan program. ° Mesin matematika merupakan model komputasi yang dapat berfungsi sebagai acceptor dan tranducer sebagai acceptor artinya bila kita memberi input maka respon mesin tersebut menolak atau menerima. Contoh pemakaian dari mesin ini yaitu pada mesin ATM, ponsel ataupun PC ketika kita diminta memasukan nomer PIN/Password. Sebagai trasducer artinya bila kita memberi input maka mesin tersebut akan memberi outputan. Contoh Mesin penjumlah, inputannya dua bilangan dan outputnya jumlah kedua bilangan tersebut; vending machine, 176 Matematika Diskrit inputannya koin dan barang pilihan, outputannya berupa barang pilihan dan mungkin uang kembaliannya. FINITE STATE A UTOMATA FSA Ditinjau dari tingkat kesulitannya mesin matematika dibagi menjadi 3 kategori yaitu ° Finite Automata FA ° Push Down Automata PDA ° Turing Machine TM Dalam buku ini kita hanya akan membahas jenis yang paling mudah yaitu FA. Finite State Automata sering disebut Finite Automata adalah mesin abstrak berupa model metematika dengan masukan dan keluaran diskrit serta dapat mengenal bahasa paling sederhana bahasa regular. Finite Automata memiliki state yang banyaknya berhingga dan memiliki fungsi transisi yang mendeskripsikan perpindahan dari sebuah state ke state yang lain. Finite Automata tidak memiliki tempat penyimpanan sehingga kemampuan mengingatnya terbatas. Mekanisme kerja Finite Automata banyak diaplikasikan seperti pada − − − − − − − − Sistim elevator Mesin jaja Vending Mechine Pengatur lampu lalu lintas traffic light regulator Sirkuit penyaklaranswitching di komputer dan telekomunikasi Protokol komunikasi Analisis Leksikal Neuron Nets Pengecek parity perity checking Mesin Matematika 177 FA dapat digambarkan dalam 3 cara, yaitu ° Diagraph ° Notasi Formal 5 – tuple ° Tabel State Menggambarkan FA dengan Digraph Seperti telah dibahas dalam bab 8 bahwa graph adalah himpunan titik dan rusuk, maka menggambar FA dengan digraph berarti menggambarkan FA dengan titik dan rusuk berarah Titik menggambarkan state, yaitu state menerima ditandai dengan lingkaran ganda dan state menolak ditandai dengan lingkaran tunggal. Rusuk berarah menggambarkan transisi/perpindahan, bila pada state tertentu mendapat input tertentu maka pindah ke state yang ditunjuk oleh arah dari rusuk berarah. Label menggambarkan inputan yang diberikan pada state tertentu, rusuk berarah tanpa label menunjukkan di state mana pertamatama kita bekerja initial state. Contoh FA untuk parity cheking. Dalam media penyimpan data magnetik tape data sering digambarkan dalam barisan bilangan binary 0 dan 1 dalam sebuah frame. Sebuah frame terdiri dari 9 bits, dimana 8 bits menggambarkan data/karakter dan 1 bits di depan sebagai check bit. 0 check bit 0 1 0 0 1 0 0 1 data bits Sebuah frame dari tape dengan labeled bits 178 Matematika Diskrit Data bit dari frame diatas adalah 0 1 0 0 1 0 0 1 yang identik dengan 0 x 27 + 1 x 26 + 0 x 25 + 0 x 24 + 1 x 23 + 0 x 22 + 0 x 21 + 1 x 20 = 64 + 8 + 1 = 73. Check bit bernilai 0 bila jumlah bit ‘1’ dalam data bits berjumlah ganjil. Check bit bernilai 1 bila jumlah bit ‘1’ dalam data bits berjumlah genap. Bagai mana kita membuat FA dengan digraph sebagai model matematis untuk persoalan check bit ini? Pertama kita perhatikan state dalam persoalan check bit ini, ada 2 state yaitu jumlah bit ‘1’ ganjil dan genap. Jadi ada 2 buah titik yaitu titik ganjil dan genap. Langkah kedua kita tentukan state menerima dan state menolak, menerima ditandai dengan lingkaran ganda dan state menolak ditandai dengan lingkaran tunggal. Langkah ketiga kita identifikasi inputannya, inputnya 0 dan 1 artinya setiap state akan mendapat input 0 dan 1, bila mendapat input 0 akan bertransisi kemana dan bila dapat input 1 bertransisi kemana. Karena statenya hanya dua, maka transisi yang mungkin adalah transisi ke state yang lain atau kedirinya sendiri. Langkah keempat kita tentukan mulai dari mana kita masuk atau proses dimulai dari mana initial state ditandai dengan panah tanpa label. Jadi FA untuk odd parity adalah Even Star 1 S0 1 0 Mesin Matematika Odd S1 0 179 Untuk frame 0 0 1 0 0 1 0 0 1 Data Data Data Data Data Data Data Data Data pertama 0, So kedua 0, So ketiga 1, So keempat 0, S1 kelima 0, S1 keenam 1, S1 ketujuh 0, So kedelapan 0, So kesembilan 1, So transisi transisi transisi transisi transisi transisi transisi transisi transisi ke ke ke ke ke ke ke ke ke So So S1 S1 S1 So So So S1 Jadi data string tersebut berhenti pada lingkaran ganda artinya string tersebut diterima, dan paritynya benar berisi 0 jenis odd parity. Menggambarkan FA dengan definisi Formal 5-Tuple Dalam definisi formal FA dinotasikan dengan 5 tuple yaitu S, S, d, So dan A, dimana S S d S0 A adalah himpunan state- state adalah himpunan simbol-simbol input adalah fungsi transisi, contoh d S0,1 = S1 , artinya S0 mendapat input 1 bertransisi ke S1 adalah state awal initial state adalah himpunan state penerima accepting state Jadi masalah odd parity di atas dapat ditulis dengan definisi formal sebagai berikut 5 \5 5 ^ ¥ \ ^ 180 F 5 5 F 5  5 5 5 F 5 5 \5 ^ F 5  5 Matematika Diskrit Menggambarkan FA dengan Tabel State Menggambarkan FA dengan tabel state adalah membuat matrik dari FA tersebut, dimana baris menggambarkan transisi state dengan bermacam input dan kolom menunjukan transisi state dengan sebuah input. State menerima dibedakan dengan state menolak yaitu state menerima diberi tanda*. Jadi masalah odd parity diatas dapat digambarkan dengan tabel state sebagai berikut S0 S * 1 0 1 S0 S1 S1 S0 Non-Deterministik Finite Automata NFA Semua aturan yang berlaku dalam deterministric fininte automata atau sering disebut finite automata, berlaku juga dalam non-deterministic finite automata, bedanya NFA memberikan kemungkinan lebih dari satu transisi untuk setiap input yang kita berikan pada sebuah state. Latihan 1a. Gambarkanlah FA di bawah dengan tabel state dan definisi formal. 1b. Berikan masing-masing sebuah contoh string yang ditolak dan diterima oleh FA tersebut. 0 1 0 S0 S1 0 S1 1 1 Mesin Matematika 181 0 1 S0 S1 1 0 1 0 S2 1 0 1 S1 S0 1 S2 0 0 0 S0 S1 1 1 1 0 1 S2 0 S3 0 182 Matematika Diskrit 2a. Gambarkan kembali FA dalam bentuk tabel state di bawah dengan digraph dan definisi formal 2b. Berikan masing-masing sebuah contoh string yang ditolak dan diterima oleh FA tersebut. S0* S1 S2 0 1 S1 S2 S0 S0 S0 S2 S0* S1* S2 S3 S0* S1* S2 a b c S1 S0 S3 S1 S0 S3 S2 S0 S2 S0 S0 S1 0 1 S0 S0 S0 S1 S2 S1 3a. Gambarkanlah kembali FA dalam bentuk definisi formal di bawah dengan digraph dan tabel state 3b. Berikanlah masing-masing sebuah contoh string yang ditolak dan diterima oleh FA tersebut F 5 5 F 5 5 F 5  5 F 5  5 5 5 F 5 5 F 5 5 \5 ^ F 5  5 F 5  5 5 \5 5 5 5 5 ^ ¥ \^ F 5 5 F 5  5 5 \5 5 5 ^ ¥ \^ 5 5 \5 ^ Mesin Matematika F 5 5 F 5 5 F 5  5 F 5  5 F 5 5 F 5  5 183 F 5 5 F 5  5 F 5  5 F 5 5 5 5 F 5 5 F 5  5 \5 5 ^ F 5  5 F 5 5 F 5 5 F 5  5 5 \5 5 5 5 5 ^ ¥ \^ 4. Gambarkan kasus di bawah dengan diagraph finite automata Seorang pemburu ingin membawa seekor rusa hasil buruannya menyebrangi sebuah sungai, bersama pemburu itu juga dibawa seekor anjing pemburu dan seikat rumput untuk persediaan makanan sirusa, anjing dan rusa tidak bisa tinggal berdua demikian juga dengan kambing dan seikat rumput, sedangkan perahu yang tersedia hanya mampu membawa si pemburu dan salah satu bawaannya 5. Sebuah mesin jaja hanya dapat menerima inputan 500 rupiah dan 1000 rupiah, dan hanya dapat memberikan outputan sejenis barang senilai 2000 rupiah. Gambarkan finite state dengan segala kemungkinan input pada mesin jaja tersebut dengan diagraph, tabel state, dan definisi formal. 6. Sebuah mesin telepon koin hanya dapat menerima inputan koin 500 rupiah dan 1000 rupiah dan dapat memberi outputan durasi bicara 2 menit bila jumlah input 1000 rupiah 5 menit bila jumlah input 1500 rupiah 10 menit bila jumlah input 2000 rupiah Gambarkan dengan diagraph, tabel state, dan definisi formal finite state automata mesin telepon koin tersebut dengan segala kemungkinan input yang dapat terjadi, bila aturan mesin tersebut “pilih durasi bicara 184 Matematika Diskrit kemudian masukkan koin serta tidak ada uang kembali ” dengan diagraph, tabel state, dan definisi formal 7. Elevator Controller mempunyai tabel state sebagai berikut input State W1 wait on 1 U1 start up UP going up DN going down W2 wait on 2 D2 start down 0 W1 UP W2 W1 W2 DN 1 W1 U1 D2 W1 DN DN 2 UP UP W2 U1 W2 D2 gambarkan diagraph dan definisi formal dari elevator controller tersebut. Non-Deterministik Finite Automata NFA Semua aturan yang berlaku dalam deterministric fininte automata atau sering disebut finite automata, berlaku juga dalam non-deterministic finite automata, bedanya NFA memberikan kemungkinan lebih dari satu transisi untuk setiap input yang kita berikan pada sebuah state. Contoh 0, 1 0 S0 1 0, 1 Mesin Matematika S1 0 S2 S0* S1 S2 0 1 S1, S2 S2 S2 S2 S0 S2 185 Perhatikan NFA diatas, pada state So bila mendapat input 0, maka fungsi transisinya bisa ke S1 bisa ke S2 Bahasa/languages yang diterima oleh NFA tersebut adalah L M = {e, 0 1, 0 1 0 1, 0 1 0 1 0 1, ....} dimana e adalah empty string Difinisi Bila M adalah sebuah NFA, maka ada sebuah deterministik finite automata yang menerima LM dari NFA tersebut mesin ekivalen . Deterministic finite automata yang menerima L M dari NFA di atas adalah 1 0, 1 1 S0 0 S1 S2 1 0 0 1 S3 0 S4 Perhatikan FA di atas Empty string e diterima String 0 1 diterima String 0 1 0 1 diterima String 0 1 0 1 0 1 diterima dan seterusnya Jadi L M = {e, 0 1, 0 1 0 1, 0 1 0 1 0 1, .....} 186 Matematika Diskrit Latihan 1. Sebuah NFA digambarkan dengan diagraph dan tabel state sebagai berikut 1 0 0,1 S0 0 S0,S1 S0 S1* S1 1 1 S1 S0,S1 Gambarkanlah sebuah FA yang ekivalen dapat menerima bahasa yang sama dengan NFA diatas. 2. Kerjakan seperti unuk NFA 0 0,1 S0 S1 3. Kerjakan seperti unuk NFA 0 S0 1 S1 S2 0,1 0 4. Tentukan L M dari NFA di bawah kemudian buatlah sebuah FA yang menerima L M tersebut. e e 0 S0 S1 e S2 e 1 S3 0 1 Mesin Matematika S4 1 1 0 0 187 5. Gambarkan dengan digraph NFA yang dinyatakan dengan tabel di bawah, kemudian tuliskan kembali dengan definisi formal S0* S1 S2 S0* S1* S2 S0* S1 S2 S3 a b φ S1, S2 S0, S1 S2 S0 S0 S1* S2 S3 φ a b c S1 S0 S0, S1, S3 φ φ S2 S0 S0, S2 S0 a b c S1 S1, S3 S0, S1, S3 φ φ S0, S3 S1, S2 S0 φ φ φ φ a b φ S3 S3 S0, S1, S3 S1, S2 φ φ φ 6. Tentukan LM dari masing - masing NFA pada soal kemudian buatlah sebuah FA yang menerima LM dari NFA tersebut. 7. Tuliskan NFA pada soal nomer 4 kedalam bentuk definisi formal dan tabel state. 8. Buatlah FA untuk mengenal deklarasi ‘variable’ pada pascal. 9. Buatlah FA untuk mengenal identifier dalam Pascal/C seperti; Total, Sum1, Sum2, dan sebagainya. 188 Matematika Diskrit Finite State Transducers Seperti telah kita pelajari di atas bahwa output dari sebuah FA sangat terbatas, yaitu menerima atau menolak artinya sebuah string yang kita input kesebuah FA bisa diterima/accepted atau ditolak/rejected. Jadi walaupun FA sangat bermanfaat sebagai pengertian dasar dalam menganalisa bahasa, namun tidak dapat digunakan untuk menjelaskan suatu proses translasi dari satu bahasa ke bahasa yang lain. Sebuah FA dapat di modifikasi sehingga dapat berfungsi sebagai translator, FA yang demikian disebut Finite tranducer atau FA dengan output. Finite state transduser dapat digambarkan dengan ° digraph ° tabel state Menggambarkan finite state transducer dengan digraph Misalkan sebuah finite transducer akan mentranslasikan sebuah bahasa ke bahasa yang lain, katakanlah Bahasa asal 1101 Bahasa baru 1111011 artinya finite transducer tersebut akan menyisipi ‘1’ setiap dapat input ‘1’, maka kita dapat menggambarkan proses traslasi di atas dengan digraph, berikut 0/0 1/11 1/11 Start S0 0/0 S1 0/0 S2 1/11 Mesin Matematika 189 Perhatikan proses translasinya Start, So dapat input 1, outputnya 1 1, transisi ke S2 S2 dapat input 1, outputnya 1 1, transisi ke S2 S2 dapat input 0, outputnya 0, transisi ke S1 S1 dapat input 1, outputnya 1 1, transisi ke S2 Jadi string 1 1 0 1 diterima dan FA tersebut memberikan output 1 1 1 1 0 1 1. Menggambarkan finite state transducer dengan tabel Sama halnya dengan menggambarkan FA dengan tabel, menggambarkan funite state transducer dengan tabel hanya melakukan sedikit perubahan pada fungsi transisi d , dalam finite state transducer fungsi transisi ditambah dengan outputtan, seperti berikut. S0 S1* S2* 0 1 S1, 0 S1, 0 S1, 0 S2, 11 S2, 11 S2, 11 Latih 1. Buatlah sebuah finite state transducer yang mentranslasikan string 1 0 1 0 0 1 1 menjadi string 1 0 0 1 0 0 0 0 1 1 dalam bentuk digraph maupun table state 2. Buatlah sebuah finite trasducer yang mampu memberikan output hasil penjumlahan dua buah bilangan integer 5 1 0 1 dan 7 1 1 1. Perhatikan 190 0101 0111 + 1100 Matematika Diskrit dalam hal ini pada initial state input yang diberikan adalah 1 1 dan outputnya 0, input berikutnya adalah 0 1 atau 1 0 dan outputnya 0, input berikutnya adalah 1 1 dan outputnya 1, input terakhir adalah 0 0 dan outputnya 1. Jadi finite transducernya dapat digambarkan dengan digraph sebagai berikut. 00/0 Start 11/0 S0 00/1 S1 01, 10/0 01, 10/0 Start, 11/1 S1 dapat input 11, output 0, transisi ke S1 S1 dapat input 01, output 0, transisi ke S1 S1 dapat input 11, output1, transisi ke S1 S1 dapat input 00, output1, transisi ke S0 Jadi hasil akhir dari proses penjumlahan tersebut adalah 1100 2b. Kerjakan dengan cara yang sama untuk 8 + 9, 6 + 5, dan 7 +8 3. Buatlah sebuah finite transducer yang mampu memberikan output hasil pengurangan dua buah bilangan integer 14 – 5, 16 – 9 dan 15 - 7 4. Buatlah sebuah finite state transducer yang mampu mentranslasi bilangan berbasis 2 binary menjadi bilangan berbasis 4. -oo0oo- Mesin Matematika 191 192 Matematika Diskrit DAFTAR PUSTAKA Firrar Utdirartatmo, Teori Bahasa Dan Otomata, Graha Ilmu, Yogyakarta, Edisi 2,2005. Jonhsonbaugh, Ricard, Discrete Mathematics. Prentice Hall Int, New Jersey, 2001. Klin, George J dan Tina A. Folger, Fuzzy Sets, Uncertainty and Information, Prentice Hall Int, New Jersey, 1998. Klin, George J, Ute H. St Clair dan Bo Yuan, Fuzzy Sets Theory, Prentice Hall Int, 1997. Sri Kusumadewi, Hari Purnomo, Aplikasi Logika Fuzzy, Graha Ilmu,Yogyakarta, 2004. Sumarna, Elektronika Digital, Graha Ilmu, Yogyakarta, 2006. Witala, Stephen A. Discrete Mathematics A Unified Approach. Mc Graw Hill Int, Singapore, 1987. -oo0oo- Teori Himpunan Fuzzy 193 194 Matematika Diskrit 2 TENTANG PENULIS SAMUEL WIBISONO menyelesaikan pendidikan dasar dan menengahnya di Surakarta. Beliau menyelesaikan pendidikan di Akademi Meteorologi dan Geofisika Jakarta, serta lulus Jurusan Fisika Fakultas MIPA Universitas Indonesia, dan menyelesaikan Program Pasca-Sarjana bidang Optoelektronika dan Aplikasi Laser tahun 1997, di Universitas Indonesia. Sejak tahun 1983 beliau mengabdi di Badan Meteorologi dan Geofisika dan terakhir sebagai dosen di Pusdiklat Meteorologi dan Geofisika. Beliau juga mengampu mata kuliah Matematika Diskrit sejak tahun 1997 di berbagai universitas antara lain Universitas Bina Nusantara Jakarta, Universitas Indonesia Esa Unggul Jakarta, Universitas Kristen Krida Wacana, AMIK BK3 Tangerang. Teori Himpunan Fuzzy 195 196 Matematika Diskrit MatematikaSekolah Menengah Pertama terjawab Diantara 100 mahasiswa, 32 mahasiswa mempelajari matematika, 20 orang mempelajari fisika, 45 mahasiswa mempelajari biologi, 15 mahasiswa mempelajari matematika dan biologi, 7 mahasiswa mempelajari matematika dan fisika, 30 mahasiswa tidak mempelajari satupun dari ketiga bidang tersebut. a. 1. Hitunglah bilangan bulat 1 sampai 100 yang habis dibagi 3 atau 5! Jawab A=bilangan yg habis dibagi 3 nA= 100/3 = 33 B=bilangan yg habis dibagi 5 nB=100/5 = 20 nA ∪B=? nA ∪B= nA+nB-nA∩B nA∩B=100/3*5 = 100/15= 6 nA ∪B = 33+20-6 =42 Ada 47 bilangan yg habis dibagi 3 atau 5. Banyak yg tidak habis dibagi 3 atau 5? nS =100 nA ∪B = 47 nA ∪Bc =nS - nA ∪B = 100-47= 53 2. Diantara bilangan bulat 1 sampai 300, berapa banyak yang tidak habis dibagi 3 atau 5? Jawab A=bilangan yg habis dibagi 3 nA= 300/3 = 100 B=bilangan yg habis dibagi 5 nB=300/5 = 60 nA ∪B=? nA ∪B= nA+nB-n nA ∪B nA ∪B=300/3*5 = 300/15= 20 nA ∪B= 100+60-20 =140 Ada 140 bilangan yg habis dibagi 3 atau 5. Banyak yg tidak habis dibagi 3 atau 5? nS =300 nA ∪B= 140 nA ∪Bc =nS - nA ∪B = 300-140=260 3. Sebanyak 1232 orang mahasiswa mengambil kuliah bahasa Inggris, 879 bahasa Prancis dan 114 mengambil bahasa Jerman. Sebanyak 103 mengambil Inggris dan Prancis, 23 orang Inggris dan Jerman dan 14 orang mengambil Prancis dan Jerman. Jika 2092 orang mengambil paling sedikit satu mata kuliah Inggris, Prancis dan Jerman, berapa banyak yang mengambil katiganya? Rumus nI∪P∪J= nI+nP+nJ – nI∩P-nI∩J-nP∩J+nI∩P∩J jawab nI = 1232 nP = 879 nJ = 114 nI∩P=103 nI∩J=23 nP∩J=14 nI∪P∪J=2092 nI∩P∩J=? nI∪P∪J= nI+nP+nJ – nI∩P-nI∩J-nP∩J+nI∩P∩J 2092= 1232 + 879 + 114 – 103 – 23 – 14 + nI∩P∩J nI∩P∩J= 2092 – 2085 = 7 4. Diantara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari Fisika, 45 orang mempelajari Biologi, 15 orang mempelajari Matematika dan Biologi, 7 orang mempelajari Matematika dan Fisika, 10 orang mempelajari Fisika dan Biologi dan 30 orang tidak mempelajari satupun diantara tiga bidang tadi. Hitunglah banyaknya mahasiswa yang mempelajari ke tiga bidang tersebut dan diagram Vennya? nS = 100 nM = 32 nF = 20 nB = 45 nM∩F=7 nF∩B=10 nM∩B=15 nM∪F∪Bc = 30 nM∪F∪B=100-30=70 nM∩F∩B=? nM∪F∪B= nM+nF+nB – nM∩F-nM∩B-nM∩B+nM∩F∩B 70=32 +20 + 45 – 7 – 10 – 15 + nM∩F∩B nM∩F∩B= 70 – 65 = 55. A={1,2,3,4} R=x,y ∈ x2 ≥ y-2R={1,1,1,2,1,3 2,1,2,2,2,3,2,4 3,1,3,2,3,3,3,4 4,1,4,2,4,3,4,4}Selidiki apakah reflektif, transitif atau simetris?a. Reflektif a,a ∈R 1,1,2,2,3,3,4,4b. Simetris X a,b∈R →b,a∈R 4,1∈R→tetap 1,4∉Rc. Transitif a,b∈R dan b,c ∈R→a,c∈R 1,22,4→1,4∉R6. Ada 5 mahasiswa jurusan SI dan 7 mahasiswa jurusan TI. Berapa banyak cara membentuk panitia yang terdiri dari 4 orang jika a. Tidak ada batasan jurusanb. Semua harus dari SIc. Semua harus dari TId. 2 orang perjurusan Jawab a. 12 ∁ 4 = 12!/8!4! b. 5 ∁ 4 = 5!/4!1! c. 5 ∁ 4 = 5!/4!1! d. 5 ∁ 2 . 7 ∁ 2 = 5!/3!2! . 7!/5!2!7. Diperpustakaan TI terdapat 3 jenis buku Algoritma, diskret dan basis data. Perpustakaan paling sedikit memiliki 10 buku untuk masing” jenis. Berapa banyak cara memilih 10 buku? Gunakan rumus kombinasi dengan perulangan; ∁ n+r-1,r Jawab Kombinasi dg perulangan ada sebanyak n jenis dan masing” jenis terdiri dari 5 individu. n+r-r ∁r = ∁ n+r-1,r n = 3 r = 10 12 ∁ 10 = 12!/2!10! = 12x11/2 = 66 Untuk diagram Vennya belum,no 3 & 4.. Diantara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 mempelajari matematika dan biologi, 7 mempelajari dan fisika, 10 mempelajari fisikan dan biologi, dan 30 tidak mempelajari satu pun di antara ketiga bidang tersebut. SOAL MATEMATIKA DISKRIT Diantara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 orang mempelajari matematika dan biologi, 7 mempelajari matematika dan fisika, 10 mempelajari fisika dan biologi dan 30 tidak mempelajari satupun diantara ketiga bidang tersebut a. Hitunglah banyaknya mahasiswa yang mempelajari ketiga bidang tersebut b. Hitunglah banyaknya mahasiswa yang mempelajari hanya 1 diantara ketiga bidang tersebut.
Diantara100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 orang mempelajari matematika dan biologi, 7 mempelajari matematika dan fisika, 10 mempelajari fisika dan biologi dan 30 tidak mempelajari satupun diantara ketiga bidang tersebut a.
0% found this document useful 0 votes45 views4 pagesOriginal TitleLatihan Soal Matdis © All Rights ReservedAvailable FormatsDOCX, PDF, TXT or read online from ScribdShare this documentDid you find this document useful?0% found this document useful 0 votes45 views4 pagesLatihan Soal Matdis 2Original TitleLatihan Soal Matdis to Page You are on page 1of 4 You're Reading a Free Preview Page 3 is not shown in this preview. Reward Your CuriosityEverything you want to Anywhere. Any Commitment. Cancel anytime. LatihanSoal Matdis 2. 26. Di antara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 mempelajari matematika dan biologi, 7 mempelajari dan fisika, 10 mempelajari fisikan dan biologi, dan 30 tidak mempelajari satu pun di antara ketiga bidang tersebut. (a) Hitunglah banyaknya mahasiswa yang mempelajari ketiga bidang
diantara 100 mahasiswa, 54 mempelajari matrmatika,69 mempelajari sejarah ,dan 35 mempelajari keduanya. bila seorang mahasiswa di ambil secara acak, hitung peluang bahwa A. ia mempelajari matematika atau sejarah B. ia tidak mempelajari keduanya C. ia mempelajari matematika Yg mempelajari matematika saja = 54 - 35 = 19yg mempelajari sejarah saja = 69 - 35 = 34yg tidak mempelajari keduanya = 100 - 19 - 34 - 35 = 12A mempelajari matematika atau sejarah 19/100 + 34/100 = = 53/100B tidak keduanya = 12/100 = 6/50C matematika = 19/100

26 Di antara 100 mahasiswa, 32 orang mempelajari matematika, 20 orang mempelajari fisika, 45 orang mempelajari biologi, 15 orang mempelajari matematika dan biologi, 7 mempelajari matematika dan fisika, 10 mempelajari fisika dan biologi, dan 30 tidak mempelajari satupun dari ke tiga bidang tersebut. (a).

Tag Archives BUKU MATEMATIKADISKRIT RINALDI MUNIR S&"'"% N. 1 /+" "& &+ $"* 3 +%" T%& '$!" 5 6"%" $%$'", '" $&" T%& " $%!""% "!", "8", "&" &'"+ $%!""% ""$+"*, $%"" $ T%& 8"! '""& "'" $*9 /"6" P ; P5 &$%'% "&"= %" '" 5 6"&". T$%'""& 1 ""! " &% ' "&"%" "!!&" +* &$%$&. B$%"" "8"+ ?"%" $$&+ $" "&" 8"! &$%'% "&" 3 %" '" 3 6"&" $'$+" $!!" $"++" "*" "& '"% " "&" &% &, &$&" &'"+ +$'"8"9 /"6" S&"'"% Contoh soal beserta jawabannya .
  • aa0d6edcq5.pages.dev/899
  • aa0d6edcq5.pages.dev/94
  • aa0d6edcq5.pages.dev/862
  • aa0d6edcq5.pages.dev/90
  • aa0d6edcq5.pages.dev/921
  • aa0d6edcq5.pages.dev/844
  • aa0d6edcq5.pages.dev/483
  • aa0d6edcq5.pages.dev/598
  • aa0d6edcq5.pages.dev/950
  • aa0d6edcq5.pages.dev/271
  • aa0d6edcq5.pages.dev/13
  • aa0d6edcq5.pages.dev/4
  • aa0d6edcq5.pages.dev/829
  • aa0d6edcq5.pages.dev/23
  • aa0d6edcq5.pages.dev/230

    • diantara 100 mahasiswa 32 orang mempelajari matematika