多値論理関数の分解としきい値回路網への応用
藤 田 志 郎＊
（昭和46年9月9日受理）
Decomposition of multi−valued logical functions and its application to threshold networks
Shiro FuJiTA
（Received September 9，1971）
In this paper， first， the theoretical aspects of the decomposition of an arbitrary rnulti−valued logical function in terms of several essentially simpler logical functions are described．
Secondly， on the basis of this theory， a methed for the realization of three−valued logical functions by net−
works of threshold gates is proposed．
Lastly， examples are worked out in detail to illustrate this method．
1．ま え が き
三値しきい値素子を用いて，任意の三値論理関数を回路 実現する手法についての報告はこれまでにいくつかみられ る。1）〜5）本論文の目的もまた，任意の三値論理関数を最小 のしきい値素子でもって実現する一つの手法を与えるもの である。
任意の関数がしきい値素子でもって回路実現されること は，しきい値素子を表わす関数を考えると，これらの関数 の合成関数として，任意の関数が表わされていることであ る。したがって，本論文の前半においては，一つの論理関 数をより簡単な関数の合成関数として表わすいわゆる関数 の分解についての理論を述べる。ここで述べられる定理は，
二値論理関数についてAshenhurst， Hu6）・7）・s）らによって 発展させられた関数の分解についての定理の多値論理関数 への一般化である。
後半においては，前半でえられた定理を用いて，最小の しきい値素子でもって与えられた三値論理関数を回路実現 する手法を述べる。
2．関数の分解
n変数のm値論理関数f（x・，x2，…， Xn）を考える。論
理変数Xi，およびその関ta fのとる真理値は整数値0，1，
2，…，m−1とする。また，π変数（x・，κ2，…， Xn）をx で表わし，この関数をノ（κ）と記す。
以下，ことわりなく関数といえば，〃植論理関数を表わ すものとする。
〔定義1〕関数！②がいくつかのより簡単な関数91，
g2，…，9kの合成関数として表わされるとき，これをf（x）
の分解といい，9i（1〈i≦k）を成分関数という。
ここで，各9iを表わす素子でもってf（X）を回路実現 したとき，feed−back loopはもたないものとする。
（例1）f（x・）x2）がつぎのように与えられているとす る。（Table 1）（m＝3とする）
Table 1
＞（X・，切口max（X・， X2）
ガ
f O12 〈（x、， x、）一min（x、， x、）
0 012 e（Xl・x2）＝x・とん2のsum modulo 3x1 1 1 1 0
2 111 とすると，f（x・， x2）は
＊非常勤講師（川崎医科大学）
f（Xユ，X2）一〈｛〉（X・，切，（D［X・，〉（X・， X2）］｝
なる分解をもつ。〉，㊦，〈が成分関数であり，これらを 素子とした！（x・，x2）の回路実現はFig．1に与えられて
いる。
x
v
X
x
e A f
Fig．1
〔定義2〕n個の変数の集合 Xt｛Xl， x2，…， Xn｝に対して，
Y＝｛pm， y2， …， yp｝（pti E−X， i一一1，2，・・一P）
Z＝＝｛Zl，22，…，εq｝（Zi∈X， i＝1，2…，の をXの分割といい，
YIZ＝y、， Y2，＿，ッpk、，22，…， aq と記す。
ここで，YUZ＝・Xであり，Xi（1≦i≦n）が同時に：V，Z に含まれていてもよい。また，0≦P≦n，2≦e≦nとす
る。
Pを第一次数，qを第二次数という。明らかに， P＋q
≧nであるが，
r＝：（P＋の一n （1）
を分割の重複度という。r＝0のとき，分割YIZ．は分離
（disjunctive）であるという。
〔定義3〕関数／（x）について，Xの一つの分割を YIZ＝y・， Y2，…， yp12・，22，…， a・とする。
このとき，つぎの二つの関数
g5＝cb（pti， ）t2， …， yp， lbn）， iP ＝aPe（ai， 22， …， Zq）
があり，
f（X）＝to｛Yi， Y2， …， Yp， th（2i， 22…， gq）｝
となるとき，φとψは分割yIZに関してア（X）の単分解 を表わすといい，記号的に（φ，ψ）とかく。このとき，
ノ（x）自身も一つの単分解と考えておく。また，（1）で与 えられるrは単分解の重複度ともいい，r．＝Oならば，単 分解は分離であるという。
二値論理関数の分解に関しては， Reduction Theorem として知られている定理があるが，9）この定理自身の内容 は，論理関数が二値であることが本質的に用いられていな いので，〃植論理関数についても成立すると考えうる。し たがって，つぎにこれを定理として述べておく。
⊂定理1〕9）任意の関数！（x）に対して，k＋1個の成分関 数をもった分解が与えられているとする。それらを伽，
ψ2，…，ψk，φkとする。
このとき，この分解はk個の単分解の系列
（｛bi， thi） （i一一1， 2， ．．・， le）
の合成として表わしうる。
この定理は，ノ④．に対するle＋1個の成分関数をもっ た分解があり，これを表わすk＋1個の成分関数をψ・，
ψ2，…，ψk，φkとすれば，単分解の系列（φユ，ψ・），（φ2，
ψ2），…，（φk，ψk）が存在して，この分解はこれらの合成
として表わすことができることを示している。
この単分解の合成を記号的に
（φk，．ψk）・（φ・一・，ψk一・）・・一一・（φ・，ψ・）・（φ・，ψ・）
と記す。幽
（例2）例1における関数の分解を考える。
まず，ψ・（x・，x2）＝V（x・， x2） とする。
このとき，
f（X・，X2）＝＝φ・｛X・，ψ1（X・， X2）｝
となり，これは単分解（φi，ψ・）を表わす。
つぎに，ψ2＝（∋（Xl，ψ1）， φ2＝〈（ψi，ψ2）
とすると，φ・＝φ2（ψ・，．ψ2） となる。
これは単分解（φ2，ψ2）を表わす。
ゆえに，分解は
（φ2，ψ2）・（φ1，ψ1） となる。
いま，関数φi一・の単分解（φi，ψi）の第一，二次数を Pi，4i（i＝1，2，…， le）とする。ただし，φo＝f（x）。
このとき，φiはPi＋1個の変数の関数であり，ψiはei 個の変数の関数である。φL・の単分解（φi，ψi）の重複度 をriとすれば，φi一・の変数の個数はPi一・＋1であるか
ら，
r・；（Pi−t−qi）一（P・一・＋1） （i＝1，2，…91e）
となる。ここで，P・＝＝n−1とする。
このle個の重複度の和をrとすれば，
ヒ な
r・＝Σ ri＝＝Σ（Pi−Pi＿1）＋Σ（qi−1）
i＿1 i＝1 i＝＝1
な ＝PヒーPO＋Σ4i一々 isl な
となる。Po＝n−1であり， R≡≡Z］ qi＋Pk＋1とおけば，
iUt1
r＝＝R−k−n （2）
をうるelo）
ここで，Rはf（X）の分解における成分関数ψ・，ψ2，…，
ψk，φkのおのおのの変数の個数の和である。（2）式で与 えられるrを分解の全重複度という。一般にf（X）の分解 を単分解の合成として表わす方法は一通りではないが，10）
上に定義したrは成分関数の変数の個数のみに依存してい るので，分解の表わし方には関係しない。
いま，e≧2をあるきまった正整数とする。そして，ノ（x）
の分解がq個の変数をもったk＋1個の成分関数の合成によ って表わされているとする。このとき誘＋1個の成分関数 の変数の個数の和はR＝q（々＋1）となる。
したがって，全重度rは
r＝＝q（le＋1）一le−n＝（q−1）（k＋1）一n＋1 となる。これより成分関数の個tw k＋1は
み十1＝ n−1
4＝一IHI十一i＝一il （3）
で与えられる。11）
3．単分解と：分割行列
〔定義4〕関tw f（x）のX・＝｛x・， x2，…， Xn｝．に関する 分離な分割 YIZ＝Yl， Y2，…， yp匿， Z2，…，2q に対して，一つの行列をつぎのように対応させる。
すなわち，工数をmP，回数をmqとし，おのおのの順序 は（Yl， Y2，…， yp），（21，22，…，2q）のm進数表示の 順とする。またmn個の劣＝（X・， X2，…， X・）（Xiは0，1，
2，…，m−1のどれかをとる）に対して，おのおの（Yl，
y2，…， yp），（2・， Z2，…，2q）がきまり，行列の一つの要 素が対応するが，これはノ（X）の値とする。
このようにしてえられた行列はその要素が，0，1，2，
…，m−1のどれかであるが，これを分割行列といい， M
（ア：yiZ）と記す。
この行列で，異なった行ベクトルの数を行多重度，異な った列べクトルの数を列多重度という。
さて，与えられた関数f（X）について分割YIZに関す る単分解が存在するかどうかは，上に定義した分割行列の 列多重度と関係がある。これに関しては，二値論理関数に ついて，Ashenhurst， Hu6）・7）・12）らによって単分解が存在 するための条件が与えられている。ここで述べられる定理 はそれのm値論理関数への一般化である。
〔定理2〕関数！（x）についてのX白蔓，x2，…tXn｝の 分離な分割Y「Zに関する分割行列M（f＝yIZ）の列多 重度功勤≦mであるならば，Yizに関する単分解（φ，
ψ）が存在する。また，外野重度vがv＞mならば単分解 は存在しない。
（証明） x＝｛x・，x2，…， x・｝の分離な分割を
YIZ＝），i， ），2， Yp122， 2i， ， 2q
とする。
いま，この分割行列の列多重度Vが，V−mであるとす る。そして，異なった列をVl， v2，…， Vmとする。
このとき，（Zl， Z2，…，2q）の関数ψ（2・，22，…，2q）
をつぎのごとく定義する。
すなわち，Vi（i＝1，2，…， m）に対応する（z・，z2，…2q）
に対しては
aPe （2i， 22， …， 2q）＝ai （i＝1， 2…， m）
とする。ただし，ai（齢1，2，…， m）の値はすべて異な った0，1，2，…，m−1のうちのどれかとする。
さらに，P＋1個の変数の関数φ（y・，ッ2，…， Ptp， yp＋・）
をつぎのように定義する。
（y・，Y2，…yp）が第1番目の行に対応しているとする。
そしてtyp＋・＝・ai（i＝1，2，…， m）ならば，
φ＝ンiに相当する列べクトルのee 1 9素 （i＝1，2，…，m）
とする。
ここで，yp＋・＝ψとすれば，
ノ②二φ｛y・，夕・，…ツP，ψ（2・，22，…，X、）｝
となり，これは明らかに，ノ（X）の分割yIZに関する単 分解である。
列多重度Vが，V＜mの場合も同様な方法により単分解 が存在することを示しうる。
つぎに，列多重度Vが，V＞mと仮定する。そのうちの 任意の異なったm＋1個の列をv・，v2，…， Vm， Vm＋・とす る。このとき，各列ベクトルに対応する（z・，z2，…，2q）
をそれぞれηi（i＝1，2，…，m＋1）とする。
いま，m＋1個の列のうちの任意の二つVj， Vkを考える
（ゴ≒の。 この二つの列べクトルにおいて，第1要素が異 なっているような1が少くとも一つは存在するはずであ る。これをaj， akとする。
一方，1番目の行に対応する（y・，Y2，…， yp）をζしで 表わす。
単分解 φ｛y・，Y2，…Yp，ψ（2・， a2，・・，
が存在すると仮定する。
このとき，ψ（η」）＝ψ（ηk）とすると，
￠｛k， i；e（nj）｝一ip｛gz， iP （qk）｝
をうる。
ところが，
￠｛gi， i；e（nj）｝＝＝aj＝￥ak＝￠｛gz， ile（nk）｝
である。ゆえに，
iPn（nj） ＞f iln（nk）
をうる。
Zg）｝
Vi（i一一1， 2， …， m十1）のうちの他の任意の二つについ ても同様な結果をうる。
したがって，ψ（η1），ψ（η2），…，ψ（ηm），ψ（ηm＋1）の 値はすべて異なった値となる。
ところが，ψは0，1，2，…，m−1のm個の値のどれ かをとるゆえに，これは矛盾である。
したがって，単分解は存在しない。 （証明終）
4． 1）o皿 t−Care をもつ関数の単分解 n変数関数f（x）が don t−care をもっている場合を 考える。
x・＝｛x・，x2，…， x・｝の分離な分割 YIZ＝＝yi， y2， …， yp12i， z2， …， zg
についての分割行列M（f：ylZ）はつぎのように定義す
る。
すなわち，x＝（x・，x2，…， Xa）がf（x）に対する don t−
care な点ならば，＊それに対応する行列の要素は＊とし
＊Xi （i＝1，2，…， n）は0，1，2，…m−1のm個の値を とるゆえに，x＝（Xl， x2，…， x・）はn次元空間のMn 個の点（格子点）に対応する。
ておく。 don，t−care でない場合の定義は第3節の場合 と同じとする。
また，（21，統，…，2q）の関数ψ（21， a2，…， Zg）と（Y1，
Y2，…， yp，ψ）の関数φ（y・， y2，…yp，ψ）に対して，
ア（X・，X・t…tXn）＝￠｛y・， y・，…，y，，ψ（2・，2・，…，Zg）｝
が， don t−care でない（Xl， x2，…， x・）において成立 しているとき，これをf（X）の単分解といい，（φ，ψ）と 記す。
いま，分割行列M（f：YIZ）の＊に対して，適当な値
（O，1，2，…，m−1のうちのどれか）を代入することによ って，争心重度VをV≦mとすることができれば，（この ようにしてえられる分割行列をM と記す。）この分割行 列M に対応する関数g（x・，x2，…， x・）を考えることが できる。
定理2より明らかにこの9（x1， x2 t…t Xn）は単分解（φ，
ψ）をもつ。またこのg（x・，x2，…， Xn）は don t−care 以外の点では f（X・，X2，…， Xn）＝9（X・． X2・…， X・）で あるから，（φ，ψ）はf（X）の単分解を与える。
これを定理としてつぎに述べておく。
〔定理3〕 don t−care をもつ関数ノωに対して，分割 行列M の列多重度VをV≦mとすることができれば，
f（X）は単分解をもつ。
5．分離でない分割による単分解
n変数関数f（x）のX＝｛x・，x2，…， x・｝に関する分割
YIZ＝＝yi， y2， …yp12i， z2， ・一・， 2g
の重複度をrとすると，
r＝＝（P＋の一n である。
P十q個の変数（Yl， Y2，…，ypレZ1， g2，…，2g）はX＝
（Xl， x2，…，κn）がきまると，これに対応して決定される。
ゆえに，関数λ（x）を
）L（X） ； X一（Yl， Y2， 一一・Yp， 21， 22， …， 2g）
で定義する。
ここで，V＝＝（Yl，Y2，…，Yp，21，22，…，2q）の関数g（の を考える。
まず，9（のの don t−care な点を
（1）v＝（Y1， Y2，…，yp，2・，22，…，2q）がλ（x）に含まれ ないとき，
（2）f（x）自身がすでに don t−care である点xに対 応ずるV（Y・，y2，…， yp，2・，22，…，2g）
として定義する。
そして，これら以外の点では 9（の量∫⑦
とする。
このとき，Yizなる分割はV ・＝｛ン1， Y2，…， yp，21；
22，…Zg｝に関する分離な分割である。
したがって，もし9（のについて分割Yizに関する単 分解が存在すれば，／（X）について分割YIZに関する単 分解が存在することになる。9（のについての単分解を見 出すことは前節の問題と同じである。
6．しきい値回路網への応用
前節までにえた関数の単分解についての結果を利用し て，三値しきい値素子の回路網によって任意の三値論理関 数を回路実現することを考える。
これは，与えられた関数に対してその成分関数がすべて しきい値関数であるような分解を与える事である。
ここで，三値しきい値関数の定義を与えておく。
〔定義5〕n変数の三値論理関数ノ（x） ＝f（Xl，x2，…）Xn）
において，
藤館liii iiili｝（・）
となるような実定数ω・，ω2，…，ωn，：「2，To（T2＞T・）が 存在するときf（x）を三値しきい値関数という。
ただし，ω（X）＝ wlxl Hrw2 x2＋…＋ω・・Xnであり， Wiを重 み，T2， Toをしきい値という。
以下，つぎのごとき問題を考える。
すなわち，q：≧2なる正整数qを与えて，すべての成分 関数の変数の数がqであり，かつすべての成分関数がしき い値関数であるような，与えられた関数！（X）の分解を求 める。しかも成分関数の個数が最小となるようにする。
これをア（x）のしきい値関数による最：小回路網実現とい うことにする。
f（X）を単分解の合成として表わしたとき，成分関数の 個数は（3）式で与えられる。したがって，全重複度rが最 小のとき，成分関数の個数も最小になる。
定理1により，もしf（x）の分解がえられると，これと 同じ成分関数を用いた単分解の合成によりこの分解を表わ
しうる。したがって，変数のtw eを与えて，しきい値関数 となるq変数の成分関数によるア（X）の単分解を作成する 過程を続け，全重複度rを最小にする分解をうると，これ がf（X）のしきい値関数による最小回路網実現となる。
以下に実現の手順を述べる。
三値n変数論理関数f（X）と成分関数の変数の数qが与 えられているとする。
（1）P＝n−q ＝Oならば，与えられたf（x）自身がしき い値関数であるかどうかを判定する。＊
＊判定の手法については文献13）を参照。
（2）n＞qならば，まずX＝伽，κ2，…，Xn｝に対して 分離な分割ylz「＝y・， y2，…， ypi9・，22，…， Zgを考え
る。
このような分割（第二次数がeである）をすべて考え，
Y1】Z1， y2iZ2，…， YilZtとする。
最初の分割から単分解が存在するかどうかを調べる。
YiIZiの分割行列を作り，列多重度vがv≦3かどうかを 調べる。v≦3ならば，定理2より単分解が存在する。もし，
v＞3ならば，単分解は存在しないのでつぎの分割ア2iz2 にうつる。このようにして，いまゴ番目の分割YiIZ，を調 べているとする。分割行列の列多重度μがv≦3であると する。すべての可能な単分解を作り
（O， a；e）ii， （（P， aPn）i2， …， （ip， th）irn
とする。
（3）（2）でえた単分解について最初のものから，ψがしき い値関数かどうかを調べる。もし，しきい値関数でなけれ ばつぎの単分解（φ，ψ）・2にうつる。すべての単分解につ いてψがしきい値関数でなければ（2）におけるつぎの分 割yi＋・IZi＋1にうつる。
いま，（φ，ψ）ijについて調べているとする。そして，こ のψがしきい値関数であるとする。
このとき，φはP＋1個（P＝n−4；第一次数）の変数の 関数であるが，つぎの二つの場合を考えうる。
（i） P十1：E｛q （ii） P÷1〈q （i）の場合
φもまたしきい値関数であるかどうかを調べる。もしそ うでなければ，つぎの単分解（φ，ψ）i，j＋・にうつる。
いま，φがしきい値関数であるとする。P＋1；qのとき は、この単分解（φ，ψ）iiが！（X）の回路実現を与える。
また，P＋1〈qの場合には，すべての成分関数の変数 の数をqにするために，Pt・， Y2，…， yp， yp＋エの後に，
yp＋2， yp＋3，…，Yqまでの変数を考え，かつすべてyp＋・に 等しくしたφ（Y・，Y2，…， yp， yp＋1，…， Yq）を考えてお くと，単分解（φ，ψ）ijがf（X）の回路実現を与える。＊
（ii）の場合
φはP＋1個の変数の関数であるから（2）以下の手順で nをP＋1におきかえ，同じ操作を行う。
（4）全重複度7が最小のとき最小回路実現を与えるか ら，成分関数がしきい値関数である単分解のうち，rが最 小となるようなものを求めて，それらの合成でf（X）を表 わすとよい。したがって，（3）までの手順で，すべて分離 な分割ばかりで単分解が求まるとそれが最小回路実現を与 える。
いまもし，分離な分割のすべてについてしきい値関数に よる単分解が存在しなければ，重複度が1である分割にっ
いて考える。この分割行列については，4， 5節で述べた ごとく＊の所に0，1または2を代入することによって，
列多重度vをv≦3とすることができると単分解が存在す るので，それらを求めて（2），（3）の手順と同様な操作を 行う。
なお，定理2の証明から明らかであるが，v≦；3の場合 に単分解を求めるとき，その成分関数の決め方は必ずしも 一意的でない。ゆえに，一つの分割に対して単分解が二つ 以上存在するかも知れない。したがって，成分関数がしき い値関数となる場合が二通り以上存在するかも知れない。
このときは，それらをすべて求めて，全重複度rが最小と なる分解を求めることが必要である。
（5）重複度が1である単分解の合成で最小回路実現がえ られないときは，これを2，3，…として，これまでと同 様な操作をくりかえす。
しきい値関数系は完全系であるから，14）必ず有限回でこ の手順は完了し，最小回路実現がえられる。
7．例 題
しきい値回路網実現の手順をくわしく説明するために，
いくつかの例題を考える。．
（1）f（κ1，x2）＝＝x1Vκ2＝max（κ1， x2） を考える。
（Table 2）
Table 2 q＝2とする。
XiVX2 o xl 1
X2 0 1 2 0 1 2 1 1 2
2i222
f（X・，X2）自身は明らかにしき い値関数でない。
したがって，まず重複度r；1 の分割Xtlx1，κ2を考える。分 割行列はつぎの通りである。
（Table 3）
Table 3
X XIX2途＼＼
012
oo
0＊＊
O1
61＊＊
02
2＊＊
10
＊−占＊
11
＊ーム＊
12
＊2＊
20
＊＊2
21
＊＊2
22
＊＊2
いま，この行列の＊に対してっぎのように値を代入す
るQ（T3ble 4）
Table 4
＼＼ｭ X2
Xi ×
＊付録1参照
012
oo
0ーワU
O1
122
02
222
10
012
11
AUーウ一
12
122
20
012
21
012
22
012
すると，列多重度vはv ・3となる。そして，ψ＝ψ（x！，
x2）なる成分関数として第1行によって定義されるものを えらぶ。（Fig．2）
Xユ2
tO 2）
（ol）
coo）
v，
ψ薯1
l12）
P
｛2a
（Il， 21，
（T O）
Fig．2
sl，
o
o
o
C20） Xt
2 2 2
1 2
o 1
22
X Xa
Fig．3 X
このψは明らかにしきい 値関数である。
たとえeg，Wi ＝一1，w2 ＝1，
T2・・2， T・＝Oとすればよ
い。
これで単分ee f・ （φ，ψ）
＝φ｛X1，ψ（κ1，X2）｝をうる が，φはFig．3のごとくな り，たとえば，κ1の重み Wl＝1，ψの重みw2＝：1，
しきい値T2＝2， To＝0と して，しきい値関数であ
る。
したがって，／（Xl， x2）
の回路実現はFig．4とな
る。
これが最小回路実現であ ることは明らかである。
この例は三値論理和とい XJ l
一1 f
窟 多6．
置 ％ Ψ
Fig． 4
われるものの実現であるが，すでに相原らによって具体的 なしきい値素子実現が与えられている。15）いまえられたも のは素子の数はこれと同じであるが，入力の接続数が一つ 少なくてすむ。
（2）f（xユ， x2）として三値NAM）16）といわれるつぎのも Table 5 のを考える。（Table 5）
いま，
甲羅i侶i
の二つの値の与え方を考えると，このψ（X・，X2）はしきい 値関数としうる。たとえば，Fig．5のごとくするとしきい 値関数である。
Xl 2
Ψ・2
2 2
2 1
Fig．5 2
1
O殉
ところが，分割行列の第 3行の要素が1，2，0の順 になっているので，φ（x1，
ψ）を作ると，φはunate でない。ゆえにしきい値関 数でない。13）
したがってrr＝1の分解 はありえない。つぎにr ＝2 を考える。
X2
0 1 2
分害［」 x・，x21x・， x2の分割行列は対角要素のみが （1， 1， 1， 1， 2， 2， 1， 2， O）
で，他はすべて＊である。
いま，＊に対してTable 7のごとく値を代入すると，
v＝2ケ年り，たとえば行列の第1行でもってψ・＝ψ・（x・，x2）
を定義する。このとき，ψiはつぎのごとき重み，しきい 値でもってしきい値関数となる。
wi＝：一1． w2＝一1． T2＝＝1． To＝：一4 一 vv一 N−t
，
これで単分解（φ・，ψ・）＝φ・｛X・，X2，ψ・（X・， X2）｝をう る。
NAND
012
ユ 1201221占11占
Table 7
XtX2 XIX2
q＝2とする。f（x・，x2）は明 らかにしきい値関数でない。
r＝1の分割Xilx・，x2を考える。
分割行列はつぎの通り。
（Table 6）
Table 6
012012012000111222
oo
11112212＊
O1
11112212＊
02
11112212＊
X1
10
11112212＊
11
11112212＊
12
11112212＊
2e
11112212＊
21
11112212＊
22
0＊＊＊＊＊＊＊0
XIX2
012
oo
−＊＊
O1
14＊＊
02
−占＊＊
10
＊−凸＊
11
＊2＊
12
＊2＊
20
＊＊−凸
21
＊＊2
22
＊＊0
つぎに（x・，x2， Vi）に関する分割x・1x2，ψ・を考え る。（重複度＝0）
分割行列はつぎの通り。（Table 8）
行列の＊に対してつぎのごとく値を代入する。（Table 9）
Table 8
渋012 oo0＊＊ Ol−ゐ11凸 02＊＊＊ 10＊＊＊ 11122 12＊＊＊ 20＊＊0 21﹂12＊ 22
与える。
（3）3変数関数∫（x・，x2， x3）としてつぎのものを考え る。（Tabie 10）
＊＊＊
Xl X2 X3
Table 9
Xl X2 1
01凸9耐
oo
000
Ol
噌■−占−
02
122
10
000
11
122
12
122
20
000
21
129個
22
ーム22
明らかに列多重度v ・3である。第3行でもって，
ψ2（X2，ψ1）を定義するとψ2はつぎのごとくなる。
（Fig． 6）
012012012000111222000000000
Table 10
ア
Xl X2 X3
叱2
011112222 012012012000111222111111111 f Xt X2 X3111112222 012012012000111222222222222 ノ122222222
匙 Ψ曙2
1 2
0 o
Fig． 6 も 1 2
2
2
OZIJX
これは，たとえば，
ω1＝1（κ2の重み）
w2＝4（ψ1の重み）
T2＝5， To ＝2として，し きい値関数となる。また，
単分解φ2α・，ψ2）はつぎ のごとくなる。（Fjg． 7）
したがって，φ2は ω1＝1（κ1の重み）
ω2＝4（ψ2の重み）
T2＝9， T。＝・2としてしき い値関数となる。
ゆえに，
f（Xi， X2）
＝＝ ￠2［Xl｝ th2 ｛XZ，
aPnl（Xl， X2， ｝］
なる分解をうる。回路実現 はつぎの通り。（Fig．8）
q ＝2とする。重複度0の分割は
xllx2， x3， X2iXl， X3， X31xl， X2，
の三つ存在するが，まずX・lX2， X3 を考える。
分割行列はつぎの通り。（Table 11）
Table 11
Xl X2×3
01幽9伊
oo
011
O1
11凸2
02
112
10
112
11
ーヨー2
12
222
20
222
21
222
22
222
trin2
1
o
i
o Fig． 7
Xt 凹1
齢Ix匙
Xa 10ｩ
舷鴇
監一 4
X
おY2
一一 4
f
Fig． 8
しきい値素子の個数は（S）
s＝r十1
であるが，r＞1であるから， s＝3が最：小回路実現であ る。したがって，いまえられた回路実現は最小回路実現を
列多重度v；3である。いまψ（x2， x3）として，第1行 kfi
X31 2 2
2
2 ×2 Fig． 9
v．g．2 一．．2・
i 1
O 8
﹁
1
o 8
Fig． 10
x 2
をえらぶ。ψ（x2， xのはた とえば，
Wl ＝・2（x2の重み）
w2 ＝1（x3の重み）
T2＝4， Te＝＝Oとしてしき い値関数である。（Fig．9）
このとき単分解（φ，ψ）
はφ｛x・，ψ（κ2，x3）｝となる
が，． eig．10で与えられる。
これは，
w、・＝1（Xlの重み）
w2＝2（ψの重み）
T2＝4， To＝0としてしき い値関数である。回路実現 はつぎの通り。（Fig．11）
X2 2
X3
A奄T＞iJ xt
2
Fig． 11
f
素子の個ta Sは
r n−1
S＝ffS：．：irl＋一4：一：11
において，n＝3， e＝2であるから
s＝ r＋2：｝12
ゆえに，2個の素子による実現は，明らかに最小回路実 現である。
8．結 論
本報告の前半において，多値論理関数をより簡単な関数 の合成によって表わす，いわゆる関数の分解についての理 論を展開した。これは，二値論理関数について，Ashenhurst，
Huらによってえられたものの多値論理への一般化であ
る。
後半においては，前半でえられた定理を用い，三値しき い値素子でもって，任意の関数を実現する手法を与えた。
変数の数が多くなると，単分解が存在するかどうかを調 べる手順の回数が多くなるが，（特に重複度が0でないと き）最後に与えた例題でもわかるように，この手法は，三 値論理関数の最小しきい値回路網実現において，十分有力 なるものといいうる。
なお，本論文の内容は，京都大学数理解析研究所におけ る研究集会「多値論理およびその応用層」（1971・7）にお いて発表したものであるが，その講演予稿を提出した後 に，本論文のr定理2〕と同様なものが文献17）において も発表されている事を見出した。しかし，本論文の〔定理 2〕はそれとは全く独立にえられたものである。
付 録
1・一般につぎのことが成立する。すなわち，P＋1個 の変数の関数がしきい値関数であるとする。このとき，変 数y・，Y2，…， yp， yp＋1に対して， q個の変数ン1， V2，…，
Np， yp＋・，み＋2，…，西を考え，かつみ＋1・＝Yp＋2＝…鵠鈎と しておくと，q個の変数の関数φ（y・，ン2，…， yp＋1，…，
Yg）もまたしきい値関数となる。理由はつぎのごとく考え るとよい。
P＋1個の変数の関数をφ （y・，Y2，…， yp＋・）とする。
そして，yt， Y2，…， yp＋1の重みをW・， W2，…，Wp， tVp＋1 とする。
これに対して，ω1＝ω 1，zv2・＝ω，z，…，ωP＝w p
Wp＋1＝W p＋1＋wtp＋2＋．．．＋wtg
となるようなωt・，ω 2s…ω p， W p＋・，…，ω gを考える。
このとき，
な サ
Σω iyi・・ΣW iyi＋ω P＋・ツP＋・＋ω P＋2ツ叶2＋…＋ω q夕q
i置1
i＝1
り＝Σωiyi＋（ω ，＋・＋〃，＋2＋…＋W q）ツP＋・
i冒1
P P十1 冨Σωiyi＋Wp＋1ンP＋1講Σωiyi
i属1 i＝1
をうるので，4変数関数φ（），・，Y2，…Yp＋・，…， Yg）は，
φ （ン1，y2，…］p， Yp＋1）と同様にしきい値関数となる。
文 献
1） W．H．Hanson： Ternary threshold logic． IEEE Trans． EC−12 （1963） p．191
2） R．Merrill： Some properties of ternary threshold logic． IEEE Trans． EC−13 （1964） p．632
3） J． Santos， H． Arango and F． Lorenzo： Threshold synthesis of ternary digital systems． IEEE Trans．
EC−15 （1966） p．105
4） R． D． Merrill ： Symmetric ternary switching func−
tions IEEE Trans EC−16 （1967） p．624
5）相原，高松； 三値論理関数のしきい素子による二段 実現 昭和45年度電子通信学会全国大会予稿集
（1970） p．45
6） R． L． Ashenhurst： The decomposition of switching functions． Annals Harvard Computational Labora−
tory， 29 （1959） p．74
7 ） S． T． Hu： On the decomposition of switching func−
tions． Lockheed Missiles and Space Division， Tech．
Rep． 6−90−61−15 （June， 1961）
8） S． T． Hu ： Threshold logic， （1965） p．256 University of California Press．
9） ibid， p．274 10） ibid， p．277 11） ibid， p．278 12） ibid， p．283
13）三根久，藤田志郎： 三値しきい値関数の判定と実現 について， 電子通信学会論文誌（C），53−C，7，（昭 45−07） p．439
14）藤田米春，他＝ 多値しきい値論理関数系の完全性 電子通信学会論文誌（C），53・C，5（昭45−05）P．341 15）相原恒博，片岡正次郎： しきい素子による三値論理 和（積）ゲートの実現法， 電子通信学会論文誌（C）．
52−C，2（昭44−02）P．122
ユ6）田中末雄，田原道夫： 三値論理関数の完全性とPoly−
Pheck， 電子通信学会論文誌（C），53−C，2（昭45−2）p．111 17） K． M． Waliuzzaman and Z． G． Vranesic： On deco一 ・mposition of multi−valued switching functions Computer Journa1， 13，4（November 1970） p．359
