特許
J-GLOBAL ID：200903072074641195
論理式の充足可能性判定装置および方法
発明者：
,
,
出願人/特許権者：
代理人 (1件)：
三好 秀和 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平8-105587
公開番号（公開出願番号）：特開平9-293087
出願日： 1996年04月25日
公開日（公表日）： 1997年11月11日
要約：
【要約】【課題】 高速に処理Aと処理Bを行うことにより、高速に論理式の充足可能性判定問題を解くことができる論理式の充足可能性判定装置および方法を提供する。【解決手段】 行方向には変数1を列方向には和項2を対応させた2次元配列に要素回路3を配置し、要素回路3と和項性質回路4と恒真恒偽回路5を用いて、変数集合の部分集合に割り当てられた値に基づいて論理式を簡単化し、その簡単化された論理式が1あるいは0となっているかどうかを判定する処理Aを行い、要素回路3と和項性質回路4と変数性質回路6と変数選択回路7を用いて、もし簡単化された論理式が1あるいは0となっていない場合は、簡単化された論理式の性質をもとにして、まだ値が割り当てられていない変数集合から次に値を割り当てる変数を選択する処理Bを行い、要素回路3の働きは、問題として与えられた和積形論理式に従って変更できる。
請求項（抜粋）：
行方向に変数を対応させ、列方向に和項を対応させた2次元配列形に要素回路を配置した構造を備えた論理式の充足可能性判定装置において、要素回路、和項性質回路および恒真恒偽回路を用いて、変数集合の部分集合に割り当てられた値に基づいて論理式を簡単化し、その簡単化された論理式が1または0となっているかどうかを判定する処理Aを行う手段と、前記要素回路、前記和項性質回路、変数性質回路および変数選択回路を用いて、前記簡単化された論理式が1または0となっていない場合は、前記簡単化された論理式の性質をもとにして、まだ値が割り当てられていない変数集合から次に値を割り当てる変数を選択する処理Bを行う手段と、与えられた和積形論理式に従って前記要素回路の働きを変更するセレクタとを有することを特徴とする論理式の充足可能性判定装置。
IPC (3件)：
G06F 17/50
, G06F 9/44 550
, H03K 19/177
G06F 15/60 654 Z
, G06F 9/44 550 C
, H03K 19/177
, G06F 15/60 664 Z
