Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

557 users

0 votes

Hello everyone, 
I would like to ask you something regarding question 1 in exercise sheet 8.

This is the two formulas that I got:
S= [[b SU a] WU c]
S2 = [[b SU a] SU c]

As far as I understood, I need to find two formulas which satisfy S1 and do not satisfy Sor vice-versa.
In order to find G formula and check my solution I made sure to use these two quantifications:

(a&!b&!c) -> [[b SU a] WU c]      valid

(a&!b&!c) -> [[b SU a] SU c]     not valid
When I enter this formula in the solution my G formula is accepted as correct. As far as for F formula I used this relationship:

!G(ø) = F!(ø)

So I did this transformation (I used simplify equation in LTL tool):

(a&!b&!c) -> [[b SU a] WU c]
!(G (a&!b&!c)) | [[b SU a] WU c]
!G !c&a&!b | [[b SU a] WU c]
F !(
!c&a&!b) | [[b SU a] WU c]

After the check:

F !(!c&a&!b) | [[b SU a] WU c]   - valid
F !(!c&a&!b) | [[b SU a] SU c]    - not valid

But after I plug in the solution in the form:
1 ; G (a&!b&!c) ; F 
!(!c&a&!b)
I get that one of the formulas is not correct. Could you advise me how to proceed.

Thank you.

in * TF "Emb. Sys. and Rob." by (140 points)
Note that the two formulas do not have to start with G or F, these formulas were just used to explain the expected syntax of the answer.

The construction of your second formula is pointless. You just rewrite the first formula, but you need to find one that is different somewhere but still meets the given requirements.

1 Answer

0 votes

See the answer to https://q2a.cs.uni-kl.de/1051/sheet-8-exercise-1 for a general discussion about what is needed for the solution. 

In your case, you have S1 = [[b SU a] WU c] and S2 = [[b SU a] SU c] and it is therefore clear that S2->S1 is valid (since SU implies WU). Hence, we have to find two nontrivial counterexamples for S1->S2, i.e., two formulas phi1 and phi2 such that the following are valid

phi1 -> [[b SU a] WU c] & ![[b SU a] SU c]
phi2 -> [[b SU a] WU c] & ![[b SU a] SU c]

Looking at the counterexample generated by the tool, you can see that phi1 := G(a&!b&!c) is such a formula. Your second formula is not correct since trying to prove 

(F !(!c&a&!b)) -> [[b SU a] WU c] & ![[b SU a] SU c]

yields as a counterexample a path where a, b, and c are always false.

Find a second one that meets the above requirements. It may not necessarily be a formula starting with G or F, this is nowhere mentioned.

To give a few further hints, consider your formulas S1 = [[b SU a] WU c] and S2 = [[b SU a] SU c]. If eventually c holds, both formulas are equivalent, i.e., 

    (F c) -> ([[b SU a] WU c] <-> [[b SU a] SU c])

is valid. So, all counterexamples must imply G!c. However, that is not enough since if just G!c would hold, then both formulas S1 and S2 are simply false. Now note that if c is never true, [[b SU a] WU c] will become equivalent to G[b SU a] which implies that infinitely often "a" must hold. From here, you may guess another candidate formula.

by (170k points)
edited by

Related questions

Imprint | Privacy Policy
...