Logika dan Pembuktian

Logika proposisi menyediakan aturan baku untuk menilai benar atau salahnya gabungan pernyataan, sedangkan pembuktian menetapkan kebenarannya untuk semua kasus sekaligus. Topik ini membahas proposisi dan konektifnya, tabel kebenaran, pemeriksaan ekuivalensi secara menyeluruh, serta empat gaya pembuktian yang umum. Setelah topik ini dipahami, ekspresi boolean pada kode dapat dibaca sebagai proposisi, dan pernyataan assert dapat dibaca sebagai pembuktian yang dijalankan ulang setiap kali program berjalan.

Proposisi dan konektif#

Proposisi adalah pernyataan deklaratif yang memiliki nilai kebenaran tunggal, yaitu benar atau salah. Kalimat “dadu menunjukkan mata enam” adalah proposisi, sedangkan kalimat perintah “tutup jendela” bukan proposisi karena tidak dapat dinilai benar atau salahnya. Pernyataan $x > 3$ juga belum menjadi proposisi selama nilai $x$ belum diketahui, sehingga nilai kebenarannya baru terbentuk setelah $x$ diberi angka.

Proposisi sederhana digabungkan oleh konektif logika menjadi proposisi majemuk. Negasi $\neg p$ membalik nilai kebenaran, konjungsi (conjunction) $p \land q$ bernilai benar hanya apabila keduanya benar, dan disjungsi (disjunction) $p \lor q$ bersifat inklusif sehingga tetap benar apabila keduanya benar. Implikasi (implication) $p \Rightarrow q$ menyatakan “jika $p$ maka $q$”, sedangkan biimplikasi (biconditional) $p \Leftrightarrow q$ menyatakan kesamaan nilai kebenaran. Ketiga konektif pertama bermuara langsung pada operator not, and, dan or pada Python, sedangkan implikasi ditulis (not p) or q dan biimplikasi ditulis p == q.

Tabel kebenaran#

Tabel kebenaran menyenaraikan nilai setiap proposisi majemuk untuk seluruh kombinasi nilai variabelnya. Dua variabel menghasilkan $2^2 = 4$ baris, dan secara umum $n$ variabel menghasilkan $2^n$ baris, sehingga jumlahnya bertambah cepat. Skrip berikut menghasilkan tabel lengkap untuk lima konektif tanpa menghitung satu baris pun secara manual.

"""Tabel kebenaran lengkap untuk lima konektif logika."""
print(f"{'p':>6} {'q':>6} {'¬p':>6} {'p∧q':>6} {'p∨q':>6} {'p⇒q':>6} {'p⇔q':>6}")
for p in [True, False]:
    for q in [True, False]:
        implikasi = (not p) or q
        biimplikasi = p == q
        baris = (p, q, not p, p and q, p or q, implikasi, biimplikasi)
        print("".join(f"{nilai!s:>6}" for nilai in baris))

     p      q     ¬p    p∧q    p∨q    p⇒q    p⇔q
  True  True False  True  True  True  True
  True False False False  True False False
 False  True  True False  True  True False
 False False  True False False  True  True

Kolom implikasi pada keluaran menuntun pembacaan aturannya. Implikasi hanya bernilai salah pada satu baris, yaitu saat $p$ benar tetapi $q$ salah, karena itulah satu-satunya keadaan yang melanggar janjinya. Apabila premisnya sudah salah, janji tidak dapat dilanggar oleh akibat apa pun, sehingga baris terakhir bernilai benar. Kesepakatan ini disebut kebenaran vakum (vacuous truth) dan sering terasa janggal pada awalnya, tetapi kepadanyalah yang membuat rumus (not p) or q cocok dengan makna “jika maka”.

Ekuivalensi dan pemeriksaan menyeluruh#

