====== CNF ======

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

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

{{tag>전산학}}