Bukti Tidak Langsung – Logika Matematika

Matematika SMA/MA/SMK/MAK

Bukti Tidak Langsung

(Pembuktian dengan Kontradiksi & Kontraposisi)

📖 Mengamati

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:

  1. Bukti dengan Kontradiksi (Proof by Contradiction)
  2. 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
❓ Menanya

B. Bukti dengan Kontradiksi

Pertanyaan: Bagaimana cara membuktikan suatu pernyataan jika kita tidak bisa membuktikannya secara langsung?

🧠 Menalar

Prinsip Kontradiksi

Untuk membuktikan pernyataan P benar dengan kontradiksi:

  1. Asumsikan negasi dari P benar (anggap ~P benar)
  2. Lakukan penalaran logis berdasarkan asumsi tersebut
  3. Tunjukkan bahwa penalaran tersebut menghasilkan kontradiksi (bertentangan dengan fakta, aksioma, atau teorema yang sudah diketahui)
  4. 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)

🔬 Mencoba

Contoh Klasik: Membuktikan √2 Irasional

Pernyataan: √2 adalah bilangan irasional.

Bukti (dengan kontradiksi):

  1. Asumsikan √2 rasional, maka √2 = a/b dengan a, b bilangan bulat, b ≠ 0, dan FPB(a, b) = 1
  2. Kuadratkan kedua ruas: 2 = a²/b², sehingga a² = 2b²
  3. Ini berarti genap, sehingga a genap. Tulis a = 2k
  4. Substitusi: (2k)² = 2b²4k² = 2b²b² = 2k²
  5. Ini berarti genap, sehingga b genap
  6. Kontradiksi! Baik a dan b genap, bertentangan dengan FPB(a, b) = 1
  7. Jadi asumsi salah, √2 adalah bilangan irasional. ∎
🧠 Menalar

C. Bukti dengan Kontraposisi

Untuk membuktikan pernyataan p → q dengan kontraposisi:

  1. Ingat bahwa p → q ekuivalen dengan ~q → ~p (kontraposisinya)
  2. Buktikan kontraposisinya: asumsikan ~q benar, lalu tunjukkan ~p benar
  3. 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!

🔬 Mencoba

Contoh: Bukti dengan Kontraposisi

Pernyataan: Jika genap, maka n genap.

Bukti (kontraposisi):

Kontraposisi: “Jika n ganjil, maka ganjil.”

  1. Asumsikan n ganjil, maka n = 2k + 1 untuk suatu bilangan bulat k
  2. n² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
  3. Karena n² = 2m + 1 dengan m = 2k² + 2k, maka ganjil
  4. Kontraposisi terbukti, jadi pernyataan asli benar. ∎
📢 Mengkomunikasikan

D. Langkah-Langkah Sistematis

Langkah Bukti Kontradiksi:

  1. Tuliskan pernyataan yang akan dibuktikan
  2. Asumsikan negasi pernyataan tersebut benar
  3. Gunakan penalaran logis dari asumsi
  4. Temukan kontradiksi
  5. Simpulkan pernyataan awal benar

Langkah Bukti Kontraposisi:

  1. Tuliskan pernyataan p → q
  2. Bentuk kontraposisi ~q → ~p
  3. Asumsikan ~q benar
  4. Tunjukkan ~p benar
  5. 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:

  1. Asumsikan ada bilangan bulat terbesar, sebut N
  2. Perhatikan bilangan N + 1
  3. N + 1 adalah bilangan bulat (penjumlahan dua bilangan bulat)
  4. N + 1 > N, ini kontradiksi dengan asumsi N terbesar
  5. Jadi tidak ada bilangan bulat terbesar. ∎

Soal 2:

Buktikan dengan kontradiksi: Jika n bilangan bulat dan ganjil, maka n ganjil.

Pembahasan:

  1. Asumsikan ganjil tetapi n genap (negasi kesimpulan)
  2. Jika n genap, maka n = 2k
  3. n² = (2k)² = 4k² = 2(2k²) genap
  4. Kontradiksi! tidak bisa ganjil sekaligus genap
  5. Jadi jika ganjil maka n ganjil. ∎