Dua proposisi disebut ekuivalen (logical equivalence), ditulis $\equiv$, apabila kolom nilai kebenaran keduanya sama pada seluruh baris. Hukum De Morgan adalah pasangan ekuivalensi yang paling sering digunakan pada kode, karena keduanya mengubah negasi di luar tanda kurung menjadi negasi di dalam.

Untuk domain yang berhingga, ekuivalensi dapat dibuktikan dengan menghabiskan seluruh kasus, dan fungsi all pada Python mengerjakannya dalam satu baris. Skrip berikut memeriksa hukum De Morgan, lalu menguji dugaan yang mirip tetapi salah.

"""Pembuktian ekuivalensi logika dengan pemeriksaan seluruh kombinasi."""
from itertools import product

kasus = list(product([True, False], repeat=2))

def implikasi(p, q):
    return (not p) or q

de_morgan = all((not (p and q)) == ((not p) or (not q)) for p, q in kasus)
print("De Morgan  not(p and q) = not p or not q :", de_morgan)

dugaan = all((not (p and q)) == ((not p) and (not q)) for p, q in kasus)
print("dugaan     not(p and q) = not p and not q:", dugaan)

pembantah = [(p, q) for p, q in kasus if (not (p and q)) != ((not p) and (not q))]
print("kasus yang membantah dugaan              :", pembantah)

kontraposisi = all((q or (not p)) == implikasi(p, q) for p, q in kasus)
print("kontraposisi not q => not p              :", kontraposisi)

De Morgan  not(p and q) = not p or not q : True
dugaan     not(p and q) = not p and not q: False
kasus yang membantah dugaan              : [(True, False), (False, True)]
kontraposisi not q => not p              : True

Satu baris keluaran cukup untuk menetapkan kebenaran hukum De Morgan karena keempat kasus sudah dihabiskan. Baris ketiga memperlihatkan arah sebaliknya, yaitu penyangkalan lewat contoh tandingan (counterexample). Dugaan yang hanya berbeda satu konektif dari hukum De Morgan gagal pada dua kasus, sehingga mencari contoh tandingan menjadi langkah pertama yang murah sebelum dugaan dianggap benar. Pemeriksaan baris terakhir juga menetapkan bahwa $\neg q \Rightarrow \neg p$ ekuivalen dengan $p \Rightarrow q$, fakta yang menjadi tulang punggung salah satu gaya pembuktian di bagian berikutnya.

Gaya pembuktian#

Empat gaya pembuktian mencakup sebagian besar kebutuhan. Pembuktian langsung mengasumsikan $p$ benar lalu menurunkan $q$ dalam rangkaian langkah yang sah. Pembuktian kontraposisi (contraposition) membuktikan $\neg q \Rightarrow \neg p$, yang ekuivalensinya sudah diperiksa pada bagian sebelumnya, dan dipilih apabila jalurnya lebih pendek. Pembuktian kontradiksi (contradiction) mengasumsikan pernyataan yang dibantah lalu menurunkan ketidakmungkinan, misalnya pembuktian bahwa $\sqrt{2}$ irasional. Pembuktian induksi (induction) menetapkan kasus dasar lalu langkah kenaikan, dan lazim digunakan untuk pernyataan tentang seluruh bilangan asli.

Diagram berikut menggambarkan implikasi sebagai relasi himpunan, yaitu kumpulan kasus dengan $p$ benar berada sepenuhnya di dalam kumpulan kasus dengan $q$ benar.

Dari gambar itu terlihat mengapa kontraposisi sah, karena berada di luar $Q$ menjamin berada di luar $P$. Gambar yang sama juga memperlihatkan salah baca yang umum, yaitu anggapan bahwa apabila $p$ salah maka $q$ juga salah, padahal di luar $P$ masih terdapat daerah $Q$, sehingga $\neg p$ tidak menjamin apa pun tentang $q$. Pemeriksaan numerik berikut mengilustrasikan kontraposisi pada klaim aritmetika “apabila $n^2$ genap maka $n$ genap”, yang jalur kontraposisinya lebih pendek daripada jalur langsungnya.

