Soal Latihan UAS (Set 4)

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`.

Pembahasan:

Ini adalah definisi standar dari biimplikasi.

Karena kolom `P <=> Q` dan `(P=>Q) and (Q=>P)` identik, maka keduanya ekuivalen.

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`.

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)`

Pembahasan:

1. $(Q \text{ or } R) \rightarrow (F \lor T) \rightarrow T$
2. $(P \text{ and } (T)) \rightarrow (T \land T) \rightarrow T$ (Ini adalah anteseden)
3. $(Q \text{ and } R) \rightarrow (F \land T) \rightarrow F$ (Ini adalah konsekuen)
4. $if \ T \ then \ F \rightarrow F$

Hasilnya False.

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.

Pembahasan:

Karena semua hasil `True`, kalimat ini adalah tautologi.

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.

Pembahasan:

1. Asumsikan `False`. Maka `(P and (P => Q))` harus `True`, dan `Q` harus `False`.
2. Agar `(P and (P => Q))` `True`, maka `P` harus `True` dan `(P => Q)` harus `True`.
3. Dengan `P=True` dan `Q=False`, `(P => Q)` menjadi `(T => F)`, yang mana `False`.
4. Ini kontradiksi dengan poin 2. Asumsi salah, kalimat valid.

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.

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).

Pembahasan:

Pohon akan menunjukkan hasil T jika P dan Q sama, dan F jika P `True` dan Q `False` (atau sebaliknya). Ini adalah kontingensi.

Pembahasan:

Pohon semantik akan menunjukkan bahwa semua cabang tertutup dengan T. Kalimat ini valid (tautologi).

Pembahasan:

1. Asumsikan `False`. Maka `((P => Q) and (Q => R))` harus `True`, dan `(P => R)` harus `False`.
2. Agar `(P => R)` `False`, maka `P`=`True` dan `R`=`False`.
3. Agar `((P => Q) and (Q => R))` `True`, maka `(P => Q)` `True` dan `(Q => R)` `True`.
4. Dengan P=T, agar `(P => Q)` `True`, maka `Q` harus `True`.
5. Dengan Q=T dan R=F, `(Q => R)` menjadi `(T => F)`, yang mana `False`.
6. Ini kontradiksi dengan poin 3. Asumsi salah, kalimat valid.

Pembahasan:

Tidak. Pohon semantik untuk `not (P and Q) <=> (not P and not Q)` akan memiliki cabang terbuka (False), menunjukkan keduanya tidak ekuivalen.

Pembahasan:

Hasil: `if (Q or R) then (S and (Q or 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.

Pembahasan:

Hasil: `(P or Q) and (R or S)`.

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)))$.

Pembahasan:

M(x): x adalah mahasiswa. T(y): y adalah tugas. S(x,y): x menyelesaikan y. Arti: "Ada mahasiswa yang menyelesaikan semua tugas."

Pembahasan:

Variabel terikat: y. Variabel bebas: z, x. Simbol konstanta: a.

Pembahasan:

1. Evaluasi term: $f(b)$ menjadi $f(10)$, yang hasilnya adalah $10+2=12$.
2. Evaluasi predikat: $p(a, f(b))$ menjadi $p(5, 12)$.
3. Artinya: "Apakah 5 adalah faktor dari 12?".
4. Hasilnya adalah False.

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)}\}$.

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.

Pembahasan:

Variabel bebasnya x, y, z. Hasil: $(\exists x)(\exists y)(\exists z)(if \ q(a,x) \ then \ r(b,y,z))$.

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`.

Pembahasan:

Kita harus mengevaluasi dari dalam ke luar.

1. Pertama, hitung term terdalam: $f(b, z)$. Di bawah $J$, ini menjadi $f_J(0.0, 0.5)$.
2. $f_J(0.0, 0.5) = 3(0.0) + 1.5 = 1.5$.
3. Sekarang, substitusikan hasil ini ke term luar: $g(a, f(b,z))$ menjadi $g(a, 1.5)$.
4. Di bawah $J$, ini menjadi $g_J(-2.5, 1.5)$.
5. $g_J(-2.5, 1.5) = 2(-2.5 + 1.5) + 0.5 = 2(-1.0) + 0.5 = -2.0 + 0.5 = -1.5$.

Jadi, nilai dari term tersebut adalah -1.5.

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.

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))$.

Pembahasan:

Agar kalimat bernilai `FALSE`, kita perlu menemukan setidaknya satu nilai `x` dari domain yang membuat $p(f(a), x)$ bernilai `False`.

Contoh Interpretasi I:

• Domain D: Himpunan semua bilangan bulat.
• Konstanta a: $a \leftarrow 5$.
• Fungsi f(d): $f(d) \leftarrow d + 1$.
• Predikat p(d1, d2): bernilai `True` jika $d1 > d2$.

Analisis:

1. Pertama, evaluasi term $f(a)$, yang menjadi $f(5) = 5+1 = 6$.
2. Kalimat $F$ menjadi $(\forall x)p(6, x)$.
3. Ini dibaca "Untuk semua bilangan bulat x, 6 lebih besar dari x".
4. Pernyataan ini False, karena kita dapat menemukan contoh penyangkal. Misalnya, jika kita pilih $x=7$, maka $p(6,7)$ (yaitu, 6 > 7) adalah `False`.

Karena ada satu nilai $x$ yang membuat predikatnya salah, maka kalimat dengan quantifier universal ini menjadi `False`.