(57)【特許請求の範囲】
【請求項１】
コンピュータが実行する論理関数評価方法であって、
連続する１以上のバイナリ変数で１つの次元が表されており、前記次元毎の第１の論理関数の解で表される連続した範囲が入力される範囲入力手順と、
任意のＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）又はＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）で表される第２の論理関数が入力される関数入力手順と、
前記範囲入力手順で入力された前記範囲に含まれる第１の論理関数の解それぞれについて前記関数入力手順で入力された前記ＢＤＤの最上位節点から辿り、第２の論理関数の「真」を表す最終節点に到達するパスの有無を判断する判断手順と、
を行う論理関数評価方法。
【請求項２】
前記判断手順は、全ての前記次元について、
前記ＢＤＤの節点ｘｉにおいて、前記次元における開始節点ｘ１から直前節点ｘｉ−１までのパス値“ｘ１ｘ２・・・ｘｉ−１”に節点ｘｉの各枝の値“０”又は“１”を付与して節点ｘｉまでのパス値“ｘ１ｘ２・・・ｘｉ−１ｘｉ”を形成し、それぞれがｉ番目の前記バイナリ変数までで表される前記範囲に含まれるか否かを確認する確認ステップと、
前記確認ステップで、パス値“ｘ１ｘ２・・・ｘｉ−１０”が前記範囲に含まれている場合、節点ｘｉの“０”枝の先にある節点を識別させ、該節点に該パス値を保存し、パス値“ｘ１ｘ２・・・ｘｉ−１１”が前記範囲に含まれている場合、節点ｘｉの“１”枝の先にある節点を識別させ、該節点に該パス値を保存するパス保存ステップと、
を行うこと特徴とする請求項１に記載の論理関数評価方法。
ただし、ｉは２以上の整数である。
【請求項３】
連続する１以上のバイナリ変数で１つの次元が表されており、前記次元毎の第１の論理関数の解で表される連続した範囲を記憶部に入力する範囲入力部と、
任意のＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）又はＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）で表される第２の論理関数を記憶部に入力する関数入力部と、
前記記憶部に入力された前記範囲に含まれる第１の論理関数の解それぞれについて前記記憶部に入力された前記ＢＤＤの最上位節点から辿り、第２の論理関数の「真」を表す最終節点に到達するパスの有無を判断するアルゴリズム実行部と、
を備える論理関数評価装置。
【請求項４】
前記アルゴリズム実行部は、全ての前記次元について、
前記ＢＤＤの節点ｘｉにおいて、前記次元における開始節点ｘ１から直前節点ｘｉ−１までのパス値“ｘ１ｘ２・・・ｘｉ−１”に節点ｘｉの各枝の値“０”又は“１”を付与して節点ｘｉまでのパス値“ｘ１ｘ２・・・ｘｉ−１ｘｉ”を形成し、それぞれがｉ番目の前記バイナリ変数までで表される前記範囲に含まれるか否かを確認する確認手段と、
前記確認手段での確認で、パス値“ｘ１ｘ２・・・ｘｉ−１０”が前記範囲に含まれている場合、節点ｘｉの“０”枝の先にある節点を識別させ、該節点に該パス値を保存し、パス値“ｘ１ｘ２・・・ｘｉ−１１”が前記範囲に含まれている場合、節点ｘｉの“１”枝の先にある節点を識別させ、該節点に該パス値を保存するパス保存手段と、
を有すること特徴とする請求項３に記載の論理関数評価装置。
【請求項５】
請求項１又は２に記載の論理関数評価方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、与えられた２つの論理関数に共通する解の存否について評価する論理関数評価方法、論理関数評価装置及びそのプログラムに関する。
【背景技術】
【０００２】
論理関数とは、バイナリ変数（ｘｉ∈｛０，１｝、０あるいは１のいずれかの値をとる変数）のベクトルを引数とし、┬（真）あるいは┴（偽）のいずれかの値を返す関数である。バイナリベクトルを｛ｘ｝＝ｘ１ｘ２・・・・とすると、ｆ（｛ｘ｝）∈｛┬、┴｝となる。例えば、ｆ（｛ｘ｝）＝┐（ｘ１∧ｘ２）という論理関数は、図９のｆ（ｘ）の欄のようになる。ここで、∧は論理積（ＡＮＤ）、∨は論理和（ＯＲ）、┐は否定を表す。また、本明細書では“｛  ｝”はベクトルを意味するものとする。
【０００３】
２つの論理関数が与えられると、それらに対してＡＮＤやＯＲなどの論理演算を行うことができる。例えば、ｇ（｛ｘ｝）＝ｘ１∨ｘ２とすると、ｆ（｛ｘ｝）∧ｇ（｛ｘ｝）＝┐（ｘ１∧ｘ２）∧（ｘ１∨ｘ２）となる。
【０００４】
ＢＤＤ（ｂｉｎａｒｙ  ｄｅｃｉｓｉｏｎ  ｄｉａｇｒａｍ）は、論理関数を表現するデータ構造である。図１ａは、論理関数ｆ（｛ｘ｝）＝┐（ｘ１∧ｘ２）を表すＢＤＤである。バイナリベクトルの値に従ってＢＤＤを上から下へ辿ると、論理関数の値がわかる。具体的には、根節点（最上位節点）からスタートし、節点が表す変数の値が０のときは点線を辿り、１であれば実線を辿る。最終的に「真」を表す節点「┬終端節点」あるいは「偽」を表す節点「┴終端節点」に到達したら、それが論理関数の値である。図の例で説明すると、｛ｘ｝＝１０（Ｘ１＝１，Ｘ２＝０）のとき、太線に従ってＢＤＤを辿ると、┬終端節点に辿り着く。
【０００５】
ＢＤＤを使って論理演算を実行する手法は非特許文献１に記載される。２つのＢＤＤに対し、論理演算を実行し、演算結果の論理関数を表す別のＢＤＤを出力する。つまり、ｆ（｛ｘ｝）のＢＤＤとｇ（｛ｘ｝）のＢＤＤがあれば、演算アルゴリズムによってｆ（｛ｘ｝）∧ｇ（｛ｘ｝）を表すＢＤＤを構築できる（図１ｃ）。演算アルゴリズムの説明は省略する。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｒ．Ｅ．Ｂｒｙａｎｔ，“Ｇｒａｐｈ−Ｂａｓｅｄ  Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｂｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎ  Ｍａｎｉｐｕｌａｔｉｏｎ”，  ＩＥＥＥ  Ｔｒａｎｓ．  Ｃｏｍｐｔ．，  Ｖｏｌ．Ｃ−３５，  Ｎｏ．８，  ｐｐ．６７７−６９１，１９８６．
【発明の概要】
【発明が解決しようとする課題】
【０００７】
論理関数を┬にするバイナリベクトルの値を「解」と呼ぶことにする。２つの論理関数が与えられたとき、共通する解の有無を知りたいことがある。この問いに答えるには、ＡＮＤ演算を行い、演算結果の論理関数が解を持つことを調べればよい。ＢＤＤを用いる場合、ＡＮＤ演算を実行し、そのＢＤＤに┬終端節点へのパスが存在することを調べればよい。しかし、知りたいことは共通解の有無だけにも関わらず、このアプローチは演算結果の論理関数そのものを計算しており、計算量が多いことが課題となっている。
【０００８】
そこで、本発明は、上記課題を解決すべく、与えられた２つの論理関数に共通する解の有無を知るための計算量を低減できる論理関数評価方法、論理関数評価装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明に係る論理関数評価方法、論理関数評価装置及びプログラムは、第１の論理関数が各次元の範囲を規定しており、第２の論理関数が任意のＢＤＤで表されている場合に、第２の論理関数のＢＤＤのレベルごとに上から順に、第１の論理関数が規定する範囲に含まれるパスを探索し、「真」を表す最終節点に到達するパスが存在すれば、共通解が存在すると判定することとした。
【００１０】
具体的には、本発明に係る論理関数評価方法は、
コンピュータが実行する論理関数評価方法であって、
連続する１以上のバイナリ変数で１つの次元が表されており、前記次元毎の第１の論理関数の解で表される連続した範囲が入力される範囲入力手順と、
任意のＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）又はＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）で表される第２の論理関数が入力される関数入力手順と、
前記範囲入力手順で入力された前記範囲に含まれる第１の論理関数の解それぞれについて前記関数入力手順で入力された前記ＢＤＤの最上位節点から辿り、第２の論理関数の「真」を表す最終節点に到達するパスの有無を判断する判断手順と、
を行う。
【００１１】
ここで、前記判断手順は、全ての前記次元について、
前記ＢＤＤの節点ｘｉにおいて、前記次元における開始節点ｘ１から直前節点ｘｉ−１までのパス値“ｘ１ｘ２・・・ｘｉ−１”に節点ｘｉの各枝の値“０”又は“１”を付与して節点ｘｉまでのパス値“ｘ１ｘ２・・・ｘｉ−１ｘｉ”を形成し、それぞれがｉ番目の前記バイナリ変数までで表される前記範囲に含まれるか否かを確認する確認ステップと、
前記確認ステップで、パス値“ｘ１ｘ２・・・ｘｉ−１０”が前記範囲に含まれている場合、節点ｘｉの“０”枝の先にある節点を識別させ、該節点に該パス値を保存し、パス値“ｘ１ｘ２・・・ｘｉ−１１”が前記範囲に含まれている場合、節点ｘｉの“１”枝の先にある節点を識別させ、該節点に該パス値を保存するパス保存ステップと、
を行うこと特徴とする。
ただし、ｉは２以上の整数である。
【００１２】
また、本発明に係る論理関数評価装置は、
連続する１以上のバイナリ変数で１つの次元が表されており、前記次元毎の第１の論理関数の解で表される連続した範囲を記憶部に入力する範囲入力部と、
任意のＢＤＤ（Ｂｉｎａｒｙ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）又はＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）で表される第２の論理関数を記憶部に入力する関数入力部と、
前記記憶部に入力された前記範囲に含まれる第１の論理関数の解それぞれについて前記記憶部に入力された前記ＢＤＤの最上位節点から辿り、第２の論理関数の「真」を表す最終節点に到達するパスの有無を判断するアルゴリズム実行部と、
を備える。
【００１３】
ここで、前記アルゴリズム実行部は、全ての前記次元について、
前記ＢＤＤの節点ｘｉにおいて、前記次元における開始節点ｘ１から直前節点ｘｉ−１までのパス値“ｘ１ｘ２・・・ｘｉ−１”に節点ｘｉの各枝の値“０”又は“１”を付与して節点ｘｉまでのパス値“ｘ１ｘ２・・・ｘｉ−１ｘｉ”を形成し、それぞれがｉ番目の前記バイナリ変数までで表される前記範囲に含まれるか否かを確認する確認手段と、
前記確認手段での確認で、パス値“ｘ１ｘ２・・・ｘｉ−１０”が前記範囲に含まれている場合、節点ｘｉの“０”枝の先にある節点を識別させ、該節点に該パス値を保存し、パス値“ｘ１ｘ２・・・ｘｉ−１１”が前記範囲に含まれている場合、節点ｘｉの“１”枝の先にある節点を識別させ、該節点に該パス値を保存するパス保存手段と、
を有すること特徴とする。
【００１４】
１つの次元が連続する１以上のバイナリ変数で表され、次元毎の第１の論理関数の解が連続した範囲で表せる場合、上述のように計算することで、従来の論理計算より簡単に共通解の有無を調べることができる。従って、与えられた２つの論理関数に共通する解の有無を知るための計算量を低減できる論理関数評価方法及び論理関数評価装置を提供することができる。
【００１５】
本発明に係るプログラムは、前記論理関数評価方法をコンピュータに実行させるためのプログラムである。本発明に係る論理関数評価方法はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【発明の効果】
【００１６】
本発明は、与えられた２つの論理関数に共通する解の有無を知るための計算量を低減できる論理関数評価方法、論理関数評価装置及びプログラムを提供することができる。
【図面の簡単な説明】
【００１７】
【図１】ＤＢＢの例を説明する図である。（ａ）は論理関数ｆの例、（ｂ）は論理関数ｇの例、（ｃ）は論理関数ｆ∧ｇの例である。
【図２】論理関数の解を次元と座標で表現した例である。解が連続範囲である場合である。
【図３】論理関数の解を次元と座標で表現した例である。解が不連続な範囲である場合である。
【図４】本発明に係る論理関数評価方法のアルゴリズムを説明する図である。
【図５】本発明に係る論理関数評価方法で最初の次元の処理を説明する図である。（ａ）は最上位節点での処理であり、対応する範囲は［０，１］である。（ｂ）は最上位節点の次位にある節点での処理であり、対応する範囲は［０１，１０］である。
【図６】本発明に係る論理関数評価方法のアルゴリズムを説明する図である。論理関数が多値関数の場合である。
【図７】本発明に係る論理関数評価方法の判断手順を説明するフローチャートである。
【図８】本発明に係る論理関数評価装置を説明する構成図である。
【図９】論理演算結果を説明する表である。
【発明を実施するための形態】
【００１８】
添付の図面を参照して本発明の実施形態を説明する。以下に説明する実施形態は本発明の実施形態であり、本発明は、以下の実施形態に制限されるものではない。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。
【００１９】
一般には、２つの論理関数の共通解の有無を調べることと、演算を実行して論理関数を計算することとの計算量は変わらない。しかし、演算される一方の論理関数が「簡単な」形をしているとき、本発明を用いることで、より簡単に２つの論理関数の共通解の有無を調べることが可能になる。
【００２０】
ここで、論理関数が「簡単な」形とは、次の２つの条件をともに満たしている場合である。一方の論理関数が簡単であればよく、他方の論理関数は任意である。
Ａ．連続するいくつかのバイナリ変数は１つの「次元」を表すとする。
Ｂ．各次元における解は、連続した範囲を表す。
【００２１】
まず、条件Ａを説明する。例えば、６つのバイナリ変数｛ｘ｝＝ｘ１，１ｘ１，２ｘ１，３ｘ２，１ｘ２，２ｘ２，３があり、３つずつを組にして２つの次元を表すとする。１つ目の次元はｘ１，１ｘ１，２ｘ１，３であり、２つ目の次元はｘ２，１ｘ２，２ｘ２，３である。各次元の最小値と最大値は０００と１１１（十進数では０と７）になる。
【００２２】
次に、図２を用いて条件Ｂを説明する。２つの次元をｘ、ｙ軸で表し、論理関数の解となる座標に色を付ける。各次元が１つの連続した範囲によって指定されていれば、解を表す領域は必ず１つの矩形αになる。より次元数が多ければ１つのｈｙｐｅｒｃｕｂｅとなる。なお、各次元が１つの連続した範囲ではなく、より複雑な方法で指定されていると、論理関数の解を表す領域は１つの矩形ではなくなる。例えば、ｘ軸を［１，２］および［３，４］という不連続な範囲によって指定すると、図３のように１つの矩形としては表現されなくなる。図３のような場合、論理関数は条件Ｂを満たしていない。
【００２３】
条件Ｂを満たせば、論理関数は「各次元における範囲」として表現できる。そこで、以降では「範囲の集合」として表すことにする。例えば、図２の矩形αは、１つ目の次元の範囲を１から５とし、２つ目の次元を２から４とする領域である。以降、このような矩形を（［１，５］，［２，４］）のように表す。
【００２４】
もう１つの論理関数はＢＤＤとして与えられ、次元上の範囲としては任意の形状をとる（例えば、図２の領域β）。なお、この座標表現で共通解の有無を考えるときは、２つの論理関数の解領域に重なりがあるかどうかをみればよい。図２では、座標（５，３）と（５，４）が重なっている。図２では、この重複領域を領域γで示している。
【００２５】
（アルゴリズムの全体像）
＜範囲入力手順及び関数入力手順＞
図４を用いて、アルゴリズムの全体像を説明する。条件Ａ、Ｂを満たす第１の論理関数の範囲（［１，２］，［０，１］）と、第２の論理関数である図４のＢＤＤが与えられている。ここでは、｛ｘ｝＝ｘ１，１ｘ１，２ｘ２，１ｘ２，２のように２つずつのバイナリ変数からなる２つの次元を考える。
【００２６】
＜判断手順＞
ＢＤＤを次元ごとに分割し、上から順に処理を進める。まず、１つ目の次元において、範囲に含まれるすべてのパスを赤で塗りながら辿り、２つ目の次元の開始節点まで進む。なお、図面では赤く塗られたことを太線で示している。この例では、３つの次元の開始節点ｘ２，１のうち、１つだけが赤くなっている。続いて２つ目の次元を処理するが、赤く塗られていない開始節点は、共通解の候補から外れたため無視して構わない。赤の開始節点のみを起点として、同じ処理を繰り返す。この処理を繰り返し、最終的に┬終端節点を赤で塗れれば、共通解があるということになる。このように、演算結果のＢＤＤを構築することなく、共通解の有無のみを知ることができる。
【００２７】
（各次元での処理）
１つの次元に含まれるバイナリ変数をｍ個とすると、最大の範囲は２ｍとなる。よって、ｍが大きくなると、辿らなければならないパスの数が指数関数的に増えてしまい、現実的な時間では終わらなくなる。そこで、１つの枝を複数回辿ることがないような辿り方を考える。
【００２８】
ある１つの次元について考える。その次元が満たすべき範囲と、起点となる開始節点が与えられているとする。ここまで、バイナリ変数の番号を「次元番号と次元内での番号の組合せ」ｘｄ、ｉで表現してきたが、以降、次元番号を無視してｘｉのように記す。範囲の下限と上限を［ｌ１ｌ２・・・、ｕ１ｕ２・・・］とする。例えば、範囲［０００，０１０］や範囲［００１，１００］である。
【００２９】
判断手順の詳細を説明する。
現在、パスがある節点に到達しているとし、その節点の変数番号をｘｉとする。また、この節点に至るまでのパスの値ｘ１・・・ｘｉ−１を覚えているとする。複数のパスを経由して到達可能な節点については後述する。ここから０枝を辿ると、パスの値はｘ１・・・ｘｉ−１０になり、１枝を辿るとパスの値はｘ１・・・ｘｉ−１１になる。ここで、対応する範囲として、ｉ番目の変数までで表される［ｌ１・・・ｌｉ、  ｕ１・・・ｕｉ］を考える。パスの値ｘ１・・・ｘｉ−１０がこの範囲に含まれていれば、０枝の先にある節点を赤く塗る。そして、赤く塗った節点にパスの値ｘ１・・・ｘｉ−１０を保存する。１枝についてもｘ１・・・ｘｉ−１１というパスの値に対して、同様の処理を行う。すなわち、パスの値ｘ１・・・ｘｉ−１１がこの範囲に含まれていれば、１枝の先にある節点を赤く塗り、赤く塗った節点にパスの値ｘ１・・・ｘｉ−１１を保存する。なお、節点ｘｉが当該次元の最終レベルである場合、枝の先にある次の次元の開始節点あるいは終端節点を赤く塗り、パスの値を保存する。
【００３０】
同じ節点に枝が合流し、かつその節点が赤く塗られていない場合は、範囲の境界に一致するパスの値を覚えておく。つまり、ｘ１・・・ｘｉ＝ｌ１・・・ｌｉあるいはｘ１・・・ｘｉ＝ｕ１・・・ｕｉとなるｘ１・・・ｘｉを優先して覚えておく。赤く塗られていないということはまだ範囲に含まれておらず、境界上にあるか外れているかのいずれかである。範囲から外れているパスは共通解が無いことを意味するから、境界に一致するパスのみを保存しておけば十分である。
【００３１】
この処理を、ＢＤＤのレベルごとに上から順に行う（例えば、幅優先探索の順序で行う）ことで、赤く塗られるべきパスを漏れなく塗ることができる。
【００３２】
図５の例で説明する。まず、ｘ１，１の節点を処理するときは、０／１いずれの枝も範囲に含まれるため各枝を赤く塗る（図５ａ）。続いて、ｘ１，２の各節点についても同様に処理を行うと図５ｂのようになる。
【００３３】
上記説明では節点状態の識別として「色」で表現したが、実際のプログラムではフラグなどの変数によって表現する。また、ここまで関数は┬あるいは┴の２値のみを取るとして説明を行ったが、本発明に係る論理関数評価方法のアルゴリズムは３値以上を取る多値関数に対しても同様に動作する。例えば、図６は、Ｉ、ＩＩ、┴という３値関数を表す場合のＢＤＤに相当するＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ  Ｄｅｃｉｓｉｏｎ  Ｄｉａｇｒａｍ）を説明する図である。ＭＤＤの場合も、図４及び図５で説明したアルゴリズムを実行して終端節点まで色を塗り、┴以外の赤く塗られたすべての終端節点（図６の例ではＩＩ）を返せばよい。
【００３４】
（フローチャート）
図７は、図４及び図５で説明したアルゴリズムを表すフローチャートである。
本論理関数評価方法は、
連続する１以上のバイナリ変数で１つの次元が表されており、前記次元毎の第１の論理関数の解で表される連続した範囲が入力される範囲入力手順（ステップＳ０１）と、
任意のＢＤＤ又はＭＤＤで表される第２の論理関数が入力される関数入力手順（ステップＳ０１）と、
前記範囲入力手順で入力された前記範囲に含まれる第１の論理関数の解それぞれについて前記関数入力手順で入力された前記ＢＤＤの最上位節点ｘ１から辿り、第２の論理関数の「真」を表す最終節点に到達するパスの有無を判断する判断手順（ステップＳ０２）と、を行う。
【００３５】
判断手順は３つのルーチン（Ｒ１１，Ｒ１２，Ｒ１３）から構成される。
前記判断手順は、全ての前記次元についてルーチンＲ１２とＲ１３を行う（ルーチンＲ１１）。なお、ｄは任意の自然数、ｉは２以上の自然数、ｊは１以上ｉ以下の自然数である。
ルーチンＲ１３において、
前記ＢＤＤの節点ｘｉにおいて、前記次元における開始節点ｘ１から直前節点ｘｉ−１までのパス値“ｘ１ｘ２・・・ｘｉ−１”に節点ｘｉの各枝の値“０”又は“１”を付与して節点ｘｉまでのパス値“ｘ１ｘ２・・・ｘｉ−１ｘｉ”を形成し、それぞれがｉ番目の前記バイナリ変数までで表される前記範囲に含まれるか否かを確認する確認ステップと、
前記確認ステップで、パス値“ｘ１ｘ２・・・ｘｉ−１０”が前記範囲に含まれている場合、節点ｘｉの“０”枝の先にある節点を識別させ、該節点に該パス値を保存し、パス値“ｘ１ｘ２・・・ｘｉ−１１”が前記範囲に含まれている場合、節点ｘｉの“１”枝の先にある節点を識別させ、該節点に該パス値を保存するパス保存ステップと、
を行う。
ルーチンＲ１３の「次の節点がある？」はＢＤＤの同レベルの節点の存在の有無を確認することである。例えば、図４のＢＤＤであれば、節点ｘ１，２は２つあり、節点ｘ２，１は３つある。同レベルにあるそれぞれの節点についてルーチンＲ１３が行われる。
【００３６】
ルーチンＲ１３が終了すると、ルーチンＲ１２を行う。ルーチンＲ１２は同一次元において下位レベルへ移動すること、つまり図４の節点ｘ１，１から節点ｘ１，２へ辿る動作や節点ｘ２，１から節点ｘ２，２へ辿る動作を説明している。下位レベルへ移動すると対応する範囲が変わる。具体的には、図５に示すようにステップＳ２１において、節点ｘ１，１で対応する範囲が［０，１］であったが、下位レベルの節点ｘ１，２では対応する範囲が［００，０１］に更新され、さらに下位レベルの節点へ移動したときには、対応する範囲が［００１，０１０］に更新される。
【００３７】
そして、本論理関数評価方法は、全ての次元についてルーチンＲ１１の終了後、ステップＳ２５で┬（真）の終端節点が赤く塗られているか否かを回答する。赤く塗られていれば、第１の論理関数と第２の論理関数との共通解が存在することを意味する。なお、第２の論理関数がＭＤＤであれば、本論理関数評価方法は、ステップＳ２５において、┴（偽）以外の赤く塗られたすべての終端節点を回答する。
【００３８】
（装置構成図）
図８は、図７で説明した論理関数評価方法を実施できる論理関数評価装置３０１の構成図である。論理関数評価装置３０１は、範囲・ＢＤＤ入力部１０１、記憶部１０２及びアルゴリズム実行部１０３を備える。範囲・ＢＤＤ入力部１０１は、図７のステップＳ０１を行ない、記憶部１０２に範囲及びＢＤＤを記憶させる。アルゴリズム実行部１０３は、記憶部１０２から範囲及びＢＤＤを取り出して図７のステップＳ０２を行う。そして、アルゴリズム実行部１０３は、結果として共通解の有無、つまり┬（真）あるいは┴（偽）を出力する。もし入力が多値関数（ＭＤＤ）であれば、┴以外の赤く塗られたすべての終端節点を出力する。
【００３９】
図７で説明した動作をさせるプログラムをコンピュータで実行させることで、コンピュータを論理関数評価装置３０１として動作させることができる。範囲・ＢＤＤ入力部１０１は、コンピュータの入力装置（キーボードや外部インターフェース等）であり、記憶部１０２はメモリ（ＤＲＡＭ）であり、アルゴリズム実行部１０３は中央処理装置（ＣＰＵ）である。計算結果は、モニタに表示されてもよいし、外部インタフェースを介して外部記憶装置に記憶されてもよい。
【００４０】
（発明の効果）
各次元における範囲を表す論理関数と、任意の論理関数が与えられたとき、それらのＡＮＤを計算することなく共通解の有無を判定することができる。これによって、計算時間およびメモリを節約できる。実験的に、２〜１０倍程度の高速化を確認している。
【産業上の利用可能性】
【００４１】
本発明は、論理関数として表現可能なデータを操作する技術（アルゴリズム）である。本発明は特定の応用技術分野に限定されない。次のようにネットワーク技術に適用することができる。パケットヘッダが表すビット列（バイナリベクトル）に対し、ファイアウォールのアクションを論理関数と見なす。本稿の後半で「次元」という言葉が出てくるが、これはパケットヘッダの各フィールド（アドレスやポート番号）を指している。例えば、いわゆる５−ｔｕｐｌｅ（送受信アドレス、送受信ポート番号、プロトコル種）でパケットを扱うときは、５次元空間を考える。本発明は、ネットワーク技術において、アドレス・プレフィックスやポート番号の範囲によって指定される単純な領域と、任意の論理関数が表す複雑な領域に、「重なり」があるか否かを調べることができ、従来よりも効率的に共通解の有無を知ることができる。
【符号の説明】
【００４２】
１０１：範囲・ＢＤＤ入力部
１０２：記憶部
１０３：アルゴリズム実行部
３０１：論理関数評価装置
【図１】
0006388856.tif 000002
【図２】
0006388856.tif 000003
【図３】
0006388856.tif 000004
【図４】
0006388856.tif 000005
【図５】
0006388856.tif 000006
【図６】
0006388856.tif 000007
【図７】
0006388856.tif 000008
【図８】
0006388856.tif 000009
【図９】
0006388856.tif 000010