m doing a practise quiz which my professor has posted online, one of the questions im very confused about was this one.

   Consider the clauses {x,y} , {~x,y} , {~y,z} , {~z,w} , {~w,~y}
is this true or false?

The implication graph contains the following bad loop:
x -> y -> z -> w -> ~y -> x

I said that this statement was false , however it came out that its true, can someone explain to me why this is the case?

Because i thought a bad loop would be a transition between a letter to the negation of its own then back to the original for example x -> ~x -> x

  • $\begingroup$ In this loop you have a path $x\rightsquigarrow y \rightsquigarrow \bar{y} \rightsquigarrow x$. So if you start from $y$, you can reach $\bar{y}$ and return to $y$, by following the path $y \rightsquigarrow \bar{y} \rightsquigarrow x \rightsquigarrow y$. $\endgroup$ – Ariel Dec 13 '15 at 19:54
  • $\begingroup$ How does that prove the implication graph containing x -> y -> z -> w -> ~y -> x has a bad loop? $\endgroup$ – Mr_Shoryuken Dec 13 '15 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.