7.1 Logika dan Set
Representasi pengetahuan dengan symbol logika
merupakan bagian dari penalaran eksak.Merupakan bagian yang paling penting
dalam penalaran adalah mengambil kesimpulan dari premis. Dan Logika
dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan
pada silogisme, dengan dua premisdan
satu konklusi.
Contoh :
– Premis :
Semua wanita adalah makhluk hidup
–
Premis : Milan adalah wanita
–
Konklusi : Milan adalah
makhluk hidup
Cara lain merepresentasikan pengetahuan adalah dengan
Diagram Venn.
Diagram Venn merepresentasikan sebuah himpunan yang
merupakan kumpulan objek. Objek dalam himpunan disebut elemen.
A ={1,3,5,7} , B = {….,-4,-2,0,2,4,…..}
, C = {pesawat, balon}
Symbol
epsilon ε menunjukkan bahwa suatu elemen merupakan anggota dari suatu himpunan,
contoh : 1 ε A . Jika suatu elemen bukan anggota dari suatu himpunan maka
symbol yang digunakan ∉,
contoh : 2 ∉ A.Jika suatu himpunan
sembarang, misal X dan Y didefinisikan bahwa setiap elemen X merupakan elemen
Y, maka X adalah subset dari Y, dituliskan : X ⊂ Y atau Y ⊃ X.
Operasi-operasi Dasar dalam Diagram Venn:
– Interseksi (Irisan)
C = A ∩ B C =
{x ∈ U | (x ∈ A) ∧ (x ∈ B)}
Dimana : ∩
menyatakan irisan himpunan | dibaca “sedemikian hingga” ∧ operator logika AND
– Union (Gabungan)
C = A ∪ B C = {x ∈ U | (x ∈ A) ∨ (x ∈ B)}
Dimana : ∪ menyatakan gabungan himpunan operator logika OR
– Komplemen
A’ = {x ∈ U | ~(x ∈ A) }
Dimana : ’ menyatakan komplemen himpunan ~ operator
logika NOT
7.2 Operator Logika
Proposisi adalah suatu pernyataan yang dapat bernilai benar (B)
atau salah (S). Simbol-simbol seperti P dan Q menunjukkan proposisi. Dua
atau lebih proposisi dapat digabungkan dengan menggunakan operator logika:
Operator Logika Proposisi
a. Operator Negasi : ⌐ (not);
Operator NOT digunakan untuk memberikan nilai negasi (lawan)
dari pernyataan yang telah ada. Tabel 3.1 menunjukkan tabel
kebenaran untuk operator NOT. Contoh :
P = Hari ini hujan
Not P = Hari ini tidak hujan
b. Operator Konjungsi : Λ (and);
Operator AND digunakan untuk mengkombinasikan 2 buah proposisi. Hasil
yang diperoleh akan bernilai benar jika kedua proposisi bernilai benar,
dan akan bernilai salah jika salah satu dari kedua proposisi bernilai
salah. Contoh :
P = Mobil saya berwarna hitam.
Q = Mesin mobil berwarna hitam itu 6 silinder.
R = P Λ Q = Mobil saya berwarna hitam dan mesinnya 6 silinder R
bernilai benar , jika P dan Q benar.
c. Operator Disjungsi : ν
(or);
Operator OR digunakan untuk mengkombinasikan 2 buah proposisi. Hasil
yang diperoleh akan bernilai benar jika salah satu dari
kedua proposisi bernilai benar, dan akan bernilai salah jika kedua
proposisi bernilai salah. Contoh :
P = Seorang wanita berusia 25 tahun
Q = Lulus Perguruan Tinggi Informatika
R = P ν Q = Seorang wanita berusia 25 tahun atau Lulus Perguruan
Tinggi Informatika R bernilai benar bila salah satu P atau Q benar
d. Implikasi :(if-then);
Implikasi: Jika P maka Q akan menghasilkan nilai salah jika P benar
dan Q salah, selain itu akan selalu bernilai benar. Contoh :
P = Mobil rusak
Q = Saya tidak bisa naik mobil
R = P -> Q = Jika Mobil
rusak Maka saya tidak bias naik mobil R bernilai benar jika P dan Q benar.
e. Ekuivalensi /
Biimplikasi / Bikondisional : ⇔ (if and only if
/Jika dan hanya Jika)
Ekuivalen akan menghasilkan nilai benar jika P dan Q keduanya
benar atau keduanya salah. Contoh :
P = Hujan turun sekarang
Q = Saya tidak akan pergi ke pasar
R = Q ⇔ P = Saya tidak akan pergi ke pasar
jika dan hanya jika Hujan turun sekarang R akan bernilai benar jika P
dan Q benar atau jika P dan Q salah.
7.3 Tautologi,
Kontradiksi, dan Contingent
Tautologi
Adalah suatu
ekspresi logika yang selalu bernilai benar di dalam tabel kebenarannya, tanpa
memperdulikan nilai kebenaran dari proposisi-proposisi yang berada didalamnya.
Example :
1. Lihat
ekspresi logika dari suatu pernyataan berikut :
(A ^ B)→(C v
(¬B→¬C))
Buatlah Tabel
Kebenarannya
C v (¬B→¬C)
(A ^ B) → (C v (¬B → ¬C))
A B C ¬B ¬C A^B ¬B→¬C
F F F T T F T T T
F F T T F F F T T
F T F F T F T T T
F T T F F F T T T
T F F T T F T T T
T F T T F F F T T
T T F F T T T T T
T T T F F T T T T
Jadi ekspresi
logika diatas adalah tautology karena pada table kebenarannya semua pasangannya
menghasilkan nilai T.
2. Buktikan
: ¬(A ^ B ) v B adalah tautologi ?
Bukti : Buat Tabel
Kebenarannya seperti berikut :
A B A
^ B ¬(A ^
B) ¬(A ^ B) v B
F F F T T
F T F T T
T F F T T
T T T F T
Jadi, ekspresi
diatas juga Tautologi
3. Jika Tono pergi
kuliah, maka Tini juga pergi kuliah. Jika siska tidur, maka Tini pergi kuliah.
Dengan demikian, jika Tono pergi kuliah atau Siska tidur, maka Tini pergi
kuliah.
Jawab :
Diubah ke variabel
proposisional :
A = Tono pergi
kuliah
B = Tini pergi
kuliah
C = Siska tidur
Diubah menjadi
ekspresi logika yang terdiri dari premis-premis dan kesimpulan. Ekspresi logika
1 dan 2 adalah premis-premis, sedangkan logika 3 adalah kesimpulan.
1. A
→
B (premis)
2. C
→
B (premis)
3. (A
v
C)→B (kesimpulan)
Selanjutnya, dapat
ditulis berikut :
((A → B) ^ (C →
B)) → ((A v C) → B)
Setelah itu,
buatlah tabel kebenarannya dari ekspresi logika tersebut :
((A →
B) ^ (C → B)) → ((A v C) → B)
A B C A→B C→B (A→B)^(C→B) AvC (AvC)→B
F F F T T T F T T
F F T T F F T F T
F T F T T T F T T
F T T T T T T T T
T F F F T F T F T
T F T F F F T F T
T T F T T T T T T
T T T T T T T T T
Jadi, jika table
kebenaran menunjukkan hasil tautology, maka argument tersebut valid.
Kontradiksi
Adalah Suatu
ekspresi logika yang selalu bernilai salah di dalam tabel kebenarannya, tanpa
memperdulikan nilai kebenarannya dari proposisi-proposisi yang berada di
dalamnya.
Example :
Lihat ekspresi
logika dari suatu pernyataan berikut :
((A v B) ^ ¬A) ^
¬B
Buatlah Tabel
Kebenarannya :
((A
v B) ^ ¬A) ^ ¬B
A B ¬A ¬B (A
v B) ((A
v B) ^ ¬A)
F F T T F F
F T T F T T
T F F T T F
T T F F T F
Jadi, ekspresi
logika di atas terjadi kontradiksi.
Contingent
Adalah Suatu
ekspresi logika yang mempunyai nilai benar dan salah di dalam tabel
kebenarannya, tanpa mempedulikan nilai kebenaran dari proposisi-proposisi yang
berada di dalamnya.
Example :
Lihat ekspresi
logika dari suatu pernyataan berikut :
((A ^
B) → C) → A
Buatlah tabel
kebenarannya :
A B C A
^ B (A ^ B) → C
F F F F T F
F F T F T F
F T F F T F
F T T F T F
T F F F T T
T F T F T T
T T F T F T
T T T T T T
2. ((A
→ B) ^ (¬B → C)) → (¬C → A)
Tabel Kebenarannya
;
((A →
B) ^ (¬B → C))
((A →
B) ^ (¬B →C)) → (¬C → A)
A B C ¬B ¬C A→B ¬B→C ¬C→A
F F F T T T F F F T
F F T T F T T T T T
F T F F T T T F T F
F T T F F T T T T T
T F F T T F F T F T
T F T T F F T T F T
T T F F T T T T T T
T T T F F T T T T T
Nilai-nilai
kebenaran pada nilai kebenaran sebagai hasil akhir di tabel kebenaran tidak
harus selalu berurutan antara F dan T, yang penting ada T dan ada F.
7.4 Resolusi
Logika Proposisi
Resolusi merupakan suatu teknik pembuktian yang lebih efisien, sebab fakta-fakta
yang akan dioperasikan terlebih dahulu dibawa ke bentuk standar yang
sering disebut dengan nama klausa. Pembuktian suatu pernyataan menggunakan
resolusi ini dilakukan dengan cara menegasikan pernyataan tersebut,
kemudian dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
Resolusi adalah suatu aturan untuk melakukan inferensi yang dapat berjalan
secara efisien dalam suatu bentuk khusus conjunctive normal form (CNF).
Pada logika proposisi, prosedur untuk membuktikan proposisi P dengan beberapa
aksioma F yang telah diketahui, dengan menggunakan resolusi.
Algoritma resolusi :
1. Konversikan semua proposisi F ke bentuk CNF.
2. Negasikan P, dan konversikan hasil negasi tersebut ke bentuk klausa. Tambahkan ke himpunan klausa yang telah ada pada langkah 1.
3. Kerjakan hingga terjadi kontradiksi atau proses tidak mengalami kemajuan
:
a. Seleksi 2 klausa sebagai klausa parent.
b. Bandingkan (resolve) secara bersama-sama. Klausa hasil resolve tersebut
dinamakan resolvent. Jika ada pasangan literal L dan ￢L, eliminir dari resolvent.
c. Jika resolvent berupa klausa kosong, maka ditemukan kontradiksi. Jika
tidak, tambahkan ke himpunan klausa yang telah ada.
Contoh :
Diketahui basis pengetahuan (fakta-fakta yang bernilai benar) sebagai
berikut:
1. P
2. (P ∧ Q) → R
3. (S ∨ T) → Q
4. T
Buktikanlah kebenaran R!
Pertama-tama kita harus ubah dulu keempat fakta di atas menjadi bentuk CNF.
Konversi ke CNF dapat dilakukan sebagai berikut:
Kemudian kita tambahkan kontradiksi pada tujuannya, R menjadi ￢R sehingga fakta-fakta (dalam bentuk CNF) dapat disusun menjadi:
1. P
2. ￢P ∨ ￢Q ∨ R
3. ￢S ∨ Q
4. ￢T ∨ Q
5. T
6. ￢R
Dengan demikian resolusi dapat dilakukan untuk membuktikan R sebagaimana
terlihat pada Gambar berikut:
Contoh apabila diterapkan dalam kalimat:
P : Andi anak yang cerdas.
Q : Andi rajin belajar.
R : Andi akan menjadi juara kelas.
S : Andi makannya banyak.
T : Andi istirahatnya cukup.
Kalimat yang terbentuk (basis pengetahuan) menjadi :
1. P : Andi anak yang cerdas.
2. (P ∧ Q) → R : Jika Andi anak yang cerdas
dan Andi rajin belajar, maka Andi akan menjadi juara kelas.
3. (S ∨ T) → Q : Jika Andi makannya banyak
atau Andi istirahatnya cukup, maka Andi rajin belajar.
4. T : Andi istirahatnya cukup.
Setelah dilakukan konversi ke bentuk CNF, didapat:
1. P : Andi anak yang cerdas.
2. ￢P ∨ ￢Q ∨ R : Andi tidak cerdas atau Andi
tidak rajin belajar atau Andi akan menjadi juara kelas.
3. ￢S ∨ Q : Andi tidak makan banyak atau Andi rajin belajar.
4. ￢T ∨ Q : Andi tidak cukup istirahat atau Andi rajin belajar.
5. T : Andi istirahatnya cukup.
6. ￢R : Andi tidak akan
menjadi juara kelas.
Pohon aplikasi resolusi
untuk kejadian di atas sebagai
berikut :
Tidak ada komentar:
Posting Komentar