이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
cnf [2010-04-22 03:40] lifthrasiir 새로 만듦 |
cnf [2011-05-30 18:25] (현재) |
||
---|---|---|---|
줄 3: | 줄 3: | ||
Conjunctive normal form. [[명제논리]]의 논리식 중 모양이 $$(a \vee b \vee \cdots) \wedge (c \vee \cdots) \wedge \cdots$$ 꼴인 것으로 ($$a$$ 따위는 변수거나 변수에 $$\neg$$가 붙은 것일 수 있다) 모든 0차 논리식은 항상 이 형태로 변환할 수 있다. | Conjunctive normal form. [[명제논리]]의 논리식 중 모양이 $$(a \vee b \vee \cdots) \wedge (c \vee \cdots) \wedge \cdots$$ 꼴인 것으로 ($$a$$ 따위는 변수거나 변수에 $$\neg$$가 붙은 것일 수 있다) 모든 0차 논리식은 항상 이 형태로 변환할 수 있다. | ||
- | 다루기 편하기 때문에 [[SAT]] 같은 데서 입력이 CNF로 되어 있다고 가정하고 쓰는 경우가 많다. 반대 형태인 [[DNF]]도 쓰지만 CNF만큼 많이 쓰지는 않는다. (아무래도 [[분해법]]이 CNF에서만 통해서 그런 건지...) | + | 다루기 편하기 때문에 [[SAT]] 같은 데서 입력이 CNF로 되어 있다고 가정하고 쓰는 경우가 많다. 반대 형태인 [[DNF]]도 쓰지만 CNF만큼 많이 쓰지는 않는다. (아무래도 [[분해법]][resolution]이 CNF에서만 통해서 그런 건지...) |
+ | {{tag>전산학}} |