(57)【要約】【課題】充足可能性問題はその対象となる式の構造により難易度が変わるが、安定して難易度の高いＳＡＴを構成する手法が存在しなかった。また、ＳＡＴで扱う値は真偽二値であり、三値以上の多値を扱うことのできるＣＮＦＳＡＴが存在しなかった。【解決手段】変数が多値変数と同じような振舞いをするよう制約した多値ＣＮＦを構成することとした。【選択図】図１
2012164295.tif 000002
【特許請求の範囲】
【請求項１】
多値変数について、全ての多値否定変数からなる錯綜目的節、及び多値肯定変数２つからなる開孔関連節の全ての組合せの場合の節により構成される多値ＣＮＦを表すデータが記録されたコンピュータ読み取り可能な記録媒体。
【請求項２】
請求項１において、多値ＣＮＦを、三値ＣＮＦ、四値ＣＮＦ、五値ＣＮＦ、六値ＣＮＦ、七値ＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項３】
請求項１〜２いずれかの項において、多値ＣＮＦを、単数または複数の異なる多値ＣＮＦの論理積となる合成ＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項４】
請求項１〜３いずれかの項において、合成ＣＮＦまたは多値ＣＮＦを、合成ＣＮＦまたは多値ＣＮＦと、ＣＮＦに含まれる多値ＣＮＦの単数あるいは複数の多値肯否変数からなる拘束節との論理積となる合成ＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項５】
請求項４において、拘束節を、３つ以上の多値ＣＮＦそれぞれの多値否定変数１つ以上または多値肯定変数１つを含む節とした、コンピュータ読み取り可能な記録媒体。
【請求項６】
請求項４において、拘束節を、その拘束節を含まない合成ＣＮＦが真となる真理値割当において、その節の値が偽となる節とした、コンピュータ読み取り可能な記録媒体。
【請求項７】
請求項４〜６いずれかの項において、合成ＣＮＦを、ある２つの変数の肯定変数からなる拘束節及び否定変数からなる拘束節の組合せを、そのいずれかの変数について、その肯定変数をもう片方の否定変数に、その否定変数をもう片方の肯定変数にしたＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項８】
請求項４〜７いずれかの項において、合成ＣＮＦを、ある変数の肯定変数とある変数の否定変数からなる拘束節及び同じ変数の肯否を入れ替えた拘束節の組合せを、そのいずれかの変数について、その肯定変数をもう片方の肯定変数に、その否定変数をもう片方の否定変数にしたＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項９】
請求項１〜８いずれかの項において、合成ＣＮＦを、合成ＣＮＦの任意の多値変数の肯否を入れ替えたＣＮＦとした、コンピュータ読み取り可能な記録媒体。
【請求項１０】
請求項１〜９いずれかの項において、データに、ＣＮＥを表すデータに加えて、ＣＮＦが真となる真理値割当を表すデータを追加したデータとした、コンピュータ読み取り可能な記録媒体。
【請求項１１】
請求項１〜１０いずれかの項において、多値ＣＮＦの錯綜目的節を、閉孔節とした、コンピュータ読み取り可能な記録媒体。
【請求項１２】
多値変数について、全ての多値否定変数から変数を１つ取り除いた閉孔節の全ての場合の節、及び多値肯定変数２つからなる開孔関連節の全ての組合せの場合の節により構成される多値ＭＵＣを表すデータが記録されたコンピュータ読み取り可能な記録媒体。
【請求項１３】
請求項１２において、多値ＭＵＣを、三値ＭＵＣ、四値ＭＵＣ、五値ＭＵＣ、六値ＭＵＣ、七値ＭＵＣとした、コンピュータ読み取り可能な記録媒体。
【請求項１４】
コンピュータを下記手段として機能させるためのプログラム。
構成する多値ＣＮＦの条件として、多値の個数または／及び多値変数のデータを受け取り構成部に出力する入力部。
入力部から構成する多値ＣＮＦの条件を受け取り、条件を満たす多値変数を定め、その多値変数全ての組合せの開孔関連節と、全ての多値変数の錯綜目的節を構成し、それらの論理積となる多値ＣＮＦを構成して出力部に出力する構成部。
構成部から多値ＣＮＦを受け取り、データを出力する出力部。
【請求項１５】
請求項１４において、入力部が多値ＣＮＦの個数も追加条件として受け取り構成部に出力し、構成部が多値ＣＮＦに替えて入力部が受け取った個数だけ異なる多値ＣＮＦを含む合成ＣＮＦを構成して出力し、出力部が合成ＣＮＦのデータを出力するプログラム。
【請求項１６】
請求項１４〜１５いずれかの項において、入力部が真となる真理値割当の個数も条件として受け取り構成部に出力し、構成部が、合成ＣＮＦを真とする真理値割当の個数が入力部から受け取った個数になるよう、多値真理値割当で偽となる拘束節を追加した合成ＣＮＦを構成して出力するプログラム。
【請求項１７】
請求項１４〜１６いずれかの項において、入力部が真となる真理値割当も条件として受け取り構成部に出力し、構成部が、合成ＣＮＦを真とする真理値割当が入力部から受け取った真理値割当になるよう、多値真理値割当で偽となる拘束節を追加した上で変数の肯否を変更した合成ＣＮＦを構成して出力するプログラム。
【請求項１８】
コンピュータを下記手段として機能させるためのプログラム。
構成する多値ＭＵＣの条件として、多値の個数または／及び多値変数のデータを受け取り構成部に出力する入力部。
入力部から構成する多値ＭＵＣの条件を受け取り、条件を満たす多値変数を定め、その多値変数全ての組合せの開孔関連節と、全ての多値変数の閉孔節を構成し、それらの論理積となる多値ＭＵＣを構成して出力部に出力する構成部。
構成部から多値ＭＵＣを受け取り、データを出力する出力部。
【発明の詳細な説明】
【技術分野】
【０００１】本発明は、ＣＮＦにおいて多値に対応する真理値割当で真となるＣＮＦのデータ構造、及びコンピュータにてＣＮＦを構成するプログラムに関する
【背景技術】
【０００２】従来、コンピュータでは様々な問題が扱われており、また論理式や充足可能性問題、恒真式問題など論理に関する問題も様々なものが扱われている。【０００３】例えばＳＡＴ（充足可能性問題）は、ＮＰ完全問題として非決定性チューリングマシンというコンピュータの論理的概念と等価であり、その応用範囲も広い。【０００４】ＳＡＴはその制約条件により様々な種類が存在する。特にＣＮＦ（乗法標準形）で構成されたＣＮＦＳＡＴが重要である。ＳＡＴはＣＮＦＳＡＴに変換可能であり（例えば非特許文献２参照）、変換後のＣＮＦは取り扱いが容易となる。【０００５】ＳＡＴは暗号を構成する時の鍵となるため（例えば非特許文献１参照）、ＳＡＴの計算複雑性を効率良く高めることは重要である。また多くのパズルがＳＡＴから生成可能であり、パズルの難易度を調整するという観点からも、ＳＡＴの計算複雑性を効率良く高めることは重要となる。ＣＮＦＳＡＴを暗号の落し戸関数として使用する場合や、パズルの問題の論理的構造として使用する場合は、問題の難易度を高めながら、同時に論理式が真となる真理値割当が存在するようにする必要がある。【０００６】逆に、充足しないＳＡＴ、特にＭＵＣと呼ばれる充足不可の論理式で構成されるＣＮＦＳＡＴも重要である。ＭＵＣはＣＮＦのどの節を取り除いても充足可能になるＣＮＦであり、充足不可となるＣＮＦの節の極小部分となる。ＣＮＦからＭＵＣを構成するのはｃｏＮＰ困難と言うＳＡＴよりも難しいと予想される問題である。また、任意の充足可能なＳＡＴの論理積としてＭＵＣを追加することで、必ず充足不可となるＳＡＴを構成することができる。このため、必ず解けない問題を構成する時などにＭＵＣは便利である。またＭＵＣはＣＮＦＳＡＴが充足しないことを示す証拠となるため、上記のように構成したＣＮＦＳＡＴにおける充足不可の証拠としてＭＵＣを活用することができる。また、ＭＵＣは任意の節を取り除くと充足可能なＣＮＦとなるため、充足可能なＣＮＦを構成するのにも活用することができる。【０００７】しかしＳＡＴはその論理式の構成により計算複雑性が大幅に変化する。特にＣＮＦＳＡＴを暗号の落し戸関数として使用する場合や、パズルの問題の論理的構造として使用する場合は、問題の難易度を高めながら、同時に論理式が真となる真理値割当が存在するようにする必要がある。しかしＳＡＴは構造を複雑にして計算複雑性を高めると充足不可になることが多くなる。よって、安定して計算複雑性の高い充足可能なＳＡＴを効率的に構成するのは困難だった。【０００８】また充足不可のＳＡＴを構成するためにＭＵＣを活用するとしても、ＣＮＦＳＡＴの追加によって変化しない安定したＭＵＣを構成する必要がある。しかし、ＣＮＦＳＡＴを追加しても安定してＭＵＣとなるためにはＭＵＣ自身の構造の効率が高くなくてはならず、そのようなＭＵＣを構成するのは困難だった。また、ＭＵＣは任意の節を取り除くと充足可能なＣＮＦとなるが、そのＣＮＦがどの真理値割当で真となるかは実際に確認しなくては判らなかった。【０００９】また、真偽二値の論理だけではなく、近年は多値論理など三値以上の値を扱う論理も存在する。このような論理は従来の二値を扱う論理よりも多くの場合に対応できるため、技術の適用範囲も広がっており、応用としてファジィ論理などが存在する。【００１０】しかし、多値論理は真偽二値に代わる新しい多値の集合に対する論理を新たに構築しており、真偽二値による論理の技術をそのまま活用できなかった。また、多値による新たな理論は取り扱いの難しい曖昧さも導入するため、真偽二値と比べてもその正確性が良くなかった。
【先行技術文献】
【００１１】
【非特許文献１】「暗号の代数理論」Ｎ．コブリッツ  シュプリンガー・ジャパン社  １９９９年  Ｐ１４３−１６１
【非特許文献２】「オートマトン  言語理論  計算論  ＩＩ」Ｊ．ホップクロフト，Ｊ．ウルマン，Ｒ．モトワニ  サイエンス社  ２００８年  Ｐ１４７−１５５
【発明の概要】
【発明が解決しようとする課題】
【００１２】上記の通り、計算複雑性の高い充足可能なＣＮＦＳＡＴのデータ構造を構成するのは困難だった。そのようなＣＮＦＳＡＴを効率的に構成するプログラムが無かった。ブール式による論理を拡張して多値を実現するデータ構造やプログラムが無かった。【００１３】本発明の解決しようとする課題は、計算複雑性の高いＣＮＦＳＡＴのデータ構造を提供する点にある。またそのようなＣＮＦを用いて取り扱いの容易なＭＵＣのデータ構造を提供する点にある。また計算複雑性の高いＣＮＦＳＡＴを構成するようコンピュータを動作させるプログラムを提供する点にある。またＣＮＦを真にする真理値割当が多値に対応する真理値割当のみになるＣＮＦのデータ構造を提供する点にある。また多値を実現するＣＮＦを構成するようコンピュータを動作させるプログラムを提供する点にある。
【課題を解決するための手段】
【００１４】上記問題を解決するため、本発明では、多値ＣＮＦを含むＣＮＦを表すデータ構造が記録されたコンピュータ読み取り可能な記録媒体とした。なお、多値ＣＮＦとは多値に対応する変数（以下、多値変数と呼ぶ）の真理値割当に含まれる偽が１つの時のみ真となるＣＮＦである。詳細は後述する。【００１５】なお本発明では、肯定リテラルを肯定変数、否定リテラルを否定変数、リテラルを肯否変数と呼び、多値変数も同様に多値肯定変数、多値否定変数と呼ぶ。【００１６】以下に多値ＣＮＦを説明する。多値ＣＮＦは次の二種類の節からなるＣＮＦである。全ての多値否定変数からなる節（この節を錯綜目的節と呼ぶ）、及び多値肯定変数２つからなる節の全ての組合せ（この節を開孔関連節と呼ぶ）。本発明では、多値ＣＮＦを多値ＣＮＦ（Ａ，Ｂ，…）のように表記する。下記に多値ＣＮＦを例示する。【００１７】二値ＣＮＦ（Ａ，Ｂ）＝（¬Ａ∨¬Ｂ）∧（Ａ∨Ｂ）【００１８】三値ＣＮＦ（Ａ，Ｂ，Ｃ）
＝（¬Ａ∨¬Ｂ∨¬Ｃ）∧（Ａ∨Ｂ）∧（Ｂ∨Ｃ）∧（Ｃ∨Ａ）【００１９】四値ＣＮＦ（Ａ，Ｂ，Ｃ，Ｄ）
＝（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｃ∨Ｄ）【００２０】五値ＣＮＦ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）
＝（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ）
∧（Ａ∨Ｂ）∧（Ｂ∨Ｃ）∧（Ｃ∨Ｄ）∧（Ｄ∨Ｅ）∧（Ｅ∨Ａ）
∧（Ａ∨Ｃ）∧（Ｃ∨Ｅ）∧（Ｅ∨Ｂ）∧（Ｂ∨Ｄ）∧（Ｄ∨Ａ）【００２１】六値ＣＮＦ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ）
＝（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ａ∨Ｅ）∧（Ａ∨Ｆ）
∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｂ∨Ｅ）∧（Ｂ∨Ｆ）
∧（Ｃ∨Ｄ）∧（Ｃ∨Ｅ）∧（Ｃ∨Ｆ）∧（Ｄ∨Ｅ）∧（Ｄ∨Ｆ）
∧（Ｅ∨Ｆ）【００２２】七値ＣＮＦ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ）
＝（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ∨¬Ｇ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ａ∨Ｅ）∧（Ａ∨Ｆ）∧（Ａ∨Ｇ）
∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｂ∨Ｅ）∧（Ｂ∨Ｆ）∧（Ｂ∨Ｇ）
∧（Ｃ∨Ｄ）∧（Ｃ∨Ｅ）∧（Ｃ∨Ｆ）∧（Ｃ∨Ｇ）
∧（Ｄ∨Ｅ）∧（Ｄ∨Ｆ）∧（Ｄ∨Ｇ）∧（Ｅ∨Ｆ）∧（Ｅ∨Ｇ）∧（Ｆ∨Ｇ）【００２３】八値ＣＮＦ及びそれ以上の多値ＣＮＦも同様に定義可能である。【００２４】なお一値ＣＮＦを次のようにすることもある。一値ＣＮＦ（Ａ）＝（¬Ａ）【００２５】多値ＣＮＦは、多値変数の真理値割当において、偽の値を２つ以上含むもの、及び全て真となるもので偽となる。多値ＣＮＦが真となるのは多値変数に偽をただ１つ含む真理値割当のみである。また多値ＣＮＦは、このような真理値割当とＣＮＦの真偽の関係を満たすＣＮＦの中で最小であり、多値変数以外の変数を含まないという特徴を持つ。【００２６】また、多値ＣＮＦが真となる真理値割当（以下、多値真理値割当と呼ぶ）の各変数の値（以下、多値真理値と呼ぶ）は、ある多値真理値が偽の時、他の多値真理値が全て真になるという特徴を持つ。そのため、ある多値変数が偽かどうかを確認することで、他の多値変数が全て真になるかを判定することもできる。本発明では、ある多値真理値割当において、他の多値真理値割当での多値変数の値がこの多値真理値割当と全て異なる多値変数を多値真理値割当の開孔変数と呼ぶ。つまり多値ＣＮＦの場合、ある多値真理値割当で否定変数の値が真となる変数が、その多値真理値割当の開孔変数となる。【００２７】ここで、多値真理値割当それぞれを多値の値と対応付けることにより、ＣＮＦによる多値を実現することができる。多値真理値割当は開孔変数と一対一に対応するため、多値の値は、対象となる多値否定変数が真となる値と定めることができる。このように多値を定めることで、多値論理を真偽二値の論理として扱うことができる。【００２８】また本発明では、ＣＮＦを、単数または複数の異なる多値ＣＮＦと、ＣＮＦに含まれる単数または複数の多値ＣＮＦのそれぞれ単数または複数の多値肯否変数からなる節を含むＣＮＦを表すデータ構造とすることがある。このＣＮＦを合成ＣＮＦと呼ぶ。なお簡単のため、単数または複数の多値ＣＮＦの論理積も合成ＣＮＦと呼ぶことがある。【００２９】特に、合成ＣＮＦは下記のＡとＢの条件を満たすＣＮＦとすることがある。Ａ：１つ以上の多値ＣＮＦを含む。Ｂ：ＣＮＦに含まれる多値ＣＮＦのうち１つ以上、特に３つ以上の多値ＣＮＦそれぞれの、多値否定変数１つ以上または多値肯定変数１つを含む節（この節を拘束節と呼ぶ）を含む。【００３０】拘束節は、多値ＣＮＥが真となる多値真理値割当のいずれかにおいて偽となる節である。複数の多値変数を含む場合は、複数の多値真理値割当を組合せた真理値割当のいずれかで偽となる。つまり、多値ＣＮＦは拘束節により真となる多値真理値割当が制限され、全ての多値について自由に真になることができなくなる。結果として拘束節は多値の論理関係を表し、多値はお互いに拘束節により制限を受ける。【００３１】例えば、三値ＣＮＦ１（Ｘ，Ｙ，Ｚ）、三値ＣＮＦ２（Ａ，Ｂ，Ｃ）、三値ＣＮＦ３（Ｐ，Ｑ，Ｒ）が合成ＣＮＦに含まれる場合を考える。この時（Ｘ∨Ａ∨Ｐ）のようなそれぞれの多値の多値変数を含む拘束節が合成ＣＮＦに含まれる場合がある。
合成ＣＮＦ＝三値ＣＮＦ１∧三値ＣＮＦ２∧三値ＣＮＦ３∧（Ｘ∨Ａ∨Ｐ）
この結果、Ｘ、Ａ、Ｐは同時に偽になることができず、その自由度が制限される。【００３２】同様に、（¬Ｙ∨Ａ∨¬Ｐ∨¬Ｑ）のような、多値肯定変数に替えて多値否定変数を１つ以上含む節が拘束節となる場合もある。
合成ＣＮＦ＝三値ＣＮＦ１∧三値ＣＮＦ２∧三値ＣＮＦ３∧（¬Ｙ∨Ａ∨¬Ｐ∨¬Ｑ）
この結果、Ｙ、Ｐ、Ｑが偽かつＡが真に同時になることができず、自由度が制限される。【００３３】また（¬Ｙ∨Ａ）のような、合成ＣＮＦに含まれる多値ＣＮＦのうち一部の多値ＣＮＦにおける多値変数を含む節が拘束節となる場合もある。
合成ＣＮＦ＝三値ＣＮＦ１∧三値ＣＮＦ２∧三値ＣＮＦ３∧（¬Ｙ∨Ａ）【００３４】上記の例の通り拘束節にはさまざまな節があるが、多値真理値割当で偽になる節ということが重要であり、上記の例に限らない。逆に合成ＣＮＦで真となる真理値割当から拘束節を構成することがある。この場合、合成ＣＮＦで真となる真理値割当から任意の変数を取り出し、その真理値割当で偽となる節を構成すれば良い。【００３５】このように合成ＣＮＦを構成することにより、このＣＮＦは充足可能かつ対称性の高い多値変数によりＣＮＦが構成される。また、似たような多値真理値割当でもＣＮＦの真偽が異なるため、絞り込みの困難な計算複雑性の高いＣＮＦとなる。【００３６】なお、任意の変数とは、従来のコンピュータで用いられる方法で選択される多値変数とする。例えばランダムに選択する場合がある。あるいはプログラムであらかじめ定められた値とする場合がある。このように様々な方法があるが、これらの例に限定されない。以降も明示しない場合は同様とする。【００３７】なお、ＣＮＦに（Ｘ∨Ｙ）∧（¬Ｘ∨¬Ｙ）の節を含む多値変数がある場合、充足可否についてＸ＝¬Ｙ、¬Ｘ＝Ｙが成立する。よって拘束節に（Ｘ∨Ｙ）∧（¬Ｘ∨¬Ｙ）が含まれる合成ＣＮＦは、Ｘを¬Ｙに置き換え、¬ＸをＹに置き換え、（Ｘ∨Ｙ）∧（¬Ｘ∨¬Ｙ）を削除した合成ＣＮＦと充足可否が等しい。よって、（Ｘ∨Ｙ）∧（¬Ｘ∨¬Ｙ）のような関係にある拘束節が存在する場合、その節による制約を変数の肯否の制約に置き換えることがある。【００３８】つまり、合成ＣＮＦについて、ある２つの変数の肯定変数からなる拘束節及び否定変数からなる拘束節の組合せを、そのいずれかの変数について、その肯定変数をもう片方の否定変数に、その否定変数をもう片方の肯定変数にしたＣＮＦとする。【００３９】同様に、ＣＮＦに（Ｘ∨¬Ｙ）∧（¬Ｘ∨Ｙ）の節を含む多値変数がある場合、充足可否についてＸ＝Ｙ、¬Ｘ＝¬Ｙが成立する。よって拘束節に（Ｘ∨¬Ｙ）∧（¬Ｘ∨Ｙ）が含まれる合成ＣＮＦは、ＸをＹに置き換え、¬Ｘを¬Ｙに置き換え、（¬Ｘ∨¬Ｙ）∧（¬Ｘ∨Ｙ）を削除した合成ＣＮＦと充足可否が等しい。よって、（Ｘ∨¬Ｙ）∧（¬Ｘ∨Ｙ）のような関係にある拘束節が存在する場合、その節による制約を変数の肯否の制約に置き換えることがある。【００４０】つまり、合成ＣＮＦについて、ある変数の肯定変数とある変数の否定変数からなる拘束節及び同じ変数の肯否を入れ替えた拘束節の組合せを、そのいずれかの変数について、その肯定変数をもう片方の肯定変数に、その否定変数をもう片方の否定変数にしたＣＮＦとする。【００４１】このように、拘束節の制約が全て変数の肯否による制約に変更できる合成ＣＮＦの場合、そのＣＮＦには拘束節が含まれない場合がある。【００４２】なお、拘束節は単独の多値ＣＮＦについても同様に考えることができる。複数の多値ＣＮＦからなる合成ＣＮＦと同様、ある多値ＣＮＦに、全ての多値真理値割当で真とならないＣＮＦを追加した合成ＣＮＦを考えることができる。例えばある多値ＣＮＦの１つの多値肯定変数からなる拘束節や、複数の多値否定変数からなる拘束節などである。【００４３】ただし、単独の多値ＣＮＦに対する拘束節は、��収律により多値ＣＮＦの節の一部を吸収する。例えば、多値肯定変数１つからなる拘束節は、同じ変数を持つ開孔関連節を吸収する。複数の多値否定変数からなる拘束節は、錯綜目的節を吸収する。【００４４】特に、錯綜目的節から１つの多値変数を除いた拘束節は、錯綜目的節を吸収するとともに多値真理値割当のうちただ一つでのみ偽となる。つまり、拘束節とその拘束節を偽にする多値が一対一に対応する。このような節をある多値に対する閉孔節と呼び、閉孔節が偽になる多値真理値割当に対応する開孔変数を閉孔変数と呼ぶ。また、多値ＣＮＦの錯綜目的節を閉孔節に置き換えたＣＮＦもまた合成ＣＮＦと呼ぶ。【００４５】また、ある多値ＣＮＦの錯綜目的節を、全ての多値変数の閉孔節で置き換えたＣＮＦはＭＵＣとなる。このＭＵＣを多値ＭＵＣと呼ぶ。多値ＭＵＣは多値変数の対称性の高いＭＵＣであり、節の追加によりＭＵＣの構造が大きく変わることは少ない。構造が大きく変化するのは、多値肯定変数１つからなる節や、多値否定変数のみからなる節を付加した時に限られる。また、多値ＭＵＣから開孔関連節を削除したＣＮＦは、その削除した開孔関連節に含まれる変数のみが偽で、他の変数が真となる真理値割当でＣＮＦが真になるという特性を持つ。多値ＭＵＣも、多値ＣＮＦと同様に多値ＭＵＣ（Ａ，Ｂ，…）のように表記する。下記に多値ＭＵＣを例示する。【００４６】二値ＭＵＣ（Ａ，Ｂ）＝（¬Ａ）∧（¬Ｂ）∧（Ａ∨Ｂ）【００４７】三値ＭＵＣ（Ａ，Ｂ，Ｃ）
＝（¬Ｂ∨¬Ｃ）∧（¬Ａ∨¬Ｃ）∧（¬Ａ∨¬Ｂ）
∧（Ａ∨Ｂ）∧（Ｂ∨Ｃ）∧（Ｃ∨Ａ）【００４８】四値ＭＵＣ（Ａ，Ｂ，Ｃ，Ｄ）
＝（¬Ｂ∨¬Ｃ∨¬Ｄ）∧（¬Ａ∨¬Ｃ∨¬Ｄ）
∧（¬Ａ∨¬Ｂ∨¬Ｄ）∧（¬Ａ∨¬Ｂ∨¬Ｃ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｃ∨Ｄ）【００４９】五値ＭＵＣ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ）
＝（¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ）∧（¬Ａ∨¬Ｃ∨¬Ｄ∨¬Ｅ）
∧（¬Ａ∨¬Ｂ∨¬Ｄ∨¬Ｅ）∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｅ）
∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ）
∧（Ａ∨Ｂ）∧（Ｂ∨Ｃ）∧（Ｃ∨Ｄ）∧（Ｄ∨Ｅ）∧（Ｅ∨Ａ）
∧（Ａ∨Ｃ）∧（Ｃ∨Ｅ）∧（Ｅ∨Ｂ）∧（Ｂ∨Ｄ）∧（Ｄ∨Ａ）【００５０】六値ＭＵＣ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ）
＝（¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ）∧（¬Ａ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ）
∧（¬Ａ∨¬ＢＶ¬Ｄ∨¬Ｅ∨¬Ｆ）∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｅ∨¬Ｆ）
∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｆ）∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ａ∨Ｅ）∧（Ａ∨Ｆ）
∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｂ∨Ｅ）∧（Ｂ∨Ｆ）
∧（Ｃ∨Ｄ）∧（Ｃ∨Ｅ）∧（Ｃ∨Ｆ）∧（Ｄ∨Ｅ）∧（Ｄ∨Ｆ）∧（Ｅ∨Ｆ）【００５１】七値ＭＵＣ（Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，Ｇ）
＝（¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ∨¬Ｇ）∧（¬Ａ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ∨¬Ｇ）
∧（¬Ａ∨¬Ｂ∨¬Ｄ∨¬Ｅ∨¬Ｆ∨¬Ｇ）∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｅ∨¬Ｆ∨¬Ｇ）
∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｆ∨¬Ｇ）∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｇ）
∧（¬Ａ∨¬Ｂ∨¬Ｃ∨¬Ｄ∨¬Ｅ∨¬Ｆ）
∧（Ａ∨Ｂ）∧（Ａ∨Ｃ）∧（Ａ∨Ｄ）∧（Ａ∨Ｅ）∧（Ａ∨Ｅ）∧（Ａ∨Ｇ）
∧（Ｂ∨Ｃ）∧（Ｂ∨Ｄ）∧（Ｂ∨Ｅ）∧（Ｂ∨Ｆ）∧（Ｂ∨Ｇ）
∧（Ｃ∨Ｄ）∧（Ｃ∨Ｅ）∧（Ｃ∨Ｆ）∧（Ｃ∨Ｇ）
∧（Ｄ∨Ｅ）∧（Ｄ∨Ｆ）∧（Ｄ∨Ｇ）∧（Ｅ∨Ｆ）∧（Ｅ∨Ｇ）∧（Ｆ∨Ｇ）【００５２】また本発明のデータ構造を、多値ごとの多値変数の組合せ及び拘束節を表すデータ構造とすることもある。例えば上記の例だと、｛Ｘ，Ｙ，Ｚ｝、｛Ａ，Ｂ，Ｃ｝、｛Ｐ，Ｑ，Ｒ｝、（Ｘ∨Ａ∨Ｐ）、（¬Ｙ∨Ａ∨¬Ｐ∨¬Ｑ）のように、多値変数の組と節が識別可能になっており、さらにそれぞれの変数の構成（及び肯否）がわかるようにしたデータ構造とすることがある。このようなデータ構造から、それぞれの多値ＣＮＦを構成し、拘束節を構成し、それぞれの論理積を構成することで合成ＣＮＦを構築できる。なお、多値が１つだけの場合や、拘束節を含まない場合も同様である。【００５３】本発明では、データ構造を単にＣＮＦを表現するデータ構造だけにするのではなく、ＣＮＦが真となる真理値割当も追加したデータ構造とすることもある。【００５４】またＣＮＦや真理値割当を表現するデータ構造を従来のコンピュータで用いられる構造とする場合もある。バイナリ列や節を配列やテーブルなどの構造とする場合もある。また変数番号の偶数奇数で変数の肯定否定を定める構造もある。あるいはＣＮＦや真理値割当の省略形を表すデータ構造などの場合もある。また暗号の鍵として使用する場合は、ＣＮＦや真理値割当に難読化が施されたデータ構造となる場合もある。また暗号の落し戸関数となる場合は、任意のＮＰ検索問題から多項式の集合を構成することができるため（例えば非特許文献１参照）、そのようにしてＣＮＦを多項式化したデータ構造となる場合もある。このように様々なデータ構造があるが、これらの方法に限定されない。また、特に明記しない限り他のＣＮＦや真理値割当を表すデータ構造も同様とする。【００５５】また本発明では、上記の多値ＣＮＦや合成ＣＮＦの任意の変数の肯否を入れ替えたＣＮＦのデータ構造とすることがある。このようにすることで、ＣＮＦの変数の構成から多値ＣＮＦを類推することを困難にすることができる。この場合、上記の多値ごとの多値変数の組合せ及び拘束節を表すデータ構造は、多値変数の肯否で多値ＣＮＦの肯否の入れ替えを示すことがある。例えば｛¬Ｘ，Ｙ，Ｚ｝、｛Ａ，¬Ｂ，Ｃ｝、｛Ｐ，Ｑ，¬Ｒ｝、（¬Ｘ∨Ａ∨Ｐ）、（¬Ｙ∨Ａ∨¬Ｐ∨¬Ｑ）の場合、三値ＣＮＦ１（Ｘ，Ｙ，２）のＸの肯否を入れ替えたＣＮＦと、三値ＣＮＦ２（Ａ，Ｂ，Ｃ）のＢの肯否を入れ替えたＣＮＦと、三値ＣＮＦ３（Ｐ，Ｑ，Ｒ）のＲの肯否を入れ替えたＣＮＦが合成ＣＮＦ含まれる。また拘束節も同様にＸの肯否が入れ替わっている。【００５６】また本発明では、プログラムを、上記の多値ＣＮＦをコンピュータに構成させるために、コンピュータを下記手段として機能させるためのプログラムとした。
構成する多値ＣＮＦの条件として、多値の個数または／及び多値変数のデータを受け取り構成部に出力する入力部。
入力部から構成する多値ＣＮＦの条件を受け取り、条件を満たす多値変数を定め、その多値変数全ての組合せの開孔関連節と、全ての多値変数の錯綜目的節を構成し、それらの論理積となる多値ＣＮＦを構成して出力部に出力する構成部。
構成部から多値ＣＮＦを受け取り、データを出力する出力部。【００５７】コンピュータは多値ＣＮＦの情報を入力として受け取ると、まずは多値変数の設定を行う。入力に多値変数の個数が含まれている場合は、その個数と合うように多値変数を選択し設定する。あるいは、入力に構成する多値変数自体が含まれている場合はその多値変数を構成する多値ＣＮＦの多値変数として設定する。あるいは入力に多値変数と多値変数の個数が含まれている場合は、その多値変数に新たに任意の多値変数を追加して、多値変数の個数が一致するように多値変数を設定する。あるいは入力に多値変数と追加する多値変数の個数が含まれている場合は、その多値変数に指定された数だけ新たに任意の多値変数を追加して多値変数を設定する。あるいは入力に多値変数や多値変数の総数に関する情報が含まれない場合は、任意の個数の任意の多値変数を設定することもある。【００５８】なお、上記の任意の多値変数及び多値変数の個数の設定方法は、従来のコンピュータで用いられる方法とする。例えばランダムに選択する場合がある。あるいはプログラムであらかじめ定められた値とする場合がある。このように様々な方法があるが、これらの例に限定されない。以降も明示しない場合は同様とする。【００５９】次に、設定した多値変数で構成される多値ＣＮＦを表すデータ構造を作成する。多値ＣＮＦは上記のＣＮＦである。多値変数の個数に合わせて多値ＣＮＦを構成する。そして、このように構成したＣＮＦのデータを出力する。【００６０】また本発明では、上記の合成ＣＮＦを複数組合せた合成ＣＮＦを出力することがある。この場合、入力に合成ＣＮＦの個数を表す情報が含まれることがある。【００６１】また本発明では、上記の合成ＣＮＦに拘束節を追加した合成ＣＮＦを出力することがある。この場合、入力に拘束節の条件を表す情報が含まれることがある。【００６２】例えば、合成ＣＮＦに含まれる真理値割当のうち、真にする（あるいは偽とする）個数が含まれる。合成ＣＮＦを真にする多値真理値割当は、それぞれの多値ＣＮＦの多値真理値割当を組合せた真理値割当から、拘束節が偽となる真理値割当を取り除いたものとなる。よって、合成ＣＮＦを真にする真理値割当が入力で指定された個数になるように拘束節（この拘束節は、複数の任意の多値の任意の多値変数で構成されている）を構成し、論理積として組合せて出力する。またこの場合、合成ＣＮＦを真にする真理値割当のデータ構造を合わせて出力することもある。【００６３】また別の例として、合成ＣＮＦが唯一真となる１つの真理値割当が拘束節の条件として含まれることがある。この場合、真理値割当に対応する変数が多値変数として指定されたと考えることができるため、上記の多値変数が指定された場合と同様に合成ＣＮＦを構成する。そして真理値割当が１つのみで真になるということは、上記の真となる真理値割当の個数を１つと指定されたと考えることができるため、上記の真理値割当の個数を指定された場合と同様に合成ＣＮＦを構成する。そして、合成ＣＮＦを真とする真理値割当と入力として与えられた真理値割当を比較し、真偽が異なる変数について、合成ＣＮＦの変数の肯否を入れ替える。このようにすることで、合成ＣＮＦは入力で指定された真理値割当のみで真となるＣＮＦとなる。【００６４】また本発明では、多値ＣＮＦに替えて多値ＭＵＣに対応するデータ構造を構成して出力することがある。この場合、多値ＣＮＦを構成する代わりに多値ＭＵＣを構成し、そのデータ構造を出力する。【００６５】例えば、合成ＣＮＦに含まれる多値ＣＮＦの個数が含まれる。この場合、前述の方法でこの個数だけ合成ＣＮＦを作成し、論理積として組合せて出力する。【００６６】あるいは、入力に多値変数自体が含まれる場合は、その多値変数がどのような集合に分られるかがわかるようになっていることがある。例えば多値変数がＡ、Ｂ、Ｃ、Ｄの場合、｛Ａ，Ｂ｝，｛Ａ，Ｃ，Ｄ｝，｛Ａ，Ｂ，Ｃ｝，｛Ｃ，Ｄ｝，｛Ｂ，Ｄ｝のように、多値変数の組合せがわかるようになっている。この場合、この多値変数の組合せごとに合成ＣＮＦを作成し、論理積として組合せて出力する。【００６７】また、入力に合成ＣＮＦの個数を示す情報が含まれない場合もあるが、その場合は任意の個数の合成ＣＮＦを構成し、論理積として組合せて出力する。【００６８】また本発明では、上記の合成ＣＮＦや多値ＭＵＣの任意の変数の肯否が入れ替わったＣＮＦに対応するデータ構造を出力することがある。
【発明の効果】
【００６９】本発明により、多値の構造の複雑性を活用した複雑性の高い合成ＣＮＦを構成することが可能となり、結果として計算複雑性の高いＣＮＦＳＡＴのデータ構造を実現できた。また、そのような計算複雑性の高いＣＮＦＳＡＴを構成するようコンピュータを動作させることが可能となった。また本発明により、ＣＮＦを真にする真理値割当が多値に対応する真理値割当のみになるＣＮＦのデータ構造を実現することができた。また、多値を実現するＣＮＦを構成するようコンピュータを動作させることが可能になった。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施形態の一例を示す構成図である。
【発明を実施するための形態】
【００７１】以下に本発明の実施形態の一つについて説明する。
【００７２】本データ構造はＣＮＦとして表される。一値から七値までの多値ＣＮＦは前述の通りである。また、八値ＣＮＦより大きな多値ＣＮＦも同様に構成できる。
【００７３】また、複数の異なる多値ＣＮＦから構成される合成ＣＮＦや、拘束節を含むＣＮＦの例も前述の通りである。
【００７４】多値ＭＵＣの構成もそれぞれ前述の通りとなる。
【００７５】以下に本発明の別の実施形態の一つについて、図面に基づき説明する。図１は本発明のプログラムの構成図である。
【００７６】本プログラムは以下の構成となる。構成するＣＮＦの条件を表すデータを受け取る入力部１１１。入力部１１１から受け取ったデータを元に、合成ＣＮＦを構成する構成部１１２。合成ＣＮＦを表すデータを出力する出力部１１３。
【００７７】入力部１１１の詳細を説明する。入力部１１１はメモリ、ストレージ、ＩＯ、他のプログラムなど、通常のコンピュータで使用される入出力部からの入力を受け取る。受け取る入力には、多値の個数、多値変数、多値ＣＮＦの個数、真となる真理値割当の個数、真となる真理値割当、などが含まれる。あるいは、出力として多値ＣＮＦではなく多値ＭＵＣを出力する指定が含まれる場合がある。入力部１１１はこれらのデータを受け取ると、構成部１１２にデータを出力する。
【００７８】構成部１１２の詳細を説明する。構成部１１２は、入力部から条件を示すデータを受け取ると、まず条件に合致するように多値変数の集合を構成する。次にそれぞれの多値変数の集合について多値ＣＮＦを構成し、その論理積として合成ＣＮＦを構成する。また、条件に多値ＭＵＣを出力することが指定されている場合は、多値ＣＮＦではなく多値ＭＵＣを構成する。そして、真となる真理値割当の個数が指定されている場合は、合成ＣＮＦを真とする真理値割当で偽となる拘束節を合成ＣＮＦに追加し、真となる真理値割当の個数が条件と一致するように調整する。また、真となる真理値割当が指定されている場合は、まず合成ＣＮＦに拘束節を追加して合成ＣＮＦが真となる真理値割当が１つになるように調整し、その後合成ＣＮＦの変数の肯否を変更してその真理値割当が入力から受け取った真理値割当と一致するようにする。
【００７９】構成部１１２は、合成ＣＮＦ／多値ＣＮＦ／多値ＭＵＣを上記のように構成すると、出力部１１３に出力する。
【００８０】なお合成ＣＮＦを出力する際に、真となる真理値割当も出力することがある。
【００８１】出力部１１３の詳細を説明する。出力部１１３は、構成部１１２からＣＮＦや真理値割当のデータを受け取り、他のプログラムなど通常のコンピュータで使用される入出力部への出力を行う。他のプログラムには通常の表示プログラムや演算プログラムなど、様々なプログラムが存在する。変換したデータには、変換結果だけではなく、変換で使用した変数や節の対応関係、データ作成の途中で生成したデータなどを含むことがある。
【産業上の利用可能性】
【００８２】前述の通り、計算複雑性の高いＣＮＦＳＡＴを構成するＣＮＦを得ることができるようになった。また、多値として扱うことのできる多値変数を含む多値ＣＮＦを構成することができるようになった。
【符号の説明】
【００８３】１１１  入力部
１１２  構成部
１１３  出力部
【図１】
2012164295.tif 000003