Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

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 \..

티스토리툴바