数理論理学(鹿島亮)7

以下のものだけからなる論理式

命題記号

⊥

¬

∧

∨

→

述語論理に対する結果の特別な場合として、命題論理の結果を得ることができる

命題論理特有の話題も多くある

7.1

この章では、命題論理の論理式だけを扱う

命題変数は必要に応じていくらでも新しい命題記号が供給される

Vは命題記号に対する真理値の割り当て

ストラクチャーの定義3.2.2の(1)だけからなるもの

命題論理の論理式で恒真なもの

すなわち、任意の真理値の割り当てVに対して、V(φ) = 真になる φのことをトートロジーと呼ぶ

健全性定理・完全性定理は、論理式を命題論理の論理式に限定しても成り立つ

⊢ φ ⇔ φはトートロジー

左辺について

左辺の「⊢」に関して、命題論理の論理式の導出の途中には∀や∃や=に関する規則を使用する必要はない。ということがいえる

命題論理の自然演繹だけで導出できることを「⊢prop」と書く

定理7.1.2

記号

φは命題論理の任意の論理式

主張

(⊢prop φ) ⇔ (φはトートロジー)

証明

⇒の場合

述語論理の健全性定理4.2.2の特別な場合として得られる

(⊢prop φ)

⇒ (⊢ φ)

「⊢prop」は「⊢」の一部分の推論規則のみを使ったものなので

⇒ (⊨ φ)

健全性定理4.2.2より

⇔ φはトートロジー

φは命題論理の論理式であるから

⇐の場合

φはトートロジー

⇔ (⊨ φ)

φは命題論理の論理式であるから

⇒ (⊢prop φ)

完全性定理の議論から、∀,∃や変数・定数・関数・述語記号や対象領域に関する議論を全て消去することで得られる

モデル存在定理・変数条件付き⇒モデル存在定理⇒完全性定理

という流れで5章で議論した

モデル存在定理⇒完全性定理

には、∃や変数・定数・関数・述語記号や対象領域に関する議論は登場しないので、そのままでOK

モデル存在定理・変数条件付き⇒モデル存在定理

命題論理の論理式しか扱わないので、未使用変数は無限個あるのでOK

モデル存在定理・変数条件付き

ここに色々な議論が出てくる。

(5.16) のφ ∈ Γ+ ならば M(φ) = 真 を示すためにいろいろ大変な議論をしているが、命題論理の論理式だけなので、φの複雑さに関する帰納法を命題論理の自然演繹に関してだけ回せば良い

定理6.3.3 述語論理式の恒真性の決定不可能性とは対照的に次の事実が成り立つ

定理7.1.3 命題論理式の恒真性の決定可能性

任意に与えられた命題論理の論理式がトートロジーであるか否かを判定するアルゴリズムが存在する

証明

n種類の命題記号を含む論理式φが与えられたら、2^n通りの全ての真理値の割り当てに対してφの真理値を計算してみれば良い

7.2

論理式の同値については定義3.4.1で与えられているが、命題論理の論理式に限れば次のようになる

定義7.2.1 同値

φ, ψを命題論理の論理式とする

V(φ) = V(ψ)

が任意の真理値割り当てVに対して成り立つことを、φとψは同値であるという

φ ≈ ψ と表記する

この節では、「どんな論理式にもそれと同値で論理記号の出現の仕方が一定の条件を満たす論理式が存在する」という対応の結果がいくつか紹介される

定理7.2.2

1. 命題論理のどんな論理式にも、それと同値で¬,∧以外の論理記号が出現しないような論理式が存在する

2. 命題論理のどんな論理式にも、それと同値で¬,∨以外の論理記号が出現しないような論理式が存在する

3. 命題論理のどんな論理式にも、それと同値で¬,→以外の論理記号が出現しないような論理式が存在する

4. 命題論理のどんな論理式にも、それと同値で⊥, →以外の論理記号が出現しないような論理式が存在する

証明

1. ⊥ ≈ A∧¬A, (φ∨ψ) ≈ ¬((¬φ)∧¬ψ), (φ→ψ) ≈ ¬(φ∧ψ) である

同値であるかは、真理値表を書いて確かめればいい

これに従って、論理式中の⊥, ∨, →をすべて¬,∧だけを使って表現(同値変形)すれば、任意に与えられた論理式から題意を満たす同値な論理式が得られる

ちゃんと議論するなら、論理式の複雑さに関して帰納法を使って、証明すればいいはず

2. ⊥ ≈ ¬(A∨¬A), (φ∧ψ) ≈ ¬((¬φ)∨¬ψ), (φ→ψ) ≈ (¬φ∨ψ) なので、その後(1)の議論と同様に行う

