MATERI MINGGU 5-8

METODE PENCARIAN dan PELACAKAN 2 ( HEURISTIK ) MINGGU 5

5.1 BEST FIRST SEARCH

• Metode ini merupakan kombinasi dari metode depth first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.
• Tak seperti Hill Climbing, teknik Best First Search mempunyai kemampuan melakukan koreksi terhadap suatu langkah yang salah yang telah dipilih lebih dulu.
• Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan : 
f’(n) = g(n) + h’(n)
• f’ = Fungsi evaluasi
• g = cost dari initial state ke current state
• h’ = prakiraan cost dari current state ke goal state
• Contoh: Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode A adalah biaya yang dikeluarkan untuk bergerak dari kota M ke kota A. Nilai g diperoleh berdasarkan biaya edge minimal. Sedangkan nilai h’ di node A merupakan hasil perkiraan terhadap biaya yang diperlukan dari node A untuk sampai ke tujuan. h’(n) bernilai ~ jika sudah jelas tidak ada hubungan antara node n dengan node tujuan (jalan buntu). Kita bisa merunut nilai untuk setiap node.

5.2 PROBLEM REDUCTION

Problem Reduction (reduksi masalah) terbagi menjadi 2, yaitu Graf AND-OR dan Graf AO*

a. Graf AND-OR

    Pada dasarnya sama dengan Best First Search dengam mempertimbangkan adanya arc 

    AND.

>> Algoritma Graf AND-OR

•Inisialisasi graf ke node awal

•Kerjakan langkah-langkah berikut hingga node awal SOLVED atau sampai biayanya 

 lebih tinggi dari F_UTILITY :

a) Telusuri graf mulai dari node awal dan ikuti jalur terbaik. 

Akumulasikan kumpulan node yang ada pada lintasan tersebut. 

Dan belum pernah diekspansi atau diberilabel SOLVED.

b) Ambil satu node dan ekspansi node tsb. Jika tidak ada successor maka set

IF_UTILITY sebagai nilai dari node tsb. 

Bila tidak demikian, tambahkan successor dari node tersebut ke graf dan 

hitung nilaisetiap f’(hanya gunakan h’dan abaikan g). 

Jika f’=0 tandai node tersebut dengan SOLVED. 

c) Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini 

secara backward sepanjang graf. Jika node berisi suatu arc successor yang 

semua descendantnya berlabel SOLVED maka tandai node itud engan 

SOLVED.

b. Graf AO*

Menggunakan struktur graf. Tiap node pada graf memiliki nilai h’ yang merupakan

biaya estimasi jalur dari node itu sendiri sampai suatu solusi.

5.3 CONSTRAINT SATISFACTION

Constraint Satisfaction Problems (CSP) adalah sebuah pendekatan dari masalah

yang bersifat matematis dengan tujuan menemukan keadaan atau objek yang

memenuhi sejumlah persyaratan. Sebuah constraint diartikan sebagai sebuah

batasan dari solusi memungkinkan dalam sebuah problem optimasi.

CSP ini merupakan algoritma general-purpose dengan kekuatan lebih daripada

algoritma pencarian standar.

Contoh - contoh Constraint Satisfaction

•n-queen problem

•Crossword (teka-teki silang)

•Mewarnai Peta (map coloring)

•Soolean Satisfiability Problem (SAT)

•Cryptarithmatic Problem

5.4 MEANS END ANALYSIS

MEA adalah strategi penyelesaian masalah yang diperkenalkan pertama kali

dalam GPS (General Problem Solver).

Proses pencarian berdasarkan ruang masalah yang menggabungkan aspek

penalaran forward dan backward.

Perbedaan antara state current dan goal digunakan untuk mengusulkan

operator yang mengurangi perbedaan itu.

Keterhubungan antara operator dan perbedaan tsb disajikan sebagai

pengetahuan dalam sistem (pada GPS dikenal dengan Table of

Connections) atau mungkin ditentukan sampai beberapa pemeriksaan

operator jika tindakan operator dapat dipenetrasi.

