1. Terjemahkan kalimat "Syarat perlu untuk mengakses sistem adalah memiliki kata sandi" ke bentuk proposisi.
Pembahasan:
P: Anda mengakses sistem. Q: Anda memiliki kata sandi. Frasa "Syarat perlu" (necessary condition) berarti jika P terjadi, maka Q pasti sudah terjadi. Ini diterjemahkan sebagai `if P then Q`.
2. Buktikan dengan tabel kebenaran bahwa $(P \text{ if and only if } Q)$ ekuivalen dengan $((if \ P \ then \ Q) \text{ and } (if \ Q \ then \ P))$.
Pembahasan:
Ini adalah definisi standar dari biimplikasi.
P
Q
P <=> Q
P => Q
Q => P
(P=>Q) and (Q=>P)
T
T
T
T
T
T
T
F
F
F
T
F
F
T
F
T
F
F
F
F
T
T
T
T
Karena kolom `P <=> Q` dan `(P=>Q) and (Q=>P)` identik, maka keduanya ekuivalen.
3. Tentukan interpretasi yang membuat kalimat $(P \text{ or } not \ Q) \text{ and } (Q \text{ or } not \ R)$ bernilai `False`.
Pembahasan:
Agar konjungsi bernilai `False`, salah satu atau kedua sisinya harus `False`.
Contoh: Buat sisi pertama `False`. `(P or not Q)` bernilai `False` jika `P`=`False` dan `not Q`=`False` (yaitu `Q`=`True`). Maka interpretasi {P=F, Q=T, R=T} akan membuat kalimat ini `False`.
4. Konversikan `if P then Q else not R` ke bentuk yang hanya menggunakan `if-then`, `not`, dan `and`.
Pembahasan:
Kalimat `if A then B else C` ekuivalen dengan `(if A then B) and (if not A then C)`. Maka hasilnya:
`(if P then Q) and (if not P then not R)`
5. Diberikan interpretasi $I = \{P \leftarrow true, Q \leftarrow false, R \leftarrow true\}$. Apa nilai dari kalimat $if \ (P \text{ and } (Q \text{ or } R)) \ then \ (Q \text{ and } R)$?
$(P \text{ and } (T)) \rightarrow (T \land T) \rightarrow T$ (Ini adalah anteseden)
$(Q \text{ and } R) \rightarrow (F \land T) \rightarrow F$ (Ini adalah konsekuen)
$if \ T \ then \ F \rightarrow F$
Hasilnya False.
6. Tentukan apakah kalimat `P and (Q or not Q)` ekuivalen dengan `P`.
Pembahasan:
Ya. Bagian `(Q or not Q)` adalah tautologi dan selalu bernilai `True`. Maka kalimat menjadi `P and True`, yang mana nilainya akan selalu sama dengan nilai `P`. Jadi, keduanya ekuivalen.
7. Gunakan tabel kebenaran untuk menentukan sifat dari `if P then (Q => P)`.
Pembahasan:
P
Q
Q => P
P => (Q => P)
T
T
T
T
T
F
T
T
F
T
F
T
F
F
T
T
Karena semua hasil `True`, kalimat ini adalah tautologi.
8. Apakah `P or Q` dan `Q or P` merupakan kalimat yang ekuivalen? Jelaskan.
Pembahasan:
Ya, ini adalah Hukum Komutatif untuk `or`. Nilai kebenaran disjungsi tidak bergantung pada urutan operan. Jika salah satunya `True`, hasilnya `True`. Jika keduanya `False`, hasilnya `False`, tidak peduli urutannya.
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 yang menghasilkan T dan F, 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. Diberikan suatu interpretasi $J$ atas (over) 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 \}$. Tentukan nilai dari term $g(a, f(b, z))$.
Pembahasan:
Kita harus mengevaluasi dari dalam ke luar.
Pertama, hitung term terdalam: $f(b, z)$. Di bawah $J$, ini menjadi $f_J(0.0, 0.5)$.
$f_J(0.0, 0.5) = 3(0.0) + 1.5 = 1.5$.
Sekarang, substitusikan hasil ini ke term luar: $g(a, f(b,z))$ menjadi $g(a, 1.5)$.
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. 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.