Belajar Math - Proof Techniques (Bukti Matematika)

#Pendahuluan

Setelah di episode 8 kita memahami relasi dan fungsi — injective, surjective, bijective — pada episode ini kita mempelajari proof techniques: teknik membuktikan pernyataan matematika secara formal. Membuktikan bukan sekadar "menunjukkan contoh" — ini adalah penalaran logis yang meyakinkan bahwa pernyataan benar untuk semua kasus, bukan hanya beberapa.

Mengapa proof techniques penting untuk programmer? Karena kalian sebenarnya sudah melakukan bukti informal setiap hari: ketika kalian menulis unit test, itu adalah verifikasi untuk beberapa kasus. Ketika kalian menulis loop invariant, itu adalah bukti informal bahwa loop menghasilkan output benar. Ketika kalian menulis property-based testing, itu adalah verifikasi untuk semua kasus dalam domain. Memahami bukti formal membuat kalian bisa menulis kode yang terbukti benar, bukan hanya "sepertinya benar".

#Direct Proof (Bukti Langsung)

Cara paling sederhana: asumsikan hipotesis benar, gunakan langkah logis berurutan hingga kesimpulan tercapai.

#Contoh: Jumlah Dua Bilangan Genap selalu Genap

Pernyataan: Jika a dan b genap, maka a + b genap.

Bukti:

1. Karena a genap, ada integer k sehingga a = 2k.
2. Karena b genap, ada integer m sehingga b = 2m.
3. a + b = 2k + 2m = 2(k + m).
4. Karena k + m adalah integer, a + b = 2 × (integer), sehingga a + b genap.

Verifikasi direct proof

def is_even(n):
    return n % 2 == 0
 
# Verifikasi untuk banyak pasangan
for a in range(0, 20, 2):  # genap
    for b in range(0, 20, 2):
        assert is_even(a + b), f"Failed: {a} + {b} = {a+b}"
 
print("Direct proof verified: genap + genap = genap")

#Proof by Contradiction (Bukti dengan Kontradiksi)

Asumusikan pernyataan yang ingin dibuktikan salah, lalu tunjukkan ini menghasilkan kontradiksi.

#Contoh: √2 Tidak Bisa Dinyatakan sebagai Pecahan

Pernyataan: √2 irasional (tidak bisa a/b di mana a, b integer).

Bukti:

1. Asumsikan √2 rasional: √2 = a/b di mana a, b integer, FPB(a,b) = 1.
2. Maka 2 = a²/b², sehingga a² = 2b².
3. Karena a² genap, a pasti genap (karena kuadrat ganjil selalu ganjil).
4. Misal a = 2k, maka (2k)² = 2b² → 4k² = 2b² → b² = 2k².
5. Karena b² genap, b juga genap.
6. Tapi jika a dan b keduanya genap, FPB(a,b) ≥ 2 — kontradiksi dengan asumsi FPB = 1.

Verifikasi √2 mendekati tapi tidak pernah sama

import math
 
# Tunjukkan bahwa a² tidak pernah = 2b² untuk a,b kecil
found = False
for b in range(1, 10000):
    for a in range(1, 10000):
        if a**2 == 2 * b**2:
            found = True
            break
    if found:
        break
 
print(f"a² = 2b² ditemukan? {found}")  # False — tidak ada solusi integer
print(f"√2 ≈ {math.sqrt(2):.15f}")  # 1.4142135623730951 — desimal tak hingga

#Proof by Contrapositive

Membuktikan P → Q dengan membuktikan ¬Q → ¬P (yang secara logika ekuivalen).

#Contoh: Jika a² genap, maka a genap

Bukti (contrapositive): Jika a ganjil, maka a² ganjil.

