Propositional Dynamic Logic

Daftar Isi:

Propositional Dynamic Logic
Propositional Dynamic Logic

Video: Propositional Dynamic Logic

Video: Propositional Dynamic Logic
Video: Logic for Programmers: Propositional Logic 2024, Maret
Anonim

Navigasi Masuk

  • Isi Entri
  • Bibliografi
  • Alat Akademik
  • Pratinjau PDF Teman
  • Penulis dan Info Kutipan
  • Kembali ke atas

Propositional Dynamic Logic

Publikasi pertama, 1 Februari 2007; revisi substantif Jum 25 Jan 2019

Logika program adalah modal logika yang timbul dari gagasan untuk mengasosiasikan dengan setiap program komputer α dari bahasa pemrograman sebagai modalitas [α]. Gagasan ini berasal dari garis karya Engeler [1967], Hoare [1969], Yanov [1959], dan lainnya yang merumuskan dan mempelajari bahasa logis di mana sifat-sifat penghubung program dapat diekspresikan. Logika algoritmik (AL) pertama kali dikembangkan oleh Salwicki [1970] dan logika dinamis (DL) yang diuraikan oleh Pratt [1976] adalah kelanjutan yang tepat dari karya-karya ini. Kami di sini akan berkonsentrasi pada DL. Banyak makalah yang ditujukan untuk DL dan variannya serta berbagai aplikasi dalam verifikasi program dan struktur data menunjukkan bahwa ia merupakan alat yang berguna dalam mempelajari sifat-sifat program. Pratt memilih untuk menggambarkan DL pada apa yang orang sebut tingkat orde pertama,dan itu adalah karyanya yang memicu Fischer dan Ladner [1979] untuk menentukan varian proposisional DL beberapa tahun kemudian. Artikel ini menyajikan pengantar untuk PDL, varian proposisional dari DL.

  • 1. Perkenalan
  • 2. Definisi dan hasil mendasar

    • 2.1 Sintaks dan semantik
    • 2.2 Aksioma dan kelengkapan
    • 2.3 Desidabilitas dan kompleksitas
  • 3. Pemrograman terstruktur dan kebenaran program

    • 3.1 Kalkulus Hoare
    • 3,2 Hoare kalkulus dan PDL
    • 3.3 Total kebenaran
  • 4. Beberapa varian

    • 4.1 PDL tanpa tes
    • 4.2 PDL dengan berbicara
    • 4.3 PDL dengan pengulangan dan pengulangan
    • 4.4 PDL dengan persimpangan
  • 5. Kesimpulan
  • Bibliografi
  • Alat Akademik
  • Sumber Daya Internet lainnya
  • Entri terkait

1. Perkenalan

Dynamic Logics (DL) adalah logika modal untuk mewakili keadaan dan kejadian sistem dinamis. Bahasa DLs adalah bahasa asersi yang mampu mengekspresikan properti status komputasi, dan bahasa pemrograman yang mampu mengekspresikan properti transisi sistem antara status ini. DL adalah logika program, dan memungkinkan untuk berbicara dan bernalar tentang keadaan, proses, perubahan, dan hasil.

Logika dinamis asli program Pratt adalah logika modal tingkat pertama. Propositional Dynamic Logic (PDL) adalah mitra proposisionalnya. Itu disajikan sebagai logika dalam dirinya sendiri di Fischer dan Ladner [1979]. Menjadi proposisional, bahasa PDL tidak menggunakan istilah, predikat, atau fungsi. Jadi dalam PDL, ada dua kategori sintaksis: proposisi dan program.

Untuk memberi makna pada pernyataan dalam PDL, kami biasanya bekerja dengan semantik abstrak dalam hal Sistem Transisi Berlabel (LTS). LTS dapat dilihat sebagai generalisasi model Kripke, di mana transisi antar dunia, atau negara, "diberi label" dengan nama program atom. Penilaian menunjukkan untuk setiap negara bagian mana yang benar proposisi di dalamnya. Transisi berlabel π dari satu keadaan x ke keadaan y-dicatat x R (π) y, atau (x, y) ∈ R (π) -menunjukkan bahwa mulai dari x, ada kemungkinan eksekusi program π yang selesai di y. Jika proposisi A benar dalam y, maka rumus A benar dalam x: yaitu, dalam keadaan x ada kemungkinan eksekusi program α yang berakhir pada keadaan memuaskan A. Seseorang mengakui dalam modalitas yang mengingatkan pada modalitas kemungkinan (sering dicatat ◊) dari logika modal. Tidak mengejutkan,ada juga gagasan kebutuhan yang sesuai (yang modalnya sering dicatat □). Rumus [π] A akan benar di negara x jika A benar di setiap negara yang dapat dijangkau dari x dengan transisi berlabel π.

Eksekusi yang mungkin dari program yang kompleks dapat didefinisikan selanjutnya secara komposisi. Misalnya, program "α pertama, lalu β" adalah program yang kompleks, lebih khusus urutan. Eksekusi yang mungkin dapat direpresentasikan dalam LTS dengan menyusun transisi dua langkah -telah transisi yang dapat ditandai oleh R (α; β) -di antara status x dan x ': ada kemungkinan eksekusi dalam x program α yang selesai dalam keadaan y dan ada kemungkinan eksekusi di y dari program β yang selesai di x '. Jika proposisi A benar dalam x ', maka rumus A akan benar dalam keadaan x. Program α dan β bisa merupakan program yang kompleks sendiri. Namun lebih banyak program dapat diekspresikan dengan lebih banyak konstruksi yang akan kami sajikan pada waktunya.

Suatu program kemudian dilihat dalam cara ekstensional: itu adalah hubungan biner antara pasangan keadaan LTS. Tepatnya, itu adalah himpunan pasangan bentuk (x, y) sedemikian rupa sehingga program dapat dieksekusi di negara x dan dapat menyebabkan negara y. Di sisi lain, proposisi adalah pernyataan tentang negara; itu benar atau salah dalam keadaan. Proposisi dengan demikian juga dapat dilihat dengan cara ekstensional: seperangkat keadaan LTS di mana ia benar.

Dengan akronim PDL, di sini kita merujuk tepat ke logika dinamis proposisional dengan konstruksi program berikut: urutan, pilihan non-deterministik, iterasi tanpa batas, dan tes. Kami menyajikannya di bagian 2, bersama dengan beberapa properti dan hasil mendasar. Secara khusus, kami akan membahas aksiomisasi dan kepantasannya.

Kalkulus Hoare dari Hoare [1969] adalah tengara untuk logika program. Ini menyangkut kebenaran pernyataan dalam bentuk {A} α {B} -berarti bahwa dengan prasyarat A, program α selalu memiliki B sebagai kondisi pasca-dan didefinisikan secara aksiomatis. Itu datang dari keinginan metode yang keras untuk alasan tentang sifat-sifat program, dan dengan demikian memberikan kegiatan pemrograman tempat tertentu di bidang ilmu pengetahuan. Burstall [1974] melihat analogi antara modal logika dan penalaran tentang program, tetapi pekerjaan yang sebenarnya dimulai dengan Pratt [1976] ketika disarankan kepadanya oleh R. Moore, seorang siswa pada saat itu. PDL berasal dari interpretasi Pratt tentang kalkulus Hoare dalam formalisme logika modal. Pengantar asal usul PDL dapat ditemukan di Pratt [1980b]. Hoare-triple {A} α {B} ditangkap oleh rumus PDL A → [α] B yang secara harfiah berarti bahwa jika A benar, maka setiap eksekusi yang berhasil menghentikan eksekusi α akan berakhir dengan B menjadi true. Dengan koneksi ini direalisasikan, merupakan rutinitas untuk membuktikan aturan awal kalkulus Hoare menggunakan secara eksklusif aksioma PDL. Ini adalah sesuatu yang akan kita lakukan secara rinci dalam bagian 3 yang berkonsentrasi pada alasan tentang kebenaran program terstruktur.

Topik tambahan yang terkait dengan PDL mencakup hasil mengenai kekuatan ekspresi komparatif, decidability, kompleksitas, dan kelengkapan sejumlah varian menarik yang diperoleh dengan memperluas atau membatasi PDL dengan berbagai cara. Sejak awal, banyak varian PDL telah menerima perhatian. Varian ini dapat mempertimbangkan program deterministik, pengujian terbatas, program tidak reguler, program sebagai automata, komplemen dan persimpangan program, perhitungan converse dan infinite, dll. aksioma mereka, dan kompleksitas komputasi mereka.

Kami menyimpulkan di bagian 5.

2. Definisi dan hasil mendasar

Kami menyajikan sintaks dan semantik PDL di bagian 2.1. Teori pembuktian PDL disajikan pada bagian 2.2 dengan aksioma dan petunjuk pada literatur tentang kelengkapan. Kami membahas masalah decidability dan kompleksitas di bagian 2.3.

2.1 Sintaks dan semantik

