Induksi Matematika

<div style="text-align: justify;">Dalam kasus diskrit kadang kala kita harus membuktikan bukan hanya satu atau beberapa pernyataan, tapi sampai tak berhingga pernyataan, tapi sampai tak berhingga pernyataan untuk bilangan asli. Induksi matematika merupakan teknik pembuktian yang sangat penting, dipergunakan secara luas untuk membuktikan pernyataan yang terkait dengan objek diskrit. Induksi matematika tidak dapat digunakan untuk menemukan rumus atau teorema, tetapi hanya untuk melakukan pembuktian dari teorema atau pernyataan tersebut sedemikian hingga berlaku untuk setiap bilangan asli (N).<br /><br />Misalkan P(n) adalah pernyataan tentang n. kita ingin membuktikan semua P(1), P(2), P(3), ….. P(n), … tidaklah praktis sebab untuk langkah ke-n tertentu pastilah ada langkah ke-(n+1) yang masih tersisa. Oleh sebab itu di perlukan suatu metode tersendiri.<br />Induksi matematika adalah cara standar dalam membuktikan bahwa sebuah pernyataan tertentu berlaku untuk setiap bilangan asli.<br /><br />Langkah langkah<br />Misalkan untuk setiap bilangan asli n kita mempunyai pernyataan P(n). pembuktian dengan induksi matematoika terdiri dari dua langkah yaitu:<br />1. Basis Induksi<br />Menunjukan bahwa pernyataan yang akan dibuktikan berlaku untuk bilangan dengan kata lain tunjukan bahwa P(1) benar.<br /><br />2. Langkah Induksi<br />Menunjukan bahwa jika pernyataan itu berlaku untuk bilangan n maka pernyataan itu juga berlaku untuk bilangan (n+1)<br />Caranya:<br />a. Asumsikan bahwa pernyataan tersebut benar untuk n=k P(k) untuk suatu k tertentu dalam kasus ini disebut hipotesa Induksi.<br />b. Tunjukan bahwa jika pernyataan tersebut benar untuk n=k, maka pernyataan tersebut juga benar untuk n=(k+1)<br />c. Dengan terbukti (a) dan (b) maka dengan induksi matematika dapat disimpilkan bahwa pernyataan tersebut berlaku untuk setiap bilangan asli n.<br /></div>

Induksi Matematika

Dalam kasus diskrit kadang kala kita harus membuktikan bukan hanya satu atau beberapa pernyataan, tapi sampai tak berhingga pernyataan, tapi...

Baca selengkapnya »

Teori Graf

