Pembuktian Dengan Kontrapositif

Salah satu metode pembuktian dalam matematika adalah pembuktian dengan kontrapositif. Pembuktian dengan kontrapositif adalah salah satu metode pembuktian tidak langsung selain pembuktian dengan kontradiksi. Pembuktian dengan kontrapositif ini didasarkan pada nilai kebenaran pernyataan “jika P maka Q” ekivalen dengan “jika bukan Q maka bukan P”. Jadi, yang perlu kita lakukan untuk membuktikan suatu implikasi dengan kontrapositif adalah dengan menegasikan konklusinya, kemudian tunjukkan bahwa negasi dari konklusi mengakibatkan negasi dari antisedennya.

Contoh : Buktikan jika dan adalah genap, maka n adalah genap!
Bukti : Pernyataan pada contoh di atas jika dinyatakan dalam simbol logika adalah dengan P : dan adalah genap dan Q : n adalah genap. Yang harus dilakukan adalah menegasikan Q dengan baik, yaitu n adalah ganjil.
Karena n ganjil, maka n dapat dinyatakan sebagai berikut
untuk semua

Kemudian dengan memisalkan maka untuk semua . Ini Berarti adalah bilangan ganjil.

pembuktian tak langsung dengan kontradiksi

Pembuktian tak langsung dengan kontradiksi

Matematika adalah sebuah studi mengenai keterkaitan antar objek. Matematika juga dikenal sebagai ilmu yang mempunyai kerangka berpikir deduktif, tidak induktif. Artinya, dari suatu hal yang bersifat umum menuju khusus. Akibatnya, dalam matematika tidak diperkenankan untuk melakukan generalisasi. Contohnya, perhatikan beberapa data di bawah.

1+3=5

3+5=8

5+7=12

7+9=16

9+11=20

Dari data di atas, kita lihat bahwa jika bilangan ganjil ditambah bilangan ganjil, akan menghasilkan bilangan genap. Namun dalam matematika tidak diperbolehkan mengatakan penjumlahan dua bilangan ganjil menghasilkan bilangan genap hanya berdasarkan data di atas. Satu-satunya cara adalah dengan pembuktian.

Apa itu pembuktian? Dalam matematika, pembuktian adalah kegiatan seseorang untuk meyakinkan sesuatu itu benar melalui langkah-langkah logis. Untuk menunjukkan sesuatu itu salah, cukup menunjukkan countre example, yaitu menunjukkan bahwa ada satu keadaan dimana suatu pernyataan tidak berlaku.

Ada berbagai macam teknik pembuktian dalam matematika. Ditinjau dari caranya, ada dua jenis pembuktian, yaitu pembuktian langsung dan pembuktian tak langsung. Untuk pembuktian tidak langsung sendiri ada dua cara, yaitu dengan kontradiksi dan kontrapositif. Namun kali ini yang akan saya bahas cuma pembuktian dengan kontradiksi. Ok, apa itu pembuktian dengan kontradiksi? Perhatikan contoh berikut.

Ketika Budi sedang asik membaca di kamar, tiba-tiba listrik di rumah Budi mati. Budi ingin tahu apakah yang mati cuma listrik di rumahnya atau memang mati dari pusat. Kemudian ia melihat keluar jendela. Ternyata listrik rumah di sekitar rumah Budi hidup. Lalu ia menyimpulkan bahwa yang mati hanya listrik di rumahnya.

Dari contoh di atas terliggat bahwa untuk membuktikan bahwa hanya listrik di rumah Budi yang mati, ia harus mengecek listrik di rumah sekitarnya. Artinya, perlu pemisalan negasi dari pernyataan yang ingin dibuktikan, yaitu misalkan tidak benar bahwa listrik yang mati hanya di rumah Budi. Dengan kata lain pemadaman listrik terjadi dari pusat. Akibatnya, rumah di sekitar Budi juga listriknya harus mati. Ternyata ketika ia melihat keluar jendela, listrik di sekitar rumah Budi masih hidup. Berarti hanya rumah anda yang listriknya mati. Keadaan ini yang disebut kontradiksi.

Dalam ilmu logika, jika pernyataan yang ingin dibuktikan berbentuk implikasi p à q, maka yang harus dibuktikan adalah q. Untuk membuktikan dengan kontradiksi, kita harus memisalkan ~q. kemudian perlihatkan bahwa ~q bertentangan dengan p. Contoh di atas, jika kita misalkan p : listrik mati dari pusat dan q : listrik rumah sekitar Budi mati, maka akan membentuk pernyataan implikasi p à q, yaitu “jika listrik mati dari pusat, maka listrik rumah sekitar Budi mati”. Tapi ternyata yang terjadi adalah ~q, yaitu listrik sekitar rumah Budi tidak mati. Jadi kesimpulannya adalah ~p, yaitu listrik tidak mati dari pusat.

Berikut ini adalah contoh pembuktian dengan kontradiksi dalam konteks matematika. Pembuktian ini mungkin yang paling sering dijadikan contoh pembuktian dengan kontradiksi.

1. Buktikan bahwa adalah irrasional.

Bukti :

Andaikan adalah rasional, maka dapat dinyatakan sebagai dengan p,q€Z dan p dan q relative prima. Kuadratkan kedua ruas, didapat

Karena adalah genap, maka juga genap dan juga p genap. Akibatnya p=2r, r€Z.

src="http://latex.codecogs.com/gif.latex?{p^{2}}" title="{p^{2}}" />

persamaan terakhir mengatakan bahwa q juga merupakan bilangan kelipatan 2. Berarti, p dan q sama-sama mempunyai factor kelipatan selain 1. Akibatnya p dan q tidak relative prima. Ini kontradiksi dengan pernyataan bahwa p dan q relative prima. Jadi, haruslah irrasional.

Induksi Matematika

Induksi Matematika (IM) adalah suatu metode/cara pembuktian (cara langsung) pernyataan matematika yang berkaitan dengan himpunan bilangan asli (N). IM didasari oleh sifat himpunan bilangan asli,yaitu sifat terurut sempurna.

Sifat terurut sempurna ini secara garis besar menyatakan bahwa tiap himpunan bagian dari himpunan bilangan asli selalu mempunyai unsur terkecil.

Proses IM
Misalkan S himpunan bagian dari N dan S tidak kosong.Jika S memenuhi sifat - sifat sbb:
(i) 1 € S.
(ii) Jika k € S maka (k+1) € S.
Maka S=N.

Bukti :
Andaikan S tidak sama dengan N,artinya N-S tidak kosong,artinya N-S punya unsur terkecil,katakanlah m. (m-1) bukan anggota N-S,berarti (m-1) anggota S. Berdasarkan (i) dan (ii) jika (m-1) anggota S,maka (m-1+1) anggota S atau m anggota S.Ini kontradiksi dengan m anggota N-S.Maka haruslah S=N.

Versi lain IM
misal P(n) suatu pernyataan yang berkaitan dengan bilangan asli n€N. Jika P(n) memenuhi kondisi berikut :
(i) P(1) benar.
(ii) Jika P(k) benar,maka P(k+1) benar.
Maka P(n) benar untuk setiap n€N.

Untuk contoh dari IM,akan saya postingkan lain waktu.
Terima kasih.
:)