読者です 読者をやめる 読者になる 読者になる

健全性と完全性

健全性と完全性の説明

ある特徴・性質cを満たす出力を生成するために提案・構築された手法Mがある。Mが健全(sound)であるとは、Mのいかなる出力oが目的とする特徴・性質cを必ず満たしていることを言う。Mが完全(complete)であるとは、検討している世界において、特徴・性質cを満たすすべての事柄を集めた集合をScとしたとき、Mの出力を集めた集合SmとScが等しくなることを言う。

概念の利用例:アンチウィルスソフトウェア

アンチウィルスソフトウェアは少なくとも健全でなければならない、完全であるならば申し分ない。

アンチウィルスソフトウェアとは、インストールされているマシンに対して保存されるファイル、あるいは、マシン上で起動されるプログラムがウィルスソフトウェアであるかどうかをチェックし、ウィルスソフトウェアであるならば、それをマシンの利用者に通知し、マシン上で起動されることがないようにすることが目的である。

アンチウィルスソフトウェアが健全であるとは、アンチウィルスソフトウェアによって「ウィルスソフトである」と判断されたファイルはすべて、ウィルスソフトであるということである。アンチウィルスソフトウェアが健全でないとは、アンチウィルスソフトウェアによって「ウィルスソフトである」と判断されたファイルが、実はウィルスソフトではないことがありえるということである。

アンチウィルスソフトウェアが完全であるとは、存在するすべてのウィルスソフトを検知できるということである。完全でないとは、検知できないウィルスソフトが存在するということである。

実際のところ、アンチウィルスソフトウェアは健全でない(ウィルス判定されたファイルがウィルスでないことがある)し、完全でもない(ウィルスは日々製作されているため、ウィルスの定義ファイルの定期更新が必要とされている)。

概念の利用例2:めんくい

健全なめんくいは貞節である可能性があるが、完全なめんくいは浮気者である。

あなたがめんくい(美女/美男子が大好物)として健全であるというのは、あなたが恋愛感情を抱く相手は、常に美女/美男子であるということである。あなたがめんくいとして完全であるというのは、すべての美女/美男子に恋愛感情を抱くということである。

論理体系における健全性と完全性(直観的説明)

  • ある論理体系において、その体系の統語論において得られる定理が、必ず意味論においても定理であるとき、その論理体系を健全であるという。
  • ある論理体系において、その体系の意味論における定理が、必ず統語論においても定理であるとき、その論理体系を完全であるという。