Propositional dynamic logic (PDL) dirancang untuk mewakili dan memberi alasan tentang sifat proposisional program. Sintaksnya didasarkan pada dua set simbol: satu set yang dapat dihitung Φ 0 dari rumus atom dan satu set yang dapat dihitung Π 0 dari program atom. Rumus kompleks dan program kompleks di atas basis ini didefinisikan sebagai berikut:

  • Setiap rumus atom adalah rumus
  • 0 ("false") adalah rumus
  • Jika A adalah formula maka ¬ A (“bukan A”) adalah formula
  • Jika A dan B adalah rumus maka (A ∨ B) ("A atau B") adalah rumus
  • Jika α adalah program dan A adalah rumus maka [α] A (“setiap eksekusi α dari kondisi saat ini mengarah ke keadaan di mana A benar”) adalah rumus
  • Setiap program atom adalah program
  • Jika α dan β adalah program maka (α; β) (“do α diikuti oleh β”) adalah program
  • Jika α dan β adalah program maka (α∪β) (“do α atau β, non-deterministically”) adalah sebuah program,
  • Jika α adalah program maka α * (“ulangi α hingga, tetapi ditentukan secara non-determinasi, berapa kali”) adalah sebuah program.
  • Jika A adalah formula maka A? (“Lanjutkan jika A benar, kalau tidak gagal”) adalah sebuah program

Konektif Boolean lainnya 1, ∧, →, dan ↔ digunakan sebagai singkatan dengan cara standar. Selain itu, kami menyingkat ¬ [α] ¬ A ke A ("beberapa eksekusi α dari keadaan saat ini mengarah ke keadaan di mana A benar") seperti dalam logika modal. Kami menulis α n untuk α; …; α dengan n kemunculan α. Lebih formal:

  • α 0 = df 1?
  • α n +1 = df α; α n

Juga:

α + = df α; α *

sering berguna untuk mewakili iterasi yang tidak terbatas tetapi terjadi setidaknya satu kali. Akhirnya, kami mengadopsi aturan standar untuk penghilangan tanda kurung.

Rumus dapat digunakan untuk menggambarkan properti yang dimiliki setelah keberhasilan eksekusi suatu program. Misalnya, rumus [α∪β] A berarti bahwa setiap kali program α atau β berhasil dieksekusi, keadaan tercapai di mana A berada, sedangkan rumus A berarti bahwa ada urutan eksekusi bergantian dari α dan β sedemikian rupa sehingga negara tercapai di mana A berada. Secara semantik, rumus ditafsirkan oleh set negara dan program ditafsirkan oleh hubungan biner atas negara dalam sistem transisi. Lebih tepatnya, arti dari formula dan program PDL diinterpretasikan di atas Sistem Transisi Berlabel (LTS) M = (W, R, V) di mana W adalah himpunan nonempty dari dunia atau negara, R adalah pemetaan dari set Π 0 atom program ke dalam hubungan biner pada W dan V adalah pemetaan dari himpunan Φ 0 rumus atom ke dalam himpunan bagian dari W.

Secara informal, pemetaan R menetapkan untuk setiap program atom π ∈ Π 0 beberapa hubungan biner R (π) pada W dengan makna yang dimaksudkan x R (π) y jika jika ada eksekusi π dari x yang mengarah ke y, sedangkan pemetaan V menugaskan setiap rumus atom p ∈ Φ 0 beberapa subset V (p) dari W dengan makna yang dimaksudkan x ∈ V (p) jika p benar dalam x. Mengingat bacaan kami 0, ¬ A, A ∨ B, [α] A, α; β, α∪β, α * dan A?, Jelas bahwa R dan V harus diperluas secara induktif sebagai berikut untuk memasok makna yang dimaksud untuk program dan formula yang rumit:

  • x R (α; β) y jika ada dunia z sedemikian sehingga x R (α) z dan z R (β) y
  • x R (α∪β) y iff x R (α) y atau x R (β) y
  • x R (α *) y jika jika ada bilangan bulat non-negatif dan ada dunia z 0, …, z n sedemikian sehingga z 0  = x, z n  = y dan untuk semua k = 1.. n, z k −1 R (α) z k
  • x R (A?) y iff x = y dan y ∈ V (A)
  • V (0) = ∅
  • V (¬ A) = W / V (A)
  • V (A ∨ B) = V (A) ∪ V (B),
  • V ([α] A) = {x: untuk semua dunia y, jika x R (α) y maka y ∈ V (A)}

Jika x ∈ V (A) maka kita mengatakan bahwa A puas pada keadaan x dalam M, atau “M, x sat A”.

Dua LTS bisimilar
Dua LTS bisimilar

Sebut M LTS yang digambarkan di atas di sebelah kiri dan M 'LTS yang digambarkan di sebelah kanan. Didefinisikan secara formal, kita memiliki M = (W, R, V) dengan W = {x 1, x 2 }, R (π 1) = {(x 1, x 1)}, R (π 2) = {(x 1, x 2)}, V (p) = {x 1 }, V (q) = {x 2 }, dan kami memiliki M '= (W', R ', V') dengan W '= {y 1, y 2, y 3, y 4 }, R (π 1) = {(y 1, y 2), (y 2, y 2)}, R '(π2) = {(y 1, y 3), (y 2, y 4)}, V '(p) = {y 1, y 2 }, V' (q) = {y 3, y 4 }}. Kami punya misalnya:

  • M, x 1 sat, hlm
  • M, x 2 sat q
  • M, x 1 sat <π 1 > p ∧ <π 2 > q
  • M, x 1 sat [π 1] p ∧ [π 1 *] p
  • M ', y 1 sat <π 1 *; π 2 > q
  • M ', y 2 sat [π 1 *] hlm
  • M ', y 1 sat [π 1 ∪π 2] (q ∨ p)
  • M ', y 3 sat [π 1 ∪π 2] 0

Sekarang pertimbangkan rumus A. Kita mengatakan bahwa A valid dalam M atau bahwa M adalah model A, atau “M ⊨ A”, iff untuk semua dunia x, x ∈ V (A). A dikatakan valid, atau "⊨ A", jika untuk semua model M, M ⊨ A. Kita mengatakan bahwa A memuaskan dalam M atau M memuaskan A, atau “M sat A”, jika ada dunia x sedemikian rupa sehingga x ∈ V (A). A dikatakan memuaskan, atau "sat A", jika ada model M sehingga M sat A. Menariknya,

sat A iff not ⊨ ¬ A

⊨ A iff not sat ¬ A

Beberapa formula PDL yang luar biasa valid. (Pembaca dapat mencoba membuktikannya secara formal, atau setidaknya mulai meyakinkan diri mereka sendiri pada beberapa contoh yang ditampilkan di atas.)

⊨ [α; β] A ↔ [α] [β] A

⊨ [α∪β] A ↔ [α] A ∧ [β] A

⊨ [α *] A ↔ A ∧ [α] [α *] A

⊨ [A?] B ↔ (A → B)

Secara ekuivalen, kita dapat menuliskannya dalam bentuk rangkap.

⊨ A ↔ A

⊨ A ↔ A ∨ A

⊨ A ↔ A ∨ A

⊨ <A?> B ↔ A ∧ B

Satu gagasan menarik menyangkut jumlah informasi, yang diungkapkan dengan formula PDL, yang terkandung dalam LTS. Perilaku suatu sistem yang digambarkan sebagai LTS memang sering sedikit tersembunyi dalam bentuknya. Misalnya, pada pemeriksaan sederhana, mudah meyakinkan diri sendiri bahwa dua LTS yang digambarkan di atas memiliki perilaku yang sama, dan memenuhi formula PDL yang sama. Untuk menyelesaikan bagian ini tentang sintaks dan semantik, kami memberikan landasan teoretis dari klaim-klaim ini.

Diberikan dua LTS, orang mungkin bertanya apakah mereka memenuhi formula yang sama. Gagasan bisimulasi telah menjadi ukuran standar untuk kesetaraan model Kripke dan Sistem Transisi Berlabel. Bisimulasi antara LTS M = (W, R, V) dan M '= (W', R ', V') adalah hubungan biner Z antara negara-negara mereka sehingga untuk semua dunia x dalam M dan untuk semua dunia x ' di M ', jika xZx' maka

  • untuk semua rumus atom p ∈ Φ 0, x ∈ V (p) iff x '∈ V' (p)
  • untuk semua program atom π ∈ Π 0 dan untuk semua dunia y dalam M, jika x R (π) y maka ada dunia y 'dalam M' sehingga yZy 'dan x' R '(π) y'
  • untuk semua program atom π ∈ Π 0 dan untuk semua dunia y 'di M', jika x 'R' (π) y 'maka ada dunia y di M sehingga yZy' dan x R (π) y

Kami mengatakan bahwa dua LTS adalah bisimilar ketika ada bisimulasi di antara mereka. Telah diketahui sejak awal PDL bahwa dalam dua bisimilar LTS M dan M ', untuk semua dunia x dalam M dan untuk semua dunia x' dalam M ', jika xZx' maka untuk semua rumus PDL A, x ∈ V (A) iff x '∈ V' (A). Jadi ketika dua LTS bisimilar di bawah definisi bisimulasi di atas, itu adalah kasus itu, jika xZx 'maka

  • untuk semua program α dan untuk semua dunia y dalam M, jika x R (α) y maka ada dunia y 'di M' sehingga yZy 'dan x' R '(α) y'
  • untuk semua program α dan untuk semua dunia y 'di M', jika x 'R' (α) y 'maka ada dunia y di M sehingga yZy' dan x R (α) y

Oleh karena itu seseorang dapat dengan mudah membandingkan perilaku dua LTS dengan hanya memeriksa program atom dan dengan aman memperkirakan pada perilaku komparatif LTS ini bahkan untuk program yang kompleks. Kami mengatakan bahwa konstruksi program PDL aman untuk bisimulasi. Lihat Van Benthem [1998] untuk karakterisasi yang tepat dari konstruksi program yang aman untuk bisimulasi.

