充足問題 その１

さて、前回は簡単二進数とブール代数について説明しました。今回は充足問題について説明しましょう。今日は、ちょっと気合いが入ってるから、つまらない冗談は抜きです多分。そうじゃないかな。ま、ちょっと覚悟はしておけ（（ｃ）さだまさし）

ちなみに、Wikipediaでは充足可能性問題（http://ja.wikipedia.org/wiki/充足可能性問題）とあるようです。この辺の日本語訳はこれまで通り、いろいろあると思います。一番ポピュラーな、アレな専門用語としてその筋に通じるというのはSATという言い方です。これは英語のsatisfiabilty problemの最初の三文字を大文字SATで表わしてこの問題を指すということになっています。以下、このブログでもSATといいます。

基本的にこの説明は、竹内外史先生の「PとNP」p.10-p11を参考にしています。

最初にいくつか、やや専門的な知識と言葉の定義をします。

まず、基本的な事項の定義です。

　　１．ブール変数と集合

　　　　u1,u2,…,um というm個ブール変数があるとします。

　　　　どれも中身はT（True）かF(False)です。

　　　　書き方を変えると、m個のブール値の集合Uは

　　　　次のように表せますよね。

　　　　　　U=｛u1,u2,…,um｝

　　２．ブール変数の否定形とリテラル（literal)

　　　　　さて、ブール変数の内容は、T（True）かF（False）しか

　　　　　ないのでした。

　　　　　

　　　　　そこで、ブール代数においては、一般にブール変数uが

　　　　　あるとき、その否定を

　　　　　　　　　

　　　　という形式で表わします。

　　　　　　※　しかし、このブログではWeb表記上の問題もあって、

　　　　　　　　いちいち画像にしないといけないのも大変なので

　　　　　　　　意味的には同じ￢uと表わします。

　　　　　　　　その旨はその都度説明します。

　　　　　　　　ご了承ください。

　　　　　さて、このuと￢uをリテラル(literal)という専門用語で

　　　　　呼ぶことにします。literalには文字通り、とか、

　　　　　意味に忠実な、とか、面白くも何ともないとか、

　　　　　そのような意味があるようです。

まあ、数学ですし（笑い）

　　３．節

　　　　　ここでは、節の例を挙げましょう。

　　　　　たとえば、｛u1,u5,￢u8,u9｝のようなものを

　　　　　節という言い方をします。

　　　　　意味的にはu1,u5,￢u8,u9の論理和です。

　　　　　すなわち

　　　　　　　u1∨u5∨￢u8∨u9

　　　　　と同等です。

補足説明をしておくと記号論理学の∨とか∧とか￢は論理記号といいます。ややこしいですね。あと、専門的には∨とか∧とかは、二つの項を持つ演算子なので、二項演算子、￢は一つの項しか持たない演算子という意味で単項演算子と呼びます。

と￢uとの違いは単なる否定の項か、項の否定を単項演算子で表わしてるか、という違いがあるんですね、意味は一緒だけど。本当にややこしい（笑い）

とりあえず、今回はここまでにしておきましょう。見慣れない言葉がたくさん出てきましたから。しかし、「真っ白かその他」の論理的思考のためには、いろいろなことをきっちりと決めておくのが大事なんです。がんばりましょう。