Logika

Reductio ad Absurdum

Reductio ad absurdum (proof by contradiction)

Bentuk

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

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

Butuh 1 premis.

Kenapa boleh

Andaikan yang ingin dibuktikan salah, lalu turunkan akibat-akibatnya sampai muncul pertentangan — dengan premis yang sudah diterima, atau dengan dirinya sendiri. Pertentangan itu yang membatalkan pengandaiannya.

Contoh

Andaikan $\sqrt{2}$ rasional, jadi $\sqrt{2} = a/b$ dengan $a/b$ paling sederhana. Turunannya memberi $a$ dan $b$ keduanya genap — bertentangan dengan “paling sederhana”. Maka $\sqrt{2}$ tidak rasional.

Jebakan

Pertentangan harus benar-benar pertentangan. Menemukan hasil yang aneh atau belum pernah dilihat bukan kontradiksi; yang membatalkan pengandaian cuma $S$ dan $\lnot S$ sekaligus.

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 Logika