Soal Latihan UAS

Pembahasan:

Contoh kalimat yang memenuhi kriteria tersebut adalah:

$if \ (P \ or \ Q) \ then \ (R \ if \ and \ only \ if \ P) \ else \ Q$

Kalimat ini menggunakan 3 simbol (P, Q, R) dan semua konektif yang diminta.

Pembahasan:

Ya, I merupakan interpretasi untuk E karena I memberikan nilai kebenaran untuk semua simbol proposisional (P, Q, R, S) yang ada di dalam kalimat E.

Pembahasan:

Dua ekspresi dikatakan ekuivalen jika mereka memiliki kolom hasil yang identik dalam tabel kebenaran.

Karena kolom hasil untuk 'if P then Q' dan 'not P or Q' identik, maka kedua ekspresi tersebut ekuivalen secara logis.

Pembahasan:

Kita substitusikan nilai-nilai kebenaran ke dalam ekspresi:

1. Evaluasi bagian dalam kurung pertama: $(P \text{ and } Q)$ menjadi $(True \text{ and } False)$, yang hasilnya adalah False.
2. Substitusikan hasil ini ke ekspresi utama: $(\text{False} \text{ or } R)$.
3. Substitusikan nilai R: $(\text{False} \text{ or } True)$.
4. Hasil akhir dari disjungsi tersebut adalah True.

Pembahasan:

Agar konjungsi (and) bernilai TRUE, kedua sisinya harus bernilai TRUE.

• $(P \text{ if and only if } Q)$ harus TRUE. Ini terjadi jika P dan Q memiliki nilai kebenaran yang sama (keduanya True atau keduanya False).
• $(not \ Q \text{ or } R)$ harus TRUE. Ini ekuivalen dengan $(if \ Q \ then \ R)$.

Kita analisis per kasus berdasarkan syarat pertama:

1. Kasus 1: P=True dan Q=True. Agar $(if \ Q \ then \ R)$ bernilai True, karena Q=True, maka R harus True. Jadi, interpretasi {P=T, Q=T, R=T} valid.
2. Kasus 2: P=False dan Q=False. Agar $(if \ Q \ then \ R)$ bernilai True, karena Q=False, R bisa True atau False. Jadi, interpretasi {P=F, Q=F, R=T} dan {P=F, Q=F, R=F} keduanya valid.

Jadi, ada 3 interpretasi yang membuat kalimat bernilai TRUE: {T, T, T}, {F, F, T}, dan {F, F, F}.

Pembahasan:

Kalimat bagiannya adalah:

• $P$
• $Q$
• $not \ Q$
• $P \text{ and } (not \ Q)$
• $P \text{ or } Q$
• $if \ (P \text{ and } (not \ Q)) \ then \ (P \ or \ Q)$

Pembahasan:

Karena hasilnya mengandung True dan False, kalimat ini kontingensi. Kalimat ini ekuivalen dengan $P \text{ if and only if } Q$.

Pembahasan:

Ya, kedua kalimat tersebut ekuivalen. Ini adalah salah satu dari Hukum De Morgan. Kita buktikan dengan tabel kebenaran:

Kolom untuk not(P and Q) dan (not P or not Q) identik, maka keduanya ekuivalen.

Pembahasan:

Kalimat valid jika semua cabang pada pohon semantiknya tertutup dengan nilai True (T).

Antecedent dari implikasi ini adalah $(P \text{ and } not \ P)$, yang merupakan sebuah kontradiksi dan akan selalu bernilai False, tidak peduli apa nilai P.

Dalam sebuah implikasi $(if \ A \ then \ B)$, jika antecedent (A) bernilai False, maka keseluruhan implikasi akan selalu bernilai True, tidak peduli nilai B.

    (if (P and not P) then Q)
              |
       [P and not P] -> selalu False
              |
     Keseluruhan kalimat -> True (T)
                        

Karena hanya ada satu jalur dan jalur tersebut langsung menghasilkan True karena sifat kontradiksi pada anteseden, maka semua cabang (yang hanya satu) tertutup dengan T. Dengan demikian, kalimat ini adalah valid (tautologi).

Pembahasan:

