Proposisjonell Dynamisk Logikk

Innholdsfortegnelse:

Proposisjonell Dynamisk Logikk
Proposisjonell Dynamisk Logikk

Video: Proposisjonell Dynamisk Logikk

Video: Proposisjonell Dynamisk Logikk
Video: Avslutningsfest del 2/3: Syv spennende miniforedrag 2024, Mars
Anonim

Inngangsnavigasjon

  • Inngangsinnhold
  • Bibliografi
  • Akademiske verktøy
  • Venner PDF forhåndsvisning
  • Forfatter og sitatinfo
  • Tilbake til toppen

Proposisjonell dynamisk logikk

Først publisert torsdag 1. februar 2007; substansiell revisjon fre 25. januar 2019

Logikk av programmer er modal logikk som stammer fra ideen om å knytte til hvert dataprogram α på et programmeringsspråk en modalitet [α]. Denne ideen stammer fra rekken av verk av Engeler [1967], Hoare [1969], Yanov [1959], og andre som formulerte og studerte logiske språk der egenskapene til programtilkoblinger kan uttrykkes. Den algoritmiske logikken (AL) først utviklet av Salwicki [1970] og den dynamiske logikken (DL) utarbeidet av Pratt [1976] er riktige fortsettelser av disse verkene. Vi vil her konsentrere oss om DL. De mange papirene som er viet til DL og dens varianter, så vel som dets mangfoldige bruksområder i programverifisering og datastrukturer, viser at det utgjør et nyttig verktøy for å studere egenskapene til programmer. Pratt valgte å skildre DL på det man kan kalle førsteordens nivå,og det var hans arbeid som utløste Fischer og Ladner [1979] til å definere proposisjonsvarianten til DL et par år senere. Denne artikkelen presenterer en introduksjon til PDL, proposisjonsvarianten til DL.

  • 1. Introduksjon
  • 2. Definisjoner og grunnleggende resultater

    • 2.1 Syntaks og semantikk
    • 2.2 Aksiomatisering og fullstendighet
    • 2.3 Avgjørbarhet og kompleksitet
  • 3. Strukturert programmering og riktighet av programmer

    • 3.1 Hoarekalkulus
    • 3.2 Hoarekalkulus og PDL
    • 3.3 Total korrekthet
  • 4. Noen varianter

    • 4.1 PDL uten tester
    • 4.2 PDL med samtale
    • 4.3 PDL med repetisjon og looping
    • 4.4 PDL med kryss
  • 5. Konklusjon
  • Bibliografi
  • Akademiske verktøy
  • Andre internettressurser
  • Relaterte oppføringer

1. Introduksjon

Dynamic Logics (DL) er modale logikker for å representere tilstandene og hendelsene til dynamiske systemer. Språket til DLs er både et påstandsspråk som kan uttrykke egenskaper ved beregningstilstander, og et programmeringsspråk som er i stand til å uttrykke egenskaper ved systemoverganger mellom disse tilstandene. DL-er er logikker over programmer, og tillater å snakke og resonnere om forhold, prosesser, endringer og resultater.

Prats opprinnelige dynamiske logikk over programmer var en førsteordens modal logikk. Propositionional Dynamic Logic (PDL) er den proposisjonelle motstykket til den. Det ble presentert som en logikk i seg selv i Fischer og Ladner [1979]. Å være proposisjonell, språket til PDL gjør ingen bruk av begreper, predikater eller funksjoner. I PDL er det således to syntaktiske kategorier: proposisjoner og programmer.

For å gi mening til uttalelser i PDL, jobber vi vanligvis med en abstrakt semantikk når det gjelder Labeled Transition Systems (LTS). LTS kan sees på som en generalisering av Kripke-modeller, der overganger mellom verdener eller tilstander er "merket" med navn på atomprogrammer. En verdivurdering indikerer for hver stat hvilke proposisjoner som er sanne i den. En overgang merket π fra en tilstand x til en tilstand y -notert x R (π) y, eller (x, y) ∈ R (π) -indikerer at fra og med x, er det en mulig utførelse av programmet π som er ferdig i y. Hvis proposisjonen A er sann i y, er formelen A sann i x: dvs. i tilstanden x er det en mulig utførelse av programmet α som ender i en tilstand som tilfredsstiller A. Man kjenner seg igjen i en modalitet som minner om muligheten for (ofte bemerket ◊) av modal logikk. Ikke overraskende,det er også en tilsvarende forestilling om nødvendighet (hvis modalitet ofte bemerkes □). Formelen [π] A vil være sant i tilstanden x hvis A er sann i hver tilstand som kan nås fra x ved en overgang merket π.

De mulige henrettelsene av komplekse programmer kan defineres i neste omgang. For eksempel er et program “først α, deretter β” et komplekst program, nærmere bestemt en sekvens. En mulig utførelse kan bli representert i en LTS ved å komponere en totrinns overgang - derav en overgang som kan betegnes med R (α; β) mellom tilstandene x og x ': det er en mulig utførelse i x av programmet α som avsluttes i en tilstand y og det er en mulig utførelse i y av programmet β som avsluttes i x '. Hvis proposisjonen A er sann i x ', vil formelen A være sann i tilstanden x. Programmene a og β kan være komplekse programmer i seg selv. Enda flere programmer kan uttrykkes med flere konstruksjoner som vi vil presentere i løpet av tiden.

Et program blir så sett på en ekstensjonell måte: det er et binært forhold mellom par av tilstander i en LTS. Nettopp er det settet med par av formen (x, y) slik at programmet kan utføres i tilstanden x og kan føre til tilstanden y. På den annen side er en proposisjon en uttalelse om en stat; det er enten sant eller usant i en tilstand. En proposisjon kan dermed også sees på en ekstensjonell måte: settet av tilstander i LTS der det er sant.

Med forkortelsen PDL refererer vi her nøyaktig til den proposisjonelle dynamiske logikken med følgende programkonstruksjoner: sekvens, ikke-deterministisk valg, ubegrenset iterasjon og test. Vi presenterer det i seksjon 2, sammen med noen egenskaper og grunnleggende resultater. Spesielt vil vi ta for oss dens aksiomatisering og dens avgjørbarhet.

Hoare-beregningen fra Hoare [1969] er et landemerke for logikk av programmer. Det gjelder sannheten om uttalelser om formen {A} α {B}, noe som betyr at programmet med forutsetningen A alltid har B som en posttilstand og er definert aksiomatisk. Det kommer fra et behov for strenge metoder for å resonnere om programmens egenskaper, og dermed gi aktiviteten til å programmere et bestemt sted i vitenskapens rike. Burstall [1974] så analogien mellom modal logikk og resonnement om programmer, men selve arbeidet med det startet med Pratt [1976] da det ble foreslått for ham av R. Moore, en student av hans den gang. PDL kommer fra Pratt sin tolkning av Hoares beregning i formaliteten av modal logikk. En introduksjon til genesis av PDL finner du i Pratt [1980b]. Hoare-trippelen {A} α {B} fanges opp av PDL-formelen A → [α] B som bokstavelig talt betyr at hvis A er sant, vil enhver vellykket avsluttende utførelse av a ende med at B er sant. Når denne forbindelsen ble realisert, er det en rutine å bevise de innledende reglene for Hoares kalkulus ved bruk av utelukkende aksiomatisering av PDL. Dette er noe vi vil gjøre i detalj i avsnitt 3 som konsentrerer seg om resonnementet om riktigheten av strukturerte programmer.

Ytterligere emner relatert til PDL inkluderer resultater om sammenlignende uttrykkskraft, avgjørbarhet, kompleksitet og fullstendighet av en rekke interessante varianter oppnådd ved å utvide eller begrense PDL på forskjellige måter. Siden oppstarten har mange varianter av PDL fått oppmerksomhet. Disse variantene kan vurdere deterministiske programmer, begrensede tester, ikke-vanlige programmer, programmer som automatikk, komplementering og kryssing av programmer, samtale og uendelig beregning, etc. Vi vil presentere noen av dem i seksjon 4, og gi noen tips om deres relative uttrykk deres aksiomatiseringer, og deres beregningsmessige kompleksitet.

Vi konkluderer med avsnitt 5.

2. Definisjoner og grunnleggende resultater

