代数正規形

Boolean polynomials as sums of monomials

ブール代数では、代数正規形( ANF )、環和正規形( RSNFまたはRNF )、ジェガルキン正規形、またはリード・ミュラー展開は、命題論理式を次の 3 つのサブフォームのいずれかで記述する方法です。

• 式全体は純粋に真か偽かです。
  • ${\displaystyle 1}$
  • ${\displaystyle 0}$
• 1つ以上の変数をAND ( )で結合して項を作成し、その後1つ以上の項をXOR ( )で結合してANFを作成します。否定は許可されません。 ${\displaystyle \land }$ ${\displaystyle \oplus }$ $${\displaystyle a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$$
• 純粋に真の項を含む前のサブフォーム: $${\displaystyle 1\oplus a\oplus b\oplus \left(a\land b\right)\oplus \left(a\land b\land c\right)}$$

ANFで書かれた式は、ジェガルキン多項式や正極性（またはパリティ）リード・ミュラー式（PPRM）とも呼ばれます。^[1]

一般的な用途

ANF は標準形式です。つまり、論理的に同値な2 つの式は同じ ANF に変換され、自動定理証明において 2 つの式が同値かどうかを簡単に示せます。他の正規形とは異なり、変数名のリストの単純なリストとして表現できます。連言正規形と選言正規形では、各変数が否定されているかどうかも記録する必要があります。否定正規形は同値性の判定には適していません。なぜなら、否定正規形では同値であることは等価性を意味しないからです。つまり、a ∨ ¬a は論理的に同値であっても、1 と同じものに簡約されるわけではありません。

式をANFに代入すると、線形関数（例えば線形フィードバックシフトレジスタで使用される関数）の識別も容易になります。線形関数とは、単一のリテラルの和で表される関数です。非線形フィードバックシフトレジスタの特性は、ANFのフィードバック関数の特定の特性から推測することもできます。

代数正規形内での演算の実行

ANF 結果を取得するために、ANF 入力に対して標準のブール演算を実行する簡単な方法があります。

XOR (排他的論理和) が直接実行されます。

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

1 ⊕ x ⊕ 1 ⊕ x ⊕ y

1 ⊕ 1 ⊕ x ⊕ x ⊕ y

y

NOT（論理否定）はXOR演算である1：^[2]

¬ (1 ⊕ x ⊕ y)

1 ⊕ (1 ⊕ x ⊕ y)

1 ⊕ 1 ⊕ x ⊕ y

x ⊕ y

AND（論理積）は代数的に分布している^[3]

( 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（論理和）は、1⊕（1⊕a）（1⊕b）^[4]（両方のオペランドが純粋に真の項を持つ場合の方が簡単）またはa⊕b⊕ab ^[5]（それ以外の場合の方が簡単）のいずれかを使用します。

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

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

1 ⊕ x(x ⊕ y)

1 ⊕ x ⊕ xy

代数正規形への変換

数式内の各変数は既に純粋なANFで記述されているため、上記のように数式のブール演算を実行するだけで、数式全体をANFに変換できます。例えば、

x + (y ⋅ ¬z)

x + (y(1 ⊕ z))

x + (y ⊕ yz)

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

x ⊕ y ⊕ xy ⊕ yz ⊕ xyz

正式な表現

ANF は次のように同様に説明されることもあります。

${\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}\!}$

ここで、 はを完全に説明します。 ${\displaystyle a_{0},a_{1},\ldots ,a_{1,2,\ldots ,n}\in \{0,1\}^{*}}$ ${\displaystyle f}$

多引数ブール関数の再帰的導出

引数が 1 つある関数は 4 つだけです。

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

複数の引数を持つ関数を表すには、次の等式を使用できます。

${\displaystyle f(x_{1},x_{2},\ldots ,x_{n})=g(x_{2},\ldots ,x_{n})\oplus x_{1}h(x_{2},\ldots ,x_{n})}$、 どこ

• ${\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})}$

確かに、

• もしそうならば ${\displaystyle x_{1}=0}$ ${\displaystyle x_{1}h=0}$ ${\displaystyle f(0,\ldots )=f(0,\ldots )}$
• もしそうならば ${\displaystyle x_{1}=1}$ ${\displaystyle x_{1}h=h}$ ${\displaystyle f(1,\ldots )=f(0,\ldots )\oplus f(0,\ldots )\oplus f(1,\ldots )}$

と はどちらも引数が少ないため、この処理を再帰的に用いることで、最終的に1つの変数を持つ関数で終わることになります。例えば、(論理和) の ANF を構築してみましょう。 ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle f}$ ${\displaystyle f(x,y)=x\lor y}$

• ${\displaystyle f(x,y)=f(0,y)\oplus x(f(0,y)\oplus f(1,y))}$
• 以来、そして ${\displaystyle f(0,y)=0\lor y=y}$ ${\displaystyle f(1,y)=1\lor y=1}$
• すると ${\displaystyle f(x,y)=y\oplus x(y\oplus 1)}$
• 分配によって最終的な ANF が得られます。 ${\displaystyle f(x,y)=y\oplus xy\oplus x=x\oplus y\oplus xy}$

参照

• リード・ミュラー展開
• ジェガルキン正規形
• ブール関数
• 論理グラフ
• ジェガルキン多項式
• 否定正規形
• 連言標準形
• 選言正規形
• カルノー図
• ブールリング

参考文献

1. Steinbach, Bernd [ドイツ語] ; Posthoff, Christian (2009). 「序文」.論理関数と方程式 - 例と演習(第1版). Springer Science + Business Media BV p. xv. ISBN 978-1-4020-9594-8。LCCN  2008941076。
2. WolframAlpha NOT同値性のデモンストレーション: ¬a = 1 ⊕ a
3. WolframAlpha AND同値性のデモンストレーション: (a ⊕ b)(c ⊕ d) = ac ⊕ ad ⊕ bc ⊕ bd
4. ド・モルガンの法則より
5. WolframAlpha OR 等価性のデモンストレーション: a + b = a ⊕ b ⊕ ab

さらに読む

• ウェゲナー、インゴ(1987). ブール関数の計算量. Wiley-Teubner . p. 6. ISBN 3-519-02107-2。
• 「プレゼンテーション」（PDF）（ドイツ語）。デュースブルク＝エッセン大学。 2017年4月20日時点のオリジナルよりアーカイブ（PDF） 。 2017年4月19日閲覧。
• Maxfield, Clive "Max" (2006年11月29日). 「リード・ミュラー論理」. Logic 101. EETimes .パート3. 2017年4月19日時点のオリジナルよりアーカイブ。 2017年4月19日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Algebraic_normal_form&oldid=1295350221"