人気ブログランキング | 話題のタグを見る

命題論理で論理記号はなぜ2種類でいいのか。

命題論理の論理記号は¬、⊃、∨、∧の四つだが、ヒルベルトの公理系では¬と⊃の二つしか使っていない。はたしてこの二つだけで全ての複合命題の真理表を作ることができるのだろうか。ちなみに A⊃Bの真理表を作ってみると次のようになる。

A B A⊃B
T T T
T F F
F T T
F F T

¬は単項演算だが、他の論理記号は2項演算だ。命題論理の場合どんな複雑な複合命題であっても2項演算を再帰的に適用することによって真理表を作成することができる。従って、2項演算の真理表のとりえる可能性を全て¬と⊃の二つの記号で作ることができればよいわけだ。

上の真理表から分かるように命題の2項演算の場合は、A、B二つの単純命題の真偽値のとり方で、4通りの複合命題の真理値のとり方が決まる。さらに、この4通りの真理値の現われ方は、2の4乗の16通りあるはずである。この16通りをA, Bと¬、⊃の記号の組み合わせで作ることができることを示す必要がある。

ところで、二項演算の演算子は⊃しかないから、二項演算に関する限り⊃の位置の変更はない。従って、複合命題の作り方は単項演算の¬の位置がどこにあるかで決まってくる。この場合、次の8通りの記号列はすぐに思いつく。

  1. A⊃B
  2. ¬(A⊃B)
  3. ¬A⊃B
  4. ¬(¬A⊃B)
  5. A⊃¬B
  6. ¬(A⊃¬B)
  7. ¬A⊃¬B
  8. ¬(¬A⊃¬B)

しかし、これでは8通りにしかならないし、真理表の値が同じものになる場合もあるだろう。これを調べるのに手仕事でいちいち真理表を作成するのは大変なので自動化を考えてみる。scheme で真理表を作成するプログラムを作ったのが次のプログラムだ。関数 imp は引数に単純命題の真偽値をとり、A⊃Bの真偽値を返す。result 関数は単純命題A, Bの真偽の値を変えたときの複合命題 f の真偽値を表示する、言い換えると真理表を作成する関数だ。all 関数は上に示した八つの複合命題の真理表を全て表示する関数だ。

(define (imp a b)
  (or (not a) b))

(define (result f)
  (for-each
   (lambda (a)
    (display (f (car a) (cdr a))))
    '((#t . #t) (#t . #f) (#f . #t) (#f . #f)))
    (newline))

(define all
  (begin
    (result imp)
    (result (lambda (a b) (not (imp a b))))
    (result (lambda (a b) (imp (not a) b)))
    (result (lambda (a b) (not (imp (not a) b))))
    (result (lambda (a b) (imp a (not b))))
    (result (lambda (a b) (not (imp a (not b)))))
    (result (lambda (a b) (imp (not a) (not b))))
    (result (lambda (a b) (not (imp (not a) (not b)))))))

(all)

関数 all を実行したものが次の結果だ。

#t#f#t#t ---- A⊃B
#f#t#f#f ---- 標準形1
#t#t#t#f ---- A∨B
#f#f#f#t ---- 標準形2
#f#t#t#t
#t#f#f#f ---- A∧B  標準形3
#t#t#f#t
#f#f#t#f ---- 標準形4

これらの中には、and や or や 4つの真理値のうちひとつだけが真であとは偽となる標準形の真理表がふくまれている。したがって、これらを組み合わせると、残りの8種類の真理表をつくりだすことができる。従って、命題論理の2項演算は全て¬と⊃の二つの記号だけで表現することができる。命題論理の全ての複合命題は2項演算の再帰的適用になるので、結果的には全ての命題論理の複合命題の真理値がふたつの論理記号で記述できることになる。

Schemeはこのように、思考をそのままプログラムにしてしまうことが多い。変数やデータ構造などを宣言せずに、何となく考えを記述していくとそれがそのままプログラムになってしまうのだ。

概念をあまり工夫もせずに直接にプログラムとして実行可能な形にしてしまうという、Schemeの不思議な機能は思考の補助手段として重要な道具ではないかと思う。

暗号的なループの書き方や、やたらと多い括弧のせいで、Schemeを敬遠していたが、間違いだったかもしれない。
by tnomura9 | 2008-02-19 19:41 | 考えるということ | Comments(0)
<< Scheme のはじめ方 A⊃Aの証明 >>