Loading AI tools
De Wikipédia, l'encyclopédie libre
La logique temporelle est une branche de la logique mathématique et plus précisément de la logique modale, qui est formalisée de plusieurs manières. La caractéristique commune de ces formalisations réside en l'ajout de modalités (autrement dit de « transformateurs de prédicats ») liées au temps ; par exemple, une formule typique de la logique modale est la formule , qui se lit : « la formule est satisfaite jusqu'à ce que la formule le soit » et qui signifie que l'on cherche à garantir qu'une certaine propriété (ici ) est satisfaite pendant tout le temps qui court avant qu'une autre formule (ici ) le soit.
D'un point de vue sémantique, cela signifie que la notion de vérité dans ces logiques prend en compte l'évolution du monde. C'est-à-dire qu'une proposition peut être, à un moment, satisfaite, puis plus tard, ne plus l'être.
Plusieurs formalisations de la logique temporelle ont été décrites, prenant en compte diverses modalités de base.
La logique temporelle est très utilisée en vérification formelle, où la technique de base est essentiellement le model checking. On peut, par exemple, y exprimer le fait qu'un événement dangereux ne doit pas survenir tant qu'une certaine condition de sécurité n'est pas satisfaite.
Dans cet article, seul est présenté le calcul des propositions temporel, autrement dit un calcul des propositions augmenté de modalités temporelles, qui sera néanmoins appelé « logique temporelle ».
Ces logiques sont définies sur un ensemble de propositions atomiques P ou variables de propositions. Ces propositions atomiques sont combinées par un certain nombre de connecteurs logiques, dont les connecteurs usuels : et, ou, non, implication, ainsi que d'autres opérateurs que l'on appelle des modalités. La logique temporelle est donc une logique modale. Dans le cas de la logique temporelle linéaire (LTL), on ajoute les modalités suivantes
Une formule de logique des propositions classique, comme la formule (a et b) ou c sur l'ensemble de propositions P = {a, b, c}, associe une valeur de vérité, vrai ou faux, à chaque sous-ensemble de P. Par cette formule exemple, le sous-ensemble {a} (où a a la valeur vrai et b et c ont la valeur faux) rend la formule fausse, le sous-ensemble {b, c} la rend vraie.
Une formule de logique temporelle associe une valeur de vérité non pas à chaque partie de P, mais selon le type de logique, à chaque suite de parties de P ou à chaque arbre sur les parties de P. Une logique définie sur les suites est dite linéaire, tandis qu'une formule définie sur les arbres est dite branching logic ou logique à embranchements.
Prenons le cas des logiques linéaires. Une telle logique associe donc une valeur de vérité, vrai ou faux, à chaque suite telle que chaque soit une partie de P. Notons M une telle formule, nous avons :
Intuitivement, si la suite V représente l'évolution dans le temps des différentes propositions de P, alors :
On peut noter que les modalités U et R sont duales l'une de l'autre :
Il existe différentes logiques temporelles, dont :
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.