Vi presenterer syntaks og semantikk for PDL i avsnitt 2.1. Bevissteorien om PDL er presentert i avsnitt 2.2 med aksiomatiseringer og pekere på litteraturen om fullstendighet. Vi tar opp problemet med avgjørbarhet og kompleksitet i avsnitt 2.3.

2.1 Syntaks og semantikk

Proposjonell dynamisk logikk (PDL) er designet for å representere og resonnere om proposisjonelle egenskaper til programmer. Syntaks er basert på to sett med symboler: et tellbart sett Φ 0 med atomformler og et tellbart sett Π 0 av atomprogrammer. Komplekse formler og komplekse programmer over denne basen er definert som følger:

  • Hver atomformel er en formel
  • 0 (“falsk”) er en formel
  • Hvis A er en formel, er ¬ A ("ikke A") en formel
  • Hvis A og B er formler, er (A ∨ B) (“A eller B”) en formel
  • Hvis α er et program og A er en formel, er [α] A ("hver utførelse av α fra den nåværende tilstanden fører til en tilstand der A er sann") er en formel
  • Hvert atomprogram er et program
  • Hvis α og β er programmer, er (α; β) (“do α etterfulgt av β”) et program
  • Hvis α og β er programmer, er (α∪β) (“gjør α eller β, ikke-deterministisk”) et program,
  • Hvis α er et program, er α * ("gjenta α en begrenset, men ikke-deterministisk bestemt antall ganger") et program.
  • Hvis A er en formel, så er A? ("Fortsett hvis A er sant, ellers mislykkes") er et program

De andre boolske tilkoblingene 1, ∧, → og ↔ brukes som forkortelser på standard måte. I tillegg forkortes vi ¬ [α] ¬ A til A ("noe utførelse av α fra nåværende tilstand fører til en tilstand der A er sant") som i modal logikk. Vi skriver α n for α;…; α med n forekomster av α. Mer formelt:

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

Også:

α + = df α; α *

er ofte nyttig for å representere en iterasjon som er ubegrenset, men som oppstår minst en gang. Til slutt vedtar vi standardreglene for utelatelse av parenteser.

Formler kan brukes til å beskrive egenskapene som holder til etter vellykket gjennomføring av et program. For eksempel betyr formelen [α∪β] A at når program α eller β blir vellykket utført, oppnås en tilstand der A holder, mens formelen A betyr at det er en sekvens av vekslende henrettelser av a og β slik at en tilstand oppnås der A holder. Semantisk sett tolkes formler av sett med tilstander og programmer tolkes av binære relasjoner over stater i et overgangssystem. Mer presist blir betydningen av PDL-formler og programmer tolket over Labeled Transition Systems (LTS) M = (W, R, V) der W er et ikke-unntatt sett med verdener eller stater, R er en kartlegging fra settet Π 0 for atomisk programmer til binære relasjoner på W og V er en kartlegging fra settet Φ 0 av atomformler til undergrupper av W.

Uformelt tilordner kartleggingen R til hvert atomprogram π ∈ Π 0 noe binært forhold R (π) på W med tiltenkt betydning x R (π) y hvis det finnes en utførelse av π fra x som fører til y, mens kartleggingen V tildeler hver atomformel p ∈ Φ 0 noen delmengde V (p) av W med tiltenkt betydning x ∈ V (p) hvisf p er sant i x. Gitt vår avlesning av 0, ¬ A, A ∨ B, [α] A, α; β, α∪β, α * og A?, Er det klart at R og V må utvides induktivt som følger for å gi de tilsiktede betydningene for de komplekse programmene og formlene:

  • x R (a; β) y hvis det finnes en verden z slik at x R (a) z og zR (ß) y
  • x R (α∪β) y iff x R (α) y eller x R (β) y
  • x R (α *) y hvis det finnes et ikke-negativt heltall n og det finnes verdener z 0, …, z n slik at z 0  = x, z n  = y og for alle k = 1.. n, z k −1 R (α) z k
  • x R (A?) y iff x = y og y ∈ V (A)
  • V (0) = ∅
  • V (¬ A) = W / V (A)
  • V (A ∨ B) = V (A) ∪ V (B),
  • V ([α] A) = {x: for alle verdener y, hvis x R (α) y så er y ∈ V (A)}

Hvis x ∈ V (A), sier vi at A er fornøyd ved tilstanden x i M, eller “M, x sat A”.

To bisimilar LTS-er
To bisimilar LTS-er

Kall M LTS avbildet ovenfor til venstre og M 'LTS avbildet til høyre. Formelt definert har vi M = (W, R, V) med 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 }, og vi har M '= (W', R ', V') med 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 }. Vi har for eksempel:

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

Vurder nå en formel A. Vi sier at A er gyldig i M eller at M er en modell av A, eller “M ⊨ A”, iff for alle verdener x, x ∈ V (A). A sies å være gyldig, eller “⊨ A”, iff for alle modellene M, M ⊨ A. Vi sier at A er tilfredsstillende i M eller at M tilfredsstiller A, eller “M satt A”, hvis det finnes en verden x slik at x ∈ V (A). A sies å være tilfredsstillende, eller "satt A", hvis det finnes en modell M slik at M satt A. Interessant,

satt A iff not ⊨ ¬ A

⊨ A iff not sat ¬ A

Noen bemerkelsesverdige formler av PDL er gyldige. (Leseren kan prøve å bevise dem formelt, eller i det minste begynne å overbevise seg om de få eksemplene som er vist over.)

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

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

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

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

På samme måte kan vi skrive dem under deres doble form.

⊨ A ↔ A

⊨ A ↔ A ∨ A

⊨ A ↔ A ∨ A

⊨ <A?> B ↔ A ∧ B

En interessant forestilling gjelder mengden informasjon, uttrykt med PDL-formler, som er inneholdt i en LTS. Oppførselen til et system beskrevet som en LTS er faktisk ofte litt skjult i sin form. For eksempel, ved enkel inspeksjon, er det lett å overbevise seg om at de to LTS-ene som er avbildet ovenfor har samme oppførsel, og tilfredsstiller de samme PDL-formlene. For å fullføre dette avsnittet om syntaks og semantikk gir vi det teoretiske grunnlaget for disse påstandene.

Gitt to LTS-er, kan man spørre seg om de tilfredsstiller de samme formlene. Forestillingen om bisimulering er blitt et standardmål for ekvivalens av Kripke-modeller og merkede overgangssystemer. En bisimulering mellom LTSs M = (W, R, V) og M '= (W', R ', V') er en binær relasjon Z mellom tilstandene deres slik at for alle verdener x i M og for alle verdener x ' i M ', hvis xZx' da

  • for alle atomformler p ∈ Φ 0, x ∈ V (p) iff x '∈ V' (p)
  • for alle atomprogrammer π ∈ Π 0 og for alle verdener y i M, hvis x R (π) y så eksisterer det en verden y 'i M' slik at yZy 'og x' R '(π) y'
  • for alle atomprogrammer π ∈ Π 0 og for alle verdener y 'i M', hvis x 'R' (π) y ', eksisterer det en verden y i M slik at yZy' og x R (π) y

Vi sier at to LTS er bisimilar når det eksisterer en bisimulering mellom dem. Det er kjent siden begynnelsen av PDL at i to bisimilar LTSs M og M ', for alle verdener x i M og for alle verdener x' i M ', hvis xZx', så for alle PDL formler A, x ∈ V (A) iff x '∈ V' (A). Når to LTS er bisimilar under definisjonen av bisimulering ovenfor, er det slik at hvis xZx 'da

  • for alle programmer α og for alle verdener y i M, hvis x R (α) y så eksisterer det en verden y 'i M' slik at yZy 'og x' R '(α) y'
  • for alle programmer α og for alle verdener y 'i M', hvis x 'R' (α) y 'så finnes det en verden y i M slik at yZy' og x R (α) y

Derfor kan man ganske enkelt sammenligne atferden til to LTS-er ved bare å inspisere atomprogrammene og trygt ekstrapolere på den komparative atferden til disse LTS-ene, selv for komplekse programmer. Vi sier at programkonstruksjonene av PDL er trygge for bisimulering. Se Van Benthem [1998] for presise karakteriseringer av programkonstruksjoner som er trygge for bisimulering.

