2-SAT (1) 썸네일형 리스트형 133. 2-SAT 충족 가능성 문제(SAT, Satisfiability Problem)는 Boolean 변수들(True 또는 False 중 한 가지 값을 가질 수 있음)로 이루어진 식의 값이 True가 되게 하는 변수들의 값 조합이 존재하는지를 알아내는 문제이다. 이러한 식은 불 연산식(Boolean Expression)이라고 부르며 다음과 같은 두 가지의 형태로 나타낼 수 있다. 식에서 $\neg$, $\wedge$, $\vee$ 기호는 각각 NOT, AND, OR 연산자와 같은 의미를 가지며 $\neg$ 연산자의 우선순위가 가장 높다. CNF(Conjunctive Normal Form): $f = (x_1 \vee x_2) \wedge (\neg x_3 \vee x_1 \vee x_4) \wedge (\neg x_2 .. 이전 1 다음