Dapat dilihat bahwa dua contoh LTS di atas adalah bisimilar. Bisimulasi Z antara M dan M 'dapat diberikan sebagai: Z = {(x 1, y 1), (x 1, y 2), (x 2, y 3), (x 2, y 4)}. Status x 1 dan y 1 memenuhi formula PDL yang persis sama. Begitu juga status x 1 dan y 2, dll.

2.2 Aksioma dan kelengkapan

Tujuan dari teori pembuktian adalah untuk memberikan karakterisasi properti ⊨ A dalam hal aksioma dan aturan inferensi. Pada bagian ini, kami mendefinisikan predikat deducibilitas ⊢ secara induktif oleh operasi pada formula yang hanya bergantung pada struktur sintaksisnya sedemikian rupa sehingga untuk semua formula A,

⊢ A iff ⊨ A.

Tentu saja, PDL adalah perpanjangan dari logika proposisional klasik. Kami pertama-tama berharap bahwa semua tautologi proposisional berlaku, dan semua penalaran proposisional diizinkan. Secara khusus, modus ponens adalah aturan yang valid: dari A dan A → B menyimpulkan B. Untuk setiap program α, membatasi LTS ke hubungan R (α) kita mendapatkan model Kripke di mana logika modalitas [α] adalah logika modal normal proposisional terlemah, yaitu, logika K. Dengan demikian, PDL berisi setiap contoh dari skema aksioma distribusi akrab:

(A0) [α] (A → B) → ([α] A → [α] B)

dan ditutup berdasarkan aturan inferensi berikut (aturan keharusan):

(N) dari A menyimpulkan [α] A.

Modal logika adalah normal jika mematuhi (A0) dan (N). Properti penting untuk semua α, adalah bahwa [α] didistribusikan melalui konjungsi ∧, dan aturan monoton, yang memungkinkan dari A → B untuk menyimpulkan [α] A → [α] B, dapat dibuktikan. Akhirnya, PDL adalah logika modal paling tidak normal yang berisi setiap instance dari skema aksioma berikut

(A1) [α; β] A ↔ [α] [β] A

(A2) [α∪β] A ↔ [α] A ∧ [β] A

(A3) [α *] A ↔ A ∧ [α] [α *] A

(A4) [A?] B ↔ (A → B)

dan ditutup di bawah aturan inferensi berikut (aturan invarian loop):

(I) dari A → [α] A menyimpulkan A → [α *] A

Jika X adalah himpunan rumus dan A adalah rumus maka kita mengatakan bahwa A adalah ded-dapat dikurangkan dari X, atau "X ⊢ A", jika ada urutan A 0, A 1, …, A n dari rumus sedemikian rupa sehingga A n  = A dan untuk semua i ≤ n, A i adalah turunan dari skema aksioma, atau rumus X, atau berasal dari formula sebelumnya dari urutan dengan aturan inferensi. Selanjutnya, ⊢ A iff ∅ ⊢ A; dalam hal ini kita mengatakan bahwa A adalah ded-deducible. X dikatakan konsisten if jika tidak X ⊢ 0. Mudah untuk menetapkan bahwa (I) dapat diganti dengan skema aksioma berikut (skema aksioma induksi):

(A5) [α *] (A → [α] A) → (A → [α *] A)

Mari kita pertama-tama menetapkan bahwa (I) adalah aturan turunan dari sistem bukti berdasarkan (A1), (A2), (A3), (A4) dan (A5):

1. A → [α] A premis
2. [α *] (A → [α] A) dari 1 menggunakan (N)
3. [α *] (A → [α] A) → (A → [α *] A) skema aksioma (A5)
4. A → [α *] A dari 2 dan 3 menggunakan mode ponens

Mari kita selanjutnya menetapkan bahwa (A5) adalah ded-deducible:

1. [α *] (A → [α] A) ↔ (A → [α] A) ∧ [α] [α *] (A → [α] A) skema aksioma (A3)
2. A ∧ [α *] (A → [α] A) → [α] (A ∧ [α *] (A → [α] A)) dari 1 menggunakan penalaran proporsional dan distributivitas [α] lebih dari ∧
3. A ∧ [α *] (A → [α] A) → [α *] (A ∧ [α *] (A → [α] A)) dari 2 menggunakan (I)
4. [α *] (A → [α] A) → (A → [α *] A) dari 3 menggunakan penalaran proporsional dan distributivitas [α *] lebih dari ∧

Aksiomaasi PDL berdasarkan skema aksioma (A1), (A2), (A3), (A4) dan (A5) telah diusulkan dalam Segerberg [1977]. Langsung dari definisi di atas bahwa ⊢ masuk akal sehubungan dengan ⊨, yaitu

Untuk semua rumus A, jika ⊢ A, maka ⊨ A

Buktinya hasil dengan induksi pada panjang pengurangan A di ⊢. Pertanyaan tentang kelengkapan ⊢ sehubungan dengan ⊨, yaitu,

Untuk semua rumus A, jika ⊨ A, maka ⊢ A

dikejar oleh beberapa ahli logika. Garis penalaran yang disajikan dalam Segerberg [1977] adalah upaya pertama untuk membuktikan kelengkapan ⊢. Segera, Parikh datang dengan bukti juga. Ketika awal 1978 Segerberg menemukan kelemahan dalam argumennya (yang akhirnya dia perbaiki), Parikh menerbitkan apa yang dapat dianggap sebagai bukti pertama dari kelengkapan ⊢ dalam Parikh [1978]. Berbagai bukti kelengkapan ⊢ telah dipublikasikan sejak itu, misalnya Kozen dan Parikh [1981].

Berbagai teori pembuktian alternatif PDL juga telah dicari. Bahkan sejak awal, terutama dalam Pratt [1978]. Mari kita juga menyebutkan kelengkapan teori terkait oleh Nishimura [1979] dan Vakarelov [1983].

Formulasi alternatif predikat deducibilitas untuk PDL memungkinkan penggunaan aturan inferensi infinitary, seperti misalnya dalam Goldblatt [1992a]. (Sebuah aturan inferensi infinitari mengambil jumlah premis yang tak terbatas.) Mari ⊢ 'menjadi predikat deducibilitas yang bersesuaian dalam bahasa logika dinamik proposisional dengan logika modal paling tidak normal yang berisi setiap instance skema aksioma (A1), (A2), (A3) dan (A4) dan ditutup di bawah aturan inferensi infinitary berikut:

(I ') dari {[β] [α n] A: n ≥ 0} menyimpulkan [β] [α *] A

Dapat dibuktikan bahwa ⊢ 'baik dan lengkap dengan hormat ⊨, yaitu,

Untuk semua rumus A, ⊢ 'A iff ⊨ A

Dengan kata lain, sejauh menghasilkan himpunan semua formula yang valid yang bersangkutan, sistem bukti ⊢ dan ⊢ 'adalah setara.

2.3 Desidabilitas dan kompleksitas

Tujuan dari teori kompleksitas adalah untuk membangun kemampuan komputasi dari sat sat dalam hal sumber daya waktu atau ruang. Kompleksitas dari logika L sering diidentifikasikan dengan masalah penentuan kepuasan formula-formula tersebut, didefinisikan sebagai:

(L-SAT) Diberikan rumus A dari L, apakah A memuaskan?

Di bagian ini, kami menyelidiki kompleksitas masalah keputusan berikut:

(PDL-SAT) Diberikan rumus A dari PDL, apakah A memuaskan?

Aksiomaasi lengkap PDL adalah definisi berulang dari himpunan rumus PDL yang valid, atau dengan kata lain, himpunan rumus yang negasinya tidak memuaskan. Karenanya, mengenai masalah (PDL-SAT), kami memiliki sub-prosedur yang akan menjawab "tidak" jika rumus A PDL tidak memuaskan. Sub-prosedur (SP1) terdiri dalam penghitungan semua rumus ⊢-deducible, mulai dari aksioma dan menyimpulkan teorema lain dengan bantuan aturan inferensi. Dengan waktu yang cukup, jika formula is-deducible, sub-prosedur akan menemukannya pada akhirnya. Jadi, jika A tidak memuaskan, (SP1) pada akhirnya harus menemukan ¬ A, dan menjawab "tidak" ketika itu.

Namun, jika rumus A memuaskan, maka (SP1) tidak akan pernah menemukan ¬ A. Itu akan berjalan selamanya, dan orang tidak bisa memastikannya kapan saja. Namun ada jalan keluar dari ketidakpastian ini. Kami juga dapat memikirkan sub-prosedur kedua yang menjawab "ya" jika formula PDL memuaskan. Memang, salah satu hasil paling awal pada PDL adalah bukti bahwa PDL memiliki properti model yang terbatas, yaitu,

Untuk semua rumus A, jika sat A maka ada model hingga M sehingga M sat A.

Properti model hingga menawarkan dasar untuk sub-prosedur (SP2) yang terdiri dalam penghitungan satu demi satu model PDL hingga dan menguji apakah salah satu dari mereka memenuhi formula. (Untuk semua rumus A dan untuk semua model hingga M, mudah untuk menguji apakah M sat A dengan menerapkan definisi V (A).) Jadi, jika A memuaskan, pada akhirnya harus menemukan model M sedemikian rupa sehingga M sat A, dan jawab "ya" saat itu. Secara simetris dengan sub-prosedur pertama (SP1), jika rumus A tidak memuaskan, maka (SP2) tidak akan pernah menemukan model yang memuaskannya, itu akan berjalan selamanya, dan orang tidak dapat memastikannya kapan saja.

Sekarang, menggabungkan (SP1) dan (SP2) bersama-sama kita memiliki cara untuk memutuskan apakah formula PDL A memuaskan. Cukup menjalankannya secara paralel: jika A memuaskan maka (SP2) pada akhirnya akan menjawab "ya", jika A tidak memuaskan maka (SP1) pada akhirnya akan menjawab "tidak". Prosedur berhenti ketika (SP1) atau (SP2) memberikan jawaban.

Jika prosedur yang diperoleh cukup untuk menyimpulkan bahwa masalah (PDL-SAT) dapat ditentukan, maka dalam praktiknya sangat tidak efektif. Ada hasil-karena Fischer dan Ladner [1979] dan Kozen dan Parikh [1981] - lebih kuat dari properti model hingga, yaitu properti model kecil:

Untuk semua rumus A, jika sat A maka ada model hingga M dengan ukuran eksponensial dalam A sehingga M sat A.

Ini berarti bahwa kita sekarang akan tahu kapan harus berhenti mencari model yang memenuhi formula dalam prosedur (SP2). Oleh karena itu, kita dapat menggunakan (SP2) untuk menguji apakah suatu formula memuaskan, tetapi begitu kita telah kehabisan semua model kecil, kita dapat menyimpulkan bahwa formula tersebut tidak memuaskan. Ini menghasilkan prosedur yang berjalan secara non-deterministik dalam waktu eksponensial (NEXPTIME): tebak model ukuran paling banyak secara eksponensial tunggal, dan periksa apakah itu memenuhi formula. Tetapi hasil utama dalam teori kompleksitas PDL berasal dari Fischer dan Ladner [1979] dan Pratt [1980a]. Mengamati bahwa rumus PDL dapat secara efisien menggambarkan perhitungan mesin Turing bergantian linear-space-bounded, Fischer dan Ladner [1979] pertama kali menetapkan batas bawah waktu eksponensial (PDL-SAT). Batas atas EXPTIME (PDL-SAT) telah diperoleh oleh Pratt [1980a],yang menggunakan persamaan untuk PDL dari metode tableaux. Dengan demikian, (PDL-SAT) adalah EXPTIME-complete. (Algoritma yang lebih efisien dalam praktiknya, meskipun masih berjalan dalam waktu eksponensial deterministik dalam kasus terburuk, diusulkan dalam De Giacomo dan Massacci [2000].)

3. Pemrograman terstruktur dan kebenaran program

Secara historis, logika program berasal dari karya ilmuwan komputer akhir 1960-an yang tertarik untuk memberi makna pada bahasa pemrograman dan menemukan standar yang ketat untuk bukti tentang program tersebut. Misalnya bukti tersebut mungkin tentang kebenaran suatu program berkenaan dengan perilaku yang diharapkan, atau tentang penghentian suatu program. Makalah mani adalah Floyd [1967] yang menyajikan analisis sifat-sifat program komputer terstruktur menggunakan diagram alur. Beberapa karya awal seperti Yanov [1959] atau Engeler [1967] telah maju dan mempelajari bahasa formal di mana sifat-sifat penghubung program dapat diekspresikan. Formalisme Hoare [1969] adalah tonggak penting dalam munculnya PDL. Itu diusulkan sebagai interpretasi aksiomatik yang ketat dari diagram alur Floyd. Kita sering berbicara tentang logika Hoare, atau logika Floyd-Hoare,atau kalkulus Hoare ketika merujuk pada formalisme ini. Hoare calculus berkaitan dengan kebenaran pernyataan (“Hoare triples”), seperti {A} α {B} yang membentuk hubungan antara prasyarat A, program α, dan kondisi pasca B. Ini menunjukkan bahwa setiap kali A berlaku sebagai prasyarat pelaksanaan α, maka B berlaku sebagai kondisi pascakondisi setelah keberhasilan eksekusi α.

Memang benar beberapa dekade yang lalu, dan itu masih terjadi: memvalidasi program lebih sering daripada tidak dilakukan dengan mengujinya pada berbagai input yang masuk akal. Ketika input tidak menghasilkan output yang diharapkan, "bug" diperbaiki. Jika pada akhirnya untuk setiap input yang diuji, kami memperoleh output yang diharapkan, seseorang memiliki keyakinan yang masuk akal bahwa program tidak memiliki kesalahan. Namun, ini adalah metode validasi yang memakan waktu, dan meninggalkan tempat untuk input yang belum teruji yang akan gagal. Menemukan kesalahan ini setelah program diimplementasikan dan mulai digunakan bahkan lebih mahal dalam sumber daya. Penalaran tentang kebenaran program dengan metode formal sangat penting untuk sistem kritis karena ia menawarkan cara untuk membuktikan secara mendalam bahwa suatu program tidak memiliki kesalahan.

3.1 Kalkulus Hoare

Untuk mengilustrasikan prinsip-prinsip program yang ditangkap oleh aturan dalam kalkulus Hoare, cukup berkonsultasi dengan beberapa di antaranya. (NB: aturannya berarti bahwa jika semua pernyataan di atas garis aturan memiliki-tempat-maka-juga pernyataan di bawah garis aturan-kesimpulan-berlaku.)

{A} α 1 {B} {B} α 2 {C} (aturan komposisi)
{A} α 1; α 2 {C}

Aturan komposisi menangkap komposisi sekuensial elementer dari program. Sebagai premis, kami memiliki dua asumsi tentang kebenaran parsial dari dua program α 1 dan α 2. Asumsi pertama adalah bahwa ketika α 1 dieksekusi dalam keadaan memuaskan A, maka akan berakhir dalam keadaan memuaskan B, kapan pun ia berhenti. Asumsi kedua adalah bahwa ketika α 2 dieksekusi dalam keadaan memuaskan B, maka akan berakhir dalam keadaan memuaskan C, kapan pun ia berhenti. Kesimpulan aturan adalah tentang kebenaran sebagian dari program α 1; α 2 (yaitu, α 1 secara berurutan disusun dengan α 2), yang mengikuti dari dua asumsi. Yaitu, kita dapat menyimpulkan bahwa jika α 1; α 2 dieksekusi dalam keadaan memuaskan A, maka selesai dalam keadaan memuaskan C, setiap kali berhenti.

Aturan iterasi adalah aturan yang penting karena menangkap kemampuan penting dari program untuk mengeksekusi beberapa bagian kode berulang kali hingga kondisi tertentu tidak lagi berlaku.

{A ∧ B} α {A} (aturan iterasi)
{A} sementara B do α {¬ B ∧ A}

Akhirnya, dua aturan konsekuensi sangat mendasar untuk memberikan dasar formal untuk penalaran yang secara intuitif jelas melibatkan masing-masing kondisi pasca yang lebih lemah dan prasyarat yang lebih kuat.

{A} α {B} B → C (aturan konsekuensi 1)
{A} α {C}
C → A {A} α {B} (aturan konsekuensi 2)
{C} α {B}

Dari formalisme yang dihadirkan di Hoare [1969], kami mengabaikan skema aksioma karena memerlukan bahasa tingkat pertama. Akhirnya, dalam pekerjaan selanjutnya pada logika Hoare, lebih banyak aturan juga sering ditambahkan. Lihat Apt [1979] untuk ikhtisar awal.

3,2 Hoare kalkulus dan PDL

Logika dinamis berasal dari interpretasi Pratt tentang Hoare tiga kali lipat dan kalkulus Hoare dalam formalisme logika modal. Dengan modalitas [α], kita dapat menyatakan secara formal bahwa semua status yang dapat dicapai dengan mengeksekusi α memenuhi rumus A. Ini dilakukan dengan menulis [α] A. Dengan demikian, triple Hoare {A} α {B} hanya ditangkap oleh rumus PDL

A → [α] B

Selain itu, konstruksi pemrograman penting mudah diperkenalkan di PDL dengan singkatan definisi:

  • jika A maka α lagi β = df ((A?; α) ∪ (¬ A?; β))
  • sementara A do α = df ((A?; α) *; ¬ A?)
  • ulangi α hingga A = df (α; ((¬ A; α) *; A?))
  • batalkan = df 0?
  • lewati = df 1?

Dengan demikian, tampaknya dengan PDL kami diperlengkapi dengan baik untuk secara logis membuktikan kebenaran program terstruktur. Di luar hubungan yang agak melambaikan tangan ini antara PDL dan kalkulus Hoare, mungkin belum jelas bagaimana mereka berhubungan secara formal. Sebenarnya PDL adalah generalisasi dari kalkulus Hoare dalam arti bahwa semua aturan kalkulus Hoare dapat dibuktikan dalam sistem aksiomatik PDL. (Dengan ketat, kalkulus Hoare berisi aksioma yang akan membutuhkan bahasa lanjutan dari Dynamic Logic orde pertama.) Ini sangat luar biasa, jadi kami akan menunjukkan di sini dua aturan di atas untuk dijadikan contoh.

Buktinya mulai dengan mengasumsikan premis aturan. Kemudian dengan menggunakan asumsi ini, aksioma dan aturan PDL, dan tidak ada yang lain, tujuannya adalah untuk menetapkan bahwa kesimpulan dari aturan tersebut secara logis mengikuti. Karenanya, untuk aturan komposisi, kita mulai dengan mengasumsikan {A} α 1 {B}, yaitu A → [α 1] B dalam formulasi PDL-nya, dan dengan mengasumsikan {B} α 2 {C}, yaitu B → [α 2] C. Tujuannya adalah untuk membuktikan bahwa {A} α 1; α 2 {C}. Tepatnya, kami ingin menetapkan bahwa A → [α 1; α 2] C adalah ded-dapat dikurangkan dari himpunan rumus {A → [α 1] B, B → [α 2] C}.

1. A → [α 1] B asumsi {A} α 1 {B}
2. B → [α 2] C asumsi {B} α 2 {C}
3. 1] B → [α 1] [α 2] C Dari 2 menggunakan monoton [α 1]
4. A → [α 1] [α 2] C dari 1 dan 3 menggunakan penalaran proposisional
5. 1; α 2] C ↔ [α 1] [α 2] C skema aksioma (A1)
6. A → [α 1; α 2] C dari 4 dan 5 menggunakan penalaran proposisional
- {A} α 1; α 2 {C}

