KB 1 — Skema kalimat valid

Kembali ke bagian induk

Cerita pengantar — penjelasan tambahan, data simulasi. Pengurus menulis “Koperasi buka dan petugas hadir”. Pengurus lain membalik urutannya menjadi “Petugas hadir dan koperasi buka”. Informasi keduanya sama. Kita ingin mengenali pola yang tetap benar sekalipun P dan Q kelak diganti dengan kalimat yang lebih panjang.

Dari cerita ke notasi dan konsep BMP. Sebuah skema memakai E, F, G sebagai tempat kalimat. Contohnya $(E \land F) \Leftrightarrow (F \land E)$ valid untuk kalimat pengisi apa pun. Untuk membuktikannya dengan pohon, cabangkan atom yang diperlukan; kedua sisi selalu mempunyai nilai yang sama.

Kelompok pola	Bentuk yang perlu dipahami
Dasar	$E \Rightarrow E$ ; $(E \land F) \Rightarrow E$ ; $E \Rightarrow (E \lor F)$
True–false	$E \land true \equiv E$ ; $E \lor false \equiv E$ ; $E \land false \equiv false$ ; $E \lor true \equiv true$
Komutatif	$E \land F \equiv F \land E$ ; $E \lor F \equiv F \lor E$
Asosiatif	$(E \land F) \land G \equiv E \land (F \land G)$ ; demikian juga untuk $\lor$
Transitif	$((E \Rightarrow F) \land (F \Rightarrow G)) \Rightarrow (E \Rightarrow G)$
Kontrapositif	$(E \Rightarrow F) \equiv (\neg F \Rightarrow \neg E)$
Distributif	$E \land (F \lor G) \equiv (E \land F) \lor (E \land G)$ ; bentuk dual menukar $\land$ dan $\lor$
Negasi	$\neg \neg E \equiv E$ ; $\neg (E \land F) \equiv \neg E \lor \neg F$ ; $\neg (E \lor F) \equiv \neg E \land \neg F$
Reduksi	$E \Rightarrow F \equiv \neg E \lor F$ ; $E \Leftrightarrow F \equiv (E \Rightarrow F) \land (F \Rightarrow E)$
Reduksi kondisional	$ite (E, F, G) \equiv (E \land F) \lor (\neg E \land G)$

Mengganti $P \Rightarrow Q$ menjadi $Q \Rightarrow P$ adalah konvers, bukan kontrapositif. Keduanya tidak otomatis ekuivalen.