多値論理関数の分解としきい値回路網への応用

多値論理関数の分解としきい値回路網への応用

藤 ^田 志 ^郎＊

（昭和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 ¹

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 ¹

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

ユ 120122^1占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 X3}111112222 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 ⁸

﹁

1

o ⁸

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 ₂

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