Bukti aturan iterasi sedikit lebih banyak terlibat.

1. A ∧ B → [α] A asumsi {A ∧ B} α {A}
2. A → (B → [α] A) dari 1 menggunakan penalaran proposisional
3. [B?] [Α] A ↔ (B → [α] A) skema aksioma (A4)
4. A → [B?] [Α] A dari 2 dan 3 menggunakan penalaran proposisional
5. [B?; α] A ↔ [B?] [α] A skema aksioma (A1)
6. A → [B?; Α] A dari 4 dan 5 menggunakan penalaran proposisional
7. A → [(B?; Α) *] A dari 6 menggunakan (I)
8. A → (¬ B → (¬ B ∧ A)) tautologi proposisional
9. A → [(B?; Α) *] (¬ B → (¬ B ∧ A)) dari 7 dan 8 menggunakan monoton [(B?; α) *] dan penalaran proposisional
10. [¬ B?] (¬ B ∧ A) ↔ (¬ B → (¬ B ∧ A)) Skema aksioma (A4)
11. A → [(B?; Α) *] [¬ B?] (¬ B ∧ A) dari 9 dan 10 menggunakan monoton [(B?; α) *] dan penalaran proposisional
12. [(B?; Α) *; ¬ B?] (¬ B ∧ A) ↔ [(B?; Α) *] [¬ B?] (¬ B ∧ A) skema aksioma (A1)
13. A → [(B?; Α) *; ¬ B?] (¬ B ∧ A) dari 12 menggunakan penalaran proposisional
- {A} sementara B do α {¬ B ∧ A}

Dalam konteks PDL, dua aturan konsekuensi sebenarnya adalah kasus khusus aturan komposisi. Untuk mendapatkan aturan pertama, gantikan α 1 dengan α dan α 2 dengan lewati. Untuk mendapatkan aturan kedua, gantikan α 1 dengan lewati dan α 2 dengan α. Cukuplah untuk menerapkan skema aksioma (A4), dan untuk menyatakan bahwa [α; lewati] A ↔ [α] A dan [α; lewati] A ↔ [α] A juga dapat direduksi ⊢ untuk semua A dan semua α.

3.3 Total kebenaran

Dengan pengakuan Hoare sendiri di Hoare [1979], kalkulus aslinya hanyalah titik awal dan mengalami beberapa keterbatasan. Khususnya, itu hanya memungkinkan seseorang untuk berpikir tentang kebenaran parsial. Yaitu, kebenaran pernyataan {A} α {B} hanya memastikan bahwa semua eksekusi α dimulai dalam keadaan memuaskan A akan berakhir dalam keadaan memuaskan B, atau tidak akan berhenti. Artinya, sebagian program yang benar mungkin memiliki eksekusi non-terminating. (Faktanya, sebuah program yang tidak memiliki eksekusi terminasi akan selalu sebagian benar. Ini adalah contoh dari program saat 1 dilewati. Formula A → [ sementara 1 dilewati] B dapat dikurangkan untuk semua rumus A dan B.) Kalkulus tidak menawarkan dasar untuk bukti bahwa suatu program berakhir. Hal ini dapat dimodifikasi untuk memperhitungkan kebenaran total program: kebenaran parsial ditambah penghentian. Itu dicapai dengan mengubah aturan iterasi. Kami tidak menyajikannya di sini dan merujuk pembaca yang tertarik ke Apt [1981].

Mari kita amati bahwa untuk program deterministik, seseorang sudah dapat menangkap kebenaran total melalui formula semacam itu

A → B

Ekspresi B berarti bahwa ada eksekusi α yang berakhir dalam keadaan yang memenuhi B. Selain itu, jika α bersifat deterministik, eksekusi terminasi yang mungkin ini adalah eksekusi unik α. Jadi, jika seseorang pertama-tama berhasil membuktikan bahwa suatu program bersifat deterministik, trik ini cukup berhasil untuk membuktikan kebenaran totalnya.

Solusi umum untuk masalah kebenaran total ada di ranah PDL. Tapi kita perlu sedikit memperluasnya. Pratt telah menyinggung dalam Pratt [1980b] bahwa PDL tidak cukup ekspresif untuk menangkap looping program yang tak terbatas. Sebagai reaksi, PDL dengan pengulangan (RPDL) diperkenalkan oleh Streett [1982]. Berisi, untuk semua program α, ekspresi Δα berarti proposisi baru dengan semantik

V (Δα) = {x: terdapat urutan tak terhingga x 0, x 1,… dari keadaan sedemikian sehingga x 0  = x dan untuk semua n ≥ 0, x n R (α) x n +1 }

Streett [1982] menduga bahwa RPDL dapat di aksioma dengan menambahkan ke sistem bukti PDL tepatnya skema aksioma berikut.

(A6) Δα → Δα

(A7) [α *] (A → A) → (A → Δα)

Bukti dugaan diberikan dalam Sakalauskaite dan Valiev [1990]. (Versi dugaan dalam varian PDL kombinasi juga terbukti dalam Gargov dan Passy [1988].)

Sangat mudah untuk melihat bahwa dalam kalkulus Hoare yang disajikan di atas, non terminasi hanya dapat berasal dari aturan iterasi. Secara analogi, non terminasi program PDL hanya dapat berasal dari penggunaan iterasi tanpa batas. Ungkapan Δα menunjukkan bahwa α * dapat berbeda, dan ini hanya jenis gagasan yang kita butuhkan. Kita sekarang dapat secara induktif mendefinisikan predikat ∞ sedemikian rupa sehingga untuk program α, rumus ∞ (α) akan benar tepat ketika α dapat memasukkan perhitungan non-terminating.

∞ (π): = 0 di mana π ∈ Π 0

∞ (φ?): = 0

∞ (α ∪ β): = ∞ (α) ∨ ∞ (β)

∞ (α; β): = ∞ (α) ∨ ∞ (β)

∞ (α *): = Δα ∨ ∞ (α)

Akhirnya, kebenaran total dari suatu program dapat diekspresikan melalui formula semacam itu

A → (¬∞ (α) ∧ [α] B)

yang berarti secara harfiah bahwa jika A adalah kasusnya, maka program α tidak dapat berjalan selamanya dan setiap eksekusi yang berhasil akan berakhir dalam keadaan memuaskan B.

4. Beberapa varian

Hasil mengenai kekuatan komparatif ekspresi, decidability, kompleksitas, aksiomatisasi dan kelengkapan sejumlah varian PDL yang diperoleh dengan memperluas atau membatasi sintaksnya dan semantiknya merupakan subjek dari banyak literatur. Kami hanya bisa mengatakan banyak dan kami akan membahas hanya beberapa varian ini meninggalkan potongan besar pekerjaan penting dalam logika dinamis.

4.1 PDL tanpa tes

Skema aksioma [A?] B ↔ (A → B) tampaknya menunjukkan bahwa untuk setiap rumus C, ada rumus bebas-uji setara C '-yaitu, ada rumus bebas uji C' sedemikian rupa sehingga ⊨ C ↔ C '. Sangat menarik untuk mengamati bahwa pernyataan ini tidak benar. Biarkan PDL 0 menjadi batasan PDL untuk program reguler bebas tes, yaitu program yang tidak mengandung tes. Berman dan Paterson [1981] menganggap rumus PDL <(p?; Π) *; ¬ p?; Π; p?> 1, yaitu

< while p do π> p

dan membuktikan bahwa tidak ada rumus PDL 0 yang setara dengannya. Oleh karena itu, PDL memiliki kekuatan lebih ekspresif daripada PDL 0. Argumen mereka sebenarnya dapat digeneralisasi sebagai berikut. Untuk semua n ≥ 0, misalkan PDL n +1 menjadi himpunan bagian dari PDL di mana program dapat berisi tes A? hanya jika A adalah rumus PDL n. Untuk semua n ≥ 0, Berman dan Paterson menganggap PDL n +1 rumus A n +1 yang didefinisikan oleh

< sementara A n do π n > <π n > A n

