06

Teknik pembuktian

06 · Himpunan, logika & diskrit9 menit · Menengah

Menguji banyak contoh tidak pernah cukup untuk membuktikan pernyataan tentang semua bilangan. Pembuktian adalah argumen yang berlaku untuk seluruh kasus sekaligus, dan hanya ada beberapa bentuk baku yang perlu dikuasai.

Lihat dulu

LIHAT DULU

Dua langkah yang menjangkau semuanya

Induksi tidak memeriksa setiap bilangan satu per satu. Ia memeriksa yang pertama, lalu menunjukkan bahwa satu kasus menyeret kasus berikutnya.

1 + 3 + 5 + … + (2n − 1) = n²yang dibuktikan
n = 1  →  ruas kiri 1, ruas kanan 1basis benar
andaikan benar untuk ndipakai di langkah berikutnya
tambahkan 2(n + 1) − 1 = 2n + 1suku berikutnya
n² + 2n + 1 = (n + 1)²tepat bentuk untuk n + 1
berlaku untuk setiap bilangan asli nselesai
6
6/6
Basis tanpa langkah induksi tidak membuktikan apa pun, dan sebaliknya. Keduanya harus dikerjakan.

Konsep

Bukti langsung

Mulai dari yang diketahui, lalu melangkah menuju yang ingin dibuktikan, dengan setiap langkah punya alasan. Contohnya, jumlah dua bilangan genap selalu genap: tulis keduanya sebagai 2m dan 2n, jumlahnya 2(m + n), dan bentuk itu memang bentuk bilangan genap.

Kontraposisi

Membuktikan “jika P maka Q” sama dengan membuktikan “jika bukan Q maka bukan P”. Kadang arah kedua jauh lebih mudah. Pernyataan “jika n² ganjil maka n ganjil” lebih sulit dibuktikan langsung daripada kontraposisinya.

Kontradiksi

Andaikan yang ingin dibuktikan itu salah, lalu turunkan akibat yang mustahil. Bukti bahwa akar dua bukan bilangan rasional bekerja begitu: andaikan ia rasional, tulis sebagai pecahan paling sederhana, dan kedua bilangan itu ternyata harus genap, padahal pecahannya sudah paling sederhana.

Induksi matematika

Dipakai untuk pernyataan yang berlaku bagi setiap bilangan asli. Buktikan benar untuk n = 1, lalu buktikan bahwa kalau benar untuk sembarang n maka benar juga untuk n + 1. Kedua langkah itu bersama-sama menjangkau semua bilangan asli, seperti deretan kartu domino yang saling menjatuhkan.

Rumus yang dipakai

Kontraposisi
(P → Q) ≡ (bukan Q → bukan P)

Kedua pernyataan itu setara nilainya.

Langkah induksi
P(1) benar  dan  P(n) → P(n + 1)

Basis dan langkah induksi harus keduanya dikerjakan.

Jumlah n bilangan ganjil pertama
1 + 3 + 5 + … + (2n − 1) = n²

Contoh klasik untuk induksi.

Jumlah n bilangan asli pertama
1 + 2 + … + n = n(n + 1)2

Sering dipakai sebagai langkah bantu.

Contoh pengerjaan

Induksi untuk jumlah bilangan ganjil

Buktikan bahwa 1 + 3 + 5 + … + (2n − 1) = n² untuk setiap bilangan asli n.

  1. Basis: untuk n = 1, ruas kiri 1 dan ruas kanan 1² = 1, jadi benar.
  2. Andaikan benar untuk n: 1 + 3 + … + (2n − 1) = n².
  3. Tambahkan suku berikutnya, yaitu 2(n + 1) − 1 = 2n + 1, ke kedua ruas.
  4. Ruas kirinya menjadi n² + 2n + 1.
  5. Bentuk itu sama dengan (n + 1)², tepat bentuk yang diharapkan untuk n + 1.
  6. Basis dan langkah induksi keduanya berhasil, jadi pernyataannya benar untuk semua bilangan asli.

JawabanTerbukti dengan induksi matematika

Poin penting

  • Contoh yang banyak tetap bukan bukti, sedangkan satu contoh penyangkal sudah cukup membantah.
  • Kontraposisi membalik sekaligus menegasikan kedua bagian pernyataan.
  • Kontradiksi bekerja dengan menurunkan akibat yang mustahil.
  • Induksi butuh dua langkah: basis dan langkah induksi.

Latihan singkat

Apa yang cukup untuk membantah pernyataan “semua bilangan prima itu ganjil”?