Soal 3:

Buktikan dengan kontradiksi bahwa jumlah bilangan rasional dan irasional adalah irasional.

Pembahasan:

  1. Misalkan r rasional dan s irasional
  2. Asumsikan r + s = t rasional
  3. Maka s = t – r
  4. Karena t rasional dan r rasional, maka t – r rasional
  5. Kontradiksi! s seharusnya irasional
  6. Jadi r + s irasional. ∎

Soal 4:

Buktikan dengan kontradiksi: Jika 3n + 2 ganjil, maka n ganjil.

Pembahasan:

  1. Asumsikan 3n + 2 ganjil tetapi n genap
  2. Jika n genap, maka n = 2k
  3. 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)
  4. Maka 3n + 2 genap
  5. Kontradiksi dengan premis 3n + 2 ganjil
  6. 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:

  1. Asumsikan a × b = 0 tetapi a ≠ 0 dan b ≠ 0
  2. Karena a ≠ 0, kita bisa membagi kedua ruas dengan a
  3. b = 0/a = 0
  4. Kontradiksi dengan asumsi b ≠ 0
  5. Jadi a = 0 atau b = 0. ∎

● Soal Sedang (6-10)

Soal 6:

Buktikan dengan kontradiksi bahwa √3 adalah bilangan irasional.

Pembahasan:

  1. Asumsikan √3 rasional, maka √3 = a/b dengan FPB(a,b) = 1
  2. Kuadratkan: 3 = a²/b²a² = 3b²
  3. habis dibagi 3, maka a habis dibagi 3. Tulis a = 3k
  4. Substitusi: 9k² = 3b²b² = 3k²
  5. habis dibagi 3, maka b habis dibagi 3
  6. Kontradiksi! a dan b sama-sama habis dibagi 3, bertentangan dengan FPB = 1
  7. Jadi √3 irasional. ∎

Soal 7:

Buktikan dengan kontradiksi: Tidak ada bilangan rasional r yang memenuhi r² = 6.

Pembahasan:

  1. Asumsikan ada r = a/b rasional dengan FPB(a,b) = 1 dan r² = 6
  2. Maka a²/b² = 6a² = 6b²
  3. habis dibagi 2, sehingga a genap. Tulis a = 2m
  4. 4m² = 6b²2m² = 3b²
  5. 3b² genap → genap → b genap
  6. Kontradiksi dengan FPB(a,b) = 1
  7. Jadi √6 irasional. ∎

Soal 8:

Buktikan dengan kontradiksi: Jika a dan b bilangan bulat dengan a² – 4b – 2 = 0, maka a ganjil.

Pembahasan:

  1. Asumsikan a genap, maka a = 2k
  2. Substitusi: (2k)² – 4b – 2 = 0
  3. 4k² – 4b – 2 = 0
  4. 2(2k² – 2b – 1) = 0
  5. 2k² – 2b – 1 = 02k² – 2b = 1
  6. Ruas kiri genap, ruas kanan ganjil. Kontradiksi!
  7. Jadi a ganjil. ∎

Soal 9:

Buktikan dengan kontradiksi: Jika n³ + 5 ganjil, maka n genap.

Pembahasan:

  1. Asumsikan n³ + 5 ganjil tetapi n ganjil
  2. Jika n ganjil, n = 2k+1
  3. n³ = (2k+1)³ = 8k³ + 12k² + 6k + 1 (ganjil)
  4. n³ + 5 = ganjil + 5 = ganjil + ganjil = genap
  5. Kontradiksi! n³ + 5 seharusnya ganjil
  6. Jadi n genap. ∎

Soal 10:

Buktikan dengan kontradiksi: Jika p bilangan prima dan p | a², maka p | a.