Kita akan membangun pohon dengan membuat cabang untuk setiap proposisi.

            (P or Q) and (not P and not Q)
                          /       \
                        P=T       P=F
                         |         |
     (T or Q) and (F and not Q)  (F or Q) and (T and not Q)
     = T and (F) = F             = Q and not Q = F
                         |         |
                         Tutup(F)  Tutup(F)
                        

Pada cabang kiri (P=T), ekspresi menjadi `(True or Q) and (False and not Q)`, yang disederhanakan menjadi `True and False`, hasilnya `False`. Cabang tertutup dengan F.

Pada cabang kanan (P=F), ekspresi menjadi `(False or Q) and (True and not Q)`, yang disederhanakan menjadi `Q and not Q`. Ini adalah kontradiksi dan selalu `False`. Cabang tertutup dengan F.

Karena semua cabang tertutup dengan nilai False, kalimat ini adalah sebuah kontradiksi.

Pembahasan:

if P then (Q or P)
      /      \
    P=T      P=F
     |        |
if T then (Q or T)   if F then (Q or F)
= if T then T        = if F then Q
= T                  = T
     |        |
   Tutup(T)   Tutup(T)

Karena semua cabang pohon tertutup dengan T (True), maka kalimat tersebut adalah tautologi (valid).

Pembahasan:

(if P then Q) or (if Q then P)
          /         \
        P=T         P=F
         |           |
(if T then Q) or   (if F then Q) or
(if Q then T)      (if Q then F)
= Q or T = T       = T or (if Q then F) = T
         |           |
       Tutup(T)      Tutup(T)

Semua cabang tertutup dengan T, maka kalimat ini valid (tautologi). Ini adalah sifat yang menarik, menunjukkan bahwa setidaknya salah satu arah implikasi antara dua proposisi apa pun pasti benar.

Pembahasan:

Asumsikan kalimat bernilai `False`. Ini hanya bisa terjadi jika anteseden `(P or not P)` bernilai `True` dan konsekuen `(Q or not Q)` bernilai `False`.
Namun, `(P or not P)` dan `(Q or not Q)` keduanya adalah tautologi, yang artinya mereka *selalu* bernilai `True`. Tidak mungkin bagi `(Q or not Q)` untuk bernilai `False`.
Asumsi kita bahwa kalimat bisa bernilai `False` telah menghasilkan sebuah kontradiksi. Oleh karena itu, kalimat tersebut harus valid.

Pembahasan:

P if and only if not P
      /          \
    P=T          P=F
     |            |
T <=> not T    F <=> not F
T <=> F        F <=> T
= F            = F
     |            |
   Tutup(F)     Tutup(F)

Semua cabang pohon tertutup dengan F (False). Maka kalimat ini adalah sebuah kontradiksi.

Pembahasan:

Hasil konversinya adalah:

IFTHENELSE(OR(NOT(AND(P, Q)), R), AND(Q, R), R)

Pembahasan:

Kita mengganti setiap kemunculan `(P and Q)` dengan `(if P then R)`.

Hasil: `(if not(Q or R) then (if P then R)) else (if P then R)`

Pembahasan:

Hanya kemunculan pertama `(P or S)` yang diganti.

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

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:

Gunakan $G(x)$ untuk "$x$ adalah gajah" dan $A(x)$ untuk "$x$ berwarna abu-abu". Kalimat ini menyatakan bahwa untuk setiap objek, jika objek itu gajah, maka ia berwarna abu-abu.

Bentuk simbolik: $(\forall x)(if \ G(x) \ then \ A(x))$.

Pembahasan:

Gunakan $M(x)$ untuk "$x$ adalah mahasiswa" dan $K(x)$ untuk "$x$ suka kalkulus". Kalimat ini menyatakan bahwa ada setidaknya satu objek yang merupakan mahasiswa dan objek itu tidak suka kalkulus.

Bentuk simbolik: $(\exists x)(M(x) \land not \ K(x))$.

Pembahasan:

• Bagian 1: $(\forall x)r(h(a), x, y)$
  • $x$ terikat oleh $\forall x$.
  • $y$ adalah bebas.
