Contoh soal logika proposisional

Dalam artikel ini, kita akan melihat beberapa formula dan kemungkinan penilaiannya dengan metode tabel kebenaran.

Contoh pertama

Mari kita cari kapan formula berikut bernilai benar: ϕ = (p ∧ q) ∨ ¬q. Kita tuliskan variabel proposisi p dan q ke dalam tabel:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Selanjutnya, kita tambahkan ke tabel bagian pertama formula, yaitu (p ∧ q), negasi ¬q, lalu seluruh formula:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Sekarang kita hitung nilai pada kolom ketiga, yang berupa konjungsi sederhana, dan sekaligus nilai negasinya. Untuk negasi, kita cukup menuliskan kebalikan nilai pada kolom kedua:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

Terakhir, kita hitung nilai pada kolom terakhir, yaitu seluruh formula. Dalam tabel kita, artinya kita menghitung disjungsi “antara kolom ketiga dan kolom keempat”. Hasilnya:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Contoh kedua

Soalnya sama, tetapi formulanya berbeda: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Terlihat bahwa formula ini memuat variabel proposisi p dan q beserta negasinya. Karena itu, pertama kita buat tabel dengan kedua variabel dan negasinya:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Selanjutnya, kita tambahkan formula p ∧ ¬q dan ¬p ⇒ q. Keduanya mudah dinilai, karena tabel sudah memuat penilaian setiap pernyataan dan juga negasinya. Tabelnya menjadi seperti ini:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

Terakhir, kita tinggal menilai seluruh formula, yaitu biimplikasi antara dua kolom terakhir:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Contoh ketiga

Contoh ketiga sedikit lebih rumit. Kita akan mencoba tiga variabel proposisi, sehingga perhitungan tabelnya menjadi lebih panjang. Formulanya seperti ini: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Karena ada tiga variabel proposisi, banyaknya kemungkinan penilaian adalah delapan:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Selanjutnya, kita bekerja dengan cara yang sama seperti pada contoh sebelumnya: setiap kolom kita nilai pada kedelapan baris. Tabel lengkapnya seperti ini:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Contoh keempat

Contoh ini tidak diberikan sebagai formula biasa, tetapi sebagai soal cerita. Tiga sekawan ingin datang ke sebuah pesta ulang tahun yang meriah dengan banyak makanan gratis. Namun, mereka tidak terlalu akur satu sama lain, sehingga masing-masing mengajukan syarat untuk datang ke pesta. Nama mereka Made, Joko, dan Putra. Aturannya sebagai berikut:

1. Jika Made datang, maka Joko juga datang.
2. Putra datang ke pesta atau, jika Made datang, maka Joko tidak datang.
3. Putra datang jika dan hanya jika Made tidak datang atau Joko tidak datang.

Pertanyaannya: apakah mereka semua bisa datang ke pesta? Jika tidak, siapa saja yang bisa datang tanpa melanggar aturan?

Pertama, kita harus menuliskan pernyataan-pernyataan dalam kalimat di atas dengan variabel proposisi dan formula. Misalkan variabel proposisinya M, J, dan P (Made, Joko, Putra). Setiap variabel menyatakan pernyataan seperti “Made datang ke pesta”. Aturan pertama dapat kita tulis sebagai M ⇒ J, yaitu “jika M, maka J”, atau “jika Made datang ke pesta, maka Joko datang ke pesta”.

Aturan kedua kita tulis sebagai berikut. Aturan ini diawali dengan kalimat “Putra datang ke pesta atau …”, jadi jelas kita memerlukan disjungsi. Untuk sementara, kita tulis: P ∨ … Bagian berikutnya berbunyi: “jika Made datang, maka Joko tidak datang”. Ini implikasi, dan di ruas kanannya kita masih harus memakai negasi: “Joko tidak datang” = ¬J. Seluruh implikasi menjadi M ⇒ ¬J. Implikasi ini kita gabungkan dengan disjungsi tadi: P ∨ (M ⇒ ¬J).

Aturan ketiga kita tulis sebagai berikut. Kita mulai dengan “Putra datang jika dan hanya jika”. Ini berarti biimplikasi: P ⇔ … Selanjutnya, ada “Made tidak datang atau Joko tidak datang”, yang kita tulis sebagai ¬M ∨ ¬J. Jika digabungkan: (P ⇔ (¬M ∨ ¬J)).

Sekarang semua formula kita masukkan ke dalam tabel dan kita hitung nilainya:

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Pertanyaannya, apakah ketiga anak itu bisa datang ke pesta bersama-sama. Jawabannya ada pada baris pertama. Baris ini sesuai dengan kasus ketika semua anak datang, yang ditandai dengan tiga angka 1 pada tiga kolom pertama. Apakah semua syarat terpenuhi? Syarat pertama terpenuhi (kolom keempat), syarat kedua juga (kolom kelima), tetapi syarat terakhir tidak (kolom terakhir), karena di sana ada angka 0. Artinya, jika ketiganya datang, syarat ketiga tidak terpenuhi.

Jadi, kita mencari baris yang pada posisi syarat-syarat (yaitu tiga kolom terakhir) seluruhnya berisi angka 1. Angka 1 berarti syaratnya terpenuhi. Terlihat bahwa hal ini terjadi dalam dua kasus: ketika Joko dan Putra datang, tetapi Made tidak, dan ketika hanya Putra yang datang.

Kamu juga dapat menghitungnya dengan menambahkan ke tabel formula ϕ yang merupakan konjungsi ketiga syarat. Formulanya menjadi ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J))). Formula ini menggambarkan apa yang kita inginkan, yaitu agar semua formula (semua syarat) terpenuhi. Tabelnya menjadi seperti ini:

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Beberapa contoh metode tabel kebenaran

Karena saya sudah menulis program yang dapat menyusun seluruh tabel secara otomatis dari formula yang diberikan, program itu harus kumanfaatkan dengan baik. Karena itu, berikut beberapa formula lagi beserta penyelesaiannya:

Formula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabelnya:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabelnya:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabelnya:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabelnya:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabelnya:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$