3. ⊥ ≈ ¬(A→A), (φ∧ψ) ≈ ¬(φ→¬ψ), (φ∨ψ) ≈ (¬φ→ψ) なので、その後(1)の議論と同様に行う

4. ¬φ ≈ φ→⊥, (φ∧ψ) ≈ (φ→¬(ψ→⊥))→⊥, (φ∨ψ) ≈ ((φ→⊥)→ψ)なので、その後(1)の議論と同様に行う

ところでこの定理7.2.2の結果よりもさらに論理記号の種類を減らすことは⊥, ¬, ∧, ∨, →の範囲では不可能である

これどうやって証明すればいいだろ？

適当に表現できると仮定して、矛盾を導くとか？

⊥, ¬, ∧, ∨, →のうち、2つの記号だけで全部表すことができるのも定理7.2.2の4つの組だけっぽいけどこれもどう証明するのかな？

これも適当に表現できると仮定して、矛盾を導くとか？

新しい論理記号

ジェファーの縦棒「|」「NAND」

table:NANDの真理値表

φ ψ φ|ψ

真 真 偽

真 偽 真

偽 真 真

偽 偽 真

定理7.2.3

命題論理のどんな論理式にも、それと同値でNAND以外の論理記号が出現しないような論理式が存在する

証明

証明は演習問題

次に論理式の特別な形である選言標準形を定義する

定義7.2.4

命題記号の前に0個または1個の¬をつけたもの

注意

2個以上のリテラルの連言には、リテラルの順番や括弧のかかり方が何通りもあるが、どれも同値

区別する必要がない場合は単に、φ1∧φ2∧φ3 のように表記する

「リテラルの連言」を∨で結んだ論理式

定理7.2.5 命題論理のどんな論理式に対しても、それと同値な選言標準形が存在する

証明

φを命題論理の任意の論理式として、そこに出現している命題記号の種類をnとする

以下ではφと同値な選言標準形が存在することをnに関する帰納法によって証明する

【n=0の場合】

φには命題記号が出現しないので、⊥, ¬, ∧, ∨, →だけで構成されている。

φは「どんな真理値の割り当てによっても真」であるか「どんな真理値の割り当てによっても偽」であるかのどちらかである

任意の真理値の割り当てV1, V2 に対して、V1(φ) = V2(φ)

前者の場合は

A∨¬Aが求める選言標準形

2個のリテラルが結ばれた形

後者の場合は

A∧¬Aが求める選言標準形

1個のリテラル

【n=k+1の場合】

φがk+1種類の命題記号 X1, X2, …, Xk+1 からなるとする

論理式⊥→⊥を⊤と表記する

⊤は「どんな真理値の割り当てによっても真」になる論理式

φ中のXk+1を⊤で置き換えた論理式をφ^⊤とよぶ

φ中のXk+1を⊥で置き換えた論理式をφ^⊥とよぶ

帰納法の仮定より

φ^⊤ ≈ τ

φ^⊥ ≈ σ

となる選言標準形τ, σが存在する

ここで論理式 (τ∧Xk+1)∨(σ∧¬Xk+1) をψと呼ぶ

次の2つを示せば証明が完了する

(ア) φ ≈ ψ

(イ) ψと同値な選言標準形が存在する

(イ)の選言標準形が求めるものになる

(ア)の証明

任意の真理値割り当てVに対して V(φ) = V(ψ) となることを示す

V(Xk+1) = 真の場合

V(φ)

= V(φ^⊤)

V(Xk+1) = 真であるから、Xk+1を⊤で置き換えても真理値は変わらない

= V(τ)

帰納法の仮定より

= V(τ∧⊤)

⊤と∧で結んでも真理値は変わらない

= V((τ∧⊤)∨(σ∧⊥))

V(σ∧⊥) = V(⊥) = 偽であるので、(σ∧⊥)と∨で結んでも真理値は変わらない

= V((τ∧Xk+1)∨(σ∧¬Xk+1))

V(Xk+1) = 真であるから

= V(ψ)

ψの定義より。

V(Xk+1) = 偽の場合

V(φ) = V(φ^⊥) = V(σ) = V((τ∧⊥)∨(σ∧⊤)) = V(ψ)

(イ)の証明

一般には選言標準形にはなっていない。

τが1つの「リテラルの連言」つまり、X1∧X2∧…∧Xkみたいになっている場合を除く

τが2つ以上の「リテラルの連言」(X1∧X2)∨…∨(Xk-1∧Xk)のように∨が含まれている形だと、(τ∧Xk+1)は((X1∧X2)∨…∨(Xk-1∧Xk))∧Xk+1みたいになってしまい、リテラルの連言すべてを∨で結んだ論理式にならない

