充足問題について その前に

Cookの定理を説明する前に、どうしても説明しないといけないものが、充足問題と言うものです。前回の最後に、「Cookの定理を簡単に説明しておくと、クラスNPに属する充足問題というものがNP完全であるということを証明するというものです。」と書きました。まず、その充足問題を今回から説明したいと思っているのですけど………。

実は、充足問題というものを説明するその前に、いくつか少しだけ専門的な知識を説明しておかなければいけませんでした。がちょーん。めんどうくさいなぁ、もう。この辺りからそろそろ、たくさん読者を無くすと思うんですよねぇ。はぁ。

さて、そうは言っても説明しておかないといけません。ブール代数（Wikipedia：http://ja.wikipedia.org/wiki/ブール代数）と二進数の計算。どう違うかもふくめてぼちぼち説明しましょう。

二進数から行きますか。われわれが、ふだん数を数えたりするのに使ってるのは10進数ですね。数の数え方として1～9を一桁目、9を超えると桁上がりします。つまり10になる。二進数は0と1だけで数を数えます。0の次が1つぎは桁上がりして10。同じ10でも、桁上がりが違えば、表記は同じでも内容が全然違いますね。2進数はコンピュータで使われている数の表現方法です。0か1かで表わされます。ちなみに、時間は24進数で桁上がりが1日というわけ。で、7日になれば1週間。ま、月はそれぞれの月によって違いますが、1年はほぼ、365日ですから365進数、で、1秒は60秒で1分だから60進で。いい加減にしろ、私（笑い）

いやぁ、つい安易なところに流されてしまいました。しかし、7とか24とか60とかには意味があると言えばあるらしい（笑い）7は1桁で一番大きな素数だし、24のほうはは、だいたい一日は12時間で昼と夜の時間に分かれますが、12というのは2,3,4,6で割りきれるかららしいです。10台の数で、一桁の整数で一番割れる数が多いらしい。で、60というのは更にそれに5が加わりますよね。あ、また、雑談で道草食って（笑い）

まぁ、生活に密接してる日時なんていうのはそういうわけで、割り切れないようで割り切れる理由があるわけですね（笑い）

さて、二進数に戻りましょうか。二進数は先に言ったように桁上がりが、いいや、さっき言ったし、説明終わり（笑い）単に、桁上がりが多いだけです。それが電気的なオンとオフでコンピュータで使うのに適した数の表現です。ちなみに、手の指を器用に曲げたり伸ばしたりできる人なら、片手で31まで数えられます。0も入れれば32個の数を数えられる。単純な分だけ便利というわけ。

ところで、ブールさん（Wikipedia：http://ja.wikipedia.org/wiki/ジョージ・ブール）という変わった数学者がまだコンピュータなんて影も形もない19世紀にいたのですが、この人は0と1だけで考える数学というものを一人で発展させました。それで、ブール代数というわけ。当時はほとんど相手にされなかったのですが、コンピュータ全盛の現代ではブール代数を知らない人間はおそらく民主党のそれも仕分け大臣ぐらいというぐらい有名になっちゃいました。いかに基礎研究が大事だという見本のような人です。ホント、頼みますよ、蓮舫さん、スパコン。

さて、ブール代数は二進数より更に簡単と言えば簡単です。何せ桁が一桁、桁上がりがありません。

きちんとした、ブール代数の演算の定義はWikipedia（http://ja.wikipedia.org/wiki/ブール代数）を見て頂くとして、たとえば、ブール代数では足し算、かけ算が次のようになります。

　　0+0=0,　0+1=1,　1+0=1,　1+1=1

　　0×0=0,　0×1=0,　1×0=0,　1×1=1

これだけです。これが何の役に立つかと思えば役に立つんですねぇ、これが。たとえば、コンピュータで正しいか正しくないかという、いわゆる論理演算を考えるとき。

　論理演算もしくは記号論理の世界では一般に、上のブール代数　0をF（False）、1をT（True）と置き換えて足し算もOR（記号論理では∨）、かけ算もAND（記号論理では∧）とすると上の足し算、かけ算の式はこうなりますね　

　　T∨F=F,　F∨T=T,　T∨F=T,　T∨T=T

　　F∧F=F,　F∧T=F,　T∧F=F,　T∧T=T

アレな専門用語としては、OR,ANDをそれぞれ論理和、論理積とも言ったりします。これに、否定をあらわすNOT（￢）も付け加えるのがちょっと違うだけ。

一応、NOTも説明しておくと

　　￢T=F

　　￢F=T

です。

いろいろ、説明していくと切りがないのですが、ブール代数というものがだいたい分かって頂いたでしょうかね。ブール代数も集合論から出ているのでANDやORの記号∧、∨も集合の和と積の記号∩、∪と似ていますよね。

あともう一つ（笑い）。まだあるのかとか言わないように。雑談の方が長い位なんだから（笑い）で、えっと、なんでしたってけ？そうそう。ブール変数というものを話をしておくと、ブール変数の中身は、FかTかのどちらかしか値がありません。そういうもんです（笑い）それだけ。やっとこさ、おしまいです。