General query regarding Problem 7 of Exams

Question

Hi,

Consider the following example,

In the above question in s0, S2 is satisfied whereas in s1 none of S2 or S1 is satisfied. When we are asked to write a path which satisfies either of the formulas does it mean that it should hold in all paths of the states? or in some of the states?

Comments

Adding to the existing reply: In this case, we have two formulas quantified with E. That means that we need such a path (starting from an initial state) that satisfies the properties of one formula but not of the other formula. The path starting from s0 does so, the (sub)path starting from s1 doesn't.

Answer 1

This kind of questions ask for differences in formulas, i.e., whether the formulas are equivalent or not. Two state formulas as the ones considered above are equivalent if their truth value is the same for EVERY state and EVERY transition system.

Hence, two formulas are not equivalent if you find ONE transition system where the two formulas have different truth values in at least ONE state.