Soal Latihan UAS (Set 2)

Pembahasan:

Frasa "hanya jika" diterjemahkan menjadi implikasi (`if...then...`) dengan urutan terbalik.

• P: Anda bisa mendapatkan diskon.
• Q: Anda adalah anggota.
• R: Anda membayar tunai.

Kalimat menjadi: `if P then (Q or R)`.

Pembahasan:

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

Pembahasan:

Implikasi bernilai `False` hanya jika anteseden (`P or Q`) bernilai `True` dan konsekuen (`R`) bernilai `False`. Agar `P or Q` bernilai `True`, setidaknya salah satu dari P atau Q harus `True`. Maka, salah satu interpretasi yang mungkin adalah:
{P=True, Q=False, R=False}.

Pembahasan:

Kalimat `if P then not P` ekuivalen dengan `not P or not P`, yang ekuivalen dengan `not P`. Maka, kalimat soal menjadi `not (not P)`, yang ekuivalen dengan `P`. Karena `P` bisa `True` atau `False`, maka kalimat ini adalah kontingensi.

Pembahasan:

Gunakan ekuivalensi `(if A then B)` $\equiv$ `(not A or B)`.

1. Ubah implikasi terdalam: `(if Q then R)` menjadi `(not Q or R)`
2. Kalimat menjadi: `if P then (not Q or R)`
3. Ubah implikasi utama: `not P or (not Q or R)`

Pembahasan:

• P, Q, R, S
• Q and R
• not S
• P or (Q and R)

Pembahasan:

Ya, keduanya ekuivalen. Ini adalah salah satu bentuk definisi dari biimplikasi. Jika P dan Q sama (keduanya T atau keduanya F), kedua ekspresi bernilai T. Jika berbeda, keduanya bernilai F.

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:

1. Asumsikan kalimat bernilai `False`.
2. Maka anteseden `(P and (if P then Q))` harus `True`, dan konsekuen `Q` harus `False`.
3. Agar anteseden `True`, maka `P` harus `True` DAN `(if P then Q)` harus `True`.
4. Jika `P` `True` dan `Q` `False`, maka `(if P then Q)` menjadi `(if True then False)`, yang hasilnya `False`.
5. Ini bertentangan dengan poin 3 yang mengharuskan `(if P then Q)` bernilai `True`.

Karena terjadi kontradiksi, asumsi awal salah. Kalimat ini valid.

Pembahasan:

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

Karena ada cabang yang menghasilkan T dan F, kalimat ini kontingensi.

Pembahasan:

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

Semua cabang tertutup dengan T, maka kalimat ini adalah tautologi (valid).

Pembahasan:

Ya, ini adalah hukum distributif. Untuk membuktikannya, kita dapat membuat pohon semantik untuk kalimat biimplikasi di antara keduanya: $(P \text{ or } (Q \text{ and } R)) \text{ if and only if } ((P \text{ or } Q) \text{ and } (P \text{ or } R))$. Jika semua cabang tertutup dengan `T`, maka keduanya ekuivalen.

Pembahasan:

1. Asumsikan `False`.
2. Maka `(P and Q)` harus `True` dan `P` harus `False`.
3. Jika `(P and Q)` `True`, maka `P` harus `True`.
4. Ini bertentangan dengan poin 2. Asumsi salah, maka kalimat valid.

Pembahasan:

Kalimat ini adalah definisi dari XOR (disjungsi eksklusif). Pohon semantiknya akan menunjukkan hasil T jika P dan Q berbeda, dan F jika P dan Q sama. Ini adalah kontingensi.

Pembahasan:

Untuk menguji validitas argumen, kita uji apakah `(Premis1 and Premis2) then Kesimpulan` adalah tautologi. Kalimatnya: `if ((if P then Q) and P) then Q`. Pohon semantik akan menunjukkan bahwa semua cabang tertutup dengan `T`, sehingga argumen ini valid (ini adalah Modus Ponens).

Pembahasan:

Hasil: `(R and not P) or (if P then (R and not P))`

Pembahasan:

1. Nol substitusi: `P and (if P then Q)`
2. Substitusi pertama: `not Q and (if P then Q)`
3. Substitusi kedua: `P and (if not Q then Q)`
4. Semua substitusi: `not Q and (if not Q then Q)`

Pembahasan:

Hasil: `R and (if S then P)`.

Pembahasan:

Gunakan P(x) untuk "$x$ adalah politisi" dan J(x) untuk "$x$ adalah jujur".

`(exists x)(P(x) and J(x)) and not (forall x)(if P(x) then J(x))`

Pembahasan:

Gunakan I(x) untuk "$x$ adalah seorang ibu" dan P(x) untuk "$x$ adalah seorang perempuan".

Hasil: $(\forall x)(if \ I(x) \ then \ P(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:

Variabel bebas $y$ tidak ada dalam kalimat. Variabel $y$ di dalam $(\exists y)q(x,y)$ adalah terikat. Substitusi hanya berlaku untuk variabel bebas. Maka, kalimat tidak berubah: $(\forall x)(p(x) \text{ or } (\exists y)q(x,y))$.

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:

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:

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:

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:

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