논리곱 표준형

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

불 대수에서 논리곱 표준형(conjunctive normal form)은 논리곱으로 나타낸 논리식을 말한다. 여기서 절은 리터럴논리합으로 이루어진다. 논리곱 표준형의 영문 표기를 줄여서 CNF라고도 한다.

CNF와 반대로 리터럴의 논리곱으로 이루어진 절들을 논리합으로 연결할 수도 있다. 이를 논리합 표준형이라고 한다.

모든 명제 논리식은 동등한 CNF로 변환될 수 있다. 이 변환은 이중부정 법칙, 드모르간 법칙, 분배 법칙 등을 써서 이루어진다.

리터럴의 개수가 3개 이하로 제한된 CNF를 3-CNF라고 하며 계산 이론에서 중요하게 다루어진다. 다른 개수로 제한할 때도 마찬가지로 정의할 수 있으나 2-CNF, 3-CNF 이외에는 중요하게 다루지 않는다.