直感的には、Xk+1と¬Xk+1をそれぞれτ, σに分配している感じだと思う

τとσがそれぞれ以下の形をしているとする

τ1∨τ2∨…∨τi

τ1, τ2 ,…,τiはすべてリテラルの連言

σ1∨σ2∨…∨σi

σ1, σ2 ,…,σiはすべてリテラルの連言

このとき、(τ1∧Xk+1)∨(τ2∧Xk+1)∨…∨(τi∧Xk+1)∨(σ1∧¬Xk+1)∨(σ2∧¬Xk+1)∨…∨(σi∧¬Xk+1)はψと同値な論理式であり、選言標準形になる

演習問題

7.1

「命題論理のどんな論理式にも、それと同値で→以外の論理記号が出現しないような論理式が存在する」という主張が誤りであることを証明せよ

証明

メモ

⊥と同値になる、→以外の論理記号が出現しない論理式が存在しない。

すなわち、φが→以外の論理記号が出現しない論理式のとき、ある真理値の割り当てVが存在して、V(⊥) ≠ V(φ) となる

このことから主張が誤りであることを示す。

論理式の複雑さ(→の出現数)に関する帰納法を回し、任意の→以外の論理記号が出現しない論理式φに対して、V(φ) = 真となる ある真理値の割り当てVが存在することを示す。

φに出現するすべての命題記号を真に割り当てるVは上記の条件を満たす。

n=1のとき

φはA→Bという形になる

A,Bは命題記号

V(φ) = 真

⇔ V(A→B) = 真

⇔ V(A) = 偽 または V(B) = 真

φに出現するすべての命題記号を真に割り当てると、V(A) = 真、V(B) = 真

よって、V(φ) = 真となる。

kで成り立つとして、k+1で成り立つことを示す

V(φ) = 真

⇔ V(φ1→φ2) = 真

⇔ V(φ1) = 偽 または V(φ2) = 真

φに出現するすべての命題記号を真に割り当てると、帰納法の仮定よりV(φ1) = 真、V(φ2) = 真

よって、V(φ) = 真となる。

メモ 他の論理記号のバージョンについて

「命題論理のどんな論理式にも、それと同値で∧以外の論理記号が出現しないような論理式が存在する」という主張が誤りであることを証明せよ

⊥と同値な∧以外の論理記号が出現しないような論理式φが作れないことを証明すればいい

つまり、ある真理値の割り当てVに対して、V(⊥) ≠ V(φ) = 真 となることを示す。

φに出現するすべての命題記号を真に割り当てるVは上記の条件を満たす。

帰納法は省略……

「命題論理のどんな論理式にも、それと同値で∨以外の論理記号が出現しないような論理式が存在する」という主張が誤りであることを証明せよ

⊥と同値な∨以外の論理記号が出現しないような論理式φが作れないことを証明すればいい

つまり、ある真理値の割り当てVに対して、V(⊥) ≠ V(φ) = 真 となることを示す。

φに出現するすべての命題記号を真に割り当てるVは上記の条件を満たす。

帰納法は省略……

「命題論理のどんな論理式にも、それと同値で⊥以外の論理記号が出現しないような論理式が存在する」という主張が誤りであることを証明せよ

A∧Bと同値な⊥以外の論理記号が出現しないような論理式φがないことを示す。

φは⊥か、単独の命題記号しかない。どの場合でもA∧Bと同値にならない つまりある真理値の割り当てVが存在して、真理値が一致しないことを示す。

φが⊥のとき

V(A) = 真、V(B) = 真、という真理値の割り当てをするVに対して、

V(A∧B) = 真 ≠ 偽 = V(⊥) = V(φ)

φがAのとき

V(A) = 真、V(B) = 偽、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(A) = V(φ)

φがBのとき

V(A) = 偽、V(B) = 真、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(B) = V(φ)

φがCのとき

V(A) = 真、V(B) = 真、V(C) = 偽という真理値の割り当てをするVに対して、

V(A∧B) = 真 ≠ 偽 = V(C) = V(φ)

「命題論理のどんな論理式にも、それと同値で¬以外の論理記号が出現しないような論理式が存在する」という主張が誤りであることを証明せよ

A∧Bと同値な¬以外の論理記号が出現しないような論理式φがないことを示す。

φは単独の命題記号か、単独の命題記号に「¬」を何回もくっつけたものしかない。どの場合でもA∧Bと同値にならない つまりある真理値の割り当てVが存在して、真理値が一致しないことを示す。

φがA, ¬¬A, ……のとき

V(A) = 真、V(B) = 偽、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(A) = V(φ)

φが¬A, ¬¬¬A, ……のとき