Man ser lett at de to forekomstene av LTSer ovenfor er bisimilar. En bisimulering Z mellom M og M 'kan gis som: Z = {(x 1, y 1), (x 1, y 2), (x 2, y 3), (x 2, y 4)}. Statene x 1 og y 1 tilfredsstiller nøyaktig de samme PDL-formlene. Så gjør tilstandene x 1 og y 2 osv.

2.2 Aksiomatisering og fullstendighet

Formålet med bevisteorien er å gi karakteriseringen av eiendommen ⊨ A når det gjelder aksiomer og regler for inferens. I dette avsnittet definerer vi et dedusibilitetspredikat ⊢ induktivt ved operasjoner på formler som bare er avhengig av deres syntaktiske struktur på en slik måte at for alle formler A,

⊢ A iff ⊨ A.

Selvfølgelig er PDL en utvidelse av klassisk proposisjonell logikk. Vi forventer først at alle proposisjonelle tautologier holder, og all proposisjonell begrunnelse er tillatt. Spesielt er modus ponens en gyldig regel: fra A og A → B infer B. For et hvilket som helst program a, som begrenser en LTS til forholdet R (α), får vi en Kripke-modell der logikken i modaliteten [α] er den svakeste proposisjonelle normale modale logikken, nemlig logikken K. Dermed inneholder PDL alle forekomster av det kjente distribusjonsaksiomskjemaet:

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

og den er stengt under følgende innledningsregel (nødvendighetsregel):

(N) fra A utlede [α] A.

En modal logikk er normal hvis den adlyder (A0) og (N). Viktige egenskaper for alle α, er at [α] fordeler seg over forbindelsen ∧, og reglen om monotoni, som tillater fra A → B å utlede [α] A → [α] B, kan påvises. Endelig er PDL den minst normale modale logikken som inneholder alle forekomster av følgende aksiomskjemaer

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

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

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

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

og lukket under følgende inferensregel (loop invariance rule):

(I) fra A → [α] A utlede A → [α *] A

Hvis X er et sett av formler, og A er en formel da vi si at A er ⊢-utledes fra X, eller “X ⊢ A”, dersom det foreligger en sekvens A 0, A 1, …, A n av formler slik at A n  = A og for alle i ≤ n, A i er et eksempel på et aksiomskjema, eller en formel av X, eller kommer fra tidligere formler av sekvensen ved en inferensregel. Videre, ⊢ A iff ∅ ⊢ A; i dette tilfellet sier vi at A er ⊢-deducerbar. X sies å være ⊢-konsistent hvis ikke X ⊢ 0. Det er lett å fastslå at (I) kan erstattes av følgende aksiomskjema (induksjonsaksiomskjema):

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

La oss først slå fast at (I) er en avledet regel i bevissystemet basert på (A1), (A2), (A3), (A4) og (A5):

1. A → [α] A premiss
2. [α *] (A → [α] A) fra 1 bruker (N)
3. [α *] (A → [α] A) → (A → [α *] A) aksiomskjema (A5)
4. A → [α *] A fra 2 og 3 ved bruk av modus ponens

La oss deretter slå fast at (A5) er ⊢-deduktiv:

1. [α *] (A → [α] A) ↔ (A → [α] A) ∧ [α] [α *] (A → [α] A) aksiomskjema (A3)
2. A ∧ [α *] (A → [α] A) → [α] (A ∧ [α *] (A → [α] A)) fra 1 ved bruk av proposisjonell resonnement og distribusjonsevne for [α] over ∧
3. A ∧ [α *] (A → [α] A) → [α *] (A ∧ [α *] (A → [α] A)) fra 2 bruker (I)
4. [α *] (A → [α] A) → (A → [α *] A) fra 3 ved bruk av proposisjonell resonnement og distribusjon av [α *] over ∧

Aksiomatiseringen av PDL basert på aksiomskjemaer (A1), (A2), (A3), (A4) og (A5) er blitt foreslått i Segerberg [1977]. Det er umiddelbart fra definisjonene over at ⊢ er forsvarlig med hensyn til ⊨, dvs.

For alle formler A, hvis ⊢ A, så ⊨ A

Beviset fortsetter ved induksjon på lengden av A-trekk i ⊢. Spørsmålet om fullstendigheten av ⊢ med hensyn til ⊨, dvs.

For alle formler A, hvis ⊨ A, så ⊢ A

ble forfulgt av flere logikere. Resonnementslinjen som ble presentert i Segerberg [1977] var det første forsøket på å bevise fullstendigheten til ⊢. Snart kom Parikh med et bevis også. Da Segerberg tidlig i 1978 fant en feil i argumentasjonen hans (som han til slutt reparerte), publiserte Parikh det som kan betraktes som det første beviset på fullstendigheten av ⊢ i Parikh [1978]. Forskjellige bevis på fullstendighet av ⊢ har blitt publisert siden, for eksempel Kozen og Parikh [1981].

Ulike alternative bevisteorier om PDL har også blitt etterspurt. Selv tidlig, spesielt i Pratt [1978]. La oss også nevne fullstendigheten av beslektede teorier av Nishimura [1979] og Vakarelov [1983].

En alternativ formulering av en dedusjonspredikat for PDL tillater bruk av en infinitær inferensregel, som for eksempel i Goldblatt [1992a]. (En infinitær inferensregel tar et uendelig antall premisser.) La be 'være dedusjonspredikatet som tilsvarer språket i proposisjonell dynamisk logikk til den minst normale modale logikken som inneholder alle forekomster av aksiomskjemaene (A1), (A2), (A3) og (A4) og stengt under følgende infinitære inferensregel:

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

Det kan bevises at ⊢ 'er både forsvarlig og fullstendig med respekt ⊨, dvs.

For alle formler A, ⊢ 'A iff ⊨ A

Med andre ord, for generering av settet med alle gyldige formler, er bevissystemene ⊢ og ⊢ 'likeverdige.

2.3 Avgjørbarhet og kompleksitet

Målet med kompleksitetsteorien er å etablere beregbarhet av eiendommen satt A når det gjelder ressurser til tid eller rom. Kompleksiteten til en logikk L identifiseres ofte med problemet med å bestemme tilfredsstillelsen av dens formler, definert som:

(L-SAT) Gitt en formel A av L, er A tilfredsstillende?

I denne delen undersøker vi kompleksiteten til følgende beslutningsproblem:

(PDL-SAT) Er A gitt en formel A av PDL, er A tilfredsstillende?

Den komplette aksiomatiseringen av PDL er en rekursiv definisjon av settet med gyldige PDL-formler, eller med andre ord, av settet med formler hvis negering ikke er tilfredsstillende. Når det gjelder problemet (PDL-SAT), har vi derfor en delprosedyre som vil svare “nei” hvis PDL-formelen A ikke var tilfredsstillende. Delprosedyren (SP1) består i å oppregne alle formlene ⊢-deduksible, starte fra aksiomene og utlede andre teoremer ved hjelp av inferensreglene. Gitt nok tid, hvis en formel er ⊢-deduherbar, vil subprosedyren finne den til slutt. Så hvis A ikke er tilfredsstillende, må (SP1) til slutt finne ¬ A, og svare “nei” når det gjør det.

Imidlertid, hvis formelen A er tilfredsstillende, vil (SP1) aldri finne ¬ A. Det ville løpe for alltid, og man kunne ikke være sikker på det når som helst. Men det er en vei ut av denne usikkerheten. Vi kan også tenke på en andre delprosedyre som svarer “ja” hvis en PDL-formel er tilfredsstillende. Et av de tidligste resultatene på PDL var faktisk beviset på at PDL har den endelige modellegenskapen, dvs.

For alle formler A, hvis satt A så eksisterer det en begrenset modell M slik at M satt A.

Den endelige modellegenskapen gir grunnlag for en delprosedyre (SP2) som består i å oppregne en etter en de endelige modellene til PDL og teste om en av dem tilfredsstiller formelen. (For alle formler A og for alle endelige modeller M er det lett å teste om M satt A ved å anvende definisjonen av V (A).) Så hvis A er tilfredsstillende, må den til slutt finne en modell M slik at M satt A, og svar "ja" når det gjør det. Symmetrisk til den første delprosedyren (SP1), hvis formelen A ikke er tilfredsstillende, vil (SP2) aldri finne en modell som tilfredsstiller den, den vil kjøres for alltid, og man kunne ikke være sikker på det når som helst.

