formalmethods.dev

§ 1.3

Linear temporal logic

A tiny language for talking about time — the backbone of this lab.

see also · Specification as the test oracle · Runtime verification · Model checking

X p — next step
pos
01234
G p — every step
pos
01234
F p — some later step
pos
01234
p U q — p until q
pos
01234
● p  ● q — read left to right, from position 0

The grammar

LTL adds temporal operators to ordinary propositional logic. Formulas are evaluated along a run, one state at a time, from the first state onward.

  • X p — next: p holds in the state that follows.
  • F p — finally: p holds somewhere later (<>).
  • G p — globally: p holds at every step ([]).
  • p U q — until: p holds until q occurs, which it eventually does.
  • p W q — weak until: drops the eventual obligation; q R p is its dual.

Two semantics, one grammar

Over an infinite run — the textbook reading — G and F quantify over an endless future. The model checker uses this one.

Over a finite trace — a test case, a log — F p only promises p within what you saw, and X p is false at the last step. That reading is LTLf, the right one for logs and concrete tests.

This lab is bilingual: lab B checks infinite runs, labs A and C check finite traces. Know which language you are speaking before you compare answers.

try it · see every operator in the truth table — lab A →