이것은 문서의 이전 버전입니다!


CNF

Conjunctive normal form. 명제 논리의 논리식 중 모양이 (a \vee b \vee \cdots) \wedge (c \vee \cdots) \wedge \cdots 꼴인 것으로 (a 따위는 변수거나 변수에 \neg가 붙은 것일 수 있다) 모든 0차 논리식은 항상 이 형태로 변환할 수 있다.

다루기 편하기 때문에 SAT 같은 데서 입력이 CNF로 되어 있다고 가정하고 쓰는 경우가 많다. 반대 형태인 DNF도 쓰지만 CNF만큼 많이 쓰지는 않는다. (아무래도 분해법이 CNF에서만 통해서 그런 건지…)


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기