Nå, ved å kombinere (SP1) og (SP2) sammen, har vi en måte å avgjøre om en PDL-formel A er tilfredsstillende. Det er nok å kjøre dem parallelt: Hvis A er tilfredsstillende, vil (SP2) til slutt svare "ja", hvis A ikke er tilfredsstillende, vil (SP1) til slutt svare "nei". Prosedyren stopper når enten SP1 eller SP2 gir svar.

Hvis prosedyren som er oppnådd er tilstrekkelig til å konkludere med at problemet (PDL-SAT) er avgjørbart, er det veldig ineffektivt i praksis. Det er et resultat på grunn av Fischer og Ladner [1979] og Kozen og Parikh [1981] - sterkere enn den endelige modellegenskapen, det vil si liten modellegenskap:

For alle formler A, hvis satt A, eksisterer det en begrenset modell M av eksponentiell størrelse i A slik at M satt A.

Dette betyr at vi nå ville vite når vi skal slutte å lete etter en modell som tilfredsstiller en formel i prosedyren (SP2). Derfor kan vi bruke (SP2) til å teste om en formel er tilfredsstillende, men når vi har brukt alle små modeller, kan vi konkludere med at formelen ikke er tilfredsstillende. Dette gir en prosedyre som kjører ikke-deterministisk i eksponentiell tid (NEXPTIME): gjett en modell av størrelse på det mest enkelt eksponentielle, og sjekk om den tilfredsstiller formelen. Men de viktigste resultatene i kompleksitetsteorien til PDL kommer fra Fischer og Ladner [1979] og Pratt [1980a]. Fischer og Ladner [1979] observerte at en formel av PDL effektivt kan beskrive beregningen av en lineær-rom-avgrenset alternerende Turing-maskin, 1979, den nedre grensen for eksponentiell tid for (PDL-SAT). EXPTIME øvre grense for (PDL-SAT) er oppnådd av Pratt [1980a],som brukte ekvivalentet for PDL av tablåsmetoden. Dermed er (PDL-SAT) EXPTIME-fullstendig. (En algoritme som er mer effektiv i praksis, selv om den fremdeles kjører i deterministisk eksponentiell tid i verste fall, foreslås i De Giacomo og Massacci [2000].)

3. Strukturert programmering og riktighet av programmer

Historisk sett stammer logikk av programmer fra arbeidet på slutten av 1960-tallet av dataforskere som er interessert i å tildele mening til programmeringsspråk og finne en streng standard for bevis på programmene. For eksempel kan slike bevis dreie seg om riktigheten av et program med hensyn til en forventet oppførsel, eller om avslutningen av et program. Et seminaloppgave er Floyd [1967] som presenterer en analyse av egenskapene til strukturerte dataprogrammer ved bruk av flytskjemaer. Noen tidlige arbeider som Yanov [1959] eller Engeler [1967] hadde avansert og studert formelle språk der egenskapene til programtilkoblinger kan uttrykkes. Formalismen til Hoare [1969] var en milepæl i ankomsten av PDL. Det ble foreslått som en streng aksiomatisk tolkning av Floyd flytdiagrammer. Vi snakker ofte om Hoare-logikk, eller Floyd-Hoare-logikk,eller Hoare-kalkulus når det refereres til denne formalismen. Hoare-kalkulus er opptatt av sannheten om uttalelser (“Hoare triples”), for eksempel {A} α {B} som etablerer en forbindelse mellom en forutsetning A, et program α og en post-betingelse B. Det indikerer at når A holder som en forutsetning for utførelsen av α, så holder B som en posttilstand etter vellykket utførelse av α.

Det var sant for noen tiår siden, og det er fremdeles tilfelle: validering av et program gjøres oftere enn ikke ved å teste det på en rimelig rekke innganger. Når en inngang ikke gir forventet utgang, er "feilen" rettet. Hvis vi til slutt oppnår forventet effekt for hver testede inngang, har man en rimelig tro på at programmet ikke har noen feil. Imidlertid er dette en tidkrevende metode for validering, og den etterlater plass for uprøvde innganger som vil mislykkes. Det er enda mer kostbart å finne disse feilene etter at programmet er implementert og tatt i bruk. Å resonnere om programmets korrekthet med formelle metoder er avgjørende for kritiske systemer siden det gir en måte å bevise uttømmende at et program ikke har noen feil.

3.1 Hoarekalkulus

For å illustrere hva slags prinsipper for programmer som er fanget opp av reglene i Hoare-beregningen, er det nok å konsultere noen av dem. (NB: reglene betyr at hvis alle utsagnene over regellinjen holder lokalene - så holder også utsagnet under regellinjen - konklusjonen.)

{A} α 1 {B} {B} α 2 {C} (komposisjonsregel)
{A} α 1; α 2 {C}

Komposisjonsregelen fanger opp den elementære sekvensielle komposisjonen til programmer. Som premisser har vi to forutsetninger om den delvise korrektheten til to programmer α 1 og α 2. Den første antakelsen er at når α 1 blir utført i en tilstand som tilfredsstiller A, så vil den avslutte i en tilstand som tilfredsstiller B, når den stopper. Den andre antakelsen er at når α 2 utføres i en tilstand som tilfredsstiller B, så vil den avslutte i en tilstand som tilfredsstiller C, når den stopper. Konklusjonen av regelen handler om den delvise korrektheten til programmet α 1; α 2 (dvs. α 1 i rekkefølge sammensatt med α 2), følger av de to forutsetningene. Nemlig kan vi konkludere med at hvis α 1; α 2 utføres i en tilstand som tilfredsstiller A, så avsluttes den i en tilstand som tilfredsstiller C, når den stopper.

Regelen om iterasjon er en viktig fordi den fanger opp programmets essensielle evne til å utføre en del av koden gjentatte ganger til en viss tilstand slutter å holde.

{A ∧ B} α {A} (iterasjonsregel)
{A} mens B gjør α {¬ B ∧ A}

Til slutt er de to konsekvensreglene grunnleggende for å gi et formelt grunnlag for intuitivt tydelig resonnement som involverer henholdsvis svakere postforhold og sterkere forutsetninger.

{A} α {B} B → C (regel om konsekvens 1)
{A} α {C}
C → A {A} α {B} (regel om konsekvens 2)
{C} α {B}

Fra formalismen som ble presentert i Hoare [1969], utelater vi dens aksiomskjemaer som det ville kreve et førsteordens språk. Til slutt, i påfølgende arbeid med Hoare-logikk, blir det ofte ofte lagt til flere regler. Se Apt [1979] for en tidlig oversikt.

3.2 Hoarekalkulus og PDL

Dynamisk logikk kommer fra Pratt sin tolkning av Hoare triples og Hoare calculus i formaliteten til modal logikk. Med modaliteten [α] kan vi formelt uttrykke at alle tilstander som kan nås ved å utføre α tilfredsstiller formelen A. Dette gjøres ved å skrive [α] A. Dermed blir Hoare-trippelen {A} α {B} enkelt fanget opp av PDL-formelen

A → [α] B

I tillegg introduseres viktige programmeringskonstruksjoner enkelt i PDL ved definisjonell forkortelse:

  • hvis A deretter α annet β = df ((A;? α) ∪ (¬ A;? β))
  • mens A gjør α = df ((A?; α) *; ¬ A?)
  • gjenta α til A = df (α; (((¬ A; α) *; A?))
  • abortere = df 0?
  • hoppe = df 1?

Dermed ser det ut til at vi med PDL er godt rustet til å logisk bevise riktigheten av strukturerte programmer. Utover denne ganske håndbølgende forbindelsen mellom PDL og Hoare-beregningen, er det kanskje ennå ikke klart hvordan de formelt forholder seg. PDL er faktisk en generalisering av Hoare-kalkulus i den forstand at alle reglene for Hoare-kalkulusen kan bevises i det aksiomatiske systemet til PDL. (På en streng måte inneholder Hoare-beregningen aksiomer som vil kreve det utvidede språket i førsteordens dynamisk logikk.) Dette er ganske bemerkelsesverdig, så vi vil her vise de to reglene ovenfor for å tjene som eksempler.

Bevisene starter med å legge til grunn premissene for reglene. Ved å bruke disse forutsetningene, aksiomene og reglene for PDL, og ingenting annet, er målet å slå fast at konklusjonen av reglene logisk følger. Derfor, for komposisjonsregelen, begynner vi med å anta {A} α 1 {B}, det vil si A → [α 1] B i sin PDL-formulering, og ved å anta {B} α 2 {C}, det vil si B → [α 2] C. Målet er å bevise at {A} α 1; α 2 {C}. Nettopp vi ønsker å slå fast at A → [α 1; α 2] C er ⊢-avdragbar fra settet med formler {A → [α 1] B, B → [α 2] C}.

1. A → [α 1] B antagelse {A} α 1 {B}
2. B → [α 2] C. antagelse {B} α 2 {C}
3. 1] B → [α 1] [α 2] C Fra 2 ved å bruke monotoni av [α 1]
4. A → [α 1] [α 2] C fra 1 og 3 ved hjelp av proposisjonelle resonnementer
5. 1; α 2] C ↔ [α 1] [α 2] C aksiomskjema (A1)
6. A → [α 1; α 2] C fra 4 og 5 ved hjelp av proposisjonelle resonnementer
- {A} α 1; α 2 {C}

