Strategi Pembuktian

Bukti dengan Kontradiksi

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

Bentuk pembuktian yang mengandaikan kebalikannya, lalu menunjukkan pengandaian itu membawa ke kemustahilan. Perhatikan bahwa yang dibuktikan di sini adalah $P$ langsung, bukan sebuah implikasi.

Contoh

Membuktikan tidak ada bilangan prima terbesar: andaikan ada, sebut $p$ . Bentuk $N = 1 \cdot 2 \cdots p + 1$ . Setiap prima $\le p$ membagi $N$ dengan sisa $1$ , jadi $N$ tidak punya faktor prima — padahal setiap bilangan $> 1$ punya. Pertentangan.

Jebakan

Pertentangannya harus dengan sesuatu yang sudah diterima: premis, definisi, atau hasil yang sudah terbukti. Menemukan hasil yang tidak Anda duga bukan pertentangan.

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