Metryczna logika temporalna

Metryczna logika czasowa (MTL) jest szczególnym przypadkiem logiki czasowej . Jest to rozszerzenie logiki temporalnej, w której operatory temporalne są zastępowane wersjami ograniczonymi czasowo, takimi jak do , następny , od i poprzednie operatory. Jest to logika czasu liniowego, która zakłada zarówno abstrakcję przeplatania, jak i fikcyjnego zegara. Jest zdefiniowany na podstawie słabo monotonicznej semantyki czasu całkowitego opartej na punktach.

MTL został opisany jako wybitny formalizm specyfikacji dla systemów czasu rzeczywistego. Pełny MTL dla nieskończonych słów w czasie jest nierozstrzygalny.

Składnia

Pełna metryczna logika czasowa jest zdefiniowana podobnie do liniowej logiki czasowej , w której do czasowych operatorów modalnych U i S dodawany jest zestaw nieujemnych liczb rzeczywistych . Formalnie MTL składa się z:

skończony zbiór zmiennych zdaniowych AP ,
operatory logiczne ¬ i ∨ oraz
czasowy operator modalny $UI I$ (wymawiane „ $φ$ aż do $I$ $ψ$ .”), gdzie $jest$ przedziałem liczb nieujemnych.
czasowy operator modalny $S I$ (wymawiane „ $φ$ ponieważ w $I$ $ψ$ .”), gdzie I $jak$ powyżej.

Kiedy indeks dolny jest pominięty, jest domyślnie równy ${\ Displaystyle [0, \ infty)}$ .

Zauważ, że następny operator N nie jest uważany za część składni MTL. Zamiast tego zostanie zdefiniowany na podstawie innych operatorów.

Przeszłość i przyszłość

Przeszły fragment metrycznej logiki temporalnej , oznaczony jako past-MTL , jest zdefiniowany jako ograniczenie pełnej metrycznej logiki temporalnej bez operatora till. Podobnie, przyszły fragment metrycznej logiki temporalnej , oznaczony jako future-MTL, jest zdefiniowany jako ograniczenie pełnej metrycznej logiki temporalnej bez operatora since.

W zależności od autorów, MTL jest definiowany jako przyszły fragment MTL, w którym to przypadku pełny MTL nazywa się MTL+Past . Lub MTL jest zdefiniowany jako pełny MTL.

Aby uniknąć dwuznaczności, w tym artykule użyto nazw full-MTL, past-MTL i future-MTL. Gdy instrukcje dotyczą trzech logiki, po prostu zostanie użyty MTL.

Model

Niech intuicyjnie reprezentuje zbiór punktów w czasie ${\ displaystyle T \ subseteq \ mathbb {R} _ {+}}$ Niech ${\ displaystyle \ gamma: T \ do A}$ funkcja, która kojarzy literę z każdym momentem ${\ displaystyle t \ in T}$ . Model formuły MTL jest taką funkcją ${\ displaystyle \ gamma}$ . Zwykle jest to $czasie$ określone w lub sygnał . W takich przypadkach $podzbiorem$ albo przedziałem zawierającym 0.

Semantyka

Niech $displaystyle T}$ $czas$ i ${\ displaystyle \ gamma}$ jak wyżej i niech jakiś ustalony Teraz wyjaśnimy, co to znaczy, że formuła MTL $gamma, t \ modele \ phi$ w czasie , który jest oznaczony . $Displaystyle$ $t$ .

