[414] 2-SAT 문제(개념만, 코드 없음)

이미지 출처: 나무위키

1. SAT(충족 가능성 문제)

다음과 같은 논리식이 있다고 하면(∧는 and 연산입니다.),

논리식 = 변수1 ∧ 변수2 ∧ 변수3

변수1, 2, 3이 어떤 값을 가지냐에 따라 논리식은 참이 될 수도 있지만, 다음과 같은 논리식에서는

논리식 = 변수1 ∧ not 변수1

만약 변수1이 참이면 not 변수1은 거짓이 되기 때문에 위 논리식은 절대 참이 될 수 없습니다.

 

이렇게 참/거짓을 가지는 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지 찾는 문제를 충족 가능성 문제(SAT)라고 부릅니다.

https://ko.wikipedia.org/wiki/충족_가능성_문제

충족 가능성 문제 - 위키백과, 우리 모두의 백과사전

 

2. 2-SAT

위의 SAT를 잘 보면 논리식에서 논리곱으로 연산되는 피연산자는 모두 참이 되어야만 논리식이 참이 될 수 있다는 것을 알 수 있습니다.

논리식에서 논리곱의 피연산자들을 절(clause)라고 부르고, 이 절은 논리합으로 여러 개의 변수를 가질 수 있습니다.

여러 절이 논리곱 연산만으로 묶여 있는 논리식을 논리곱 표준형(CNF; Conjunctive Normal Foam)이라고 부릅니다.

논리식 = (변수1 ∨ 변수2) ∧ (not 변수2 ∨ 변수3)

이 논리식은 각 절에는 변수가 두 개씩 들어가있습니다.

이렇게 각 절에 변수가 두 개씩 들어가있는 논리식이 참이 되는 변수값이 있는지를 찾는 문제(SAT)를 2-SAT라고 합니다.

 

만약 각 절에 변수가 한 개씩만 들어가 있을 때 논리식이 참이 될 수 없는 경우는, 어떤 변수와 그 변수의 부정변수(예를 들면 변수1과 not 변수1)가 같이 들어가있는 경우입니다.

논리식 = 변수1 ∧ not 변수2 ∧ 변수3

(어떤 변수가 자신의 부정변수와 함께 포함되어 있지 않기 때문에 위 논리식은 참이 될 수 있습니다.)

논리식 = 변수1 ∧ 변수2 ∧ not 변수1

(변수1이 자신의 부정변수인 not 변수1과 논리곱으로 연산되기 때문에, 변수1이 어떤 값을 가지더라도 논리식은 참이 될 수 없습니다.)

 

그러나 절에 변수를 두 개씩 갖는 2-SAT는 논리식이 참이 될 수 있는지 확인하려면 보다 복잡한 과정을 거치게 됩니다.

논리식 = (변수1 ∨ 변수2) ∧ (not 변수2 ∨ 변수3)

위 논리식은 절마다 변수가 두 개이기 때문에, 각 절이 모두 참이 될 수 있는지 살펴보아야 합니다.

(변수1 ∨ 변수2)

변수1과 변수2의 값에 따라 결과는 다음과 같습니다.

변수1	변수2	변수1 ∨ 변수2
참	참	참
참	거짓	참
거짓	참	참
거짓	거짓	거짓

 

결과가 참이 되는 경우를 살펴보면, 변수1이 참이 되면 변수2는 참, 거짓이 둘 다 되도 상관 없습니다.

그리고 변수2가 참이 되어도 변수1은 참, 거짓이 둘다 되어도 상관 없습니다.

하지만, 변수1이 거짓일 경우 결과가 참이 되는 경우는 변수2가 참이 되는 경우 밖에 없으며, 변수2가 거짓일 경우 결과가 참이 되는 경우는 변수1이 참인 경우 밖에 없습니다.

따라서 논리식이 참이 되려면, 변수1이 거짓이라면 변수2는 참이어야하고, 변수2가 거짓이라면 변수1은 참이어야 합니다.

그래프로 나타내면,

이렇게 나타낼 수 있습니다.

 

이에 따라

논리식 = (변수1 ∨ 변수2) ∧ (not 변수2 ∨ 변수3)

위 논리식을 그래프로 나타내면

이렇게 나타낼 수 있습니다.

 

그렇다면 이제 논리식이 참이 될 수 있는지 없는지(2-SAT 문제) 어떻게 알 수 있을까요?

바로 그래프 상에 사이클이 생기는 부분에서 알 수 있습니다.

논리식 = (변수1 ∨ 변수2) ∧ (not 변수2 ∨ 변수3) ∧ (not 변수1 ∨ not 변수3)

위 논리식을 위의 과정을 거쳐 그래프로 그리면 다음과 같습니다.

이전 그래프와 다르게 사이클이 생겼습니다.

사이클이 중요한 이유는 명제의 모순을 통해 2-SAT 논리식이 참이 될 수 없음을 증명할 수 있기 때문입니다.

변수 p, q, r이 사이클인 경우 p이면 q이고, q이면 r이고, r이면 p이기 때문에 p, q, r 중에 하나라도 참이면 나머지는 모두 참이어야 하고, 하나라도 거짓이면 모두 거짓이어야 합니다.

즉, 사이클의 변수는 모두 같은 값이어야 합니다.

결론적으로 사이클 안에 어떤 변수와 그 변수의 부정변수가 같이 들어있다면 모순이 되면서 논리식이 참이 될 수 없다는 것을 알 수 있습니다.

 

정리하자면 2-SAT 문제는 그래프로 변환되고, 그래프에서 사이클(강한 연결 요소)을 확인하는 타잔의 scc알고리즘을 통해 다항 시간 내에 풀 수 있습니다.

참고로 3-SAT 이상의 문제는 모두 다항 시간 내에 3-SAT 꼴로 나타낼 수 있으며, 3-SAT 문제는 NP-완전 문제라고 합니다.

 

https://en.wikipedia.org/wiki/2-satisfiability

2-satisfiability - Wikipedia