METODE INFERENSI
METODE INFERENSI
Tree (Pohon) dan Graph
-
Tree
(pohon) adalah suatu hierarki struktur yang terdiri dari Node (simpul/veteks) yang menyimpan informasi atau pengetahuan dan
cabang (link/edge) yang menghubungkan node.
-
Binary
tree mempunyai 0,1 atau 2 cabang per-node.
o Node tertinggi disebut root
o Node terendah disebut daun
-
Tree
merupakan tipe khusus dari jaringan semantic, yang setiap nodenya kecuali akar,
mempunyai satu node oran
-
Tree
adalah kasus khusus dalam Graph
-
Graph
dapat mempunyai nol atau lebih link di antara node dan tidak ada perbedaan
antara oran
-
Dalam
graph, link dapat ditunjukkan berupa panah atau arah yang memadukan node dan
bobot yang merupakan karakteristik beberapa aspek dari link.
-
Beberapa
contoh graph sederhana:
-
Graph
asiklik adalah graph yang tidak
mengandung siklus.
-
Graph
dengan link berarah disebut digraph.
-
Graph
asiklik berarah disebut lattice.
-
Tree
yang hanya dengan path tunggal dari akar untuk satu daun disebut degenerate tree.
-
Aplikasi
tree dan lattice adalah pembuatan keputusan disebut decision tree dan decision
lattice.
-
Contoh
: decision tree yang menunjukkan pengetahuan tentang hewan.
-
Aturan
produksi (IF…THEN…) dari contoh di atas :
JIKA pertanyaan=”Apakah dia bertubuh besar ?”
DAN jawaban=”Tidak”
MAKA pertanyaan=”Apakah dia mencicit?”
JIKA pertanyaan=”Apakah dia bertubuh besar ?”
DAN jawaban=”Ya”
MAKA pertanyaan=”Apakah dia mempunyai leher panjang?”
dst……
Pohon AND-OR dan Tujuan
-
Banyak
tipe system pakar menggunakan backward
chaining untuk mendapatkan solusi dari permasalahan.
-
Salah
satu tipe dari tree atau lattice yang digunakan dalam masalah representasi backward chaining adalah Pohon AND-OR.
-
 |
