부정 정규 형식

수학 논리학에서 부정 연산자( (${\displaystyle \lnot$ $\},)$인 경우 공식은 부정 정규 형식(NNF)이다.not)은 변수에만 적용되며, 허용된 다른 부울 연산자는 접속사( (${\displaystyle \land }$및)와 분리${\displaystyle }$ ${\displaystyle \lor}$ , 또는$)$뿐이다.

부정 정규 형식은 표준 형식이 아니다. 예를 들어, ${\displaystyle \wedge }$(${\displaystyle b}$c${\displaystyle \mathrm{}c}$c )$${\$displaystyle$a\$land (b\lor \lnot$ c$)}$과${\displaystyle }$(${\displaystyle }$(${\displaystyle }$b )${\displaystyle (}$ ($land$∨ ($land$b$)\lor$ ($a\land \lnot c)}$은 동등하며$$, 둘 다 부정 정규 형식이다.

고전적 논리와 많은 모달 로직에서, 모든 공식은 그 정의에 의해 함축과 등가성을 대체하고, 드 모건의 법칙을 사용하여 부정의 내부를 밀어내고, 이중 부정의 존재를 제거함으로써 이 형태로 가져올 수 있다.이 프로세스는 다음과 같은 재작성 규칙을 사용하여 나타낼 수 있다(자동화된 추론 1, 페이지 204).

${\displaystyle {\reasoned}A\Rightarrow B&~\to ~\lnot A\lor B\\\lnot (A\lor B)&~\to ~\lnot A\land \lnot B\\\lnot (A\land B)&~\to ~\lnot A\lor \lnot B\\\lnot \lnot A&~\to ~A\\\lnot \exists xA&~\to ~\forall x\lnot A\\\lnot \forall xA&~\to ~\exists x\lnot A\end{aligned}}}$

[이 규칙에서 $\Rightarrow {\displaystyle }$ ${\displaystyle \Rightarrow }$ 기호는$$ 다시 작성되는 수식에 대한 논리적 함의를 나타내며${\displaystyle }$→ ${\displaystyle \to }$은(는) 다시 쓰기 작업이다.]

부정 정규 형식으로의 변환은 공식의 크기를 선형적으로만 늘릴 수 있다: 원자 공식의 발생 횟수는 그대로 유지되며, $\wedge {\displaystyle }$ ${\displaystyle \land}$과${\displaystyle }$and$$ ${\displaystyle \lor}$의 총 발생 횟수는 변경되지 않으며$$, $\neg {\displaystyle \mathrm{}}$ ${\displaystyle \lnot }$의 발생 횟수는 두 배가될 수 있다$$.

부정 정상 형태의 공식은 분배율을 적용하여 더 강한 결합 정상 형태 또는 분리 정상 형태에 넣을 수 있다.분배성의 반복적인 적용은 공식의 크기를 기하급수적으로 증가시킬 수 있다.고전적인 명제 논리학에서, 부정 정상 형태로의 변환은 계산 속성에 영향을 미치지 않는다: 만족도 문제는 계속 NP-완전이며, 유효성 문제는 계속 공동 NP-완전이다.CNF 공식의 경우 유효성 문제는 다항식 시간에 해결할 수 있고, DNF 공식의 경우 만족도 문제는 다항식 시간에 해결할 수 있다.

예제 및 counterexample

다음의 공식은 모두 부정 정상형이다.

$\displaystyle {\begin{ligned}(A&\ve B)\wedge C\\(A&\bee C)\wedge \ve D\\\a&\vee \lnot B\\\\\\\)A&\wedge \lnot B\end{aigned}}$

첫 번째 예도 역시 결막 정상형이고 마지막 두 번째 예도 결막 정상형과 절연 정상형이지만 두 번째 예도 둘 다 아니다.

다음 공식은 부정 정상 형식이 아니다.

${\displaystyle {\reasoned}A&\\Rightarrow B\\lnot (A&\ve B)\\lnot (A&\wedge B)\\lnot (A&\vee \lnot C)\ended}}}}$

그러나 이 공식은 정규식을 부정하는 다음 공식과 각각과 동일하다.

$#\displaystyle {\begin}\lnot A&\vee B\\\lnot A&\lnot A&\lnt A&\lnt C\ended}}}$

참조

• 앨런 J.A.로빈슨과 안드레이 보론코프, 자동 추론 핸드북1:203ff (2001) ISBN0444829490.

외부 링크

• 논리 공식을 Negination Normal Form로 변환하여 사용된 법률을 표시하는 Java 애플릿