Pembahasan:

  1. Asumsikan p | a² tetapi p tidak membagi a
  2. Karena p prima dan p ∤ a, maka FPB(p, a) = 1
  3. Dari Lemma Euclid: jika p | (a × a) dan FPB(p, a) = 1, maka p | a
  4. Kontradiksi dengan asumsi p ∤ a
  5. 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):

  1. Asumsikan hanya ada berhingga bilangan prima: p₁, p₂, …, pₙ
  2. Bentuk bilangan N = p₁ × p₂ × … × pₙ + 1
  3. N > 1, jadi N memiliki faktor prima (bisa dirinya sendiri)
  4. Misalkan p faktor prima dari N. Maka p = pᵢ untuk suatu i
  5. pᵢ | N dan pᵢ | (p₁ × p₂ × … × pₙ)
  6. Maka pᵢ | (N – p₁ × p₂ × … × pₙ) = 1
  7. Kontradiksi! Tidak ada prima yang membagi 1
  8. Jadi ada tak berhingga bilangan prima. ∎

Soal 12:

Buktikan dengan kontradiksi bahwa log₂ 3 adalah bilangan irasional.

Pembahasan:

  1. Asumsikan log₂ 3 rasional, maka log₂ 3 = p/q dengan p, q bulat positif
  2. Dari definisi logaritma: 2^(p/q) = 3
  3. Pangkatkan dengan q: 2^p = 3^q
  4. Ruas kiri genap (pangkat dari 2), ruas kanan ganjil (pangkat dari 3)
  5. Kontradiksi! Bilangan genap tidak bisa sama dengan bilangan ganjil
  6. Jadi log₂ 3 irasional. ∎

Soal 13:

Buktikan dengan kontradiksi: Jika a + b > 100, maka a > 50 atau b > 50.

Pembahasan:

  1. Asumsikan a + b > 100 tetapi a ≤ 50 dan b ≤ 50
  2. Dari asumsi: a + b ≤ 50 + 50 = 100
  3. Jadi a + b ≤ 100
  4. Kontradiksi dengan premis a + b > 100
  5. 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:

  1. Asumsikan ada n bulat sehingga n² + n + 1 ≡ 0 (mod 4)
  2. Kasus 1: n genap, n = 2k4k² + 2k + 1 ≡ 2k + 1 (mod 4)
  3. Jika k genap: 2k + 1 ≡ 1 (mod 4) ≠ 0
  4. Jika k ganjil: 2k + 1 ≡ 3 (mod 4) ≠ 0
  5. Kasus 2: n ganjil, n = 2k+14k²+4k+1+2k+1+1 ≡ 2k+3 (mod 4)
  6. Jika k genap: 2k+3 ≡ 3 (mod 4) ≠ 0. Jika k ganjil: 2k+3 ≡ 1 (mod 4) ≠ 0
  7. 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:

  1. Asumsikan x + y = 2 tetapi x > 1 dan y > 1
  2. Dari asumsi: x + y > 1 + 1 = 2
  3. Jadi x + y > 2
  4. Kontradiksi dengan x + y = 2
  5. Jadi x ≤ 1 atau y ≤ 1. ∎

F. Contoh Soal: Bukti Kontraposisi

● Soal Mudah (1-5)

Soal 1:

Buktikan dengan kontraposisi: Jika genap, maka n genap.

Pembahasan:

  1. Kontraposisi: “Jika n ganjil, maka ganjil”
  2. Misalkan n ganjil, maka n = 2k + 1
  3. n² = (2k+1)² = 4k² + 4k + 1 = 2(2k²+2k) + 1
  4. berbentuk 2m+1, jadi ganjil
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 2:

Buktikan dengan kontraposisi: Jika n² > 9, maka n > 3 (untuk n bilangan asli).

Pembahasan:

  1. Kontraposisi: “Jika n ≤ 3, maka n² ≤ 9
  2. Misalkan n ≤ 3 (n bilangan asli, jadi n = 1, 2, atau 3)
  3. Karena n ≤ 3 dan n > 0, maka n² ≤ 3² = 9
  4. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 3:

