논리곱 표준형

명제 논리에서, 논리곱 표준형(論理곱標準型, 영어: conjunctive normal form, CNF)은 명제 기호 또는 그 부정들의 논리합들을 논리곱으로 연결한 명제식이다. 명제 논리의 모든 명제식은 어떤 논리곱 표준형과 논리적으로 동치이다.

그 쌍대 개념인 논리합 표준형(論理합標準型, 영어: disjunctive normal form, DNF)은 명제 기호 또는 그 부정들의 논리곱들을 논리합으로 연결한 명제식이다. 명제 논리의 모든 명제식은 어떤 논리합 표준형과 논리적으로 동치이다.

주어진 명제식과 동치인 논리곱·논리합 표준형은 이중 부정의 소거, 드 모르간의 법칙, 분배 법칙 등을 사용하여 구할 수 있다.

3-논리곱 표준형(영어: 3-conjunctive normal form, 3-CNF)은 3개 이하의 명제 기호 또는 그 부정들의 논리합들의 논리곱인 명제식이다. 이는 계산 이론에서 중요하게 다루어진다. 다른 개수로 제한할 때도 마찬가지로 정의할 수 있으나 2-CNF, 3-CNF 이외에는 중요하게 다루지 않는다.

정의

명제 논리의 논리곱 표준형은 다음과 같은 꼴의 명제식이다.

$(\phi _{11}\lor \cdots \lor \phi _{1n_{1}})\land \cdots \land (\phi _{m1}\lor \cdots \lor \phi _{mn_{m}})$

여기서, 각 $\phi _{ij}$는 어떤 명제 기호

${\mathsf {p}}_{n_{ij}}$

이거나 어떤 명제 기호의 부정

$\lnot {\mathsf {p}}_{n_{ij}}$

이다.

명제 논리의 논리합 표준형은 다음과 같은 꼴의 명제식이다.

$(\phi _{11}\land \cdots \land \phi _{1n_{1}})\lor \cdots \lor (\phi _{m1}\land \cdots \land \phi _{mn_{m}})$

여기서, 각 $\phi _{ij}$는 어떤 명제 기호

${\mathsf {p}}_{n_{ij}}$

이거나 어떤 명제 기호의 부정

$\lnot {\mathsf {p}}_{n_{ij}}$

이다.

성질

명제 논리의 모든 명제식은 어떤 논리곱 표준형 및 어떤 논리합 표준형과 논리적으로 동치이다. 즉, 명제 논리의 명제식 $\phi$에 대하여,

$\phi \models \phi ^{\land }$

$\phi ^{\land }\models \phi$

인 논리곱 표준형 $\phi ^{\land }$가 존재하며, 마찬가지로

$\phi \models \phi ^{\lor }$

$\phi ^{\lor }\models \phi$

인 논리합 표준형 $\phi ^{\lor }$가 존재한다.

주어진 명제식 $\phi$와 동치인 논리곱 표준형과 논리합 표준형은 다음과 같이 재귀적으로 구할 수 있다. 만약 $\phi$가 어떤 명제 기호 ${\mathsf {p}}_{n}$인 경우, 이는 이미 논리곱 표준형이자 논리합 표준형이다. 만약 $\phi$가 다른 명제식의 부정

$\lnot \psi$

인 경우, $\psi$와 동치인 논리곱 표준형

$(\phi _{11}\lor \cdots \lor \phi _{1n_{1}})\land \cdots \land (\phi _{m1}\lor \cdots \lor \phi _{mn_{m}})$

을 잡자. 그렇다면 $\lnot \psi$는 논리합 표준형

$(\phi _{11}^{*}\land \cdots \land \phi _{1n_{1}}^{*})\lor \cdots \lor (\phi _{m1}^{*}\land \cdots \land \phi _{mn_{m}}^{*})$

과 동치이다. 여기서, 명제 기호 ${\mathsf {p}}_{n}$에 대하여 $({\mathsf {p}}_{n})^{*}$는 $\lnot {\mathsf {p}}_{n}$이며 $(\lnot {\mathsf {p}}_{n})^{*}$는 ${\mathsf {p}}_{n}$이다. 마찬가지로, $\psi$와 동치인 논리합 표준형

$(\psi _{11}\land \cdots \land \psi _{1q_{1}})\lor \cdots \lor (\psi _{p1}\land \cdots \land \psi _{pq_{p}})$

을 잡자. 그렇다면 $\lnot \psi$는 논리곱 표준형

$(\psi _{11}^{*}\lor \cdots \lor \psi _{1q_{1}}^{*})\land \cdots \land (\psi _{p1}^{*}\lor \cdots \lor \psi _{pq_{p}}^{*})$

와 동치이다. 만약 $\phi$가 함의

$\psi \implies \chi$

인 경우, 이는 명제식 $\lnot \psi \lor \chi$와 동치이다.

$\phi _{1}\lor \cdots \lor \phi _{m}$

$\psi _{1}\lor \cdots \lor \psi _{n}$

가 각각 $\lnot \psi$ 및 $\chi$와 동치인 논리합 표준형이라고 하자. 그렇다면 $\lnot \psi \lor \chi$는 논리합 표준형

$\phi _{1}\lor \cdots \lor \phi _{m}\lor \psi _{1}\lor \cdots \lor \psi _{n}$

과 동치이다. 이제,

$\theta _{1}\land \cdots \land \theta _{m}$

$\eta _{1}\land \cdots \land \eta _{n}$

가 각각 $\lnot \psi$ 및 $\chi$와 동치인 논리곱 표준형이라고 하자. 그렇다면 $\lnot \psi \lor \chi$는 논리곱 표준형

$(\theta _{1}\lor \eta _{1})\land (\theta _{1}\lor \eta _{2})\land \cdots \land (\theta _{m}\lor \eta _{n})$

과 동치이다.

외부 링크

• Weisstein, Eric Wolfgang. “Conjunctive normal form” (영어). 《Wolfram MathWorld》. Wolfram Research. 
• Weisstein, Eric Wolfgang. “Disjunctive normal form” (영어). 《Wolfram MathWorld》. Wolfram Research. 

같이 보기

• 콰인-매클러스키 알고리즘