充足問題 その２

さて、前回は様々な定義をしてきました。もう一つ重要なことを定義しておきましょう。それは、真理関数という奴です。

　４．真理関数

　　　前回m個のブール値の集合を

　　　　　U=｛u1,u2,…,um｝

　　　と表せるとしましたが、このm個のブール値の集合、

　　　言い換えれば、m個のブール変数UをTかFへ対応する関数tを、

　　　真理関数と言います。これまでの数学っぽい書き方だと

　　　　　t：U　→　｛T,F｝

　　　ですね。

もしかして、そろそろ、充足問題について説明してることを忘れてしまう人もいるかと思います。ようやく、今回の充足問題を説明するための最後の定義です。

　５．充足

　　　真理関数 t：U　→　｛T,F｝が節｛l1,l2,…lk｝を充足することを

　　　　　　t(li) ＝T

　　　となるようなliが｛l1,l2,…lk｝のなかに存在することと定義する

　　　とします。否定のリテラルの定義きちんとするようです。

　　　つまり、リテラルli=¬uiの形式のときは以下のようになります。　　　　　　

　　　　　

　　　ここまでは、関数ｔの要素が単独の節についての定義でしたが、

　　　節の集合についても定義をしておきます。

　　　　「いま、Cを集合U上の節c1,…,crの集合とするときに、

　　　　　真理関数tが節の集合Cのすべての元、節c1,…,crを

　　　　　充足することとする」

　　　となります。

　　　節の時は一つのリテラルを満たせば良かったのですが、

　　　節の集合になると、

　　　真理関数tがその節の集合の元をすべて満たす、

　　　というところがちょっとややこしいですよね。

さて、ようやく充足問題を説明しようかという段階に入りました。

しかし、風呂に入りたいので今回はここまで（笑い）