Buktikan dengan kontraposisi: Jika xy ganjil, maka x ganjil.

Pembahasan:

  1. Kontraposisi: “Jika x genap, maka xy genap”
  2. Misalkan x genap, maka x = 2k
  3. xy = 2k × y = 2(ky)
  4. xy genap (kelipatan 2)
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 4:

Buktikan dengan kontraposisi: Jika n + 1 > 4, maka n > 3.

Pembahasan:

  1. Kontraposisi: “Jika n ≤ 3, maka n + 1 ≤ 4
  2. Misalkan n ≤ 3
  3. Tambah 1 kedua ruas: n + 1 ≤ 3 + 1 = 4
  4. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 5:

Buktikan dengan kontraposisi: Jika 5n + 1 genap, maka n ganjil.

Pembahasan:

  1. Kontraposisi: “Jika n genap, maka 5n + 1 ganjil”
  2. Misalkan n = 2k
  3. 5n + 1 = 5(2k) + 1 = 10k + 1 = 2(5k) + 1
  4. 5n + 1 ganjil
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

● Soal Sedang (6-10)

Soal 6:

Buktikan dengan kontraposisi: Jika n³ + 1 genap, maka n ganjil.

Pembahasan:

  1. Kontraposisi: “Jika n genap, maka n³ + 1 ganjil”
  2. Misalkan n = 2k
  3. n³ = (2k)³ = 8k³ (genap)
  4. n³ + 1 = 8k³ + 1 = 2(4k³) + 1 (ganjil)
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 7:

Buktikan dengan kontraposisi: Untuk bilangan real, jika x² + y² = 0 maka x = 0 dan y = 0.

Pembahasan:

  1. Kontraposisi: “Jika x ≠ 0 atau y ≠ 0, maka x² + y² ≠ 0
  2. Misalkan x ≠ 0 (kasus y ≠ 0 serupa)
  3. Maka x² > 0 (kuadrat bilangan real tak nol selalu positif)
  4. Karena y² ≥ 0, maka x² + y² > 0 ≠ 0
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 8:

Buktikan dengan kontraposisi: Jika 3n + 7 genap, maka n ganjil.

Pembahasan:

  1. Kontraposisi: “Jika n genap, maka 3n + 7 ganjil”
  2. Misalkan n = 2k
  3. 3n + 7 = 3(2k) + 7 = 6k + 7 = 6k + 6 + 1 = 2(3k+3) + 1
  4. 3n + 7 ganjil
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 9:

Buktikan dengan kontraposisi: Jika n² – 2n + 7 genap, maka n ganjil.

Pembahasan:

  1. Kontraposisi: “Jika n genap, maka n² – 2n + 7 ganjil”
  2. Misalkan n = 2k
  3. n² – 2n + 7 = 4k² – 4k + 7 = 4k² – 4k + 6 + 1 = 2(2k²-2k+3) + 1
  4. Hasilnya ganjil
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 10:

Buktikan dengan kontraposisi: Jika ab ganjil, maka a ganjil dan b ganjil.

Pembahasan:

  1. Kontraposisi: “Jika a genap atau b genap, maka ab genap”
  2. Kasus 1: a genap, a = 2kab = 2kb genap ✓
  3. Kasus 2: b genap, b = 2mab = 2am genap ✓
  4. Kedua kasus menghasilkan ab genap
  5. 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:

  1. Kontraposisi: “Jika n tidak habis dibagi 3, maka n² – 1 habis dibagi 3″
  2. Jika n tidak habis dibagi 3, maka n = 3k+1 atau n = 3k+2
  3. Kasus 1: n = 3k+1n²-1 = 9k²+6k+1-1 = 3(3k²+2k)
  4. Kasus 2: n = 3k+2n²-1 = 9k²+12k+4-1 = 9k²+12k+3 = 3(3k²+4k+1)
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 12:

Buktikan dengan kontraposisi: Untuk bilangan bulat positif, jika 2^n – 1 prima, maka n prima.

