Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/computer-aided-formal-verification/3/b/solution

Let . By computation tree logic semantics, a state belongs to exactly when every infinite path in a transition system starting there stays in at every position, including position zero. There are no terminal states, so every state lies at the start of an infinite path in a transition system.
If , then . For any successor of , every infinite path in a transition system from can be prefixed with . Hence every such continuation stays in , so . Thus and .
Conversely, if , then and every successor belongs to . Every infinite path in a transition system from therefore has its first state in and its entire remaining tail in . Consequently . Both inclusions give
so the desired satisfaction set is a fixed point of .

New to topics? Read the docs here!