<h2 style="text-align: justify;"><span class="mw-headline">Pendahuluan</span></h2><div style="text-align: justify;"> </div><p style="text-align: justify;">Di <a href="http://id.wikipedia.org/wiki/Matematika" title="Matematika">matematika</a> dan <a href="http://id.wikipedia.org/wiki/Ilmu_komputer" title="Ilmu komputer">ilmu komputer</a>, <b>teori graf</b> adalah cabang ilmu yang mempelajari sifat-sifat <a href="http://id.wikipedia.org/w/index.php?title=Graf&action=edit&redlink=1" class="new" title="Graf (belum dibuat)">graf</a>. Secara informal, suatu graf adalah himpunan benda-benda yang disebut <a href="http://id.wikipedia.org/w/index.php?title=Verteks&action=edit&redlink=1" class="new" title="Verteks (belum dibuat)">verteks</a> (atau <i>node</i>) yang terhubung oleh <i>edge</i>-<i>edge</i> (atau <i>arc</i>). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan <i>edge</i>).</p><div style="text-align: justify;"> </div><p style="text-align: justify;">Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada <a href="http://id.wikipedia.org/wiki/Friendster" title="Friendster">Friendster</a> bisa direpresentasikan dengan graf: verteks-verteksnya adalah para pemakai Friendster dan ada <i>edge</i> antara A dan B jika dan hanya jika A berteman dengan B. Perkembangan <a href="http://id.wikipedia.org/wiki/Algoritma" title="Algoritma">algoritma</a> untuk menangani graf akan berdampak besar bagi <a href="http://id.wikipedia.org/wiki/Ilmu_komputer" title="Ilmu komputer">ilmu komputer</a>.</p><div style="text-align: justify;"> </div><p style="text-align: justify;">Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap <i>edge</i>. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat <i>edge</i>nya berarah, yang secara teknis disebut <a href="http://id.wikipedia.org/w/index.php?title=Graf_berarah&action=edit&redlink=1" class="new" title="Graf berarah (belum dibuat)">graf berarah</a> atau <a href="http://id.wikipedia.org/w/index.php?title=Digraf&action=edit&redlink=1" class="new" title="Digraf (belum dibuat)">digraf</a> (<i>directed graph</i>). Digraf dengan <i>edge</i> berbobot disebut <a href="http://id.wikipedia.org/w/index.php?title=Jaringan_%28matematika%29&action=edit&redlink=1" class="new" title="Jaringan (matematika) (belum dibuat)">jaringan</a>.</p><div style="text-align: justify;"> </div><p style="text-align: justify;">Jaringan banyak digunakan pada cabang praktis teori graf yaitu <a href="http://id.wikipedia.org/w/index.php?title=Analisis_jaringan&action=edit&redlink=1" class="new" title="Analisis jaringan (belum dibuat)">analisis jaringan</a>. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).</p><h2 style="text-align: justify;"><span class="mw-headline">Sedikit lebih formal</span></h2><div style="text-align: justify;"> </div><p style="text-align: justify;">Suatu graph G dapat dinyatakan sebagai <span class="texhtml"><i>G</i> = < <i>V</i>,<i>E</i> ></span> . Graph G terdiri atas himpunan V yang berisikan verteks/node pada graph tersebut dan himpunan dari E yang berisi <i>edge</i> pada graph tersebut. Himpunan E dinyatakan sebagai pasangan dari verteks yang ada dalam V. Sebagai contoh definisi dari graf pada gambar diatas adalah : <span class="texhtml"><i>V</i> = {1,2,3,4,5,6}</span> dan <span class="texhtml"><i>E</i> = {(1,2),(1,5),(2,3),(3,4),(4,5),(5,2),(4,6)}</span></p> <p><br /></p> <div class="thumb tright"> <div class="thumbinner" style="width: 241px;"><a href="http://id.wikipedia.org/wiki/Berkas:Cesta_%28graf%29.svg" class="image" title="Gambar dengan node yang sama dengan yang diatas, tapi merupakan digraf."><img alt="" border="0" class="thumbimage" height="160" src="http://upload.wikimedia.org/wikipedia/commons/thumb/b/bd/Cesta_%28graf%29.svg/239px-Cesta_%28graf%29.svg.png" width="239" /></a> <div class="thumbcaption"><span style="font-size:78%;">Gambar dengan node yang sama dengan yang diatas, tapi merupakan digraf.</span></div> </div> </div> <p style="text-align: justify;">Pada <a href="http://id.wikipedia.org/w/index.php?title=Digraf&action=edit&redlink=1" class="new" title="Digraf (belum dibuat)">digraf</a> maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan <i>edge</i> sebagai berikut :</p><div style="text-align: justify;"> </div><p style="text-align: justify;"><span class="texhtml"><i>E</i> = { <> , <> , <> , <> , <> , <> , <> }</span></p><div style="text-align: justify;"> </div><p style="text-align: justify;">Dalam himpunan <i>edge</i> untuk digraf, urutan pasangan verteks menentukan arah dari <i>edge</i> tersebut.</p><div style="text-align: justify;"> </div><p style="text-align: justify;">Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :</p><div style="text-align: justify;"> </div><ul style="text-align: justify;"><li><i>Degree</i> atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.</li><li><i>Path</i> suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path <img alt=" b \rightarrow c \rightarrow g " class="tex" src="http://upload.wikimedia.org/math/d/6/3/d63998de5eb6a43e2c535815b7898e0d.png" /></li><li><i>Cycle</i> siklus ? path yang kembali melalui titik asal 2 <img alt=" f \rightarrow c \rightarrow d \rightarrow e " class="tex" src="http://upload.wikimedia.org/math/f/7/9/f792b9df357badf7c61037c39e8b1e7d.png" /> kembali ke 2.</li><li><i>Tree</i> merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex</li></ul>source:<br /><a href="http://id.wikipedia.org/wiki/Teori_graf">id.wikipedia.org</a>

Teori Graf

Pendahuluan Di matematika dan ilmu komputer , teori graf adalah cabang ilmu yang mempelajari sifat-sifat graf . Secara informal, suatu gr...

Baca selengkapnya »

Himpunan