Contoh OPERATOR first-order predicate calculus dan operator2 tertentu

mengijinkan perbedaan korelasi task-independent terhadap operator yang

menguranginya.

Kapan pengetahuan ada tersedia mengenai pentingnya perbedaan,

perbedaan yang paling utama terpilih pertama lebih lanjut meningkatkan

rata-rata capaian dari MEA di atas strategi pencarian Brute-Force.

Bagaimanapun, bahkan tanpa pemesanan dari perbedaan menurut arti

penting, MEA meningkatkan metode pencarian heuristik lain (di rata-rata

kasus) dengan pemusatan pemecahan masalah pada perbedaan yang

nyata antara current state dengan goal-nya.

REPRESENTASI PENGETAHUAN 

MINGGU 6

Representasi pengetahuan adalah cara untuk menyajikan pengetahuan yang diperoleh ke dalam suatu skema/diagram tertentu sehingga dapat diketahui relasi antara suatu pengetahuan dengan pengetahuan yang lain dan dapat dipakai untuk menguji kebenaran penalarannya.

Secara teknik kita akan membahas representasi pengetahuan menjadi lima kelompok:

1.    Representasi Logika

2.    Jaringan Semantik

3.    Frame

4.    Script (Naskah)

5.    Aturan Produksi (Kaidah Produksi)

    

1.    Representasi Logika

Logika didefinisikan sebagai ilmu untuk berpikir dan menalar dengan benar sehingga didapatkan kesimpulan yang absah.

Tujuan dari logika: memberikan aturan-aturan penalaran sehingga orang dapat menentukan apakah suatu kalimat bernilai benar atau salah.

Representasi Logika dibagi menjadi dua:

 Pembagian formal language

Formal Language	Apa yang ada di dunia nyata	Apa yang dipercayaagenttentang fakta
Propositional logic	Facts	True/false/unknown
First-order logic	Facts, objects, relations	True/false/unknown
Temporal logic	Facts, objects, relations, times	True/false/unknown
Probability theory	Facts	Degree of believe 0…1
Fuzzy logic	Degree of truth	Degree of believe 0…1

1. Propositional Logic (Logika Proposisi)

Suatu Proposisi merupakan suatu statemen atau pernyataan yang menyatakan benar (TRUE) atau salah (FALSE). Dalam PropositionalLogic fakta dilambangkan dengan simbol misalnya P, Q dan R.Lambang-lambang tersebut dihubungkan dengan relasi-relasi logika

Dengan menggunakan operator logika:

Tabel Kebenaran Logika

2. Predicate Logic (Logika Predikat)

Pada logika predikat proposisi dibedakan menjadi argumen (obyek) dan predikat (keterangan). Secara umum penulisan proposisi dalam logika predikat dapat dinyatakan sebagai berikut:

Predikat (argumen-1, argumen-2,..., argumen-3)

Contoh:

Proposisi: “Bu Atika mencintai Pak Agus Setiawan”

Dalam logika predikat disajikan dalam bentuk:

Mencintai (Bu Atika, Pak Agus Setiawan)

      P         Argumen-1            Argumen-2

Contoh Silsilah Keluarga yang dipresentasikan dalam Prolog

Jika silsilah di atas dibentuk dalam Representasi Logika, sebagai berikut:

Orangtua (Komarudin, Andika)

Orangtua (Komarudin, Atika)

Orangtua (Komarudin, Agus)

Orangtua (Andika, Rika)

Orangtua (Atika, Anjar)

2.  Jaringan Semantik

Pengetahuan disusun dalam sebuah jaringan yang memiliki komponen utama:

- Node: menyatakan obyek, konsep, atau situasi. Dinyatakan dengan kotak atau lingkaran

- Arcs/Link: Menyatakan hubungan antar node. Dinyatakan dengan tanda panah.

3.  Frame

Frames: merupakan semantic net dilengkapi dengan properties. Suatu Frame menggambarkan entitas sebagai set dari attribute dan nilai yang bersesuaian.Suatu frame dapat berelasi dengan frame yang lainnya.

