Nama:
NIM:
(Contoh Solusi) PR 1 METODE FORMAL (CIG4F3) Semester Ganjil 2015-2016 Dikumpulkan paling lambat pukul 15:00, Jumat, 25 September 2015, di slot pengumpulan PR di idea (softcopy) atau Loker Pengumpulan PR Metode Formal (hardcopy). Lokasi loker berada di antara toilet dan ruang E 108 (IF2.01.08). Petunjuk pengerjaan: 1. Sebagaimana telah dijelaskan di awal perkuliahan, bobot seluruh nilai PR yang diberikan dalam satu semester untuk perkuliahan Metode Formal pada semester ganjil 20152016 direncanakan sebesar 25% dari nilai akhir. 2. Gunakan PR sebagai sarana berlatih untuk menghadapi ujian. Oleh karenanya, kerjakan PR ini dengan serius. Jangan hanya memberi jawaban dan argumen untuk PR ini tanpa memahaminya dengan baik. 3. PR dikerjakan secara individu. Meskipun begitu, Anda diperkenankan berdiskusi dengan teman sekelas, teman sekampus, atau teman yang berasal dari kampus lain. Tuliskan nama-nama orang yang Anda ajak berdiskusi lengkap dengan asal institusinya pada bagian referensi yang mungkin perlu ditambahkan pada bagian akhir PR. 4. PR ini terdiri dari 6 (enam) soal dengan bobot masing-masing soal yang bervariasi. Anda akan dinilai tidak hanya pada jawaban akhir saja, tetapi juga pada argumen dan tata bahasa penulisan ilmiah yang Anda tuliskan. 5. Berkas PR dikumpulkan dalam bentuk softcopy saja, atau softcopy dan hardcopy. 6. Pengumpulan berkas softcopy dilakukan pada slot yang telah disediakan di idea, batas waktu unggah adalah Jumat 25 September 2015 pukul 15:00 waktu idea. Berkas yang diunggah berformat .pdf dengan format penamaan PR1MetFor-
-Nama_Panggilan. Contoh: PR1MetFor-1103130128-Indra. 7. PR boleh dikerjakan dengan cara: Ditulis dengan tulisan tangan sendiri, kemudian hasilnya dipindai (scan) dan dijadikan berkas .pdf. Kertas yang boleh dipakai adalah kertas A4, HVS, atau folio bergaris. Jawaban boleh ditulis dengan pensil 2B, pensil HB, atau pulpen bertinta hitam/ biru. Diketik rapi. Usahakan untuk memakai notasi yang telah diajarkan diperkuliahan. Jika tidak, jelaskan terlebih dulu notasi yang Anda pakai. halaman 1 dari 15
Nama:
NIM:
8. Jika Anda berniat untuk mengumpulkan berkas hardcopy, berkas dikumpulkan di loker pengumpulan PR Metode Formal yang terdapat pada loker dosen KK ICM di depan ruang E 108 (IF2.01.08). Batas pengumpulan berkas hardcopy adalah Jumat 25 September 2015 pukul 15:00 waktu idea. 9. Selamat berlatih dan mengerjakan PR. Semoga beruntung ketika ujian.
halaman 2 dari 15
Nama:
NIM:
Soal 1 (5 + 5 + 2 + 6 + 2 = 20) Diberikan proposisi p, q, dan r. (a). [5 poin] Buatlah tabel kebenaran untuk proposisi (p (b). [5 poin] Buatlah tabel kebenaran untuk proposisi p
q) (q
r. r).
(c). [2poin] Apakah merupakan operator logika proposisi yang bersifat asosiatif? Jelaskan jawaban Anda. (d). [6 poin] Buatlah tabel kebenaran untuk (p ^ :q ^ :r)_(:p ^ q ^ :r)_(:p ^ :q ^ r). (e). [2 poin] Apakah p q r ekuivalen dengan (p ^ :q ^ :r) _ (:p ^ q ^ :r) _ (:p ^ :q ^ r)? S OLUSI : (a). Tabel kebenaran untuk (p p
q
r
1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
p
q
(p
0 0 1 1 1 1 0 0
q)
q
r
1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
q
r 0 1 1 0 0 1 1 0
r adalah:
r
1 0 0 1 0 1 1 0
(b). Tabel kebenaran untuk p p
q)
p
(q
(q
r) adalah:
r)
1 0 0 1 0 1 1 0
(c). Karena tabel kebenaran (p q) r dan p (q r) identik untuk konfigurasi nilai kebenaran proposisi atom yang sama, maka (p q) r p (q r), akibatnya merupakan operator logika yang bersifat asosiatif dan penulisan p q r tidak ambigu.
halaman 3 dari 15
Nama:
NIM:
(d). Untuk memperingkas penulisan, kolom untuk :p, :q, dan :r tidak ditulis dan misalkan = (p ^ :q ^ :r) _ (:p ^ q ^ :r) _ (:p ^ :q ^ r). Tabel kebenaran untuk adalah: p
q
r
1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
p ^ :q ^ :r 0 0 0 1 0 0 0 0
:p ^ q ^ :r 0 0 0 0 0 1 0 0
:p ^ :q ^ r 0 0 0 0 0 0 1 0
0 0 0 1 0 1 1 0
(e). Untuk konfigurasi nilai kebenaran proposisi atom yang sama, kolom paling kanan tabel kebenaran untuk p q r berbeda dengan tabel kebenaran untuk (p ^ :q ^ :r) _ (:p ^ q ^ :r) _ (:p ^ :q ^ r). Akibatnya p q r 6 (p ^ :q ^ :r) _ (:p ^ q ^ :r) _ (:p ^ :q ^ r).
halaman 4 dari 15
Nama:
NIM:
Soal 2 (2 + 2 + 2 + 2 + 2 = 10) Misalkan a, s, dan n adalah proposisi-proposisi berikut: a : “sistem dijalankan dalam administrator mode” s : “sistem dijalankan dalam safe mode” n : “sistem dijalankan dalam normal mode” Translasikan pernyataan-pernyataan berikut ke dalam formula logika proposisi menggunakan proposisi a, s, dan n yang telah dijelaskan serta operator-operator logika :, ^, _, , !, dan $. (a). [2 poin] Sistem tidak dapat dijalankan dalam administrator mode bila sistem dijalankan dalam safe mode. (b). [2 poin] Ketika sistem dijalankan dalam normal mode, maka sistem dijalankan dalam tepat salah satu dari administrator mode atau safe mode. (c). [2 poin] Sistem selalu dijalankan dalam administrator mode dan normal mode secara bersamaan. (d). [2 poin] Sistem dapat dijalankan dalam administrator mode jika tidak dijalankan dalam safe mode. (e). [2 poin] Sistem dapat dijalankan dalam tepat salah satu dari administrator mode, safe mode, atau normal mode. (Petunjuk: perhatikan kembali Soal 1 (d) dan (e)). S OLUSI : (a). Kalimat dapat ditulis ulang sebagai: “jika sistem dijalankan dalam safe mode, maka sistem tidak dapat dijalankan dalam administrator mode”, sehingga translasinya adalah: s ! :a. (b). n ! a
s
(c). Kalimat dapat ditulis ulang sebagai: “sistem dijalankan dalam administrator mode jika dan hanya jika sistem dijalankan dalam normal mode”, sehingga translasinya adalah: a $ n. (d). Kalimat dapat ditulis ulang sebagai: “jika sistem tidak dijalankan dalam safe mode, maka sistem dapat dijalankan dalam administrator mode, sehingga translasinya adalah: :s ! a. (e). Kalimat menyatakan suatu spesfikasi yang bernilai benar tepat ketika hanya salah satu dari proposisi a, s, dan n bernilai benar. Berdasarkan jawaban Soal 1 (e), hasil translasi kalimat ini adalah: (a ^ :s ^ :n) _ (:a ^ s ^ :n) ^ (:a ^ :s ^ n).
halaman 5 dari 15
Nama:
NIM:
Definisi 1 Misalkan
adalah sebuah formula logika proposisi:
(a). formula dikatakan absah (valid) apabila terpretasi I
selalu bernilai benar untuk setiap in-
(b). formula dikatakan terpenuhi (satisfiable) apabila suatu interpretasi I
dapat bernilai benar untuk
(c). formula dikatakan kontradiksi (contradictory) apabila tuk setiap interpretasi I (d). formula dikatakan tersalahkan (falsifiable) apabila suatu interpretasi I
selalu bernilai salah un-
dapat bernilai salah untuk
(e). formula dikatakan kontingensi (contingency) apabila bukan formula yang bersifat absah dan bukan pula formula yang bersifat kontradiksi. Soal 3 (4 + 4 + 4 + 4 + 4 = 20) Diberikan formula-formula
1,
2,
(a). [4 poin]
1
:= (p _ q) ^ (:q _ r) ^ (:r _ s) ! p _ s
(b). [4 poin]
2
:= p _ q _ r _ s ! p ^ q ^ r ^ s
(c). [4 poin]
3
:= p ! (q ! r) ^ (p ^ q ^ :r)
(d). [4 poin]
4
:= (:p ^ q ^ r) _ (p ^ :q ^ r) _ (p ^ q ^ :r)
(e). [4 poin]
5
:= (:p _ :q _ r) ^ (:p _ q _ :r) ^ (p _ :q _ :r)
3,
4,
dan
5
berikut:
Berikan tanda X pada baris dan kolom yang bersesuaian untuk Tabel 1 bila formula i memenuhi sifat-sifat yang telah dijelaskan pada Definisi 1. Berikan bukti dan argumen yang mendukung jawaban Anda. valid
satisfiable contradiction falsifiable contingency
1 2 3 4 5
Tabel 1: Tabel Sifat-sifat Formula
halaman 6 dari 15
Nama:
NIM:
S OLUSI : Tabel dapat dilengkapi sebagai berikut valid satisfiable contradiction falsifiable 1
X
contingency
X
2
X
X
X
3
X
X
X
4
X
X
X
5
X
X
X
(a). Formula 1 := (p _ q) ^ (:q _ r) ^ (:r _ s) ! p _ s bersifat absah (valid). Hal ini dapat dibuktikan sebagai berikut. Cara 1 (metode falsifikasi): Andaikan 1 tidak absah, maka terdapat interpretasi I sehingga I ( 1 ) = F. Akibatnya I ((p _ q) ^ (:q _ r) ^ (:r _ s)) = T dan
(1)
I (p _ s) = F.
(2)
Dari persamaan (1) kita memiliki I (p _ q) = T
(3)
I (:q _ r) = T
(4)
I (:r _ s) = T
(5)
dan dari persamaan (2) kita memiliki I (p) = I (s) = F. Akibatnya: (i) dari persamaan (3) diperoleh I (q) = T, (ii) dari persamaan (5) diperoleh I (:r) = T, sehingga I (r) = F. Kedua hasil (i) dan (ii) di atas memberikan I (:q _ r) = :T _ F = F, yang bertentangan dengan persamaan (4). Jadi formula 1 tidak mungkin bernilai F untuk interpretasi apapun. Dengan demikian 1 bersifat absah dan terpenuhi.
halaman 7 dari 15
Nama:
NIM:
Cara 2 (ekuivalensi logika): Akan dibuktikan bahwa bahwa 1
(p _ q) ^ (:q _ r) ^ (:r _ s) ! p _ s : ((p _ q) ^ (:q _ r) ^ (:r _ s)) _ (p _ s) : (p _ q) _ : (:q _ r) _ : (:r _ s) _ (p _ s) : (p _ q) _ : (:q _ r) _ : (:r _ s) _ (p _ q _ :q _ r _ :r _ s) : (p _ q) _ : (:q _ r) _ : (:r _ s) _ (p _ q) _ (:q _ r) _ (:r _ s) : (p _ q) _ (p _ q) _ : (q _ r) _ (:q _ r) _: (:r _ s) _ (:r _ s) T_T_T T
:=
(b). Formula
2
T. Perhatikan
1
(ekuivalensi ! (De Morgan) (ekuivalensi _ : _ T T) (sifat asosiatif _)
: _ ) T dan
(sifat asosiatif dan komutatif _) (ekuivalensi
_:
T).
:= p _ q _ r _ s ! p ^ q ^ r ^ s memiliki sifat-sifat berikut:
(i)
terpenuhi (satisfiable) karena untuk I (p) = I (q) = I (r) = I (s) = T, maka I ( 2 ) = (T _ T _ T _ T) ! (T ^ T ^ T ^ T) = T.
(ii)
tersalahkan (falsifiable) karena untuk I (p) = T dan I (q) = I (r) = I (s) = F, maka I ( 2 ) = (T _ F _ F _ F) ! (T ^ F ^ F ^ F) = T ! F = F.
2
2
(iii)
2
tidak absah (valid) karena
(iv)
2
tidak kontradiksi (contradictory ) karena
Akibatnya (c). Formula
2
3
2
tersalahkan. 2
terpenuhi.
suatu kontingensi.
:= p ! (q ! r) ^ (p ^ q ^ :r) memiliki sifat-sifat berikut:
(i)
terpenuhi (satisfiable) karena untuk I (p) = I (q) = I (r) = F, maka I ( 3 ) = F ! ((F ! F) ^ (F ^ F ^ :F)) = F ! (T ^ F) = F ! F = T.
(ii)
tersalahkan (falsifiable) karena untuk I (p) = T dan I (q) = I (r) = F, maka I ( 3 ) = T ! ((F ! F) ^ (T ^ F ^ :F)) = T ! (T ^ F) = T ! F = F.
3
3
(iii)
3
tidak absah (valid) karena
(iv)
3
tidak kontradiksi (contradictory ) karena
Akibatnya
3
3
tersalahkan. 3
terpenuhi.
suatu kontingensi.
halaman 8 dari 15
Nama:
NIM:
(d). Formula berikut:
4
:= (:p ^ q ^ r) _ (p ^ :q ^ r) _ (p ^ q ^ :r) memiliki sifat-sifat
(i)
terpenuhi (satisfiable) karena untuk I (p) = I (q) = T dan I (r) = F, maka I ( 4 ) = (:T ^ T ^ F) _ (T ^ :T ^ F) _ (T ^ T ^ :F) = T.
(ii)
tersalahkan (falsifiable) karena untuk I (p) = I (q) = I (r) = T, maka I ( 4 ) = (:T ^ T ^ T) _ (T ^ :T ^ T) _ (T ^ T ^ :T) = F.
4
4
(iii)
4
tidak absah (valid) karena
(iv)
4
tidak kontradiksi (contradictory ) karena
Akibatnya (e). Formula berikut:
4
5
4
tersalahkan. 4
terpenuhi.
suatu kontingensi.
:= (:p _ :q _ r)^(:p _ q _ :r)^(p _ :q _ :r) memiliki sifat-sifat
(i)
terpenuhi (satisfiable) karena untuk I (p) = I (q) = I (r) = T, maka I ( 4 ) = (:T _ :T _ T) ^ (:T _ T _ :T) ^ (T _ :T _ :T) = T.
(ii)
tersalahkan (falsifiable) karena untuk I (p) = I (q) = T dan I (r) = F, maka I ( 4 ) = (:T _ :T _ F) ^ (:T _ T _ :F) ^ (T _ :T _ :F) = F.
5
5
(iii)
5
tidak absah (valid) karena
(iv)
5
tidak kontradiksi (contradictory ) karena
Akibatnya
5
5
tersalahkan. 5
terpenuhi.
suatu kontingensi.
halaman 9 dari 15
Nama:
NIM:
Soal 4 (5 + 5 = 10) Periksa apakah himpunan-himpunan formula berikut konsisten atau tidak. Jelaskan jawaban Anda. (a). [5 poin] A = fp _ q; :p; p ! q; :qg (b). [5 poin] B = f:p ! q; :p $ r; :q $ s; :p ! sg S OLUSI : (a). Kita akan membuktikan bahwa A tidak konsisten. B UKTI : (Dengan metode falsifikasi) Andaikan A konsisten, maka terdapat interpretasi I sehingga I (p _ q) = T
(6)
I (:p) = T
(7)
I (p ! q) = T
(8)
I (:q) = T
(9)
Dari persamaan (7) diperoleh I (p) = F dan dari persamaan (9) diperoleh I (q) = F. Kedua hasil ini memberikan I (p _ q) = F yang bertentangan dengan persamaan (6). B UKTI : (Dengan tabel kebenaran) Misalkan formula pada A, maka p
q
1 1 0 0
1 0 1 0
:p 0 0 1 1
:q 0 1 0 1
Karena formula kontradiksi, maka A tidak konsisten.
p_q 1 1 1 0
adalah konjungsi dari setiap
p!q 1 0 1 1
0 0 0 0
tidak terpenuhi, akibatnya himpunan
(b). Himpunan B = f:p ! q; :p $ r; :q $ s; :p ! sg konsisten bila terdapat interpretasi I sehingga I (:p ! q) = T
(10)
I (:p $ r) = T
(11)
I (:q $ s) = T
(12)
I (:p ! s) = T
(13)
halaman 10 dari 15
Nama:
NIM:
Dari persamaan (11) dan persamaan (12), haruslah I (:p) = I (r) dan I (:q) = I (s). Akibatnya I (r) = :I (p) dan I (s) = :I (q). Dengan memilih I (p) = I (q) = T dan I (r) = I (s) = F, kita memperoleh I (:p ! q) = :T ! T = F ! T = T I (:p $ r) = :T $ F = F $ F = T I (:q $ s) = :T $ F = F $ F = T I (:p ! s) = :T ! F = F ! F = T. Jadi himpunan B bersifat konsisten dan salah satu interpretasi yang mengakibatkan B konsisten adalah I (p) = I (q) = T dan I (r) = I (s) = F. Catatan 1 Soal ini juga dapat diselesaikan dengan tabel kebenaran, namun tidak efisien karena memerlukan 24 = 16 baris.
halaman 11 dari 15
Nama:
NIM:
Soal 5 (5 + 5 + 5 + 5 = 20) Ubahlah formula logika proposisi berikut menjadi formula yang ekuivalen dan hanya memakai operator : dan ! saja. Verifikasi jawaban Anda dengan tabel kebenaran. (a). [5 poin] p ^ q (b). [5 poin] p _ q (c). [5 poin] p
q
(d). [5 poin] p $ q S OLUSI : Untuk menjawab permasalahan ini, kita akan memakai ekuivalensi ! : _ . (a). Tinjau bahwa p ^ q p
q
1 1 0 0
1 0 1 0
:q 0 1 0 1
: (:p _ :q) = : (p ! :q). Jadi p ^ q
p ! :q
: (p ! :q) p ^ q
0 1 1 1
1 0 0 0
(b). Tinjau bahwa p _ q p
q
1 1 0 0
1 0 1 0
:p 0 0 1 1
: (p ! :q).
1 0 0 0
::p _ q
:p ! q
: (:p) _ q
:p ! q. Jadi p _ q
:p ! q.
p_q
1 1 1 0
1 1 1 0
(c). Tinjau bahwa p
(:p ^ q) _ (p ^ :q) : (:p ! :q) _ : (p ! ::q) :: (:p ! :q) ! : (p ! q) (:p ! :q) ! : (p ! q)
q
p
q
1 1 0 0
1 0 1 0
:p 0 0 1 1
:q 0 1 0 1
p!q 1 0 1 1
(dengan (dengan
: (p ! q) :p ! :q 0 1 0 0
1 1 0 1
^ _
: ( ! : )) : ! )
(:p ! :q) ! : (p ! q) p 0 1 1 0
halaman 12 dari 15
q 0 1 1 0
Nama:
NIM:
atau dapat pula p
(p _ q) ^ : (p ^ q) (:p ! q) ^ : (: (p ! :q))
q
(dengan dan ^
_
(:p ! q) ^ (p ! :q) : ((:p ! q) ! : (p ! :q)) (dengan p
q
:p
:q
:p ! q
p ! :q
: (p ! :q)
1 1 0 0
1 0 1 0
0 0 1 1
0 1 0 1
1 1 1 0
0 1 1 1
1 0 0 0
: ((:p ! q) ! : (p ! :q)) p 0 1 1 0
: ! : ( ! : ))
^
: ( ! : ))
(:p ! q) ! : (p ! :q) 1 0 0 1
q 0 1 1 0
(d). Tinjau bahwa p$q
(p ! q) ^ (q ! p) : ((p ! q) ! : (q ! p)) (dengan
p
q
p!q
q!p
: (q ! p)
1 1 0 0
1 0 1 0
1 0 1 1
1 1 0 1
0 0 1 0
(p ! q) ! : (q ! p) 0 1 1 0
^ :
:( ! : ) (p ! q) ! : (q ! p)
!
p$q
1 0 0 1
halaman 13 dari 15
1 0 0 1
Nama:
NIM:
Soal 6 (5 + 5 + 5 + 5 = 20) Periksa apakah pasangan formula-formula ekuivalen atau tidak. Berikan argumen pada jawaban Anda. (a). [5 poin]
:= :p ! (q ! r) dan
(b). [5 poin]
:= p ! (q ! (r ! s)) dan
:= ((p ! q) ! r) ! s
(c). [5 poin]
:= p ! (q ! (r ! s)) dan
:= p ^ q ^ r ! s
(d). [5 poin]
:= p
(q ^ r ^ s) dan
dan
berikut
:= q ! (p _ r)
:= (p
q) ^ (p
r) ^ (p
s)
S OLUSI : (a). Formula
dan
ekuivalen, buktinya adalah sebagai berikut
:= :p ! (q ! r) :p ! (:q _ r) ::p _ (:q _ r) p _ (:q _ r) :q _ (p _ r) q ! (p _ r)
(dengan ! : _ ) (dengan ! : _ ) (dengan :: ) (sifat komutatif dan asosiatif _) (dengan : _ ! )
(b). Formula dan tidak ekuivalen, untuk I (p) = F, I (q) = I (r) = T, I (s) = F kita memiliki I ( ) = I (p ! (q ! (r ! s))) = F ! (T ! (T ! F)) = F ! (T ! F) = F ! F = T, tetapi I ( ) = I (((p ! q) ! r) ! s) = ((F ! T) ! T) ! F = (T ! T) ! F = T ! F = F. (c). Formula
dan
ekuivalen, buktinya adalah sebagai berikut
:= p ! (q ! (r ! s)) p ! (q ! (:r _ s)) p ! (:q _ (:r _ s)) (:p _ (:q _ (:r _ s))) (:p _ :q _ :r) _ s : (p ^ q ^ r) _ s p^q^r !s
(dengan ! : _ ) (dengan ! : _ ) (dengan ! : _ ) (sifat asosiatif _) (De Morgan) (dengan : _ ! )
halaman 14 dari 15
Nama:
NIM:
(d). Formula dan tidak ekuivalen, untuk I (p) = I (q) = I (r) = I (s) = T, maka I ( ) = I (p (q ^ r ^ s)) = T (T ^ F ^ F) = T F = T, tetapi I ( ) = I ((p q) ^ (p r) ^ (p s)) = (T T) ^ (T F) ^ (T F) = F ^ T ^ T = F. Catatan 2 Pemeriksaan ekuivalensi juga dapat dilakukan dengan tabel kebenaran, namun tidak efisien karena memerlukan 24 = 16 baris untuk proposisi yang memuat 4 proposisi atom berbeda.
halaman 15 dari 15