Pengertian<br /><br />Himpunan adalah kumpulan objek-objek yang keanggotaannya didefinisikan dengan jelas.<br /><br />Contoh:<br /><br />* Himpunan siswi kelas III SMU Tarakanita tahun 1999-2000 yang nilai IQ-nya diatas 120.<br />* Himpunan bilangan-bilangan bulaT diantara 10 dan 500 yang habis dibagi 7<br /><br />Himpunan hanya membicarakan objek-objek yang berlainan saja.<br /><br />1. Metode Roster<br />yaitu dengan menuliskan semua anggota himpunan di dalam<br />tanda kurung {...........}<br />contoh: himpunan bilangan ganjil N = {1,3,5,7,9,.......}<br /><br />2. Metode Rule<br />yaitu dengan menyebutkan syarat keanggotaannya<br />contoh: N = {x½x adalah bilangan asli}<br /><br />3. Elemen (Anggota) notasi : Î<br />setiap unsur yang terdapat dalam suatu himpunan disebut<br />elemen/anggota himpunan itu.<br />contoh:<br />A ={a,b,c,d}<br />a Î A (a adalah anggota himpunan A)<br />e Ï A (e bukan anggota himpunan A)<br /><br /><span class="fullpost"><br />4. Himpunan kosong notasi : f atau {}<br />yaitu himpunan yang tidak mempunyai anggota<br />contoh :<br />A = { x | x² = -2; x riil}<br />A = f<br /><br /><br />5. Himpunan semesta notasi : S<br />yaitu himpunan yang memuat seluruh objek yang dibicarakan<br />contoh :<br />K = {1,2,3}<br />S = { x | x bilangan asli } atau<br />S = { x | x bilangan cacah } atau<br />S = { x | x bilangan positif } dsb.<br /><br />6. Himpunan bagian notasi : Ì atau É<br /><br />Himpunan A adalah himupnan bagian dari himpunan B, jika setiap anggota A adalah anggota B.<br /><br />Ditulis : A Ì Bf atau B É A<br /><br />contoh:<br />A={a,b}; B={a,b,c}; C={a,b,c,d}<br />maka A Ì B ; A Ì C ; B Ì C<br /><br />ketentuan :<br /><br />* himpunan kosong merupakan himpunan bagian dari sembarang<br />* himpunan ( f Ì A )himpunan A adalah himpunan bagian dari<br />* himpunan A sendiri ( A Ì A)jika anggota himpunan A ada sebanyak n, maka banyaknya himpunan bagian dari A adalah HB = 2n<br /><br />HB = 2n<br /><br />contoh:<br />jika A = {a,b,c}<br />maka himpunan bagian dari A adalah :<br />{a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} dan f<br /><br />seluruhnya ada 2³ = 8<br /><br />7. POWER SET 2s<br />himpunan yang elemennya adalah himpunan-himpunan bagian dari S<br /><br />contoh:<br />S = {a,b,c}<br />2s = { {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}, f }<br /><br /><br />8. Himpunan sama notasi : =<br /><br />Dua himpunan A dan B adalah sama, jika setiap elemen A adalah elemen B, dan setiap elemen B adalah elemen A.<br /><br />Ditulis A = B<br /><br />contoh:<br />K = {x | x²-3x+2=0}<br />L = {2,1}<br />maka K = L<br /><br /><br />9. Himpunan lepas notasi : //<br /><br />Dua himpunan A dan B disebut saling lepas, jika himpunan A tidak mempunyai anggota persekutuan dengan himpunan B.<br /><br />Ditulis A // B<br /><br />contoh:<br />A = {a,b,c}<br />B = {k,l,m}<br />Maka A // B<br /><br />10. Gabungan (union) notasi : È<br /><br />Gabungan dari dua himpunan A dan B adalah himpunan yang terdiri dari semua elemen yang menjadi anggota A atau menjadi anggota B.<br /><br />A È B = { x | x Î A atau x Î B }<br /><br /><br />Gbr. Diagram Venn<br />daerah yang diarsir menyatakan A È B<br /><br />contoh:<br />A = {1,2,3}<br />B = {0,2,4}<br />Maka A È B = {0,1,2,3,4}<br /><br /><br />11. Irisan (intersection) notasi : Ç<br /><br />Irisan dari dua himpunan A dan B adalah himpunan yang terdiri dari semua elemen persekutuan dari himpunan A dan B.<br /><br />A Ç B = { x | x Î A dan x Î B }<br /><br /><br />Gbr. Diagram Venn<br />daerah yang diarsir menyatakan A Ç B<br /><br />contoh:<br />A={1,2,3,4}<br />B={3,4,5}<br />maka A Ç B = {3,4}<br /><br /><br />12. Selisih notasi : -<br /><br />Selisih antara dua himpunan A dan B adalah himpunan yang terdiri dari semua anggota A yang bukan anggota B.<br /><br />A - B = { x | x Î A dan x Ï B }<br /><br /><br />Gbr. Diagram Venn<br />daerah yang diarsir menyatakan A - B<br /><br />contoh:<br />A = {1,2,3,4,5}<br />B = {2,4,6,7,10}<br />Maka A - B = {1,3,5}<br /><br />_<br />13. Komplemen notasi: A', Ac, A<br /><br />Komplemen dari himpunan A adalah himpunan yang terdiri dari semua anggota himpunan S yang bukan anggota A.<br /><br />A' = { x | x Î S dan x Ï A }<br /><br /><br />Gbr. Diagram Venn<br />daerah yang diarsir menyatakan A'<br /><br />contoh:<br />S = {1,2,3,4,5,6,7,8,9,10}<br />A = {1,2,3,4,5}<br />Maka A' = {6,7,8,9,10}<br /><br /><br />14. Komutatif<br /><br />A Ç B = B Ç A<br />A È B = B È A<br /><br /><br />15. Asosiatif<br /><br />A Ç (B Ç C) = (A Ç B) Ç C<br />A È (B È C) = (A È B) È C<br /><br /><br />16. Distributif<br /><br />A Ç (B È C) = (A Ç B) È (A Ç C)<br />A È (B Ç C) = (A È B) Ç (A È C)<br /><br /><br /><br />17. De Morgan ____ _ _<br />(A È B)= A Ç B<br />____ _ _<br />(A Ç B)= A È B<br /><br /><br /><br />Jika n menyatakan banyaknya anggota himpunan, maka berlaku hubungan :<br /><br />2 HIMPUNAN<br />____<br />n(s) = n (A È B) + n (A È B)<br /><br /><br />3 HIMPUNAN<br />________<br />n(S) = n (A È B È C) + (A È B È C)<br /><br />di mana<br /><br />n (A È B) = n (A) + n (B) - n (A Ç B)<br /><br />n (A È B È C) = n (A) + n (B) + n (C) - n (A Ç B) - n (A Ç C) - n (B Ç C) + n (A Ç B Ç C)<br /><br />18. Himpunan bilangan asli<br />Himpunan bilangan asli adalah himpunan bilangan yang anggota-anggotanya merupakan bilangan bulat positif.<br /><br />N = {1,2,3,4,5,6,......}<br /><br />19. Himpunan bilangan prima<br />Himpunan bilangan prima adalah himpunan bilangan-bilangan asli yang hanya dapat dibagi dirinya sendiri dan satu, kecuali angka 1.<br /><br />P = {2,3,5,7,11,13,....}<br /><br />20. Himpunan bilangan cacah<br />Himpunan bilangan cacah adalah himpunan bilangan yang anggota-anggotanya merupakan bilangan bulat positif digabung dengan nol.<br /><br />C = {0,1,2,3,4,5,6,....}<br /><br />21. Himpunan bilangan bulat<br />Himpunan bilangan bulat adalah himpunan bilangan yang anggota-anggotanya seluruh bilangan bulat, baik negatif, nol, dan positif.<br /><br />B = {...,-3,-2,-1,0,1,2,3,...}<br /><br />22. Himpunan bilangan rasional<br />Himpunan bilangan rasional adalah himpunan bilangan yang anggota-anggonya merupakan bilangan yang dapat dinyatakan sebagai:<br />p/q dimana p,q Î bulat dan q ¹ 0 atau dapat dinyatakan sebagai suatu desimal berulang.<br /><br />contoh: 0,-2, 2/7, 5, 2/11, dan lain lain<br /><br />23. Himpunan bilangan irasional<br />Himpunan bilangan irasional adalah himpunan bilangan yang anggota-anggotanya tidak dapat dinyatakan sebagai sebagai p/q atau tidak dapat dinyatakan sebagai suatu desimal berulang.<br /><br />contoh: log 2, e, Ö7<br /><br />24. Himpunan bilangan riil<br />Himpunan bilangan riil adalah himpunan yang anggota-anggotanya merupakan gabungan dari himpunan bilangan rasional dan irasional.<br /><br />contoh: log 10, 5/8, -3, 0, 3<br /><br />25. Himpunan bilangan imajiner<br />Himpunan bilangan imajiner adalah himpunan bilangan yang anggota-anggotanya merupakan i (satuan imajiner) dimana i merupakan lambang bilangan baru yang bersifat i² = -1<br /><br />contoh: i, 4i, 5i<br /><br />26. Himpunan bilangan kompleks<br />Himpunan bilangan kompleks adalah himpunan bilangan yang anggota-anggotanya (a + bi) dimana a, b Î R, i² = -1, dengan a bagian riil dan b bagian imajiner.<br /><br />contoh: 2-3i, 8+2<br /><br />source:<br /><a href="http://bebas.vlsm.org/v13/Sponsor/_Sponsor-Pendamping/Praweda/Matematika/0355%20Mat%201-1a.htm">http://bebas.vlsm.org</a><br /></span>