Tiga komponen utama dari frame

•         frame name

•         attributes (slots)

•         values (subslots)

Book Frame

Slot à Subslots

Title     à AI. A modern Approach Author à Russell & Norvig Year    à 2003

Contoh di atas dibentuk dalam Frame:

Nama Frame: Burung
Orangtua	Hewan
Anak	Kenari, Pipit
Mempunyai	Sayap
Cara Berpindah tempat	Terbang

4.  Script (Naskah)

Conceptual Dependency (ketergantungan konseptual) adalah teori tentang bagaimana mempresentasikan pengetahuan tentang event (kejadian) yang biasanya terkandung dalam kalimat bahasa natural.

Contoh: representasi Conceptual Dependency

“Budi memberi Atika sebuah buku”

Script adalah skema representasi pengetahuan yang menggambarkan urutan-urutan kejadian (sequence of events). Script dilengkapi dengan elemen-elemen agar lebih memudahkan dalam memahami urutan kejadian.

a. Track/Jalur: variasi yang mungkin terjadi dalam script

b. Kondisi Input: situasi yang harus dipenuhi sebelum sesuatu kejadian terjadi

c. Prop/Pendukung: objek pendukung yang digunakan dalam urutan peristiwa yang terjadi ( yang harus ada )

d. Role/Peran: orang-orang yang terlibat dalam suatu peran

e. Scene/Adegan: urutan peristiwa aktual

f.  Hasil: kondisi akhir yang terjadi setelah urutan peristiwa dalam script terjadi

Keuntungan:

1. Mampu memprediksi event yang tidak disebutkan secara eksplisit.

2. Menyediakan cara pembangunan interpretasi tunggal dari sekumpulan observasi.

3. Mampu memfokuskan perhatian pada event yang “tidak biasa”.

Contoh 1:

John pergi ke restaurant kemarin malam. Dia memesan steak. Saat membayar, dia

menyadari uangnya kurang. Dia cepat pulang, karena hujan mulai turun.

Question: Apakah John makan malam?

(Dijawab dengan mengaktifkan Script restaurant)

Dari soal, urutan kejadian normal, sehingga pasti script restaurant berjalan normal, jadi

John pasti melewati tahap makan.

Conceptual Dependency (CD)

Merupakan Strong Slot-and-Filler structure karena menambahkan gagasan khusus tentang: apa tipe objek dan relasi yang diijinkan.

CD : Teori untuk merepresentasikan pengetahuan tentang kejadian yang terkandung dalam kalimat bahasa natural. Dengan catatan: menggambarkan penalaran kalimat dan tidak bergantung bahasa apa.

Contoh: I gave the man a book.

Dalam CD, representasi aksi dibangun dari himpunan aksi primitif, yaitu:

ATRANS	Transfer of abstract relationship (e.g., give)
PTRANS	Transfer of physical location of an object (e.g., go)
PROPEL	Application of the physical force to an object (e.g., push)
MOVE	Movement of a body part by its owner (e.g., kick)
GRASP	Grasping of an object by an actor (e.g., clutch)
INGEST	Ingestion of an object by an animal (e.g., eat)
EXPEL	Expulsion of something from the body of an animal (e.g., cry)
MTRANS	Transfer of mental information (e.g., go)
MBUILD	Building new information out of old (e.g., decide)
SPEAK	Production of sound (e.g., say)
ATTEND	Focusing of a sense organ toward a stimulus (e.g., listen)

Terdapat 4 katagori konseptual primitif yang dapat dibangun, yaitu:

• ACTS : aksi
• PPs : objek / gambaran prosedur
• AAs : peubah aksi (pendukung aksi)
• PAs : peubah PPs (pendukung gambaran)

Tenses:

p	Past
f	Future
t	Transition
ts	Start transition
tf	Finished transition
k	Continuing
?	Interrogative
/	Negative
nil	Present
delta	Timeless
c	Conditional

CD tidak bisa membedakan yang alurnya sama. Misalnya : give, take, steal, donate.