Beviset på iterasjonsregelen er litt mer involvert.

1. A ∧ B → [α] A antagelse {A ∧ B} α {A}
2. A → (B → [α] A) fra 1 ved hjelp av proposisjonelle resonnementer
3. [B?] [Α] A ↔ (B → [α] A) aksiomskjema (A4)
4. A → [B?] [Α] A fra 2 og 3 ved hjelp av proposisjonelle resonnementer
5. [B?; α] A ↔ [B?] [α] A aksiomskjema (A1)
6. A → [B?; Α] A fra 4 og 5 ved hjelp av proposisjonelle resonnementer
7. A → [(B?; Α) *] A fra 6 bruker (I)
8. A → (¬ B → (¬ B ∧ A)) proposisjonell tautologi
9. A → [(B?; Α) *] (¬ B → (¬ B ∧ A)) fra 7 og 8 ved å bruke monotoni av [(B?; α) *] og proposisjonell resonnement
10. [¬ B?] (¬ B ∧ A) ↔ (¬ B → (¬ B ∧ A)) Aksiomskjema (A4)
11. A → [(B?; Α) *] [¬ B?] (¬ B ∧ A) fra 9 og 10 ved å bruke monotoni av [(B?; α) *] og proposisjonell resonnement
12. [(B?; Α) *; ¬ B?] (¬ B ∧ A) ↔ [(B?; Α) *] [¬ B?] (¬ B ∧ A) aksiomskjema (A1)
1. 3. A → [(B?; Α) *; ¬ B?] (¬ B ∧ A) fra 12 ved hjelp av proposisjonelle resonnementer
- {A} mens B gjør α {¬ B ∧ A}

I sammenheng med PDL er de to konsekvensreglene faktisk spesielle tilfeller av komposisjonsregelen. For å få den første regelen, erstatt α 1 med α og α 2 med hopp. For å få den andre regelen, erstatt α 1 med hopp og α 2 med α. Det er nok å anvende aksiomskjemaet (A4), og å bemerke at [α; hopp over] A ↔ [α] A og [α; hopp over] A ↔ [α] A er også ⊢-deduberbare for alle A og alle α.

3.3 Total korrekthet

Ved Hoares egen innrømmelse i Hoare [1979] var hans opprinnelige beregning bare et utgangspunkt og led ganske mange begrensninger. Spesielt tillater det bare en å resonnere om delvis korrekthet. Det vil si at sannheten i en uttalelse {A} α {B} bare sørger for at alle henrettelser av α som starter i en tilstand som tilfredsstiller A, vil ende i en tilstand som tilfredsstiller B, eller ikke vil stoppe. Det vil si at et delvis korrekt program kan ha ikke-avsluttende henrettelser. (Faktisk vil et program som ikke har noen avsluttende utførelse alltid være delvis riktig. Dette er tilfellet for eksempel for programmet mens 1 hopper over. Formelen A → [ mens 1 hopper over] B er deducerbar for alle formlene A og B.) Kalkulaturen gir ikke grunnlag for et bevis på at et program avsluttes. Den kan modifiseres for å gjøre rede for programmets totale korrekthet: delvis korrekthet pluss avslutning. Det oppnås ved å endre iterasjonsregelen. Vi presenterer det ikke her og henviser den interesserte leseren til Apt [1981].

La oss først observere at for deterministiske programmer kan man allerede fange total korrekthet via formler av den typen

A → B

Uttrykket B betyr at det er en henrettelse av α som avsluttes i en tilstand som tilfredsstiller B. Hvis α er deterministisk, er dessuten denne mulige avsluttende utførelsen den unike utførelsen av α. Hvis man først klarer å bevise at et program er deterministisk, fungerer dette trikset godt nok til å bevise dets totale korrekthet.

En generell løsning på problemet med total korrekthet eksisterer i PDL-området. Men vi må utvide det litt. Pratt hadde allerede antydet i Pratt [1980b] at PDL ikke er uttrykksfull nok til å fange ut uendelig looping av programmer. Som reaksjon ble PDL med repetering (RPDL) introdusert av Streett [1982]. Det inneholder, for alle programmer α, uttrykket Δα som står for en ny proposisjon med semantikk

V (Δα) = {x: det eksisterer en uendelig sekvens x 0, x 1, … av tilstander slik at x 0  = x og for alle n ≥ 0, x n R (α) x n +1 }

Streett [1982] antok at RPDL kan aksiomatiseres ved å legge til korrektursystemet til PDL nøyaktig de følgende aksiomskjemaene.

(A6) Δα → Δα

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

Beviset for formodningen ble gitt i Sakalauskaite og Valiev [1990]. (En versjon av formodningen i varianten av kombinasjons-PDL ble også påvist i Gargov og Passy [1988].)

Det er lett å se at i Hoare-beregningen som er presentert over, kan ikke terminering bare komme fra iterasjonsregelen. Analogt kan ikke avslutning av et PDL-program bare komme fra bruk av ubegrenset iterasjon. Uttrykket indicatesα indikerer at α * kan avvike, og dette er bare den typen forestillinger vi trenger. Vi kan nå induktiv definere et predikat ∞ slik at for et program α, vil formelen ∞ (α) være sant nøyaktig når α kan gå inn i en ikke-avsluttende beregning.

∞ (π): = 0 hvor π ∈ Π 0

∞ (φ?): = 0

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

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

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

Til slutt kan den totale korrektheten til et program uttrykkes via formler av den typen

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

som bokstavelig talt betyr at hvis A er tilfelle, kan ikke programmet α kjøres for alltid, og enhver vellykket utførelse vil ende i en tilstand som tilfredsstiller B.

4. Noen varianter

Resultater om komparativ uttrykkskraft, avgjørbarhet, kompleksitet, aksiomatisering og fullstendighet av en rekke varianter av PDL oppnådd ved å utvide eller begrense syntaks og dens semantikk utgjør emnet for et vell av litteratur. Vi kan bare si så mye, og vi vil ta opp bare noen få av disse variantene og etterlater store biter av ellers viktig arbeid i dynamisk logikk.

4.1 PDL uten tester

Aksiomskjemaet [A?] B ↔ (A → B) ser ut til å indikere at for hver formel C finnes det en ekvivalent testfri formel C '-ie, det er en testfri formel C' slik at ⊨ C ↔ C '. Det er interessant å observere at denne påstanden er usann. La PDL 0 være begrensningen av PDL til testfrie vanlige programmer, dvs. programmer som ikke inneholder tester. Berman og Paterson [1981] vurderte PDL-formelen <(p?; Π) *; ¬ p?; Π; p?> 1, som er

< mens p do π> s

og bevist at det ikke er noen PDL 0- formel som tilsvarer den. Derfor har PDL mer uttrykkelig kraft enn PDL 0. Argumentasjonen deres kan faktisk generaliseres som følger. For alle n ≥ 0, la PDL n +1 være delmengden av PDL der programmene kan inneholde test A? bare hvis A er en PDL n- formel. For alle n ≥ 0 vurderte Berman og Paterson PDL n +1 formel A n +1 definert av

< mens A n gjør π n > <π n > A n

hvor A 0  = p og π 0  = π og beviste at for alle n ≥ 0, er det ingen PDL n- formel som tilsvarer A n +1. Derfor, for alle n ≥ 0, har PDL n +1 mer uttrykkskraft enn PDL n.

4.2 PDL med samtale

