1. Terjemahkan kalimat "Program akan berhenti jika terjadi error, kecuali jika ada penanganan error" ke bentuk proposisi.
Pembahasan:
P: Program akan berhenti. Q: Terjadi error. R: Ada penanganan error. "jika..., kecuali jika..." dapat diartikan sebagai `if (Q and not R) then P`.
2. Buktikan dengan tabel kebenaran bahwa $(P \text{ and } (P \text{ or } Q))$ ekuivalen dengan $P$.
Pembahasan:
Ini adalah Hukum Penyerapan (Absorption Law).
P
Q
P or Q
P and (P or Q)
T
T
T
T
T
F
T
T
F
T
T
F
F
F
F
F
Kolom untuk P dan kolom hasil akhir identik. Maka keduanya ekuivalen.
3. Tentukan nilai kebenaran dari $if \ (not \ P \text{ and } R) \ then \ (Q \text{ if and only if } P)$ dengan interpretasi {P=F, Q=T, R=T}.
Pembahasan:
`not P` adalah `T`.
Anteseden: `(not P and R)` menjadi `(T and T)` -> `T`.
Konsekuen: `(Q if and only if P)` menjadi `(T <=> F)` -> `F`.
Keseluruhan: `if T then F` -> False.
4. Diberikan interpretasi I: {P=True, Q=False}. Tentukan nilai kebenaran kalimat $F: (if \ P \ then \ Q) \ if \ and \ only \ if \ (not \ P \ or \ Q)$
Pembahasan:
Kita evaluasi kedua sisi biimplikasi:
Sisi kiri: `(if P then Q)` menjadi `(if True then False)`, yang hasilnya adalah False.
Sisi kanan: `(not P or Q)` menjadi `(not True or False)`, yang disederhanakan menjadi `(False or False)`, hasilnya adalah False.
Keseluruhan: `(False if and only if False)`, hasilnya adalah True.
5. Apakah $(P \text{ or } Q) \text{ and } (P \text{ or } R)$ ekuivalen dengan $P \text{ or } (Q \text{ and } R)$?
Pembahasan:
Ya, ini adalah Hukum Distributif. Bisa dibuktikan dengan tabel kebenaran.
6. Tentukan apakah kalimat `if (P and Q) then (R or not R)` adalah tautologi, kontradiksi atau kontingensi tanpa tabel kebenaran.
Pembahasan:
Bagian konsekuen, `(R or not R)`, adalah sebuah tautologi yang selalu bernilai `True`. Dalam sebuah implikasi `if A then B`, jika B (konsekuen) bernilai `True`, maka keseluruhan kalimat pasti `True`, tidak peduli nilai A. Maka, kalimat ini adalah tautologi.
7. Tentukan interpretasi yang membuat `if P then (Q and R)` bernilai `True`.
Pembahasan:
Kalimat ini akan `True` selama kasus `P=True, (Q and R)=False` tidak terjadi. Ini berarti kalimat ini `True` jika `P`=`False`, ATAU jika `P`=`True` dan `Q` dan `R` keduanya `True`. Contoh: {P=F, Q=F, R=F} atau {P=T, Q=T, R=T}.
8. Konversikan notasi function `IFTHENELSE(P, AND(Q,R), OR(P,R))` menjadi notasi proposisional standar.
Pembahasan:
`if P then (Q and R) else (P or R)`
Topik 2: Pohon Semantik (Soal 9-15)
9. Gunakan Proof by Falsification untuk membuktikan validitas `(P and (P => Q)) => Q` (Modus Ponens).
Pembahasan:
Asumsikan `False`. Maka `(P and (P => Q))` harus `True`, dan `Q` harus `False`.
Agar `(P and (P => Q))` `True`, maka `P` harus `True` dan `(P => Q)` harus `True`.
Dengan `P=True` dan `Q=False`, `(P => Q)` menjadi `(T => F)`, yang mana `False`.
Ini kontradiksi dengan poin 2. Asumsi salah, kalimat valid.
10. Bangun pohon semantik untuk `if P then (Q or not P)`. Apa hasilnya?
Pembahasan:
if P then (Q or not P)
/ \
P=T P=F
| |
if T then (Q or F) if F then (Q or T)
= Q = T
/ \ |
Q=T Q=F Tutup(T)
| |
Tutup(T) Tutup(F)
Ada cabang terbuka (F) dan tertutup (T). Kalimat ini kontingensi.
11. Gunakan pohon semantik untuk menentukan apakah kalimat berikut satisfiable: `(P <=> Q) and (P and not Q)`.
Pembahasan:
(P <=> Q) and (P and not Q)
/ \
P=T P=F
| |
(T <=> Q) and (T and not Q) (F <=> Q) and (F and not Q)
= Q and not Q = F = not Q and F = F
| |
Tutup(F) Tutup(F)
Semua cabang tertutup dengan F. Kalimat ini tidak satisfiable (unsatisfiable).
12. Tentukan sifat dari `(P or Q) => (P and Q)` dengan pohon semantik.
Pembahasan:
Pohon akan menunjukkan hasil T jika P dan Q sama, dan F jika P `True` dan Q `False` (atau sebaliknya). Ini adalah kontingensi.
13. Validitas dari `(P => Q) or (Q => R)` dapat dibuktikan dengan pohon semantik. Apakah hasilnya?
Pembahasan:
Pohon semantik akan menunjukkan bahwa semua cabang tertutup dengan T. Kalimat ini valid (tautologi).
14. Gunakan Proof by Falsification pada `((P => Q) and (Q => R)) => (P => R)` (Silogisme Hipotetis).
Pembahasan:
Asumsikan `False`. Maka `((P => Q) and (Q => R))` harus `True`, dan `(P => R)` harus `False`.
Agar `(P => R)` `False`, maka `P`=`True` dan `R`=`False`.
Agar `((P => Q) and (Q => R))` `True`, maka `(P => Q)` `True` dan `(Q => R)` `True`.
Dengan P=T, agar `(P => Q)` `True`, maka `Q` harus `True`.
Dengan Q=T dan R=F, `(Q => R)` menjadi `(T => F)`, yang mana `False`.
Ini kontradiksi dengan poin 3. Asumsi salah, kalimat valid.
15. Apakah kalimat `not (P and Q)` dan `not P and not Q` ekuivalen? Jawab dengan pohon semantik.
Pembahasan:
Tidak. Pohon semantik untuk `not (P and Q) <=> (not P and not Q)` akan memiliki cabang terbuka (False), menunjukkan keduanya tidak ekuivalen.
16. Lakukan substitusi total $\{P \leftarrow (Q \text{ or } R)\}$ pada kalimat $F: if \ P \ then \ (S \text{ and } P)$.
Pembahasan:
Hasil: `if (Q or R) then (S and (Q or R))`
17. Tentukan hasil substitusi total $F \triangleleft \{(P \text{ or } S) \leftrightarrow (Q \text{ and } R), not \ S \leftrightarrow (P \text{ or } Q) \}$ pada kalimat $F: ((P \text{ and } Q) \text{ or } (not \ Q \text{ and } R)) \text{ if and only if } (not \ P \text{ or } (Q \text{ and } R))$.
Pembahasan:
Dalam kalimat F, tidak ada bagian kalimat yang cocok persis dengan $g_1 = (P \text{ or } S)$ atau $g_2 = not \ S$. Oleh karena itu, tidak ada substitusi yang terjadi. Hasilnya tetap kalimat F semula.
18. Tentukan hasil substitusi parsial (satu kemunculan terakhir) dari $\{Q \leftarrow S\}$ pada $F: (P \text{ or } Q) \text{ and } (R \text{ or } Q)$.
Pembahasan:
Hasil: `(P or Q) and (R or S)`.
19. Terjemahkan "Semua kucing takut pada anjing" ke logika predikat.
Pembahasan:
K(x): x adalah kucing. T(x,y): x takut pada y. A(y): y adalah anjing. Hasil: $(\forall x)(K(x) \rightarrow (\forall y)(A(y) \rightarrow T(x,y)))$.
20. Apa arti dari kalimat $(\exists x)(M(x) \land (\forall y)(T(y) \rightarrow S(x,y)))$?
Pembahasan:
M(x): x adalah mahasiswa. T(y): y adalah tugas. S(x,y): x menyelesaikan y. Arti: "Ada mahasiswa yang menyelesaikan semua tugas."
21. Tentukan variabel bebas dan terikat: $(\forall y)(q(y,z) \lor p(x,a))$.
Pembahasan:
Variabel terikat: y. Variabel bebas: z, x. Simbol konstanta: a.
22. Diketahui interpretasi I atas domain bilangan bulat: { a $\leftarrow$ 5, b $\leftarrow$ 10, f(d) = d+2, p(d1, d2) = (d1 adalah faktor dari d2) }. Tentukan nilai kebenaran dari kalimat `p(a, f(b))`.
Pembahasan:
Evaluasi term: $f(b)$ menjadi $f(10)$, yang hasilnya adalah $10+2=12$.
Evaluasi predikat: $p(a, f(b))$ menjadi $p(5, 12)$.
Artinya: "Apakah 5 adalah faktor dari 12?".
Hasilnya adalah False.
23. Lakukan perluasan interpretasi J dengan menambahkan variabel bebas `z` yang bernilai -5. Interpretasi awal $J = \{a \leftarrow 0, x \leftarrow 1, f \leftarrow \text{fungsi predecessor (d-1)}\}$.
Pembahasan:
Perluasan interpretasi berarti menambahkan definisi baru ke interpretasi yang sudah ada. Interpretasi yang diperluas J' adalah:
$J' = \{a \leftarrow 0, x \leftarrow 1, z \leftarrow -5, f \leftarrow \text{fungsi predecessor (d-1)}\}$.
24. Jelaskan apa artinya dua interpretasi I dan J `agree on` sebuah simbol fungsi `f`.
Pembahasan:
Artinya, untuk setiap input `d` yang sama dari domain, fungsi `f` di bawah interpretasi I ($f_I(d)$) dan fungsi `f` di bawah interpretasi J ($f_J(d)$) menghasilkan output yang sama. Definisi fungsinya identik di kedua interpretasi.
25. Tentukan klosur eksistensial dari kalimat $if \ q(a,x) \ then \ r(b,y,z)$.
Pembahasan:
Variabel bebasnya x, y, z. Hasil: $(\exists x)(\exists y)(\exists z)(if \ q(a,x) \ then \ r(b,y,z))$.
26. Berikan sebuah interpretasi dimana $(\forall x)(p(x) \lor q(x))$ bernilai `True`, tetapi $((\forall x)p(x) \lor (\forall x)q(x))$ bernilai `False`.
Pembahasan:
Domain D = {A, B}. Interpretasi I: p(A)=T, p(B)=F; q(A)=F, q(B)=T. $(\forall x)(p(x) \lor q(x))$ adalah `True` karena untuk A (T or F)=T, dan untuk B (F or T)=T. $(\forall x)p(x)$ adalah `False` (gagal di B). $(\forall x)q(x)$ adalah `False` (gagal di A). `False or False` adalah `False`.
27. Tentukan suatu interpretasi $J$ atas domain $D$=himpunan semua bilangan riil, dengan $J=\{a \leftarrow -2.5, b \leftarrow 0.0, y \leftarrow 1.5, z \leftarrow 0.5, f \leftarrow f_J(d_1,d_2)=3d_1+1.5, g \leftarrow g_J(d_1,d_2)=2(d_1+d_2)+0.5, p \leftarrow p_J(d_1,d_2): d_1 < 2d_2, q \leftarrow q_J(d_1,d_2,d_3,d_4): d_1+d_3=d_2+d_4 \}$. Lakukan perluasan terhadap interpretasi $J$ dengan memberi nilai baru terhadap simbol predikat p.
Pembahasan:
Tujuan soal ini adalah untuk memahami konsep perluasan interpretasi, di mana kita mengubah definisi dari salah satu simbol. Kita dapat memilih definisi baru apa pun untuk predikat $p$.
Contoh perluasan $J'$:
Semua definisi dalam $J$ dipertahankan, kecuali untuk $p$. Kita mendefinisikan ulang $p$ sebagai berikut:
$p \leftarrow p_{J'}(d_1,d_2): d_1 \ge d_2$
Interpretasi baru $J'$ sekarang memiliki definisi yang berbeda untuk predikat $p$ dibandingkan dengan interpretasi $J$ yang asli, sementara semua definisi simbol lainnya tetap sama.
28. Apakah kalimat $p(a) \text{ and } (\exists x)q(x,a)$ merupakan kalimat tertutup (closed)?
Pembahasan:
Ya. Sebuah kalimat tertutup jika tidak memiliki variabel bebas. Dalam kalimat ini, $a$ adalah konstanta, dan $x$ adalah variabel terikat oleh $\exists x$. Tidak ada variabel bebas, sehingga kalimat ini tertutup.
29. Tentukan klosur universal (universal closure) dari kalimat $F: p(x,y) \text{ or } (\exists z)q(x,z)$.
Pembahasan:
Klosur universal menambahkan quantifier `for all` untuk setiap variabel bebas yang ada dalam kalimat. Variabel bebas di sini adalah $x$ dan $y$. Variabel $z$ sudah terikat.
Hasil klosur universal: $(\forall x)(\forall y)(p(x,y) \text{ or } (\exists z)q(x,z))$.
30. Diketahui interpretasi I atas domain D={1, 2, 3} dimana predikat $p(d)$ adalah True jika $d$ adalah ganjil. Buatlah sebuah perluasan interpretasi $I'$ dari I dengan menambahkan konstanta `c` dan variabel `x` sehingga kalimat $p(c)$ dan $p(x)$ keduanya bernilai `True`.
Pembahasan:
Interpretasi awal $I$ hanya mendefinisikan predikat $p$. Kita perlu memperluasnya.
Untuk membuat $p(c)$ dan $p(x)$ bernilai `True`, kita perlu memberikan nilai ganjil dari domain D ke $c$ dan $x$.
Contoh perluasan yang valid:
Di bawah $I'$, $p(c)$ menjadi $p(1)$ yang bernilai `True`, dan $p(x)$ menjadi $p(3)$ yang juga bernilai `True`.