Dysjunkcyjna postać normalna

W logice boolowskiej dysjunkcyjna postać normalna ( DNF ) jest kanoniczną postacią normalną formuły logicznej składającej się z dysjunkcji spójników; można to również opisać jako OR z ORAZ , sumę produktów lub (w logice filozoficznej ) koncepcję klastra . Jako postać normalna jest użyteczna w automatycznym dowodzeniu twierdzeń .

Definicja

Formuła logiczna jest uważana za DNF, jeśli jest dysjunkcją jednego lub więcej koniunkcji jednego lub więcej literałów . Formuła DNF jest w pełnej rozłącznej postaci normalnej, jeśli każda z jej zmiennych występuje dokładnie raz w każdym połączeniu. $displaystyle \ neg}$ jak w koniunkcyjnej postaci normalnej (CNF), jedynymi operatorami zdaniowymi w DNF są i ${\$$)$ lub ( , a nie ( ¬ ). Operator not może być używany tylko jako część literału, co oznacza, że ​​może poprzedzać zmienną zdaniową .

Poniżej znajduje się gramatyka bezkontekstowa dla DNF:

1. DNF → ( koniunkcja ) ${\ Displaystyle \ vee}$ DNF
2. DNF → ( spójnik )
3. Spójnik → Dosłowny ${\ displaystyle \ klin}$ Spójnik
4. Spójnik → Literał
5. Dosłownie → ${\ displaystyle \ neg}$ Zmienna
6. Literał → Zmienna

Gdzie Zmienna to dowolna zmienna.

Na przykład wszystkie poniższe formuły znajdują się w formacie DNF:

• ${\ Displaystyle (A \ ląd \ neg B \ ląd \ neg C) \ lor (\ neg D \ ląd E \ ląd F)}$
• ${\ Displaystyle (A \ ziemia B) \ lor (C)}$
• ${\ Displaystyle (A \ ziemia B)}$
• ${\ Displaystyle (A)}$

Jednak następujące formuły nie występują w DNF:

• ${\ Displaystyle \ neg (A \ lor B)}$ , ponieważ OR jest zagnieżdżone w NOT
• ${\ Displaystyle \ neg (A \ ziemia B) \ lor C}$ , ponieważ AND jest zagnieżdżone w NOT
• ${\ Displaystyle A \ lor (B \ ziemia (C \ lor D))}$ , ponieważ OR jest zagnieżdżone w ORAZ

Formuła $jest w$ ale nie w pełnym DNF równoważna pełna wersja DNF to ${\ Displaystyle (A \ ziemia B) \ lor (A \ ziemia \ lnot B) \ lor (\ lnot A\kraina B)}$ .

Konwersja do DNF

Mapa Karnaugha dysjunktywnej postaci normalnej (¬ A ∧¬ B ∧¬ D ) ∨ (¬ A ∧ B ∧ C ) ∨ ( A ∧ B ∧ D ) ∨ ( A ∧¬ B ∧¬ C )

Mapa Karnaugha dysjunktywnej postaci normalnej (¬ A ∧ C ∧¬ D ) ∨ ( B ∧ C ∧ D ) ∨ ( A ∧¬ C ∧ D ) ∨ (¬ B ∧¬ C ∧¬ D ) . Pomimo innego grupowania, te same pola zawierają „1”, jak na poprzedniej mapie.

Konwersja formuły na DNF obejmuje użycie logicznych równoważności , takich jak eliminacja podwójnej negacji , prawa De Morgana i prawo rozdzielności .

Wszystkie formuły logiczne można przekształcić w równoważną rozłączną postać normalną. Jednak w niektórych przypadkach konwersja do DNF może prowadzić do wykładniczej eksplozji formuły. Na przykład konwersja formuły ${\ Displaystyle (X_ {1} \ lor Y_ {1}) \ land (X_ {2}\lor Y_{2})\land \dots \land (X_{n}\lor Y_{n})}$ do DNF daje formułę zawierającą 2 ⁿ wyrazów.

Każda poszczególna funkcja boolowska może być reprezentowana przez jedną i tylko jedną pełną dysjunktywną postać normalną, jedną z form kanonicznych . W przeciwieństwie do tego, dwie różne zwykłe rozłączne formy normalne mogą oznaczać tę samą funkcję boolowską; zobacz ilustracje.

Złożoność obliczeniowa

Boolowski problem spełnialności na koniunkcyjnych formułach w postaci normalnej jest NP-trudny ; przez zasadę dwoistości , tak samo jest z problemem falsyfikowalności we wzorach DNF. Dlatego trudno jest zdecydować, czy formuła DNF jest tautologią .

I odwrotnie, formuła DNF jest spełnialna wtedy i tylko wtedy, gdy jedna z jej koniunkcji jest spełnialna; można to rozstrzygnąć w czasie wielomianowym .

Warianty

Ważną odmianą stosowaną w badaniu złożoności obliczeniowej jest k-DNF . Formuła jest w k-DNF, jeśli jest w DNF, a każda koniunkcja zawiera co najwyżej k literałów.

Zobacz też

• Algebraiczna postać normalna – XOR klauzul AND
• Postać kanoniczna Blake’a – DNF uwzględniająca wszystkie implikanty pierwsze
  • Algorytm Quine’a–McCluskeya – algorytm obliczania implikantów pierwszych
• Logika zdaniowa
• Tabela prawdy

Notatki

•   Davida Hilberta; Wilhelma Ackermanna (1999). Zasady logiki matematycznej . American Mathematical Soc. ISBN 978-0-8218-2024-7 .
•   J. Eldon Whitesitt (24 maja 2012). Algebra Boole'a i jej zastosowania . Firma kurierska. ISBN 978-0-486-15816-7 .
•   Colin Howson (11 października 2005). Logika z drzewami: wprowadzenie do logiki symbolicznej . Routledge'a. ISBN 978-1-134-78550-6 .
•   Davida Griesa; Fred B. Schneider (22 października 1993). Logiczne podejście do matematyki dyskretnej . Springer Science & Business Media. s. 67–. ISBN 978-0-387-94115-8 .

Linki zewnętrzne

• „Rozłączna postać normalna” , Encyklopedia matematyki , EMS Press , 2001 [1994]