CPDL er utvidelsen av PDL med converse. Det er en konstruksjon som har blitt vurdert siden begynnelsen av PDL. For alle programmene α, la α -1 stå for et nytt program med semantikk

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

Den samtale konstruksjonen lar oss uttrykke fakta om tilstander som går foran den nåværende og å resonnere baklengs om programmer. For eksempel betyr [α -1] A at A måtte holde inne før han utførte α. Vi har

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

Tilsetningen av converse-konstruksjonen endrer ikke egenskapene til PDL på noen vesentlig måte. Ved å legge til alle forekomster av følgende aksiomskjemaer:

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

(A9) A → [α -1] A

til bevissystemet til PDL, oppnår vi et forsvarlig og fullstendig dedusibilitetspredikat på det utvidede språket. Se Parikh [1978] for detaljer. CPDL har den lille modellegenskapen og (CPDL-SAT) er EXPTIME-komplett.

Det er lett å bemerke at CPDL har mer uttrykkelig kraft enn PDL. For å se dette, vurder CPDL-formelen <π -1 > 1 og LTSs M = (W, R, V) og M '= (W', R ', V') hvor W = {x, y}, R (π) = {(x, y)}, W '= {y'}, R '(π) = ∅ og V (x) = V (y) = V' (y ') = ∅. Siden M, y satt <π -1 > 1, ikke M ', y' satt <π -1 > 1, og fordi det for alle PDL-formler A er tilfelle at M, y sat A iff M ', y' sat A, da er det klart at ingen PDL-formel tilsvarer <π -1 > 1.

4.3 PDL med repetisjon og looping

Vi har allerede utsatt kraften til å gjenta i avsnitt 3.3 ved å innføre RPDL. Her oppsummerer vi flere resultater om RPDL og dens tilknytning til andre varianter av forestillingen om gjentatte programmer.

Når det gjelder kompleksitetsteorien til RPDL, hadde Streett [1982] allerede slått fast at RPDL hadde den endelige modellegenskapen; nettopp at hver RPDL-tilfredsstillende formel A er tilfredsstillende i en modell av størrelse, høyst tredobbelt eksponentiell i lengden på A. Et automatisk-teoretisk argument tillatt å konkludere med at problemet (RPDL-SAT) kan løses i deterministisk trippel eksponentiell tid (3-EXPTIME). Gapet mellom denne øvre grensen for å bestemme (RPDL-SAT) og den enkle eksponentielle tidens nedre grense for å bestemme (PDL-SAT) var således åpen. Problemet fant seg sterkt knyttet til den økende interessen til dataforskere for å etablere kompleksiteten i tidsmessige logikker, og mer spesifikt til (proposisjonell) modal μ-kalkulus (MMC) på grunn av Kozen [1983], fordi RPDL har et lineært slag- opp oversettelse til MMC. Dessuten,Streetts argumentasjon satte noe prejudikat i den nå gjennomgripende bruken av automatteknikker for å bevise beregningsegenskaper for logikk for programmer og for tidslogikk. I Vardi og Stockmeyer [1985] ble det vist en øvre grense i ikke-deterministisk eksponentiell tid. I Emerson og Jutla [1988] og i den endelige formen i Emerson og Jutla [1999] ble det vist at (MMC-SAT) og (RPDL-SAT) er EXPTIME-komplette. Hvis vi legger til samtaleoperatøren i avsnitt 4.2, oppnår man CRPDL. Kompleksiteten til (CRPDL-SAT) forble åpen i noen år, men det kan vises til å være EXPTIME-fullstendig. Dette oppnås ved å kombinere teknikkene til Emerson og Jutla [1988] og Vardi [1985], som i Vardi [1998]. I Vardi og Stockmeyer [1985] ble det vist en øvre grense i ikke-deterministisk eksponentiell tid. I Emerson og Jutla [1988] og i den endelige formen i Emerson og Jutla [1999] ble det vist at (MMC-SAT) og (RPDL-SAT) er EXPTIME-komplette. Hvis vi legger til samtaleoperatøren i avsnitt 4.2, oppnår man CRPDL. Kompleksiteten til (CRPDL-SAT) forble åpen i noen år, men det kan vises til å være EXPTIME-fullstendig. Dette oppnås ved å kombinere teknikkene til Emerson og Jutla [1988] og Vardi [1985], som i Vardi [1998]. I Vardi og Stockmeyer [1985] ble det vist en øvre grense i ikke-deterministisk eksponentiell tid. I Emerson og Jutla [1988] og i den endelige formen i Emerson og Jutla [1999] ble det vist at (MMC-SAT) og (RPDL-SAT) er EXPTIME-komplette. Hvis vi legger til samtaleoperatøren i avsnitt 4.2, oppnår man CRPDL. Kompleksiteten til (CRPDL-SAT) forble åpen i noen år, men det kan vises til å være EXPTIME-fullstendig. Dette oppnås ved å kombinere teknikkene til Emerson og Jutla [1988] og Vardi [1985], som i Vardi [1998]. Kompleksiteten til (CRPDL-SAT) forble åpen i noen år, men det kan vises til å være EXPTIME-fullstendig. Dette oppnås ved å kombinere teknikkene til Emerson og Jutla [1988] og Vardi [1985], som i Vardi [1998]. Kompleksiteten til (CRPDL-SAT) forble åpen i noen år, men det kan vises til å være EXPTIME-fullstendig. Dette oppnås ved å kombinere teknikkene til Emerson og Jutla [1988] og Vardi [1985], som i Vardi [1998].

I avsnitt 3.3 har vi definert et predikat ∞, der ∞ (α) betyr at α kan ha ikke-avsluttende beregning. Vi kaller LPDL logikken oppnådd ved å øke PDL med predikatet ∞. Det er klart RPDL er minst like uttrykksfulle som LPDL; Den induktive definisjonen av ∞ (α) på språket til RPDL er vitne til den. RPDL er faktisk strengt mer uttrykksfull enn LPDL. Dette ble vist i Harel og Sherman [1982]. Som det kan mistenkes, har både RPDL og LPDL mer uttrykkelig kraft enn PDL. Det er etablert ved å bevise at noen formler av RPDL og LPDL ikke har noen tilsvarende uttrykk i PDL. Beviset innebærer filtreringsteknikken som er designet for å kollapse en LTS til en endelig modell, mens den ikke inneholder sannheten eller falsken i visse formler. For noen sett med PDL-formler X,det består i å gruppere tilstandene i en LTS i ekvivalensklasser som tilfredsstiller nøyaktig de samme formlene i X. Settet med ekvivalensklasser av stater som således oppnås blir settet med tilstander i filtratmodellen, og en overgang bygges passende over dem.

Med et nøye valgt sett FL (A) som er avhengig av en PDL-formel A (den såkalte Fischer-Ladner-lukkingen av settet med underformler til A), gir en filtrering av en LTS M et begrenset filtrat M ', slik at A er tilfredsstillende i en verden u i M hvis og bare hvis den er tilfredsstillende i ekvivalensklassen som inneholder u i filtratet. (Se Fischer og Ladner [1979].)

Vi kan nå vurdere filtreringene av LTS M = (W, R, V) hvor

  • W = {(i, j): j og i positive tall, 0 ≤ j ≤ i} ∪ {u}
  • (i, j) R (π) (i, j -1) når 1 ≤ j ≤ i
  • u R (π) (i, i) for hvert jeg
  • V (p) = ∅ for hver p ∈ Φ 0

I en setning, det som foregår i M, er at fra verden u er det et uendelig antall endelige π-stier med økende lengde. Vi har både M, u satt ¬Δπ og M, u sat ¬∞ (π *). Likevel, for hver PDL-formel A, vil vi ha både Δπ og π (π *) som er tilfreds med ekvivalensklassen til u i modellen oppnådd ved filtrering av M med FL (A). Faktisk må filtreringen kollapse noen tilstander i M og skape noen løkker. Således eksisterer det ingen PDL-formel som kan uttrykke verken Δπ eller ∞ (π *). og likevel vil vi ha både Δπ og ∞ (π *) som er tilfredsstilt i ekvivalensklassen u i ethvert begrenset filtrat av M. Verken Δπ eller ∞ (π *) kan således uttrykkes i PDL.

Det er andre måter å muliggjøre påstanden om at et program kan utføre for alltid. For eksempel, Danecki [1984a] foreslo et predikat livbåten for å kvalifisere programmer som kan gå inn i sterke løkker, som er:

V (livbåten (α)) = {x: x R (α) x}

La oss kalle SLPDL logikken oppnådd ved å øke PDL med sloop (α). RPDL og SLPDL er i det vesentlig uforlignelige: predikatet Δ er ikke definert i SLPDL, og predikat- sloop er ikke definert i RPDL. SLPDL har ikke den endelige modellegenskapen. For eksempel formelen

[π *] (1 ∧ ¬ sløyfe+))

