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

選言標準形とトートロジー

含意 A -> B の真理値表は次のようになる。

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

この真理表は、含意の演算規則を定めたのち、命題 A, B の真理値によって真理表を作成したものだ。

それでは任意の真理表があるとき、それを表す論理式をみつけるにはどうしたらよいだろうか。たとえば、次のような真理表に対応する論理式をどうやって見つけたらよいだろうか。

A | B | A * B
T | T | F
T | F | T
F | T | T
F | F | F

これは、選言標準形を利用するのが便利だ。選言標準形とは原子命題の連言でできた項を連言でつなげた論理式だ。たとえばつぎのような論理式だ。

(A ∧ B) ∨ (A ∧ ¬B)

かっこで囲まれた連言の項2つを選言でつないでいる。このうち項 A ∧ B の真理表を見てみると次のようになる。

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

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

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

これらの論理式は、A と B の真理値のくみあわせが特定の場合だけ T になりその他は F になる。上の例でいえば A ∧ B は、V(A) = T かつ V(B) = T のときのみ、V(A ∧ B) = T でその他は V(A ∧ B) = F である。同様に A ∧ ¬B は V(A) = T, V(B) = F の時のみ V(A ∧ ¬B) = T でその他は F である。このように真理値表のうち1行だけが T になり、他は F になる論理式は選言演算式 ∨ で組み合わせると論理式全体の真理値の任意の行の真理値をコントロールできる。たとえば、上でのべた A * B の論理式は、つぎのように (A ∧ ¬B) ∨ (¬A ∧ B) で表すことができる。

A | B | (A ∧ ¬B) ∨ (¬A ∧ B)
T | F | F
T | F | T
F | T | T
F | F | F

したがって、原子命題 A と B のみから構成されるトートロジーの一つは少なくとも次の形をしていることが分かる。

A | B | (A ∧ B) ∨ (A ∧ ¬B) ∨ (¬A ∧ B) ∨ (¬A ∧ ¬B)
T | T | T
T | F | T
F | T | T
F | F | T

もちろん、原子命題 A と B で構成されるトートロジーの論理式はこればかりではない。たとえば A -> (B -> A) もトートロジーである。しかし、この論理式は次のように論理式の演算規則を利用して選言標準形に変形することができる。

A -> (B -> A)
¬A ∨ (¬B ∨ A)
A ∨ ¬A ∨ ¬B
(A ∧ (B ∨ ¬B)) ∨ (¬A ∧ (B∨ ¬B)) ∨ ((A ∨ ¬A) ∧ ¬B)
(A ∧ B) ∨ (A ∧ ¬B) ∨ (¬A ∧ B) ∨ (¬A ∧ ¬B)

論理式の演算規則による変形は同値変換だから可逆的で、双方向の変換が可能だ。したがって、原子命題 A, B から構成される任意のトートロジーは論理式の演算規則により相互に変換可能であることがわかる。

もし、演算規則による論理式の変形が公理系で演繹可能であれば、公理から A, B で構成されるトートロジーのどれかが演繹できれば、A, B で構成されるトートロジーのすべては公理から演繹可能であることになる。これは命題論理の完全性定理の直接的な証明となる。

しかし、その場合、演算規則による論理式の変形と同じことが公理系で演繹できることを示す必要がある。だが、これは可能な気がする。例えば二重否定の含意は定理である(公理から演繹できる)

¬¬A -> A

このとき、B -> ¬¬A が定理であれば、B -> A が定理であることを次のように証明できる。

¬¬A -> A .......... 仮定より定理
B -> (¬¬A -> A) .......... A が定理の時任意の命題 B について B -> A は定理
(B -> ¬¬A) -> (B -> A) .......... 公理P2の前件が定理の場合の後件
B -> ¬¬A .......... 仮定より定理
B -> A .......... 2つ上の定理の後件

これは B -> ¬¬A の ¬¬A を A で置き換える演算規則が、公理系の演繹としても証明できることを示している。


by tnomura9 | 2016-09-07 16:49 | 考えるということ | Comments(0)
<< 前件肯定 modus pone... 公理と否定演算子 >>