induksi matematika - ee.unsoed.ac.idstwn/kul/tke132107/matdis-2013-5.pdf · matematika diskret...
Post on 14-Oct-2019
46 Views
Preview:
TRANSCRIPT
Tahun Ajaran 2013/2014
Induksi MatematikaMatematika Diskret (TKE132107)
Program Studi Teknik Elektro, Unsoed
Iwan Setiawan <stwn at unsoed.ac.id>
Ingat proposisi?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Sebuah proposisi mempunyai nilai.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Benar atau salah.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Perlu dibuktikan.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Metode pembuktian yang sahih.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pembuktian proposisi himpunan.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Pembuktian proposisi bilangan bulat.
Buktikan pernyataan “hasil penjum- lahan n buah bilangan bulat positif pertama adalah n(n+1)/2”!
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Metode pembuktian untuk proposisi perihal bilangan bulat disebut dengan Induksi
Matematika.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Teknik pembuktian yangbaku di dalam matematika.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Dalam pembuktian, kita ingin mencari mana teknik yang paling efisien/sangkil.
(dan tentu saja efektif/mangkus)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Dengan induksi matematika kita dapat melakukan pengurangan langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran melalui sejumlah langkah terbatas.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Postulat Peano.(aksioma: proposisi yang diasumsikan benar)
Proposisi PerihalBilangan Bulat
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Banyak hal terkait dengan bilangan bulat.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) benar untuk semua bilangan bulat positif n.
fungsi proposisi
p(n) adalah proposisi yang menya- takan “hasil penjumlahan bilangan bulat positif dari 1 sampai n adalah n(n+1)/2”.
Buktikan bahwa p(n) benar!
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Coba subtitusikan nilai n!
Apakah cara tersebut dapat membuktikan bahwa
p(n) benar?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Subtitusi langsung p(n) dengan n yang “dicoba-coba” tidak dapat disebut sebagai
pembuktian bahwa p(n) benar untuk seluruh n.
Temukan rumus hasil penjumlahan dari n buah bilangan ganjil
positif pertama!
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Coba subtitusikan nilai n dan simpulkan!
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Dugaan.
Apakah cara tersebut dapat membuktikan bahwa rumus
tersebut benar?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Contoh-contoh lainnya dapatdibaca pada buku referensi.
Prinsip InduksiSederhana
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) adalah proposisi perihal bilangan bulat positif, dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Prinsip Induksi Sederhana
1. p(1) benar, basis induksi;
2. Jika p(n) benar, p(n+1) juga benar untuk setiap n ≥ 1, langkah induksi;
sehingga p(n) benar untuk semua bilangan bulat positif n.
Hipotesis Induksi
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Basis induksi digunakan untuk memperlihatkan bahwa pernyataan tersebut benar jika n
diganti dengan elemen terkecil.(bilangan bulat positif terkecil)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kita harus memperlihatkan bahwaimplikasi p(n) → p(n+1) benar untuk
setiap bilangan bulat positif.
Bagaimana cara membuktikanimplikasi tersebut?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tunjukkan bahwa:jika p(n) benar, p(n+1) benar.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Tidak ada asumsi p(n) benaruntuk semua bilangan positif.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kita hanya memperlihatkan bahwa jika diasumsikan p(n) benar, maka p(n+1)
benar untuk setiap n positif.
Soham Banerjee, CC BY, http://flic.kr/p/tkDMw
Buktikan dengan induksi matematika bahwa 1 + 2 + 3 + … + n = n(n+1)/2, untuk n ≥ 1!
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) menyatakan proposisi tersebut.bahwa jumlah n bilangan bulat positif pertama adalah n(n+1)/2,
untuk n ≥ 1, yaitu 1 + 2 + 3 + … + n = n(n+1)/2
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Gunakan 2 langkah pembuktianprinsip induksi sederhana.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
1) basis induksi: p(1) benar, dengan n=1.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
2) langkah induksi:jika p(n) benar, p(n+1) juga benar.(hipotesis induksi)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
1 + 2 + 3 + … + n + (n + 1) = (n + 1)((n + 1) + 1)/2
Prinsip Induksiyang Dirampatkan
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Kita ingin membuktikan bahwa p(n) benaruntuk semua bilangan bulat yang
tidak dimulai dari 1 saja.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
≥ n0
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) adalah proposisi perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar
untuk semua bilangan bulat n ≥ n0.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Prinsip Induksi yang Dirampatkan
1. p(n0) benar;
2. Jika p(n) benar, p(n+1) juga benar untuk setiap n ≥ n0;
sehingga p(n) benar untuk semua bilangan bulat n ≥ n0.
Buktikan dengan induksi matematikabahwa 3n < n!, untuk n bilangan bulat
positif yang lebih besar dari 6.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) menyatakan proposisi tersebut.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
1) basis induksi: p(7); 37 < 7!.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
2) langkah induksi:jika p(n) benar, p(n+1) juga benar.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
3(n+1) < (n+1)!
Prinsip Induksi Kuat
Induksi kuat?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
p(n) adalah proposisi perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar
untuk semua bilangan bulat n ≥ n0.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Prinsip Induksi Kuat
1. p(n0) benar;
2. Jika p(n0), p(n0+1), …, p(n) benar, p(n+1) juga benar untuk setiap n ≥ n0;
sehingga p(n) benar untuk semua bilangan bulat n ≥ n0.
Hipotesis yang lebih banyak
Buktikan dengan induksi kuat bahwa setiap bilangan bulat positif n (n ≥ 2) dapat dinyatakan sebagai perkalian dari satu atau lebih bilangan prima!
Bilangan bulat positif disebut prima, jika dan hanya jika, bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri.
Bentuk InduksiSecara Umum
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Umum.
Generik?
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Dapat diterapkan dalamhimpunan obyek secara umum.
(tidak hanya pada proposisi himpunan bilangan bulat positif)
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Syarat: (1) himpunan obyek punya keterurutan,(2) mempunyai elemen terkecil.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Baca Definisi 4.1 pada buku referensi.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
X terurut dengan baik oleh “<” dan p(x) adalah pernyataan perihal elemen x dari X. Kita ingin
membuktikan bahwa p(x) benar untuksemua x ∈ X.
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Prinsip Induksi secara Umum
1. p(x0) benar;
2. Jika p(y) benar untuk y < x, p(x) juga benar untuk setiap x > x0 di dalam X;
sehingga p(x) benar untuk semua x ∈ X.
x0 adalah elemen terkecil di dalam X
Matematika Diskret (TKE132107) - Program Studi Teknik Elektro, Unsoed
Daftar Bacaan
● Munir, R. 2010. Matematika Diskrit, Revisi Keempat, Penerbit Informatika.
top related