Niech ${\ Displaystyle I \ subseteq \ mathbb {R} _ {+}}$ i ${\ Displaystyle \ phi, \ psi \ w MTL}$ . Najpierw rozważymy formułę ${\ Displaystyle \ phi {\ mathcal {U}} _ {I} \ psi}$ . Mówimy, że ${\ Displaystyle \ gamma, t \ modele \ fi {\ mathcal {U}} _ {I} \ psi}$ i tylko wtedy, gdy istnieje jakiś czas ${\ Displaystyle t '\ in I + t}$ takie, że:

${\ Displaystyle \ gamma, t '\ modele \ psi}$ i
dla każdego ${\ Displaystyle t''\ w T}$ z ${\ Displaystyle t <t'' <t'}$ , ${\ Displaystyle \ gamma, t ''\modele \phi}$ .

Rozważymy teraz formułę (wymawianą " ${\ Displaystyle \ phi}$ $ponieważ$ ja $I}$ $\ displaystyle \psi}$ $.$ ") Mówimy wtedy i tylko ${\ displaystyle t'\ in It}$ takie, że:

${\ Displaystyle \ gamma, t '\ modele \ psi}$ i
dla każdego ${\ Displaystyle t''\ w T}$ z ${\ Displaystyle t' <t'' <t}$ , ${\ Displaystyle \ gamma, t ''\modele \phi}$ .

Definicje dla wartości $nieuwzględnionych$ $podobne$ w LTL

Operatory zdefiniowane z podstawowych operatorów MTL

Niektóre formuły są tak często używane, że wprowadza się dla nich nowy operator. Operatory te zwykle nie są uważane za należące do definicji MTL, ale są cukrem składniowym , który oznacza bardziej złożoną formułę MTL. Najpierw rozważymy operatorów, które istnieją również w LTL. $mathbb {R} _ {+$ \ Displaystyle $subseteq$ .

Operatorzy podobni do operatorów LTL

Zwolnij i wróć do

Oznaczamy przez ${\ Displaystyle \ phi {\ mathcal {R}} _ {I} \ psi}$ (wymawiane " ${\ Displaystyle \ phi}$ wydanie w ${\ displaystyle I}$ , ${\ displaystyle \ \ psi}$ ") formuła ${\ Displaystyle \ neg \ phi {\ mathcal {U}} _ {I} \ neg \ psi}$ . Ta formuła obowiązuje w czasie, jeśli: ${\ displaystyle t}$

jest jakiś czas ${\ displaystyle t'\$ , że utrzymuje się i utrzymuje się w przedziale ${\ Displaystyle (t, t') \ czapka (t + ja)}$ $+ ja$ $t$ .
za każdym razem ${\ displaystyle t'\ w t + ja}$ , ${\ displaystyle \ phi}$ .

Nazwa „wydanie” pochodzi z przypadku LTL, gdzie ten wzór oznacza po prostu, że $.$ $go$ obowiązywać, chyba że zwolni

$\ Displaystyle$ odpowiednik wydania jest oznaczony przez (wymawiane " $\ phi}$ powrotem do w $displaystyle I}$ , ${\ Displaystyle \ psi}$ ") i jest równa formule ${\ Displaystyle \ neg \ phi {\ mathcal {S}} _ {I} \ neg \ phi}$ .

Wreszcie i ostatecznie

Oznaczamy przez ${\ Displaystyle \ Diament _ {I} \ phi}$ $($ wymawiane „Wreszcie w $displaystyle I}$ , ${\ Displaystyle \ phi}$ "lub "Ostatecznie w ${\ displaystyle I}$ ϕ $\ Displaystyle \ phi}$ ") formuła ${\ Displaystyle \ top {\ mathcal {U}} _ { I}\phi}$ . Intuicyjnie ta formuła obowiązuje w czasie ${\ displaystyle t}$ , jeśli jest trochę czasu, tak że ${\ displaystyle t '\ in t + ja}$ ${\ displaystyle \ phi}$ .

Oznaczamy przez ${\ Displaystyle \ Box _ {I} \ phi}$ lub ${\ Displaystyle {\ mathcal {G}} _ {I} \ phi}$ (wymawiane „Globalnie w $\ displaystyle I}$ , ${\ Displaystyle \ phi}$ ",) formuła ${\ Displaystyle \ neg \ Diament _ {I} \ neg \ phi}$ . Intuicyjnie, ta formuła obowiązuje w czasie, $przez$ cały czas ${\ displaystyle t'\ w t + ja}$ , ${\ displaystyle \ phi}$ trzyma.

Oznaczamy przez formułę ${\ Displaystyle {\ overleftarrow {\ Box}} _ {I} \ phi}$ i ${\ Displaystyle {\ overleftarrow {\ diament}} _ {I} \ phi}$ podobny do ${\ Displaystyle \ Box _ {I} \ phi}$ i ${\ Displaystyle \ Diament _ {I} \ phi}$ , gdzie zastępuje się ${\ Displaystyle {\ mathcal {U}}}$ ${\ Displaystyle {\ mathcal {S}}}$ . Obie formuły mają intuicyjnie to samo znaczenie, ale gdy weźmiemy pod uwagę przeszłość zamiast przyszłości.

Następny i poprzedni

Ten przypadek różni się nieco od poprzednich, ponieważ intuicyjne znaczenie formuł „Następny” i „Poprzedni” różni się w zależności od rodzaju $funkcji$ .

Oznaczamy przez ${\ displaystyle \ bigcirc _ {ja} \ phi}$ $lub$ ( wymawiane "Następny za $}$ , ${\ Displaystyle \ phi}$ ") formuła ${\ Displaystyle \ bot {\ mathcal {U}} _ {I} \ phi}$ . $Podobnie$ oznaczamy przez „Wcześniej ${\ Displaystyle I}$ ϕ $\ Displaystyle \ phi}$ ) formuła ${\ Displaystyle \ bot {\ mathcal {S}} _ {I} \ phi}$ . Poniższa dyskusja na temat operatora Next odnosi się również do operatora Poprzednio, poprzez odwrócenie przeszłości i przyszłości.

$oba$ ta formuła jest oceniana na podstawie , formuła oznacza, że

następnym razem w domenie definicji ${\ displaystyle$ obowiązywać formuła $T} .$
ponadto odległość między tym następnym razem a obecnym czasem należy do przedziału. ${\ displaystyle I}$ .
W szczególności ten następny czas się utrzymuje, więc obecny czas nie jest końcem słowa.

Kiedy ta formuła jest oceniana na $.$ sygnału , pojęcie następnego razu nie ma sensu Zamiast tego „następny” oznacza „zaraz po”. Dokładniej oznacza: ${\ Displaystyle \ gamma, t \ modele \ circ \ phi}$

${\ Displaystyle I}$ zawiera przedział postaci ${\ Displaystyle (0, \ epsilon)}$ i
dla każdego ${\ Displaystyle t '\ w (t, t + \ epsilon)}$ , ${\ Displaystyle \ gamma, t' \ modele \ phi}$ .

Inni operatorzy

Rozważymy teraz operatorów, którzy nie są podobni do żadnych standardowych operatorów LTL.

Upadek i powstanie

Oznaczamy przez ${\ displaystyle \ uparrow \ phi}$ (wymawiane "wzrost ${\ displaystyle \ phi}$ $"$ , wzór, który obowiązuje, gdy staje się prawdziwy. Dokładniej, albo $przeszłości$ i obowiązuje obecnie, albo nie obowiązuje i obowiązuje w najbliższej przyszłości Formalnie ${\ Displaystyle \ uparrow \ phi}$ jest zdefiniowany jako ${\ Displaystyle (\ phi \ ziemia (\ neg \ phi {\ mathcal {S}} \ top)} \ lor (\ neg \ phi \ ziemia (\ phi {\mathcal {U}}\top })}$ .

Ponadczasowe słowa, ta formuła zawsze obowiązuje. Rzeczywiście ${\ Displaystyle \ phi {\ mathcal {U}} \ top}$ i ${\ Displaystyle \ neg \ phi {\ mathcal {S}} \ top}$ zawsze trzymają. Zatem wzór jest równoważny , stąd jest prawdziwy. ${\ Displaystyle \ phi \ lor \ neg \ phi}$

$fałszywa$ symetrię oznaczamy przez $formułę$ wymawiane „Jesień $)$ , która obowiązuje, gdy staje się ${\ Displaystyle (\ neg \ phi \ ziemia (\ phi {\ mathcal {S}} \ top}) \ ziemia (\ phi \ ziemia (\ neg \ phi {\ mathcal {U}} \ top)}}$ .

Historia i proroctwo

Wprowadzimy teraz operator proroctwa , oznaczony przez ${\ displaystyle \ triangleright}$ . Oznaczamy przez $\$ ¬ $Displaystyle \ neg \ phi {\ mathcal {U}} _ {I}$ . Formuła ta stwierdza, że istnieje pierwszy moment w przyszłości, taki, że $zachodzi$ $a$ czas oczekiwania na ten pierwszy moment należy do .

Rozważymy teraz tę formułę względem słów czasowych i sygnałów. Najpierw rozważamy słowa czasowe. Załóżmy $że$ gdzie $_$ _ $_$ _ Niech ${\ displaystyle \ gamma}$ będzie słowem czasowym i ${\ displaystyle t}$ w jego domenie definicji. Ponadczasowe słowa, formuła ${\ Displaystyle \ gamma, t \ modele \ trójkąt w prawo _ {ja} \ phi}$ zachodzi wtedy i tylko wtedy, gdy ${\ Displaystyle \ gamma, t\models \Box _{]0,b[\setminus I}\neg \phi \land \Diamond _{I}\phi }$ również obowiązuje. Oznacza to, że ta formuła po prostu zapewnia, że w przyszłości, dopóki nie zostanie spełniony przedział $displaystyle t + I}$ ${\ displaystyle \ phi}$ nie powinno się utrzymywać. Ponadto ${\ displaystyle \ phi}$ powinien mieścić się kiedyś w przedziale ${\ displaystyle t + I}$ . ${\ Displaystyle t''\$ dowolny czas taki, że tylko $in t +$ skończoną liczbę czasu ${\ Displaystyle t'\ w t + ja}$ z ${\ Displaystyle t' <t''}$ i ${\ Displaystyle \ gamma, t' \ modele \ phi}$ . Zatem z konieczności istnieje mniejszy taki ${\ displaystyle t''}$ .

Rozważmy teraz sygnał. Wspomniana powyżej równoważność nie dotyczy już sygnału. Wynika to z faktu, że przy użyciu zmiennych wprowadzonych powyżej może istnieć nieskończona liczba poprawnych wartości dla $.$ na fakt, że dziedzina definicji sygnału jest ciągła $,$ wzór zapewnia również że pierwszy przedział, w którym $,$ jest zamknięty po lewej

Przez symetrię czasową definiujemy operator historii , oznaczony przez ${\ displaystyle \ triangleleft}$ . ◃ ja $\ Displaystyle \ triangleleft _ {I} \ phi}$ jako $S}} _ {I} \ phi}$ . Formuła ta stwierdza, że w przeszłości istnieje taki ostatni moment, który $utrzymywał$ . A czas od tej pierwszej chwili należy do ${\ displaystyle I}$ .

Nieścisły operator

Semantyka operatorów do i od wprowadzenia nie uwzględnia bieżącego czasu. To znaczy, aby w pewnym momencie trzymał się $phi _ {2}$ $}$ ${\ Displaystyle \ phi _ {1}},$ ani ϕ $\ Displaystyle \ phi _ {2}}$ nie musi się utrzymywać w czasie ${\ displaystyle t}$ . Nie zawsze jest to pożądane, na przykład w zdaniu „nie ma błędu, dopóki system nie zostanie wyłączony”, w rzeczywistości może być pożądane, aby w danym momencie nie było błędu. $związku$ tym wprowadzamy kolejny operator till , zwany nieścisłym till , oznaczony przez , który uwzględnia bieżący czas.

Oznaczamy przez ${\ Displaystyle \ phi _ {1} {\ overline {\ mathcal {U}}} _ {I} \ phi _ {2}}$ i ${ \ Displaystyle \ phi _ {1} {\ overline {\ mathcal {S}}} _ {I} \ phi _ {2}}$ albo:

ϕ ${\ Displaystyle \ phi _ {2} \ lor (\ phi _ {1} \ ziemia (\ phi _ {1} {\ mathcal {$ i ${\ Displaystyle \ phi _ {2} \ lor (\ phi _ {1} \land (\phi _{1}{\mathcal {S}}_{I}\phi _{2}))}$ jeśli ${\ Displaystyle 0 \ w I}$ i
φ ${\ Displaystyle \ phi _ {1} \ ziemia (\ phi _ {1} {\ mathcal {U}} _ {I} \ phi _ {2})$ i inaczej ${\ Displaystyle \ phi _ {1} \ ziemia (\ phi _ {1} {\ mathcal {S}} _ {I} \ phi _ {2})}$ .

Dla dowolnego z operatorów wprowadzonych powyżej oznaczamy formułę, w $}}$ nieścisłe do i od są $}$ używany. Na przykład ${\ displaystyle {\ overline {\ diament}} p}$ jest skrótem od ${\ displaystyle \ top {\ overline {\ mathcal {U}}} p}$ .

Operatora ścisłego nie można zdefiniować za pomocą operatora nieścisłego. Oznacza to, że nie ma formuły równoważnej z, $operatora$ nieścisłego. Ta formuła jest zdefiniowana jako ${\ displaystyle \ bot {\ mathcal {U}} _ {I} p}$ . Ta formuła $być$ $może$ zachowana w danym momencie, $jest$ to wymagane .

Przykład

Podamy teraz przykłady formuł MTL. Więcej przykładów można znaleźć w artykule fragmentów MITL, takich jak metryka interwałowa logika temporalna .

${\ Displaystyle \ Box (p \ implikuje \ Diament _ {\ {1 \}} q)}$ stwierdza, że po każdej literze następuje dokładnie jedna jednostka czasu później ${\ displaystyle p}$ litera ${\ Displaystyle q}$ .
${\ Displaystyle \ Box (p \ implikuje \ neg \ Diament _ {\ {1 \}} p)} stwierdza, że nie$ mogą wystąpić żadne dwa kolejne wystąpienia ${\ displaystyle p}$ dokładnie w jednej jednostce czasu od siebie.

Porównanie z LTL

Standardowe (nieokreślone w czasie) nieskończone słowo $\ Displaystyle \ mathbb {N}}$ N $Displaystyle \ mathbb {$ N ${\ displaystyle A}$ . Możemy rozważyć takie słowo za pomocą zestawu czasu $ja$ funkcji $) = a_ {i}}$ . W tym przypadku za ${\ Displaystyle \ phi}$ arbitralna formuła LTL, ${\ Displaystyle w, i \ modele \ phi}$ wtedy i tylko wtedy, gdy ${\ Displaystyle \ gamma, i \ modele \ phi}$ , gdzie $operatorem$ $MTL$ z nieścisłym i W tym sensie MTL jest rozszerzeniem LTL. ^{[ wymagane wyjaśnienie ]}

$dolnym jest$ tego powodu formuła używająca tylko nieścisłego operatora z formułą LTL Wynika to z faktu, że ^{[ potrzebne są dalsze wyjaśnienia ]}

Złożoność algorytmiczna

Spełnialność ECL na sygnałach jest EXPSPACE - zupełna .

Fragmenty MTL

Rozważymy teraz niektóre fragmenty MTL.

MITL

Ważnym podzbiorem MTL jest Metric Interval Temporal Logic ( MITL ). Jest to zdefiniowane podobnie do MTL, z $,$ że zbiory używane $przedziałami$ i $są$ które nie są singletonami i których granicami są liczby naturalne lub nieskończoność.

Niektóre inne podzbiory MITL są zdefiniowane w artykule MITL .

Przyszłe fragmenty

Future-MTL został już przedstawiony powyżej. Zarówno w przypadku słów o określonym czasie, jak i sygnałów, jest mniej ekspresyjny niż Full-MTL.

Logika czasowa zegara zdarzeń

Fragment Event-Clock Temporal Logic MTL, oznaczony jako EventClockTL lub ECL , dopuszcza tylko następujących operatorów:

operatory boolowskie i, lub, nie
bezczasowe operatory till i since.
Operatory proroctw czasowych i historii.

Ponad sygnałami, ECL jest tak wyrazisty jak MITL i MITL ₀ . Równoważność między dwiema ostatnimi logikami jest wyjaśniona w artykule MITL ₀ . Szkicujemy równoważność tych logik z ECL.

Jeśli $singletonem$ $zdefiniowana$ i formułą MITL, $jest$ jako formuła ja $\}}$ singletonem $◻$ równoważne który $_$ Z drugiej strony, dla $wzoru$ ECL i przedziału, którego dolna granica wynosi 0, $Displaystyle \ Box _ {I} \ psi}$ ${\$ z ECL -formuła ${\ Displaystyle \ neg \ trójkąt w prawo _ {I} \ neg \ psi}$ .

Spełnialność ECL po sygnałach jest PSPACE-zupełna .

Dodatnia postać normalna

Formuła MTL w dodatniej postaci normalnej jest zdefiniowana prawie jak każda formuła MTL, z dwoma następującymi zmianami:

operatory Release i Back są wprowadzone w języku logicznym i nie są już uważane za oznaczenia niektórych innych formuł.
negacje można zastosować tylko do liter.

Każda formuła MTL jest równoważna formule w normalnej postaci. Można to wykazać za pomocą łatwej indukcji we wzorach. $_ \displaystyle (\neg \phi {\mathcal {R}}_ {S}(\neg \psi)}$ formuła $_$ formule . Podobnie spójniki i alternatywy można rozpatrywać za pomocą praw De Morgana .

Ściśle mówiąc, zbiór formuł w dodatniej postaci normalnej nie jest fragmentem MTL.

Zobacz też

Timed propositional temporal logic , kolejne rozszerzenie LTL, w którym można mierzyć czas.