V(A) = 偽、V(B) = 真、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(¬A) = V(φ)

φがB, ¬¬B, ……のとき

V(A) = 偽、V(B) = 真、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(B) = V(φ)

φが¬B, ¬¬¬B, ……のとき

V(A) = 真、V(B) = 偽、という真理値の割り当てをするVに対して、

V(A∧B) = 偽 ≠ 真 = V(¬B) = V(φ)

φがC, ¬¬C, ……のとき

V(A) = 真、V(B) = 真、V(C) = 偽、という真理値の割り当てをするVに対して、

V(A∧B) = 真 ≠ 偽 = V(C) = V(φ)

φが¬C, ¬¬¬C, ……のとき

V(A) = 真、V(B) = 真、V(C) = 真という真理値の割り当てをするVに対して、

V(A∧B) = 真 ≠ 偽 = V(¬C) = V(φ)

7.3

定理7.2.3

命題論理のどんな論理式にも、それと同値でNAND以外の論理記号が出現しないような論理式が存在する

証明

¬φ ≈ φ nand φ

φ∧ψ ≈ (φ nand ψ) nand (φ nand ψ)

である。

命題論理の論理式を定理7.2.2を使って、「¬」と「∧」のみの論理式に変換した後、上記の結果を使って、任意の論理式にも、それと同値でNAND以外の論理記号が出現しないような論理式が存在する

7.4

1個以上のリテラルを∨で結んだ論理式のことを「リテラルの選言」と呼び、1個以上の「リテラルの選言」を∧を結んだ論理式のことを連言標準形とよぶ。命題論理のどんな論理式にも、それと同値な連言標準形が存在することを示せ

証明

φを命題論理の任意の論理式として、そこに出現している命題記号の種類をnとする

以下ではφと同値な連言標準形が存在することをnに関する帰納法によって証明する

【n=0の場合】

φには命題記号が出現しないので、⊥, ¬, ∧, ∨, →だけで構成されている。

φは「どんな真理値の割り当てによっても真」であるか「どんな真理値の割り当てによっても偽」であるかのどちらかである

任意の真理値の割り当てV1, V2 に対して、V1(φ) = V2(φ)

前者の場合は

A∨¬Aが求める連言標準形

1個のリテラルの選言が結ばれた形

後者の場合は

A∧¬Aが求める連言標準形

2個のリテラルの選言が結ばれた形

【n=k+1の場合】

φがk+1種類の命題記号 X1, X2, …, Xk+1 からなるとする

論理式⊥→⊥を⊤と表記する

⊤は「どんな真理値の割り当てによっても真」になる論理式

φ中のXk+1を⊤で置き換えた論理式をφ^⊤とよぶ

φ中のXk+1を⊥で置き換えた論理式をφ^⊥とよぶ

帰納法の仮定より

φ^⊤ ≈ τ

φ^⊥ ≈ σ

となる連言標準形τ, σが存在する

ここで論理式 (τ∨¬Xk+1)∧(σ∨Xk+1) をψと呼ぶ

次の2つを示せば証明が完了する

(ア) φ ≈ ψ

(イ) ψと同値な連言標準形が存在する

(イ)の連言標準形が求めるものになる

(ア)の証明

任意の真理値割り当てVに対して V(φ) = V(ψ) となることを示す

V(Xk+1) = 真の場合

V(φ)

= V(φ^⊤)

V(Xk+1) = 真であるから、Xk+1を⊤で置き換えても真理値は変わらない

= V(τ)

帰納法の仮定より

= V(τ∨⊥)

⊥と∨で結んでも真理値は変わらない

= V((τ∨⊥)∧(σ∨⊤))

V(σ∨⊤) = V(⊤) = 真であるので、(σ∨⊤)と∧で結んでも真理値は変わらない

= V((τ∨¬Xk+1)∧(σ∨Xk+1) )

V(Xk+1) = 真であるから

= V(ψ)

ψの定義より。

V(Xk+1) = 偽の場合

V(φ) = V(φ^⊥) = V(σ) = V((τ∨⊤)∧(σ∨⊥)) = V(ψ)

(イ)

τとσがそれぞれ以下の形をしているとする

τ1∧τ2∧…∧τi

τ1, τ2 ,…,τiはすべてリテラルの選言

σ1∧σ2∧…∧σi

σ1, σ2 ,…,σiはすべてリテラルの選言

このとき、(τ1∨¬Xk+1)∧(τ2∨¬Xk+1)∧…∧(τi∨¬Xk+1)∧(σ1∨Xk+1)∧(σ2∨Xk+1)∧…∧(σi∨Xk+1)はψと同値な論理式であり、連言標準形になる