er tilfredsstillende bare i uendelige LTS-er. Ikke desto mindre etablerte Danecki [1984a] avgjørbarheten av (SLPDL-SAT) formler i deterministisk eksponentiell tid.

4.4 PDL med kryss

En annen konstruksjon er studert: skjæringspunktet mellom programmer. Ved å legge kryss mellom programmer til PDL, oppnår vi logikken IPDL. I IPDL, for alle programmene α, β, står uttrykket α∩β for et nytt program med semantikk

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

For eksempel er den tiltenkte avlesningen av A at hvis vi utfører α og β i nåværende tilstand, så eksisterer det en tilstand som kan nås av begge programmene som tilfredsstiller A. Som et resultat har vi det

⊨ A → A ∧ A

men generelt har vi det

ikke ⊨ A ∧ A → A

Selv om kryssing av programmer spiller en viktig rolle i ulike anvendelser av PDL på kunstig intelligens og informatikk, forble bevissteorien og kompleksitetsteorien til PDL med kryss uutforsket i flere år. Når det gjelder kompleksitetsteorien til IPDL, dukker det opp vanskeligheter når man vurderer den endelige modellegenskapen. Faktisk konstruksjonen livbåten (α) kan uttrykkes i IPDL. I proposisjonell dynamisk logikk med kryss er den ekvivalent med 1. Vi kan dermed tilpasse formelen til IPDL i avsnitt 4.3, og vi har det

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

er tilfredsstillende bare i uendelige LTS-er. Med andre ord, IPDL har ikke den endelige modellegenskapen. Danecki [1984b] undersøkte kompleksitetsteorien til IPDL og viste at det å bestemme (IPDL-SAT) kan gjøres i deterministisk dobbel eksponentiell tid. (Et moderne bevis er presentert i Göller, Lohrey og Lutz [2007].) Kompleksitetsgapet mellom denne doble eksponentielle tidens øvre grense for avgjørelse (IPDL-SAT) og den enkle eksponensialtidens nedre grense for å bestemme (PDL-SAT) oppnådd av Fischer og Ladner [1979] forble åpen i mer enn tjue år. I 2004 etablerte Lange [2005] den nedre grensen for eksponentiell plass til (IPDL-SAT). I 2006Lange og Lutz [2005] ga et bevis på en dobbelt eksponensiell tids nedre grense av tilfredshetsproblemet for IPDL uten tester ved en reduksjon fra ordproblemet med eksponentielt plassbundne alternerende Turing-maskiner. I denne reduksjonen er iterasjonskonstruksjonens rolle essensiell siden, ifølge Massacci [2001], tilfredsstillelsesproblemet for iterasjonsfri IPDL uten test bare er PSPACE-fullstendig. Ved å legge converse-konstruksjonen til IPDL, får vi ICPDL. Tilfredshetsproblemet til ICPDL har vist seg å være 2-EXPTIME-fullstendig av Göller, Lohrey og Lutz [2007]. Tilfredshetsproblemet til ICPDL har vist seg å være 2-EXPTIME-fullstendig av Göller, Lohrey og Lutz [2007]. Tilfredshetsproblemet til ICPDL har vist seg å være 2-EXPTIME-fullstendig av Göller, Lohrey og Lutz [2007].

Når det gjelder bevisteorien om IPDL, oppstår vanskeligheter når vi innser at ikke noe aksiomskjema, på språket til PDL med kryss, “tilsvarer” semantikken x R (α∩β) y iff x R (α) y og x R (β) y av programmet α∩β. Det vil si, ikke på samme måte som for eksempel at aksiomskjemaene (henholdsvis A1) og (A2) “tilsvarer” semantikken til programmene α; β og α∪β. Av denne grunn var aksiomatiseringen av PDL med krysset åpen inntil det komplette bevissystemet ble utviklet i Balbiani og Vakarelov [2003].

I en annen variant av PDL, på grunn av Peleg [1987] og videre studert av Goldblatt [1992b], blir uttrykket ∩∩β tolket “do α og parallelt”. I denne sammenheng er de binære relasjonene R (α) og R (β) ikke lenger sett med par av formen (x, y) med x, y-verdener, men snarere sett med par av formen (x, Y) med xa verden og Y et sett med verdener. Den ble inspirert av Game Logic of Parikh [1985], en tolkning av PDL med “programmer som spill”. Game Logic gir en ekstra programkonstruksjon som dualiserer programmer, og dermed tillater å definere skjæringspunktet mellom programmer som det dobbelte av det ikke-deterministiske valget mellom programmer.

5. Konklusjon

Denne artikkelen har fokusert på proposisjonell dynamisk logikk og noen av dens betydningsfulle varianter. Det finnes nå en rekke bøker - Goldblatt [1982], Goldblatt [1992a], Harel [1979] og Harel, Kozen og Tiuryn [2000] - og undersøkelsesartikler-Harel [1984], Kozen og Tiuryn [1990], Parikh [1983] -behandlende PDL og relaterte formalismer. Forskningsdelen av PDL er absolutt medvirkende til å utvikle mange logiske teorier om systemdynamikk. Imidlertid er disse teoriene uten tvil utenfor omfanget av denne artikkelen. Van Eijck og Stokhof [2006] er en nyere oversikt over emner som bruker dynamisk logikk, og tar for seg ulike temaer som er av en viss interesse for filosofer: for eksempel kommunikasjonsdynamikk eller naturlig språksemantikk. Nyere bøker kommer mye mer om nyere emner,som dynamisk kunnskapslogikk (dynamisk epistemisk logikk) i Van Ditmarsch, Van Der Hoek og Kooi [2007], og den dynamiske logikken til kontinuerlige og hybride systemer (differensial dynamisk logikk) i Platzer [2010]. PDL ble først og fremst utformet for å resonnere om programmer. Det er mange andre applikasjoner med modal logikk for å resonnere om programmer. Algoritmisk logikk er nærmere PDL siden den lar en snakke eksplisitt om programmer. Leseren blir invitert til å konsultere arbeidet studert i Mirkowska og Salwicki [1987]. Midlertidig logikk er nå hovedlogikken i teoretisk informatikk og har en nær tilknytning til logikk av programmer. De lar en uttrykke den tidsmessige oppførselen til overgangssystemer med et språk som abstraherer bort fra etikettene (derav programmene). Se for eksempel Schneider [2004] for en oversikt over grunnlaget i dette forskningsområdet.