di mana A 0  = p dan π 0  = π dan membuktikan bahwa untuk semua n ≥ 0, tidak ada rumus PDL n yang setara dengan A n +1. Oleh karena itu, untuk semua n ≥ 0, PDL n +1 memiliki kekuatan lebih ekspresif daripada PDL n.

4.2 PDL dengan berbicara

CPDL adalah ekstensi dari PDL dengan converse. Ini adalah konstruksi yang telah dipertimbangkan sejak awal PDL. Untuk semua program α, biarkan α -1 berarti program baru dengan semantik

x R (α -1) y iff y R (α) x.

Konversi sebaliknya memungkinkan kita untuk mengungkapkan fakta tentang keadaan sebelum yang sekarang dan untuk alasan mundur tentang program. Sebagai contoh, [α -1] A berarti bahwa sebelum menjalankan α, A harus menahan. Kita punya

⊨ A → [α] <α -1 > A, ⊨ A → [α -1] A.

Penambahan konstruksi sebaliknya tidak mengubah sifat-sifat PDL dengan cara yang signifikan. Dengan menambahkan setiap contoh skema aksioma berikut:

(A8) A → [α] <α -1 > A

(A9) A → [α -1] A

untuk sistem pembuktian PDL, kami memperoleh predikat deducibilitas yang lengkap dan lengkap dalam bahasa yang diperluas. Lihat Parikh [1978] untuk detailnya. CPDL memiliki properti model kecil dan (CPDL-SAT) adalah EXPTIME-complete.

Sangat mudah untuk mengatakan bahwa CPDL memiliki kekuatan lebih ekspresif daripada PDL. Untuk melihat ini, pertimbangkan rumus CPDL <π -1 > 1 dan LTS M = (W, R, V) dan M '= (W', R ', V') di mana W = {x, y}, R (π) = {(x, y)}, W '= {y'}, R '(π) = ∅ dan V (x) = V (y) = V' (y ') = ∅. Karena M, y sat <π -1 > 1, bukan M ', y' sat <π -1 > 1, dan karena untuk semua rumus PDL A, inilah kasus M, y sat A iff M ', y' sat A, maka jelas bahwa tidak ada rumus PDL yang setara dengan <π -1 > 1.

4.3 PDL dengan pengulangan dan pengulangan

Kami telah mengungkapkan kekuatan pengulangan di bagian 3.3 dengan memperkenalkan RPDL. Di sini, kami merangkum lebih banyak hasil tentang RPDL dan hubungannya dengan variasi lain pada gagasan program berulang.

Mengenai teori kompleksitas RPDL, Streett [1982] telah menetapkan bahwa RPDL memiliki properti model yang terbatas; tepatnya bahwa setiap RPDL formula yang memenuhi syarat A memuaskan dalam model ukuran paling banyak tiga kali lipat eksponensial dalam panjang A. Argumen automata-teoritik diizinkan untuk menyimpulkan bahwa masalah (RPDL-SAT) dapat diselesaikan dalam waktu eksponensial tiga deterministik (3-EXPTIME). Kesenjangan antara batas atas ini untuk menentukan (RPDL-SAT) dan batas bawah waktu-eksponensial sederhana untuk memutuskan (PDL-SAT) dengan demikian terbuka. Masalahnya menemukan dirinya sangat terhubung dengan meningkatnya minat para ilmuwan komputer dalam membangun kompleksitas logika temporal, dan lebih khusus dari modal (proposisional) kalkulus (MMC) karena Kozen [1983], karena RPDL memiliki pukulan linear. terjemahan ke MMC. Bahkan,Argumen Streett agak menetapkan preseden dalam penggunaan teknik automata yang sekarang luas dalam membuktikan sifat komputasi dari logika program dan logika temporal. Dalam Vardi dan Stockmeyer [1985], batas atas dalam waktu eksponensial non-deterministik ditunjukkan. Dalam Emerson dan Jutla [1988] dan dalam bentuk terakhirnya di Emerson dan Jutla [1999], ditunjukkan bahwa (MMC-SAT) dan (RPDL-SAT) adalah EXPTIME-complete. Jika kita menambahkan operator converse dari bagian 4.2 seseorang memperoleh CRPDL. Kompleksitas (CRPDL-SAT) tetap terbuka selama beberapa tahun, tetapi juga dapat terlihat lengkap-EKSPTIM. Ini dicapai dengan menggabungkan teknik Emerson dan Jutla [1988] dan Vardi [1985], seperti dalam Vardi [1998]. Dalam Vardi dan Stockmeyer [1985], batas atas dalam waktu eksponensial non-deterministik ditunjukkan. Dalam Emerson dan Jutla [1988] dan dalam bentuk terakhirnya di Emerson dan Jutla [1999], ditunjukkan bahwa (MMC-SAT) dan (RPDL-SAT) adalah EXPTIME-complete. Jika kita menambahkan operator converse dari bagian 4.2 seseorang memperoleh CRPDL. Kompleksitas (CRPDL-SAT) tetap terbuka selama beberapa tahun, tetapi juga dapat terlihat lengkap-EKSPTIM. Ini dicapai dengan menggabungkan teknik Emerson dan Jutla [1988] dan Vardi [1985], seperti dalam Vardi [1998]. Dalam Vardi dan Stockmeyer [1985], batas atas dalam waktu eksponensial non-deterministik ditunjukkan. Dalam Emerson dan Jutla [1988] dan dalam bentuk terakhirnya di Emerson dan Jutla [1999], ditunjukkan bahwa (MMC-SAT) dan (RPDL-SAT) adalah EXPTIME-complete. Jika kita menambahkan operator converse dari bagian 4.2 seseorang memperoleh CRPDL. Kompleksitas (CRPDL-SAT) tetap terbuka selama beberapa tahun, tetapi juga dapat terlihat lengkap-EKSPTIM. Ini dicapai dengan menggabungkan teknik Emerson dan Jutla [1988] dan Vardi [1985], seperti dalam Vardi [1998]. Kompleksitas (CRPDL-SAT) tetap terbuka selama beberapa tahun, tetapi juga dapat terlihat lengkap-EKSPTIM. Ini dicapai dengan menggabungkan teknik Emerson dan Jutla [1988] dan Vardi [1985], seperti dalam Vardi [1998]. Kompleksitas (CRPDL-SAT) tetap terbuka selama beberapa tahun, tetapi juga dapat terlihat lengkap-EKSPTIM. Ini dicapai dengan menggabungkan teknik Emerson dan Jutla [1988] dan Vardi [1985], seperti dalam Vardi [1998].

Dalam bagian 3.3 kami telah mendefinisikan predikat ∞, di mana ∞ (α) berarti bahwa α dapat memiliki perhitungan yang tidak berakhir. Kami menyebut LPDL logika yang diperoleh dengan menambah PDL dengan predikat ∞. Jelas, RPDL setidaknya sama ekspresifnya dengan LPDL; Definisi induktif ∞ (α) dalam bahasa RPDL adalah saksi dari itu. RPDL sebenarnya lebih ekspresif daripada LPDL. Ini ditunjukkan dalam Harel dan Sherman [1982]. Seperti dapat diduga, RPDL dan LPDL memiliki kekuatan lebih ekspresif daripada PDL. Hal ini ditetapkan dengan membuktikan bahwa beberapa formula RPDL dan LPDL tidak memiliki ekspresi yang setara dalam PDL. Buktinya melibatkan teknik penyaringan yang dirancang untuk meruntuhkan LTS ke model hingga sambil meninggalkan kebenaran atau kepalsuan formula tertentu. Untuk beberapa set rumus PDL X,itu terdiri dalam pengelompokan ke dalam kelas kesetaraan status LTS yang memenuhi formula yang sama persis di X. Himpunan kelas ekivalensi keadaan yang diperoleh menjadi himpunan keadaan model filtrat, dan transisi dibangun secara tepat di atasnya.

Dengan himpunan FL (A) yang dipilih dengan hati-hati yang bergantung pada formula PDL A (yang disebut penutupan Fischer-Ladner dari himpunan sub-formula A), penyaringan LTS M menghasilkan filtrat terbatas M ', seperti bahwa A memuaskan pada dunia u dalam M jika dan hanya jika itu memuaskan dalam kelas ekivalensi yang mengandung u dalam filtrat. (Lihat Fischer dan Ladner [1979].)

Kita sekarang dapat mempertimbangkan penyaringan LTS M = (W, R, V) di mana

  • W = {(i, j): j dan i bilangan bulat positif, 0 ≤ j ≤ i} ∪ {u}
  • (i, j) R (π) (i, j -1) saat 1 ≤ j ≤ i
  • u R (π) (i, i) untuk setiap i
  • V (p) = ∅ untuk setiap p ∈ Φ 0

Dalam satu kalimat, yang terjadi dalam M adalah bahwa dari dunia u, ada jumlah tak terbatas dari jalur π terbatas dengan panjang tumbuh. Kami memiliki M, u sat ¬Δπ dan M, u sat ¬∞ (π *). Namun, untuk setiap rumus PDL A, kita akan memiliki Δπ dan ∞ (π *) yang dipenuhi pada kelas ekuivalensi u dalam model yang diperoleh dengan penyaringan M dengan FL (A). Memang, penyaringan harus runtuh beberapa negara bagian M dan membuat beberapa loop. Dengan demikian, tidak ada rumus PDL yang dapat mengekspresikan Δπ atau ∞ (π *). namun, kita akan memiliki Δπ dan ∞ (π *) yang dipenuhi pada kelas ekuivalensi u dalam setiap filtrat terbatas M. Dengan demikian, baik ∞ maupun ∞ (π *) tidak dapat diekspresikan dalam PDL.

Ada cara lain untuk memungkinkan pernyataan bahwa suatu program dapat dijalankan selamanya. Sebagai contoh, Danecki [1984a] mengusulkan predikat sekoci untuk memenuhi syarat program yang dapat masuk dalam loop kuat, yaitu:

V (sloop (α)) = {x: x R (α) x}

Mari kita sebut SLPDL logika yang diperoleh dengan menambah PDL dengan sloop (α). RPDL dan SLPDL pada dasarnya tidak ada bandingannya: predikat Δ tidak dapat didefinisikan dalam SLPDL, dan predikat sloop tidak dapat didefinisikan dalam RPDL. SLPDL tidak memiliki properti model hingga. Misalnya rumusnya

[π *] (1 ∧ ¬ sloop+))

