논리곱 표준형

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

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

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

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

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

여기서, 각 는 어떤 명제 기호

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

이다.

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

여기서, 각 는 어떤 명제 기호

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

이다.

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

인 논리곱 표준형 가 존재하며, 마찬가지로

인 논리합 표준형 가 존재한다.

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

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

을 잡자. 그렇다면 는 논리합 표준형

과 동치이다. 여기서, 명제 기호 에 대하여 는 이며 는 이다. 마찬가지로, 와 동치인 논리합 표준형

을 잡자. 그렇다면 는 논리곱 표준형

와 동치이다. 만약 가 함의

인 경우, 이는 명제식 와 동치이다.

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

과 동치이다. 이제,

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

과 동치이다.

 참고 문헌 

 외부 링크 



 같이 보기 
 콰인-매클러스키 알고리즘

분류:논리학
분류:불 대수