ARSTEMA ACADEMY ANALISIS MATEMATIKA DAN FONDASI RIGOR BAGIAN I — BAB 1 MAT-02 · 1 Oktober 2026 · Revisi editorial naratif, putaran 1 Dokumen Gamma asal: https://gamma.app/docs/avuoaeh8vr9oe1l Versi ini mempertahankan seluruh 36 bagian dan koreksi naskah yang telah ditelaah. Putaran editorial ini mengembangkan pembukaan, uraian kalimat terbuka, dan transisi menuju sintaks, valuasi, serta penghubung. Bagian 1.2 hingga akhir dipertahankan utuh dari versi ditelaah. Dokumen Gamma tetap merupakan draf asal; versi ini tidak menyatakan bahwa dokumen Gamma telah diperbarui. BAB 1 — LOGIKA PROPOSISIONAL: MAKNA, BUKTI, DAN BATAS PENALARAN Analisis Matematika dan Fondasi Rigor · Arstema Academy Ambil sebuah bilangan bulat n. Kita diberi satu informasi: n habis dibagi 4. Apa yang dapat dikatakan tentang n tanpa terlebih dahulu mengetahui bilangannya? Untuk n = 4, kita memperoleh bilangan genap. Hal yang sama terjadi pada n = 8, n = 12, dan n = 20. Deretan contoh ini memberi petunjuk, tetapi pertanyaannya belum selesai. Kita sedang membicarakan setiap bilangan bulat yang habis dibagi 4, termasuk bilangan yang tidak sempat dituliskan. Jika jawabannya harus berlaku untuk semuanya, kita membutuhkan alasan yang menjangkau semuanya. Alasan itu sudah tersimpan dalam arti “habis dibagi”. Pernyataan 4 membagi n, ditulis 4 | n, berarti ada bilangan bulat k sehingga n = 4k. Persamaan ini dapat ditulis kembali sebagai n = 2(2k). Karena 2k juga bilangan bulat, n habis dibagi 2. Dengan demikian, kita telah membuktikan: Untuk setiap n ∈ ℤ, jika 4 | n, maka 2 | n. Bukti ini tidak memerlukan daftar kelipatan 4. Huruf k mewakili bilangan bulat mana pun yang menjadikan n = 4k, dan langkah n = 2(2k) berlaku untuk setiap pilihan itu. Bahkan n = 0 dan bilangan negatif tercakup: 0 = 4·0, sedangkan −12 = 4·(−3). Tidak ada alasan mengecualikannya dari pernyataan yang baru saja dibuktikan. Sekarang ubah pertanyaannya. Kita hanya mengetahui bahwa n habis dibagi 2. Apakah n pasti habis dibagi 4? Pada n = 8, jawabannya ya. Pada n = 12, jawabannya juga ya. Namun n = 2 memenuhi informasi yang diberikan dan menggagalkan kesimpulan yang diusulkan: 2 habis dibagi 2, tetapi tidak habis dibagi 4. Satu bilangan ini cukup untuk menghentikan dugaan bahwa arah balik selalu berlaku. Persoalannya bukan kurang banyak contoh yang mendukung. Persoalannya ialah kesimpulan menuntut sesuatu yang tidak dijamin oleh informasi awal. Kita dapat melihat letak kekurangan itu lebih dekat. Dari 2 | n diperoleh n = 2k untuk suatu k ∈ ℤ. Agar n habis dibagi 4, kita masih memerlukan k genap. Jika k = 1, n = 2 dan syarat tambahan itu gagal. Jadi penalaran yang keliru bukan tidak memiliki perhitungan; ia menyisipkan syarat yang belum diberikan. Di sinilah kita mulai membedakan dua pekerjaan. Pekerjaan pertama menentukan apakah suatu pernyataan benar. Pekerjaan kedua menentukan apakah pernyataan itu mengikuti alasan yang diajukan. Pada n = 8, kesimpulan “4 membagi n” memang benar. Namun keberhasilan pada masukan itu tidak memperbaiki pola penalaran yang gagal pada n = 2. Sebuah jawaban dapat benar sementara alasan yang dipakai untuk memperoleh jawaban tersebut belum sah. Perhatikan pula perubahan yang lain. Andaikan n tidak habis dibagi 2. Mungkinkah ia habis dibagi 4? Jika 4 | n, bukti kita tadi akan memberikan 2 | n. Ini bertentangan dengan informasi bahwa 2 tidak membagi n. Maka 4 juga tidak membagi n. Kita tidak harus mencoba semua bilangan ganjil satu per satu; kita memakai hubungan yang sudah dibuktikan untuk menyingkirkan kemungkinan yang berlawanan. Dua arah penalaran ini mudah tertukar karena menggunakan kalimat yang hampir sama. Kita memerlukan cara mencatat hubungan mereka tanpa terus-menerus membawa seluruh isi aritmetisnya. Untuk satu n yang sedang dibicarakan, tulis: P: “4 membagi n”. Q: “2 membagi n”. Jika n belum ditentukan, kalimat tersebut masih bergantung pada n. Ketika n ditetapkan, masing-masing memiliki nilai benar atau salah. Huruf P dan Q membantu kita memperhatikan pola yang terbentuk: dari “jika P maka Q” bersama “tidak Q”, kita dapat memperoleh “tidak P”; sedangkan dari “jika P maka Q” bersama Q, kita belum boleh memperoleh P. Pola pertama disebut modus tollens. Pola kedua adalah kesalahan menegaskan konsekuen, yang akan diperiksa kembali setelah penghubung “jika … maka …” didefinisikan dengan tepat. Ada batas penting dalam langkah menyingkat kalimat ini. Bukti bahwa setiap kelipatan 4 adalah kelipatan 2 memakai sifat bilangan bulat. Penggantian kalimat dengan P dan Q tidak menciptakan bukti aritmetis tersebut. Logika proposisional memeriksa bagaimana nilai dan hubungan antarkalimat membatasi kesimpulan. Isi kalimat tetap harus dibenarkan oleh bidang matematika tempat kalimat itu berasal. Pembedaan itu akan terus kita gunakan. Ketika nanti kita membahas pertaksamaan, sebuah operasi aljabar mungkin benar hanya pada bagian tertentu dari domain. Ketika membahas limit, satu pilihan parameter mungkin bekerja untuk satu toleransi tetapi gagal untuk toleransi lain. Dalam kedua situasi tersebut, menuliskan hasil akhir saja belum cukup. Kita perlu mengetahui apa yang diasumsikan, apa yang hendak dibuktikan, dan apakah setiap perpindahan masih membawa syarat yang diperlukan. Bab ini menyiapkan kebiasaan membaca seperti itu. Kita terlebih dahulu menentukan ekspresi mana yang mempunyai nilai kebenaran. Sesudahnya, kita membangun formula dari bagian-bagian yang lebih sederhana dan memberi aturan untuk menilai formula tersebut. Dengan dasar itu kita dapat menguji sebuah argumen, menyederhanakan bentuknya, atau menyusun bukti yang memperlihatkan alasan pada tiap langkah. Contoh rangkaian digital dan aturan keputusan akan dipakai ketika struktur yang telah dibangun memang membantu menjelaskan persoalannya. Untuk sementara, simpan satu pertanyaan dari contoh n = 2: adakah keadaan yang membuat seluruh informasi awal benar, tetapi kesimpulan salah? Menemukan keadaan semacam itu akan cukup untuk menolak suatu pola inferensi. Sebaliknya, membuktikan bahwa keadaan tersebut mustahil akan memberi jaminan yang tidak dapat diberikan oleh beberapa contoh yang kebetulan berhasil. Agar pertanyaan itu dapat diajukan secara teliti, kita mulai dengan memperjelas apa yang dimaksud dengan sebuah pernyataan. 1.1 Apa Sebenarnya Objek yang Diperiksa Logika? Sebelum membangun sistem formal apa pun, kita perlu jujur tentang objek yang sedang kita pelajari. Logika sering disebut sebagai "ilmu penalaran yang benar", tetapi klaim itu terlalu longgar untuk menjadi titik tolak yang produktif. Lebih baik kita mulai dari sebuah pertanyaan konkret: di antara semua ekspresi yang dapat diucapkan atau ditulis, mana yang dapat dinilai benar atau salah? Pertimbangkan empat ekspresi berikut: (i) "2 + 2 = 4"; (ii) "x² = 4"; (iii) "Tutup pintunya!"; (iv) "Apakah bilangan prima terbesar ada?" Ekspresi (i) jelas memiliki nilai kebenaran — ia benar, dan kebenarannya tidak bergantung pada konteks apa pun selama kita berbicara tentang aritmetika bilangan bulat biasa. Ekspresi (iii) adalah perintah: ia tidak benar atau salah, melainkan merupakan tindak tutur yang berbeda secara kategoris. Ekspresi (iv) adalah pertanyaan, yang juga tidak memiliki nilai kebenaran meskipun jawabannya — "tidak" — memiliki nilai kebenaran. Logika formal, setidaknya dalam kerangka yang kita bangun, hanya peduli pada jenis ekspresi yang pertama: ekspresi yang memiliki nilai kebenaran yang pasti. Namun ekspresi (ii) lebih licin. "x² = 4" tidak benar atau salah begitu saja — nilainya bergantung pada apa yang dimaksud dengan x. Jika x = 2, ekspresi ini benar. Jika x = 1, ia salah. Jika x = −2, ia benar kembali. Ekspresi semacam ini disebut kalimat terbuka: ia mengandung variabel bebas, dan nilai kebenarannya baru terdefinisi setelah variabel itu diberi nilai dari suatu domain tertentu. Domain sangat penting: jika domain kita adalah bilangan bulat positif ℤ⁺, maka "x² = 4" hanya benar untuk x = 2 saja; jika domain adalah bilangan real ℝ, maka ia benar untuk x = 2 dan x = −2. Perubahan nilai x pada contoh ini mengajarkan sesuatu tentang pekerjaan yang dilakukan oleh sebuah definisi. Jika seseorang menulis x² = 4 di tengah pembuktian, pembaca perlu mengetahui dari mana x berasal. Apakah x sudah dipilih? Apakah persamaan itu sedang diasumsikan? Ataukah penulis mengklaim persamaan tersebut berlaku bagi semua bilangan dalam domain? Tulisan yang sama dapat menjalankan tugas berbeda di dalam argumen. Menentukan tugasnya lebih dahulu akan mencegah kita menilai sebuah langkah dengan pertanyaan yang keliru. Ambil domain ℝ. Pernyataan “ada x yang memenuhi x² = 4” dapat dibenarkan dengan memilih x = 2 dan memeriksa 2² = 4. Pernyataan “setiap x memenuhi x² = 4” justru ditolak oleh x = 1, sebab 1² = 1. Kita belum memerlukan notasi kuantifikator untuk memahami perbedaan itu. Pilihan satu contoh berhasil menjawab tuntutan keberadaan, sedangkan satu contoh gagal sudah menolak tuntutan universal. Nanti, notasi formal akan mencatat perbedaan tuntutan yang kini sudah terlihat pada bilangan sederhana. Pembaca juga tidak harus segera mengetahui nilai benar atau salah sebuah pernyataan agar pernyataan itu layak diperiksa. Misalkan seseorang menyodorkan bilangan bulat yang sangat panjang dan bertanya apakah bilangan tersebut prima. Pekerjaan menghitungnya bisa sulit, tetapi kesulitan itu tidak mengubah arti pertanyaannya. Yang harus jelas ialah objek dan sifat yang sedang dinyatakan. Dengan pemisahan ini, kita dapat membicarakan struktur penalaran tanpa menganggap bahwa semua persoalan aritmetis sudah selesai dihitung. Perbedaan antara kalimat terbuka dan proposisi (atau pernyataan) adalah perbedaan fundamental. Proposisi adalah kalimat yang memiliki nilai kebenaran yang pasti — ia tidak bergantung pada variabel bebas yang belum diberi nilai. Proposisi atomik, dalam konteks logika proposisional, adalah unit kebenaran yang paling dasar: kita tidak menganalisis struktur internalnya. "4 membagi 12" adalah proposisi atomik dalam konteks logika proposisional, meskipun dalam konteks teori bilangan ia memiliki struktur internal yang kaya. Ada satu nuansa penting yang sering diabaikan: status "belum diketahui" pada suatu pernyataan adalah berbeda dari status "salah". Misalnya, Hipotesis Goldbach menyatakan bahwa setiap bilangan genap lebih besar dari 2 adalah jumlah dua bilangan prima. Konjektur biner ini masih dibahas sebagai masalah terbuka dalam rujukan yang diperiksa: paparan Ben Green di Oxford dan tulisan Joseph Malkevitch pada Feature Column AMS tahun 2026; lihat [R7]. Dalam kerangka logika klasik bivalen yang kita adopsi — kerangka di mana setiap proposisi memiliki tepat satu dari dua nilai: benar (1) atau salah (0) — Hipotesis Goldbach tetaplah proposisi dengan nilai kebenaran yang pasti, hanya saja kita belum mengetahuinya. Logika bivalen adalah kerangka semantik yang dipilih di sini. Logika intuisionistik memakai tuntutan pembuktian yang berbeda dan tidak menjadikan hukum tertutup-tengah sebagai prinsip umum; ini tidak sama dengan sekadar menambah nilai “belum diketahui”. Sistem logika tiga nilai memiliki semantiknya sendiri. Ketidaktahuan seorang pembaca, penolakan suatu aturan bukti, dan penambahan nilai semantik merupakan tiga persoalan yang perlu dibedakan. Namun untuk buku ini, logika klasik bivalen adalah kerangka yang kita pilih, dan konsekuensinya akan kita eksplorasi secara penuh. Terakhir, pertimbangkan pernyataan "1 + 1 = 0". Dalam aritmetika bilangan bulat biasa, ini salah. Namun dalam aritmetika modulo 2 — di mana kita hanya peduli sisa pembagian oleh 2 — pernyataan ini benar, karena 1 + 1 = 2 ≡ 0 (mod 2). Ini bukan perubahan nilai kebenaran secara misterius; ini adalah perubahan interpretasi simbol "+". Logika proposisional tidak akan memutuskan mana interpretasi yang "benar" — ia hanya akan menjamin bahwa jika kita sudah sepakat tentang nilai kebenaran atom-atom, maka nilai kebenaran formula-formula kompleks mengikuti secara mekanis dan konsisten. Inilah salah satu kekuatan sekaligus batas logika proposisional. Contoh-contoh tadi membawa kita dari isi kalimat menuju cara mencatat kalimat. Dalam aritmetika, kita memahami mengapa 4 membagi 12. Untuk memeriksa pola “P dan Q”, yang diperlukan selanjutnya ialah nilai P dan nilai Q serta arti penggabungannya. Akan tetapi, penggabungan itu harus ditulis secara pasti. Kita tidak ingin dua pembaca memperoleh susunan berbeda hanya karena mereka memasang jeda pada tempat yang berbeda. Itulah pekerjaan bahasa formal yang sekarang kita bangun. 1.1 (Lanjutan) — Bahasa Dibangun, Bukan Sekadar Dicatat Satu kekeliruan umum ketika pertama kali belajar logika adalah memperlakukan simbol-simbol seperti ¬, ∧, ∨, →, ↔ sebagai singkatan dari kata-kata bahasa Indonesia. Kekeliruan ini berbahaya karena bahasa alami mengandung ambiguitas yang luar biasa — kata "atau" dalam bahasa Indonesia kadang inklusif, kadang eksklusif; kata "jika" kadang bermakna kausalitas, kadang hanya kondisional material. Logika formal membangun bahasanya sendiri dari bawah, dengan definisi yang tidak meninggalkan celah ambiguitas. Kita memulai dari atom: simbol-simbol seperti P, Q, R, S, yang masing-masing mewakili satu proposisi yang nilainya belum ditentukan. Atom adalah formula paling sederhana. Dari atom, kita membangun formula yang lebih kompleks melalui definisi rekursif berikut: - Setiap atom (P, Q, R, …) adalah formula. - Jika A adalah formula, maka ¬A adalah formula (negasi). - Jika A dan B adalah formula, maka (A ∧ B) adalah formula (konjungsi). - Jika A dan B adalah formula, maka (A ∨ B) adalah formula (disjungsi). - Jika A dan B adalah formula, maka (A → B) adalah formula (kondisional). - Jika A dan B adalah formula, maka (A ↔ B) adalah formula (bikondisional). - Tidak ada yang lain yang merupakan formula. Perhatikan klausul terakhir — "tidak ada yang lain" — yang sering terlupakan. Klausul ini memastikan bahwa bahasa kita memiliki batas yang jelas: hanya ekspresi yang dapat dibangun melalui tahap-tahap di atas yang merupakan formula yang sah. Ini penting karena definisi rekursif memberi kita metode induktif untuk membuktikan sesuatu berlaku bagi semua formula: cukup periksa kasus basis (atom) dan tunjukkan bahwa setiap aturan pembangunan melestarikan sifat yang ingin dibuktikan. Sebagai contoh, mari kita bangun formula ¬(P ∧ (Q ∨ R)) langkah demi langkah. Pertama, P, Q, dan R masing-masing adalah formula (kasus basis). Kedua, karena Q dan R formula, maka (Q ∨ R) adalah formula. Ketiga, karena P dan (Q ∨ R) formula, maka (P ∧ (Q ∨ R)) adalah formula. Keempat, karena (P ∧ (Q ∨ R)) adalah formula, maka ¬(P ∧ (Q ∨ R)) adalah formula. Proses pembangunan ini dapat divisualisasikan sebagai pohon, di mana akar adalah formula lengkap, dan setiap simpul interior adalah konektif yang menggabungkan subformula-subformula di bawahnya. Pohon ini menentukan konektif utama (main connective) dari suatu formula — konektif yang dibentuk paling akhir dalam proses rekursif, dan yang memberi label pada akar pohon. Untuk ¬(P ∧ (Q ∨ R)), konektif utamanya adalah ¬. Mengapa konektif utama penting? Karena ia menentukan bagaimana kita mengevaluasi formula. Ketika kita menghitung nilai kebenaran ¬(P ∧ (Q ∨ R)), kita pertama menghitung nilai (Q ∨ R), lalu nilai (P ∧ (Q ∨ R)), baru akhirnya menerapkan ¬. Ketergantungan evaluasi ditentukan oleh struktur pohon: nilai suatu simpul dihitung sesudah nilai anak-anaknya diketahui. Ungkapan informal “dari dalam ke luar” dapat menggambarkan urutan ini; evaluasi dua cabang yang independen tidak harus mempunyai satu urutan waktu yang sama. Tanda kurung adalah mekanisme yang mengkodekan struktur pohon secara linier. Kita juga dapat mendefinisikan ukuran sederhana sebuah formula: jumlah kemunculan konektif. Atom berukuran 0, ¬A berukuran ukuran(A) + 1, dan (A ∘ B) berukuran ukuran(A) + ukuran(B) + 1 untuk setiap konektif biner ∘. Formula ¬(P ∧ (Q ∨ R)) berukuran 3. Ukuran ini berguna karena ia memberikan dasar untuk induksi struktural: untuk membuktikan sesuatu berlaku bagi semua formula, kita dapat melakukan induksi atas ukuran formula, dengan kasus basis pada ukuran 0 (atom) dan langkah induktif menangani setiap aturan pembangunan. Sekarang, sebuah demonstrasi penting tentang mengapa tanda kurung — dan dengan demikian struktur pohon — tidak bisa diabaikan. Perhatikan dua formula: (P ∨ Q) ∧ R dan P ∨ (Q ∧ R). Untuk menunjukkan bahwa keduanya berbeda sebagai formula (dan bukan sekadar berbeda penulisan), kita cukup mencari satu valuasi di mana nilainya berbeda. Ambil P = 1, Q = 0, R = 0. Maka: (P ∨ Q) ∧ R = (1 ∨ 0) ∧ 0 = 1 ∧ 0 = 0; sedangkan P ∨ (Q ∧ R) = 1 ∨ (0 ∧ 0) = 1 ∨ 0 = 1. Valuasi ini adalah valuasi penyangkal yang membuktikan kedua formula tidak ekuivalen secara logis. Terakhir, kita buktikan bahwa → tidak asosiatif: formula (P → Q) → R tidak selalu ekuivalen dengan P → (Q → R). Ambil P = 0, Q = 0, R = 0. Maka (P → Q) → R = (0 → 0) → 0 = 1 → 0 = 0; sedangkan P → (Q → R) = 0 → (0 → 0) = 0 → 1 = 1. Valuasi P = Q = R = 0 memisahkan kedua formula tersebut. Karena itu, tanpa tanda kurung, ekspresi "P → Q → R" adalah ambigu dan tidak dapat diterima dalam bahasa formal kita. Ini bukan pedantri — ini adalah jaminan bahwa setiap formula memiliki satu dan hanya satu makna. Satu catatan notasi yang perlu digarisbawahi sejak awal: simbol ≡ dalam buku ini adalah simbol metabahasa yang menyatakan bahwa dua formula selalu memiliki nilai yang sama pada semua valuasi (ekuivalensi logis). Simbol ↔ adalah konektif dalam bahasa objek; A ↔ B adalah formula, sedangkan simbol ↔ sendirian bukan formula. Simbol ⊨ menyatakan konsekuensi semantik, dan ⊢ menyatakan derivabilitas dalam sistem deduktif. Keempat simbol ini berbeda dan akan dikembangkan masing-masing pada tempatnya. Sampai di sini, kita sudah dapat menjawab pertanyaan tentang bentuk: apakah suatu ekspresi adalah formula, bagian mana yang menjadi komponennya, dan penghubung mana yang bekerja paling akhir. Pertanyaan tentang nilainya masih menunggu. Formula ¬(P ∧ (Q ∨ R)) tetap mempunyai susunan yang sama ketika P, Q, atau R berubah nilai. Pemisahan antara susunan dan nilai memungkinkan satu bentuk formula dipakai untuk menelaah banyak keadaan tanpa menulis ulang aturan penggabungannya. 1.1 (Lanjutan) — Dari Atom Menuju Valuasi Formula sebagai ekspresi sintaktis belum memiliki nilai kebenaran — ia hanya sebuah string simbol yang dibangun sesuai aturan. Untuk memberi makna pada formula, kita perlu konsep valuasi. Secara informal, valuasi adalah cara kita mengisi setiap atom dengan nilai 0 (salah) atau 1 (benar), yang kemudian menentukan nilai seluruh formula secara mekanis. Secara formal, misalkan Atm adalah himpunan semua atom dalam bahasa kita. Sebuah valuasi adalah fungsi v : Atm → {0, 1}. Dengan kata lain, valuasi menetapkan satu nilai — 0 atau 1 — kepada setiap atom. Dari satu valuasi atom, nilai setiap formula dapat dihitung secara unik menggunakan aturan rekursif berikut, di mana A dan B adalah sembarang formula: Formula | Nilai di bawah valuasi v v(¬A) | 1 − v(A) v(A ∧ B) | v(A) · v(B) v(A ∨ B) | v(A) + v(B) − v(A) · v(B) v(A → B) | 1 − v(A) + v(A) · v(B) = (1 − v(A)) + v(A) · v(B) v(A ↔ B) | 1 − v(A) − v(B) + 2 · v(A) · v(B) Rumus-rumus aritmetis di atas mungkin tampak aneh pada pandangan pertama, tetapi ada alasan mengapa kita menuliskannya demikian: kita sedang mengodekan operasi Boolean menggunakan aritmetika bilangan bulat biasa, dan penting untuk tidak mencampuradukkan keduanya. Misalnya, v(A ∨ B) = v(A) + v(B) − v(A) · v(B) bukan berarti 1 + 1 = 1 dalam aritmetika biasa. Apa yang terjadi adalah: jika keduanya bernilai 1, maka formula menghasilkan 1, dan rumus di atas memberikan 1 + 1 − 1·1 = 1, yang benar. Rumus ini adalah cara mengkodekan tabel kebenaran ∨ menjadi operasi aritmetis. Yang terpenting adalah bahwa perluasan dari atom ke formula terjadi secara unik. Artinya, untuk setiap valuasi v : Atm → {0, 1} dan setiap formula F, terdapat tepat satu nilai v(F) ∈ {0, 1}. Keunikan ini mengikuti dari struktur berhingga formula: setiap formula dibangun melalui berhingga banyak langkah rekursif, dan di setiap langkah, nilai formula ditentukan secara unik oleh nilai subformula-subformulannya, yang pada gilirannya ditentukan secara unik oleh struktur rekursif yang lebih kecil. Argumen ini adalah sketsa dari apa yang disebut induksi struktural — prinsip pembuktian yang akan dikembangkan secara penuh di Bab 7. Untuk sekarang, cukup kita catat bahwa keunikan ini adalah fakta yang bisa dibuktikan, bukan sekadar asumsi. Mari kita hitung secara eksplisit. Ambil formula F = ¬(P ∧ (Q ∨ R)) dan dua valuasi: valuasi pertama v₁ dengan v₁(P) = 1, v₁(Q) = 0, v₁(R) = 1; valuasi kedua v₂ dengan v₂(P) = 1, v₂(Q) = 0, v₂(R) = 0. Untuk v₁: v₁(Q ∨ R) = 0 + 1 − 0·1 = 1. Kemudian v₁(P ∧ (Q ∨ R)) = 1 · 1 = 1. Akhirnya v₁(¬(P ∧ (Q ∨ R))) = 1 − 1 = 0. Untuk v₂: v₂(Q ∨ R) = 0 + 0 − 0·0 = 0. Kemudian v₂(P ∧ (Q ∨ R)) = 1 · 0 = 0. Akhirnya v₂(¬(P ∧ (Q ∨ R))) = 1 − 0 = 1. Dua valuasi yang berbeda hanya pada R menghasilkan nilai F yang berbeda. Ini menunjukkan bahwa F adalah formula yang peka terhadap nilai R — dalam terminologi yang akan kita gunakan nanti, F bukan tautologi, bukan pula kontradiksi. Nilai formula bergantung pada valuasi, dan ini berbeda dari bentuk formula yang selalu sama: bentuk F adalah ¬(P ∧ (Q ∨ R)) terlepas dari valuasi apa pun. Nilai formula adalah sebuah bilangan dalam {0, 1}; bentuk formula adalah sebuah ekspresi sintaktis. Mencampuradukkan keduanya adalah salah satu kesalahan paling umum dalam logika pemula. Ada pelajaran tambahan dari dua perhitungan tersebut. Perubahan pada satu atom tidak selalu mengubah hasil akhir, tetapi kita tidak dapat mengetahuinya hanya dengan melihat bahwa atom itu muncul dalam formula. Untuk F = ¬(P ∧ (Q ∨ R)), jika P bernilai 0, konjungsi P ∧ (Q ∨ R) langsung bernilai 0 pada setiap pilihan Q dan R. Akibatnya F bernilai 1, baik R bernilai 0 maupun 1. Sebaliknya, ketika P = 1 dan Q = 0, nilai R menentukan hasil: F bernilai 1 − v(R). Ketergantungan keluaran pada satu masukan dapat berubah sesuai masukan lainnya. Perhitungan itu juga memberi cara membaca formula yang lebih hemat. Pada keadaan P = 0, kita sudah mempunyai alasan mengapa pilihan Q dan R tidak dapat mengubah nilai F. Pada keadaan P = 1, kita masih harus memeriksa bagian yang lain. Kedua pembacaan tetap mengikuti aturan yang sama. Yang berbeda ialah informasi yang tersedia pada keadaan yang sedang diperiksa. Namun aturan evaluasi baru berguna jika arti setiap penghubung dipahami. Mengapa “atau” mengizinkan dua komponen sekaligus benar? Mengapa “jika … maka …” tidak sama dengan hubungan sebab-akibat? Bagian berikut menelaah keputusan semantik tersebut, kemudian menghubungkannya kembali dengan syarat perlu, syarat cukup, serta argumen aritmetis pada pembukaan bab. 1.2 Penghubung dan Informasi yang Dibawanya Setiap konektif dalam bahasa proposisional tidak hanya menggabungkan formula secara sintaktis — ia membawa informasi spesifik tentang hubungan nilai kebenaran antara komponen-komponennya. Memahami informasi apa yang dibawa setiap konektif, termasuk mengapa tabel kebenarannya didefinisikan seperti itu, jauh lebih penting daripada sekadar menghafal tabel. Kita mulai dengan negasi ¬A. Ini adalah konektif unary — ia hanya bekerja pada satu formula. Maknanya sederhana: ¬A benar tepat ketika A salah, dan sebaliknya. Dalam konteks aritmetis, jika A menyatakan "x < 2", maka ¬A menyatakan "tidak (x < 2)", yang ekuivalen dengan "x ≥ 2", bukan "x > 2". Kesalahan umum adalah menuliskan negasi dari x < 2 sebagai x > 2, yang melewatkan kasus x = 2. Dalam logika klasik, negasi memang tepat membalik nilai, dan kehilangan satu titik batas sudah menghasilkan formula yang berbeda. P | Q | P ∧ Q | P ∨ Q 1 | 1 | 1 | 1 1 | 0 | 0 | 1 0 | 1 | 0 | 1 0 | 0 | 0 | 0 Konjungsi P ∧ Q hanya benar ketika keduanya benar. Ini mencerminkan intuisi "keduanya diperlukan": untuk menyatakan bahwa seseorang "datang dan mengerjakan tugas", keduanya harus terjadi. Disjungsi P ∨ Q dalam logika proposisional adalah inklusif: ia benar ketika setidaknya satu dari keduanya benar, termasuk ketika keduanya benar. Ini berbeda dari disjungsi eksklusif (XOR), yang benar hanya ketika tepat satu dari keduanya benar. Formula XOR dapat dituliskan sebagai (P ∨ Q) ∧ ¬(P ∧ Q). Perbedaan antara OR inklusif dan eksklusif penting dalam konteks syarat-syarat. Misalkan kita ingin menyatakan "nilai x berada dalam interval [1, 4]": ini adalah kondisi 1 ≤ x ≤ 4, yang setara dengan konjungsi (x ≥ 1) ∧ (x ≤ 4). Negasinya — "nilai di luar interval" — adalah (x < 1) ∨ (x > 4), menggunakan OR inklusif (tidak mungkin keduanya terpenuhi sekaligus untuk bilangan real, tetapi struktur logisnya tetap OR inklusif). P | Q | P → Q | P ↔ Q 1 | 1 | 1 | 1 1 | 0 | 0 | 0 0 | 1 | 1 | 0 0 | 0 | 1 | 1 Bikondisional P ↔ Q benar tepat ketika P dan Q memiliki nilai yang sama — keduanya benar atau keduanya salah. Ia adalah XOR yang dinegasi, atau ekuivalen, persamaan nilai antara dua komponen. Ini berbeda dari ekuivalensi logis (≡) yang merupakan pernyataan tentang semua valuasi yang sama-sama dipakai untuk menilai kedua formula — perbedaan yang akan kita elaborasi di Bagian 1.3. Perlu diperhatikan bahwa tiap baris tabel kebenaran membawa informasi tersendiri tentang apa yang diklaim konektif. Untuk P ∧ Q, baris 1 (keduanya benar) menyatakan bahwa kondisi bersama terpenuhi; baris 2 dan 3 (satu salah) menyatakan kondisi gagal karena satu komponen; baris 4 (keduanya salah) menyatakan kegagalan total. Setiap baris adalah skenario yang mungkin terjadi, dan tabel kebenaran adalah deskripsi lengkap bagaimana konektif berperilaku di semua skenario tersebut. Tabel negasi melengkapi tabel penghubung biner: P | ¬P 1 | 0 0 | 1 Tidak diperlukan nilai Q untuk mengevaluasi ¬P karena negasi hanya mempunyai satu argumen. 1.2 (Lanjutan) — Mengapa Anteseden Salah Tidak Melanggar Kondisional? Konektif yang paling sering menimbulkan kebingungan adalah kondisional P → Q, khususnya ketika P bernilai salah (0). Mengapa P → Q bernilai benar ketika P salah, tanpa mempedulikan nilai Q? Banyak penjelasan yang beredar berbunyi "dari yang salah, apa pun bisa disimpulkan" — penjelasan ini, meskipun mnemonic yang berguna, tidak memberikan pemahaman yang sesungguhnya. Mari kita turunkan tabel P → Q dari definisi yang lebih mendasar. Definisi yang kita adopsi adalah: P → Q ≡ ¬P ∨ Q. Dua persyaratan awal—nilai 1 pada (P,Q)=(1,1) dan nilai 0 pada (1,0)—belum menentukan satu fungsi Boolean yang unik. Masih ada dua baris, (0,1) dan (0,0), yang masing-masing bisa diberi nilai 0 atau 1; jadi ada empat kemungkinan pelengkapan tabel. Misalnya, P∧Q dan P↔Q juga memenuhi dua persyaratan awal itu. Dalam logika klasik kita memilih kondisional material dengan definisi lengkap ¬P∨Q. Pilihan ini menetapkan bahwa satu-satunya pelanggaran adalah P benar bersama Q salah. Setelah definisi tersebut dipilih, keempat barisnya dapat dihitung: - P = 1, Q = 1: ¬P ∨ Q = 0 ∨ 1 = 1. Sesuai persyaratan (1). - P = 1, Q = 0: ¬P ∨ Q = 0 ∨ 0 = 0. Sesuai persyaratan (2). - P = 0, Q = 1: ¬P ∨ Q = 1 ∨ 1 = 1. Kondisional benar. - P = 0, Q = 0: ¬P ∨ Q = 1 ∨ 0 = 1. Kondisional benar. Dua baris terakhir itulah yang mengejutkan: ketika P = 0 (anteseden salah), kondisional selalu benar, apapun nilai Q. Secara naratif: kondisional hanya dapat dilanggar dengan cara satu: anteseden benar tetapi konsekuen salah. Jika anteseden sudah salah, tidak ada cara untuk "melanggar" kondisional — janji tidak pernah diuji, dan karena itu tidak dilanggar. Kondisional semacam ini disebut vacuously true (benar secara vacuous). Penting untuk membedakan tiga level yang sering dicampuradukkan. Level pertama: nilai P → Q pada satu valuasi tertentu — ini adalah pertanyaan tentang satu skenario. Level kedua: apakah P → Q adalah tautologi? Ini adalah pertanyaan apakah P → Q bernilai benar pada semua valuasi. Tabel di atas menunjukkan bahwa jawabannya tidak, karena baris P = 1, Q = 0 memberikan nilai 0. Level ketiga: apakah pernyataan aritmetis "untuk setiap n bilangan bulat, jika 4 membagi n maka 2 membagi n" adalah benar? Ini adalah pernyataan universal tentang bilangan bulat, bukan tentang formula proposisional. Pada level ketiga ini, pernyataan aritmetis tersebut benar karena argumen matematika: jika 4 membagi n, maka n = 4k untuk suatu k ∈ ℤ, sehingga n = 2(2k), yang berarti 2 membagi n. Setelah argumen ini dilakukan, kita tahu bahwa dalam domain bilangan bulat, valuasi P = 1, Q = 0 tidak pernah terjadi secara bersamaan — tidak ada n ∈ ℤ untuk mana 4 | n tetapi 2 ∤ n. Dengan kata lain, konten aritmetis memaksa baris tertentu pada tabel tidak dapat diwujudkan. Inilah yang membedakan kebenaran material dari kebenaran tautologis. Untuk lebih memperjelas pembedaan ini, pertimbangkan kondisional berikut: "Jika Matahari terbuat dari es, maka 7 adalah bilangan prima." Di sini antesedennya salah (Matahari tidak terbuat dari es) dan konsekuennya benar (7 memang prima). Kondisional ini benar secara material — berdasarkan tabel P → Q baris 0,1. Tetapi jelas tidak ada hubungan sebab-akibat antara komposisi Matahari dan keprimeran 7. Kondisional material adalah konektif tentang nilai, bukan tentang kausalitas atau relevansi. Ambiguitas antara kondisional material dan implikasi kausal adalah sumber kebingungan yang diidentifikasi secara sistematis dalam studi literatur buku teks logika — penelitian kualitatif terhadap tujuh belas buku teks menemukan bahwa banyak teks tidak membedakan secara konsisten antara kondisional pada satu objek, pernyataan universal, dan konsekuensi logis, dan penulisnya menganalisis ambiguitas yang berpotensi membingungkan pembaca. Studi [R4] meneliti buku, bukan menguji secara langsung pemahaman siswa atas bab Arstema. 1.2 (Lanjutan) — Syarat Perlu, Syarat Cukup, dan Negasi yang Tepat Bahasa matematika sehari-hari menawarkan berbagai cara mengekspresikan kondisional — "jika", "hanya jika", "bilamana", "syarat cukup", "syarat perlu" — dan ketepatan dalam membaca ekspresi-ekspresi ini adalah keterampilan yang harus dilatih secara sadar. Kita mulai dengan contoh konkret. Pernyataan "x = 2 adalah syarat cukup untuk x² = 4" berarti: jika x = 2, maka x² = 4. Lebih umum, P adalah syarat cukup untuk Q berarti P → Q. Mengapa "cukup"? Karena memiliki P sudah cukup untuk menjamin Q — kita tidak memerlukan informasi tambahan. Namun x = 2 bukan syarat perlu untuk x² = 4, karena x = −2 juga menghasilkan x² = 4. Pernyataan "P adalah syarat perlu untuk Q" berarti: tanpa P, Q tidak mungkin — atau secara logis, Q → P. Mengapa "perlu"? Karena P harus ada agar Q dapat terjadi. Syarat perlu dan syarat cukup adalah perbedaan yang mendasar dan asimetris. Ekspresi | Simbolik | Arah implikasi Pernyataan asal (P → Q) | P → Q | P ke Q Konvers | Q → P | Q ke P Invers | ¬P → ¬Q | ¬P ke ¬Q Kontrapositif | ¬Q → ¬P | ¬Q ke ¬P Klaim penting yang perlu dibuktikan: P → Q dan kontrapositifnya ¬Q → ¬P adalah logis ekuivalen. Bukti melalui definisi ¬P ∨ Q: nilai P → Q = nilai ¬P ∨ Q. Nilai ¬Q → ¬P = nilai ¬(¬Q) ∨ ¬P = nilai Q ∨ ¬P = nilai ¬P ∨ Q. Karena ∨ komutatif, nilai ¬Q → ¬P = nilai ¬P ∨ Q = nilai P → Q untuk setiap valuasi. Jadi keduanya memiliki nilai yang sama di semua valuasi — ekuivalen secara logis. Ekuivalensi ini bukan sekadar hasil aljabar; ia mencerminkan fakta bahwa untuk membantah "jika P maka Q", satu-satunya cara adalah menemukan P benar dan Q salah, yang sama dengan menemukan ¬Q benar dan ¬P salah, yakni melanggar kontrapositif. Sebaliknya, konvers Q → P dan invers ¬P → ¬Q adalah ekuivalen satu sama lain (keduanya sama dengan ¬Q ∨ P), tetapi tidak umumnya ekuivalen dengan pernyataan asal. Contoh: pernyataan asal "jika x = 2 maka x² = 4" benar. Konversnya "jika x² = 4 maka x = 2" salah (x = −2 adalah counterexample). Kebingungan antara pernyataan asal dan konversnya adalah salah satu kesalahan penalaran paling umum. Sekarang, bagaimana kita menegasikan P → Q? Kita turunkan langkah demi langkah: ¬(P → Q) ≡ ¬(¬P ∨ Q). Dengan hukum De Morgan: ¬(¬P ∨ Q) ≡ ¬(¬P) ∧ ¬Q ≡ P ∧ ¬Q. Jadi negasi dari "P → Q" adalah "P ∧ ¬Q" — anteseden benar dan konsekuen salah. Ini memverifikasi tabel: satu-satunya baris di mana P → Q bernilai 0 adalah baris P = 1, Q = 0. Terakhir, ada satu perbedaan yang perlu disiapkan untuk bab berikutnya. Membantah kondisional "jika P maka Q" untuk satu objek berbeda dari menegasikan pernyataan universal "untuk semua x, jika P(x) maka Q(x)". Untuk yang terakhir, cukup satu counterexample — satu x₀ di mana P(x₀) benar tetapi Q(x₀) salah. Ini bukan menegasikan P → Q sebagai formula proposisional; ini adalah menegasikan klaim universal yang membutuhkan kuantifikasi. Bab 2 akan mengembangkan aparatus kuantifikasi yang diperlukan untuk menangani klaim semacam ini secara tepat. Frasa “P hanya jika Q” berarti P→Q: Q harus terpenuhi apabila P terpenuhi. Frasa “P jika Q” berarti Q→P: Q cukup untuk memperoleh P. “P jika dan hanya jika Q” berarti (P→Q)∧(Q→P), yaitu P↔Q. Contohnya, “x=2 hanya jika x²=4” benar pada domain real; membalik susunannya menjadi “x=2 jika x²=4” menghasilkan klaim yang ditolak oleh x=−2. 1.3 Membaca Semua Kemungkinan, Bukan Memilih Contoh yang Cocok Salah satu transisi terpenting dalam belajar matematika dengan pembuktian ketat adalah beralih dari cara berpikir "coba beberapa contoh" ke cara berpikir "pertimbangkan semua kemungkinan". Dalam logika proposisional, semua kemungkinan valuasi atom-atom dalam formula adalah wilayah yang terbatas dan dapat dikuasai sepenuhnya — itulah daya tabel kebenaran. Kita mendefinisikan kategori formula berdasarkan perilakunya di semua valuasi. Formula F adalah tautologi jika v(F) = 1 untuk setiap valuasi v; F adalah kontradiksi jika v(F) = 0 untuk setiap valuasi v; F adalah kontingensi jika ada valuasi yang membuatnya benar dan ada yang membuatnya salah. Kita menulis ⊤ untuk tautologi kanonik (misalnya P ∨ ¬P) dan ⊥ untuk kontradiksi kanonik (misalnya P ∧ ¬P). Formula F disebut satisfiable jika ada setidaknya satu valuasi yang membuatnya benar — baik tautologi maupun kontingensi adalah satisfiable. Formula F disebut unsatisfiable jika tidak ada valuasi yang membuatnya benar — kontradiksi adalah satu-satunya yang unsatisfiable. Contoh-contoh ilustratif: P ∨ ¬P adalah tautologi (terbukti dari dua baris: P = 1 memberikan 1 ∨ 0 = 1; P = 0 memberikan 0 ∨ 1 = 1). P ∧ ¬P adalah kontradiksi. Formula P → Q adalah kontingensi: baris P = 1, Q = 0 memberikan nilai 0, sedangkan baris lainnya memberikan 1. Formula (P ∨ Q) ∧ ¬P benar hanya pada P = 0, Q = 1 — ia satisfiable tetapi bukan tautologi. Sekarang kita buktikan bahwa formula G = ((P → Q) ∧ (Q → R)) → (P → R) adalah tautologi — ini adalah bentuk proposisional dari silogisme hipotetis. Karena ada tiga atom P, Q, R, tabel memiliki 2³ = 8 baris. P | Q | R | P→Q | Q→R | P→R | (P→Q)∧(Q→R) | G 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 Kolom terakhir seluruhnya bernilai 1, sehingga G adalah tautologi. Mari kita pahami mengapa secara naratif. Formula G adalah kondisional yang anteseden-nya adalah (P → Q) ∧ (Q → R) dan konsekuennya adalah P → R. Formula G hanya bisa bernilai 0 jika antesedennya bernilai 1 dan konsekuennya bernilai 0. Konsekuen P → R bernilai 0 hanya jika P = 1 dan R = 0. Jika P = 1 dan R = 0, periksa anteseden: kita perlu Q → R dan P → Q keduanya benar. Dari R = 0, Q → R benar hanya jika Q = 0. Dari Q = 0 dan P = 1, P → Q = 1 → 0 = 0. Tetapi jika P → Q = 0, maka anteseden (P → Q) ∧ (Q → R) = 0, sehingga G = 0 → 0 = 1. Kontradiksi dengan asumsi G = 0. Jadi tidak ada valuasi yang membuat G bernilai 0 — G adalah tautologi. Perlu ditegaskan: tabel kebenaran dengan 8 baris adalah bukti yang lengkap bahwa G adalah tautologi, karena mencakup seluruh domain valuasi yang mungkin untuk tiga atom. Ini berbeda secara fundamental dari mencoba nilai n = 1, 2, 4 pada domain bilangan bulat: domain bilangan bulat tidak terbatas, sehingga pengecekan berhingga banyak kasus tidak membuktikan klaim universal. 1.3 (Lanjutan) — Konsekuensi, Kesetaraan, dan Kesalahan Tingkat Bahasa Kita telah membangun konsep tautologi sebagai formula yang benar di semua valuasi. Sekarang kita memerlukan konsep yang lebih umum: kapan suatu himpunan premis memaksa suatu kesimpulan? Konsep ini adalah konsekuensi semantik (semantic consequence), yang kita tuliskan Γ ⊨ C. Definisikan: jika Γ adalah himpunan formula (premis-premis) dan C adalah formula (kesimpulan), maka Γ ⊨ C berarti: setiap valuasi v yang memenuhi semua formula dalam Γ juga memenuhi C. Kita katakan v memenuhi formula F jika v(F) = 1. Himpunan semua valuasi yang memenuhi Γ dapat kita notasikan Mod(Γ) — "model-model dari Γ". Maka Γ ⊨ C berarti: Mod(Γ) ⊆ Mod({C}), atau setiap v ∈ Mod(Γ) juga memenuhi C. Penting untuk membedakan tiga hal yang seringkali dicampuradukkan: (1) A ≡ B, yaitu ekuivalensi logis — A dan B memiliki nilai yang sama pada semua valuasi; (2) formula A ↔ B, yang merupakan formula dalam bahasa objek; (3) A ⊨ B, yang berarti setiap valuasi yang memenuhi A juga memenuhi B. Hubungan antara ketiganya perlu dibuktikan, bukan diasumsikan. Teorema: A ≡ B jika dan hanya jika ⊨ (A ↔ B) (yaitu A ↔ B adalah tautologi). Bukti: (⇒) Misalkan A ≡ B, artinya untuk setiap valuasi v, v(A) = v(B). Kita perlu menunjukkan v(A ↔ B) = 1 untuk setiap v. Karena v(A) = v(B), maka keduanya sama-sama 0 atau sama-sama 1. Dalam kedua kasus, v(A ↔ B) = 1 (dari tabel ↔). (⇐) Misalkan ⊨ (A ↔ B), artinya untuk setiap v, v(A ↔ B) = 1. Dari tabel ↔, v(A ↔ B) = 1 jika dan hanya jika v(A) = v(B). Jadi untuk setiap v, v(A) = v(B), artinya A ≡ B. ∎ Teorema: Untuk premis berhingga A₁, …, Aₖ dan kesimpulan C, berlaku: {A₁, …, Aₖ} ⊨ C jika dan hanya jika ⊨ (A₁ ∧ … ∧ Aₖ) → C, jika dan hanya jika formula (A₁ ∧ … ∧ Aₖ ∧ ¬C) adalah unsatisfiable. Bukti arah pertama (⊨ berhingga ↔ tautologi kondisional): Misalkan {A₁, …, Aₖ} ⊨ C. Ambil sembarang valuasi v. Kita akan menunjukkan v((A₁ ∧ … ∧ Aₖ) → C) = 1. Jika v memenuhi semua Aᵢ, maka karena {A₁, …, Aₖ} ⊨ C, v juga memenuhi C, sehingga kondisional bernilai 1. Jika v tidak memenuhi setidaknya satu Aᵢ, maka anteseden (A₁ ∧ … ∧ Aₖ) bernilai 0, sehingga kondisional otomatis bernilai 1. Jadi kondisional itu tautologi. Arah balik: Misalkan ⊨ (A₁ ∧ … ∧ Aₖ) → C. Ambil sembarang v ∈ Mod({A₁, …, Aₖ}), artinya v memenuhi semua Aᵢ. Maka v(A₁ ∧ … ∧ Aₖ) = 1. Dari tautologi, v(C) = 1. Jadi v ∈ Mod({C}). Karena v sembarang, {A₁, …, Aₖ} ⊨ C. Bukti arah kedua (tautologi kondisional ↔ konjungsi dengan negasi tidak terpenuhi): ⊨ (A₁ ∧ … ∧ Aₖ) → C berarti untuk setiap v, nilai kondisional itu 1. Nilai kondisional itu 0 hanya jika anteseden 1 dan konsekuen 0, yaitu jika v memenuhi semua Aᵢ dan v(¬C) = 1. Tautologi kondisional berarti tidak ada valuasi semacam itu — artinya (A₁ ∧ … ∧ Aₖ ∧ ¬C) tidak memiliki model — yaitu unsatisfiable. ∎ Teorema ini sangat kuat secara praktis: untuk memeriksa apakah suatu argumen valid (premis memaksa kesimpulan), kita dapat mencari model dari negasi kesimpulan yang memenuhi semua premis. Jika tidak ada model seperti itu, argumen valid. Pendekatan ini adalah dasar dari banyak metode otomatis dalam verifikasi formal. 1.3 (Lanjutan) — Menemukan Ketidakvalidan Secara Konstruktif Empat pola inferensi proposisional yang paling sering dibicarakan adalah: modus ponens (MP), modus tollens (MT), affirming the consequent, dan denying the antecedent. Dua yang pertama valid; dua yang terakhir tidak. Memahami mengapa secara konstruktif — yaitu dengan menemukan valuasi penyangkal secara eksplisit — lebih mendalam daripada sekadar menghafal namanya. Pola Valid Modus Ponens (MP): Dari P → Q dan P, simpulkan Q. Tidak ada valuasi di mana P → Q benar, P benar, tetapi Q salah: jika P = 1 dan P → Q = 1, maka dari tabel → harus Q = 1. Modus Tollens (MT): Dari P → Q dan ¬Q, simpulkan ¬P. Tidak ada valuasi di mana P → Q benar, Q salah, tetapi P benar: jika Q = 0 dan P = 1, maka P → Q = 0, bertentangan dengan premis. Pola Tidak Valid Affirming the Consequent: Dari P → Q dan Q, simpulkan P. Penyangkal: P = 0, Q = 1. Maka P → Q = 1 (benar) dan Q = 1 (benar), tetapi kesimpulan P salah. Denying the Antecedent: Dari P → Q dan ¬P, simpulkan ¬Q. Penyangkal: P = 0, Q = 1. Maka P → Q = 1, ¬P = 1, tetapi ¬Q = 0, kesimpulan salah. Perhatikan bahwa penyangkal untuk affirming the consequent dan denying the antecedent adalah valuasi yang sama: P = 0, Q = 1. Ini menarik: satu valuasi mematahkan kedua pola sekaligus. Kita dapat menghubungkan ini kembali ke pembukaan bab: argumen pertama ("jika 4 | n maka 2 | n; 2 | n; maka 4 | n") adalah contoh affirming the consequent dengan anteseden "4 | n" dan konsekuen "2 | n", dan n = 2 memberikan penyangkal konkret — premis keduanya benar tetapi kesimpulan salah. Sebuah aspek penting yang sering terlewat: suatu argumen bisa saja valid dengan premis-premis yang salah. Pertimbangkan: "Jika Bumi adalah kubus, maka Bumi memiliki 8 sudut. Bumi adalah kubus. Jadi Bumi memiliki 8 sudut." Argumen ini valid secara formal (modus ponens), tetapi premis kedua salah. Kesimpulan tentang Bumi pada contoh ini juga salah; hal itu tidak diperoleh hanya dari fakta bahwa ada premis salah. Argumen valid dengan premis salah dapat mempunyai kesimpulan benar ataupun salah. Validitas suatu argumen hanya menjamin bahwa jika premis-premisnya benar, maka kesimpulannya pun benar. Ini tidak menjamin bahwa premisnya benar. Sebaliknya, kesimpulan yang benar tidak menjamin bahwa argumen itu valid. Ambil kembali pola “jika 4 membagi n, maka n genap; n genap; jadi 4 membagi n”, kali ini pada n=4. Premis-premis dan kesimpulannya benar pada masukan itu. Namun bentuk penalarannya tetap tidak valid: masukan n=2 memenuhi kedua premis tetapi menggagalkan kesimpulan. Kebenaran hasil pada n=4 tidak menghilangkan contoh penyangkal pada n=2. Tugas untuk pembaca: Dalam modus tollens, dari P → Q dan ¬Q, kita simpulkan ¬P. Identifikasikan: (i) asumsi mana yang dipakai dalam langkah derivasinya? (ii) mengapa penambahan premis ¬Q tidak cukup sendirian untuk menyimpulkan ¬P tanpa premis pertama P → Q? (iii) apa yang terjadi jika kita ganti ¬Q dengan Q — apakah kesimpulan berubah? Pembahasan tugas: (i) kedua premis P→Q dan ¬Q digunakan; asumsi sementara P menghasilkan Q melalui modus ponens, lalu bertentangan dengan ¬Q. (ii) Dari ¬Q saja, P masih dapat bernilai 1: valuasi P=1,Q=0 menyangkal inferensi ¬Q⊨¬P. (iii) Mengganti ¬Q dengan Q memberi premis {P→Q,Q}, yang tidak menentukan P. Kedua valuasi (P,Q)=(0,1) dan (1,1) memenuhi premis; jadi baik P maupun ¬P tidak dipaksa. 1.4 Menghitung dengan Formula Logika proposisional bukan hanya tentang memeriksa kebenaran — ia juga menyediakan perangkat aljabar untuk menyederhanakan dan memanipulasi formula. Hukum-hukum aljabar Boolean yang kita sajikan di sini adalah teorema yang dapat dibuktikan dari definisi konektif, bukan aksioma yang diasumsikan. Hukum | Untuk ∧ | Untuk ∨ Identitas | A ∧ ⊤ ≡ A | A ∨ ⊥ ≡ A Dominasi | A ∧ ⊥ ≡ ⊥ | A ∨ ⊤ ≡ ⊤ Idempoten | A ∧ A ≡ A | A ∨ A ≡ A Komutatif | A ∧ B ≡ B ∧ A | A ∨ B ≡ B ∨ A Asosiatif | (A∧B)∧C ≡ A∧(B∧C) | (A∨B)∨C ≡ A∨(B∨C) Distributif | A∧(B∨C) ≡ (A∧B)∨(A∧C) | A∨(B∧C) ≡ (A∨B)∧(A∨C) Absorpsi | A ∧ (A ∨ B) ≡ A | A ∨ (A ∧ B) ≡ A Komplemen | A ∧ ¬A ≡ ⊥ | A ∨ ¬A ≡ ⊤ Involusi | ¬(¬A) ≡ A | — De Morgan | ¬(A∧B) ≡ ¬A∨¬B | ¬(A∨B) ≡ ¬A∧¬B Mari kita buktikan hukum absorpsi ∧: A ∧ (A ∨ B) ≡ A. Kita lakukan analisis kasus pada nilai A. Kasus A = 1: Sisi kiri = 1 ∧ (1 ∨ B) = 1 ∧ 1 = 1 (karena 1 ∨ B = 1 untuk semua B). Sisi kanan = A = 1. Keduanya 1. Kasus A = 0: Sisi kiri = 0 ∧ (0 ∨ B) = 0 (karena 0 ∧ (apa pun) = 0). Sisi kanan = A = 0. Keduanya 0. Karena dalam semua kasus nilainya sama tanpa bergantung pada B, hukum absorpsi terbukti. ∎ Sekarang kita buktikan distributivitas A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C). Kita analisis kasus pada A. Kasus A = 1: Sisi kiri = 1 ∨ (B ∧ C) = 1. Sisi kanan = (1 ∨ B) ∧ (1 ∨ C) = 1 ∧ 1 = 1. Sama. Kasus A = 0: Sisi kiri = 0 ∨ (B ∧ C) = B ∧ C. Sisi kanan = (0 ∨ B) ∧ (0 ∨ C) = B ∧ C. Sama. Jadi distributivitas terbukti. ∎ Mengapa kita diperbolehkan mengganti subformula ekuivalen dalam formula yang lebih besar? Ini adalah prinsip kongruensi evaluasi. Setiap konektif adalah fungsi dari nilai komponen-komponennya. Jika A ≡ A' (nilai A dan A' sama di semua valuasi), maka mengganti A dengan A' dalam formula F tidak mengubah nilai F di mana pun. Argumen formalnya: nilai F dihitung dari daun menuju akar pohon; mengganti subformula ekuivalen tidak mengubah nilai simpul manapun di atas penggantian itu. Ini berbeda dari identitas sintaktis: A dan A' mungkin formula yang berbeda secara bentuk, tetapi nilai mereka identik di semua valuasi. 1.4 (Lanjutan) — Kasus Empat Variabel yang Memerlukan Strategi Sebagai latihan aljabar Boolean yang lebih menuntut, kita selesaikan sepenuhnya penyederhanaan formula empat variabel berikut: F = (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ S) ∧ (¬R ∨ S) Target ekuivalen kita adalah S ∧ [(P ∧ R) ∨ (¬P ∧ Q)]. Sebelum bekerja dengan F, kita terlebih dahulu membuktikan sebuah lemma penting yang disebut lemma konsensus: Lemma: (P ∧ R) ∨ (¬P ∧ Q) ∨ (Q ∧ R) ≡ (P ∧ R) ∨ (¬P ∧ Q). Bukti: Kita distribusikan suku Q ∧ R menurut P ∨ ¬P (yang ≡ ⊤): Q ∧ R ≡ Q ∧ R ∧ (P ∨ ¬P) = (Q ∧ R ∧ P) ∨ (Q ∧ R ∧ ¬P) = (P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ R). Sekarang substitusikan ke dalam disjungsi tiga suku: (P ∧ R) ∨ (¬P ∧ Q) ∨ (P ∧ Q ∧ R) ∨ (¬P ∧ Q ∧ R). Perhatikan bahwa (P ∧ Q ∧ R) diserap oleh (P ∧ R): P ∧ R ∨ P ∧ Q ∧ R = P ∧ R ∧ (⊤ ∨ Q) = P ∧ R. Demikian pula, (¬P ∧ Q ∧ R) diserap oleh (¬P ∧ Q): ¬P ∧ Q ∨ ¬P ∧ Q ∧ R = ¬P ∧ Q ∧ (⊤ ∨ R) = ¬P ∧ Q. Sehingga seluruh ekspresi menjadi (P ∧ R) ∨ (¬P ∧ Q). ∎ Sekarang kita kerjakan F. Langkah pertama: kembangkan (P ∨ Q) ∧ (¬P ∨ R). Distribusikan ∧ atas ∨: (P ∨ Q) ∧ (¬P ∨ R) = (P ∧ ¬P) ∨ (P ∧ R) ∨ (Q ∧ ¬P) ∨ (Q ∧ R) = ⊥ ∨ (P ∧ R) ∨ (¬P ∧ Q) ∨ (Q ∧ R) = (P ∧ R) ∨ (¬P ∧ Q) ∨ (Q ∧ R). Dengan lemma konsensus: (P ∨ Q) ∧ (¬P ∨ R) ≡ (P ∧ R) ∨ (¬P ∧ Q). Kita sebut hasil ini M = (P ∧ R) ∨ (¬P ∧ Q). Sekarang F = M ∧ (¬Q ∨ S) ∧ (¬R ∨ S). Langkah kedua: distribusikan M menurut dua kasus: M = (P ∧ R) ∨ (¬P ∧ Q). Kita terapkan dua klausul terakhir pada masing-masing suku. Cabang P ∧ R: Perlu memenuhi ¬Q ∨ S dan ¬R ∨ S. Perhatikan R = 1 memaksa ¬R = 0, sehingga ¬R ∨ S = S. Jadi cabang ini memberikan (P ∧ R) ∧ (¬Q ∨ S) ∧ S. Karena S ∧ (¬Q ∨ S) ≡ S (absorpsi), hasil cabang P ∧ R adalah (P ∧ R) ∧ S = P ∧ R ∧ S. Cabang ¬P ∧ Q: Perlu memenuhi ¬Q ∨ S dan ¬R ∨ S. Karena Q = 1 memaksa ¬Q = 0, maka ¬Q ∨ S = S. Jadi cabang ini memberikan (¬P ∧ Q) ∧ S ∧ (¬R ∨ S) = (¬P ∧ Q ∧ S) ∧ (¬R ∨ S). Dengan absorpsi S ∧ (¬R ∨ S) = S, hasil adalah ¬P ∧ Q ∧ S. Menggabungkan kedua cabang: F ≡ (P ∧ R ∧ S) ∨ (¬P ∧ Q ∧ S) = S ∧ [(P ∧ R) ∨ (¬P ∧ Q)]. Ini adalah target yang dicari. Mari kita verifikasi dengan dua valuasi konkret. Ambil P = 1, Q = 0, R = 1, S = 1: F = (1∨0)∧(0∨1)∧(1∨1)∧(0∨1) = 1∧1∧1∧1 = 1. Target: S∧[(P∧R)∨(¬P∧Q)] = 1∧[(1∧1)∨(0∧0)] = 1∧[1∨0] = 1. Cocok. Ambil P = 1, Q = 1, R = 0, S = 1: F = (1∨1)∧(0∨0)∧(0∨1)∧(1∨1) = 1∧0∧1∧1 = 0. Target: 1∧[(1∧0)∨(0∧1)] = 1∧[0∨0] = 0. Cocok. 1.4 (Lanjutan) — Bentuk Normal dan Informasi yang Terlihat Hasil penyederhanaan formula seringkali mengikuti pola struktural tertentu yang memiliki nama dan sifat matematika yang penting. Konsep-konsep bentuk normal memungkinkan kita membandingkan formula secara sistematis dan menganalisis apa yang "terlihat" dari struktur sintaktis sebuah formula. Kita mulai dari unit terkecil. Sebuah literal adalah atom P atau negasi atom ¬P. Sebuah klausa disjungtif (atau cukup klausa) adalah disjungsi literal: misalnya P ∨ ¬Q ∨ R. Sebuah klausa konjungtif (atau suku) adalah konjungsi literal: misalnya P ∧ ¬Q ∧ R. Formula dalam Bentuk Normal Disjungtif (DNF) adalah disjungsi klausa konjungtif (disjungsi suku-suku). Formula dalam Bentuk Normal Konjungtif (CNF) adalah konjungsi klausa disjungtif (konjungsi klausa-klausa). Sebagai contoh nyata, pertimbangkan fungsi majority M(P, Q, R) yang bernilai 1 tepat ketika setidaknya dua dari tiga variabel bernilai 1. Kita identifikasi baris-baris yang memberikan nilai 1: (P,Q,R) = (1,1,0), (1,0,1), (0,1,1), (1,1,1) — yaitu dalam notasi biner 110, 101, 011, 111. Setiap baris ini menghasilkan satu minterm: konjungsi literal di mana variabel bernilai 1 muncul positif dan variabel bernilai 0 muncul ternegasi. - Baris 110: P ∧ Q ∧ ¬R - Baris 101: P ∧ ¬Q ∧ R - Baris 011: ¬P ∧ Q ∧ R - Baris 111: P ∧ Q ∧ R DNF kanonik M adalah disjungsi keempat minterm ini: (P∧Q∧¬R) ∨ (P∧¬Q∧R) ∨ (¬P∧Q∧R) ∨ (P∧Q∧R). DNF ini dapat disederhanakan: misalnya (P∧Q∧¬R) ∨ (P∧Q∧R) = P∧Q∧(¬R∨R) = P∧Q. Setelah absorpsi serupa, M = (P∧Q) ∨ (P∧R) ∨ (Q∧R), yang merupakan DNF yang lebih sederhana tetapi bukan kanonik (tidak semua suku adalah minterm tiga-variabel). CNF M dibangun dari baris-baris yang memberikan nilai 0 (baris yang tersisa: 000, 001, 010, 100), lalu untuk setiap baris itu kita buat maxterm — disjungsi literal di mana variabel bernilai 0 muncul positif dan variabel bernilai 1 muncul ternegasi — kemudian konjungsi keempat maxterm. Hasilnya adalah CNF kanonik yang kompleks. Namun untuk M, CNF yang sederhana tersedia: (P∨Q) ∧ (P∨R) ∧ (Q∨R). Ini dapat diverifikasi: ia bernilai 1 tepat ketika setidaknya dua dari P, Q, R bernilai 1. Satu hal yang perlu ditekankan: DNF tidak selalu minimal atau unik dalam bentuk non-kanoniknya. Untuk daftar variabel yang tetap, himpunan minterm dalam DNF kanonik ditentukan secara unik oleh baris bernilai 1; susunan urutan suku dan tanda kurung dapat berbeda. Bentuk ini bisa panjang. Menyederhanakan DNF ke bentuk minimal adalah masalah non-trivial. Juga, tidak semua formula sudah dalam DNF atau CNF — formula ¬(P ∨ Q) bukan DNF karena negasi berada di luar disjungsi, bukan di level literal. Untuk mengubahnya ke DNF, kita perlu menerapkan De Morgan: ¬(P ∨ Q) = ¬P ∧ ¬Q, yang merupakan konjungsi literal — ini adalah suku tunggal, sehingga trivially DNF maupun CNF. Ketika minterm P∧Q∧R diperlukan dalam lebih dari satu pengelompokan penyederhanaan, kita boleh menuliskannya berulang melalui hukum idempoten A∨A≡A. Dengan begitu pasangan untuk P∧Q, P∧R, dan Q∧R dapat dibentuk tanpa menghapus keadaan bernilai 1 yang masih diperlukan. 1.4 (Lanjutan) — Mengapa Setiap Fungsi Boolean Dapat Dituliskan? Kita telah melihat bagaimana membangun DNF untuk fungsi majority melalui minterm. Sekarang kita buktikan hasil yang lebih umum: setiap fungsi Boolean — setiap fungsi f : {0,1}ⁿ → {0,1}, dengan n bilangan bulat positif — dapat dituliskan sebagai formula proposisional. Ini adalah teorema representasi yang fundamental. Teorema Representasi DNF: Setiap fungsi f : {0,1}ⁿ → {0,1} dapat dituliskan sebagai formula dalam DNF (atau CNF) atas n variabel P₁, …, Pₙ. Bukti untuk DNF: Untuk setiap vektor a = (a₁, …, aₙ) ∈ {0,1}ⁿ, definisikan minterm m_a sebagai konjungsi: m_a = L₁ ∧ L₂ ∧ … ∧ Lₙ, di mana Lᵢ = Pᵢ jika aᵢ = 1, dan Lᵢ = ¬Pᵢ jika aᵢ = 0. Klaim: untuk setiap vektor b ∈ {0,1}ⁿ, nilai m_a pada valuasi yang menetapkan nilai b adalah: m_a(b) = 1 jika dan hanya jika b = a. Bukti klaim: Jika b = a, maka untuk setiap i, bᵢ = aᵢ, sehingga nilai Lᵢ pada b adalah 1 (karena jika aᵢ = 1 maka Pᵢ bernilai bᵢ = 1; jika aᵢ = 0 maka ¬Pᵢ bernilai 1 − bᵢ = 1). Jadi nilai m_a pada b adalah 1ⁿ = 1. Jika b ≠ a, maka ada suatu j dengan bⱼ ≠ aⱼ. Nilai Lⱼ pada b adalah 0 (karena jika aⱼ = 1 maka Pⱼ bernilai bⱼ = 0; jika aⱼ = 0 maka ¬Pⱼ bernilai 1 − bⱼ = 0). Karena konjungsi mengandung faktor bernilai 0, m_a(b) = 0. ∎ Sekarang definisikan formula DNF untuk f: ambil disjungsi seluruh minterm m_a di mana f(a) = 1. Secara formal: F_f = ∨{m_a : f(a) = 1}. Maka untuk setiap valuasi b: F_f(b) = 1 jika dan hanya jika ada a dengan f(a) = 1 dan m_a(b) = 1, yaitu jika dan hanya jika f(b) = 1. Jadi F_f merepresentasikan f secara tepat. Jika f adalah fungsi yang selalu bernilai 0 (f ≡ 0), disjungsi di atas adalah disjungsi kosong, yang kita definisikan bernilai ⊥ (selalu salah) — konsisten dengan konvensi bahwa konjungsi kosong adalah ⊤ dan disjungsi kosong adalah ⊥. CNF dapat diperoleh dengan dua cara: (1) dari baris-baris di mana f bernilai 0, bangun maxterm untuk setiap baris tersebut, lalu konjungsikan; (2) terapkan teorema representasi DNF pada ¬f, lalu negasikan menggunakan De Morgan untuk memperoleh CNF f. Implikasi kuantitatif penting: ada 2ⁿ vektor input untuk n variabel, dan ada 2^(2ⁿ) fungsi Boolean berbeda (karena setiap fungsi adalah pemetaan dari 2ⁿ input ke {0,1}, dan ada 2^(2ⁿ) pemetaan seperti itu). Untuk n = 1: 4 fungsi (selalu-0, selalu-1, identitas P, negasi ¬P). Untuk n = 2: 16 fungsi. Untuk n = 3: 256 fungsi. Semua dapat direpresentasikan. Ini adalah kelengkapan fungsional himpunan {¬, ∧, ∨}: himpunan konektif ini cukup untuk mengekspresikan setiap fungsi Boolean. Kelengkapan fungsional ini berbeda dari kelengkapan sistem deduktif (setiap tautologi dapat dibuktikan) dan dari sifat kelengkapan bilangan real yang akan dibahas pada Bagian II. Kelengkapan fungsional membicarakan daya ekspresi penghubung; kelengkapan deduksi membicarakan hubungan antara keterbuktian dan validitas; kelengkapan bilangan real membicarakan, antara lain, keberadaan supremum. Nama yang sama tidak membuat ketiga sifat ini identik. 1.5 Ketika Bukti Menyimpan Alasan Tabel kebenaran memberikan cara yang dapat diandalkan untuk menentukan apakah suatu formula adalah tautologi, atau apakah suatu argumen valid. Tabel kebenaran memberikan pembuktian melalui pemeriksaan semua kasus. Akan tetapi, tabel itu belum menyajikan rantai inferensi atau strategi tertentu yang menjelaskan hubungan antarbagian argumen. Lebih jauh, untuk formula dengan banyak variabel, tabel kebenaran tumbuh secara eksponensial dan tidak praktis. Sistem deduktif natural menawarkan pendekatan yang berbeda: kita membangun bukti sebagai urutan langkah yang masing-masing dapat dipertanggungjawabkan, dan setiap langkah menggunakan aturan inferensi yang dijamin melestarikan kebenaran. Kita menulis Γ ⊢ C untuk menyatakan bahwa C dapat diturunkan dari himpunan asumsi Γ menggunakan aturan-aturan sistem deduksi natural yang kita adopsi. Simbol ⊢ adalah simbol derivabilitas — ia berbeda dari ⊨ yang merupakan simbol konsekuensi semantik. Hubungan antara keduanya (soundness dan completeness) adalah salah satu hasil terdalam logika, yang akan kita sentuh di Bagian 1.5 lanjutan. Sistem deduksi natural yang kita gunakan bekerja dengan asumsi. Sebuah bukti dimulai dengan beberapa asumsi (yang bisa berupa premis global atau asumsi sementara), lalu mengaplikasikan aturan inferensi, dan akhirnya menutup asumsi-asumsi sementara. Asumsi yang ditutup tidak lagi muncul sebagai bergantung dalam langkah berikutnya. Asumsi yang masih terbuka di akhir bukti adalah premis global yang harus diasumsikan. Konsep "asumsi terbuka" dan "asumsi tertutup" ini adalah inti dari deduksi natural, dan kita akan melihatnya bekerja secara konkret di subbagian berikutnya. Aturan-aturan inferensi yang kita adopsi dalam sistem deduksi natural klasik: Aturan Konjungsi ∧-Intro: Dari A dan B, simpulkan A ∧ B. ∧-Elim₁: Dari A ∧ B, simpulkan A. ∧-Elim₂: Dari A ∧ B, simpulkan B. Aturan Disjungsi & Kondisional ∨-Intro₁: Dari A, simpulkan A ∨ B. ∨-Intro₂: Dari B, simpulkan A ∨ B. →-Elim (MP): Dari A → B dan A, simpulkan B. →-Intro: Jika dari asumsi A kita dapat menurunkan B, maka kita dapat menutup asumsi A dan simpulkan A → B. Aturan Disjungsi & Negasi ∨-Elim: Dari A ∨ B, dengan subbukti A ⊢ C dan subbukti B ⊢ C, simpulkan C. ¬-Intro: Jika dari asumsi A kita peroleh kontradiksi ⊥, tutup A dan simpulkan ¬A. Kontradiksi (¬-Elim): Dari A dan ¬A, simpulkan ⊥. ⊥-Elim: Dari ⊥, simpulkan sembarang formula C. ¬¬-Elim: Dari ¬¬A, simpulkan A (aturan klasik). Aturan ∨-Eliminasi memerlukan penjelasan lebih lanjut karena ia memperkenalkan ide pemisahan kasus. Jika kita tahu A ∨ B benar, kita tidak bisa begitu saja memilih A atau B — kita harus mempertimbangkan kedua kemungkinan. Kita membuat dua subbukti: satu yang mengasumsikan A dan menurunkan C, dan satu yang mengasumsikan B dan menurunkan C. Karena A ∨ B dijamin salah satunya benar, dan keduanya mengarah ke C, maka C pasti benar. Aturan ¬-Intro (dan aturan ⊥-Elim yang menyertainya) memberikan dasar untuk reductio ad absurdum: untuk membuktikan ¬A, asumsikan A, turunkan kontradiksi, dan tutup asumsi A. 1.5 (Lanjutan) — Membuka dan Menutup Asumsi Aturan-aturan di atas menjadi hidup ketika kita melihatnya bekerja dalam bukti konkret. Kita buktikan formula (P → Q) → ((Q → R) → (P → R)), yang merupakan bentuk proposisional dari prinsip transitif kondisional. No. | Formula | Aturan | Asumsi bergantung 1 | P → Q | Asumsi [a] | {a} 2 | Q → R | Asumsi [b] | {a,b} 3 | P | Asumsi [c] | {a,b,c} 4 | Q | →-Elim baris 1,3 | {a,b,c} 5 | R | →-Elim baris 2,4 | {a,b,c} 6 | P → R | →-Intro: tutup [c], baris 3–5 | {a,b} 7 | (Q→R)→(P→R) | →-Intro: tutup [b], baris 2–6 | {a} 8 | (P→Q)→((Q→R)→(P→R)) | →-Intro: tutup [a], baris 1–7 | {} Baris 8 tidak bergantung pada asumsi terbuka mana pun — himpunan ketergantungannya adalah {}. Ini berarti formula pada baris 8 adalah teorema: dapat diturunkan tanpa asumsi apa pun, atau ekuivalen, ia adalah tautologi yang dapat dibuktikan. Proses menutup asumsi adalah kunci: ketika kita menerapkan aturan →-Intro pada baris 3–5 untuk memperoleh P → R, kita "mengkonsumsi" asumsi [c] tentang P — artinya, kesimpulan P → R tidak lagi bergantung pada asumsi bahwa P benar. Mengapa kesimpulan akhir tidak bergantung pada asumsi terbuka? Karena setiap asumsi yang dibuka telah ditutup secara eksplisit. Asumsi [c] tentang P ditutup di baris 6, menghasilkan kondisional P → R. Asumsi [b] tentang Q → R ditutup di baris 7, menghasilkan kondisional (Q → R) → (P → R). Asumsi [a] tentang P → Q ditutup di baris 8. Pada akhirnya, kita memiliki formula yang "berdiri sendiri" — tidak ada hutang asumsi yang belum dibayar. Perlu dibedah pula sebuah kesalahan yang umum: "Asumsikan P. Dari asumsi ini, P benar. Tutup asumsi. Simpulkan P." Langkah ini tidak valid. Aturan →-Intro menyatakan: jika dari asumsi A kita dapat menurunkan B, maka kita dapat menutup A dan simpulkan A → B. Jika kita mengasumsikan P dan (trivially) menurunkan P, yang kita peroleh bukan P, melainkan P → P. Formula P → P memang tautologi dan dapat dibuktikan dengan cara ini — tetapi kita tidak bisa dari sini menyimpulkan P tanpa asumsi apa pun. Menyimpulkan P tanpa asumsi apa pun berarti mengklaim P adalah tautologi, yang jelas tidak benar untuk variabel proposisional bebas. Kolom “Asumsi bergantung” mencatat konteks asumsi yang masih diizinkan pada baris tersebut, bukan selalu himpunan ketergantungan terkecil. Misalnya baris 4 cukup bergantung pada [a] dan [c], meskipun [b] juga sedang terbuka. Memperbesar konteks dengan asumsi yang tidak digunakan tidak mengubah keabsahan langkah; yang tidak diizinkan adalah memakai asumsi yang sudah ditutup. Konvensi konteks yang sama berlaku pada tabel bukti berikutnya. 1.5 (Lanjutan) — Bukti dengan Pemisahan Kasus Aturan ∨-Eliminasi adalah salah satu aturan yang paling kuat sekaligus paling mudah disalahgunakan. Kekuatannya berasal dari kemampuannya untuk menangani disjungsi tanpa harus "memilih" salah satu disjungsi. Kita buktikan bahwa dari P ∨ Q, P → R, dan Q → R, kita dapat menurunkan R. No. | Formula | Aturan | Ketergantungan 1 | P ∨ Q | Premis | {1} 2 | P → R | Premis | {2} 3 | Q → R | Premis | {3} 4 | P | Asumsi cabang-kiri [d] | {1,2,3,d} 5 | R | →-Elim baris 2,4 | {1,2,3,d} 6 | Q | Asumsi cabang-kanan [e] | {1,2,3,e} 7 | R | →-Elim baris 3,6 | {1,2,3,e} 8 | R | ∨-Elim baris 1,4–5,6–7: tutup [d],[e] | {1,2,3} Mengapa tidak boleh dari P ∨ Q memilih P tanpa alasan? Karena kita tidak tahu apakah P benar secara individual — kita hanya tahu bahwa setidaknya satu dari P atau Q benar. Jika kita hanya mengasumsikan P dan menurunkan R, kita belum menangani kemungkinan bahwa P = 0 dan Q = 1. Untuk membuktikan bahwa R pasti benar, kita harus menunjukkan R benar dalam semua kasus yang konsisten dengan premis. Valuasi P = 0, Q = 1, R = 1 adalah contoh konkret di mana P ∨ Q benar, P → R benar, Q → R benar, R benar — argumen berhasil. Tetapi jika kita hanya mengandalkan cabang P tanpa menutup cabang Q, kita melewatkan skenario ini. Sekarang kita tunjukkan ekuivalensi antara aturan pemisahan kasus dan kondisional. Kita buktikan (P ∨ Q) → R dari (P → R) ∧ (Q → R): Asumsikan [f] bahwa P ∨ Q. Dari (P → R) ∧ (Q → R), ekstrak P → R dan Q → R. Terapkan ∨-Elim pada P ∨ Q dengan dua cabang untuk memperoleh R. Tutup asumsi [f], simpulkan (P ∨ Q) → R. Arah balik — dari (P ∨ Q) → R simpulkan (P → R) ∧ (Q → R): Untuk P → R, asumsikan [g] P, terapkan ∨-Intro₁ memperoleh P ∨ Q, terapkan MP dengan premis memperoleh R, tutup [g] memperoleh P → R. Demikian pula untuk Q → R. Dari keduanya, ∧-Intro memberikan (P → R) ∧ (Q → R). Jadi {(P→R), (Q→R)} ⊢ (P∨Q)→R dan sebaliknya — ada ekuivalensi penuh. Pembaca diminta merefleksikan: apa perbedaan antara asumsi cabang (seperti [d] dan [e] di atas) dan premis global (seperti baris 1, 2, 3)? Asumsi cabang hanya berlaku dalam subbukti tempat ia dibuka, dan ia harus ditutup sebelum meninggalkan subbukti tersebut. Premis global tidak perlu ditutup — ia tetap berlaku di seluruh bukti. 1.5 (Lanjutan) — Kontradiksi, Ledakan, dan Batas Diagnosis Salah satu fitur paling kuat dari deduksi klasik juga merupakan salah satu yang paling mudah disalahpahami: prinsip ex falso quodlibet (dari kontradiksi, sembarang formula dapat diturunkan), atau dalam bahasa deduksi natural, aturan ⊥-Eliminasi. Kita mulai dengan derivasi yang mendasar — modus tollens. No. | Formula | Aturan | Ketergantungan 1 | P → Q | Premis | {1} 2 | ¬Q | Premis | {2} 3 | P | Asumsi [h] untuk reductio | {1,2,h} 4 | Q | →-Elim baris 1,3 | {1,2,h} 5 | ⊥ | Kontradiksi dari baris 2,4 (Q dan ¬Q) | {1,2,h} 6 | ¬P | ¬-Intro: tutup [h], baris 3–5 | {1,2} Bukti modus tollens melalui reductio ini bersih: kita mengasumsikan P, menurunkan kontradiksi, dan menutup asumsi P untuk memperoleh ¬P. Perhatikan bahwa ⊥ di baris 5 dihasilkan dari konjungsi Q (baris 4) dan ¬Q (baris 2) — dua formula yang saling berkontradiksi. Logika klasik memperlakukan A dan ¬A yang keduanya benar sebagai situasi yang mustahil, sehingga dari situ segala sesuatu dapat disimpulkan. Prinsip ini — dari P dan ¬P, kita dapat menurunkan Q untuk sembarang Q — disebut prinsip ledakan (principle of explosion). Derivasinya sederhana: Baris 1: P (premis). Baris 2: ¬P (premis). Baris 3: ⊥ (kontradiksi dari 1,2). Baris 4: Q (⊥-Elim baris 3). Ini memperlihatkan bahwa himpunan premis yang tidak konsisten — yang mengandung kontradiksi — secara semantik memaksa semua formula menjadi konsekuensi. Secara semantik, Γ ⊨ C berarti semua valuasi yang memenuhi Γ juga memenuhi C. Jika Γ tidak konsisten, tidak ada valuasi yang memenuhi Γ, sehingga kondisi "semua valuasi yang memenuhi Γ…" terpenuhi secara vacuous untuk semua C. Jadi Γ tidak konsisten mengimplikasikan Γ ⊨ C untuk semua C. Implikasi praktis dari prinsip ini sangat penting dalam rekayasa sistem. Misalkan sebuah sistem memiliki aturan-aturan berikut: E (entitas ada), E → A (jika entitas ada maka akun aktif), ¬A (akun tidak aktif). Dari E dan E → A, dengan MP diperoleh A. Tetapi ¬A juga menjadi premis. Dari A dan ¬A, kontradiksi terjadi, dan dari kontradiksi ini sistem dapat "membuktikan" apa pun — termasuk klaim yang absurd. Solusinya bukan memilih kesimpulan yang diinginkan dari kontradiksi, melainkan memperbaiki spesifikasi: identifikasi premis mana yang bertabrakan dan revisi dengan mengklarifikasi makna atau menghilangkan ketidakkonsistenan. Logika tidak memilih resolusi yang "masuk akal" — ia hanya menunjukkan bahwa kontradiksi ada. Perlu dibedakan pula antara asumsi sementara yang ditutup dalam subbukti dan premis global yang inkonsisten. Dalam subbukti reductio, kita mengasumsikan A untuk ditutup — kontradiksi yang muncul hanya berlaku dalam konteks asumsi sementara itu. Tetapi jika premis global sendiri yang inkonsisten, tidak ada "penutupan" yang membantu — kumpulan premis global itu tidak mempunyai model bersama dan perlu diperiksa. Pembedaan ini perlu dijaga: P yang bernilai 0 pada satu valuasi tidak dengan sendirinya memenuhi P⊨Q untuk sembarang Q. Atom P mempunyai model-model lain, dan model P=1,Q=0 menyangkal P⊨Q. Prinsip ledakan berlaku ketika premis-premis tidak mempunyai model bersama, seperti {P,¬P}, atau ketika ⊥ telah diturunkan. 1.5 (Lanjutan) — Mengapa Aturan Inferensi Dapat Dipercaya? Setelah membangun sistem deduksi natural dengan berbagai aturan, kita perlu bertanya: apakah sistem ini dapat dipercaya? Lebih konkret, apakah setiap kesimpulan yang diturunkan mempertahankan kebenaran dari premis-premisnya? Pertanyaan ini mengarah pada soundness (kesahihan sistem): Γ⊢C menjamin Γ⊨C. Kesimpulan C sendiri baru harus tautologis apabila ia diturunkan tanpa premis. Pernyataan Soundness: Jika Γ ⊢ C (C dapat diturunkan dari Γ menggunakan aturan-aturan sistem), maka Γ ⊨ C (setiap valuasi yang memenuhi semua anggota Γ juga memenuhi C). Kita buktikan soundness untuk beberapa aturan kunci. Strategi umum: kita menunjukkan bahwa setiap aturan inferensi melestarikan kebenaran — jika semua formula yang digunakan sebagai input aturan benar di bawah valuasi v, maka formula output juga benar di bawah v. Kemudian, dengan argumen induktif pada panjang pohon derivasi, kesimpulan pada akar derivasi mengikuti asumsi-asumsi yang masih terbuka pada daun-daunnya. Lemma Soundness untuk ∧-Intro: Jika v(A) = 1 dan v(B) = 1, maka v(A ∧ B) = 1. Bukti: langsung dari definisi v(A ∧ B) = v(A) · v(B) = 1 · 1 = 1. ∎ Lemma Soundness untuk ∧-Elim₁: Jika v(A ∧ B) = 1, maka v(A) = 1. Bukti: v(A ∧ B) = v(A) · v(B) = 1 mengimplikasikan v(A) = 1 (karena nilai dalam {0,1} dan perkalian 0·x = 0). ∎ Lemma Soundness untuk →-Elim (MP): Jika v(A → B) = 1 dan v(A) = 1, maka v(B) = 1. Bukti: v(A → B) = 1 − v(A) + v(A)·v(B). Jika v(A) = 1, ini menjadi 0 + v(B) = v(B) = 1, sehingga v(B) = 1. ∎ Lemma Soundness untuk →-Intro: Jika subbukti menunjukkan bahwa dengan asumsi A kita dapat menurunkan B, maka v(A → B) = 1 untuk setiap v yang memenuhi asumsi-asumsi yang tersisa. Bukti: Pertimbangkan dua kasus. Kasus v(A) = 0: maka v(A → B) = 1 − 0 + 0·v(B) = 1, langsung benar. Kasus v(A) = 1: karena subbukti valid dan semua asumsi tersisa benar, dan kita tambahkan A dengan nilai 1, maka (secara induktif) B menjadi benar, sehingga v(B) = 1, dan v(A → B) = 0 + 1·1 = 1. ∎ Argumen induktif penuh: kita lakukan induksi pada panjang pohon derivasi (jumlah node). Kasus basis: pohon dengan satu simpul adalah sebuah asumsi A; setiap valuasi yang memenuhi konteks berisi A tentu memenuhi A. Ini tidak menyatakan bahwa A benar pada semua valuasi. Langkah induktif: setiap node non-daun diperoleh dari node-node di bawahnya melalui satu aturan inferensi. Karena (secara induktif) formula di node-node bawah benar pada valuasi yang memenuhi asumsi aktif, dan karena setiap aturan melestarikan kebenaran (lemma-lemma di atas), formula di node ini juga benar. Ini adalah sketsa argumen induksi struktural yang akan dikembangkan secara penuh di Bab 7. Soundness yang kita buktikan di sini mencakup aturan-aturan yang telah kita periksa. Sistem penuh — termasuk aturan ∨-Elim, ¬-Intro, ⊥-Elim, dan ¬¬-Elim — memiliki bukti soundness yang lebih lengkap; hasilnya bahwa sistem deduksi natural klasik memang sound terhadap semantik nilai kebenaran adalah teorema yang diketahui, dengan referensi ke sumber seperti forall x: Calgary untuk detail. Yang penting dicatat: kami belum membuktikan completeness — arah balik yang menyatakan bahwa setiap formula yang valid secara semantik dapat diturunkan. Completeness adalah teorema yang lebih dalam dan tidak dibuktikan di sini. Aturan ∧-Elim₂ memiliki pemeriksaan simetris: jika v(A∧B)=v(A)v(B)=1, maka v(B)=1. Karena itu seluruh aturan konjungsi yang dicantumkan, bersama aturan kondisional yang diperiksa, tercakup dalam subsistem pada argumen di atas. 1.6 Kasus Sulit: Apa yang Sebenarnya Dipaksa Premis? Kita telah membangun semua alat yang diperlukan. Saatnya menggunakannya pada kasus yang lebih menantang dan menunjukkan kekuatan penuh dari analisis semantik dan deduktif secara bersamaan. Pertimbangkan himpunan premis berikut: Γ = {P → (Q ∨ R), Q → S, R → S, ¬S} Klaim: Γ ⊨ ¬P. Artinya, setiap valuasi yang memenuhi keempat premis harus menghasilkan ¬P benar, atau ekuivalen, P salah. Bukti cara pertama: MT + De Morgan. Dari Q → S dan R → S, kita tahu bahwa ¬S mengimplikasikan ¬Q (MT pada Q → S, ¬S) dan ¬R (MT pada R → S, ¬S). Dari ¬Q dan ¬R: ¬Q ∧ ¬R ≡ ¬(Q ∨ R) (De Morgan). Sekarang dari P → (Q ∨ R) dan ¬(Q ∨ R), dengan MT, simpulkan ¬P. Bukti cara kedua: Reductio dengan pemisahan kasus. Asumsikan P. Dari P dan P → (Q ∨ R), dengan MP peroleh Q ∨ R. Sekarang bagi menjadi dua kasus. Kasus Q: dari Q dan Q → S, dengan MP peroleh S. Tetapi ¬S adalah premis, kontradiksi. Kasus R: dari R dan R → S, dengan MP peroleh S. Tetapi ¬S adalah premis, kontradiksi. Dalam kedua kasus muncul kontradiksi. Jadi asumsi P mengarah ke kontradiksi, sehingga ¬P. ∎ Sekarang kita tentukan seluruh model Γ. Kita cari semua valuasi yang memenuhi keempat premis. Dari ¬S, S = 0. Dari Q → S dan S = 0: Q harus 0 (karena jika Q = 1 maka S = 1, kontradiksi). Dari R → S dan S = 0: R harus 0 juga. Dari P → (Q ∨ R) = P → (0 ∨ 0) = P → 0: kondisional ini hanya benar jika P = 0 (karena P = 1 memberikan 1 → 0 = 0). Jadi satu-satunya valuasi yang memenuhi Γ adalah P = Q = R = S = 0. Kita juga periksa minimalitas himpunan premis untuk entailment ¬P. Apakah setiap premis benar-benar diperlukan? Kita lakukan dengan melepas satu premis pada satu waktu dan mencari model di mana ¬P gagal (P = 1 dan tiga premis lainnya benar). Premis yang dilepas | Model pembuktian kebutuhan premis tsb. P → (Q ∨ R) dilepas | P=1, Q=0, R=0, S=0: Q→S, R→S, ¬S semua benar; kesimpulan ¬P gagal. Q → S dilepas | P=1, Q=1, R=0, S=0: P→(Q∨R), R→S, ¬S semua benar; kesimpulan ¬P gagal. R → S dilepas | P=1, Q=0, R=1, S=0: P→(Q∨R), Q→S, ¬S semua benar; kesimpulan ¬P gagal. ¬S dilepas | P=1, Q=1, R=0, S=1: P→(Q∨R), Q→S, R→S semua benar; kesimpulan ¬P gagal. Setiap model di atas menunjukkan bahwa tanpa premis yang bersangkutan, P = 1 dapat terpenuhi bersamaan dengan tiga premis lainnya. Ini berarti setiap premis adalah esensial untuk entailment ¬P — tidak ada satu pun yang dapat dibuang tanpa melemahkan argumen. Minimalitas ini bukan tentang panjang bukti terpendek, melainkan tentang apakah setiap premis berkontribusi secara informasi pada kesimpulan. 1.6 (Lanjutan) — Sertifikat Ketidakmungkinan Analisis sebelumnya memperlihatkan himpunan premis yang konsisten — ada model yang memenuhi semua premis secara bersamaan — dan kita mencari apa yang dipaksa premis-premis itu. Sekarang kita beralih ke situasi yang berbeda: himpunan klausa yang sama sekali tidak memiliki model. Bukti ketidakterpenuhan himpunan semacam ini menjadi sertifikat ketidakmungkinan: ia menunjukkan bahwa tidak ada cara untuk menetapkan nilai kebenaran kepada variabel-variabel sehingga semua klausa terpenuhi sekaligus. Pertimbangkan formula berikut, disajikan dalam bentuk konjungsi klausa: K = (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ R) ∧ ¬R Klaim: K tidak terpenuhi (unsatisfiable). Bukti melalui unit propagation: Dari ¬R, kita peroleh R = 0. Substitusikan R = 0 ke dalam klausa kedua: ¬P ∨ 0 = ¬P, sehingga P = 0. Substitusikan R = 0 ke dalam klausa ketiga: ¬Q ∨ 0 = ¬Q, sehingga Q = 0. Sekarang klausa pertama: P ∨ Q = 0 ∨ 0 = 0. Klausa ini tidak terpenuhi. Dengan demikian tidak ada valuasi yang memenuhi K — K tidak terpenuhi. ∎ Sekarang kita tunjukkan bahwa K adalah minimal unsatisfiable: menghapus klausa mana pun menghasilkan himpunan yang satisfiable. Kita lakukan dengan memberikan model untuk setiap subhimpunan tiga klausa yang diperoleh dengan menghapus satu klausa dari K. Klausa yang dihapus | Model (P,Q,R) | Verifikasi tiga klausa tersisa Hapus (P ∨ Q) | P=0, Q=0, R=0 | (¬P∨R)=1, (¬Q∨R)=1, ¬R=1. ✓ Hapus (¬P ∨ R) | P=1, Q=0, R=0 | (P∨Q)=1, (¬Q∨R)=1, ¬R=1. ✓ Hapus (¬Q ∨ R) | P=0, Q=1, R=0 | (P∨Q)=1, (¬P∨R)=1, ¬R=1. ✓ Hapus ¬R | P=1, Q=0, R=1 | (P∨Q)=1, (¬P∨R)=1, (¬Q∨R)=1. ✓ Setiap baris di atas adalah model eksplisit — assignment konkret nilai 0 atau 1 kepada setiap variabel — yang membuktikan bahwa tiga klausa yang tersisa dapat dipenuhi bersamaan. Gabungkan ini dengan fakta bahwa keempat klausa bersama-sama tidak terpenuhi: K adalah minimal unsatisfiable. Tidak ada klausa yang "berlebihan" atau redundant dalam K. Penting untuk membandingkan K dengan Γ dari subbagian sebelumnya. Γ adalah himpunan premis yang konsisten — ada satu model (P=Q=R=S=0) yang memenuhi semua premis. K, di sisi lain, tidak memiliki model sama sekali. Perbedaan ini fundamental: himpunan yang konsisten dapat digunakan sebagai basis penalaran (kita bertanya "apa yang dipaksa premis?"); himpunan yang tidak konsisten tidak dapat digunakan demikian tanpa terlebih dahulu diperbaiki. Satu nuansa lebih lanjut yang perlu diperhatikan: ketika kita menemukan bahwa suatu himpunan klausa tidak konsisten, kita tidak dapat langsung menyimpulkan bahwa setiap klausa individual itu salah. Sebagai contoh, masing-masing dari empat klausa K dapat bernilai benar secara individual pada valuasi tertentu — yang tidak mungkin adalah keempat klausa bernilai benar bersamaan. Kontradiksi timbul dari interaksi antara klausa-klausa, bukan dari klausa tunggal. Implikasinya untuk desain sistem: menemukan kontradiksi dalam spesifikasi tidak berarti semua aturan salah — sebaliknya, kita perlu mengidentifikasi subset minimal yang bertabrakan dan memutuskan, berdasarkan pertimbangan bisnis atau ilmiah, aturan mana yang perlu direvisi. 1.7 Dari Spesifikasi Menuju Aturan Keputusan Logika proposisional bukan hanya alat teoretis — ia adalah bahasa yang tepat untuk mengekspresikan aturan-aturan keputusan dalam sistem yang konkret. Untuk mengilustrasikan proses dari spesifikasi bahasa alami ke formula proposisional, kita gunakan sebuah kasus hipotetis. Kasus ini dirancang sebagai ilustrasi pendidikan dan tidak merepresentasikan kebijakan aktual platform mana pun. Misalkan sebuah sistem akademik daring memberikan akses materi lanjutan (E) kepada pengguna berdasarkan kondisi berikut. Pengguna harus memenuhi dua jenis syarat: syarat keberadaan dan syarat pencapaian. Syarat keberadaan: pengguna harus memiliki akun aktif (A). Syarat pencapaian: pengguna harus memenuhi setidaknya dua dari tiga kriteria berikut — verifikasi identitas lulus (V), tugas selesai dengan nilai cukup (T), dan ujian lulus (U). Formulasi bahasa alami ini perlu diubah menjadi formula proposisional yang tepat. Langkah pertama: terjemahkan "setidaknya dua dari V, T, U". Kondisi ini terpenuhi ketika setidaknya dua variabel bernilai 1. Kita dapat mengekspresikannya sebagai disjungsi pasangan: M = (V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U). Perhatikan bahwa kondisi "setidaknya dua" mencakup kasus ketika ketiganya benar (V = T = U = 1), karena dalam kasus itu semua tiga pasangan terpenuhi. Ini berbeda dari "tepat dua dari tiga", yang akan mengecualikan kasus ketiga semuanya benar dan memerlukan formula yang berbeda: (V ∧ T ∧ ¬U) ∨ (V ∧ ¬T ∧ U) ∨ (¬V ∧ T ∧ U). Formula akses penuh: E = A ∧ M = A ∧ [(V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U)]. Sekarang pertimbangkan kasus konkret dengan ambang nilai 80 sebagai ilustrasi semata. Definisikan: V = 1 jika verifikasi identitas lulus (biner), T = 1 jika rata-rata nilai tugas ≥ 80, U = 1 jika nilai ujian ≥ 80. Misalkan seorang pengguna memiliki: nilai tugas 82 (T = 1 karena 82 ≥ 80), nilai ujian 76 (U = 0 karena 76 < 80), verifikasi lulus (V = 1). Maka pasangan-pasangan: V ∧ T = 1 ∧ 1 = 1. V ∧ U = 1 ∧ 0 = 0. T ∧ U = 1 ∧ 0 = 0. Jadi M = 1 ∨ 0 ∨ 0 = 1. Jika A = 1, maka E = 1 ∧ 1 = 1 — pengguna mendapatkan akses. Penting untuk memisahkan tiga lapisan dalam analisis ini. Lapisan pertama adalah masukan: nilai numerik (82, 76) dan status biner (verifikasi). Lapisan kedua adalah logika keputusan: formula proposisional E yang mengubah nilai-nilai biner menjadi keputusan akses. Lapisan ketiga adalah penafsiran hasil: apa yang dilakukan sistem ketika E = 1 atau E = 0. Logika proposisional hanya menangani lapisan kedua — ia tidak memvalidasi kebenaran data masukan, tidak memeriksa apakah nilai 82 dihitung dengan benar, dan tidak menentukan konsekuensi akses. Pemisahan lapisan ini penting agar kita tidak menuntut dari logika lebih dari yang dapat diberikannya. 1.7 (Lanjutan) — Membuktikan Dua Implementasi Identik Setelah menetapkan formula M = (V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U) sebagai ekspresi untuk kondisi "setidaknya dua dari V, T, U", kita dapat bertanya: apakah ada representasi alternatif yang ekuivalen secara logis? Jawabannya ya — dan membuktikan ekuivalensi tersebut memberikan keyakinan bahwa dua implementasi berbeda yang sama-sama diklaim mengimplementasikan aturan yang sama memang benar-benar identik. Klaim: M = (V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U) ≡ (V ∨ T) ∧ (V ∨ U) ∧ (T ∨ U) = M_CNF. Bukti naratif melalui jumlah nilai 1: Perhatikan bahwa kondisi "setidaknya dua dari tiga" setara dengan "tidak ada yang kurang dari dua bernilai 1", yaitu "paling sedikit dua bernilai 1". Ekspresi DNF langsung menangkap ini: setidaknya satu pasangan bernilai 1 berarti setidaknya dua variabel bernilai 1. Ekspresi CNF (V ∨ T) ∧ (V ∨ U) ∧ (T ∨ U) menyatakan: V atau T bernilai 1, V atau U bernilai 1, T atau U bernilai 1. Jika tepat satu di antara V, T, U bernilai 1, misalkan hanya V = 1, T = U = 0, maka T ∨ U = 0, sehingga M_CNF = 0. Jika tepat dua bernilai 1, semua klausa terpenuhi. Jika semua tiga bernilai 1, semua klausa terpenuhi. Jika tidak ada yang bernilai 1, semua klausa gagal. Jadi M_CNF = 1 tepat ketika setidaknya dua bernilai 1 — sama dengan M. Bukti aljabar: Distribusikan (V ∨ T) ∧ (V ∨ U) terlebih dahulu. Dengan distributivitas ∨ atas ∧: (V ∨ T) ∧ (V ∨ U) = V ∨ (T ∧ U) (karena (V ∨ T) ∧ (V ∨ U) = V ∧ V ∨ V ∧ U ∨ T ∧ V ∨ T ∧ U = V ∨ V∧U ∨ T∧V ∨ T∧U = V∧(⊤ ∨ U ∨ T) ∨ T∧U = V ∨ T∧U). Sekarang: (V ∨ T∧U) ∧ (T ∨ U) = V∧T ∨ V∧U ∨ T∧U∧T ∨ T∧U∧U = V∧T ∨ V∧U ∨ T∧U ∨ T∧U = (V∧T) ∨ (V∧U) ∨ (T∧U) = M. ∎ V | T | U | M (DNF) | M_CNF | E (A=1) 1 | 1 | 1 | 1 | 1 | 1 1 | 1 | 0 | 1 | 1 | 1 1 | 0 | 1 | 1 | 1 | 1 1 | 0 | 0 | 0 | 0 | 0 0 | 1 | 1 | 1 | 1 | 1 0 | 1 | 0 | 0 | 0 | 0 0 | 0 | 1 | 0 | 0 | 0 0 | 0 | 0 | 0 | 0 | 0 Kolom M dan M_CNF identik di semua baris — konfirmasi tabel atas ekuivalensi aljabar. Untuk A = 0, seluruh E = 0 tanpa melihat M, karena E = 0 ∧ M = 0. Dengan demikian tabel lengkap mencakup 16 kombinasi (2 nilai A × 8 kombinasi V,T,U). Dua implementasi — satu menggunakan DNF, satu menggunakan CNF — menghasilkan keputusan yang identik pada semua 16 input yang mungkin. Catatan semantik penting: formula E adalah fungsi Boolean murni tanpa efek samping. Ia menerima nilai-nilai biner dan menghasilkan nilai biner. Formula ini tidak memvalidasi apakah data masukan benar, tidak memeriksa apakah sistem yang mengirimkan nilai T = 1 memang sudah menghitung nilai tugas dengan benar, dan tidak menjamin bahwa nilai A = 1 mencerminkan status akun yang akurat. Kebenaran output logis bergantung sepenuhnya pada kebenaran input — garbage in, garbage out dalam arti yang paling tepat. Implementasi keputusan dapat ditulis dalam pseudocode berikut. Masukan diasumsikan telah divalidasi: aktif dan verifikasi berupa Boolean, sedangkan nilai_tugas dan nilai_ujian berupa bilangan real yang sah. function akses(aktif, verifikasi, nilai_tugas, nilai_ujian): T = (nilai_tugas >= 80) U = (nilai_ujian >= 80) M = (verifikasi and T) or (verifikasi and U) or (T and U) return aktif and M Batas 80 memakai ≥, sehingga 79 menghasilkan 0, 80 menghasilkan 1, dan 81 menghasilkan 1. Mengganti ≥ dengan > akan mengubah keputusan tepat pada nilai 80. Pemeriksaan batas numerik ini melengkapi tabel Boolean: tabel memeriksa penggabungan status, sementara uji batas memeriksa cara angka diterjemahkan menjadi status. 1.7 (Lanjutan) — Bug yang Lolos Beberapa Contoh Salah satu kegunaan terpenting analisis logis adalah mendeteksi perbedaan antara implementasi yang dimaksud dan implementasi yang ada. Bahkan implementasi yang bekerja dengan benar pada banyak test case bisa saja mengandung bug yang hanya terungkap pada input tertentu. Logika proposisional memungkinkan kita membuktikan secara pasti apakah dua implementasi identik, atau menemukan secara konstruktif contoh di mana keduanya berbeda. Pertimbangkan dua formula: implementasi benar E = A ∧ M = A ∧ [(V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U)], dan implementasi bermasalah B = (A ∧ V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U). Perbedaan: pada formula B, syarat A hanya diterapkan pada pasangan pertama (V ∧ T), tetapi tidak pada pasangan kedua (V ∧ U) dan ketiga (T ∧ U). Ini adalah bug yang sangat halus — ia melewatkan pengecekan akun aktif untuk dua dari tiga kasus. Untuk menemukan counterexample, kita cari valuasi di mana B = 1 tetapi E = 0. Ini terjadi ketika A = 0 (akun tidak aktif) tetapi setidaknya satu dari (V ∧ U) atau (T ∧ U) bernilai 1. Ambil A = 0, V = 1, T = 0, U = 1: B = (0 ∧ 1 ∧ 0) ∨ (1 ∧ 1) ∨ (0 ∧ 1) = 0 ∨ 1 ∨ 0 = 1. Tetapi E = 0 ∧ [(1 ∧ 0) ∨ (1 ∧ 1) ∨ (0 ∧ 1)] = 0 ∧ 1 = 0. Pada input ini B memberikan akses kepada pengguna yang akunnya tidak aktif — bug terbukti. Sekarang kita buktikan secara logis: apakah E → B adalah tautologi? Dengan kata lain, apakah setiap situasi yang memberikan E = 1 juga memberikan B = 1? Jika E = 1, maka A = 1 dan M = 1. Jika M = 1, maka setidaknya satu dari (V ∧ T), (V ∧ U), (T ∧ U) bernilai 1. Kasus (V ∧ T) = 1: karena A = 1, maka A ∧ V ∧ T = 1, sehingga B = 1. Kasus (V ∧ U) = 1: suku kedua B bernilai 1, sehingga B = 1. Kasus (T ∧ U) = 1: suku ketiga B bernilai 1, sehingga B = 1. Jadi E → B adalah tautologi. Sebaliknya, B → E gagal — counterexample di atas membuktikannya. Berapa banyak input dari 16 kombinasi yang menghasilkan B = 1 tetapi E = 0? Kondisi ini terpenuhi ketika A = 0 dan M = 1 (sehingga E = 0) dan [(V ∧ U) ∨ (T ∧ U)] = 1 (sehingga B = 1 melalui suku dua atau tiga). A = 0, V = 1, T = 0, U = 1: B = 1, E = 0. A = 0, V = 0, T = 1, U = 1: B = 1, E = 0. A = 0, V = 1, T = 1, U = 1: B = 1, E = 0. Jadi terdapat 3 dari 16 kombinasi yang menghasilkan perbedaan. Angka 3/16 adalah proporsi dalam ruang input formal yang berdistribusi seragam — bukan probabilitas kegagalan di dunia nyata, yang bergantung pada distribusi aktual pengguna. Perbaikan formula sangat sederhana: pindahkan A ke luar sebagai faktor global, menghasilkan E = A ∧ [(V ∧ T) ∨ (V ∧ U) ∨ (T ∧ U)], yang memastikan tidak ada akses tanpa akun aktif. 1.7 (Lanjutan) — Kesetaraan Bersyarat dan Keadaan Mustahil Dalam sistem nyata, tidak semua kombinasi nilai variabel proposisional dapat terwujud. Ketika kita mendefinisikan atom P dan Q sebagai proposisi yang berhubungan dengan satu nilai real x, struktur domain tersebut membatasi kombinasi yang mungkin — dan ini memiliki implikasi yang halus tetapi penting bagi analisis logis. Misalkan kita mendefinisikan P sebagai proposisi "x < 1" dan Q sebagai proposisi "x ≥ 1", di mana x adalah bilangan real. Pada domain bilangan real, untuk setiap x yang diberikan, tepat satu dari P atau Q bernilai 1 — tidak pernah keduanya benar sekaligus, dan tidak pernah keduanya salah sekaligus. Ini tercermin dalam premis lingkungan D = (P ∨ Q) ∧ ¬(P ∧ Q). Perhatikan bahwa pada domain bilangan real dengan interpretasi ini, hanya dua dari empat kombinasi (P, Q) yang dapat diwujudkan secara matematis oleh suatu x∈ℝ: (P=1, Q=0) untuk x < 1, dan (P=0, Q=1) untuk x ≥ 1. Kombinasi (1,1) dan (0,0) tidak memiliki representasi pada x real — keduanya adalah kombinasi yang mustahil dalam konteks interpretasi ini. Konsekuensinya yang menarik: pada lingkungan D, formula P ∨ Q memang selalu bernilai 1 — karena D memaksa setidaknya satu dari P atau Q benar. Dalam notasi semantik: D ⊨ (P ∨ Q), artinya Γ = {D} ⊨ (P ∨ Q). Tetapi (P ∨ Q) bukan tautologi ketika P dan Q diperlakukan sebagai atom bebas — kita tunjukkan bahwa pada P = Q = 0, (P ∨ Q) = 0. Perbedaan ini penting: ⊨ (P ∨ Q) berarti benar di semua valuasi; {D} ⊨ (P ∨ Q) berarti benar di semua valuasi yang memenuhi D. Bahaya timbul ketika kita melupakan premis lingkungan D dan memperlakukan hasil {D} ⊨ (P ∨ Q) sebagai jika ⊨ (P ∨ Q) — ini adalah kategori yang berbeda. Bahaya yang lebih praktis: ketika data nyata tidak mengikuti domain yang diasumsikan. Jika x entah bagaimana bernilai NaN (Not a Number — situasi yang muncul dalam floating-point), atau jika data belum tervalidasi sehingga nilai x tidak diketahui atau di luar jangkauan yang diharapkan, maka proposisi P = "x < 1" mungkin tidak terdefinisi dengan baik. Model matematis kita — yang mengasumsikan x ∈ ℝ — tidak mencakup situasi ini. Ini bukan kekurangan logika proposisional; ini adalah peringatan bahwa domain interpretasi adalah bagian integral dari spesifikasi, dan harus ditetapkan secara eksplisit sebelum analisis logis dimulai. Implikasi desain: setiap sistem yang menggunakan penalaran logis harus menetapkan domain variabelnya dengan jelas, termasuk penanganan kasus tepi seperti nilai tak terdefinisi, nilai di luar jangkauan, atau situasi yang secara fisik mustahil tetapi secara sintaktis mungkin. Logika proposisional bekerja dengan baik dalam domain yang jelas didefinisikan — di luar itu, tanggung jawab berada pada perancang sistem untuk memastikan asumsi domain terpenuhi sebelum formula-formula diterapkan. 1.7 (Lanjutan) — Penjumlah Biner: Keluaran Boolean Membawa Nilai Aritmetis Aplikasi paling elegan dari logika proposisional dalam komputasi adalah rangkaian digital, di mana nilai Boolean (0 dan 1) bukan hanya nilai kebenaran abstrak tetapi representasi konkret dari bit informasi. Penjumlah biner adalah contoh di mana formula-formula proposisional secara harfiah menghitung hasil aritmetis. Half Adder: Diberikan dua bit a, b ∈ {0, 1}, operasi penjumlahan biner menghasilkan dua bit keluaran: bit jumlah s dan bit carry c, di mana a + b = s + 2c (dalam aritmetika bilangan bulat biasa). Definisi: s = a XOR b = (a ∨ b) ∧ ¬(a ∧ b), dan c = a ∧ b. a | b | s = a⊕b | c = a∧b | s + 2c = a+b? 0 | 0 | 0 | 0 | 0 + 0 = 0 ✓ 0 | 1 | 1 | 0 | 1 + 0 = 1 ✓ 1 | 0 | 1 | 0 | 1 + 0 = 1 ✓ 1 | 1 | 0 | 1 | 0 + 2 = 2 ✓ Full Adder: Untuk menjumlahkan bit-bit multi-digit, kita perlu rangkaian yang menerima tiga masukan: a, b ∈ {0, 1} (bit yang dijumlahkan) dan c_in ∈ {0, 1} (carry masuk dari posisi sebelumnya). Keluarannya adalah s (bit jumlah) dan c_out (carry keluar). Definisi: s = a ⊕ b ⊕ c_in, dan c_out = (a ∧ b) ∨ (a ∧ c_in) ∨ (b ∧ c_in). Perhatikan bahwa c_out = 1 tepat ketika setidaknya dua dari a, b, c_in bernilai 1 — yaitu c_out adalah fungsi majority yang sama yang kita analisis di Bagian 1.4! Kita verifikasi persamaan a + b + c_in = s + 2·c_out dengan mempertimbangkan jumlah bit yang bernilai 1 di antara a, b, c_in: - Jumlah 0 bit bernilai 1: a=b=c_in=0. s = 0⊕0⊕0 = 0, c_out = 0. Persamaan: 0 = 0 + 0. ✓ - Jumlah 1 bit bernilai 1: misalnya a=1, b=c_in=0. s = 1, c_out = 0. Persamaan: 1 = 1 + 0. ✓ - Jumlah 2 bit bernilai 1: misalnya a=b=1, c_in=0. s = 1⊕1⊕0 = 0, c_out = (1∧1)∨0∨0 = 1. Persamaan: 2 = 0 + 2. ✓ - Jumlah 3 bit bernilai 1: a=b=c_in=1. s = 1⊕1⊕1 = 1, c_out = 1∨1∨1 = 1. Persamaan: 3 = 1 + 2. ✓ Contoh konkret 1 + 1 + 1 = 3 = (11)₂: s = 1 (bit satuan dari 3), c_out = 1 (bit dua dari 3). Dengan demikian output (c_out, s) = (1, 1) merepresentasikan bilangan biner 11₂ = 3. Benar. Untuk penjumlahan multi-bit, kita rangkai full adder secara berurutan. Hitung 2 + 4 = (010)₂ + (100)₂: posisi pertama (bit 0): 0 + 0 + 0 = 0, carry = 0; posisi kedua (bit 1): 1 + 0 + 0 = 1, carry = 0; posisi ketiga (bit 2): 0 + 1 + 0 = 1, carry = 0. Hasil: (110)₂ = 6. ✓ Hitung 3 + 1 = (011)₂ + (001)₂: bit 0: 1 + 1 + 0 → s=0, c=1; bit 1: 1 + 0 + 1 → s=0, c=1; bit 2: 0 + 0 + 1 → s=1, c=0. Hasil: (100)₂ = 4. ✓ Hubungan antara fungsi majority dan carry bukan kebetulan: c_out dari full adder adalah fungsi majority, karena carry keluar tepat ketika mayoritas dari tiga bit masukan bernilai 1. Pada bit, XOR sama dengan penjumlahan modulo 2: dua bit sama memberi 0 dan dua bit berbeda memberi 1. Karena penjumlahan modulo 2 asosiatif, (a⊕b)⊕c_in dan a⊕(b⊕c_in) mempunyai nilai yang sama. Tiga bit menghasilkan s=1 tepat ketika jumlah bit bernilai 1 adalah ganjil. 1.8 Keterpenuhan Sebagai Cara Mencari Jawaban Seluruh pembahasan kita tentang tabel kebenaran dan ekuivalensi logis mengandaikan kemampuan untuk memeriksa apakah suatu formula terpenuhi atau tidak. Untuk formula kecil, enumerasi lengkap semua 2ⁿ valuasi adalah pendekatan yang dapat dilakukan. Tetapi ketika n tumbuh besar, pendekatan ini menjadi tidak praktis. Bidang SAT (Boolean Satisfiability) adalah bidang yang mempelajari pertanyaan ini secara sistematis: diberikan formula proposisional, apakah ada valuasi yang memenuhinya? Formula sering disajikan dalam CNF untuk metode yang dibahas berikut. Secara formal, masalah SAT adalah: diberikan formula F, tentukan apakah F satisfiable. Sebuah model — valuasi yang membuat F bernilai 1 — adalah sertifikat positif: ia membuktikan bahwa F satisfiable dengan cara konstruktif. Untuk ketidakpenuhan (unsatisfiability), satu valuasi yang gagal tidak cukup: kita perlu alasan yang menyingkirkan semua model. Alasan itu dapat berupa sertifikat refutasi, seperti derivasi klausa kosong melalui resolusi. Sertifikat tersebut dapat diperiksa langkah demi langkah; panjang sertifikat tidak otomatis kecil dibandingkan ukuran formula. Ini berbeda dari mengklaim bahwa tidak mungkin ada sertifikat ketidakpenuhan yang singkat. Hubungan dengan konsekuensi semantik: untuk memeriksa apakah Γ ⊨ C, kita menggunakan teorema dari Bagian 1.3: Γ ⊨ C jika dan hanya jika formula F_Γ ∧ ¬C tidak terpenuhi, di mana Γ berhingga dan F_Γ adalah konjungsi semua premis dalam Γ. Jadi pertanyaan entailment direduksi menjadi pertanyaan SAT atas negasi. Sebagai ilustrasi metode sederhana yang disebut unit propagation, kita gunakan kembali formula K = (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ R) ∧ ¬R dari Bagian 1.6. Klausa ¬R adalah klausa unit — klausa yang hanya berisi satu literal. Klausa unit memaksa nilai variabelnya: dari ¬R, kita harus menetapkan R = 0. Substitusi R = 0: klausa (¬P ∨ R) menjadi (¬P ∨ 0) = ¬P — klausa unit baru, memaksa P = 0. Dengan substitusi R = 0 yang sama, klausa (¬Q ∨ R) menjadi (¬Q ∨ 0) = ¬Q — klausa unit baru, memaksa Q = 0. Substitusi Q = 0: klausa (P ∨ Q) menjadi (0 ∨ 0) = ⊥ — klausa kosong. Klausa kosong menyatakan ketidakmungkinan: ia tidak dapat dipenuhi oleh valuasi apa pun. Jadi K tidak terpenuhi, tanpa perlu mencoba semua 2³ = 8 valuasi. Beberapa catatan penting tentang skala. Untuk n variabel, terdapat 2ⁿ valuasi yang mungkin. Beberapa angka konkret: n = 4 menghasilkan 16 valuasi (dapat dienumerasi dengan mudah); n = 20 menghasilkan 1.048.576 valuasi (lebih dari satu juta — sudah tidak trivial); n = 30 menghasilkan 1.073.741.824 valuasi (lebih dari satu miliar — enumerasi lengkap tidak praktis). Contoh berukuran tiga atau empat variabel dalam bab ini dipilih agar seluruh kemungkinan masih mudah diperiksa; ukuran formula aplikasi dapat jauh melampauinya. Perlu diperhatikan dua perbedaan penting yang sering dicampuradukkan. Pertama, ukuran input formula (panjang string simbol) berbeda dari jumlah variabel (n). Formula dengan 1000 klausa masing-masing berisi 3 literal memiliki 3000 kemunculan literal, ditambah simbol penghubung, tanda kurung, dan penamaan variabel, tetapi jumlah variabelnya bisa jauh lebih kecil (misalnya 100 variabel). Jumlah valuasi dalam enumerasi lengkap adalah 2ⁿ; waktu untuk mengevaluasi satu valuasi juga dipengaruhi panjang formula. Solver tertentu dapat menghindari enumerasi lengkap. Kedua, keberadaan solver SAT yang efisien dalam praktik tidak berarti semua instance SAT dapat diselesaikan dengan cepat — SAT adalah NP-complete: ia termasuk NP (jawaban “ya” mempunyai sertifikat berupa valuasi yang bisa diverifikasi dalam waktu polinomial terhadap ukuran masukan), dan setiap masalah dalam NP dapat direduksi ke SAT dalam waktu polinomial. Apakah SAT mempunyai algoritma waktu polinomial untuk semua masukan setara dengan pertanyaan P=NP yang masih dicantumkan sebagai masalah terbuka oleh Clay Mathematics Institute saat diperiksa [R6]. NP-complete bukan berarti “setiap masukan memerlukan waktu eksponensial”. Solver modern menggunakan heuristik dan algoritma canggih yang bekerja dengan baik untuk banyak instance praktis, tetapi tidak untuk semua. 1.8 (Lanjutan) — Resolusi dan Alasan Satu Langkahnya Sah Unit propagation yang kita demonstrasikan adalah kasus khusus dari aturan inferensi yang lebih umum dan sangat kuat: aturan resolusi. Resolusi menurunkan klausa konsekuensi dari klausa yang sudah tersedia. Derivasi yang mencapai klausa kosong membuktikan ketidakpenuhan. Menemukan valuasi pemenuh memerlukan prosedur pencarian atau rekonstruksi model; penerapan satu aturan resolusi saja tidak otomatis mengeluarkan model. Aturan Resolusi: Diberikan dua klausa (A ∨ P) dan (B ∨ ¬P), di mana A dan B masing-masing adalah disjungsi literal (mungkin kosong) dan P adalah variabel, kita dapat menurunkan resolvent A ∨ B. Keabsahan aturan ini dapat dibuktikan dengan mempertimbangkan dua nilai P. Kasus P = 1: Klausa (A ∨ P) = A ∨ 1 = 1 (otomatis benar). Klausa (B ∨ ¬P) = B ∨ 0 = B. Untuk kedua klausa bernilai 1, kita butuh B = 1. Jadi nilai A∨B adalah v(A)∨1=1. Kasus P = 0: Klausa (A ∨ P) = A ∨ 0 = A. Untuk bernilai 1, butuh A = 1. Jadi nilai A∨B adalah 1∨v(B)=1. Dalam kedua kasus, jika kedua klausa induk bernilai 1, maka resolvent A ∨ B juga bernilai 1. ∎ Perlu ditekankan: resolvent adalah konsekuensi konjungsi kedua klausa induk, bukan ekuivalen. Dengan kata lain, (A ∨ P) ∧ (B ∨ ¬P) ⊨ (A ∨ B), tetapi tidak sebaliknya. Untuk melihat ini: ambil A = 1, B = 0, P = 1. Maka A ∨ B = 1 (resolvent benar). Tetapi B ∨ ¬P = 0 ∨ 0 = 0 (klausa kedua salah). Jadi model di mana resolvent benar tidak harus memenuhi kedua klausa induk. Yang penting adalah: jika kedua klausa induk dipenuhi, maka resolvent pasti dipenuhi. Mari kita terapkan pada K = (P ∨ Q) ∧ (¬P ∨ R) ∧ (¬Q ∨ R) ∧ ¬R untuk membuktikan ketidakpenuhan melalui refutasi resolusi: No. | Klausa | Diperoleh dari | Variabel resolusi 1 | (P ∨ Q) | Premis K | — 2 | (¬P ∨ R) | Premis K | — 3 | (¬Q ∨ R) | Premis K | — 4 | ¬R | Premis K | — 5 | ¬P | Resolusi baris 2,4 atas R | R 6 | ¬Q | Resolusi baris 3,4 atas R | R 7 | Q | Resolusi baris 1,5 atas P | P 8 | ⊥ (klausa kosong) | Resolusi baris 6,7 atas Q | Q Rangkaian derivasi baris 1–8 yang berakhir pada klausa kosong ⊥ adalah sertifikat refutasi: ia menyatakan bahwa kita telah menurunkan klausa yang tidak dapat dipenuhi oleh valuasi apa pun, sehingga formula asli tidak terpenuhi. Setiap langkah resolusi dapat diverifikasi secara lokal — pembaca dapat memeriksa bahwa baris 5, 6, 7, 8 mengikuti aturan resolusi dengan benar dari klausa-klausa yang dirujuk. Sertifikat refutasi ini memiliki sifat yang berguna: ia dapat dicek secara efisien, bahkan jika proses menemukannya memerlukan pencarian yang panjang. Teorema kelengkapan refutasi resolusi — bahwa jika formula CNF tidak terpenuhi maka selalu ada refutasi resolusi — adalah hasil yang signifikan, tetapi buktinya melampaui cakupan bab ini. 1.8 (Lanjutan) — Mengapa Variabel Tambahan Harus Dijelaskan Dalam praktik sistem SAT modern, teknik yang sangat umum adalah mengubah formula yang kompleks menjadi CNF dengan memperkenalkan variabel-variabel baru (tambahan). Ide ini pertama kali disistematisasi dalam konteks yang lebih umum, tetapi mekanisme dasarnya dapat dipahami melalui contoh konkret yang sederhana. Pertimbangkan formula F = (P ∧ Q) ∨ R. Formula ini bukan dalam CNF karena mengandung disjungsi (P ∧ Q) ∨ R di mana salah satu disjun adalah konjungsi. Untuk mengubahnya ke CNF, kita perkenalkan variabel baru X yang dimaksudkan untuk "mengodekan" nilai P ∧ Q. Secara formal, kita tetapkan bikondisional X ↔ (P ∧ Q), yang ekuivalen dengan (X → (P ∧ Q)) ∧ ((P ∧ Q) → X), yaitu (¬X ∨ P) ∧ (¬X ∨ Q) ∧ (X ∨ ¬P ∨ ¬Q). Ditambah klausa untuk F itu sendiri: X ∨ R. Maka formula tambahan H adalah: H = (¬X ∨ P) ∧ (¬X ∨ Q) ∧ (X ∨ ¬P ∨ ¬Q) ∧ (X ∨ R) Klaim 1: Setiap model F meluas secara unik ke model H dengan menetapkan X = P ∧ Q (nilai aritmetis dari konjungsi dalam {0,1}). Bukti: Misalkan v adalah valuasi yang memenuhi F, yaitu v(F) = 1. Tetapkan v(X) = v(P) · v(Q). Kita periksa semua klausa H. Untuk (¬X ∨ P): jika X = 1 maka P = 1 (karena X = P·Q = 1 hanya jika P = Q = 1), sehingga ¬X ∨ P = 0 ∨ 1 = 1. Jika X = 0, maka ¬X = 1, klausa benar. Untuk (¬X ∨ Q): argumen simetris. Untuk (X ∨ ¬P ∨ ¬Q): jika P = Q = 1 maka X = 1, klausa benar. Jika salah satu P atau Q bernilai 0, maka ¬P ∨ ¬Q = 1, klausa benar. Untuk (X ∨ R): karena v(F) = v((P∧Q) ∨ R) = 1, maka v(P∧Q) = 1 atau v(R) = 1. Jika v(P∧Q) = 1 maka X = 1. Jika v(R) = 1 maka R = 1. Dalam kedua kasus, X ∨ R = 1. Jadi semua klausa H terpenuhi. ∎ Klaim 2: Setiap model H yang diproyeksikan ke (P, Q, R) memenuhi F. Bukti: Misalkan v memenuhi H. Dari klausa (X ∨ R), kita tahu X = 1 atau R = 1. Jika R = 1, maka F = (P∧Q) ∨ 1 = 1. Jika X = 1, dari klausa (¬X ∨ P) = (0 ∨ P) = P = 1 dan (¬X ∨ Q) = Q = 1, sehingga P∧Q = 1, dan F = 1 ∨ R = 1. Jadi F benar. ∎ Hubungan yang benar antara F dan H: F dan H tidak ekuivalen sebagai formula atas empat variabel bebas P, Q, R, X. Counterexample: P = Q = 1, R = 0, X = 0. Maka F = (1∧1) ∨ 0 = 1. Tetapi H: klausa (¬X∨P) = (1∨1) = 1, (¬X∨Q) = 1, (X∨¬P∨¬Q) = (0∨0∨0) = 0 — klausa ini gagal. Jadi v(H) = 0. Dengan X = 0 dan P = Q = 1, H gagal meskipun F benar. Keunikan perlu dibuktikan selain keberadaan. Tiga klausa pertama H memaksa X=P∧Q: jika P=Q=1, klausa X∨¬P∨¬Q menyusut menjadi X, sehingga X=1. Jika P=0, klausa ¬X∨P memaksa X=0; jika Q=0, klausa ¬X∨Q memaksa X=0. Jadi tidak ada pilihan X kedua untuk masukan P,Q,R yang sama. Yang benar adalah bahwa F dan H adalah ekuisatisfiable: F satisfiable jika dan hanya jika H satisfiable (sebagai formula atas {P,Q,R,X}). Lebih tepatnya, F ≡ ∃X H, dengan X menjelajahi {0,1}; ruas kanan berarti H(P,Q,R,0)∨H(P,Q,R,1). Ini adalah notasi yang mengkuantifikasikan X — pembaca dapat melihat ini sebagai pratinjau konsep kuantifikasi eksistensial yang akan dikembangkan secara formal di Bab 2. Mekanisme yang kita demonstrasikan di sini adalah esensi dari encoding variabel tambahan dalam praktik SAT, meskipun teorema umum tentang encoding semacam ini memerlukan analisis yang lebih lengkap. Untuk contoh sekecil ini, variabel tambahan sebenarnya tidak diperlukan: distributivitas langsung memberi (P∧Q)∨R ≡ (P∨R)∧(Q∨R). Contoh dengan X sengaja dipakai untuk mempelajari hubungan model. Pada formula yang lebih besar, teknik variabel tambahan berguna untuk menghindari perluasan distributif yang dapat memperbanyak suku secara tajam; analisis ukuran encoding umumnya memerlukan pembahasan tersendiri. 1.9 Jarak Antara Model dan Perhitungan Sepanjang bab ini, kita telah bekerja dalam kerangka di mana variabel-variabel proposisional memiliki nilai kebenaran yang terdefinisi dengan baik, dan di mana operasi-operasi seperti A ∧ B atau A → B dievaluasi secara mekanis. Model matematis ini sangat bersih dan konsisten. Namun ketika kita mengimplementasikan penalaran logis dalam program komputer atau sistem nyata, muncul kesenjangan antara model dan implementasi yang perlu dipahami secara eksplisit. Pertimbangkan ekspresi aritmetis 1/x pada bilangan real. Dalam matematika, fungsi f(x) = 1/x adalah fungsi yang tidak total pada ℝ — ia tidak terdefinisi untuk x = 0. Kondisional "x ≠ 0 → 1/x > 0" tampaknya menyatakan sesuatu yang bermakna, tetapi ia tidak secara otomatis "menyelesaikan" masalah pendefinisian 1/x pada x = 0. Untuk menangani ini dengan tepat, kita harus secara eksplisit membatasi domain ke ℝ \ {0}, atau menggunakan definisi fungsi yang total dengan menetapkan nilai pada x = 0 secara konvensional. Dalam kerangka proposisional, mari definisikan P sebagai "x > 0" pada domain ℝ \ {0}. Kondisional P → (1/x > 0) berarti: jika x > 0 maka 1/x > 0. Untuk x = 2: P = 1, dan 1/2 = 0.5 > 0, sehingga konsekuen benar — kondisional benar. Untuk x = −2: P = 0, dan 1/(−2) = −0.5 < 0 — konsekuen salah, tetapi kondisional benar secara vacuous (anteseden salah). Jadi kondisional P → (1/x > 0) hanya memberikan informasi berguna ketika x > 0; ia tidak memberikan informasi apakah 1/x > 0 ketika x < 0. Untuk menyimpulkan sesuatu tentang tanda 1/x ketika x < 0, kita perlu premis tambahan tentang tanda x. Dalam pemrograman, pola umum untuk menangani pembagian adalah menggunakan guard: memeriksa kondisi sebelum operasi yang berpotensi tidak terdefinisi dilakukan. Dalam pseudocode: function safe_inverse(x): if x == 0: return undefined // atau raise error return 1/x Pola guard ini memastikan bahwa operasi 1/x hanya dijalankan ketika x ≠ 0. Mekanismenya adalah alur kontrol dengan pengembalian dini: ketika x=0, fungsi berhenti sebelum mencapai pembagian. Short-circuit pada operator Boolean adalah mekanisme terkait tetapi berbeda. Keduanya merupakan aturan evaluasi program, bukan hukum kondisional material. Semantik logika proposisional klasik menetapkan nilai P→Q sebagai fungsi dari nilai P dan Q; ia tidak menentukan urutan eksekusi ataupun mewajibkan program menghitung kedua nilai dengan satu algoritma tertentu. Banyak bahasa pemrograman memang mengimplementasikan evaluasi short-circuit untuk operator AND dan OR (misalnya, dalam x != 0 && 1/x > 0, bagian 1/x > 0 tidak dievaluasi jika x == 0), tetapi ini adalah fitur implementasi, bukan konsekuensi dari semantik logika proposisional. Model matematis kita tidak serta-merta sama dengan perilaku hardware floating-point, yang memiliki representasi tersendiri untuk ketidak-hinggaan dan NaN. Konsekuensi untuk penalaran tentang pertaksamaan, yang akan menjadi tema sentral Bagian III buku ini: setiap kali kita menulis pertaksamaan seperti 1/x > 0 atau mengalikan kedua sisi pertaksamaan dengan suatu ekspresi, kita harus memastikan bahwa domain variabel terdefinisi dengan jelas dan bahwa operasi yang dilakukan valid pada seluruh domain tersebut. Mengabaikan domain adalah sumber kesalahan yang sangat umum dalam penalaran matematika. Kembali ke kondisional awal x≠0 → 1/x>0 pada domain ℝ\{0}: pada x=2, anteseden dan konsekuen benar; pada x=−2, anteseden benar tetapi konsekuen salah karena 1/(−2)=−0,5. Jadi kondisional awal tidak benar untuk semua x dalam domain itu. Menggantinya dengan x>0 → 1/x>0 memperkuat anteseden dan menghasilkan klaim berbeda yang benar. Domain x≠0 menjamin operasi terdefinisi, sedangkan syarat x>0 menjamin tanda hasil; kedua tugas ini tidak boleh dicampur. 1.9 (Lanjutan) — Dari Penalaran Proposisional Menuju Pertaksamaan Sebagai contoh konkret bagaimana penalaran proposisional menginformasikan analisis pertaksamaan, kita selesaikan secara lengkap masalah berikut: tentukan semua x ∈ ℝ yang memenuhi (x − 1)(x − 4) ≥ 0. Struktur logis masalah ini adalah: kondisi (x − 1)(x − 4) ≥ 0 terpenuhi tepat ketika kedua faktor satu tanda (keduanya positif atau keduanya negatif), atau salah satu faktor nol. Ini adalah disjungsi dua kasus: [(x − 1 ≥ 0) ∧ (x − 4 ≥ 0)] ∨ [(x − 1 ≤ 0) ∧ (x − 4 ≤ 0)]. Kita analisis masing-masing kasus. Titik kritis: x = 1 (di mana x − 1 = 0) dan x = 4 (di mana x − 4 = 0). Titik-titik ini membagi garis bilangan real menjadi tiga interval: x < 1, 1 ≤ x ≤ 4, x > 4. Kita periksa tanda setiap faktor di setiap interval. Interval | Tanda (x−1) | Tanda (x−4) | Tanda perkalian x < 1 | negatif | negatif | positif (≥ 0) ✓ x = 1 | nol | negatif | nol (= 0) ✓ 1 < x < 4 | positif | negatif | negatif (< 0) ✗ x = 4 | positif | nol | nol (= 0) ✓ x > 4 | positif | positif | positif (≥ 0) ✓ Himpunan solusi: x ≤ 1 atau x ≥ 4, atau dalam notasi interval: (−∞, 1] ∪ [4, +∞). Perhatikan bahwa titik-titik x = 1 dan x = 4 dimasukkan karena pertaksamaannya adalah ≥ 0 (bukan > 0 yang akan mengecualikannya). Verifikasi dengan nilai konkret: x = 0 memberikan (−1)(−4) = 4 > 0. ✓ x = 2 memberikan (1)(−2) = −2 < 0. ✗ x = 5 memberikan (4)(1) = 4 > 0. ✓ Perhatikan bahaya yang muncul jika kita salah menangani logika. Klaim "x ≥ 1 atau x ≥ 4 adalah solusi" adalah keliru — ia memasukkan x = 2 (yang memberikan nilai negatif) dan melewatkan x = 0 (yang memberikan nilai positif). Klaim ini menggunakan disjungsi dari dua kondisi satu-sisi, tetapi kondisi yang benar mula-mula diperoleh sebagai disjungsi dua konjungsi tanda faktor; sesudah disederhanakan hasilnya ialah (x ≤ 1) ∨ (x ≥ 4). Kesalahan dalam mengidentifikasi struktur logis langsung menghasilkan jawaban yang salah. Analisis ini adalah contoh penerapan penalaran disjungtif: lima baris analisis tanda mencakup seluruh garis real tanpa tumpang tindih. Dari pembagian lengkap itu, kita memilih baris yang memenuhi pertaksamaan, lalu menggabungkannya menjadi dua wilayah solusi, x≤1 dan x≥4. Kedua wilayah solusi itu saling asing, tetapi tidak mencakup seluruh ℝ: interval (1,4) justru harus ditolak. Ini persis struktur ∨-Eliminasi dalam deduksi natural — bedanya adalah bahwa semantik aritmetis memverifikasi komponen-komponennya, bukan tabel kebenaran proposisional. Bagian III buku ini akan mengembangkan teori pertaksamaan secara lebih lengkap; contoh di sini adalah jembatan yang menunjukkan bagaimana penalaran logis mengalir ke analisis matematis. 1.9 (Lanjutan) — Mengapa Bab Berikutnya Memerlukan Kuantifikator Kita menutup bab ini dengan merefleksikan batas fundamental dari logika proposisional dan motivasi untuk melampaui batas tersebut. Batasan ini bukan kelemahan teknis yang perlu diperbaiki — melainkan batas yang bersifat prinsipil dan informatif tentang apa yang dapat dan tidak dapat dinyatakan dalam kerangka yang telah kita bangun. Perhatikan empat bilangan: 1, 2, 4, 8. Keempat bilangan ini adalah pangkat 2 (2⁰, 2¹, 2², 2³). Apakah kenyataan ini membuktikan bahwa "setiap bilangan bulat positif berbentuk 2ᵏ untuk suatu bilangan bulat k≥0"? Tentu tidak — bilangan 3 adalah counterexample langsung. Namun pernyataan "setiap bilangan bulat positif berbentuk 2ᵏ untuk suatu bilangan bulat k≥0" dapat diberi satu nama atom, misalnya P, tetapi struktur “setiap bilangan” di dalamnya tidak terwakili oleh penghubung proposisional. Agar objek dan hubungan dalam pernyataan itu dapat dianalisis, kita memerlukan predikat dan kuantifikator. Bahasa proposisional finitari sendiri tidak mempunyai simbol untuk mengikat variabel objek melalui “untuk setiap x dalam suatu domain”. Pernyataan universal semacam ini memerlukan kuantifikator universal ∀. Demikian pula, pernyataan eksistensial "ada y yang lebih besar dari x" memerlukan kuantifikator eksistensial ∃. Dua pernyataan berikut terlihat mirip tetapi secara logis sangat berbeda: - ∀x ∃y (y > x): Untuk setiap x ∈ ℝ, ada y ∈ ℝ yang lebih besar dari x. Ini BENAR — ambil y = x + 1. - ∃y ∀x (y > x): Ada suatu y ∈ ℝ yang lebih besar dari semua x ∈ ℝ. Ini SALAH — untuk sembarang y yang dipilih, ambil x = y; maka y > y adalah kontradiksi. Perbedaan antara keduanya bukan sekadar urutan simbol — ia mencerminkan perbedaan mendalam tentang apakah pilihan y bergantung pada x (dalam ∀x ∃y, kita memilih y setelah mengetahui x, sehingga y boleh bergantung pada x) atau tidak (dalam ∃y ∀x, y harus dipilih sebelum x diketahui, sehingga y harus bekerja untuk semua x sekaligus). Kemampuan untuk mengekspresikan ketergantungan ini secara tepat adalah salah satu kekuatan terbesar logika predikat (logika orde pertama) dibandingkan logika proposisional. Ada juga perbedaan struktural yang fundamental: formula proposisional adalah ekspresi berhingga yang menyatakan sesuatu tentang berhingga banyak atom. Kita tidak dapat menuliskan konjungsi tak hingga "P₁ ∧ P₂ ∧ P₃ ∧ …" sebagai formula dalam bahasa proposisional finitari yang kita gunakan. Pernyataan "setiap bilangan asli memiliki sifat X" memerlukan kuantifikasi universal atas domain yang tak hingga — di sinilah logika predikat dan pada akhirnya teori himpunan mengambil alih. Kita tutup dengan merangkum penguasaan yang telah dicapai dalam bab ini. Untuk setiap masalah penalaran, kita sekarang dapat mengidentifikasi: domain apa yang menjadi konteks pernyataan, premis-premis apa yang diasumsikan, target apa yang ingin dicapai, dan alasan apa yang menghubungkan premis dengan target — baik melalui analisis semantis (tabel kebenaran, counterexample) maupun melalui derivasi formal (deduksi natural, resolusi). Penguasaan ini bukan klaim bahwa semua masalah dapat diselesaikan dengan logika proposisional, melainkan kepastian tentang kapan kerangka ini berlaku dan bagaimana menerapkannya dengan tepat. Bab 2 akan membawa kita melangkah ke dunia kuantifikator, di mana pernyataan "untuk semua x" dan "ada x" dapat ditangani dengan presisi yang sama. Latihan Penyelidikan — Diagnosis dan Konstruksi Dua belas latihan berikut dirancang untuk menguji pemahaman yang sesungguhnya, bukan sekadar kemampuan mengikuti prosedur. Setiap soal meminta pembaca untuk melakukan sesuatu — menemukan, membuktikan, memperbaiki, atau menganalisis — bukan hanya menghitung. Soal-soal tersusun secara berjenjang dalam kompleksitas tetapi tidak mengikuti satu template yang kaku. L1 — Countermodel dan tanda kurung: Tunjukkan bahwa (P → Q) → R dan P → (Q → R) adalah formula yang berbeda secara logis dengan menemukan valuasi yang membedakannya. Jelaskan mengapa countermodel yang kamu temukan membuktikan bahwa keduanya tidak ekuivalen, bukan hanya bahwa keduanya berbeda dalam satu kasus. L2 — Negasi kondisional majemuk: Misalkan F=P→(Q∨R). Tuliskan negasi ¬F, lalu sederhanakan dengan definisi kondisional dan hukum De Morgan. Sebutkan hukum pada setiap langkah. Verifikasi bahwa F dan ¬F bernilai berlawanan pada setiap valuasi, sedangkan ¬F dan bentuk sederhana hasilmu selalu bernilai sama. L3 — Syarat perlu dan cukup: Misalkan P menyatakan "x = 2" dan Q menyatakan "x² = 4", di mana x ∈ ℝ. (a) Apakah P adalah syarat cukup untuk Q? Apakah P adalah syarat perlu untuk Q? Berikan alasan dengan mencari atau membuktikan ketiadaan counterexample. (b) Tuliskan pernyataan bikondisional P ↔ Q dan tentukan apakah ia benar untuk semua x ∈ ℝ atau hanya untuk sebagian. L4 — Argumen tidak valid: Pertimbangkan argumen: premis P → Q, premis R → Q, premis P; kesimpulan R. Tunjukkan bahwa argumen ini tidak valid dengan menemukan valuasi eksplisit di mana ketiga premis benar tetapi kesimpulan salah. Kemudian identifikasi: pola penalaran keliru apa yang digunakan argumen ini? L5 — Ekuivalensi dengan kondisional disjungtif: Buktikan bahwa (P → R) ∧ (Q → R) ≡ (P ∨ Q) → R melalui derivasi aljabar (gunakan definisi → dan hukum-hukum Boolean). Verifikasi dengan tabel kebenaran tiga variabel. L6 — Analisis formula empat variabel: Untuk formula F = S ∧ [(P ∧ R) ∨ (¬P ∧ Q)] dari Bagian 1.4: (a) Hitung jumlah valuasi (dari 16 kemungkinan untuk P, Q, R, S) yang membuat F bernilai 1. Tunjukkan cara menghitungnya secara sistematis tanpa membuat seluruh tabel 16 baris. (b) Berikan dua valuasi konkret di mana F = 1 dan dua di mana F = 0. L7 — Membuang premis untuk melemahkan entailment: Dari himpunan Γ = {P → (Q ∨ R), Q → S, R → S, ¬S} di Bagian 1.6, kita buktikan Γ ⊨ ¬P. Tugasmu: buang tepat satu premis dari Γ sehingga ¬P bukan lagi konsekuensi dari tiga premis yang tersisa. Berikan model eksplisit yang memenuhi tiga premis tersisa tetapi tidak ¬P. Petunjuk: Bagian 1.6 sudah menunjukkan model untuk setiap kasus pelepasan premis — identifikasi premis mana yang ingin kamu lepas dan ambil model yang disediakan di sana. L8 — Tepat dua dari tiga: Tuliskan formula proposisional yang bernilai 1 tepat ketika dua dari tiga variabel V, T, U bernilai 1 (bukan setidaknya dua, tetapi tepat dua). Tunjukkan bahwa formulamu bernilai 0 ketika V = T = U = 1 (berbeda dengan fungsi majority). Berikan interpretasi mengapa "tepat dua" lebih ketat dari "setidaknya dua" dalam konteks aturan keputusan. L9 — Full adder untuk input 0,1,1: Hitung output full adder (s, c_out) untuk input a = 0, b = 1, c_in = 1 menggunakan definisi s = a ⊕ b ⊕ c_in dan c_out = (a ∧ b) ∨ (a ∧ c_in) ∨ (b ∧ c_in). Verifikasi bahwa a + b + c_in = s + 2·c_out secara aritmetis. L10 — Proyeksi model encoding: Dalam encoding formula F = (P ∧ Q) ∨ R dengan variabel tambahan X dari Bagian 1.8: pertimbangkan valuasi P = 1, Q = 0, R = 1. (a) Berapa nilai X yang harus ditetapkan sehingga valuasi ini dapat menjadi model H? (b) Verifikasi bahwa semua klausa H terpenuhi dengan nilai X tersebut. Petunjuk: Ingat bahwa X dikodekan sebagai P ∧ Q, bukan sebagai variabel bebas. L11 — Audit bukti dengan asumsi bocor: Perhatikan "bukti" berikut yang mengklaim membuktikan Q tanpa asumsi apa pun. Baris 1: P (asumsi [a]). Baris 2: P → Q (asumsi [b]). Baris 3: Q (→-Elim baris 1,2). Baris 4: Q (tutup [a] dan [b]). Identifikasi kesalahan dalam "bukti" ini. Apa yang sebenarnya terbukti dari baris 1–3? Bagaimana memperbaiki bukti untuk mendapatkan formula yang benar-benar tanpa asumsi? L12 — Alihan ke pertaksamaan dengan analisis tanda: Tentukan semua x ∈ ℝ yang memenuhi (x + 1)(x − 3) ≤ 0. Gunakan analisis tanda faktor pada interval yang ditentukan oleh titik kritis. Nyatakan solusinya sebagai pernyataan disjungtif atau konjungtif dalam bentuk pertaksamaan, dan identifikasi struktur logis disjungsi/konjungsi mana yang relevan. Pembahasan Latihan L1–L6 L1 — Countermodel tanda kurung: Kita mencari valuasi yang memisahkan (P → Q) → R dari P → (Q → R). Ambil P = 0, Q = 0, R = 0. Formula pertama: anteseden P → Q = 0 → 0 = 1; kemudian (P → Q) → R = 1 → 0 = 0. Formula kedua: P → (Q → R) = 0 → (0 → 0) = 0 → 1 = 1. Valuasi (0, 0, 0) memberikan nilai 0 untuk formula pertama dan 1 untuk formula kedua — keduanya berbeda. Mengapa countermodel ini membuktikan non-ekuivalensi, bukan sekadar perbedaan satu kasus? Karena ekuivalensi logis (≡) didefinisikan sebagai nilai yang sama pada semua valuasi. Satu valuasi yang menunjukkan perbedaan sudah cukup untuk menunjukkan bahwa definisi ≡ tidak terpenuhi. Ini adalah simetri dengan cara kita membuktikan suatu formula bukan tautologi: satu valuasi yang memberikan nilai 0 sudah cukup. L2 — Negasi kondisional majemuk: Kita negasikan F=P→(Q∨R). Urutannya: ¬F ≡ ¬(¬P∨(Q∨R)) [definisi kondisional] ≡ ¬¬P ∧ ¬(Q∨R) [De Morgan] ≡ P ∧ (¬Q∧¬R) [negasi ganda dan De Morgan] ≡ P∧¬Q∧¬R. [asosiativitas] F salah tepat pada P=1,Q=0,R=0. Pada valuasi itulah ¬F dan bentuk P∧¬Q∧¬R benar. F dan ¬F mempunyai nilai berlawanan; ¬F dan bentuk hasil penyederhanaan mempunyai nilai sama. P | Q | R | F | ¬F | P∧¬Q∧¬R 1 | 1 | 1 | 1 | 0 | 0 1 | 1 | 0 | 1 | 0 | 0 1 | 0 | 1 | 1 | 0 | 0 1 | 0 | 0 | 0 | 1 | 1 0 | 1 | 1 | 1 | 0 | 0 0 | 1 | 0 | 1 | 0 | 0 0 | 0 | 1 | 1 | 0 | 0 0 | 0 | 0 | 1 | 0 | 0 L3 — Syarat perlu dan cukup: (a) P = "x = 2" adalah syarat cukup untuk Q = "x² = 4": jika x = 2, maka x² = 4. Benar. P bukan syarat perlu untuk Q: x = −2 memberikan x² = 4 tetapi x ≠ 2 — ini adalah counterexample untuk arah Q → P. (b) Bikondisional P ↔ Q menyatakan "x = 2 jika dan hanya jika x² = 4". Ini salah untuk x = −2: Q benar tetapi P salah. Jadi P ↔ Q bukan pernyataan yang benar untuk semua x ∈ ℝ — ia hanya benar ketika (x = 2 dan x² = 4) atau (x ≠ 2 dan x² ≠ 4). Untuk x = −2, bikondisional gagal. L4 — Argumen tidak valid: Argumen: P → Q, R → Q, P; kesimpulan R. Counterexample: P = 1, Q = 1, R = 0. Cek premis: P → Q = 1 → 1 = 1 (benar); R → Q = 0 → 1 = 1 (benar); P = 1 (benar). Cek kesimpulan: R = 0 (salah). Semua premis benar, kesimpulan salah — argumen tidak valid. Pola keliru yang digunakan: dari R → Q dan Q (yang diketahui benar), disimpulkan R — ini adalah affirming the consequent (menegaskan konsekuen) pada kondisional R → Q. L5 — Ekuivalensi kondisional disjungtif: Kita buktikan (P → R) ∧ (Q → R) ≡ (P ∨ Q) → R. Sisi kiri: (¬P ∨ R) ∧ (¬Q ∨ R). Kita gunakan distributivitas ∨ terhadap ∧ dalam arah pemfaktoran R: (¬P ∨ R) ∧ (¬Q ∨ R) = (¬P ∧ ¬Q) ∨ R (menggunakan A ∧ B ∨ C = (A ∨ C) ∧ (B ∨ C) dibalik, atau langsung: jika R = 1 keduanya benar; jika R = 0 butuh ¬P = 1 dan ¬Q = 1). Lebih tepat: (¬P ∨ R) ∧ (¬Q ∨ R) = R ∨ (¬P ∧ ¬Q) (dengan distribusi R ∨ dari faktor). Sisi kanan: (P ∨ Q) → R = ¬(P ∨ Q) ∨ R = (¬P ∧ ¬Q) ∨ R. Keduanya sama. ∎ L6 — Jumlah model formula empat variabel: Untuk F = S ∧ [(P ∧ R) ∨ (¬P ∧ Q)], kita hitung model dengan cara sistematis. F = 1 memerlukan S = 1 dan [(P ∧ R) ∨ (¬P ∧ Q)] = 1. Kasus P = 1: (P ∧ R) ∨ (¬P ∧ Q) = R ∨ 0 = R. Butuh R = 1. Q bebas (0 atau 1). Memberikan 2 valuasi: (P,Q,R,S) = (1,0,1,1) dan (1,1,1,1). Kasus P = 0: (P ∧ R) ∨ (¬P ∧ Q) = 0 ∨ Q = Q. Butuh Q = 1. R bebas (0 atau 1). Memberikan 2 valuasi: (0,1,0,1) dan (0,1,1,1). Total: 4 model dari 16 kombinasi. Dua contoh F = 1: (1,0,1,1) dan (0,1,0,1). Dua contoh F = 0: (1,0,0,1) karena P=1 dan R=0 memberikan ekspresi dalam kurung = 0; (1,0,1,0) karena S = 0. Verifikasi tabel untuk L5: P | Q | R | (P→R)∧(Q→R) | (P∨Q)→R 1 | 1 | 1 | 1 | 1 1 | 1 | 0 | 0 | 0 1 | 0 | 1 | 1 | 1 1 | 0 | 0 | 0 | 0 0 | 1 | 1 | 1 | 1 0 | 1 | 0 | 0 | 0 0 | 0 | 1 | 1 | 1 0 | 0 | 0 | 1 | 1 Kedua kolom terakhir identik pada delapan valuasi. Kasus P=Q=0 tetap memberi nilai 1 meskipun R=0, karena kedua anteseden yang relevan salah. Pembahasan Latihan L7–L12 L7 — Membuang premis: Dari Bagian 1.6, kita sudah menunjukkan model untuk setiap pelepasan premis. Misalkan kita melepas premis R → S. Model yang memenuhi tiga premis lainnya {P → (Q ∨ R), Q → S, ¬S} tetapi tidak ¬P: ambil P = 1, Q = 0, R = 1, S = 0. Cek: P → (Q ∨ R) = 1 → (0 ∨ 1) = 1 → 1 = 1 ✓; Q → S = 0 → 0 = 1 ✓; ¬S = 1 ✓; P = 1 sehingga ¬P = 0 ✗. Model (1,0,1,0) memenuhi tiga premis tetapi tidak ¬P. Ini membuktikan bahwa ketiga premis tanpa R → S tidak lagi memaksa ¬P. Catatan penting: model ini bukan "bukti bahwa P benar" — ia hanya menunjukkan bahwa tiga premis tersisa konsisten dengan P = 1. L8 — Tepat dua dari tiga: Formula untuk "tepat dua dari V, T, U bernilai 1" adalah disjungsi kasus di mana tepat satu variabel bernilai 0: T₂ = (V ∧ T ∧ ¬U) ∨ (V ∧ ¬T ∧ U) ∨ (¬V ∧ T ∧ U). Untuk V = T = U = 1: T₂ = (1∧1∧0) ∨ (1∧0∧1) ∨ (0∧1∧1) = 0 ∨ 0 ∨ 0 = 0. Formula T₂ memang bernilai 0 ketika ketiganya benar, sedangkan fungsi majority M bernilai 1. Interpretasi kontekstual: aturan "tepat dua" menciptakan zona yang lebih sempit dari "setidaknya dua" — ia memasukkan kondisi setidaknya dua tetapi mengeluarkan kasus ketiga semuanya memenuhi syarat. Contoh pemodelan yang lebih langsung adalah memilih tepat dua dari tiga kegiatan ketika anggaran hanya membiayai dua. Dalam contoh itu, V,T,U harus ditafsirkan sebagai status kegiatan yang dipilih, bukan keberhasilan verifikasi. Satu formula dapat dipakai pada penafsiran berbeda, tetapi alasan memilih “tepat dua” perlu dinyatakan dalam spesifikasi. L9 — Full adder input 011: Input: a = 0, b = 1, c_in = 1. Hitung s = a ⊕ b ⊕ c_in = 0 ⊕ 1 ⊕ 1. Langkah: 0 ⊕ 1 = 1, kemudian 1 ⊕ 1 = 0. Jadi s = 0. Hitung c_out = (a ∧ b) ∨ (a ∧ c_in) ∨ (b ∧ c_in) = (0∧1) ∨ (0∧1) ∨ (1∧1) = 0 ∨ 0 ∨ 1 = 1. Jadi c_out = 1. Verifikasi aritmetis: a + b + c_in = 0 + 1 + 1 = 2. s + 2·c_out = 0 + 2·1 = 2. ✓ Output (c_out, s) = (1, 0) merepresentasikan bilangan biner 10₂ = 2. Benar. L10 — Proyeksi model encoding: Valuasi P = 1, Q = 0, R = 1. Nilai X harus ditetapkan sebagai P ∧ Q = 1 ∧ 0 = 0. Jadi X = 0. Verifikasi klausa H: (¬X ∨ P) = (1 ∨ 1) = 1 ✓; (¬X ∨ Q) = (1 ∨ 0) = 1 ✓; (X ∨ ¬P ∨ ¬Q) = (0 ∨ 0 ∨ 1) = 1 ✓; (X ∨ R) = (0 ∨ 1) = 1 ✓. Semua klausa terpenuhi dengan X = 0. Perhatikan: jika kita mencoba X = 1 untuk valuasi yang sama, klausa (X ∨ ¬P ∨ ¬Q) = (1 ∨ 0 ∨ 1) = 1 masih terpenuhi, tetapi klausa (¬X ∨ Q) = (0 ∨ 0) = 0 gagal. Jadi X = 0 adalah satu-satunya nilai yang memungkinkan — perpanjangan unik terbukti untuk kasus ini. L11 — Audit bukti dengan asumsi bocor: Kesalahan pada baris 4 bukan sekadar menutup dua asumsi sekaligus. Kesalahan utamanya adalah menghapus ketergantungan pada asumsi sambil mempertahankan Q sebagai kesimpulan tanpa syarat. Baris 1–3 hanya membuktikan {P,P→Q}⊢Q. Dalam susunan subbukti yang membuka [a] lebih dahulu lalu [b], kita menutup [b] sebelum [a]: No. | Formula | Alasan | Asumsi terbuka 1 | P | Asumsi [a] | {a} 2 | P→Q | Asumsi [b] | {a,b} 3 | Q | →-Elim 1,2 | {a,b} 4 | (P→Q)→Q | →-Intro 2–3, tutup [b] | {a} 5 | P→((P→Q)→Q) | →-Intro 1–4, tutup [a] | {} Jadi formula tanpa asumsi yang diperoleh adalah P→((P→Q)→Q), bukan Q. Verifikasi semantiknya: jika P=0, kondisional luar benar. Jika P=1, maka P→Q bernilai sama dengan Q, sehingga kondisional dalam bernilai Q→Q=1. Rumus (P→Q)→((P→Q)→Q) yang muncul dalam draf asal bukan tautologi: P=Q=0 membuat P→Q=1 dan keseluruhan rumus itu bernilai 0. Menunjukkan penyangkal bagi rumus yang salah membantu memastikan bahwa koreksi bukan hanya perubahan notasi. L12 — Pertaksamaan dengan analisis tanda: Tentukan x ∈ ℝ yang memenuhi (x + 1)(x − 3) ≤ 0. Titik kritis: x = −1 (di mana x + 1 = 0) dan x = 3 (di mana x − 3 = 0). Analisis tanda pada tiga interval: (i) x < −1: (x+1) < 0, (x−3) < 0, perkalian > 0 — tidak memenuhi ≤ 0; (ii) −1 ≤ x ≤ 3: (x+1) ≥ 0, (x−3) ≤ 0, perkalian ≤ 0 — memenuhi; (iii) x > 3: (x+1) > 0, (x−3) > 0, perkalian > 0 — tidak memenuhi. Titik kritis: x = −1 dan x = 3 memberikan perkalian = 0 ≤ 0, memenuhi. Solusi: −1 ≤ x ≤ 3, atau [−1, 3]. Struktur logis: solusi adalah konjungsi (x ≥ −1) ∧ (x ≤ 3) — interval tertutup. Ini berbeda dari soal sebelumnya di mana solusi adalah disjungsi dua interval tidak terhubung. Perbedaan struktur logis (∧ vs ∨) mencerminkan perbedaan arah ketidaksamaan faktor: perkalian dua faktor ≤0 ketika tandanya berlawanan atau setidaknya satu faktor nol. Untuk faktor x+1 dan x−3, kondisi yang mungkin disederhanakan menjadi x+1≥0 dan x−3≤0, sehingga diperoleh interval tersebut. Catatan Rujukan dan Cara Membaca Bukti Bab ini ditulis melalui Gamma dari brief berbasis riset, kemudian ditelaah dan dikoreksi dalam versi TXT ini. Definisi dan teorema yang dibahas merupakan materi standar logika. Contoh terhitung dan alur penjelasan dikembangkan untuk naskah ini; tidak ada klaim bahwa pola bukti atau contoh matematis sederhana tersebut merupakan penemuan baru. Rujukan berikut digunakan untuk memeriksa konsep dan memberi jalur bacaan lebih lanjut. [R1] Richard Hammack — Book of Proof Edisi 3.4, Bab 2 (§2.1–2.6, §2.8–2.12). Tersedia bebas di: richardhammack.github.io/BookOfProof (https://richardhammack.github.io/BookOfProof/Main.pdf). Diakses 1 Oktober 2026. Pemetaan ke bab ini: Buku ini membangun bahasa pernyataan dan ekuivalensi logis dengan gaya yang ramah untuk pembaca yang baru pertama kali bertemu logika formal. Bagian 2.1–2.4 membahas pernyataan dan penghubung, §2.5 tabel kebenaran, serta §2.6 ekuivalensi. Bagian 2.8–2.12 melanjutkan pembahasan kondisional, penerjemahan kalimat, negasi, inferensi, dan catatan tentang bentuk serta isi pernyataan. Pembaca yang ingin melihat presentasi alternatif tentang kondisional material dan ekuivalensi dapat membandingkan dengan Bagian 1.2–1.3 kita. [R2] Magnus, Button, Trueman, Zach — forall x: Calgary Versi HTML Fall 2025, revisi 27 September 2026. Tersedia di: forallx.openlogicproject.org (https://forallx.openlogicproject.org/html/). Bab yang relevan: Bab 12 (Semantic Concepts), Bab 16 (Natural Deduction), Bab 45 (Normal Forms), Bab 48 (Soundness). Diakses 1 Oktober 2026. Pemetaan ke bab ini: Buku ini menyajikan deduksi natural dan konsekuensi semantik dengan ketelitian yang sangat tinggi, dan merupakan referensi utama untuk pernyataan soundness dan completeness penuh sistem klasik yang disebut di Bagian 1.5 kita. Bab 45 tentang bentuk normal melengkapi Bagian 1.4 kita dengan perspektif yang berbeda. Sistem notasi buku ini sedikit berbeda dari yang kita gunakan; pembaca perlu memperhatikan perbedaan konvensi. [R3] Lehman, Leighton, Meyer — Mathematics for Computer Science (MIT) 18 Mei 2015, Bab 3 §3.2–3.5. Tersedia di: ocw.mit.edu (https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_042js15_textbook.pdf). Diakses 1 Oktober 2026. Pemetaan ke bab ini: Bagian 3.2–3.5 membahas proposisi, kondisional, dan logika dalam konteks matematika komputasional — sangat relevan untuk pembaca yang datang dari latar belakang pemrograman. Diskusi tentang encoding variabel tambahan dan penjumlahan biner dalam Bagian 1.7–1.8 kita dapat dibandingkan dengan presentasi komputasional buku ini. Perlu diingat bahwa penautan logika ke komputasi tidak berarti semua formula dapat disederhanakan secara cepat atau efisien. [R4] Alcock & Sa — How do Introduction-to-Proof Textbooks Explain Conditionals and Implications? International Journal of Research in Undergraduate Mathematics Education 12, 113–140 (2026). Pertama terbit daring 13 Maret 2025. DOI: 10.1007/s40753-024-00263-1 (https://doi.org/10.1007/s40753-024-00263-1). Diakses 1 Oktober 2026. Pemetaan ke bab ini: Studi kualitatif ini menganalisis tujuh belas buku teks pengantar bukti matematis dan menemukan bahwa banyak buku tidak membedakan secara konsisten tiga hal: kondisional pada satu objek konkret, pernyataan universal tentang domain, dan konsekuensi logis antara formula. Temuan ini menginformasi keputusan editorial di Bagian 1.2 kita untuk membedakan ketiga level ini secara eksplisit. Penelitian ini bukan eksperimen yang membuktikan metode pengajaran tertentu lebih efektif, melainkan analisis deskriptif tentang praktik penulisan buku teks. [R5] Hodds, Alcock, Inglis — Self-Explanation Training Improves Proof Comprehension Journal for Research in Mathematics Education 45(1), 62–101 (2014). DOI: 10.5951/jresematheduc.45.1.0062 (https://doi.org/10.5951/jresematheduc.45.1.0062). Naskah penulis: mjinglis.github.io (https://mjinglis.github.io/files/JRME_SelfExpl_Paper.pdf). Diakses 1 Oktober 2026. Pemetaan ke bab ini: Tiga eksperimen dalam studi ini mendukung efektivitas latihan yang meminta pembaca menjelaskan hubungan antarbaris bukti dalam kata-kata sendiri, dalam konteks peserta penelitian tertentu. Temuan ini menjadi dasar keputusan editorial untuk menyertakan pertanyaan reflektif di akhir bukti-bukti utama, seperti "asumsi mana yang dipakai?", "mengapa langkah ini sah?", dan "apa yang gagal jika syarat dilepas?". Studi ini tidak membuktikan bahwa teks yang lebih panjang selalu lebih baik, atau bahwa efektivitasnya berlaku tanpa pengujian untuk konteks pembelajaran daring Arstema Academy. Sebagai penutup bab, beberapa saran tentang cara membaca bukti yang produktif. Untuk menguji pemahaman sendiri, pembaca perlu mencoba lebih dari mengikuti urutan simbol yang sudah tertulis. Setelah membaca setiap bukti dalam bab ini, cobalah melakukan empat hal berikut secara aktif. Pertama, tuliskan alasan setiap langkah dalam kata-katamu sendiri. Bukan hanya nama aturannya ("→-Elim"), tetapi mengapa aturan itu boleh diterapkan di sini — syarat apa yang terpenuhi, dan apa yang dihasilkan. Kedua, ubah satu syarat dalam bukti dan telusuri apa yang berubah. Misalnya, jika bukti menggunakan P → Q dan P, apa yang terjadi jika kita ganti P dengan ¬P? Apakah bukti masih berjalan? Jika tidak, di mana ia gagal? Ketiga, cari counterexample untuk pernyataan yang dimodifikasi. Jika teorema menyatakan A ≡ B, cobalah menentukan apakah A ≡ C untuk C yang sedikit berbeda dari B — temukan valuasi yang memisahkan A dari C. Keempat, cobalah variasi bukti: bisakah teorema yang sama dibuktikan dengan rute yang berbeda? Bab ini menyajikan beberapa teorema dengan dua cara bukti (misalnya Γ ⊨ ¬P di Bagian 1.6) justru karena variasi cara pandang memperdalam pemahaman. Naskah ini merupakan pengembangan materi pengantar pembuktian untuk Arstema Academy. Contoh aturan akses bersifat hipotetis. Efektivitas bab terhadap pembelajaran pengguna Arstema belum diuji melalui penelitian empiris. [R6] Stephen Cook — The P Versus NP Problem; Clay Mathematics Institute, deskripsi resmi masalah. https://www.claymath.org/wp-content/uploads/2022/06/pvsnp.pdf Status masalah pada laman CMI: https://www.claymath.org/millennium/p-vs-np/ Bagian tentang NP-completeness dan sertifikat dipakai untuk memeriksa catatan kompleksitas pada §1.8. Diakses 1 Oktober 2026. [R7] Rujukan konteks Goldbach. Ben Green, “Mathematics: the past, present and future — The Goldbach Conjecture”, Mathematical Institute, University of Oxford, paparan 16 November 2018; laman diperbarui 6 Mei 2025. https://www.maths.ox.ac.uk/node/30003 Joseph Malkevitch, “Does Mathematics Progress?”, AMS Feature Column, 1 Februari 2026, bagian Mathematical progress. https://mathvoices.ams.org/featurecolumn/2026/02/01/does-mathematics-progress/ Kedua rujukan ini digunakan khusus untuk konteks status konjektur Goldbach biner pada §1.1; bukan dasar pembuktian konjektur tersebut. Diakses 1 Oktober 2026.