Algebraiczna postać normalna

W algebrze Boole'a algebraiczna postać normalna ( ANF ), postać normalna sumy pierścieniowej ( RSNF lub RNF ), postać normalna Zhegalkina lub rozwinięcie Reeda-Mullera to sposób pisania formuł logiki zdań w jednej z trzech podform:

Cała formuła jest całkowicie prawdziwa lub fałszywa:

${\ displaystyle 1}$

${\ displaystyle 0}$
Jedna lub więcej zmiennych jest łączona w termin przez $)$ ( ) $,$ a następnie jeden lub więcej warunków jest łączony przez XOR ( razem w ANF Negacje są niedozwolone:

{\ Displaystyle a \ oplus b \ oplus \ lewo (a \ ziemia b \ po prawej) \ oplus \ lewo (a \ ziemia b \ ziemia c \ prawa )}

Poprzedni podformularz z wyrazem czysto prawdziwym:

{\ Displaystyle 1 \ oplus a \ oplus b \ oplus \ lewo (a \ ziemia b \ po prawej) \ oplus \ lewo (a \ ziemia b \ ziemia c \ prawa)}

Formuły napisane w ANF są również znane jako wielomiany Zhegalkina i wyrażenia Reeda-Mullera o dodatniej polaryzacji (lub parzystości) (PPRM).

Typowe zastosowania

ANF jest formą kanoniczną , co oznacza, że dwie logicznie równoważne formuły zostaną przekształcone w tę samą ANF, łatwo pokazując, czy dwie formuły są równoważne w przypadku automatycznego dowodzenia twierdzeń . W przeciwieństwie do innych postaci normalnych, można ją przedstawić jako prostą listę list nazw zmiennych — koniunkcyjne i dysjunkcyjne również wymagają zapisania, czy każda zmienna jest zanegowana, czy nie. Postać normalna negacji nie nadaje się do określania równoważności, ponieważ w przypadku form normalnych negacji równoważność nie implikuje równości: a ∨ ¬a nie jest redukowane do tego samego co 1, mimo że są one logicznie równoważne.

Umieszczenie formuły w ANF ułatwia również identyfikację funkcji liniowych (używanych na przykład w rejestrach przesuwnych z liniowym sprzężeniem zwrotnym ): funkcja liniowa to taka, która jest sumą pojedynczych literałów. Właściwości rejestrów przesuwnych z nieliniowym sprzężeniem zwrotnym można również wywnioskować z pewnych właściwości funkcji sprzężenia zwrotnego w ANF.

Wykonywanie operacji w algebraicznej postaci normalnej

Istnieją proste sposoby wykonywania standardowych operacji boolowskich na wejściach ANF w celu uzyskania wyników ANF.

XOR (logiczna wyłączna dysjunkcja) jest wykonywana bezpośrednio:

( 1 ⊕ x ) ⊕ ( 1 ⊕ x ⊕ y )

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

y

NOT (negacja logiczna) to XORing 1:

¬ (1 ⊕ x ⊕ y)

1 ⊕ (1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

x ⊕ y

AND (spójnik logiczny) ma rozkład algebraiczny

( 1 ⊕ x ) (1 ⊕ x ⊕ y)

1 (1 ⊕ x ⊕ y) ⊕ x (1 ⊕ x ⊕ y)

(1 ⊕ x ⊕ y) ⊕ (x ⊕ x ⊕ xy)

1 ⊕ x ⊕ x ⊕ x ⊕ y ⊕ xy

1 ⊕ x ⊕ y ⊕ xy

OR (alternatywa logiczna) używa albo 1 ⊕ (1 ⊕ a) (1 ⊕ b) (łatwiej, gdy oba operandy mają czysto prawdziwe wyrazy) albo a ⊕ b ⊕ ab (łatwiej w innym przypadku):

( 1 ⊕ x ) + ( 1 ⊕ x ⊕ y )

1 ⊕ (1 ⊕ 1 ⊕ x )(1 ⊕ 1 ⊕ x ⊕ y )

1 ⊕ x(x ⊕ y)

1 ⊕ x ⊕ xy

Konwersja do algebraicznej postaci normalnej

Każda zmienna w formule jest już w czystym ANF, więc wystarczy wykonać operacje logiczne formuły, jak pokazano powyżej, aby przenieść całą formułę do ANF. Na przykład:

x + (y ⋅ ¬z)

x + (y(1 ⊕ z))

x + (y ⊕ yz)

x ⊕ (y ⊕ yz) ⊕ x(y ⊕ yz) x

⊕ y ⊕ xy ⊕ yz ⊕ xyz

Formalna reprezentacja

ANF jest czasami opisywane w równoważny sposób:

${\ Displaystyle f (x_ {1}, x_ {2}, \ ldots, x_ {n}) = \!}$	${\ Displaystyle a_ {0} \ oplus \!}$
	${\ Displaystyle a_ {1} x_ {1} \ oplus a_ {2} x_ {2} \ oplus \ cdots \ oplus a_ {n} x_ { n}\oplus \!}$
	${\ Displaystyle a_ {1,2} x_ {1} x_ {2} \ oplus \ cdots \ oplus a_ {n-1, n} x_ {n-1} x_ {n} \ oplus \!} ⋯$
	$\ displaystyle \ cdots \ oplus \!}$
	${\ Displaystyle a_ {1,2, \ ldots, n} x_ {1} x_ {2} \ ldots x_ {n }\!}$

gdzie

\ Displaystyle a_ {0}, a_ {1}, \ ldots, a_ {1,2, \ ldots, n} \ w \{0,1\}^{*}}