• Bagian 2: $(\exists z)s(g(x, b), z)$
  • $z$ terikat oleh $\exists z$.
  • $x$ adalah bebas.

Jadi, variabel terikat adalah $x$ (pada bagian pertama) dan $z$. Variabel bebas adalah $y$ dan $x$ (pada bagian kedua).

Pembahasan:

Domain $D = \{0, 1, 2, ...\}$. Kita perlu memberikan nilai/arti untuk simbol bebas (a, y, x, b) dan fungsi/predikat (h, r, g, s).

Contoh Interpretasi I:

• a $\leftarrow 5$
• b $\leftarrow 2$
• x $\leftarrow 10$ (variabel bebas)
• y $\leftarrow 3$ (variabel bebas)
• $h(d_1) = d_1 + 1$
• $g(d_1, d_2) = d_1 \times d_2$
• $r(d_1, d_2, d_3)$ bernilai True jika $d_1+d_2 > d_3$
• $s(d_1, d_2)$ bernilai True jika $d_1 = d_2$

Pembahasan:

Interpretasi baru $J''$ adalah salinan dari $J$ dengan satu perubahan. Domain dan definisi simbol lain tetap sama, hanya nilai konstanta b yang berubah.

$J'' = \{a \leftarrow 2.5, b \leftarrow 4.0, y \leftarrow 1.5, ...\}$

Pembahasan:

Kalimat ini dibaca "Untuk setiap elemen x, ada suatu elemen y, dimana x sama dengan y". Ini selalu benar karena untuk setiap x yang kita pilih dari domain, kita selalu bisa memilih y sebagai x itu sendiri. Karena $x=x$ selalu benar, maka pernyataan ini valid.

Pembahasan:

Kalimat ini dibaca "Ada suatu elemen x, sedemikian sehingga untuk semua elemen y, x sama dengan y". Ini berarti ada satu elemen khusus yang sama dengan semua elemen lain di domain. Ini hanya mungkin benar jika domain hanya memiliki satu elemen. Jika domain memiliki dua elemen, A dan B, maka tidak ada satu elemen pun yang sama dengan *semua* elemen lainnya. Maka dari itu, kalimat ini tidak valid secara umum.

Pembahasan:

Perluasan interpretasi berarti mengubah definisi dari salah satu simbol. Kita bisa mengubah predikat $p$ menjadi relasi yang berbeda.

Contoh perluasan $J'$:

$J' = J \text{ dengan perubahan } p \leftarrow p_{J'}(d_1,d_2): d_1 = d_2^2$

Dalam interpretasi baru ini, semua simbol lain tetap sama, tetapi relasi untuk $p$ telah diubah.

Pembahasan:

Tidak, kalimat ini tidak valid. Kita dapat dengan mudah menemukan interpretasi yang membuatnya salah (counterexample). Misal domain D adalah {A, B}. Definisikan predikat p sebagai: p(A) = True, p(B) = False.
Maka, anteseden $(\exists x)p(x)$ bernilai True (karena ada A).
Konsekuen $(\forall x)p(x)$ bernilai False (karena tidak berlaku untuk B).
Sehingga, `if True then False` hasilnya `False`. Karena ada interpretasi yang membuatnya `False`, kalimat ini tidak valid.

Pembahasan:

Tidak. 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:

Kalimat ini adalah valid. Ini merupakan contoh dari 'penamaan ulang variabel terikat'.

Penjelasan:

Dalam logika predikat, nama variabel yang terikat oleh sebuah quantifier (seperti $x$ dalam $(\forall x)$) tidak mengubah makna dari pernyataan, asalkan variabel baru tersebut tidak bentrok dengan variabel bebas lain yang sudah ada (dalam kasus ini tidak ada). Pernyataan $(\forall x)p(x)$ ("untuk semua x, p(x) berlaku") menyatakan hal yang persis sama dengan $(\forall y)p(y)$ ("untuk semua y, p(y) berlaku"). Keduanya menyatakan bahwa predikat $p$ berlaku untuk setiap elemen dalam domain. Karena kedua sisi dari biimplikasi (if and only if) akan selalu memiliki nilai kebenaran yang sama di bawah interpretasi apapun, maka keseluruhan kalimat selalu bernilai `True`.