Matematika SMA/MA/SMK/MAK
Bukti Tidak Langsung
(Pembuktian dengan Kontradiksi & Kontraposisi)
A. Pengertian Bukti Tidak Langsung
Dalam logika matematika, bukti tidak langsung (indirect proof) adalah metode pembuktian suatu pernyataan matematika yang tidak membuktikan secara langsung kebenaran pernyataan tersebut, melainkan menggunakan pendekatan lain untuk menunjukkan kebenarannya.
Terdapat dua jenis bukti tidak langsung:
- Bukti dengan Kontradiksi (Proof by Contradiction)
- Bukti dengan Kontraposisi (Proof by Contrapositive)
Perbedaan Bukti Langsung dan Tidak Langsung:
| Aspek | Bukti Langsung | Bukti Tidak Langsung |
|---|---|---|
| Pendekatan | Membuktikan p → q secara langsung | Membuktikan melalui kontradiksi atau kontraposisi |
| Langkah Awal | Asumsikan p benar, tunjukkan q benar | Asumsikan negasi dari kesimpulan |
| Kapan Digunakan | Hubungan p dan q jelas | Sulit membuktikan langsung |
B. Bukti dengan Kontradiksi
Pertanyaan: Bagaimana cara membuktikan suatu pernyataan jika kita tidak bisa membuktikannya secara langsung?
🧠 MenalarPrinsip Kontradiksi
Untuk membuktikan pernyataan P benar dengan kontradiksi:
- Asumsikan negasi dari P benar (anggap ~P benar)
- Lakukan penalaran logis berdasarkan asumsi tersebut
- Tunjukkan bahwa penalaran tersebut menghasilkan kontradiksi (bertentangan dengan fakta, aksioma, atau teorema yang sudah diketahui)
- Simpulkan bahwa asumsi ~P salah, sehingga P benar
Skema Logis:
Jika ~P menghasilkan kontradiksi, maka P benar.
Secara simbolis: (~P → F) ⟹ P bernilai benar
(F = kontradiksi/falsum)
Contoh Klasik: Membuktikan √2 Irasional
Pernyataan: √2 adalah bilangan irasional.
Bukti (dengan kontradiksi):
- Asumsikan √2 rasional, maka √2 = a/b dengan a, b bilangan bulat, b ≠ 0, dan FPB(a, b) = 1
- Kuadratkan kedua ruas: 2 = a²/b², sehingga a² = 2b²
- Ini berarti a² genap, sehingga a genap. Tulis a = 2k
- Substitusi: (2k)² = 2b² → 4k² = 2b² → b² = 2k²
- Ini berarti b² genap, sehingga b genap
- Kontradiksi! Baik a dan b genap, bertentangan dengan FPB(a, b) = 1
- Jadi asumsi salah, √2 adalah bilangan irasional. ∎
C. Bukti dengan Kontraposisi
Untuk membuktikan pernyataan p → q dengan kontraposisi:
- Ingat bahwa p → q ekuivalen dengan ~q → ~p (kontraposisinya)
- Buktikan kontraposisinya: asumsikan ~q benar, lalu tunjukkan ~p benar
- Jika kontraposisi terbukti, maka pernyataan asli p → q juga terbukti
Tabel Kebenaran Ekuivalensi:
| p | q | p → q | ~q | ~p | ~q → ~p |
|---|---|---|---|---|---|
| B | B | B | S | S | B |
| B | S | S | B | S | S |
| S | B | B | S | B | B |
| S | S | B | B | B | B |
Kolom p → q dan ~q → ~p selalu sama → ekuivalen!
Contoh: Bukti dengan Kontraposisi
Pernyataan: Jika n² genap, maka n genap.
Bukti (kontraposisi):
Kontraposisi: “Jika n ganjil, maka n² ganjil.”
- Asumsikan n ganjil, maka n = 2k + 1 untuk suatu bilangan bulat k
- n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
- Karena n² = 2m + 1 dengan m = 2k² + 2k, maka n² ganjil
- Kontraposisi terbukti, jadi pernyataan asli benar. ∎
D. Langkah-Langkah Sistematis
Langkah Bukti Kontradiksi:
- Tuliskan pernyataan yang akan dibuktikan
- Asumsikan negasi pernyataan tersebut benar
- Gunakan penalaran logis dari asumsi
- Temukan kontradiksi
- Simpulkan pernyataan awal benar
Langkah Bukti Kontraposisi:
- Tuliskan pernyataan p → q
- Bentuk kontraposisi ~q → ~p
- Asumsikan ~q benar
- Tunjukkan ~p benar
- Simpulkan p → q terbukti
Kapan Menggunakan Masing-Masing?
| Gunakan Kontradiksi Ketika | Gunakan Kontraposisi Ketika |
|---|---|
| Pernyataan bukan berbentuk implikasi | Pernyataan berbentuk p → q |
| Membuktikan eksistensi/ketidakmungkinan | Lebih mudah bekerja dari ~q ke ~p |
| Contoh: “√2 irasional” | Contoh: “Jika n² genap maka n genap” |
E. Contoh Soal: Bukti Kontradiksi
● Soal Mudah (1-5)
Soal 1:
Buktikan dengan kontradiksi bahwa tidak ada bilangan bulat terbesar.
Pembahasan:
- Asumsikan ada bilangan bulat terbesar, sebut N
- Perhatikan bilangan N + 1
- N + 1 adalah bilangan bulat (penjumlahan dua bilangan bulat)
- N + 1 > N, ini kontradiksi dengan asumsi N terbesar
- Jadi tidak ada bilangan bulat terbesar. ∎
Soal 2:
Buktikan dengan kontradiksi: Jika n bilangan bulat dan n² ganjil, maka n ganjil.
Pembahasan:
- Asumsikan n² ganjil tetapi n genap (negasi kesimpulan)
- Jika n genap, maka n = 2k
- n² = (2k)² = 4k² = 2(2k²) → n² genap
- Kontradiksi! n² tidak bisa ganjil sekaligus genap
- Jadi jika n² ganjil maka n ganjil. ∎
Soal 3:
Buktikan dengan kontradiksi bahwa jumlah bilangan rasional dan irasional adalah irasional.
Pembahasan:
- Misalkan r rasional dan s irasional
- Asumsikan r + s = t rasional
- Maka s = t – r
- Karena t rasional dan r rasional, maka t – r rasional
- Kontradiksi! s seharusnya irasional
- Jadi r + s irasional. ∎
Soal 4:
Buktikan dengan kontradiksi: Jika 3n + 2 ganjil, maka n ganjil.
Pembahasan:
- Asumsikan 3n + 2 ganjil tetapi n genap
- Jika n genap, maka n = 2k
- 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)
- Maka 3n + 2 genap
- Kontradiksi dengan premis 3n + 2 ganjil
- Jadi jika 3n + 2 ganjil maka n ganjil. ∎
Soal 5:
Buktikan dengan kontradiksi bahwa jika a × b = 0 maka a = 0 atau b = 0.
Pembahasan:
- Asumsikan a × b = 0 tetapi a ≠ 0 dan b ≠ 0
- Karena a ≠ 0, kita bisa membagi kedua ruas dengan a
- b = 0/a = 0
- Kontradiksi dengan asumsi b ≠ 0
- Jadi a = 0 atau b = 0. ∎
● Soal Sedang (6-10)
Soal 6:
Buktikan dengan kontradiksi bahwa √3 adalah bilangan irasional.
Pembahasan:
- Asumsikan √3 rasional, maka √3 = a/b dengan FPB(a,b) = 1
- Kuadratkan: 3 = a²/b² → a² = 3b²
- a² habis dibagi 3, maka a habis dibagi 3. Tulis a = 3k
- Substitusi: 9k² = 3b² → b² = 3k²
- b² habis dibagi 3, maka b habis dibagi 3
- Kontradiksi! a dan b sama-sama habis dibagi 3, bertentangan dengan FPB = 1
- Jadi √3 irasional. ∎
Soal 7:
Buktikan dengan kontradiksi: Tidak ada bilangan rasional r yang memenuhi r² = 6.
Pembahasan:
- Asumsikan ada r = a/b rasional dengan FPB(a,b) = 1 dan r² = 6
- Maka a²/b² = 6 → a² = 6b²
- a² habis dibagi 2, sehingga a genap. Tulis a = 2m
- 4m² = 6b² → 2m² = 3b²
- 3b² genap → b² genap → b genap
- Kontradiksi dengan FPB(a,b) = 1
- Jadi √6 irasional. ∎
Soal 8:
Buktikan dengan kontradiksi: Jika a dan b bilangan bulat dengan a² – 4b – 2 = 0, maka a ganjil.
Pembahasan:
- Asumsikan a genap, maka a = 2k
- Substitusi: (2k)² – 4b – 2 = 0
- 4k² – 4b – 2 = 0
- 2(2k² – 2b – 1) = 0
- 2k² – 2b – 1 = 0 → 2k² – 2b = 1
- Ruas kiri genap, ruas kanan ganjil. Kontradiksi!
- Jadi a ganjil. ∎
Soal 9:
Buktikan dengan kontradiksi: Jika n³ + 5 ganjil, maka n genap.
Pembahasan:
- Asumsikan n³ + 5 ganjil tetapi n ganjil
- Jika n ganjil, n = 2k+1
- n³ = (2k+1)³ = 8k³ + 12k² + 6k + 1 (ganjil)
- n³ + 5 = ganjil + 5 = ganjil + ganjil = genap
- Kontradiksi! n³ + 5 seharusnya ganjil
- Jadi n genap. ∎
Soal 10:
Buktikan dengan kontradiksi: Jika p bilangan prima dan p | a², maka p | a.
Pembahasan:
- Asumsikan p | a² tetapi p tidak membagi a
- Karena p prima dan p ∤ a, maka FPB(p, a) = 1
- Dari Lemma Euclid: jika p | (a × a) dan FPB(p, a) = 1, maka p | a
- Kontradiksi dengan asumsi p ∤ a
- Jadi jika p | a² maka p | a. ∎
● Soal Sulit (11-15)
Soal 11:
Buktikan dengan kontradiksi bahwa terdapat tak berhingga banyak bilangan prima.
Pembahasan (Bukti Euclid):
- Asumsikan hanya ada berhingga bilangan prima: p₁, p₂, …, pₙ
- Bentuk bilangan N = p₁ × p₂ × … × pₙ + 1
- N > 1, jadi N memiliki faktor prima (bisa dirinya sendiri)
- Misalkan p faktor prima dari N. Maka p = pᵢ untuk suatu i
- pᵢ | N dan pᵢ | (p₁ × p₂ × … × pₙ)
- Maka pᵢ | (N – p₁ × p₂ × … × pₙ) = 1
- Kontradiksi! Tidak ada prima yang membagi 1
- Jadi ada tak berhingga bilangan prima. ∎
Soal 12:
Buktikan dengan kontradiksi bahwa log₂ 3 adalah bilangan irasional.
Pembahasan:
- Asumsikan log₂ 3 rasional, maka log₂ 3 = p/q dengan p, q bulat positif
- Dari definisi logaritma: 2^(p/q) = 3
- Pangkatkan dengan q: 2^p = 3^q
- Ruas kiri genap (pangkat dari 2), ruas kanan ganjil (pangkat dari 3)
- Kontradiksi! Bilangan genap tidak bisa sama dengan bilangan ganjil
- Jadi log₂ 3 irasional. ∎
Soal 13:
Buktikan dengan kontradiksi: Jika a + b > 100, maka a > 50 atau b > 50.
Pembahasan:
- Asumsikan a + b > 100 tetapi a ≤ 50 dan b ≤ 50
- Dari asumsi: a + b ≤ 50 + 50 = 100
- Jadi a + b ≤ 100
- Kontradiksi dengan premis a + b > 100
- Jadi a > 50 atau b > 50. ∎
Soal 14:
Buktikan dengan kontradiksi: Tidak ada bilangan bulat n yang memenuhi n² + n + 1 ≡ 0 (mod 4).
Pembahasan:
- Asumsikan ada n bulat sehingga n² + n + 1 ≡ 0 (mod 4)
- Kasus 1: n genap, n = 2k → 4k² + 2k + 1 ≡ 2k + 1 (mod 4)
- Jika k genap: 2k + 1 ≡ 1 (mod 4) ≠ 0
- Jika k ganjil: 2k + 1 ≡ 3 (mod 4) ≠ 0
- Kasus 2: n ganjil, n = 2k+1 → 4k²+4k+1+2k+1+1 ≡ 2k+3 (mod 4)
- Jika k genap: 2k+3 ≡ 3 (mod 4) ≠ 0. Jika k ganjil: 2k+3 ≡ 1 (mod 4) ≠ 0
- Semua kasus memberikan kontradiksi. Jadi tidak ada n yang memenuhi. ∎
Soal 15:
Buktikan dengan kontradiksi: Jika x dan y bilangan real dengan x + y = 2, maka x ≤ 1 atau y ≤ 1.
Pembahasan:
- Asumsikan x + y = 2 tetapi x > 1 dan y > 1
- Dari asumsi: x + y > 1 + 1 = 2
- Jadi x + y > 2
- Kontradiksi dengan x + y = 2
- Jadi x ≤ 1 atau y ≤ 1. ∎
F. Contoh Soal: Bukti Kontraposisi
● Soal Mudah (1-5)
Soal 1:
Buktikan dengan kontraposisi: Jika n² genap, maka n genap.
Pembahasan:
- Kontraposisi: “Jika n ganjil, maka n² ganjil”
- Misalkan n ganjil, maka n = 2k + 1
- n² = (2k+1)² = 4k² + 4k + 1 = 2(2k²+2k) + 1
- n² berbentuk 2m+1, jadi ganjil
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 2:
Buktikan dengan kontraposisi: Jika n² > 9, maka n > 3 (untuk n bilangan asli).
Pembahasan:
- Kontraposisi: “Jika n ≤ 3, maka n² ≤ 9“
- Misalkan n ≤ 3 (n bilangan asli, jadi n = 1, 2, atau 3)
- Karena n ≤ 3 dan n > 0, maka n² ≤ 3² = 9
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 3:
Buktikan dengan kontraposisi: Jika xy ganjil, maka x ganjil.
Pembahasan:
- Kontraposisi: “Jika x genap, maka xy genap”
- Misalkan x genap, maka x = 2k
- xy = 2k × y = 2(ky)
- xy genap (kelipatan 2)
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 4:
Buktikan dengan kontraposisi: Jika n + 1 > 4, maka n > 3.
Pembahasan:
- Kontraposisi: “Jika n ≤ 3, maka n + 1 ≤ 4“
- Misalkan n ≤ 3
- Tambah 1 kedua ruas: n + 1 ≤ 3 + 1 = 4
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 5:
Buktikan dengan kontraposisi: Jika 5n + 1 genap, maka n ganjil.
Pembahasan:
- Kontraposisi: “Jika n genap, maka 5n + 1 ganjil”
- Misalkan n = 2k
- 5n + 1 = 5(2k) + 1 = 10k + 1 = 2(5k) + 1
- 5n + 1 ganjil
- Kontraposisi terbukti → pernyataan asli benar. ∎
● Soal Sedang (6-10)
Soal 6:
Buktikan dengan kontraposisi: Jika n³ + 1 genap, maka n ganjil.
Pembahasan:
- Kontraposisi: “Jika n genap, maka n³ + 1 ganjil”
- Misalkan n = 2k
- n³ = (2k)³ = 8k³ (genap)
- n³ + 1 = 8k³ + 1 = 2(4k³) + 1 (ganjil)
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 7:
Buktikan dengan kontraposisi: Untuk bilangan real, jika x² + y² = 0 maka x = 0 dan y = 0.
Pembahasan:
- Kontraposisi: “Jika x ≠ 0 atau y ≠ 0, maka x² + y² ≠ 0“
- Misalkan x ≠ 0 (kasus y ≠ 0 serupa)
- Maka x² > 0 (kuadrat bilangan real tak nol selalu positif)
- Karena y² ≥ 0, maka x² + y² > 0 ≠ 0
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 8:
Buktikan dengan kontraposisi: Jika 3n + 7 genap, maka n ganjil.
Pembahasan:
- Kontraposisi: “Jika n genap, maka 3n + 7 ganjil”
- Misalkan n = 2k
- 3n + 7 = 3(2k) + 7 = 6k + 7 = 6k + 6 + 1 = 2(3k+3) + 1
- 3n + 7 ganjil
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 9:
Buktikan dengan kontraposisi: Jika n² – 2n + 7 genap, maka n ganjil.
Pembahasan:
- Kontraposisi: “Jika n genap, maka n² – 2n + 7 ganjil”
- Misalkan n = 2k
- n² – 2n + 7 = 4k² – 4k + 7 = 4k² – 4k + 6 + 1 = 2(2k²-2k+3) + 1
- Hasilnya ganjil
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 10:
Buktikan dengan kontraposisi: Jika ab ganjil, maka a ganjil dan b ganjil.
Pembahasan:
- Kontraposisi: “Jika a genap atau b genap, maka ab genap”
- Kasus 1: a genap, a = 2k → ab = 2kb genap ✓
- Kasus 2: b genap, b = 2m → ab = 2am genap ✓
- Kedua kasus menghasilkan ab genap
- Kontraposisi terbukti → pernyataan asli benar. ∎
● Soal Sulit (11-15)
Soal 11:
Buktikan dengan kontraposisi: Jika n² – 1 tidak habis dibagi 3, maka n habis dibagi 3.
Pembahasan:
- Kontraposisi: “Jika n tidak habis dibagi 3, maka n² – 1 habis dibagi 3″
- Jika n tidak habis dibagi 3, maka n = 3k+1 atau n = 3k+2
- Kasus 1: n = 3k+1 → n²-1 = 9k²+6k+1-1 = 3(3k²+2k) ✓
- Kasus 2: n = 3k+2 → n²-1 = 9k²+12k+4-1 = 9k²+12k+3 = 3(3k²+4k+1) ✓
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 12:
Buktikan dengan kontraposisi: Untuk bilangan bulat positif, jika 2^n – 1 prima, maka n prima.
Pembahasan:
- Kontraposisi: “Jika n bukan prima (komposit), maka 2^n – 1 bukan prima”
- Jika n komposit, maka n = ab dengan 1 < a, b < n
- Gunakan identitas: x^(ab) – 1 = (x^a – 1)(x^(a(b-1)) + x^(a(b-2)) + … + 1)
- Maka 2^n – 1 = 2^(ab) – 1 habis dibagi 2^a – 1
- Karena 1 < a < n, maka 1 < 2^a – 1 < 2^n – 1
- 2^n – 1 memiliki faktor selain 1 dan dirinya → bukan prima
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 13:
Buktikan dengan kontraposisi: Jika a² + b² ganjil, maka a dan b tidak sama paritas (satu genap satu ganjil).
Pembahasan:
- Kontraposisi: “Jika a dan b sama paritas, maka a² + b² genap”
- Kasus 1: Keduanya genap. a=2m, b=2n → a²+b² = 4m²+4n² = 2(2m²+2n²) genap ✓
- Kasus 2: Keduanya ganjil. a=2m+1, b=2n+1
- a²+b² = 4m²+4m+1+4n²+4n+1 = 2(2m²+2m+2n²+2n+1) genap ✓
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 14:
Buktikan dengan kontraposisi: Jika n² ≡ 1 (mod 4), maka n ganjil.
Pembahasan:
- Kontraposisi: “Jika n genap, maka n² ≢ 1 (mod 4)“
- Misalkan n = 2k
- n² = 4k² ≡ 0 (mod 4)
- 0 ≠ 1, jadi n² ≢ 1 (mod 4)
- Kontraposisi terbukti → pernyataan asli benar. ∎
Soal 15:
Buktikan dengan kontraposisi: Jika x³ + x > 0, maka x > 0 (untuk x bilangan real).
Pembahasan:
- Kontraposisi: “Jika x ≤ 0, maka x³ + x ≤ 0“
- Misalkan x ≤ 0
- Faktorkan: x³ + x = x(x² + 1)
- x ≤ 0 dan x² + 1 > 0 (selalu positif)
- Maka x(x² + 1) ≤ 0 (negatif × positif = negatif atau nol)
- Kontraposisi terbukti → pernyataan asli benar. ∎
G. Latihan Soal
Kerjakan soal-soal berikut tanpa melihat pembahasan. Tentukan metode bukti tidak langsung yang tepat (kontradiksi atau kontraposisi) dan buktikan!
● Soal Mudah (1-5)
● Soal Sedang (6-10)
● Soal Sulit (11-15)
H. Ringkasan
| Metode | Ide Utama | Langkah Kunci |
|---|---|---|
| Kontradiksi | Asumsikan negasi, temukan pertentangan | ~P → Kontradiksi → P benar |
| Kontraposisi | Buktikan bentuk ekuivalen ~q → ~p | p→q ≡ ~q→~p |