Contoh :
Penalaran Deduktif dan Silogisme
-
Tipe-tipe
Inferensi
Deduction
Ø Pemberian
alasan logikal dimana kesimpulan harus mengikuti premis
Induction
Ø Inferensi
dari khusus ke umum
Intuition
Ø Tidak
ada teori yg menjamin. Jawabannya hanya muncul, mungkin dengan penentuan pola
yg ada secara tidak disadari.
Heuristic
Ø Aturan
yg didasarkan pada pengalaman
Generate
& Test
Ø Trial
dan error. Digunakan dgn perencanaan.
Abduction
Ø Pemberian
alasan kembali dari kesimpulan yg benar ke premis .
Default
Ø Diasumsikan
pengetahuan umum sebagai default
Autoepistemic
Ø Self-knowledge
Nonmonotonic
Ø Pengetahuan
yg sebelumnya mungkin tdk benar jika bukti baru didapatkan
Analogy
Ø Kesimpulan
yg berdasarkan pada persamaan untuk situasi yg lainnya.
-
Suatu
logika argument adalah kumpulan dari pernyataan-pernyataan yang dinyatakan
untuk dibenarkan sebagai dasar dari rantai penalaran.
-
Salah
satu jenis logika argunen adalah Silogisme.
-
Contoh
:
Premis : Siapapun
yang dapat membuat program
adalah pintar
Premis : John dapat
membuat program
Konklusi : Oleh
karenanya John adalah pintar
Proses deduktif pada contoh di atas bergerak dari prinsip
umum menuju konklusi khusus.
-
Penalaran
deduktif umumnya terdiri dari tiga bagian : premis
mayor, premis minor dan konklusi.
-
Premis
disebut juga antecedent
-
Konklusi/kesimpulan
disebut juga consequent
-
Silogisme
dapat direpresentasikan ke dalam bentuk aturan JIKA…..MAKA….. (IF…THEN…..),
contoh :
JIKA siapapun yang dapat membuat program adalah pintar
DAN John dapat
membuat program
MAKA John adalah pintar
-
Silogisme
klasik disebut categoricall syllogism
(silogisme yang pasti)
-
Premis
dan konklusi didefinisikan sebagai statement yang pasti dari empat bentuk berikut
:
|
Bentuk
|
Skema
|
Arti
|
|
A
|
Semua S adalah P
|
Universal Afirmative
|
|
E
|
Tidak S adalah P
|
Universal Negative
|
|
I
|
Beberapa S adalah P
|
Particular Afirmative
|
|
O
|
Beberapa S bukan P
|
ParticularNegative
|
-
Subjek
dari konklusi S disebut bagian minor bila predikat konklusi P adalah bagian
mayor.
-
Premis
terdiri dari premis mayor dan premis minor.
-
Contoh
:
Premis mayor : Semua M adalah P
Premis minor : Semua S
adalah M
Konklusi : Semua
S adalah P
Silogisme di atas adalah bentuk standar karena premis mayor
dan minor sudah diketahui.
Contoh :
“Semua
mikrokomputer adalah computer”
Subjeknya (objek yang digambarkan) adalah mikrokomputer.
Predikatnya (beberapa sifat subjek) adalah computer
-
M
(middle term) adalah hal yang penting karena silogisme didefinisikan sedemikian
sehingga konklusi tidak dapat disimpulkan dengan mengambil salah satu premis.
-
Q
(quantifier) menggambarkan porsi dari kelas yang diketahui.
o Quantifier “semua” dan “tidak” adalah
universal karean menunjukkan keseluruhan kelas.
o “beberapa” adalah khusus (particular)
karena hanya menunjukkan satu bagian dari kelas yang diketahui.
-
Mood
dari silogisme didefinisikan sebagai tiga huruf yang memberikan bentuk
masing-masing premis mayor, minor dan konklusi.
Contoh :
Semua M
adalah P
Semua S
adalah M
\Semua S adalah P
menunjukkan suatu mood AAA-1
-
Ada
|
|
Figure 1
|
Figure 2
|
Figure 3
|
Figure 4
|
|
Premis Mayor
|
MP
|
PM
|
MP
|
PM
|
|
Premis Minor
|
SM
|
SM
|
MS
|
MS
|
-
Tidak
selalu argument yang mempunyai bentuk silogisme merupakan silogisme yang valid.
-
Contoh
: Silogisme tidak valid berbentuk AEE-1
Semua M adalah P
Tidak S adalah M
\Tidak S adalah P
Semua mikrokomputer adalah computer
Bukan mainframe adalah mikrokomputer
\Bukan mainframe adalah computer
-
Diperlukan
prosedur keputusan (decision procedure)
untuk pembuktian validitas.
-
Prosedur
keputusan untuk silogisme dapat dilakukan menggunakan diagram venn tiga
lingkaran yang saling berpotongan yang merepresentasikan S,P, M.
-
Contoh
: Prosedur Keputusan untuk AEE-1
Semua M adalah P
Tidak S adalah M
\Tidak S adalah P
-
Contoh
: Prosedur Keputusan untuk EAE-1
Tidak M adalah P
Semua S adalah
M
\Tidak S adalah P
Kaidah dari Inferensi
-
Diagram
Venn tidak sesuai untuk argumen yang lebih kompleks karena sulit dibaca pada
decision tree untuk silogisme.
-
Logika
proposisi memberikan pengertian lain dari penggambaran argumen.
-
Contoh
:
Jika ada daya listrik, komputer akan bekerja
\
Komputer akan bekerja
A = ada daya listrik
B = komputer akan bekerja
Sehingga dapat ditulis :
AàB
A
\
B
-
Bentuk
umum Ponens
/ direct reasoning / law of detachment / assuming the antecedent
pàq
p atau pàq, p;
\ q
\ q
Bentuk tersebut valid, karena argumen tersebut dapat
ditunjukkan sebagai suatu tautologi.
((pàq)Ùp) àq
Tabel Kebenaran Po nens :
|
p
|
q
|
pàq
|
((pàq)Ùp)
|
((pàq)Ùp) àq
|
|
T
|
T
|
T
|
T
|
T
|
|
T
|
F
|
F
|
F
|
T
|
|
F
|
T
|
T
|
F
|
T
|
|
F
|
F
|
T
|
F
|
T
|
-
Terdapat
argumen yang menyerupai ponens namun perlu dibuktikan validitasnya.
Contoh :
Jika tidak kesalahan maka program dapat mengkompile
Program dapat mengkompile
\ Tidak ada kesalahan
pàq
q atau pàq, q;
\ p
\
p
Tabel Kebenaran:
|
p
|
q
|
pàq
|
((pàq)Ùq)
|
((pàq)Ùq) àp
|
|
T
|
T
|
T
|
T
|
T
|
|
T
|
F
|
F
|
F
|
T
|
|
F
|
T
|
T
|
T
|
F
|
|
F
|
F
|
T
|
F
|
T
|
(Bukan Pones karena tidak bersifat Tautology)
-
Skema
argumen lain :
pàq
~q
\
~p
Tabel Kebenaran:
|
p
|
q
|
pàq
|
~q
|
(pàq)Ù~q)
|
~p
|
((pàq)Ù~q) à~p
|
|
T
|
T
|
T
|
F
|
F
|
F
|
T
|
|
T
|
F
|
F
|
T
|
F
|
F
|
T
|
|
F
|
T
|
T
|
F
|
F
|
T
|
T
|
|
F
|
F
|
T
|
T
|
T
|
T
|
T
|
Argumen di atas disebut Tollens / ind
-
Beberapa
huum Inferensi
|
Hukum Inferensi
|
Skema
|
|
1. Hukum Detasemen
|
pàq
 p