1. Jika a ganjil, a = 2k + 1 untuk some integer k.
2. a² = (2k+1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.
3. 2(2k² + 2k) + 1 adalah ganjil. QED.

Contrapositive: jika a² genap → a genap

def bukti_contrapositive():
    """Verifikasi: jika a² genap, a pasti genap."""
    for a in range(-100, 101):
        if a ** 2 % 2 == 0:  # a² genap
            assert a % 2 == 0, f"Counterexample: a={a}, a²={a**2}"
    print("Contrapositive verified: a² genap → a genap")
 
bukti_contrapositive()

#Mathematical Induction (Induksi Matematika)

Induksi adalah teknik untuk membuktikan pernyataan untuk semua bilangan natural: buktikan base case (n=0 atau n=1), lalu buktikan jika berlaku untuk n=k, maka berlaku untuk n=k+1.

#Contoh: Σ i² dari 1 sampai n = n(n+1)(2n+1)/6

Base case (n=1): 1² = 1. Rumus: 1(2)(3)/6 = 1. ✓

Inductive step: Asumsikan berlaku untuk n=k. Tunjukkan berlaku untuk n=k+1.

Verifikasi induksi untuk Σi² = n(n+1)(2n+1)/6

def sigma_kuadrat_manual(n):
    """Penjumlahan manual."""
    return sum(i**2 for i in range(1, n + 1))
 
def sigma_kuadrat_rumus(n):
    """Rumus tertutup."""
    return n * (n + 1) * (2 * n + 1) // 6
 
# Verifikasi untuk banyak nilai n
for n in range(1, 101):
    manual = sigma_kuadrat_manual(n)
    rumus = sigma_kuadrat_rumus(n)
    assert manual == rumus, f"Failed at n={n}: {manual} != {rumus}"
 
print(f"Σi² (n=1..10) manual: {sigma_kuadrat_manual(10)}")
print(f"Σi² (n=1..10) rumus: {sigma_kuadrat_rumus(10)}")
print(f"Induksi terverifikasi untuk n=1 sampai 100!")

#Rekursi Adalah Induksi

Dalam programming, rekursi adalah implementasi langsung dari induksi: base case = base case induksi; recursive case = inductive step:

Rekursi sebagai induksi

def faktorial(n):
    """Base case: 0! = 1. Recursive: n! = n × (n-1)!"""
    if n == 0:       # Base case
        return 1
    return n * faktorial(n - 1)  # Inductive step
 
def power(b, n):
    """Base case: b^0 = 1. Recursive: b^n = b × b^(n-1)."""
    if n == 0:
        return 1
    return b * power(b, n - 1)
 
print(f"5! = {faktorial(5)}")      # 120
print(f"2^10 = {power(2, 10)}")    # 1024

#Loop Invariants

Loop invariant adalah properti yang selalu benar sebelum dan sesudah setiap iterasi loop — ini adalah bukti informal bahwa loop menghasilkan output yang benar.

#Contoh: Bubble Sort

Invariant: Setelah setiap iterasi outer loop, elemen terakhir yang diproses berada di posisi yang benar.

Bubble sort dengan loop invariant

def bubble_sort(arr):
    """
    Invariant: Setelah iterasi i, elemen arr[n-i:] sudah terurut.
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        # Invariant check (untuk debugging):
        # assert all(arr[j] <= arr[j+1] for j in range(n-i-1, n))
        if not swapped:
            break
    return arr
 
data = [64, 34, 25, 12, 22, 11, 90]
print(f"Before: {data}")
print(f"After:  {bubble_sort(data.copy())}")

#Penutup

Inti yang harus dibawa pulang:

• Direct proof: langkah logis berurutan dari hipotesis ke kesimpulan.
• Contradiction: asumsikan salah, temukan kontradiksi — teknik untuk membuktikan "tidak ada".
• Contrapositive: buktikan ¬Q → ¬P sebagai ganti P → Q — kadang lebih mudah.
• Induction: base case + inductive step = berlaku untuk semua natural — ini adalah rekursi.
• Loop invariants: properti yang selalu benar di loop — ini adalah bukti informal bahwa kode kalian benar.

Di episode 10 selanjutnya kita akan mempelajari counting: sum rule dan product rule — prinsip dasar menghitung kombinasi yang menjadi fondasi dari combinatorics. Bukti induction yang baru kalian pelajari akan sering menggunakan teknik counting untuk menghitung jumlah kasus!