CD cocok untuk kalimat yang sederhana. Untuk primitif tingkat tinggi CD merepotkan.

Misal: “John bet Sam $50 that the Mets would win the World Series”

5.  Aturan Produksi (Kaidah Produksi)

Pengetahuan dalam kaidah produksi direpresentasikan dalam bentuk

       JIKA [kondisi] MAKA [Aksi]

       JIKA [premis] MAKA [Konklusi]

Aturan Produksi (kaidah produksi) adalah salah satu representasi pengetahuan yang menghubungkan premis dengan konklusi.

Bentuknya: If Premis Then Konklusi

Konklusi pada bagian then bernilai benar jika premis pada bagian if bernilai benar.

Contoh:

If  hari ini hujan then saya tidak kuliah.

REPRESENTASI PENGETAHUAN LOGIKA PROPOSISI

MINGGU 7

Representasi pengetahuan dengan symbol logika merupakan bagian dari penalaran eksak. Bagian yang paling penting dalam penalaran adalah mengambil kesimpulan dari premis. Logika dikembangkan oleh filusuf Yunani, Aristoteles (abad ke 4 SM) didasarkan pada silogisme, dengan dua premis dan satu konklusi.

Contoh :

– Premis : Semua laki-laki adalah makhluk hidup

– Premis : Socrates adalah laki-laki

– Konklusi : Socrates 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

Logika Proposisi

Logika Proposisi disebut juga kalkulus proposisi yang merupakan logika simbolik untuk memanipulasi proposisi. Proposisi merupakan pernytaan yang dapat bernilai benar atausalah.

Operator logika yang digunakan :

Operator	Fungsi
∧	Konjungsi (AND/DAN)
∨	Disjungsi (OR/ATAU)
~	Negasi (NOT/TIDAK)
->	Implikasi/Kondisional (IF..THEN../JIKA.. MAKA….)
↔	Equivalensi/Bikondisional

(IF AND ONLY IF / JIKA DAN HANYA JIKA)

p ↔q≡(p -> q) ∧(q -> p)

 Kondisional merupakan operator yang analog dengan production rule.

 Contoh 1 :

 “ Jika hujan turun sekarang maka saya tidak pergi ke pasar”

Kalimat di atas dapat ditulis : p -> q

Dimana : p = hujan turun

q = saya tidak pergi ke pasar

Contoh 2 :

 p = “Anda berusia 21 atau sudah tua”

q = “Anda mempunyai hak pilih”

Kondisional p -> q dapat ditulis/berarti : 

Kondisional	Berarti
p implies q	Anda berusia 21 tahun atau sudah tua implies Anda mempunyai hak pilih.
Jika p maka q	Jika Anda berusia 21 tahun atau sudah tua, maka Anda mempunyai hak pilih.
p hanya jika q	Anda berusia 21 tahun atau sudah tua, hanya jika Anda mempunyai hak pilih.
p adalah (syarat

cukup untuk q)Anda berusia 21 tahun atau sudah tua adalah syarat cukup Anda mempunyai hak pilih.q jika pAnda mempunyai hak pilih, jika Anda berusia 21 tahun atau sudah tua.q adalah (syarat

perlu untuk p)Anda mempunyai hak pilih adalah syarat perlu Anda berusia 21 tahun atau sudah tua.

Logika Proposisi juga menjelaskan tentang :

Tautologi: pernyataan gabungan yang selalu bernilai benar.

Kontradiksi: pernyataan gabungan yang selalu bernilai salah.

Contingent: pernyataan yang bukan tautology ataupun kontradiksi.

Tabel Kebenaran untuk logika konektif :

p	q	p ^ q	p v q	p -> q	p ↔ q
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

Tabel kebenaran untuk negasi konektif :

p	~p
T	F
F	T

REPRESENTASI PENGETAHUAN LOGIKA PREDIKAT

MINGGU 8

Logika Predikat Order Pertama 

Logika Predikat Order Pertama disebut juga kalkulus predikat, merupakan logika yang digunakan untuk merepresentasikan masalah yang tidak dapat direpresentasikan dengan menggunakan proposisi. Logika predikat dapat memberikan representasi fakat-fakta sebagai suatu pernyataan yang mapan (well form).

Logika orde pertama adalah sistem resmi yang digunakan dalam matematika , filsafat ,linguistik , dan ilmu komputer . Hal ini juga dikenal sebagai orde pertama predikat kalkulus, semakin rendah kalkulus predikat, teori kuantifikasi, dan logika predikat. Logika orde pertama dibedakan dari logika proposisional oleh penggunaan variabel terukur .

Sebuah teori tentang beberapa topik biasanya logika orde pertama bersama-sama dengan yang ditentukan domain wacana dimana variabel diukur berkisar, finitely banyak fungsi yang memetakan dari domain yang ke dalamnya, finitely banyak predikat didefinisikan pada domain tersebut, dan satu set rekursif dari aksioma yang diyakini terus untuk hal-hal. Kadang-kadang “teori” dipahami dalam arti yang lebih formal, yang hanya satu set kalimat dalam logika orde pertama.

Kata sifat “orde pertama” membedakan orde pertama logika darilogika tingkat tinggi di mana ada predikat yang memiliki predikat atau fungsi sebagai argumen, atau di mana salah satu atau kedua bilangan predikat atau fungsi bilangan diizinkan. Dalam first teori order, predikat sering dikaitkan dengan set. Dalam ditafsirkan tingkat tinggi teori, predikat dapat ditafsirkan sebagai set set.

Ada banyak sistem deduktif untuk orde pertama logika yang sehat(semua laporan dapat dibuktikan benar dalam semua model) danlengkap (semua pernyataan yang benar dalam semua model yang dapat dibuktikan). Meskipun konsekuensi logis hubungan hanyasemidecidable , banyak kemajuan telah dibuat dalam teorema otomatis dalam logika orde pertama. Logika orde pertama juga memenuhi beberapa metalogical teorema yang membuatnya setuju untuk analisis dalam teori bukti , seperti teorema Löwenheim-Skolem dan teorema kekompakan .

Logika orde pertama adalah standar untuk formalisasi matematika menjadi aksioma dan dipelajari di dasar matematika . Teori matematika, seperti nomor teori dan teori himpunan , telah diresmikan menjadi orde pertama aksioma skema seperti Peano aritmatika dan Zermelo-Fraenkel teori himpunan masing-masing (ZF).

Tidak ada teori orde pertama, bagaimanapun, memiliki kekuatan untuk menggambarkan sepenuhnya dan kategoris struktur dengan domain yang tak terbatas, seperti bilangan asli atau garis nyata .Sistem aksioma kategoris untuk struktur ini dapat diperoleh dalam logika kuat seperti logika orde kedua .

Syarat-syarat symbol dalam logika predikat :

• himpunan huruf, baik huruf kecil maupun huruf besar dalam abjad.
• Himpunan digit (angka) 0,1,2,…9
• Garis bawah “_”
• Symbol-simbol dalam logika predikat dimulai dengan sebuah huruf dan diikuti oleh sembarang rangkaian karakter-karakter yang diijinkan.
• Symbol-simbol logika predikat dapat merepresentasikan variable, konstanta, fungsi atau predikat.

Logika Predikat Order Pertama terdiri dari :

Konstanta: objek atau sifat dari semesta pembicaraan. Penulisannya diawali denganhuruf kecil, seperti : pohon, tinggi. Konstanta true(benar) dan false(salah) adalah symbol kebenaran (truth symbol).

Variable : digunakan untuk merancang kelas objek atau sifat-sifat secara umum dalam semesta pembicaraan. Penulisannya diawali dengan huruf besar, seperti : Bill, Kate.

Fungsi : pemetaan (mapping) dari satu atau lebih elemen dalam suatu himpunan yang disebut domainfungsi ke dalam sebuah elemen unik pada himpunan lain yang disebutrangefungsi. Penulisannya dimulai dengan huruf kecil. Suatu ekspresi fungsi merupakan symbol fungsi yang diikuti argument.

Argument adalah elemen-elemen dari fungsi, ditulis diapit tanda kurung dan dipisahkan dengan tanda koma.

Predikat: menamai hubungan antara nol atau lebih objek dalam semesta pembicaraan. Penulisannya dimulai dengan huruf kecil, seperti : equals, sama dengan, likes, near.

Contoh kalimat dasar :

teman(george,allen)

teman(ayah_dari(david),ayah_dari(andrew))

dimana:

argument : ayah_dari(david) adalah george

argument : ayah_dari(andrew) adalah allen

predikat : teman

Quantifier Universal

Dalam logika predikat , quantifieri universal merupakan jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “diberi” atau “untuk semua”. Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setiapanggota dari domain wacana. Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setiap anggota domain. Ini menegaskanbahwa predikat dalam lingkup dari quantifier universal benar dari setiap nilai dari variabel predikat .

Hal ini biasanya dilambangkan dengan berbalik A (∀) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier universal  (“∀x”, “∀ (x)”, atau kadang-kadang dengan “(x) “saja). Kuantifikasi Universal berbeda dari kuantifikasi eksistensial (“ada ada”), yang menegaskan bahwa properti atau relasi hanya berlaku untuk setidaknya satu anggota dari domain.

Contoh 1 :

(∀x) (x + x = 2x)

“untuk setiap x (dimana x adalah suatu bilangan), kalimat x + x = 2x adalah benar.”

Contoh 2 :

(∀x) (p) (Jika x adalah seekor kucing -> x adalah binatang).

Kebalikan kalimat “bukan kucing adalah binatang” ditulis :

(∀x) (p) (Jika x adalah seekor kucing -> ~x adalah binatang)

dan dibaca :

– “setiap kucing adalah bukan binatang”

“semua kucing adalah bukan binantang”

Contoh 3:

(∀x) (Jika x adalah segitiga -> x adalah polygon)

Dibaca : “untuk semua x, jika x adalah segitiga, maka x adalah polygon”.

Dapat pula ditulis : (∀x) (segitiga(x) -> polygon(x))

(∀x) (T(x) -> P(x))

Contoh 4 :

(∀x) (H(x) -> M(x))

Dibaca : “untuk semua x, jika x adalah manusia (human), maka x melahirkan (mortal)”.

Ditulis dalam aturan : IF x adalah manusia THEN x melahirkan.

Digambar dalam jaringan semantic :

Quantifier Exsistensial

Dalam logika predikat , suatu quantifier eksistensial adalah jenis quantifier , sebuah konstanta logis yang ditafsirkan sebagai “ada ada,” “ada setidaknya satu,” atau “untuk beberapa.” Ini mengungkapkan bahwa fungsi proposisi dapat dipenuhi oleh setidaknya satu anggota dari domain wacana . Dalam istilah lain, itu adalah predikasi dari properti atau hubungan dengan setidaknya satu anggota dari domain. Ini menegaskan bahwa predikat dalamlingkup dari quantifier eksistensial adalah benar dari setidaknya satu nilai darivariabel predikat .

Hal ini biasanya dilambangkan dengan E berubah (∃) operator logika simbol, yang bila digunakan bersama-sama dengan variabel predikat, disebut quantifier eksistensial (“∃x” atau “∃ (x)”) Kuantifikasi eksistensial.

Contoh 1 :

(∃x) (x . x = 1)

Dibaca : “terdapat x yang bila dikalikan dengan dirinya sendiri hasilnya sama dengan 1.”

Contoh 2 :

(∃x) (gajah(x) ∧ nama(Clyde))

Dibaca : “beberapa gajah bernama Clyde”.

Contoh 3 :

(∀x) (gajah(x) -> berkaki empat(x))

Dibaca : “semua gajah berkaki empat”.

Universal quantifier dapat diekspresikan sebagai konjungsi.

(∃x) (gajah(x) ∧ berkaki tiga(x))

Dibaca : “ada gajah yang berkaki tiga”

Existensial quantifier dapat diekspresikan sebagai disjungsi dari

urutan ai. P(a1) ∨ P(a2) ∨ P(a3) …∨ P(aN)

Quantifier dan Set / Jaringan

Set Expression	Logical Equivalent
A = B	∀x (x ∈A ↔ x ∈B)
A ⊆ B	∀x (x ∈A -> x ∈B)
A ∩ B	∀x (x ∈A ∧x ∈B)
A ∪ B	∀x (x ∈A ∨x ∈B)
μ(universe)	T (True)
φ(empty set)	F (False)

• Relasi A proper subset dari B ditulis A ⊂ B, dibaca “semua elemen A ada pada B”, dan “paling sedikit satu elemen B bukan bagian dari A”.

• Hukum de Morgan berlaku untuk analogi himpunan dan bentuk logika :

Himpunan	Logika
(A∩B)≡A’∪B’	~(p∧q) ≡p∨~q
(A∪B)≡A’∩B’	~(p∨q) ≡p ∧~q

Contoh :

Diketahui :

E = elephant

R = reptile

G = gray

F = four legged

D = dogs

M = mammals

Set expression	Berarti
E ⊂M	“elephant termasuk mammals”, tetapi tidak semua mammals adalah elephant
(E ∩G ∩F) ⊂M	“elephant yang berwarna gray dan memiliki four legged termasuk mammals”
E ∩R = φ	“tidak ada elephant yang termasuk reptile”
E ∩G ≠φ	“beberapa elephant berwarna gray”
E ∩G = φ	“tidak ada elephant yang berwarna gray”
E ∩G’≠φ	“beberapa elephants tidak berwarana gray”
E ⊂(G ∩F)	“semua elephants berwarna gray dan memiliki four legged”
(E ∪D) ⊂M	“semua elephants dan dogs termasuk mammals”
(E ∩F ∩G) ≠φ	“beberapa elephants memiliki four legged dan berwarna gray”

Batasan Logika Predikat

Logika proposisional sudah cukup untuk menangani pernyataan-pernyataan yang sederhana.

Pernyataan yang mengandung kata, semua, ada atau kata yang lain tidak bisa diselesaikan.

Untuk pernyataan yang lebih rumit, misal:

A = semua mahasiswa pandai.

B = Badu seorang mahasiswa.

C = Dengan demikian, Badu pasti pandai.

bentuk ekspresi logika

(A ∧ B) → C : tidak bisa dibuktikan!

Bila menginginkan diselesaikan dengan logika proposisi, pernyataan pernyataannya harus dirubah menjadi

A → B = Jika Badu mahasiswa, maka ia pasti pandai.

A = Badu seorang mahasiswa.

B = Dengan demikian, ia pasti pandai

(( A → B) ∧ A) → B

Logika predikat merupakan pengembangan dari logika proposisional dengan masalah pengkuantoran dan menambah istilah-istilah baru.

Istilah dalam Logika Predikat:

Term : kata benda atau subjek

Predikat : properti dari term

Fungsi proposisional=fungsi

Kuantor

– Universal: yang selalu bernilai benar (∀).

Contoh :

• Semua gajah mempunyai belalai
• G(x) = gajah
• B(x) = belalai

Bentuk logika predikat

(∀x)(G(x)→B(x))

Dibaca: untuk semua x, jika x seekor gajah, maka x mempunyai belalai.

– Eksistensial: bisa bernilai benar atau salah(∃).

Contoh :

• Ada bilangan prima yang bernilai genap.
• P(x) = bilangan prima
• G(x) = bernilai genap

Bentuk logika predikat

(∃x)(P(x)∧G(x))

Dibaca: ada x, yang x adalah bilangan prima dan x bernilai genap.

Contoh Logika Predikat:

Nani adalah ibu dari Ratna.

Term=nani , ratna

Predikat=adalah ibu dari

Fungsi=ibu(nani,ratna) ; M(n,r)

Bentuk logika predikat:

M(n,r)→¬M(r,n)