\q
|
|
2. Hukum Kontrapositif
|
pàq
 \~q à~p |
|
3. Hukum Modus Tollens
|
pàq
~q
 \ ~p |
|
4. Aturan Rantai
(hukum
silogisme)
|
pàq
qàr
\ pàr
|
|
5. Hukum Inferensi Disjungsi
|
pÚq pÚq
~p ~q \ q \ p |
|
6. Hukum negasi
|
~(~p)
\ p
|
|
7. Hukum de Morgan
|
~(pÙq)
~(pÚq)
  \~pÚ~q \~pÙq |
|
8. Hukum Simplifikasi
|
pÙq pÙq
 \p \q |
|
9. Hukum Konjungsi
|
p
q
 \pÙq |
|
10. Hukum Penambahan
Disjungtif
|
p
\
 pÚq |
|
11. Hukum Argumen
Konjugtif
|
~(pÙq) ~(pÙq)
p
q
 ~q
~p |
-
Kaidah
inferensi dapat digunakan untuk argumen yang mempunyai lebih dari dua premis.
Contoh :
Harga chip naik hanya jika yen naik
Yen naik hanya jika dollar turun dan
jika dollar
turun maka yen naik
Karena harga chip telah naik
\Dollar harus turun
Misal : C = harga chip naik
Y = Yen
naik
D =
Dollar turun
1. C àY
2. (Y àD)Ù( D àY)
3. C
\D
-
Kondisional
p àq mempunyai converse, inverse dan kontrapositif
|
Kondisional
|
p àq
|
|
Converse
|
q à p
|
|
Inverse
|
~p à~q
|
|
Kontrapositif
|
~q à ~p
|
Jika p àq dan q
à p bernilai benar, maka keduanya adalah ekuivalen.
p àqÙ
q à p ekuivalen dengan p«q
atau pºq.
sehingga argumen untuk contoh di atas, menjadi :
1. C àY
2. (Y àD)Ù( D àY)
3. C /\D
4. YºD 2 ekuivalen
5. C àD 1
substitusi
6. D 3,5 modus
ponens
METODE INFERENSI (2)
KETERBATASAN
LOGIKA PROPOSISI
-
Perhatikan contoh berikut :
All men are mortal
Socrates is a man
Therefore, Socrates is mortal
Misal : p = All men are mortal
q = Socrates is a man
r =
Socrates is mortal
Skema
argumennya menjadi : p, q; \
r
p
q
\
r
Bila dibuat tabel
kebenaran, hasilnya invalid.
-
Argumen invalid sering diinterpretasikan
sebagai konklusi yang salah (walaupun beberapa orang berpendapat argumen itu
dapat saja bernilai benar).
-
Argumen yang invalid berarti argumen
tersebut tidak dapat dibuktikan dengan logika proposisi.
-
Keterbatasan logika proposisi dapat
diatasi melalui logika predikat sehingga argumen tersebut menjadi valid.
-
Kenyataannya, semua logika silogistik
adalah subset yang valid dari logika proposisi urutan pertama.
-
Contoh :
If Socrates is a man,
then Socrates is mortal
Socrates is a man
Therefore, Socrates is
mortal
Misal: p = Socrates is a man
q = Socrates is mortal
Argumennya menjadi :
p à q
p
q
Argumen di atas adalah
silogistik yang valid, yaitu bentuk modus
ponens.
LOGIKA
PREDIKAT URUTAN PERTAMA
(First Order Predicate Logic)
-
Representasi 4 kategori silogisme
menggunakan logika predikat
|
Bentuk
|
Skema
|
Representasi Predikat
|
|
A
|
Semua S adalah P
|
("x) (S(x)àP(x))
|
|
E
|
Tidak S adalah P
|
("x) (S(x)à~P(x))
|
|
I
|
Beberapa S adalah P
|
($x) (S(x)àP(x))
|
|
O
|
Beberapa S bukan P
|
($x) (S(x)à~P(x))
|
-
Kaidah Universal Instatiation merupakan
state dasar, dimana suatu individual dapat digantikan (disubsitusi) ke dalam
sifat universal.
-
Contoh :
Misal, f
merupakan fungsi proposisi :
("x) f(x)
\
f(a)
merupakan bentuk yang
valid, dimana a menunjukkan spesifik individual, sedangkan x adalah suatu
variabel yang berada dalam jangkauan semua individu (universal)
Contoh lain : ("x) H(x)
\
H(Socrates)
-
Berikut ini adalah contoh pembuktian
formal silogisme:
All men are mortal
Socrates is a man
Therefore, Socrates is mortal
Misal : H = man, M = mortal,
s = Socrates
1.
("x) (H (x) à M(x))
2.
H(s) / \ M(s)
3.
H(s)
à M(s) 1
Universal Instatiation
4.
M(s) 2,3 Modus Ponens
SISTEM
LOGIKA
-
Sistem logika adalah kumpulan objek
seperti kaidah (rule), aksioma, statement dan lainnya yang diatur dalam cara
yang konsisten.
-
Sistem logika mempunyai beberapa tujuan
:
1.
Menentukan bentuk argumen.
Awalnya argumen logika
tidak memiliki arti dalam semantic sense, bentuk yang valid pada dasarnya dapat
dicapai jika validitas dari argumen tersebut dapat ditentukan.
Fungsi terpenting dari
logika sistem adalah menentukan well
formed formulas (wffs) dari argumen yang digunakan.
Contoh :
All S is P ….. merupakan wffs
tapi….
All
All is S P ….. bukan wffs
Is S all
2.
Menunjukkan kaidah inferensi yang
valid.
3.
Mengembangkan dirinya sendiri dengan
menemukan kaidah baru inferensi dan memperluas jangkauan argumen yang dapat
dibuktikan.
-
Sistem logika dibangun melalui
Sentential atau kalkulus proposisi, kalkulus predikat dst.
-
Setiap sistem disandarkan pada aksioma atau postulat, yang merupakan definisi mendasar dari sistem.
Suatu aksioma merupakan fakta sederhana atau
assertion yang tidak dapat dibuktikan dalam sistem. Terkadang, kita menerima
aksioma dikarenakan ada sesuatu yang menarik atau melalui pengamatan.
-
Sistem formal membutuhkan :
1.
simbol alfabet.
2.
suatu set finite string dari simbol
tertentu, wffs
3.
aksioma, definisi dari sistem
4.
kaidah inferensi, yang memungkinkan
wffs, A
untuk dikurangi sebagai kesimpulan dari set finite G
wff lain dimana G = {A1,A2,…An}. Wffs
harus berupa aksioma atau teori lain dari sistem logis. Sebagai contoh : sistem
logika dapat didefinisikan menggunakan modus pones untuk diturunkan menjadi
teorema baru.
- Jika terdapat argumen :
A1, A2, ……., AN;
\ A
yang valid, maka A
disebut teorema dari sistem logika formal dan ditulis dengan simbol (metasymbol) yang menunjukkan wff adalah suatu
teorema .
A1, A2,
……., AN A
Contoh : teorema
silogisme tentang Socrates yang
ditulis dalam bentuk logika
predikat.
("x) (H (x)àM(x)), H(s) M(s)
M(s) dapat dibuktikan
dari aksioma di sisi kiri, hal tersebut menunjukkan aksioma
-
Suatu teorema merupakan tautology, ditunjukkan melalui G
sebagai set null dimana wff selalu bernilai null dan tidak tergantung dari
aksioma atau teorema yang lain.
Teorema dengan
tautology ditulis dengan simbol ,
misalnya A.
Contoh :
Jika A º p Ú
~p maka p Ú
~p
-
Suatu model adalah interpretasi wff
bernilai benar.
Suatu wff disebut konsisten atau satifiable jika interpretasi yang dihasilkan benar, dan
disebut inkonsisten atau unsatisfiable jika wff menghasilkan
nilai yang salah pada semua interpretasi.
RESOLUSI
-
Diperkenalkan oleh Robinson (1965).
-
Resolusi merupakan kaidah inferensi
utama dalam bahasa PROLOG.
-
PROLOG menggunakan notasi
“quantifier-free”.
-
PROLOG didasarakan pada logika predikat
urutan pertama.
-
Sebelum resolusi diaplikasikan, wff
harus berada dalam bentuk normal
atau standard.
Tiga tipe utama bentuk
normal : conjunctive normal form,
clausal form dan subset Horn clause.
-
Resolusi diaplikasikan ke dalam bentuk
normal wff dengan menghubungkan seluruh elemen dan quantifier yang dieliminasi.
-
Contoh :
(A Ú
B) Ù (~B ÚC) ………… conjunctive normal form
Dimana A Ú B dan ~B
ÚC
adalah clause.
Logika proposional
dapat ditulis dalam bentuk clause.
Full clause form yang mengekspresikan formula logika predikat
dapat ditulis dalam Kowalski clause form.
A1, A2, ……., AN à B1, B2, ……., BM
Clause
yang ditulis dalam notasi standard :
A1Ù
A2, ……., AN à B1 Ú B2, ……., BM
Bentuk disjungsinya
merupakan disjungsi dari literal menggunakan equivalence :
p à q º ~p Ú q
sehingga
A1Ù
A2, ……., AN à B1 Ú B2, ……., BM
º
~( A1Ù A2, …, AN)
Ú (B1 Ú B2, …., BM)
º
~A1Ú ~A2, …, ~AN
Ú B1 Ú B2, …., BM
Yang merupakan hukum
de Morgan :
~(p Ù q) º ~p Ú ~q
Dengan Horn clause
dapat ditulis :
A1, A2,
……., AN à B
Dalam
bahasa PROLOG ditulis :
B
:- A1, A2, ……., AN
Untuk membuktikan
teorema di atas benar, digunakan metode klasik reductio ad absurdum atau metode
kontradiksi.
Tujuan dasar resolusi
adalah membuat infer klausa baru yang disebut “revolvent” dari dua klausa lain yang disebut parent clause.
Contoh :
A Ú B
A Ú ~B
\
A
Premis dapat ditulis
: (A Ú B) Ù
(A Ú ~B)
Ingat Aksioma
Distribusi :
p Ú (q Ù
r) º (p Ú q) Ù
(p Ú q)
Sehingga premis di
atas dapat ditulis :
(A Ú
B) Ù (A Ú ~B) º
A Ú (B Ù ~B) º
A
dimana B Ù ~B selalu bernilai
salah.
Tabel Klausa dan Resolvent
|
Parent Clause
|
Resolvent
|
Arti
|
|
p à q , p atau
~p Ú q, p
|
q
|
Modus Pones
|
|
p à q , q à r atau
~p Ú q, ~ q Ú r
|
p à r atau
~p Ú r
|
Chaining atau
Silogisme Hipotesis
|
|
~p Ú q, p Ú q
|
q
|
Penggabungan
|
|
~p Ú ~q, p Ú q
|
~p Ú p atau
~q Ú q
|
TRUE (tautology)
|
|
~p, p
|
Nill
|
FALSE (kontradiksi)
|
SISTEM
RESOLUSI DAN DEDUKSI
-
Refutation adalah pembuktian
teorema dengan menunjukkan negasi atau pembuktian kontradiksi melalui reductio
ad absurdum.
-
Melakukan refute berarti membuktikan
kesalahan.
-
Contoh :
A à
B
B à
C
C à
D
\A à
D
Untuk membuktikan
konklusi A à D adalah suatu teorema melalui resolusi
refutation, hal yang dilakukan :
p à q º ~p Ú q
sehingga
Aà D º ~A Ú D
dan langkah terakhir
adalah melakukan negasi
~(~A Ú D) º A Ù ~D
Penggunaan konjungsi
dari disjunctive form pada premis dan negasi pada konsklusi, memberikan
conjuctive normal form yang cocok untuk resolusi refutation.
Dari contoh di atas,
penulisannya menjadi :
(~A Ú
B) Ù (~B Ú C) Ù
(~C Ú D) Ù A Ù
~D
Akar bernilai nill,
menunjukkan kontradiksi. Sehingga melalui refutation dapat ditunjukkan konklusi
asli (awal) adalah teorema dengan
peran kontradiksi.
SHALLOW
(DANGKAL) PENALARAN CAUSAL
-
Sistem pakar menggunakan rantai
inferensi, dimana rantai yang panjang
merepresentasikan lebih banyak causal
atau pengetahuan yang mendalam. Sedangkan penalaran
shallow umumnya menggunakan kaidah tunggal atau inferensi yang sedikit.
-
Kualitas inferensi juga faktor utama
dalam penentuan kedalaman dan pendangkalan dari penalaran.
-
Shallow
knowledge
disebut juga experiment knowledge.
-
Contoh : Penalaran shallow
IF a car has
a
good battery
good sparkplugs conditional elements
gas
good tires
THEN the car can move
-
Pada penalaran shallow, tidak ada atau
hanya terdapat sedikit pemahaman dari subjek, dikarenakan tidak ada atau hanya
terdapat sedikit rantai inferensi.
-
Keuntungan dari penalaran shallow
adalah kemudahan dalam pemograman, yang berarti waktu pengembangan program
menjadi singkat, program menjadi lebih kecil, lebih cepat dan biaya
pengembangan menjadi murah.
-
Penalaran causal disebut juga penalaran
mendalam (deep reasoning), karena
pemahaman yang mendalam diperoleh dari pemahaman rantai causal kejadian yang
terjadi, atau dengan kata lain kita dapat memahami proses dari suatu abstrak
yang disajikan.
-
Frame dan jaringan semantik adalah
contoh model yang menggunakan penalaran causal.
-
Contoh :
IF the battery is good
THEN there is
electricity
IF there is
electricity
and the sparkplugs are good
THEN the sparkplugs
will fire
IF the sparkplugs fire
and there is gas
THEN the engine will
run
IF the engine runs
and there are is gas
THEN the engine will
run
IF the engine runs
and there are good tires
THEN the car will move
-
Penalaran causal cocok digunakan untuk
operasi yang berubah-ubah dari sistem yang dibatasi oleh kecepatan eksekusi,
memori dan peningkatan biaya pengembangan.
-
Penalaran causal dapat digunakann untuk
membangun model sistem nyata, seperti model yang dipakai untuk simulasi
penggalian hipotesa penalaran pada tipe query “what if”.
-
Contoh : Dalam mengobati pasien, dokter
dihadapkan pada jangkauan yang lebar dalam melakukan tes diagnosa untuk
memverifikasi kejadian/penyakit secara cepat dan tepat.
-
Karena kebutuhan akan penalaran causal
meningkat, diperlukan kombinasi dengan kaidah penalaran satu shallow.
-
Metode resolusi dengan refutation dapat
digunakan untuk membuktikan apakah kaidah tunggal konklusi bernilai benar dari
banyak kaidah (multiple rule).
-
Contoh :
B=battery is good C= car will move
E=there is electricity F=sparkplugs will fire
G=there is gas R=engine will run
S=sparkplugs are good T=there are good tires
(1)
B Ù S Ù
G Ù T à C
(2)
B à E
(3)
E Ù S à
F
(4)
F Ù G à
R
(5)
R Ù T à
C
Langkah pertama di
atas diaplikasikan pada resolusi refutation dengan menegasikan konklusi atau
kaidah tujuan.
(1’) ~( B Ù
S Ù G Ù T à
C) = ~[~( B Ù S Ù G Ù
T) Ú C]
Selanjutnya, setiap
kaidah yang lain diekspresikan dalam disjunctive form menggunakan equivalesi
seperti :
p à q º
~p Ú q
dan ~(p Ù
q) º ~p Ú ~q
sehingga versi baru
dari (2)-(5) menjadi :
(2’) ~B Ú
E
(3’) ~(E Ù
S) Ú F
= ~E Ú
~S Ú F
(4’) ~(F ÙG)
Ú R
= ~F Ú
~G Ú R
(5’) ~(R Ù
T) Ú C
= ~R Ú
~T Ú C
Pohon Resolusi
Refutation-nya :
Akar bernilai nill,
menunjukkan kontradiksi. Sehingga melalui refutation dapat ditunjukkan konklusi
asli (awal) :
B Ù S Ù
G Ù T à C
adalah teorema dengan peran kontradiksi.
FORWARD
CHAINING DAN BACKWARD CHAINING
-
Chain (rantai) : perkalian inferensi
yang menghubung-kan suatu permasalahan dengan solusinya.
-
Forward chaining :
ü
Suatu rantai yang dicari atau
dilewati/dilintasi dari suatu permasalahn untuk memperoleh solusi.
ü
Penalaran dari fakta menuju konklusi
yang terdapat dari fakta.
-
Backward chaining :
ü
Suatu rantai yang dilintasi dari suatu
hipotesa kembali ke fakta yang mendukung hipotesa tersebut.
ü
Tujuan yang dapat dipenuhi dengan
pemenuhan sub tujuannya.
-
Contoh rantai inferensi :
gajah(x) à
mamalia (x)
mamalia(x)
à binatang(x)
·
Causal (sebab-akibat) Forward chain
gajah(clyde)
gajah(x) mamalia(x)
mamalia(x) binatang(x)
binatang(clyde)
·
Explicit Causal chain
gajah(clyde)
unifikasi
implikasi gajah(clyde) mamalia(clyde)
unifikasi
implikasi mamalia(clyde)
-
Karakteristik Forward dan Backward
chaining
|
Forward chaining
|
Backward chaining
|
|
Perencanaan,
monitoring, kontrol
|
Diagnosis
|
|
Disajkan untuk masa
depan
|
Disajikan untuk masa
lalu
|
|
Antecedent ke
konsekuen
|
Konsekuen ke
antecedent
|
|
Data memandu,
penalaran dari bawah ke atas
|
Tujuan memandu,
penalaran dari atas ke bawah
|
|
Bekerja ke depan
untuk mendapatkan solusi apa yang mengikuti fakta
|
Bekerja ke belakang
untuk mendapatkan fakta yang mendukung hipotesis
|
|
Breadth first search dimudahkan
|
Depth first search dimudahkan
|
|
Antecedent menentukan
pencarian
|
Konsekuen menentukan
pencarian
|
|
Penjelasan tidak
difasilitasi
|
Penjelasan
difasilitasi
|
ü
Forward Chaining
ü Backward
Chaining
METODE
LAIN DARI INFERENSI
ANALOGI
-
Mencoba dan menghubungkan situasi lama
sebagai penuntun ke situasi baru.
-
Contoh : diagnosis medical (gejala
penyakit yang diderita oleh seorang pasien ternyata sama dengan gejala yang
dialami pasien lain).
-
Pemberian alasan analogis berhubungan
dgn induksi. Bila induksi membuat inferensi dari spesifik ke umum pada situasi
yang sama, maka analogy membuat inferensi dari situasi yang tidak sama.
GENERATE AND TEST
-
Pembuatan solusi kemudian pengetesan
untuk melihat apakah solusi yg diajukan memenuhi semua persyaratan. Jika solusi
memenuhi maka berhenti yg lain membuat sollusi yg baru kemudian test lagi dst.
-
Contoh : Dendral, prog AM ( artificial
Mathematician), Mycin
ABDUCTION/PENGAMBILAN
-
Metodenya mirip dengan modus ponens
Abduction Modus ponens
p à
q p à
q
 |
 |
q p
\
p \
q
-
Bukan argument deduksi yang valid
-
Berguna untuk kaidah inferensi heuristik
-
Analogi,generate and test, abduction
adalah metode bukan deduksi. Dari premise yg benar, metode ini tidak dapat
membuktikan kesimpulan yg benar
Perbedaan Forward Chaining,
Backward Chaining dan Abduction
Inference
|
Start
|
Tujuan
|
|
FORWARD
BACKWARD
ABDUCTION
|
Fakta
Kesimpulan tdk pasti
Kesimpulan benar
|
Kesimpulan yang harus mengikuti
Fakta pendukung kesimpulan
Fakta yang dapat mengikuti
|
NONMONOTONIC REASONING
-
Adanya tambahan aksioma baru pada
sistem logika berarti akan banyak teorema yang dapat dibuktikan.
-
Peningkatan teorema dengan peningkatan
aksioma dikenal dengan sistem monotonik
-
Suatu masalah dapat terjadi, jika
diperkenalkan aksioma parsial atau komplit baru yang kontradikasi dengan
aksioma sebelumnya.
-
Pada sistem nonmonotonik, tidak perlu adanya peningkatan teorema yang
sejalan dengan peningkatan aksioma.
METODE
INFERENSI (3)
(Tambahan untuk sub materi RESOLUSI)
RESOLUSI LOGIKA PROPOSISI
-
Dalam proposisi, resolusi merupakan aturan untuk melakukan
inferensi yang dapat berjalan secara efisien dalam suatu bentuk khusus, yaitu conjunctive normal form (CNF)
-
Bentuk CNF memiliki ciri-ciri :
·
Setiap kalimat merupakan disjungsi literal
·
Semua kalimat terkonjungsi secara implisit.
-
Untuk mengubah suatu kalimat ke dalam bentuk CNF, dapat
digunakan langkah-langkah sebagai berikut :
·
Hilangkan implikasi dan euivalensi
o
x à
y menjadi ~x Ú y
o
x «
y menjadi (~x Ú
y) Ù (~y Ú x)
·
Kurangi lingkup semua negasi menjadi satu negasi saja
o
~(~x) menjadi x
o
~( x Ú
y) menjadi (~x Ù
~y)
o
~( x Ù
y) menjadi (~x Ú
~y)
·
Gunakan aturan asosiatif dan distributif untuk
mengkonversi menjadi conjuction of disjunction.
o
Assosiatif : (A Ú B) Ú C
= A Ú (B Ú C)
o
Distributif : (A Ù B) Ú C
= (A Ú C) Ù (B ÚC)
·
Buatu satu kalimat terpisah untuk tiap-tiap konjungsi.
-
Pada logika proposisi, prosedur untuk membuktikan
proposisi P dengan beberapa aksioma F yang telah diketahui, dengan menggunakan
resolusi, dapat dilakukan melalui algoritma sebagai berikut :
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 sebgai berikut :
1.
P
2.
(P Ù
Q) à R
3.
(S Ú
T) à Q
4.
T
Buktikan kebenaran R !
Apabila kita ingin membuktikan
kebenaran R dengan menggunakan resolusi, maka pertama-tama kita harus ubah dulu
keempat fakta di atas menjadi bentuk CNF. Konversi ke CNF dapat dilakukan
sebagai berikut :
|
Kalimat
|
Langkah-langkah
|
CNF
|
|
1. P
|
Sudah merupakan
bentuk CNF
|
P
|
|
2. (P Ù Q) à R
|
- Menghilangkan
implikasi
~(P Ù Q) Ú R
- Mengurangi lingkup
negasi
(~P Ú ~Q) Ú R
- Gunakan assosiatif
~P Ú ~Q Ú R
|
~P Ú ~Q Ú R
|
|
3. (S Ú T) à Q
|
- Menghilangkan
implikasi
~(S Ú T) Ú Q
- Mengurangi lingkup
negasi
(~S Ù ~T) Ú Q
- Gunakan
distributif
(~S Ú Q) Ù (~T Ú Q)
|
(~S Ú Q)
(~T Ú Q)
|
|
4. T
|
Sudah merupakan
bentuk CNF
|
T
|
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 di bawah ini.
-
Contoh diatas apabila diterapkan dalam kalimat :
·
P : Andi anak yang cerdas.
·
Q : Andri rajin belajar.
·
R : Andi akan menajdi juara kelas
·
S : Andi makannya banyak
·
T : Andi istrirahatnya cukup
Kalimat yang terbentuk :
·
Andi anak yang cerdas
·
Jika Andi anak yang
cerdas dan Andi rajin belajar, maka Andi akan menjadi juara kelas
·
Jika Andi makannya banyak atau Andi istirahatnya cukup,
maka Andi rajin belajar
·
Andi istirahatnya cukup
Setelah dilakukan konversi ke bentuk
CNF, didapat :
·
Fakta ke-2 : Andi
tidak cerdas atau Andi tidak rajin belajar atau
Andi akan menjadi juara kelas.
·
Fakta ke-3 : Andi
tidak makan banyak atau Andi rajin belajar
·
Fakta ke-4 : Andi
tidak cukup istirahat atau Andi rajin belajar.
Pohon aplikasi resolusi untuk kejadian
di atas adalah :
RESOLUSI LOGIKA PREDIKAT
-
Resolusi predikat 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-pernyataan tersebut, kemudian
dicari kontradiksinya dari pernyataan-pernyataan yang sudah ada.
-
Algoritma konversi
ke bentuk klausa :
1. Eliminir a à b menjadi ~a Ú b
2. Reduksi skope dari
~ sebagai berikut :
~(~a Ú b) º ~a Ù ~b
~(~a Ù b) º ~a Ú ~b
~"x :
P(x) º $x:~P(x)
~$x :
P(x) º "x:~P(x)
3. Standarisasi
variabel sehingga semua qualifier (" dan $) terletak pada satu variabel yang
unik.
"x : P(x) Ú
"x :
Q(x) menjadi
"x : P(x) Ú
"y :
Q(y)
4. Pindahkan semua
qualifier ke depan tanpa mengubah urutan relatifnya.
5. Eliminasi
qualifier “$”
"x : $y : P(y,x) menjadi
"x : P(S(x),x)
6. Buang semua
prefiks qualifier “"”
7. Ubah menjadi conjuction of disjunction
(a Ù b) Ú c
º (a Ú b) Ù (a Ú b)
8. Bentuk klausa
untuk tiap-tiap bagian konjungsi
9. Standarisasi
variabel di tiap klausa.
-
Resolusi pada logika predikat pada dasarnya sama dengan
resolusi pada logika proposisi, hanya saja ditambahkan dengan unifikasi. Pada
logika predikat, prosedur untuk membuktikan pernyataan P dengan beberapa pernyataan
F yang telah diketahui, dengan menggunakan resolusi
dapat dilakukan algoritma sebagai berikut :
1. Konversikan semua
proposisi F ke bentuk klausa
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 T1 dan ~T2 sedemikian sehingga keduanya dapat
dilakukan unifikasi, maka salah satu T1 atau T2 tidak muncul lagi dalam resolvent. T1 dan T2 disebut sebagai complementary literal. Jika ada lebih
dari 1 complementary literal, maka
ahnya sepasang yang dapat meninggalkan resolvent.
(c) Jika resolvent berupa klausa kosong, maka
ditemukan kontradiksi. Jika tidak, tambahkan ke himpunan klausa yang telah ada.
-
Contoh : terdapat pernyataan-pernyataan sebagai berikut :
- Andi
adalah seorang mahasiswa
- Andi
masuk Jurusan Elektro
- Setiap
mahasiswa elektro pasti mahasiswa teknik
- Kalkulus
adalah matakuliah yang sulit
- Setiap
mahasiswa teknik pasti akan suka kalkulus atau akan membencinya
- Setiap
mahasiswa pasti akan suka terhadap suatu matakuliah
- Mahasiswa
yang tidak pernah hadir pada kuliah matakuliah sulit, maka mereka pasti
tidak suka terhadap matakuliah tersebut.
- Andi
tidak pernah hadir kuliah matakuliah kalkulus.
Kedelapan pernyataan di atas dapat
dibawa ke bentuk logika predikat :
1.
mahasiswa(Andi)
2.
Elektro(Andi)
3.
"x: Elektro(x) à Teknik(x)
4.
sulit(Kalkulus)
5.
"x: Teknik(x) à suka(x, Kalkulus) Ú benci(x, Kalkulus)
6.
"x:$y : suka(x,y)
7.
"x: "y: mahasiswa(x) Ù sulit(y) Ù ~hadir(x,y) à ~suka(x,y)
8.
~hadir(Andi, Kalkulus)
Kemudian dibuat dalam bentuk klausa :
1.
mahasiswa(Andi)
2.
Elektro(Andi)
3.
~Elektro(x1) Ú Teknik(x1)
4.
sulit(Kalkulus)
5.
~Teknik(x2) Ú suka(x2, Kalkulus) Ú benci(x2, Kalkulus)
6.
suka(x3,f1(x3))
7.
~mahasiswa(x4) Ú ~sulit(y1) Ú hadir(x4,y1) Ú ~suka(x4,y1)
8.
~hadir(Andi,Kalkulus)
Akan dibuktikan apakah “Andi benci
kalkulus” atau dapat ditulis :
benci(Andi,Kalkulus)
Pohon resolusi pada logika predikat
untuk contoh di atas adalah :
Komentar
Posting Komentar