이절정규격

이 글에는 여러 가지 문제가 있다.이 문제를 개선하거나 대화 페이지에서 토의하십시오.(이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "해당 정규 형식" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2010년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 학습) 이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오.(2010년 11월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

부울 논리학에서, 이격 정상 형태(DNF)는 접속사 분리로 구성된 논리 공식의 표준적인 정상 형태로서, AND의 OR, 제품의 합계 또는 (철학적 논리학에서) 클러스터 개념으로도 설명할 수 있다.^{[citation needed]}정상적인 형태로서 자동화된 정리증명에 유용하다.

정의

논리 공식은 하나 이상의 리터럴 접속사를 분리하는 경우 DNF에 있는 것으로 간주된다.^{[1]: 153} DNF 공식은 각각의 변수가 매 접속사마다 정확히 한 번씩 나타나는 경우 완전 분리 정규 형식이다.접속 정상 형태(CNF)와 마찬가지로, DNF의 유일한 제안 연산자는 및 $({\displaystyle \wedge }$${\displaystyle }$})$$이며, $({\displaystyle \ve$} )가 아니다$({\$displaystyle \neg }).연산자가 아닌 연산자는 단지 리터럴의 일부로서만 사용할 수 있으며, 이는 명제 변수 앞에만 이를 수 있다는 것을 의미한다.

다음은 DNF를 위한 문맥 없는 문법이다.

1. DNF → (Conjection)${\displaystyle }$) ${\displaystyle \ve }$DNF$$
2. DNF → (연결)
3. 접속사 → 리터럴 $\wedge {\displaystyle }$ ${\displaystyle \wedge }$ 접속사$$
4. 접속사 → 리터럴
5. 리터럴 → $\neg {\displaystyle \mathrm{}}$ ${\displaystyle \neg }$ 변수$$
6. 리터럴 → 가변

여기서 변수는 변수다.

예를 들어, 다음의 모든 공식은 DNF에 있다.

• $#\displaystyle(A\land \ng B\land \ng C)\lor(\ng D\land E\land F)}$
• $(A\playstyle (A\land B)\lor (C)}$
• $(A\displaystyle (A\land B)}$
• $(\displaystyle (A)}$

그러나 다음 공식은 DNF에 없다.

• ${\displaystyle \mathrm{or}}$(${\displaystyle A}$ within B ) $displaystyle \neg(A\lor$ B$)},$OR이 NOT 내에 중첩되기 때문에
• ${\displaystyle }$AND가 NOT 내에 중첩되기 때문에${\displaystyle }$(${\displaystyle A}$ ${\displaystyle \wedge }$ B${\displaystyle }$) ${\displaystyle \vee }$ ${\displaystyle C}$ ${\displaystyle \neg(A\land$ B$)\lor C$
• ${\displaystyle }$OR이 AND 내에 중첩되기 때문에 ${\displaystyle A}$ ${\displaystyle \vee }$(${\displaystyle B}$ ${\displaystyle \wedge }$ ${\displaystyle (C}$ ${\displaystyle \vee }$ ${\displaystyle D}$)${\displaystyle A\lor (B\land (C\lor D$

The formula ${\displaystyle A\lor B}$ is in DNF, but not in full DNF; an equivalent full-DNF version is ${\displaystyle (A\land B)\lor (A\land \lnot B)\lor (\lnot A\land B)}$.

DNF로의 변환

공식을 DNF로 변환하는 것은 이중 부정 제거, De Morgan의 법칙, 그리고 분배 법칙과 같은 논리적 동등성을 사용하는 것을 포함한다.

모든 논리 공식은 등가 이격 정규 형식으로 변환될 수 있다.^{[1]: 152–153} 그러나 경우에 따라 DNF로 변환하면 공식이 기하급수적으로 폭발할 수 있다.For example, converting the formula ${\displaystyle (X_{1}\lor Y_{1})\land (X_{2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$ to DNF yields a formula with 2ⁿ terms.

모든 특정 부울 함수는 표준 형식 중 하나인 하나의 완전한^{[note 1]} 분리 정규 형식으로 나타낼 수 있다.이와는 대조적으로 두 가지 다른 일반적 이항 정규 형태는 동일한 부울 함수를 나타낼 수 있다. 그림을 참조하십시오.

계산 복잡성

결합 정상 형태 공식에 대한 부울 만족도 문제는 NP-hard이다; 이중성 원칙에 따르면, DNF 공식에 대한 위변성 문제도 그렇다.따라서 DNF 공식이 tautology인지 결정하는 것은 공동 NP-hard이다.

변형

계산 복잡성의 연구에 사용되는 중요한 변화는 k-DNF이다. 공식은 DNF에 있고 각 접속사가 최대 kL를 포함하는 경우 k-DNF에 있다.

참고 항목

• 대수 정규 형식 - 논리 공식에 대한 기타 정규 형식
• 블레이크 표준 양식 — DNF의 특별한 경우
• 명제 논리학
• Quine-McCluskey 알고리즘 — 주어진 부울 함수에 대한 최소 DNF 획득
• 진리표

메모들

참조

• David Hilbert; Wilhelm Ackermann (1999). Principles of Mathematical Logic. American Mathematical Soc. ISBN 978-0-8218-2024-7.
• J. Eldon Whitesitt (24 May 2012). Boolean Algebra and Its Applications. Courier Corporation. ISBN 978-0-486-15816-7.
• Colin Howson (11 October 2005). Logic with Trees: An Introduction to Symbolic Logic. Routledge. ISBN 978-1-134-78550-6.
• David Gries; Fred B. Schneider (22 October 1993). A Logical Approach to Discrete Math. Springer Science & Business Media. pp. 67–. ISBN 978-0-387-94115-8.

외부 링크

• "Disjunctive normal form", Encyclopedia of Mathematics, EMS Press, 2001 [1994]