hanya memuaskan dalam LTS tak terbatas. Meskipun demikian, Danecki [1984a] menetapkan desidabilitas formula (SLPDL-SAT) dalam waktu eksponensial deterministik.

4.4 PDL dengan persimpangan

Konstruksi lain telah dipelajari: persimpangan program. Dengan menambahkan persimpangan program ke PDL, kami memperoleh logika IPDL. Dalam IPDL, untuk semua program α, β, ekspresi α∩β berarti program baru dengan semantik

x R (α∩β) y iff x R (α) y dan x R (β) y

Misalnya, bacaan yang dimaksudkan dari A adalah bahwa jika kita mengeksekusi α dan β dalam keadaan sekarang maka ada keadaan yang dapat dicapai oleh kedua program yang memenuhi A. Hasilnya, kita punya

⊨ A → A ∧ A

tetapi, secara umum, kita miliki

tidak ⊨ A ∧ A → A

Meskipun persimpangan program memainkan peran penting dalam berbagai aplikasi PDL untuk kecerdasan buatan dan ilmu komputer, teori pembuktian dan teori kompleksitas PDL dengan persimpangan tetap belum dijelajahi selama beberapa tahun. Mengenai teori kompleksitas IPDL, kesulitan muncul ketika seseorang mempertimbangkan properti model hingga. Bahkan construct sloop (α) dapat diekspresikan dalam IPDL. Dalam logika dinamis proposisional dengan persimpangan, itu sama dengan 1. Kita dengan demikian dapat mengadaptasi formula IPDL dari bagian 4.3, dan kami memiliki itu

[π *] (1 ∧ [π + ∩1?] 0)

hanya memuaskan dalam LTS tak terbatas. Dengan kata lain, IPDL tidak memiliki properti model hingga. Danecki [1984b] meneliti teori kompleksitas IPDL dan menunjukkan bahwa penentuan (IPDL-SAT) dapat dilakukan dalam waktu eksponensial ganda deterministik. (Bukti modern disajikan dalam Göller, Lohrey dan Lutz [2007].) Kesenjangan kompleksitas antara batas atas waktu eksponensial ganda untuk penentuan (IPDL-SAT) dan batas bawah waktu eksponensial sederhana untuk penentuan (PDL-SAT) diperoleh oleh Fischer dan Ladner [1979] tetap terbuka selama lebih dari dua puluh tahun. Pada tahun 2004, Lange [2005] menetapkan batas bawah ruang eksponensial (IPDL-SAT). Pada tahun 2006,Lange dan Lutz [2005] memberikan bukti dari batas bawah waktu eksponensial ganda dari masalah kepuasan untuk IPDL tanpa tes dengan pengurangan dari masalah kata mesin Turing bergantian secara eksponensial ruang-baling. Dalam pengurangan ini, peran konstruk iterasi sangat penting karena, menurut Massacci [2001], masalah kepuasan untuk IPDL bebas-iterasi tanpa tes hanya PSPACE-complete. Menambahkan konstruksi sebaliknya ke IPDL, kami memperoleh ICPDL. Masalah kepuasan ICPDL telah terbukti 2-EXPTIME-lengkap oleh Goller, Lohrey dan Lutz [2007]. Masalah kepuasan ICPDL telah terbukti 2-EXPTIME-lengkap oleh Goller, Lohrey dan Lutz [2007]. Masalah kepuasan ICPDL telah terbukti 2-EXPTIME-lengkap oleh Goller, Lohrey dan Lutz [2007].

Mengenai teori bukti IPDL, kesulitan muncul ketika kita menyadari bahwa tidak ada skema aksioma, dalam bahasa PDL dengan persimpangan, "berkorespondensi" dengan semantik x R (α∩β) y iff x R (α) y dan x R (β) y dari program α∩β. Yaitu, tidak dengan cara yang sama misalnya, bahwa skema aksioma (A1) dan (A2) masing-masing “berhubungan” dengan semantik program α; β dan α∪β. Untuk alasan ini, aksiomatisasi PDL dengan persimpangan terbuka sampai sistem bukti lengkap dikembangkan di Balbiani dan Vakarelov [2003].

Dalam varian lain dari PDL, karena Peleg [1987] dan dipelajari lebih lanjut oleh Goldblatt [1992b], ekspresi α∩β diinterpretasikan “do α dan β secara paralel”. Dalam konteks ini, hubungan biner R (α) dan R (β) tidak lagi set pasangan bentuk (x, y) dengan x, y dunia, melainkan kumpulan pasangan bentuk (x, Y) dengan xa dunia dan Y seperangkat dunia. Itu terinspirasi oleh Game Logic of Parikh [1985], sebuah intepretasi PDL dengan "program sebagai permainan". Game Logic menyediakan konstruk program tambahan yang menggandakan program, sehingga memungkinkan untuk mendefinisikan persimpangan program sebagai ganda dari pilihan non-deterministik antar program.

5. Kesimpulan

Artikel ini berfokus pada logika dinamis proposisional dan beberapa variannya yang signifikan. Sekarang ada sejumlah buku-Goldblatt [1982], Goldblatt [1992a], Harel [1979] dan Harel, Kozen dan Tiuryn [2000] -dan makalah survei-Harel [1984], Kozen dan Tiuryn [1990], Parikh [1983] -mengobati PDL dan formalisme terkait. Badan penelitian tentang PDL tentu berperan dalam mengembangkan banyak teori logis dari dinamika sistem. Namun, teori-teori ini bisa dibilang keluar dari ruang lingkup artikel ini. Van Eijck dan Stokhof [2006] adalah tinjauan yang lebih baru tentang topik-topik yang menggunakan logika dinamis, membahas berbagai tema yang menarik bagi para filsuf: misalnya, dinamika komunikasi, atau semantik bahasa alami. Buku-buku terbaru banyak membahas tentang topik-topik baru,seperti logika pengetahuan dinamis (dynamic epistemic logic) dalam Van Ditmarsch, Van Der Hoek dan Kooi [2007], dan logika dinamis sistem kontinu dan hybrid (logika dinamis diferensial) dalam Platzer [2010]. PDL disusun terutama karena alasan tentang program. Ada banyak aplikasi lain dari logika modal untuk alasan tentang program. Logika algoritma lebih dekat ke PDL karena memungkinkan seseorang untuk berbicara secara eksplisit tentang program. Pembaca diundang untuk berkonsultasi dengan karya yang dipelajari di Mirkowska dan Salwicki [1987]. Logika temporal sekarang menjadi logika utama dalam ilmu komputer teoretis dan memiliki hubungan dekat dengan logika program. Mereka memungkinkan seseorang untuk mengekspresikan perilaku temporal dari sistem transisi dengan bahasa yang abstrak dari label (karenanya program). Lihat misalnya Schneider [2004] untuk tinjauan umum tentang fondasi di bidang penelitian ini.