Himpunan

Pengertian Himpunan adalah kumpulan objek-objek yang keanggotaannya didefinisikan dengan jelas. Contoh: * Himpunan siswi kelas III SMU Tarak...

Baca selengkapnya »

Teka Teki Matematika (pendeta dan kanibal)

<div style="text-align: justify;"> Ini merupakan jenis soal metode diskrit yang diajarkan oleh dosen saya. soalnya gampang dimengerti, biasa seperti soal matematika yang lain soalnya memang gampang untuk dimengerti tapi sulit untuk di jawab atau di selesaikan. ini adalah salah satu contoh soalnyaada 3 orang pendeta dan 3 orang kanibal yang hendak menyebrang sungai. tetapi perahu yang digunakan hanya cukup untuk menampung 2 orang. bisa keduanya pendeta, atau keduanya kanibal atau mungkin pendeta dan kanibal, tetapi</div> <br /> <span class="fullpost"><span class="fullpost">ada beberapa persyaratan yang harus di penuhi untuk mngangkut semua pendeta dan kanibal yaitu tidak boleh jumlah pendeta lebih sedikit dari jumlah kanibal yang tersisa atau yang sudah berangkat, pertanyaannya bagaimana caranya agar ketiga pendeta tersebut selamat sampai ke seberang sungai? </span></span><br /> <br /> <span class="fullpost"><span class="fullpost"><b><a href="http://matematikakuadrat.blogspot.com/2008/12/game-game-yang-berhubungan-dengan.html">KLIK DISINI</a>  </b>untuk memainkan gamenya, selamat mencoba..</span></span>