Pembahasan:

  1. Kontraposisi: “Jika n bukan prima (komposit), maka 2^n – 1 bukan prima”
  2. Jika n komposit, maka n = ab dengan 1 < a, b < n
  3. Gunakan identitas: x^(ab) – 1 = (x^a – 1)(x^(a(b-1)) + x^(a(b-2)) + … + 1)
  4. Maka 2^n – 1 = 2^(ab) – 1 habis dibagi 2^a – 1
  5. Karena 1 < a < n, maka 1 < 2^a – 1 < 2^n – 1
  6. 2^n – 1 memiliki faktor selain 1 dan dirinya → bukan prima
  7. 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:

  1. Kontraposisi: “Jika a dan b sama paritas, maka a² + b² genap”
  2. Kasus 1: Keduanya genap. a=2m, b=2na²+b² = 4m²+4n² = 2(2m²+2n²) genap ✓
  3. Kasus 2: Keduanya ganjil. a=2m+1, b=2n+1
  4. a²+b² = 4m²+4m+1+4n²+4n+1 = 2(2m²+2m+2n²+2n+1) genap ✓
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 14:

Buktikan dengan kontraposisi: Jika n² ≡ 1 (mod 4), maka n ganjil.

Pembahasan:

  1. Kontraposisi: “Jika n genap, maka n² ≢ 1 (mod 4)
  2. Misalkan n = 2k
  3. n² = 4k² ≡ 0 (mod 4)
  4. 0 ≠ 1, jadi n² ≢ 1 (mod 4)
  5. Kontraposisi terbukti → pernyataan asli benar. ∎

Soal 15:

Buktikan dengan kontraposisi: Jika x³ + x > 0, maka x > 0 (untuk x bilangan real).

Pembahasan:

  1. Kontraposisi: “Jika x ≤ 0, maka x³ + x ≤ 0
  2. Misalkan x ≤ 0
  3. Faktorkan: x³ + x = x(x² + 1)
  4. x ≤ 0 dan x² + 1 > 0 (selalu positif)
  5. Maka x(x² + 1) ≤ 0 (negatif × positif = negatif atau nol)
  6. 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)

1. Buktikan dengan kontradiksi bahwa tidak ada bilangan bulat yang sekaligus genap dan ganjil.
2. Buktikan dengan kontraposisi: Jika ganjil, maka n ganjil.
3. Buktikan dengan kontradiksi bahwa jika n genap, maka n + 1 ganjil.
4. Buktikan dengan kontraposisi: Jika 7n + 4 genap, maka n genap.
5. Buktikan dengan kontradiksi bahwa jika a × b ganjil, maka a ganjil.

● Soal Sedang (6-10)

6. Buktikan dengan kontradiksi bahwa √5 adalah bilangan irasional.
7. Buktikan dengan kontraposisi: Jika n² + n ganjil, maka n ganjil.
8. Buktikan dengan kontradiksi: Jika a bilangan bulat dan a² – 4a + 7 genap, maka a ganjil.
9. Buktikan dengan kontraposisi: Jika 3n² + 1 genap, maka n ganjil.
10. Buktikan dengan kontradiksi: Tidak ada bilangan bulat n sehingga n² + 2 habis dibagi 4.

● Soal Sulit (11-15)

11. Buktikan dengan kontradiksi bahwa log₁₀ 2 adalah bilangan irasional.
12. Buktikan dengan kontraposisi: Jika a³ + b³ ganjil, maka a dan b berbeda paritas.
13. Buktikan dengan kontradiksi: Jika p prima dan p > 3, maka p² – 1 habis dibagi 24.
14. Buktikan dengan kontraposisi: Jika 2^n + 1 prima, maka n adalah pangkat dari 2.
15. Buktikan dengan kontradiksi: Tidak ada tiga bilangan bulat berurutan yang semuanya merupakan bilangan kuadrat sempurna.
📢 Mengkomunikasikan

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

Materi Matematika – Epres.web.id & Ngelumath.com

By admin

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

You cannot copy content of this page