TREES,LATTICES DAN GRAF
Tree :struktur data hirarki yg berisi node/vertices/objek yg menyimpan informasi/pengetahuan dan link/edges/cabang yg menghubungkan node
Disebut juga dg tipe jaringan semantik khusus
Merupakan kasus khusus yg disebut graf
Suatu graf dapat mempunyai nol atau lebih link, dan tidak ada perbedaan antara root dan child
Root : node tertinggi, leaves : terendah
Stuktur keputusan : skema representasi pengetahuan dan metode pemberian alasan tentang pengetahuannya.
Jika suatu keputusan adalah binary, maka tree keputusan binary mudah dibuat dan sangat efisien.
Setiap pertanyaan, turun satu tingkat dalam tree.Jika seluruh leaves adalah jawaban dan seluruh node yg turun adalah pertanyaan, maka ada max 2n untuk jawaban dan n pertanyaan
STATE SPACE
State adalah kumpulan karakteristik yg dapat digunakan untuk menentukan status.
State Space adalah rangkaian pernyataan yg menunjukkan transisi antara state dimana objek dieksprerimen
POHON AND-OR
Dalam SP, untuk menemukan solusi problem dapat menggunakan rangkaian backward yaitu dengan tree AND-OR dan AND-OR-NOT
LOGIKA DEDUKTIF DAN SILOGISME
Tipe-tipe Inferensi
Induction Heuristics Abduction Autoepistemic Analogy
Deduction Intuition Generate&Test Default Nonmonotonic
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.
Yang paling sering dipakai : deductive logic, unruk menentukan validitas “argument”.
Silogisme merupakan satu type argumen logika.
Contoh :
Premise : Anyone who can program is intelligent
Premise : John can program
Conclusion : Therefore, John is intelligent
Premise
Digunakan sebagai bukti untuk mendukung sutu kesimpulan.
Disebut juga antecedent
Kesimpulan/Conclusion
Disebut juga consequent
Karakteristik logika deduktif adalah kesimpulan benar harus mengikuti dari premis yg benar
Anyone who can program is intelligent
John can program
John is intelligent
Dalam bentuk IF-THEN
IF Anyone who can program is intelligent And
John can program
THEN John is intelligent
Silogisme klasik disebut categorical syllogism.
Premis dan kesimpulan ditentukan sebagai statement categorical dari 4 bentuk berikut :
FORM SCHEMA
A All S is P
E No S is P
I Some S is P
O Some S is not P
S : Subjek kesimpulan disebut minor term
P : Predikat kesimpulan disebut major term
Major premise : All M is P
Minor premise : All S is M
Concluusion : All S is P
Silogisme diatas disebut standard form dimana major dan minor premis diidentifikasi.
Categorical Silogisme
A dan I disebut “affirmative in quality” , subjek dimasukkan kedalam jenis predikat
E dan O disebut “negative in quality”, subjek tidak masuk dalam jenis predikat
IS = capula = menghubungkan, menunjukkan bentuk tense dari kata kerja “tobe”
Middle term (M)
All dan No : universal quantifier, Some :particular quantifier
Mood silogisme ditentukan dengan 3 huruf yg memberikan bentuk premis pokok, minor premis, dan kesimpulan.
Figure 1 Figure 2 Figure 3 Figure 4
Major Premise M P P M M P P M
Minor Premise S M S M M S M S
Contoh :
All M is P
All S is M type AAA-1
All S is P
All M is P Some P are M
No S is M type ???? All M are S type ????
No S is P Some S are P
Untuk membuktikan validitas argumen silogisme, ada metode yang dinamakan “decision prosedure” yaitu dengan menggunakan diagram venn.
Contoh :
All M is P
All S is M type AAA-1
All S is P
S P S P
M M
S P
M
BARIS INFERENCE (RULES OF INFERENCE)
Yaitu modus ponens dan modus tollens
Diagram venn tidak sesuai untuk argumen yg lebih kompleks karena menjadi sulit untuk dibaca pada decision tree untuk silogisme
Pada logika proposisional,
If there is power, the computer will work
There is power
The computer will work
Maka dapat ditulis
A B p q
A p p, p q; q
B q
disebut “direct reasoning,modus ponenes, law of detachment dan assuming the antecedent”
p,q disebut variabel logika
A,B disebut konstanta proposisional
Bagaimana dengen skema untuk argumen dari tipe ini :
1. p q 2. p q
q ~q
p ~p
1. Disebut dg fallacy of converse
2. Disebut dg indirect reasoning, modus tollens, law of contrapositive
Tabel Kondisional dan variantnya
Kondisional p q
Konversi q p
Invensi ~p ~q
Kontrapositif ~q ~p
Contoh argumen dengan lebih dari 2 promise:
Chip prices rise only if the yen rises
The yen rises only if the dollar falls and
If the dollar falls then the yen rises.
Since chip proses have risen,
the dollar must have fallen
Proposisinya C = chip prices rise
Y = yen rises
D = dollar falls
C Y
(Y D) (D Y)
C
D
Buktikan !…..
Solusi :
1. Ingat p q dan q p benar maka p dan q ekuivalen
2. Jika (p q) (q p) maka ekuivalen dg pq dg kata lain p q
Maka argumennya menjadi
C Y
Y D
C
D
3. Karena Y sama dengan D maka substitusi D kedalam Y
Maka argumennya menjadi :
C D
C
D (TERBUKTI valid bahwa ini adalah modus ponens)
SOAL :
All men are mortal (p)
Socrates is a man (q)
Therefore, Socrates is mortal r
Buktikan valid atau tidak ?….
FIRST ORDER PREDICATE LOGIC
Kategori silogisme dengan menggunakan predikat logik
TIPE SKEMA REPRESENTASI PREDIKAT
A All S is P (x) (S(x) P(x))
E No S is P (x) (S(x) ~P(x))
I Some S is P (x) (S(x) P(x))
O Some S is not P (x) (S(x) ~P(x))
Rule Hukum Universal Instantion menunjukkan individual yg mungkin digantikan dg universal yaitu simbol yg berarti fungsi proposisional
(x) (x) x= variabel yg mengatur seluruh individual
(a) a= individual khusus
Contoh : Socrates is human
(x) H (x)
H (Socrates)
dimana H(x) : fungsi proposissional dg x adalah human
Contoh lain
All men are mortal
Socrates is a man
Socrates is mortal
dimana H=man, M=mortal, s=socrates
Solusi :
1. (x) (H(x) M(x))
2. H(s)
3. M(s)
4. H(s) M(s)
5. M(s)
LOGIC SYSTEMS = WFFS = WFF
Koleksi objek seperti baris, aksioma, pernyataan dsb
Tujuan :
1. Menentukan bentuk argumen (WFFS=Well Formed Formulas)
Contoh All S is P
2. Menunjukkan baris inference yg valid
3. Mengembangkan sendiri dg menemukan baris baru dari inference shg memperluas rentangan argumen yg dapat dibuktikan
Aksioma :fakta sederhana atau assertion yg tidak dapat dibuktikan dari dalam sistem
System formal yang diperlukan :
1. Alfabet simbol
2. String finite dari simbol tertentu, wffs
3. Aksioma, definisi system
4. Baris inference, yang memungkinkan wff, A untuk dikurangi sebagai kesimpulan dari set finite wff lain dimana = {A1,A2,…An}. Wffs harus berupa aksioma atau teori lain dari sistem logis
RESOLUSI
Diperkenalkan oleh Robinson (1965)
Merupakan baris inference yg utama dalam prolog
Prolog menggunakan notasi “quantifier-free”
Prolog didasarkan pada logika predikat first-order
Sebelum resolusi diterapkan, wff harus berada dalam keadaan normal (bentuk standar) yaitu hanya menggunakan V , , ~
Mis wff (A V B) (~B V C) disebut bentuk normal konjungtif
A V B dan ~B V C
Ekspresi clausal umumnyya dituliskan dalam bentuk khusus yg disebut kowalski :
A1, A2, ………. AN B1, B2, ….BM
Dalam notasi predikat standar :
A1 A2 ………. AN B1 V B2 V, ….BM
Bentuk disjungsinya menggunakan
(p q) ~p v q
menjadi :
A1 A2 V ………. AN B1 V B2 V, ….BM
~(A1 A2 ………. AN ) V (B1 V B2 V, ….BM )
~A1 V ~A2 V ………. ~AN V B1 V B2 V, …. BM INGAT De Morgan ~(p q) ~p v ~q
Dengan klausa Horn menjadi :
A1, A2, ………. AN B
Dalam prolog :
B :- A1, A2, … AN
Untuk membuktikan teori benar dengan metode klasik “reductio ad absurdum” metode kontradiksi.
Tujuan resolusi adalah meng-infer klause baru “revolvent” dari 2 clause yang disebut parent clauses
Contoh
A V B
A V ~B
A
dapat ditulis sbb
(A V B) (A V ~B)
ingat distribusi :
p V (q r) (p V q) (p V r)
sehingga
(A V B) (A V ~B) A V (B ~B) A (resolvent)
ingat (B ~B) nil/null
SISTEM RESOLUSI DAN DEDUKSI
Refutation adalah salah satu type pembuktian yang salah
Contoh A B
B C
C D
A D
A B, B C, C D ├ A B
Buktikan bahwa kesimpulan adalah teori resolusi refulasi
Solusi :
Gunakan (p q) ~p v q untuk semua premise dan kesimpulan, kemudian negasikan untuk kesimpulannya, sehingga menjadi
(~A V B) (~B V C) (~C V D) A ~D
Pohon resolusi refutation
Terbukti bahwa A D adalah teori
Latihan :
B E
E E
E S F
F G R
R T C
B S G T C
RESOLUSI DAN LOGIKA PREDIKAT FIRT ORDER
Sebelum resolusi dapat diterapkan, wff harus diletakkan dalam bentuk casual
Contoh :
Some programmers hate all failures
No programmer hates any success
No failure is a success
P(x) = x is a progammer
F(x) = x is a failure
S(x) = x is a success
H(x,y) = x hates y
Premise dan kesimpulannya
(1) (x) [P(x) (y) (F(y) H(x,y))]
(2) (x) (P(x) (y) (S(y) ~H(x,y))]
(3) ~(y) (F(y) ~S(,y))
Konversi ke bentuk clausal
1. Hilangkan kondisional, (p q) ~p v q
2. Geser negasi ke dalam (reduksi skope ~).
Negasi digeser hanya berlaku untuk atomik formula
3. Hilangkan quantifier eksistensial
• Jika tidak ada dalam skope , ganti variabel dengan suatu konstanta baru
(x) P(x) diganti P(a)
• Jika berada dalam skope , ganti variabel dengan suatu fungsi yang memiliki argumen semua variabel dari tersebut
x ,y , z P(x,y,z) diganti menjadi
x,y, P(x,y,F(x,y))
4. Standarisasi variabel (jika perlu) sehingga tiap quantifier memiliki variabel yang berbeda
5. Geser semua ke kiri (karena semua quantifier punya nama yang berbeda, pergeseran tidak mempengaruhi hasil)
Bentuk ini disebut prenex normal form terdiri atas prefix quantifier yang diikuti matriks
6. Hilangkan . tidak perlu ditulis, diasumsikan semua variabel terkuantifikasi universal
7. Geser disjungsi (V) kedalam, sehingga terbentuk conjungsi normal form
8. Buang konjungsi dan uraikan menjadi klausa-klausa
9. Standarisasi variabel (jika perlu) sehingga tidak ada variabel yang muncul pada lebih dari 1 klausa.
Contoh : Ubah ke bentuk klausal !!!!!!
x (Balok (x) (y (Diatas(x,y) ~Piramid(y))
~y (Diatas(x,y) Diatas(y,x))
y (~Balok(y) ~Sama(x,y))))
Solusi :
1. x (~Balok (x) V (y (Diatas(x,y) ~Piramid(y))
~y (Diatas(x,y) Diatas(y,x))
y (~Balok(y) V ~Sama(x,y))))
2. x (~Balok (x) V (y (Diatas(x,y) ~Piramid(y))
y (~Diatas(x,y) V~ Diatas(y,x))
y (~Balok(y) V ~Sama(x,y))))
3. x (~Balok (x) V (Diatas(x,f(x)) ~Piramid(f(x)))
y (~Diatas(x,y) V~ Diatas(y,x))
y (~Balok(y) V ~Sama(x,y))))
4. x (~Balok (x) V (Diatas(x,f(x)) ~Piramid(f(x)))
y (~Diatas(x,y) V~ Diatas(y,x))
z (~Balok(z) V ~Sama(x,z))))
5. xyz (~Balok (x) V (Diatas(x,f(x)) ~Piramid(f(x)))
(~Diatas(x,y) V~ Diatas(y,x))
(~Balok(z) V ~Sama(x,z))))
6. (~Balok (x) V ((Diatas(x,f(x)) ~Piramid(f(x)))
(~Diatas(x,y) V~ Diatas(y,x))
(~Balok(z) V ~Sama(x,z))))
7. (~Balok (x) V Diatas(x,f(x))
(~Balok (x) V ~Piramid(f(x)))
(~Balok (x) V ~Diatas(x,y) V~ Diatas(y,x))
(~Balok (x) V ~Balok(z) V ~Sama(x,z))))
8. 1. ~Balok (x) V Diatas(x,f(x))
2. ~Balok (x) V ~Piramid(f(x))
3. ~Balok (x) V ~Diatas(x,y) V~ Diatas(y,x)
4. ~Balok (x) V ~Balok(z) V ~Sama(x,z)
9. 1. ~Balok (x) V Diatas(x,f(x))
2.~Balok (k) V ~Piramid(f(k))
3.~Balok (m) V ~Diatas(m,y) V~ Diatas(y,m)
4. ~Balok (n) V ~Balok(z) V ~Sama(n,z)
RANGKAIAN BACKWARD DAN FORWARD
Forward : bottom-up reasoning, breadth first
Backward : top-down reasoning, depth-first
Rangkaian forward Rangkaian Backward
-Planning, monitoring,control
-Saat sekarang ke masa depan
-Antecedent ke consequent
-Data driven, bottom-up
-Kerja mundur untuk menemukan pemecahan yg mengikuti fakta
-Breadth-first search
-Antecedent menentukan pencarian
-Fasilitas bukan penjelasan -Diagnosis
-Sekarang ke masa lalu
-Consequent ke antecedent
-Goal driven, top-down
-Kerja mundur untuk menemukan fakta yg mendukung hipotesa
-Depth-first search
-Consequent menentukan pencarian
-Fasilitas penjelasan
METODE LAIN DARI INFERENCE/KESIMPULAN
ANALOGI
Mencoba dan menghubungkan situasi lama sebagai penuntun ke situasi baru.
Contoh : diagnosis medical
Pemberian alasan analogis berhubungan dgn induksi
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 sama dg modus ponens
Abduction Modus ponens
p q p q
q p
p q
Bukan argument deduksi yg valid
Berguna untuk baris/rules heuristik inference
Analogi,generate and test, abduction adalah metode bukan deduksi. Dari premise yg benar, metode ini tidak dapat membuktikan kesimpulan yg benar
Perbedaan :
Inference Start Tujuan
FORWARD
BACKWARD
ABDUCTION Fakta
Kesimpulan tdk pasti
Kesimpulan benar Kesimpulan yg harus mengikuti
Fakta pendukung kesimpulan
Fakta yg dpt mengikuti
NONMONOTONIC REASONING
Tambahan aksioma yg baru pada sistem logika berarti bahwa banyak teori yg dapat dibuktikan jika ada banyak aksioma dari teori yg didapat, disebut monotonik sistem
METAKNOWLEDGE
Program meta-DENDRAL menggunakan induksi untuk menyimpulkan baris baru dari struktur kimia.
Contoh : TEIRESIAS yg menambah pengetahuan secara interaktif dari expert