Temporal logic

From Free net encyclopedia

In logic, the term temporal logic is used to describe any system of rules and symbolism for representing, and reasoning about, propositions qualified in terms of time. It is sometimes also used to refer to tense logic, a particular modal logic-based system of temporal logic introduced by Arthur Prior in the 1960s. Subsequently it has been developed further by computer scientists, notably Amir Pnueli, and logicians.

Temporal logic was first studied in depth by Aristotle, whose writings are filled with a crude form of first order temporal modal binary logic. Any logic which uses the existential quantifier or the universal quantifier is said to be a first order logic. Any logic which views time as a sequence of states is a temporal logic, and any logic which uses only two truth values is a binary logic.

Consider the statement: "I am hungry." Though its meaning is constant in time, the truth value of the statement can vary in time. Sometimes the statement is true, and sometimes the statement is false, but the statement is never true and false simultaneously. In a temporal logic, statements can have a truth value which can vary in time. Contrast this with an atemporal logic, which can only handle statements whose truth value is constant in time.

1 Temporal operators
2 Temporal logics
3 See also
4 External link

[edit]

Temporal operators

Temporal logic has two kinds of operators: logical operators and modal operators [1]. Logical operators are usual truth-functional operators (<math>\neg,\or,\and,\rightarrow</math>) and odal operators used in temporal logic are defined as follows:

Textual	Symbolic	Definition	Explanation	Diagram
Binary operators
<math>\phi</math> U <math>\psi</math>	<math>\phi ~\mathcal{U}~ \psi</math>	<math>\begin{matrix}(B\mathcal{U}C)(\phi)= \\ (\exists i:C(\phi_i))\land(\forall j<i:B(\phi_j))\end{matrix}</math>	Until: <math>\psi</math> holds at the current or a future position, and <math>\phi</math> has to hold until that position. At that position <math>\phi</math> does not have to hold any more.	<timeline> ImageSize = width:240 height:94 PlotArea = left:30 bottom:30 top:0 right:20 DateFormat = x.y Period = from:0 till:6 TimeAxis = orientation:horizontal AlignBars = justify ScaleMajor = gridcolor:black increment:1 start:0 ScaleMinor = gridcolor:black increment:1 start:0 PlotData= bar:p color:red width:10 align:left fontsize:S from:1 till:3 bar:q color:red width:10 align:left fontsize:S from:3 till:5 bar:pUq color:red width:10 align:left fontsize:S from:1 till:5 </timeline>
<math>\phi</math> R <math>\psi</math>	<math>\phi ~\mathcal{R}~ \psi</math>	<math>\begin{matrix}(B\mathcal{R}C)(\phi)= \\ (\forall i:C(\phi_i))\lor(\exists j<i:B(\phi_j))\end{matrix}</math>	Release: <math>\phi</math> releases <math>\psi</math> if <math>\psi</math> is true until the first position in which <math>\phi</math> is true (or forever if such a position does not exist).	<timeline> ImageSize = width:240 height:100 PlotArea = left:30 bottom:30 top:0 right:20 DateFormat = x.y Period = from:0 till:6 TimeAxis = orientation:horizontal AlignBars = justify ScaleMajor = gridcolor:black increment:1 start:0 ScaleMinor = gridcolor:black increment:1 start:0 PlotData= bar:p color:red width:10 align:left fontsize:S from:2 till:4 bar:q color:red width:10 align:left fontsize:S from:1 till:3 from:5 till:6 bar:pRq color:red width:10 align:left fontsize:S from:1 till:3 from:5 till:6 </timeline>
Unary operators
N <math>\phi</math>	<math>\circ \phi</math>	<math>\mathcal{N}B(\phi_i)=B(\phi_{i+1})</math>	Next: <math>\phi</math> has to hold at the next state. (X is used synonymously.)	<timeline> ImageSize = width:240 height:60 PlotArea = left:30 bottom:30 top:0 right:20 DateFormat = x.y Period = from:0 till:6 TimeAxis = orientation:horizontal AlignBars = justify ScaleMajor = gridcolor:black increment:1 start:0 ScaleMinor = gridcolor:black increment:1 start:0 PlotData= bar:p color:red width:10 align:left fontsize:S from:2 till:3 from:5 till:6 bar:Np color:red width:10 align:left fontsize:S from:1 till:2 from:4 till:5 </timeline>
F <math>\phi</math>	<math>\Diamond \phi</math>	<math>\mathcal{F}B(\phi)=(true\mathcal{U}B)(\phi)</math>	Finally: <math>\phi</math> eventually has to hold (somewhere on the subsequent path).	<timeline> ImageSize = width:240 height:60 PlotArea = left:30 bottom:30 top:0 right:20 DateFormat = x.y Period = from:0 till:6 TimeAxis = orientation:horizontal AlignBars = justify ScaleMajor = gridcolor:black increment:1 start:0 ScaleMinor = gridcolor:black increment:1 start:0 PlotData= bar:p color:red width:10 align:left fontsize:S from:2 till:3 from:4 till:5 bar:Fp color:red width:10 align:left fontsize:S from:0 till:5 </timeline>
G <math>\phi</math>	<math>\Box \phi</math>	<math>\mathcal{G}B(\phi)=\neg\mathcal{F}\neg B(\phi)</math>	Globally: <math>\phi</math> has to hold on the entire subsequent path.	<timeline> ImageSize = width:240 height:60 PlotArea = left:30 bottom:30 top:0 right:20 DateFormat = x.y Period = from:0 till:6 TimeAxis = orientation:horizontal AlignBars = justify ScaleMajor = gridcolor:black increment:1 start:0 ScaleMinor = gridcolor:black increment:1 start:0 PlotData= bar:p color:red width:10 align:left fontsize:S from:1 till:3 from:4 till:6 bar:Gp color:red width:10 align:left fontsize:S from:4 till:6 </timeline>
A <math>\phi</math>		<math>\begin{matrix}(\mathcal{A}B)(\psi)= \\ (\forall \phi:\phi_0=\psi\to B(\phi))\end{matrix}</math>	All: <math>\phi</math> has to hold on all paths starting from the current state.
E <math>\phi</math>		<math>\begin{matrix}(\mathcal{E}B)(\psi)= \\ (\exists \phi:\phi_0=\psi\land B(\phi))\end{matrix}</math>	Exists: there exists at least one path starting from the current state where <math>\phi</math> holds.

Note: <math>\phi</math> denotes a path and <math>\psi</math> denotes a state.

Alternate symbols:

operator N is sometimes noted X
operator R is sometimes noted V or W

Unary opearators are well-formed formulas whenever B(<math>\phi</math>) is well-formed. Binary operators are well-formed formulas whenever B(<math>\phi</math>) and C(<math>\phi</math>) are well-formed.

In some logics, some operators cannot be expressed. For example, N operator cannot be expressed in Temporal Logic of Actions.

[edit]