Rozdzielna forma normalna - Disjunctive normal form

W operacji logicznych , A rozłączne postaci normalnej ( DNF ) jest kanoniczną postać normalna formuły logicznej obejmującej alternatywą koniunkcji; można go również opisać jako OR z AND , sumę produktów lub ( w logice filozoficznej ) pojęcie klastra . Jako forma normalna jest użyteczna w automatycznym dowodzeniu twierdzeń .

Definicja

Formuła logiczna jest uważana za w DNF, jeśli jest alternatywą jednego lub więcej spójników 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 koniunkcji. Podobnie jak w przypadku koniunkcyjnej postaci normalnej (CNF), jedynymi operatorami zdań w DNF są i ( ), lub ( ), a nie ( ). Nie operatora może być stosowany jedynie w ramach dosłownego, co oznacza, że można go tylko poprzedzają zmienną zdaniową . ${\ Displaystyle \ klin}$${\displaystyle \vee}$${\displaystyle \neg}$

Poniżej znajduje się gramatyka bezkontekstowa dla DNF:

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

Gdzie zmienna to dowolna zmienna.

Na przykład wszystkie poniższe formuły są w DNF:

• ${\ Displaystyle (A \ ziemia \ neg B \ ziemia \ neg C) \ lor (\ neg D \ ziemia E \ ziemia F)}$
• ${\displaystyle (A\land B)\lor(C)}$
• ${\displaystyle (A\land B)}$
• ${\ Displaystyle (A)}$

Jednak następujące formuły nie są dostępne w DNF:

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

Formuła jest w DNF, ale nie w pełnym DNF; odpowiednikiem pełnej wersji DNF jest . ${\ Displaystyle A\ lub B}$${\ Displaystyle (A \ ziemia B) \ lor (A \ ziemia \ nie B) \ lor (\ nie A \ ziemia 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 różnych grupowań, te same pola zawierają „1” jak na poprzedniej mapie.

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

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 przekonwertowanie formuły na DNF daje formułę z 2 ⁿ terminami. ${\ Displaystyle (X_ {1} \ Lor Y_ {1}) \ Ziemia (X_ {2} \ Lor Y_ {2}) \ Ziemia \ kropki \ Ziemia (X_ {n} \ Lor Y_ {n})}$

Każda konkretna funkcja Boole'a może być reprezentowana przez jedną i tylko jedną pełną dysjunktywną formę normalną, jedną z form kanonicznych . W przeciwieństwie do tego, dwie różne zwykłe dysjunktywne formy normalne mogą oznaczać tę samą funkcję Boole'a, patrz rysunki.

Złożoność obliczeniowa

Problem spełnialności na równoczesne postaci normalnej wzorze jest NP-trudny ; zgodnie z zasadą dwoistości , tak samo jest z problemem falsyfikowalności we wzorach DNF. Dlatego też współ-NP-trudno jest zdecydować, czy formuła DNF jest tautologią .

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żde połączenie zawiera co najwyżej k literałów.

Zobacz też

• Postać normalna algebraiczna — inne postacie normalne dla formuł logicznych
• Forma kanoniczna Blake'a — szczególny przypadek DNF
• Logika zdań
• Algorytm Quine'a-McCluskeya — uzyskuje minimalny DNF dla danej funkcji Boole'a
• Tabela prawdy

Uwagi

Bibliografia

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

Zewnętrzne linki

• „Rozdzielna forma normalna” , Encyklopedia Matematyki , EMS Press , 2001 [1994]