11281번 - 2-SAT - 4
그리 깊게 생각한 내용은 아니지만 기록을 할 수 있으면 하는 게 좋겠다 싶어 남기고 갑니다.
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 세 종류의 관계만 존재한다.
댓글을 작성하려면 로그인해야 합니다.
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 세 종류의 관계만 존재한다.