Strategi Pembuktian

Bukti dengan Kontraposisi

Proof by contraposition

Bentuk

(\lnot Q \to \lnot P) \;\;\vdash\;\; (P \to Q)

Premis-premisnya di kiri, dibaca “maka”, dan kesimpulannya di kanan.

Butuh 1 premis.

Kenapa boleh

Karena $P \to Q$ dan $\lnot Q \to \lnot P$ setara, membuktikan yang kedua sama saja dengan membuktikan yang pertama. Sering jauh lebih mudah, karena kita mulai dari $\lnot Q$ yang bentuknya lebih konkret.

Contoh

Untuk membuktikan “kalau $n^2$ genap maka $n$ genap”, buktikan kontraposisinya: “kalau $n$ ganjil maka $n^2$ ganjil”. Yang kedua itu bukti langsung yang singkat.

Jebakan

Ini bukan bukti kontradiksi, meskipun sepintas mirip. Di sini kita menurunkan $\lnot P$ dari $\lnot Q$ secara langsung, tanpa pernah memunculkan pertentangan. Menulisnya sebagai kontradiksi tidak salah, tetapi menambahkan langkah yang tidak diperlukan.

Dipakai di

Belum ada pembuktian yang memakai aturan ini — daftarnya akan terisi sendiri begitu teorema mulai ditulis, karena setiap langkah mencatat aturan yang dipakainya.

Bentuk

Kenapa boleh

Contoh

Jebakan

Dipakai di

Aturan lain di Strategi Pembuktian