METODE PEMBUKTIAN DAN INDUKSI MATEMATIKA DALAM MATEMATIKA DISKRIT

RANGKUMAN
PEMBUKTIAN TRIVIAL
Dalam pembuktian ini kita harus bisa menunjukkan nilai pernyataan q benar untuk semua bilangan real termasuk nilai p.Sehingga kita berhasil menunjukkan kebenaran implikasi p⇒q.
PEMBUKTIAN LANGSUNG
Dalam pembuktian ini,kita harus tahu terlebih dahulu apa yang diketahui dan apa yang akan dibuktikan.Karena pernyataan yang diketahui sudah benar sehingga kita hanya menunjukkan pernyataan q nya juga benar.Apabila q sudah benar,otomatis implikasi p ⇒q terbukti.
PEMBUKTIAN BERDASARKAN KASUS KASUS
Dalam metode pembuktian ini ,kita akan membuktikan implikasi dari bentuk 〖(p〗_1˅〖 p〗_2˅…˅〖 p〗_n)⇒q dengan tautologi ditulis[(p_(2 )˅ p_(2 )˅… ˅ p_(n ) )⇒q]⇔[(p_1⇒q)∧(p_(2 )⇒q)∧… ∧(p_n⇒q)]dapat digunakan aturan penyimpulan .Itu dapat ditunjukkan dengan membuktikan setiap n implikasi p_i⇒q,dengan i = 1,2,3,…,n secara masing-masing.
PEMBUKTIAN EKUIVALENSI
Metode pembuktian ini merupakan pembuktian teorema berbentuk biimplikasi p ⇔ q dengan p dan q adalah pernyataan.Pernyataan p ⇔ q ekuivalen dengan [(p ⇒q)∧(q ⇒p) ].Jika dapat membuktikan pernyataan p⇒q dan q⇒p benar,maka implikasi p⇔q juga akan benar.
PEMBUKTIAN TIDAK LANGSUNG
1.pembuktian dengan kontradiksi Jika ada teorema implikasi p⇒q, maka kita buktikan implikasi tersebut dengan mengandaikan negasi pernyataan q benar (-q benar),sampai dihasilkan suatu pernyataan yang kontradiksi atau bertentangan dengan pernyataan yang diketahui.Sehingga pengandaian –q tersebut adalah salah dan benar adalah pernyataan q.Karena q benar otomatis implikasi p ⇒ q terbukti benar.
2.pembuktian dengan kontraposisi, Implikasi p⇒q ekuivalen dengan kontraposisi –q ⇒ -p.Dalam pembuktian ini terlebih dahulu kita membuktikan pernyataan -q⇒-p benar,maka implikasi p⇒q juga pasti akan benar.
INDUKSI MATEMATIKA
Induksi matematika merupakan teknik pembuktian yang baku di dalam matematika.
Melalui induksi matematik kita dapat
mengurangi langkah-langkah pembuktian bahwa semua bilangan bulat termasuk ke dalam suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.
Induksi Sederhana
Misalkan p(n) adalah pernyataan perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.Untuk membuktikan pernyataan ini,kita hanya perlu menunjukkan bahwa:
1.p(1) benar,dan
2.jika p(n)benar maka p(n+1) juga benar,untuk semua bilangan bulat positif n≥1,
Induksi yang Dirampatkan
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥n_0.Untuk membuktikan ini,kita hanya perlu menunjukkan bahwa:
1.p(n_0) benar, dan
2.jika p(n) benar maka p(n+1) juga benar ,untuk semua bilangan bulat n≥n_0,
Induksi Kuat
Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat n≥n_0.Untuk membuktikan ini ,kita hanya perlu menunjukkan bahwa:
1.p(n_0) benar, dan
2.jika p(n_0),p(n_0+1),…,p(n) benar maka p(n+1) juga benar untuk semua bilangan bulat n≥n_0