Bibliografi

  • Apt, K., 1981, "Sepuluh tahun logika Hoare: Sebuah survei - Bagian I", Transaksi ACM pada Bahasa dan Sistem Pemrograman, 3 (4): 431-483.
  • Balbiani, P., dan D. Vakarelov, 2003, "PDL dengan persimpangan program: axiomatization lengkap", Jurnal Logika Non-Klasik Terapan, 13: 231-276.
  • van Benthem, J., 1998, “Konstruksi program yang aman untuk bisimulasi”, Studia Logica, 60: 311–330.
  • Berman, F., dan M. Paterson, 1981, "Logika dinamis proposisional lebih lemah tanpa tes", Theoretical Computer Science, 16: 321-328.
  • Burstall, R., 1974, "Program Membuktikan sebagai Simulasi Tangan dengan Induksi Kecil", Pemrosesan Informasi 74: Prosiding Kongres IFIP 74, Amsterdam: North Holland Publishing Company, 308–312.
  • Danecki, R., 1984a, "Logika dinamis proposisional dengan predikat loop kuat", dalam M. Chytil dan V. Koubek, Yayasan Matematika Ilmu Komputer, Berlin: Springer-Verlag, 573-581.
  • –––, 1984b, “Logika dinamis proposisional nondeterministik dengan persimpangan dapat dipilih”, dalam A. Skowron (ed.), Teori Komputasi, Berlin: Springer-Verlag, 34-53.
  • De Giacomo, G., dan F. Massacci, 2000, “Menggabungkan deduksi dan pengecekan model ke dalam tableaux dan algoritma untuk converse-PDL”, Information and Computation, 160: 109–169.
  • van Ditmarsch, H., W. van Der Hoek, dan B. Kooi, 2007, Logika epistemik dinamis, Dordrecht: Springer-Verlag.
  • van Eijck, J., dan M. Stokhof, 2006, "The Gamut of Dynamic Logics", di D. Gabbay dan J. Woods (eds.), Buku Pegangan Sejarah Logika, Volume 7- Logika dan Modalitas dalam Twentieth Century, Amsterdam: Elsevier, 499-600.
  • Emerson, E., dan Jutla, C., 1988, "Kompleksitas Pohon Automata dan Logika Program (Extended Abstract)", dalam Prosiding Simposium Tahunan ke-29 tentang Yayasan Ilmu Komputer, Los Alamitos, CA: IEEE Computer Society, 328–337.
  • –––, 1999, “Kompleksitas Pohon Automata dan Logika Program”, dalam SIAM Journal of Computing, 29: 132–158.
  • Engeler, E., 1967, "sifat-sifat struktur algoritma", Teori Sistem Matematika, 1: 183–195.
  • Fischer, M., dan R. Ladner, 1979, "Logika dinamis proposisional dari program reguler", Jurnal Ilmu Komputer dan Sistem, 18: 194–211.
  • Floyd, R., 1967, "Menugaskan makna untuk program", Prosiding Simposium Masyarakat Matematika Amerika pada Matematika Terapan (Volume 19), Providence, RI: Masyarakat Matematika Amerika, 19-31.
  • Gargov, G., dan S. Passy, 1988, "Determinisme dan perulangan dalam kombinasi PDL", Ilmu Komputer Teoretis, Amsterdam: Elsevier, 259-277.
  • Goldblatt, R., 1982, Axiomatising the Logic of Computer Programming, Berlin: Springer-Verlag.
  • –––, 1992a, Logika Waktu dan Perhitungan, Stanford: Pusat Studi Bahasa dan Publikasi Informasi.
  • –––, 1992b, “Aksi Paralel: Logika Dinamis Bersama dengan Modalitas Independen”, Studia Logica, 51: 551–578.
  • Göller, S., M. Lohrey, dan C. Lutz, 2007, "PDL dengan persimpangan dan berbicara adalah 2EXP-lengkap", Yayasan Sains Perangkat Lunak dan Struktur Komputasi, Berlin: Springer, 198-212.
  • Harel, D., 1979, First-Order Dynamic Logic, Berlin: Springer-Verlag.
  • –––, 1983, “Domino berulang: membuat yang sangat tidak dapat diputuskan menjadi sangat dapat dimengerti”, dalam M. Karpinski (ed.), Yayasan Teori Komputasi, Berlin: Springer-Verlag, 177–194.
  • –––, 1984, “Logika dinamis”, dalam D. Gabbay dan F. Guenthner (eds.), Handbook of Philosophical Logic (Volume II), Dordrecht: D. Reidel, 497–604.
  • Harel, D., D. Kozen, dan J. Tiuryn, 2000, Dynamic Logic, Cambridge, MA: MIT Press.
  • Harel, D. dan Sherman, R., 1982, “Looping vs. Repeating in Dynamic Logic”, Information and Control, 55: 175–192.
  • Hoare, C., 1969, “Dasar aksiomatik untuk pemrograman komputer”, Communications of Association of Computing Machinery, 12: 576–580.
  • Kozen, D., 1983, "Hasil pada Proposisional μ-Calculus", Ilmu Komputer Teoretis, 27: 333-354.
  • Kozen, D., dan R. Parikh, 1981, "Sebuah bukti dasar dari kelengkapan PDL", Theoretical Computer Science, 14: 113–118.
  • Kozen, D., dan J. Tiuryn, 1990, "Logika program", dalam J. Van Leeuwen (ed.), Buku Pegangan Ilmu Komputer Teoritis (Volume B), Amsterdam: Elsevier, 789–840.
  • Lange, M., 2005, "Sebuah kompleksitas yang lebih rendah terikat untuk logika dinamis proposisional dengan persimpangan", dalam R. Schmidt, I. Pratt-Hartmann, M. Reynolds dan H. Wansing (eds.), Kemajuan dalam Modal Logic (Volume 5), London: King's College Publications, 133–147.
  • Lange, M., dan C. Lutz, 2005, "batas bawah 2-EXPTIME untuk logika dinamis proposisional dengan persimpangan", Journal of Symbolic Logic, 70: 1072-1086.
  • Lutz, C., 2005, "PDL dengan persimpangan dan berbicara adalah decidable". Dalam L. Ong (ed.), Ilmu Komputer Logika, Berlin: Springer-Verlag, 413-427.
  • Massacci, F., 2001, "Prosedur pengambilan keputusan untuk logika deskripsi ekspresif dengan persimpangan, komposisi, konversi peran dan identitas peran", dalam B. Nebel (ed.), Konferensi Gabungan Internasional ke-17 tentang Kecerdasan Buatan, San Francisco: Morgan Kaufmann, 193–198.
  • Mirkowska, G., dan A. Salwicki, 1987, Algorithmic Logic, Dordrecht: D. Reidel.
  • Nishimura, H., 1979, "Metode berurutan dalam logika dinamis proposisional", Acta Informatica, 12: 377-400.
  • Parikh, R., 1978, "Kelengkapan logika dinamis proposisional", dalam J. Winkowski (ed.), Yayasan Matematika Ilmu Komputer, Berlin: Springer-Verlag, 1978, 403-415.
  • –––, 1983, “Logika proposisional program: arah baru”, dalam M. Karpinski (ed.), Yayasan Teori Komputasi, Berlin: Springer-Verlag, 347-359.
  • –––, 1985, “Logika permainan dan aplikasinya”, Annals of Discrete Mathematics, 24: 111–140.
  • Peleg, D., 1987, "Concurrent dynamic logic", Journal of Association of Computing Machinery, 34: 450-479.
  • Platzer, A., 2010, Analisis Logika Sistem Hibrida: Teorema Pembuktian untuk Kompleks Dinamika, Berlin: Springer, 2010.
  • Pratt, V., 1976, "Pertimbangan semantik pada logika Floyd-Hoare", dalam Prosiding Simposium IEEE ke-17 tentang Yayasan Ilmu Komputer, Los Alamitos, CA: IEEE Computer Society, 109-121.
  • –––, 1978, “Suatu metode keputusan praktis untuk logika dinamis proposisional”, dalam Prosiding Simposium ACM Tahunan ke 10 tentang Teori Komputasi, New York, NY: ACM, 326–337.
  • –––, 1980a, “Metode yang hampir optimal untuk penalaran tentang tindakan”, Jurnal Ilmu Komputer dan Sistem, 20: 231–254.
  • –––, 1980b, “Penerapan Modal Logika untuk Pemrograman”, Studia Logica, 39: 257–274.
  • Sakalauskaite, J., dan M. Valiev, 1990, "Kelengkapan logika dinamis proposisional dengan pengulangan tak terbatas", dalam P. Petkov (ed.), Logika Matematika, New York: Plenum Press, 339–349.
  • Salwicki, A., 1970, "Bahasa algoritmik yang diformalkan", Bulletin de l'Academie, Polonaise des Sciences, Seri ilmu matematika, astronomiques et physiques, 18: 227–232.
  • Segerberg, K., 1977, "Sebuah teorema kelengkapan dalam modal logika program", Pemberitahuan Masyarakat Matematika Amerika, 24: 522.
  • Schneider, K., 2004, Verifikasi Sistem Reaktif, Berlin: Springer-Verlag.
  • Streett, R., 1982, "Logika dinamis proposisional dari looping dan converse adalah elemen dasar", Information and Control, 54: 121-141
  • Vakarelov, D., 1983, "Teorema filtrasi untuk aljabar dinamis dengan tes dan operator terbalik", dalam A. Salwicki (ed.), Logika Program dan Aplikasi mereka, Berlin: Springer-Verlag, 314–324.
  • Vardi, M., 1985, "The Taming of Converse: Reasoning about Two-way Computations", dalam Catatan Kuliah dalam Ilmu Komputer (Volume 193), Berlin-Heidelberg: Springer, 413-423.
  • –––, 1998, “Penalaran tentang masa lalu dengan automata dua arah”, dalam Lecture Notes in Computer Science (Volume 1443), Berlin-Heidelberg: Springer, 628-641.
  • Vardi, M., dan Stockmeyer, L., 1985, "Peningkatan Batas Atas dan Bawah untuk Modal Logika Program: Laporan Awal", dalam Prosiding Simposium ACM Tahunan ke-17 tentang Teori Komputasi, New York, NY: ACM, 240 –251.
  • Yanov, J., 1959, "Pada kesetaraan skema operator", Masalah Cybernetic, 1: 1–100.

Alat Akademik

ikon sep man
ikon sep man
Cara mengutip entri ini.
ikon sep man
ikon sep man
Pratinjau versi PDF dari entri ini di Friends of the SEP Society.
ikon inpho
ikon inpho
Cari topik entri ini di Internet Ontology Philosophy Project (InPhO).
ikon makalah phil
ikon makalah phil
Bibliografi yang disempurnakan untuk entri ini di PhilPapers, dengan tautan ke basis datanya.

Sumber Daya Internet lainnya

[Silakan hubungi penulis dengan saran.]

Direkomendasikan: