Γραμμική χρονική λογική: Διαφορά μεταξύ των αναθεωρήσεων

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Ρομπότ: Μεταφέρω 4 σύνδεσμους interwiki, που τώρα παρέχονται από τα Wikidata στο d:Q1536492
μ Αντικατάσταση παρωχημένης σύνταξης latex (mw:Extension:Math/Roadmap)
Γραμμή 5: Γραμμή 5:


== Σύνταξη ==
== Σύνταξη ==
Η LTL αποτελείται από ένα σύνολο από προτασιακές μεταβλητές <math>p_1, p_2, \dots</math>, τους γνωστούς λογικούς συνδέσμους <math>\neg,\or,\and,\rightarrow</math> και τους ακόλουθους χρονικούς τροπικούς τελεστές:
Η LTL αποτελείται από ένα σύνολο από προτασιακές μεταβλητές <math>p_1, p_2, \dots</math>, τους γνωστούς λογικούς συνδέσμους <math>\neg,\lor,\land,\rightarrow</math> και τους ακόλουθους χρονικούς τροπικούς τελεστές:


*'''X''' για το "επόμενο" (ή '''N''')
*'''X''' για το "επόμενο" (ή '''N''')
Γραμμή 65: Γραμμή 65:
== Ισοδυναμίες ==
== Ισοδυναμίες ==


<math>X ( \phi \or \psi ) \equiv X \phi \or X \psi</math>
<math>X ( \phi \lor \psi ) \equiv X \phi \lor X \psi</math>


<math>X ( \phi \and \psi ) \equiv X \phi \and X \psi</math>
<math>X ( \phi \land \psi ) \equiv X \phi \land X \psi</math>


<math>X \neg \phi \equiv \neg X \phi</math>
<math>X \neg \phi \equiv \neg X \phi</math>
Γραμμή 73: Γραμμή 73:
<math>X ( \phi U \psi ) \equiv ( X \phi ) U ( X \psi )</math>
<math>X ( \phi U \psi ) \equiv ( X \phi ) U ( X \psi )</math>


<math>F ( \phi \or \psi ) \equiv F \phi \or F \psi</math>
<math>F ( \phi \lor \psi ) \equiv F \phi \lor F \psi</math>


<math>\neg F \phi \equiv G \neg \phi</math>
<math>\neg F \phi \equiv G \neg \phi</math>


<math>G ( \phi \and \psi ) \equiv G \phi \and G \psi</math>
<math>G ( \phi \land \psi ) \equiv G \phi \land G \psi</math>


<math>\neg G \phi \equiv F \neg \phi</math>
<math>\neg G \phi \equiv F \neg \phi</math>


<math>( \phi \and \psi ) U \rho \equiv ( \phi U \rho ) \and ( \psi U \rho )</math>
<math>( \phi \land \psi ) U \rho \equiv ( \phi U \rho ) \land ( \psi U \rho )</math>


<math>\rho U ( \phi \or \psi ) \equiv ( \rho U \phi ) \or ( \rho U \psi )</math>
<math>\rho U ( \phi \lor \psi ) \equiv ( \rho U \phi ) \lor ( \rho U \psi )</math>


<math>F \phi \equiv F F \phi</math>
<math>F \phi \equiv F F \phi</math>
Γραμμή 91: Γραμμή 91:
<math>\phi U \psi \equiv \phi U ( \phi U \psi )</math>
<math>\phi U \psi \equiv \phi U ( \phi U \psi )</math>


<math>F \phi \equiv \phi \or X F \phi</math>
<math>F \phi \equiv \phi \lor X F \phi</math>


<math>G \phi \equiv \phi \and X G \phi</math>
<math>G \phi \equiv \phi \land X G \phi</math>


<math>\phi U \psi \equiv \psi \or ( \phi \and X ( \phi U \psi ) )</math>
<math>\phi U \psi \equiv \psi \lor ( \phi \land X ( \phi U \psi ) )</math>


<math>\phi W \psi \equiv \psi \or ( \phi \and X ( \phi W \psi ) )</math>
<math>\phi W \psi \equiv \psi \lor ( \phi \land X ( \phi W \psi ) )</math>


<math>\phi R \psi \equiv ( \phi \and \psi ) \or ( \psi \and X ( \phi R \psi ) )</math>
<math>\phi R \psi \equiv ( \phi \land \psi ) \lor ( \psi \land X ( \phi R \psi ) )</math>


== Ειδικοί σύνδεσμοι==
== Ειδικοί σύνδεσμοι==

Έκδοση από την 20:43, 19 Νοεμβρίου 2018

Η γραμμική χρονική λογική (linear temporal logic, LTL) είναι μια τροπική χρονική λογική με τροπικότητες που αναφέρονται στο χρόνο. Στην LTL, μπορούν να κωδικοποιηθούν προτάσεις για το μέλλον κάποιου μονοπατιού, ώστε μια συνθήκη να είναι τελικά αληθής, ή να είναι αληθής μέχρι ένα άλλο γεγονός να είναι αληθές, κλπ.

Ιστορία

Η LTL προτάθηκε αρχικά από τον Αμίρ Πνουέλι για την επαλήθευση προγραμμάτων υπολογιστή το 1977.

Σύνταξη

Η LTL αποτελείται από ένα σύνολο από προτασιακές μεταβλητές , τους γνωστούς λογικούς συνδέσμους και τους ακόλουθους χρονικούς τροπικούς τελεστές:

  • X για το "επόμενο" (ή N)
  • G για το "πάντα" (αγγλ. globally)
  • F για το "τελικά" (αγγλ. future)
  • U για το "μέχρι"
  • R για το "απελευθέρωση"

Οι πρώτοι τρεις τελεστές είναι μοναδιαίοι, δηλαδή η X είναι καλά ορισμένη πρόταση όταν η είναι μια καλά ορισμένη πρόταση. Οι άλλοι δύο τελεστές είναι δυαδικοί, δηλαδή η U είναι καλά ορισμένη πρόταση όταν η και η είναι καλά ορισμένες.

Ένα μοντέλο της γραμμικής χρονικής λογικής

Σημασιολογία

Μια πρόταση LTL μπορεί να αποτιμηθεί πάνω σε μια άπειρη ακολουθία από αποτιμήσεις αληθείας, με μια θέση πάνω σε αυτό το μονοπάτι. Μια πρόταση LTL ικανοποιείται από ένα μονοπάτι αν και μόνο αν ικανοποιείται στη θέση 0 αυτού του μονοπατιού. Η σημασιολογία των τροπικών τελεστών δίνεται ως εξής:

Κείμενο Συμβολισμός Επεξήγηση Διάγραμμα
Μοναδιαίοι τελεστές:
X neXt: η πρέπει να ισχύει στην επόμενη κατάσταση. τελεστής LTL "επόμενο"
G Globally: η πρέπει να ισχύει σε όλο το υπόλοιπο μονοπάτι. τελεστής LTL "πάντα"
F Finally: η πρέπει τελικά να ισχύει (κάπου στο υπόλοιπο μονοπάτι). τελεστής LTL "τελικά"
Δυαδικοί τελεστές:
U Until: η πρέπει να ισχύει τουλάχιστον μέχρι τη , η οποία ισχύει στην τρέχουσα θέση ή σε κάποια θέση στο μέλλον. τελεστής LTL "μέχρι"
R Release: η πρέπει να είναι αληθής μέχρι και τη στιγμή που η γίνεται αληθής για πρώτη φορά - αν η δε γίνει ποτέ αληθής, η πρέπει να μείνει αληθής για πάντα. τελεστής LTL "απελευθέρωση" (που τερματίζει)

τελεστής LTL "απελευθέρωση" (που δεν τερματίζει)

Οι σύνδεσμοι X και U μπορούν να θεωρηθούν θεμελιώδεις και οι υπόλοιποι να οριστούν με βάση αυτούς, επειδή οι ακόλουθες ιδιότητες ικανοποιούνται πάντα:

  • F = αληθές U
  • G = ψευδές R = F
  • R = ( U )

Ισοδυναμίες

Ειδικοί σύνδεσμοι

Κάποιοι συγγραφείς ορίζουν ένα δυαδικό τελεστή αδύναμο μέχρι (weak until) με το σύμβολο W, η σημασιολογία του οποίου μοιάζει με αυτήν του τελεστή μέχρι αλλά η συνθήκη τερματισμού δε χρειάζεται να ισχύει (όπως στην απελευθέρωση). Είναι μερικές φορές χρήσιμος γιατί οι τελεστές U και R μπορούν να οριστούν με βάση αυτόν:

  • U = F ( W )
  • R = W ()
  • W = R ()
  • W = ( U )G

Σημαντικές ιδιότητες

Υπάρχουν δύο ειδών ιδιότητες που μπορούν να εκφραστούν με τη χρήση γραμμικής χρονικής λογικής: οι ιδιότητες χρονικής ασφάλειας (safety) συνήθως δηλώνουν ότι κάτι κακό δε συμβαίνει ποτέ (G), ενώ οι ιδιότητες ζωτικότητας (liveness) δηλώνουν ότι κάτι καλό συνεχίζει να συμβαίνει (GF ή GF). Γενικά: οι ιδιότητες της πρώτης κατηγορίας είναι αυτές στις οποίες οποιοδήποτε αντιπαράδειγμα έχει ένα τέτοιο πρόθεμα ώστε, με οποιοδήποτε τρόπο και αν επεκταθεί σε ένα άπειρο μονοπάτι, να είναι ακόμα αντιπαράδειγμα. Στις ιδιότητες της δεύτερης κατηγορίας όμως, κάθε πεπερασμένο πρόθεμα ενός αντιπαραδείγματος μπορεί να επεκταθεί σε ένα άπειρο μονοπάτι που ικανοποιεί την πρόταση.

Σχέσεις με άλλες λογικές

Η LTL είναι ισοδύναμη με τη λογική πρώτου βαθμού στην ολική διάταξη FO[<] , καθώς και με τις κανονικές εκφράσεις χωρίς άστρο και με τα ντετερμινιστικά αυτόματα πεπερασμένων καταστάσεων με πολυπλοκότητα βρόχου 0.

Έλεγχος μοντέλων γραμμικής χρονικής λογικής (θεωρία αυτομάτων)

Ένα σημαντικός τρόπος ελέγχου μοντέλων είναι η έκφραση της επιθυμητής ιδιότητας (όπως οι παραπάνω) με τελεστές LTL και ο έλεγχος αν το μοντέλο την ικανοποιεί. Μια τεχνική είναι η δημιουργία ενός αυτόματου Büchi που να είναι "ισοδύμαμο" με το μοντέλο και ενός που να είναι "ισοδύναμο" με την άρνηση της ιδιότητας. Αν το μοντέλο ικανοποιεί την ιδιότητα, τότε η τομή των δύο μη-ντετερμινιστικών αυτομάτων Büchi είναι κενή.

Εφαρμογές

Μια από τις εφαρμογές της γραμμικής χρονικής λογικής είναι η προδιαγραφή των προτιμήσεων (preference) στην Planning Domain Definition Language (preference-based planning).

Αναφορές

  • Αμίρ Πνουέλι: The temporal logic of programs. Proceedings of the 18th Annual Symposium on Foundations of Computer Science (FOCS), 1977, 46-57. DOI= 10.1109/SFCS.1977.32

Δείτε επίσης

Εξωτερικοί σύνδεσμοι

CC-BY-SA
Μετάφραση
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Linear temporal logic της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 4.0. (ιστορικό/συντάκτες).