一般ＮＡＮＤ論理回路
自身が加入・所属する二つの団体の今年度アドベント・カレンダー用に寄稿しました，タイトルがやや誇張気味で正確には『或るＭＶ代数系（多元代数系）に於けるＮＡＮＤ論理回路の１つの構成・実現』でしてそれを普遍代数学の立場から示しつつ序にそのＮＡＮＤ論理演算子のプライマリネスを示します．
また，一般に電子回路で２元論理が実装されているとされるコンピューターの動作原理に就きましても少しだけ述べます．
最初に言葉や記号と記法の準備をしますが，誤訳や適当でない言い回し等ございましたらご指摘よろしくおねがいします．
- 普遍代数系$\mathbb{A}=(A;F)$とは，非空な（空で無い）台集合$A$と有限（項的）演算子$f\colon A^n\rightarrow A;n\in\mathbb{N}\xcancel{\sqcup\{0\}}$全体から成る集合$F$の組を言う．
- 射影演算子$x_i\colon A^n\ni(a_1,a_2,a_3,\ldots,a_i,\ldots,a_n)\mapsto a_i\in A$
- 定数演算子$\mathrlap{c}\phantom{x_i}\colon A^n\ni(a_1,a_2,a_3,\ldots,a_i,\ldots,a_n)\mapsto\mathrlap{c}\phantom{a_i}\in A$
- ｎ項多項式$\mathrlap{p}\phantom{x_i}\colon A^n\rightarrow A$とは，射影演算子と定数演算子に対する$F$に帰属する有限演算子の有限回適用より構成されるもののこと．例えば，$F=\{+,\cdot\}$の際は次の様な式．$$p=\sum_{i=1}^n\sum_{j=0}^{d_i}c_{i,j}x_i{}^j.$$ｎ項多項式が射影演算子のみから構成される場合には，特にｎ項項関数と言う．
- 普遍代数系$\mathbb{A}$が関数的完全であるとは，任意の有限演算子$f\in F$が（ｎ項）多項式．
- 普遍代数系$\mathbb{A}$がプライマルであるとは，任意の有限演算子$f\in F$が（ｎ項）項関数．
例を幾つか次に示します，何れも身近な代数的対象でしょう．
何れも「ラグランジュの補間多項式」を使用してｎ項多項式を作成している所に留意，
- 標数$q$の有限体$\mathbb{F}_q$は関数的完全，というのも任意のｎ項多項式$P\colon\mathbb{F}_q{}^n\rightarrow\mathbb{F}_q$に就いて次の等式が成り立つからだ．
$$P(X_1,X_2,\ldots,X_n)=\sum\nolimits_{\xi_1,\xi_2,\ldots,\xi_n\in\mathbb{F}_q}P(\xi_1,\xi_2,\ldots,\xi_n)\prod_{m=1}^n(1-(X_m-\xi_m)^{q-1}).$$ - ２元ブール環$\mathbb{B}=(\{\mathtt{False}=0,\mathtt{True}=1\};\{-\mathllap{\neg},\wedge,\vee\})$はプライマル，というのも任意のｎ項多項式$P\colon\mathbb{B}^n\rightarrow\mathbb{B}$に就いて次の等式が成り立つからだ．
$$P(X_1,X_2,\ldots,X_n)=\bigvee\nolimits_{b_1,b_2\ldots,b_n\in\mathbb{B}}P(b_1,b_2\ldots,b_n)\bigwedge_{m=1}^n\overline{X_m}^{\times(b_m+1)}.$$
更に２元ブール環の場合にて「ラグランジュの基底多項式」の定数演算子となる係数部が項関数として看做せるというのは$0=X_m\wedge-\mathllap{\neg}X_m,1=X_m\vee-\mathllap{\neg}X_m$から明らかだろう．
次に示す定理は，有限の制約が掛かりつつも関数的完全な普遍代数系の有用な特徴附けを与えて呉れます．
並びに
❝$\exists+,\times\in\{f\in F\mid f\colon A^2\rightarrow A\}\text{ {\rm s.t.} }\forall a\in A:a+0=a=0+a,\begin{cases}a\times 0=0&\!\!\!\!\!\!,\\a\times1=a\end{cases}$❞
及び
❝任意の元$a\in A$に対する特性演算子$\chi_a\colon A\rightarrow A,\chi_a(x)=\begin{cases}1&(x=a)\\0&(x\neq a)\end{cases}\,\,$が多項式❞
が成立
最初に，必要性❛$\Rightarrow$❜を証明する．原論文では自明の一言で済まされていますが，個人的には自明ではなく行間があると感じました．
任意の２元を$A$から取り出し$0,1$と置く，$\#A=1$ならば零環の様に$0=1$で良い．２項多項式（演算子）$+,\times\in F$を例えば次の通りに定義すれば各々の等式の成立が容易に確認され，仮定の$\mathbb{A}$の関数的完全性質より特性演算子$\chi_a$は項関数となるので宜しい．
$$x+x^\prime\coloneqq\begin{cases}x&(x^\prime=0)\\x^\prime&(x^\prime\neq0)\end{cases}\quad,\qquad x\times x^\prime\coloneqq\begin{cases}x\phantom{{}^\prime}&(x^\prime=0)\\0&(x^\prime\neq0)\end{cases}\quad.$$
最後に，充分性❛$\Leftarrow$❜を証明する．
所与の特性演算子$\chi_a$の総乗を「ラグランジュの基底多項式」として看做すことで，任意の有限演算子$f\in F$は「ラグランジュの補間多項式」の要領で次の通りに展開が可能．
$$f(\boldsymbol{x})=\sum\nolimits_{a_1,a_2,a_3,\ldots,a_m,\ldots,a_n\in\mathbb{A}}f(a_1,a_2,a_3,\ldots,a_m,\ldots,a_n)\prod_{m=1}^n\chi_{a_m}(x_m).$$
$+,\times,\chi_a$は多項式と仮定されてあったのだから，$f$も多項式だと承認せざるを得ない．
$\square$
但し，多変数関数$f(\boldsymbol{x})$に就いて変数部をベクトル表記しつつ加法$+$と乗法$\times$に結合律が課されていないので総和$\Sigma$と総積$\Pi$の計算は順に左から右へ行うものとする点に注意．
そして直ぐに系も導出されるのですが，こちらも有用なステートメントです．
並びに
❝$\exists+,\times\in\{f\in F\mid f\colon A^2\rightarrow A\}\text{ {\rm s.t.} }\forall a\in A:a+0=a=0+a,\begin{cases}a\times 0=0&\!\!\!\!\!\!,\\a\times1=a\end{cases}$❞
及び
❝任意の元$a\in A$に対する特性演算子$\chi_a\colon A\rightarrow A,\chi_a(x)=\begin{cases}1&(x=a)\\0&(x\neq a)\end{cases}\,\,$が項関数❞
が成り立ち
且つ$\phantom{\begin{cases}{}\\{}\end{cases}}$
全定数が項関数
早速ですが，有限群に Werner–Wille の定理の系を適用してみましょう．ですが，有限群にはゼロ元が存在しないので単なる適用では厳しいです．そこで，強引にゼロ元を作り出します．本稿では以降，前者のゼロ元と後者のゼロ元を明確に識別する為それぞれ内零元／外零元と特称するとします．一見すると，代数的構造を破壊しているようで作為的操作の観は否めませんがそこがポイントです．
有限群$(G;\{\cdot\})$に外零元$c\notin G;\forall g\in\bar{G}\colon g\cdot c=c=c\cdot g$を付加した拡張$\bar{G}=G\sqcup\{c\}$に，更に巡回置換（作用素）$\sigma\in\mathfrak{S}_{\smash{\bar{G}}}$を導入する．この時，普遍代数系$(\bar{G};\{\cdot,\sigma\})$はプライマル．
$\#\bar{G}=n>1$として，$\sigma^\nu(c)=e$なる正整数$\nu\in\mathbb{N}$を取りつつ$\sigma^\nu(z)=c$なる$z\in G$も取って来る．
そして，２項演算子$+,\times$と１項演算子の特性演算子$\chi_{\smash{\sigma^m(c)}}(\bullet);m\in\mathbb{N}_0$を次の如く定義する．式を追うに連れて、、、特に特性演算子の定め方の巧みさには涙を禁じ得無いでしょう。。。
あとは，確認作業．
$$x+y\coloneqq\sigma^{n-\nu}(\sigma^\nu(x)\cdot\sigma^\nu(y)),\quad x\times y\coloneqq x\cdot y,\quad\chi_{\smash{\sigma^m(c)}}(x)\coloneqq\sigma^\nu(z\cdot(\sigma^{n-m}(x))^{n-1}).$$
加法演算子
$$
\begin{align}
x+\mathrlap{c}\phantom{e} &=\sigma^{n-\nu}(\sigma^\nu(x)\cdot\sigma^\nu(c)) \\
&=\sigma^{n-\nu}(\sigma^\nu(x)\cdot e) \\
&=\sigma^{n-\nu}(\sigma^\nu(x)) \\
&=\sigma^n(x) \\
&=x \\
&=\sigma^n(x) \\
&=\sigma^{n-\nu}(\sigma^\nu(x)) \\
&=\sigma^{n-\nu}(e\cdot\sigma^\nu(x)) \\
&=\sigma^{n-\nu}(\sigma^\nu(c)\cdot\sigma^\nu(x))=\mathrlap{c}\phantom{e}+x.
\end{align}
$$
乗法演算子
$$
\begin{cases}
x\times\mathrlap{c}\phantom{e}=x\cdot\mathrlap{c}\phantom{e}=c & , \\
x\times e=x\cdot e=x & .
\end{cases}
$$
特性演算子
$$
\begin{align}
&\sigma^\nu(z\cdot(\sigma^{n-m}(x))^{n-1})=\chi_{\smash{\sigma^m(c)}}(x)=
\begin{cases}
e & , \\
c
\end{cases}
\\
\Longleftrightarrow{} &z\cdot(\sigma^{n-m}(x))^{n-1}=
\begin{cases}
c & , \\
z
\end{cases}
\\
\Longleftrightarrow{} &(\sigma^{n-m}(x))^{n-1}=
\begin{cases}
c & , \\
e
\end{cases}
\\
\Longleftrightarrow{} &\sigma^{n-m}(x)
\begin{cases}
=c & , \\
\neq c
\end{cases}
\\
\Longleftrightarrow{} &x=\sigma^n(x)
\begin{cases}
=\sigma^m(c) & , \\
\neq\sigma^m(c) &.
\end{cases}
\end{align}
$$
定数演算子
$$
\begin{cases}
\sigma^0(x)\cdot\sigma^1(x)\cdot\sigma^2(x)\cdot\cdots\cdot\sigma^{n-1}(x)=c & , \\
\{\sigma^m(c)\in\bar{G}\mid\exists m\in\mathbb{Z}\}=\bar{G} & .
\end{cases}
$$
前述の Werner–Wille の定理の系の条件を全て満足する為，普遍代数系$(\bar{G};\{\cdot,\sigma\})$のプライマリネスの成立が示された．これで，題意の証明が完了する．
$\square$
話題を逸脱しますので，読み飛ばして頂いても結構です．証明中の文字に就きまして，
- 有限群$G$の外零元$c\notin G$は，原論文では形式的なゼロ元と言う意味を込めて英単語 cipher の頭文字から採られて居そうでその意図に倣って使って居ります．
- 他方，元$z\in G$は見方に拠っては有限群$G$で内零元的な振る舞いを示してて英単語 zero の頭文字を与えました．
でして決して無作為に文字を決めてる訳では無いです．
併し乍ら，（有限）群では要請される条件が強過ぎてしまい適用先が限られるのです．ですので，（有限の）交わり半束というより緩い代数的構造へのこのアイデアの移植を考えます．
最大元（単位元）$1=\max L\mathbin{}(=\top)$と最小元（内零元）$0=\min L\mathbin{}(=\bot)$を持つ有限な交わり半束$(L;\{\wedge\})$に外零元$\cancel{0}\notin L;\forall\ell\in\bar{L}\colon\ell\wedge\cancel{0}=\cancel{0}$を付加した拡張$\bar{L}=L\sqcup\{\cancel{0}\}$に，更に$\sigma^2(1)=\sigma(\sigma(1))=\sigma(\cancel{0})=0$なる巡回置換（作用素）$\sigma\in\mathfrak{S}_{\smash{\bar{L}}}$を導入する．この時，普遍代数系$(\bar{L};\{\wedge,\sigma\})$はプライマル．
$\#\bar{L}=n>1$として，２項演算子$+,\times$と１項演算子の特性演算子$\chi_{\smash{\sigma^m(\cancel{0})}}(\bullet);m\in\mathbb{N}_0$を次の通りとする．そして，先程と同様に確認して行く．
$$\ell+\ell^\prime\coloneqq\sigma(\sigma^{n-1}(\ell)\wedge\sigma^{n-1}(\ell^\prime)),\enspace\ell\times\ell^\prime\coloneqq\ell\wedge\ell^\prime,\enspace\chi_{\smash{\sigma^m(\cancel{0})}}(\ell)\coloneqq\sigma^{n-1}(0\wedge\sigma^{n-m}(\ell)).\enspace$$
加法演算子
$$
\begin{align}
\ell+\cancel{0} &=\sigma(\sigma^{n-1}(\ell)\wedge\sigma^{n-1}(\cancel{0})) \\
&=\sigma(\sigma^{n-1}(\ell)\wedge1) \\
&=\sigma(\sigma^{n-1}(\ell)) \\
&=\sigma^n(\ell) \\
&=\ell \\
&=\sigma^n(\ell) \\
&=\sigma(\sigma^{n-1}(\ell)) \\
&=\sigma(1\wedge\sigma^{n-1}(\ell)) \\
&=\sigma(\sigma^{n-1}(\cancel{0})\wedge\sigma^{n-1}(\ell))=\cancel{0}+\ell.
\end{align}
$$
乗法演算子
$$
\begin{cases}
\ell\times\cancel{0}=\ell\wedge\cancel{0}=\cancel{0} & , \\
\ell\times\mathrlap{\;1}\phantom{\cancel{0}}=\ell\wedge\mathrlap{\;1}\phantom{\cancel{0}}=\ell & .
\end{cases}
$$
特性演算子
$$
\begin{align}
&\sigma^{n-1}(0\wedge\sigma^{n-m}(\ell))=\chi_{\smash{\sigma^m(\cancel{0})}}(\ell)=
\begin{cases}
\;1 & , \\
\cancel{0}
\end{cases}
\\
\Longleftrightarrow{} &0\wedge\sigma^{n-m}(\ell)=
\begin{cases}
\cancel{0} & , \\
\;0
\end{cases}
\\
\Longleftrightarrow{} &\sigma^{n-m}(\ell)\lesseqqgtr\cancel{0}
\\
\Longleftrightarrow{} &\ell=\sigma^n(\ell)\lesseqqgtr\sigma^m(\cancel{0}).
\end{align}
$$
定数演算子
$$
\begin{cases}
\sigma^0(\ell)\wedge\sigma^1(\ell)\wedge\sigma^2(\ell)\wedge\cdots\wedge\sigma^{n-1}(\ell)=\cancel{0} & , \\
\{\sigma^m(\cancel{0})\in\bar{L}\mid\exists m\in\mathbb{Z}\}=\bar{L} & .
\end{cases}
$$
先述の Werner–Wille の定理の系の条件を全て満足する為，普遍代数系$(\bar{L};\{\wedge,\sigma\})$のプライマリネスの成立が示された．これで，題意の証明が完了する．
$\square$
ここで，次の有限束$(S=S_n;<{=}\mathrel{\sphericalangle};\wedge=\min_\mathrel{\sphericalangle};\vee=\max_\mathrel{\sphericalangle})$を考察します．
$$
\begin{cases}
S_n\coloneqq\{e^{i\cdot(2m/n)\cdot\pi}\in\mathbb{C}\mid0<\exists m< n\} & , \\
\zeta\mathrel{\sphericalangle}\zeta^\prime\mathrlap{{}\coloneqq}\,\Longleftrightarrow\mathop{\mathrm{Arg}_{[0,2\pi)}}\zeta<\mathop{\mathrm{Arg}_{[0,2\pi)}}\zeta^\prime & .
\end{cases}
$$
ステートメントの通りに，$\cancel{0}\coloneqq e^{i\cdot(2\cdot0/n)\cdot\pi}=1$を付加します．これは，更にＭＶ代数系と言う代数的構造を成し２元ブール環の一般化と成ります．ＭＶ代数系の定義は転記して置くとして，２元ブール環が特殊な場合なことは簡単に確かめられますので省略したく思います．
非空台$M$と２項演算子$\oplus$と１項演算子$\ast$と０定数$0$から成る代数的構造$\mathbb{M}=(M;\oplus;\ast;0)$が次の公理を全て具備する時，ＭＶ代数系と呼称される．
$$
\forall\mu,\mu^\prime,\mu^{\prime\prime}\in M\colon
\begin{cases}
(\mu\oplus\mu^\prime)\oplus\mu^{\prime\prime}=\mu\oplus(\mu^\prime\oplus\mu^{\prime\prime}) & , \\
\mu\oplus0=\mu & , \\
\mu\oplus\mu^\prime=\mu^\prime\oplus\mu & , \\
{\ast}{\ast}\mu=\mu & , \\
\mu\oplus\ast0=\ast0 & , \\
\ast(\ast\mu\oplus\mu^\prime)\oplus\mu^\prime=\ast(\ast\mu^\prime\oplus\mu)\oplus\mu & .
\end{cases}
$$
特に，$\#M=2$の場合の際は２元ブール環との一致がこれ等から導かれる．
否定を意味させたい１項演算子$\ast$は，$\ast\zeta\coloneqq e^{-i\cdot(2\cdot1/n)\pi}\cdot\bar{\zeta}=e^{-2\pi i/n}\bar{\zeta}$で良いでしょう．
折角なので，有名な例も紹介します．
$M=[0,1]$としつつ$\mu\oplus\mu^\prime\coloneqq\min(\mu+\mu^\prime,1),\ast\mu\coloneqq1-\mu$としたＭＶ代数系はファジィ論理と呼称されており，制御理論から人工知能に至る迄多岐に亘って応用がある．
特別に同代数的構造体を$\mathbb{n}$で表記するとして，天下り的ですが次の$\mathbb{n}$上演算$\odot$を導入するとしましょう．
$$\zeta\odot\zeta^\prime\coloneqq e^{i\cdot(+2\cdot1/n)\cdot\pi}\cdot e^{i\cdot\min\mathop{\mathrm{Arg}_{[0,2\pi)}}(\zeta,\zeta^\prime)}=e^{+2\pi i/n}\cdot\min\nolimits_\mathrel{\sphericalangle}(\zeta,\zeta^\prime).$$
すると，
$$ \begin{align} (\zeta\odot\zeta^\prime)^{\odot(n-1)} &=e^{i\cdot(+2\cdot(n-1)/n)\cdot\pi}\cdot\min\nolimits_\mathrel{\sphericalangle}(\zeta\odot\zeta^\prime,\zeta\odot\zeta^\prime) \\ &=e^{i\cdot(+2\cdot(n-1)/n)\cdot\pi}\cdot(\zeta\odot\zeta^\prime) \\ &=e^{i\cdot(+2\cdot(n-1)/n)\cdot\pi}\cdot e^{i\cdot(+2\cdot1/n)\cdot\pi}\cdot\min\nolimits_\mathrel{\sphericalangle}(\zeta,\zeta^\prime) \\ &=\min\nolimits_\mathrel{\sphericalangle}(\zeta,\zeta^\prime). \end{align} $$
が成り立ち次が従います．
ＭＶ代数系$(U(\mathbb{n});\{\odot\})$はプライマル．故に，周知のプライマルな普遍代数系$(U(\mathbb{B});\{\mathrel{\mathtt{NAND}}\})$の一般化に当たる物が得られた事も直ちに分かり，又尚$U$は忘却関手の意．斯様なる演算$\odot$には様々な呼称が存在し， Sheffer stroke ＝シェファーの棒記号と言う表記法でも知られる．
こちらが本稿の最終目標でしたが，最後にコンピューターやＩＴの分野との関係に就いてお話しします．
現在一般に論理回路は２元論理として２元ブール環が採用されているとされてはいますが、実際はバイナリのコンピューターでスペックが充分であって更なる高性能化の可能性を模索して多元論理を採用したハードウェアを作るよりも既存のバイナリのコンピューターでシミュレーションしたほうが速くて安く済むという状況にあるのだそうです．
他にも，ＲＤＢのブーリアンでも真偽$\mathtt{True},\mathtt{False}$とは別の第三の真理値・不定不明$\mathtt{Unknown}$を用いた３元論理という体系が使われています．これは，ＳＱＬで空虚$\mathtt{NULL}$の存在を許容した結果として導入が必要となったという経緯があります．業務ではMicrosoft SQL Serverを使用しているものの$\mathtt{Unknown}$に関する使用等の経験は未だありませんが，可能な限り解説します．$\mathrel{\mathtt{NOT}},\mathrel{\mathtt{AND}},\mathrel{\mathtt{OR}}$の各真理値表は，次の通りとなります．
| $\mathrel{\mathtt{NOT}}$ | |
|---|---|
| $\mathtt{True}$ | $\mathtt{False}$ |
$\mathtt{Unknown}$ | $\mathtt{Unknown}$ |
| $\mathtt{False}$ | $\mathtt{True}$ |
| $\mathrel{\mathtt{AND}}$ | $\mathtt{True}$ | $\mathtt{Unknown}$ | $\mathrlap{\mathtt{False}}\phantom{\mathtt{Unknown}}$ |
|---|---|---|---|
| $\mathtt{True}$ | $\mathtt{True}$ | $\mathtt{Unknown}$ | $\mathtt{False}$ |
$\mathtt{Unknown}$ | $\mathtt{Unknown}$ | $\mathtt{Unknown}$ | $\mathtt{False}$ |
| $\mathtt{False}$ | $\mathtt{False}$ | $\mathtt{False}$ | $\mathtt{False}$ |
| $\mathrel{\mathtt{OR}}$ | $\mathrlap{\mathtt{True}}\phantom{\mathtt{Unknown}}$ | $\mathtt{Unknown}$ | $\mathtt{False}$ |
|---|---|---|---|
| $\mathtt{True}$ | $\mathtt{True}$ | $\mathtt{True}$ | $\mathtt{True}$ |
$\mathtt{Unknown}$ | $\mathtt{True}$ | $\mathtt{Unknown}$ | $\mathtt{Unknown}$ |
| $\mathtt{False}$ | $\mathtt{True}$ | $\mathtt{Unknown}$ | $\mathtt{False}$ |
ここで Sheffer–Webb の定理を想起します，次の順序を考えることで何れも理解が捗って暗記は不要かと思います．
$$\omega^0=\mathtt{False}\mathrel{\sphericalangle}\omega^1=\mathtt{Unknown}\mathrel{\sphericalangle}\omega^2=\mathtt{True}.$$
ここからは憶測の域を超出しないのですが，今日のＲＤＢやＳＱＬは Sheffer–Webb の定理で演算$\zeta\odot\zeta^\prime=\omega\cdot\min_\mathrel{\sphericalangle}(\zeta,\zeta^\prime)$のプライマリネスを考慮して構築されて来たのかも知れません．
参考文献
この記事を高評価した人
この記事に送られたバッジ
投稿者
