Java で論理を記述する

まず、値を持つ論理式を LogicNode という形で定義してやる。

    public class LogicNode {
	    public boolean value(){ return true; } ;
	    
    }

この value は、LogicNode のSub class で上書きされるはず。なので、これはabstract class として定義しても良い。あるいは、LogicNode を interface として定義しても良い。でも、ここでは、単純な親クラスとして定義してやろう。

どういうテストが通って欲しいかをまず考える。

    M(a)= T, M(b)=F

で、

    M( a ∧ b )

を計算するテストを考えよう。

    import java.*;
    public class LogicNodeTest {
	    
	    static public void main(String args[]) {
		    LogicNode a = new VariableNode("a",true);
		    LogicNode b = new VariableNode("b",false);
		    LogicNode e = new AndNode(a,b);
		    
		    System.out.println(e.value());
	    }
    }

こんな感じか? 変数a, b に対しては、名前と値を持てば良い。値は、boolean と決めて付けているが、本当は拡張性があった方が良い。

    public class VariableNode extends LogicNode {
	    public String name;
	    public boolean value;
	    
	    public VariableNode(String _name, boolean _value) {
		    name = _name;
		    value = _value;
	    }
	    public String name() {
		    return name;
	    }
	    public boolean value() {
		    return value;
	    }
    }

というような感じか。値を設定するaccessor methodもあった方が良い。

∧を表すノードは、以下のようになる。M(a∧b)=M(a)∧M(b) に対応する部分がどこかが自明にわかるはずだ。

    public class AndNode extends LogicNode {
	    LogicNode left;
	    LogicNode right;
	    
	    public AndNode(LogicNode left0,LogicNode right0) {
		    left = left0;
		    right = right0;
	    }
	    public boolean value() {
		    return left.value() && right.value();
	    }
    }

残る課題は、NotNode, OrNode の実装だ。

与えられた論理式のModelを見つけるためには、以下のようなプログラムを作れば良い。

    for interpretation (論理式中のすべての引数の値の組み合わせ) {
	interpretation に対して論理式の意味を計算
	もし、意味が真なら Model として表示
    }

これだと、状態を持たないといけないので、少し面倒。でも、この方が綺麗。

簡単に、すべての引数の値の組合せを得るには、再帰呼び出しを使うのが良い。

    interpretation(論理式e, 変数のリスト L) {
	if (L がnull) {
	    intepretation が設定されたので、eを処理する
	    retun;
	}
	a を最初の変数とする
	a を T にセット
	interpration(e, 残りの変数のリスト);
	a を F にセット
	interpration(e, 残りの変数のリスト);
    }

さぁ、あとは、これを Java で書くだけだ。

ソース

Java で途中まで書いた例 build.xml が定義されているので、展開した後、

    ant compile
    ant jar
    ant run

として見よう。

Eclipse で、既存のbuild.xml からプロジェクトを読み込むを使っても良い。

Optional な課題

論理式を文字列として入力して、LogicNode のインスタンスを返すプログラムを作る。(Parser) JavaCC を使ってみよう。 JavaCC

LogicNode に、print というmethodを付ける。

LogicNode 自体の and/or/not を行うプログラムを作成する。

LogicNode を、より、コンパクトな形式、BDD などに変換する。