w pełni opisuje

{\ displaystyle f}

.

Rekurencyjne wyprowadzanie wieloargumentowych funkcji boolowskich

Istnieją tylko cztery funkcje z jednym argumentem:

${\ displaystyle f (x) = 0}$
${\ Displaystyle f (x) = 1}$
${\ Displaystyle f (x) = x}$
${\ Displaystyle f (x) = 1 \ oplus x}$

Aby przedstawić funkcję z wieloma argumentami, można użyć następującej równości:

{\ Displaystyle f (x_ {1}, x_ {2 },\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})} ,

gdzie

${\ Displaystyle g (x_ {2}, \ ldots, x_ {n}) = f (0, x_ {2}, \ldots ,x_{n})}$
${\ Displaystyle h (x_ {2}, \ ldots, x_ { n})=f(0,x_{2},\ldots,x_{n})\oplus f(1,x_{2},\ldots,x_{n})}$

Rzeczywiście,

jeśli ${\ Displaystyle x_ {1} = 0}$ wtedy ${\ Displaystyle x_ {1} h = 0}$ i tak ${\ Displaystyle f (0, \ldots )=f(0,\ldots )}$
jeśli $}$ ${\ Displaystyle f (1, \ ldots) = f (0, \ ldots) \ oplus f (0, \ ldots) \ oplus f (1, \ ldots)}$ $)$ to i

Ponieważ zarówno $jak$ i $wynika z tego$ mniej argumentów niż , $rekurencyjnie$ zakończymy funkcjami z jedną zmienną. Na przykład skonstruujmy ANF z ${\ Displaystyle f (x, y) = x \ lor y}$ (logiczne lub):

${\ Displaystyle f (x, y) = f (0, y) \ oplus x (f ( 0,y)\oplus f(1,y))}$
ponieważ ${\ Displaystyle f (0, y) = 0 \ lor y = y}$ i ${\ Displaystyle f (1, y) =1\lub y=1}$
wynika z tego, że ${\ Displaystyle f (x, y) = y \ oplus x (y \ oplus 1)}$
przez rozkład otrzymujemy ostateczny ANF: ${\ Displaystyle f (x, y) = y \ oplus xy \ oplus x = x \ oplus y\oplus xy}$

Zobacz też

Dalsza lektura

Wegener, Ingo (1987). Złożoność funkcji boolowskich . Wiley-Teubner . P. 6. ISBN 3-519-02107-2 .
„Prezentacja” (PDF) (w języku niemieckim). Uniwersytet Duisburg-Essen . Zarchiwizowane (PDF) od oryginału w dniu 2017-04-20 . Źródło 2017-04-19 .
Maxfield, Clive "Max" (29.11.2006). „Logika Reeda-Mullera” . Logika 101 . EETimes . Część 3. Zarchiwizowane od oryginału w dniu 2017-04-19 . Źródło 2017-04-19 .