Bibliografi

  • Apt, K., 1981, “Ti år med Hoares logikk: En undersøkelse - Del I”, ACM Transactions on Programming Language and Systems, 3 (4): 431–483.
  • Balbiani, P., og D. Vakarelov, 2003, "PDL med skjæringspunkt mellom programmer: en fullstendig aksiomatisering", Journal of Applied Non-Classical Logics, 13: 231-276.
  • van Benthem, J., 1998, “Programkonstruksjoner som er trygge for bisimulering”, Studia Logica, 60: 311–330.
  • Berman, F. og M. Paterson, 1981, "Proposjonell dynamisk logikk er svakere uten tester", Theoretical Computer Science, 16: 321–328.
  • Burstall, R., 1974, “Program Proving as Hand Simulation with a Little Induction”, Informasjonsbehandling 74: Proceedings of IFIP Congress 74, Amsterdam: North Holland Publishing Company, 308–312.
  • Danecki, R., 1984a, "Propositionional dynamic logic with strong loop predicate", i M. Chytil og V. Koubek, Mathematical Foundations of Computer Science, Berlin: Springer-Verlag, 573-581.
  • –––, 1984b, “Nondeterministic proposjonal dynamisk logikk med kryss er avgjørbar”, i A. Skowron (red.), Computation Theory, Berlin: Springer-Verlag, 34-53.
  • De Giacomo, G. og F. Massacci, 2000, "Kombinere deduksjon og modellkontroll i tabeller og algoritmer for converse-PDL", Information and Computation, 160: 109–169.
  • van Ditmarsch, H., W. van Der Hoek, og B. Kooi, 2007, Dynamic epistemic logic, Dordrecht: Springer-Verlag.
  • van Eijck, J., og M. Stokhof, 2006, “The Gamut of Dynamic Logics”, i D. Gabbay og J. Woods (red.), The Handbook of History of Logic, Volume 7- Logic and the Modalities in the Twentieth Century, Amsterdam: Elsevier, 499–600.
  • Emerson, E., og Jutla, C., 1988, “The Complexity of Tree Automata and Logics of Programs (Extended Abstract)”, i Proceedings of the 29.th Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 328–337.
  • –––, 1999, “Kompleksiteten av treautomater og logikk av programmer”, i SIAM Journal of Computing, 29: 132–158.
  • Engeler, E., 1967, “Algoritmiske egenskaper ved strukturer”, Mathematical Systems Theory, 1: 183–195.
  • Fischer, M. og R. Ladner, 1979, “Proposjonell dynamisk logikk for vanlige programmer”, Journal of Computer and System Sciences, 18: 194–211.
  • Floyd, R., 1967, “Tildeling av mening til programmer”, Proceedings of the American Mathematical Society Symposia on Applied Mathematics (Volum 19), Providence, RI: American Mathematical Society, 19–31.
  • Gargov, G. og S. Passy, 1988, “Determinism and looping in combinatory PDL”, Theoretical Computer Science, Amsterdam: Elsevier, 259–277.
  • Goldblatt, R., 1982, Axiomatising the Logic of Computer Programming, Berlin: Springer-Verlag.
  • –––, 1992a, Logics of Time and Computation, Stanford: Center for the Study of Language and Information Publications.
  • ––– 1992b, “Parallel action: Concurrent Dynamic Logic with Independent Modalities”, Studia Logica, 51: 551–578.
  • Göller, S., M. Lohrey, og C. Lutz, 2007, “PDL med kryss og snakk er 2EXP-komplett”, Foundations of Software Science and Computational Structures, Berlin: Springer, 198–212.
  • Harel, D., 1979, First-Order Dynamic Logic, Berlin: Springer-Verlag.
  • –––, 1983, “Gjentakende dominoer: å gjøre det svært ubestridelige høyst forståelige”, i M. Karpinski (red.), Foundations of Computation Theory, Berlin: Springer-Verlag, 177–194.
  • –––, 1984, “Dynamisk logikk”, i D. Gabbay og F. Guenthner (red.), Handbook of Philosophical Logic (bind II), Dordrecht: D. Reidel, 497–604.
  • Harel, D., D. Kozen, og J. Tiuryn, 2000, Dynamic Logic, Cambridge, MA: MIT Press.
  • Harel, D. og Sherman, R., 1982, “Looping vs. Repeating in Dynamic Logic”, Information and Control, 55: 175–192.
  • Hoare, C., 1969, "Et aksiomatisk grunnlag for dataprogrammering", Communications of the Association of Computing Machinery, 12: 576–580.
  • Kozen, D., 1983, “Results on the Propositionional μ-calculus”, Theoretical Computer Science, 27: 333–354.
  • Kozen, D. og R. Parikh, 1981, “Et elementært bevis på fullstendigheten av PDL”, Theoretical Computer Science, 14: 113–118.
  • Kozen, D. og J. Tiuryn, 1990, “Logics of programmer”, i J. Van Leeuwen (red.), Handbook of Theoretical Computer Science (Volum B), Amsterdam: Elsevier, 789–840.
  • Lange, M., 2005, "En lavere kompleksitet bundet for proposisjonell dynamisk logikk med kryss", i R. Schmidt, I. Pratt-Hartmann, M. Reynolds og H. Wansing (red.), Fremskritt i modal logikk (bind 5), London: King's College Publications, 133–147.
  • Lange, M. og C. Lutz, 2005, “2-EXPTIME lavere grenser for proposisjonell dynamisk logikk med kryss”, Journal of Symbolic Logic, 70: 1072–1086.
  • Lutz, C., 2005, "PDL med skjæringspunkt og samtale er avgjørelig". I L. Ong (red.), Computer Science Logic, Berlin: Springer-Verlag, 413-427.
  • Massacci F. 193-198.
  • Mirkowska, G., og A. Salwicki, 1987, Algorithmic Logic, Dordrecht: D. Reidel.
  • Nishimura, H., 1979, “Sequential method in propositionional dynamic logic”, Acta Informatica, 12: 377–400.
  • Parikh, R., 1978, "The complete propositionional dynamic logic", i J. Winkowski (red.), Mathematical Foundations of Computer Science, Berlin: Springer-Verlag, 1978, 403-415.
  • –––, 1983, “Proposjonell logikk av programmer: nye retninger”, i M. Karpinski (red.), Foundations of Computation Theory, Berlin: Springer-Verlag, 347-359.
  • –––, 1985, “Logikken i spill og dens anvendelser”, Annals of Discrete Mathematics, 24: 111–140.
  • Peleg, D., 1987, "Samtidig dynamisk logikk", Journal of the Association of Computing Machinery, 34: 450–479.
  • Platzer, A., 2010, Logical Analysis of Hybrid Systems: Proving Theorems for Complex Dynamics, Berlin: Springer, 2010.
  • Pratt, V., 1976, “Semantiske betraktninger om Floyd-Hoare-logikk”, i Proceedings of the 17. IEEE Symposium on Foundations of Computer Science, Los Alamitos, CA: IEEE Computer Society, 109–121.
  • –––, 1978, “En praktisk beslutningsmetode for proposisjonell dynamisk logikk”, i Proceedings of the 10th Annual ACM Symposium on Theory of Computing, New York, NY: ACM, 326–337.
  • –––, 1980a, “En nesten optimal metode for resonnement om handling”, Journal of Computer and System Sciences, 20: 231–254.
  • –––, 1980b, “Application of Modal Logic to Programming”, Studia Logica, 39: 257–274.
  • Sakalauskaite, J., og M. Valiev, 1990, "Fullstendighet av proposisjonell dynamisk logikk med uendelig gjentagelse", i P. Petkov (red.), Mathematical Logic, New York: Plenum Press, 339–349.
  • Salwicki, A., 1970, "Formaliserte algoritmiske språk", Bulletin de l'Academie Polonaise des Sciences, Serie des sciences matematics, astronomiques et physiques, 18: 227–232.
  • Segerberg, K., 1977, "A completeness theorem in the modal logic of programmer", Notices of the American Mathematical Society, 24: 522.
  • Schneider, K., 2004, Verification of Reactive Systems, Berlin: Springer-Verlag.
  • Streett, R., 1982, "Proposjonell dynamisk logikk for looping og converse er elementær avgjørbar", Information and Control, 54: 121–141.
  • Vakarelov, D., 1983, "Filtreringsteorem for dynamiske algebraer med tester og invers operatør", i A. Salwicki (red.), Logics of Programs and the Applications, Berlin: Springer-Verlag, 314–324.
  • Vardi, M., 1985, “The Taming of Converse: Reasoning about Two-way Computations”, i Lecture Notes in Computer Science (bind 193), Berlin-Heidelberg: Springer, 413–423.
  • –––, 1998, “Resonnerer om fortiden med toveis automata”, i Lecture Notes in Computer Science (bind 1443), Berlin-Heidelberg: Springer, 628–641.
  • Vardi, M. og Stockmeyer, L., 1985, "Forbedrede øvre og nedre grenser for modal logikk av programmer: Foreløpig rapport", i Proceedings of the 17th ACM Symposium on Theory of Computing, New York, NY: ACM, 240 -251.
  • Yanov, J., 1959, “On equivalence of operator plans”, Problems of Cybernetic, 1: 1–100.

Akademiske verktøy

september mann ikon
september mann ikon
Hvordan sitere denne oppføringen.
september mann ikon
september mann ikon
Forhåndsvis PDF-versjonen av denne oppføringen hos Friends of the SEP Society.
inpho-ikonet
inpho-ikonet
Slå opp dette emnet på Internet Philosophy Ontology Project (InPhO).
phil papirer ikon
phil papirer ikon
Forbedret bibliografi for denne oppføringen på PhilPapers, med lenker til databasen.

Andre internettressurser

[Ta kontakt med forfatteren med forslag.]

Anbefalt: