Apa itu prinsip resolusi?

Resolusi adalah satu aturan inferensi yang mengambil dua klausa yang mengandung literal komplementer dan menghasilkan klausa baru yang menggabungkan sisanya. Diterapkan berulang kali dengan unifikasi, ini dapat menunjukkan bahwa serangkaian klausa orde pertama tidak dapat dipuaskan, yang merupakan dasar untuk membuktikan teorema melalui refutasi.

Apakah pembuktian teorema otomatis dijamin akan berakhir (terminate)?

Untuk logika proposisional, validitas dapat diputuskan, sehingga prosedur akan berakhir. Untuk logika orde pertama penuh, validitas hanya semi-terputuskan: pembukti yang lengkap pada akhirnya akan mengkonfirmasi formula yang valid, tetapi mungkin berjalan selamanya pada formula yang tidak valid, sehingga pengakhiran tidak dijamin secara umum.

Penalaran Logis dan Pembuktian Teorema

Penalaran logis dan pembuktian teorema berkaitan dengan penggunaan logika formal untuk merepresentasikan pengetahuan dan otomatisasi deduksi, yaitu menurunkan kesimpulan yang secara niscaya mengikuti dari serangkaian premis.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Pembuktian teorema adalah penurunan otomatis apakah suatu formula logis mengikuti dari serangkaian aksioma, biasanya dengan memanipulasi formula menggunakan aturan inferensi yang sahih hingga tujuan tercapai atau kontradiksi ditemukan.

Scope

Topik ini mencakup penalaran dalam logika proposisional dan logika orde pertama serta algoritma yang mengotomatiskannya: pemeriksaan kepuasan berbasis tabel kebenaran dan DPLL untuk logika proposisional, unifikasi dan prinsip resolusi untuk logika orde pertama, forward dan backward chaining, serta dasar-dasar pemrograman logika. Ini membahas keandalan (soundness), kelengkapan (completeness), dan keterputusan (decidability) prosedur inferensi. Penalaran yang mentolerir ketidakpastian atau nilai default dibahas dalam topik terkait mengenai penalaran dalam ketidakpastian dan penalaran non-monotonik.

Core questions

Apa artinya suatu kesimpulan diimplikasikan oleh serangkaian premis, dan bagaimana implikasi tersebut diperiksa secara mekanis?
Bagaimana prinsip resolusi, dengan unifikasi, memberikan satu aturan inferensi yang lengkap untuk logika orde pertama?
Bagaimana perbedaan antara forward dan backward chaining sebagai strategi inferensi?
Apa batasan penalaran otomatis, mengingat validitas orde pertama hanya semi-terputuskan (semi-decidable)?

Key concepts

logika proposisional dan orde pertama
implikasi (entailment) dan validitas
unifikasi
resolusi dan refutasi
DPLL dan penyelesaian SAT
forward dan backward chaining
klausa Horn dan pemrograman logika
keandalan (soundness) dan kelengkapan (completeness)

Key theories

Prinsip resolusi: Resolusi Robinson adalah satu aturan inferensi pada klausa yang, dikombinasikan dengan unifikasi, bersifat lengkap-refutasi untuk logika orde pertama: setiap himpunan klausa yang tidak dapat dipuaskan dapat ditunjukkan tidak dapat dipuaskan dengan menurunkan klausa kosong.
DPLL dan kepuasan proposisional: Prosedur Davis-Putnam dan penyempurnaan DPLL-nya memutuskan kepuasan proposisional dengan pembagian kasus sistematis dengan propagasi unit dan eliminasi literal murni, membentuk dasar pemecah SAT modern.
Pemrograman logika dan backward chaining: Membatasi logika orde pertama pada klausa Horn dan menyelesaikan tujuan secara mundur menghasilkan pemrograman logika, di mana komputasi adalah pencarian bukti, menyediakan metode penalaran dan paradigma pemrograman.

Clinical relevance

Pembuktian teorema otomatis dan penyelesaian SAT/SMT digunakan dalam verifikasi perangkat keras dan perangkat lunak, analisis program, perencanaan, dan matematika, sementara bahasa pemrograman logika seperti Prolog menerapkan inferensi backward-chaining ke basis data, penguraian (parsing), dan sistem berbasis aturan.

History

Prosedur pembuktian awal oleh Gilmore, Davis dan Putnam (1960) mengotomatiskan penalaran proposisional dan kuantifikasional, dan prinsip resolusi Robinson (1965) menyatukan inferensi orde pertama menjadi satu aturan. Tahun 1970-an menyaksikan resolusi disempurnakan menjadi pemrograman logika dan Prolog; penyelesaian SAT dan SMT kemudian berkembang menjadi teknologi praktis utama.

Key figures

John Alan Robinson
Martin Davis
Hilary Putnam
Robert Kowalski
Alan Robinson

Seminal works

robinson1965
davis1960
kowalski1979

Frequently asked questions

Apa itu prinsip resolusi?: Resolusi adalah satu aturan inferensi yang mengambil dua klausa yang mengandung literal komplementer dan menghasilkan klausa baru yang menggabungkan sisanya. Diterapkan berulang kali dengan unifikasi, ini dapat menunjukkan bahwa serangkaian klausa orde pertama tidak dapat dipuaskan, yang merupakan dasar untuk membuktikan teorema melalui refutasi.
Apakah pembuktian teorema otomatis dijamin akan berakhir (terminate)?: Untuk logika proposisional, validitas dapat diputuskan, sehingga prosedur akan berakhir. Untuk logika orde pertama penuh, validitas hanya semi-terputuskan: pembukti yang lengkap pada akhirnya akan mengkonfirmasi formula yang valid, tetapi mungkin berjalan selamanya pada formula yang tidak valid, sehingga pengakhiran tidak dijamin secara umum.