Teka Teki Matematika (pendeta dan kanibal)

Ini merupakan jenis soal metode diskrit yang diajarkan oleh dosen saya. soalnya gampang dimengerti, biasa seperti soal matematika yang lain...

Baca selengkapnya »

Pigeon Hole (sarang merpati)

<div style="text-align: justify;">Jika (k + 1) atau lebih obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut.<br /></div><div style="text-align: justify;"><br />Contoh 1: Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali.<br /><br /><div style="text-align: justify;">Contoh 2: Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, maka haruslah terdapat paling sedikit satu hari ketika anda menghadiri paling sedikit dua kelas.<br /></div></div><div style="text-align: justify;"><br />Jika N obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat sedikitnya N/k obyek.<br /><span class="fullpost"><br />Bukti?<br /><br />Contoh 1: Di dalam kelas dengan 60 mahasiswa, terdapat paling sedikit 12 mahasiswa akan mendapat nilai yang sama (A, B, C, D, atau E).</span><br /><br />Contoh 2: Di dalam kelas dengan 61 mahasiswa, paling sedikit 13 mahasiswa akan memperoleh nilai yang sama.<br /><br />Misalkan ada laci yang berisi selusin kaus kaki coklat dan selusin kaus kaki hitam yang didistribusikan secara acak. Pada saat listrik padam, berapa kaus kaki yang harus anda ambil untuk memastikan bahwa di antaranya terdapat sepasang kaus yang sewarna?<br /><br /><br />Terdapat dua tipe kaus kaki, jadi jika anda memilih paling sedikit 3 kaus kaki, haruslah terdapat paling sedikit dua kaus kaki coklat atau paling sedikit dua kaus kaki hitam .<br /><br />Generalisasi Prinsip Sarang Merpati : 3/2 = 2.<br /></div>

Pigeon Hole (sarang merpati)

Jika (k + 1) atau lebih obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebu...

Baca selengkapnya »