canplane   3년 전

그리 깊게 생각한 내용은 아니지만 기록을 할 수 있으면 하는 게 좋겠다 싶어 남기고 갑니다.



F => T, F => F는 모두 참인데 반해, T => T는 참이지만 T => F는 거짓이므로

뒤따르는 변수가 참이 아니게 되어 모순을 도출하는 것을 피하기 위해, 위상 정렬 후 임의 변수를 뽑을 때 있어 그에 대한 negation 변수의 state가 아직 정해지지 않은 상태라면 그리디하게 F로 잡고, 이미 정해진 상태라면 T로 잡는다.


이렇게 하면, T => x => ... => F 즉 T => F로 귀결되는 경로가 없는지를 보장할 수 있는가?

일단 값을 뽑는다는 것은 satisfiability를 보장함을 뜻하므로 x => ~x이면서 ~x => x인 경로는 존재할 수 없다.

따라서 이러한 경로가 존재한다면, 그것은 서로 다른 변수가 작용하는 것이다.


어떤 변수 x1, x2에 대하여 관계가 x1, ..., ~x1, ... ,  x2 순서로 이어져 있고, x1, ~x1, x2의 state를 각각 F, T, F라 가정하자.

~x1, x2가 위 순서로 이어져 있음은 ~x1 => x2을 뜻하고, 이는 x1 V x2  ≡  x2 V x1  ≡  ~x2 => x1 역시 존재함을 뜻한다.

그렇다면 x1 이전에 ~x2가 존재해야 하고, 즉 x2 이전에 ~x2를 방문하는 것이 먼저이므로 ~x2의 state는 F가 되어야 한다.

이는 x2가 F라 가정한 데 대하여 모순이다.


즉, 각 변수를 가능한 한 F로 세팅하려 한다면 T => F를 도출하는 경로는 존재할 수 없으며, 오직 F => F, F => T, T => T 세 종류의 관계만 존재한다.

댓글을 작성하려면 로그인해야 합니다.