KB 2 — Proof by falsification (PBF)

Kembali ke bagian induk

Cerita pengantar — penjelasan tambahan, data simulasi. Aturan yang diperiksa adalah “Jika kartu berlaku dan petugas hadir, maka kartu berlaku.” Cobalah membayangkan aturan itu salah. Agar salah, bagian “kartu berlaku dan petugas hadir” harus benar, tetapi “kartu berlaku” harus salah. Kita segera mendapat dua tuntutan yang bertentangan tentang kartu yang sama.

Dari cerita ke notasi dan konsep BMP. Untuk membuktikan $(P \land Q) \Rightarrow P$ valid:

Andaikan kalimat bernilai S.
Aturan implikasi memaksa $P \land Q = B$ dan P=S.
Aturan konjungsi pada bagian benar memaksa P=B dan Q=B.
P dituntut B sekaligus S pada interpretasi yang sama. Ini mustahil.
Tidak ada interpretasi penyangkal; kalimat valid.

Tuntutan	Akibat yang harus diperiksa
$\neg E = B$ / $\neg E = S$	E=S / E=B
$E \land F = B$	E=B dan F=B
$E \land F = S$	E=S atau F=S; mungkin perlu cabang
$E \lor F = B$	E=B atau F=B; mungkin perlu cabang
$E \lor F = S$	E=S dan F=S
$E \Rightarrow F = S$	E=B dan F=S
$E \Rightarrow F = B$	E=S atau F=B
$E \Leftrightarrow F = B$	Keduanya B atau keduanya S
$E \Leftrightarrow F = S$	Nilainya berbeda

Jika ada cabang, semua cabang yang mungkin harus berakhir kontradiksi untuk membuktikan validitas. Bila satu cabang memberi penetapan lengkap yang benar-benar membuat kalimat salah, itulah contoh penyangkal. Untuk membuktikan contradictory, balik sasaran: andaikan kalimat benar dan tunjukkan semua kemungkinan mustahil.

flowchart TD
    A[Ingin membuktikan F valid] --> B[Andaikan F salah]
    B --> C[Turunkan tuntutan nilai bagian]
    C --> D{Ada beberapa kemungkinan?}
    D -->|Ya| E[Periksa semua cabang]
    D -->|Tidak| F[Lanjutkan akibat yang wajib]
    E --> G{Semua cabang bertentangan?}
    F --> G
    G -->|Ya| H[F valid]
    G -->|Tidak| I[Cari dan periksa contoh penyangkal]