def benar(n):
    p = n % 2 != 0          # n ganjil
    q = n * n % 2 != 0      # n kuadrat ganjil
    return (not p) or q     # p => q

hasil = all(benar(n) for n in range(100))
print("jika n ganjil maka n kuadrat ganjil, pada 0..99 :", hasil)

jika n ganjil maka n kuadrat ganjil, pada 0..99 : True

Pemeriksaan seratus kasus memberi keyakinan yang kuat, tetapi klaim tersebut berlaku untuk seluruh bilangan bulat, dan pernyataan semacam ini memang menjadi contoh klasik pembuktian kontraposisi dalam teori bilangan. Perbedaan antara taksiran lewat pemeriksaan dan penetapan lewat pembuktian inilah yang membedakan pengujian kode dari pembuktian matematis.

Di mana hal ini ditemui dalam kode#

Setiap kondisi if dan setiap gabungan operator boolean adalah proposisi yang dinilai program, sehingga aturan pada tabel kebenaran berjalan jutaan kali di dalam mesin. Python menilai operatornya dengan aljabar yang sama dan menambahkan penilaian singkat (short-circuit), yaitu or berhenti pada operan pertama yang benar dan and berhenti pada operan pertama yang salah. Pada saat mencari bug, menuliskan kondisi rumit sebagai tabel kebenaran kecil sering mengungkap baris yang terlupakan.

Pernyataan assert membawa pembuktian masuk ke kode. Apabila ekspresinya bernilai benar, program berlanjut, sedangkan apabila salah, Python menghentikannya dengan error AssertionError beserta pesan yang menyertainya. Perilaku ini menjadikan assert tempat alami untuk menyematkan ekuivalensi logika dan prasyarat fungsi.

for p in [True, False]:
    for q in [True, False]:
        assert (not (p and q)) == ((not p) or (not q))

def persentase(bagian, total):
    assert total != 0, "total tidak boleh nol"
    return round(bagian / total * 100, 2)

print(persentase(19, 40))
print("seluruh asersi ekuivalensi lolos")

47.5
seluruh asersi ekuivalensi lolos

Asersi pertama memeriksa hukum De Morgan pada seluruh kombinasi setiap kali program berjalan, sedangkan asersi kedua menjaga prasyarat pembagian dan memunculkan pesan yang jelas apabila dilanggar. Keduanya murah dan membantu menangkap asumsi yang salah pada titik terjadinya, bukan beberapa langkah kemudian.

Ringkasan#

• Proposisi bernilai benar atau salah, dan konektif $\neg$, $\land$, $\lor$, $\Rightarrow$, serta $\Leftrightarrow$ membentuk gabungannya dengan padanan not, and, or, (not p) or q, dan p == q.
• Tabel kebenaran $n$ variabel memuat $2^n$ baris, dan implikasi hanya salah pada satu baris, yaitu premis benar dengan akibat salah.
• Ekuivalensi berarti sama pada seluruh baris, sehingga dapat dibuktikan dengan menghabiskan kasus pada domain berhingga dan cukup dibantah dengan satu contoh tandingan.
• Gaya pembuktian langsung, kontraposisi, kontradiksi, dan induksi menetapkan kebenaran untuk domain tak berhingga, sedangkan assert menyematkan versi pembuktian yang diperiksa ulang di dalam kode.

Referensi#

• Contemporary Mathematics — OpenStax — Buku teks terbuka dengan bab logika proposisi, tabel kebenaran, dan metode pembuktian yang menjadi rujukan topik ini.
• Truth Value Testing — Python Software Foundation — Dokumentasi cara Python menilai kebenaran nilai dan ekspresi boolean.
• itertools — Python Software Foundation — Dokumentasi fungsi product yang digunakan pemeriksaan seluruh kombinasi nilai kebenaran.