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

命題論理(3)

3.命題論理のすべての命題は2つの論理記号、¬ と -> だけで記述できる

原子命題から命題を作るために命題論理では、否定記号、連言記号、選言記号、含意の4つの記号を使うが、これらの記号は他の論理記号で置き換えることができる。最終的には2つの論理記号があれば、命題論理のすべての命題が記述できることが分かっている。

たとえば、A -> B の真理値表は次のようになる。

A | B | A -> B
T | T | T
T | F | F
F | T | T
F | F | T

また、¬A ∨ B の真理値表は次のようになる。

A | B | ¬A | ¬A ∨ B
T | T | F | T
T | F | F | F
F | T | T | T
F | F | T | T

これらの二つの真理値表の結果は同じだ。つまり、論理記号の含意記号 -> は否定記号 ¬ と選言記号 ∨に置き換えることができる。また、A ∨ B の真理値表を ¬A -> B の真理値表と比較すると、選言記号を否定記号と含意記号に置き換えることができるのが分かる。

A | B | A ∨ B
T | T | T
T | F | T
F | T | T
F | F | F

A | B | ¬A | ¬A -> B
T | T | F | T
T | F | F | T
F | T | T | T
F | F | T | F

また、次の真理値表から A ∧ B は ¬(A -> ¬B) で置き換えることができることが分かる。

A | B | A ∧ B
T | T | T
T | F | F
F | T | F
F | F | F

A | B | ¬B | A -> ¬B | ¬(A -> ¬B)
T | T | F | F | T
T | F | T | T | F
F | T | F | T | F
F | F | T | T | F

結局、否定記号、連言記号、選言記号、含意記号の4つの論理記号のうち、否定記号と含意記号の二つだけで命題論理のすべての命題を表記できることが分かる。

それぞれの論理記号には直感的な意味があるので、わざわざ2つの記号に集約するために複雑な表現を取らなくてもいいように思えるが、論理記号を減らすことによって、公理から定理を導くための証明が簡単になる。ウカシェビッチの公理系では、公理は次の3つの命題で、推論規則に三段論法だけを使い、全ての常に真な命題(すなわち定理)を証明することができる。

P1. A -> (B -> A)
P2. (A -> (B -> C)) -> ((A -> B) -> (A -> C))
P3. (¬B -> ¬A) -> (A -> B)

三段論法とは A -> B が定理の時、Aが定理であれば B は定理であるという論証である。命題論理の命題は多様なものが考えられるが、そのうち真理値が常に真である定理はすべて上の3つの公理と三段論法だけで論証できるとなると、命題論理の構造が実にシンプルに見えてくる。

by tnomura9 | 2016-07-30 14:29 | 考えるということ | Comments(0)
<< 命題論理(4) 命題論理(2) >>