数理論理学(鹿島亮)3

p40

注釈によると10章,11章ではこの見方に単純に従わない論理体系も扱う

直観主義論理など

以下の記号からなる論理式

命題記号

論理記号(⊥,¬,∧,∨,→)

括弧

真理値の定義

table:⊥の真理値

⊥

偽

table:¬の真理値

φ ¬φ

真 偽

偽 真

table:∧, ∨, → の真理値

φ ψ φ∧ψ φ∨ψ φ→ψ

真 真 真 真 真

真 偽 偽 真 偽

偽 真 偽 真 真

偽 偽 偽 偽 真

(A→B)→((A∨¬C)∨⊥)の真理値を考える

Aが偽、Bが真、Cが真の場合

(A→B)は真

¬Cは偽

(A∨¬C)は偽

((A∨¬C)∨⊥)は偽

(A→B)→((A∨¬C)∨⊥)は偽

ひとつの設定の中で、同一の命題記号に異なる真理値を割り当てることはできない

述語記号や関数記号の入った一般の論理式の真理値

「x > 3」という言明は正しいか？

xが不定でならば答えられない

自由出現する変数記号を含んだ真理値を定めるのは厄介

本書では閉論理式だけが真理値を持つという方針で進めていく

注釈によると別の流儀もあるらしい

ストラクチャーとは

閉論理式の真理値を定めるために必要なもの

以下の3つからなる

命題記号への真理値割り当て

定数記号、関数記号、述語記号それぞれを対象領域上でどのように解釈するか

じゃんけんを例に

ストラクチャーJ

対象領域

{グー, チョキ, パー}

関数記号sucの解釈

suc^J(グー) = チョキ

suc^J(チョキ) = パー

suc^J(パー) = グー

「『勝てる相手』を返す」関数を表す

述語記号Rの解釈

R^J(グー,チョキ)=R^J(チョキ,パー)=R^J(パー,グー)=真

R^J(グー,グー)=R^J(チョキ,チョキ)=R^J(パー,パー)=偽

R^J(グー,パー)=R^J(チョキ,グー)=R^J(パー,チョキ)=偽

R(x,y)は「xはyに勝つ」を表す述語

ストラクチャーJにおける論理式φの真理値をJ(φ)と書く

例

J(R(グー,チョキ))=真

しかし、R(グー,チョキ)は論理式ではない

グー,チョキは対象領域の要素の名前ではある

が、論理式を構成する際に使用できる記号ではないから

グー,チョキが定数記号であれば論理式となる

D拡大項

対象領域がDのとき

Dの要素の名前をすべて定数記号として認めたときに項となるもの

特に閉項となっているものは

D拡大閉項と呼ぶ

例：{グー, チョキ, パー}拡大閉項となるもの

グー

suc(グー)

suc(two)

「グー, チョキ, パー」の名前を使用しない従来の項や論理式も拡大項・拡大論理式と読んで良い

D拡大論理式

対象領域がDのとき

Dの要素の名前をすべて定数記号として認めたときに論理式となるもの

特に閉論理式となっているものは

D拡大閉論理式と呼ぶ

例：{グー, チョキ, パー}拡大閉論理式となるもの

R(グー,チョキ)

注意

Dの1つの要素が複数の名前を持っていてもよい

例

じゃんけんの同じ手を指している2つの名前「グー」「ぐぅ」を定数記号として認めてよい

必要なのはDのすべての要素がそれぞれ名前を持っているということ

命題記号への真理値割り当て

対象領域

これは空ではない集合である

もし空の場合は健全性定理が成り立たなくなる

定数記号の解釈、関数記号の解釈、等号以外の述語記号の解釈

これらは対象領域上の要素や関数や述語である

ストラクチャーMによる記号ξの解釈をξ^Mと書く

定数記号の解釈

zero^M, one^M, two^M, omega^M, unity^M, rt^M

は全てDの要素

関数記号の解釈

⊕^M, ⊙^M, ⊗^M, suc^M

は全てD上の関数

D上の関数というよくわからないもの？に定義を押し付けているもやもや感が少しする

定義域D^nからDへの関数

suc^MはD上の1変数関数

⊕^M, ⊙^M, ⊗^MはD上の2変数関数

等号以外の述語記号の解釈

⧀^M, P^M, Q^M, R^M

は全てD上の述語

P^M, Q^MはD上の1変数述語

⧀^M, R^MはD上の2変数述語

Mは対象領域がDのストラクチャー

以下を再帰的に定義していく

拡大閉項の値の定義 3.2.3

D拡大閉項tのMにおける値をM(t)と表記する

tがDの要素の名前のとき、M(t)はその要素である

tが定数記号(Dの要素の名前ではない)のとき、M(t)の値はストラクチャーの定義より(定数記号の解釈)決まる

例

M(two)=two^M

tがより短い項と関数記号とを組み合わせて作られているとき、M(t)の値は短い項の値とストラクチャーの定義(関数記号の解釈)より決まる

例

M(suc(s)) = suc^M(M(s))

M(u⊗v) = (M(u) ⊗^M M(v))

拡大閉論理式の真理値の定義

D拡大閉論理式φのMにおける真理値をM(φ)と表記する

この値は真か偽のどちらか

φが命題記号のとき、M(φ)の値はストラクチャーの定義(命題記号の解釈)より決まる

φが（t=s）という形のとき、M(φ)の値は拡大閉項の値の定義によって規定されたtとsの値が等しいか否かで決まる

M(t=s) = 真 ⇔ M(t) = M(s)

φがひとつの述語記号をD拡大閉項に適用した形の論理式のとき、M(φ)の値は拡大閉項の値の定義によって規定された項の値とストラクチャーの定義による述語記号の解釈で決まる

例

M(R(s,t)) = 真 ⇔ R^M(M(s), M(t)) = 真

φが論理記号を含むとき、M(φ)の値はφより簡単な(すなわち論理記号の出現数が少ない)論理式のMにおける真理値から次のように決まる

-------------よく見るので強調---------------------------------------------------------

M(⊥) = 偽

M(¬ψ) = 真 ⇔ M(ψ) = 偽

M(¬ψ) = 偽 ⇔ M(ψ) = 真

M(ψ∧ρ) = 真 ⇔ (M(ψ) = 真 かつ M(ρ) = 真)

M(ψ∨ρ) = 真 ⇔ (M(ψ) = 真 または M(ρ) = 真)

M(ψ→ρ) = 真 ⇔ (M(ψ) = 偽 または M(ρ) = 真)

---------------------------------------------------------------------------------------------------

具体例(自然数のストラクチャーN)

対象領域は{0,1,2,…}

関数記号、述語記号P, Qの解釈は次の通り

suc^N(x) = x+1

P^N(x)

P^N(x) = 真 (xが偶数のとき)

P^N(x) = 偽 (xが奇数のとき)

Q^N(x)

Q^N(x) = 真 (xが奇数のとき)

Q^N(x) = 偽( xが偶数のとき)

論理式の真理値の例

N( ( ∀x(P(x)∨Q(x)) ) → ( (∀xP(x)) ∨ (∀xQ(x))) ) = 偽

論理式の真理値を詳しく分析する

∀x(P(x)∨Q(x)) = 真

どんな自然数も偶数か奇数のどちらかではある

∀xP(x) = 偽

どんな自然数も偶数である

∀xQ(x) = 偽

どんな自然数も奇数である

(∀xP(x)) ∨ (∀xQ(x))) = 偽

対象領域の要素数だけに真理値が依存する論理式

∃x∃y∃z((¬(x=y)∧¬(x=z))∧¬(y=z))

この論理式をφとしたとき、任意のストラクチャーMに対して以下が成り立つ

M(φ) = 真 ⇔ Mの対象領域の要素の個数が3個以上である

【定理3.2.5】真理値と代入に関する基本的な性質

Mは対象領域がDのストラクチャー

s,tはD拡大閉項

xは変数記号

φはx以外の変数記号の自由出現を含まないD拡大論理式

Mは対象領域がDのストラクチャー

s1,t1,s2,t2,…sn,tnはD拡大閉項

x1,x2,…xnは変数記号

φはx1,x2,…xn以外の変数記号の自由出現を含まないD拡大論理式

n=1の時を考えて、nで成り立つとして、n+1の場合を証明するみたいに帰納法回す証明できそう？

証明

φの複雑さに関する帰納法によって証明する

φの複雑さとは、φ中の論理記号(⊥, ¬, ∧, ∨, →, ∀, ∃)の出現数のこと

φが原始論理式のとき(論理記号の出現数が0のとき)

φが単独の命題記号や⊥の場合

φ中にxが出現しない場合

気持ち的には明らかなだと思っているけど、厳密？にやるなら

論理式の複雑さに関する帰納法を回したりする必要がある

閉項の複雑さという言葉で言いたいのは閉項の中に出現する関数記号の出現数のこと

証明のイメージ

φがP(zero)の場合

P(suc(u))も成り立つ

P(u⊕v)も成り立つ

…

みたいな証明必要にならないのかな？

面倒だし、明らかと言ってもいい気もしますが

φ中にxが出現する場合

たとえば、φがR(x,(two⊗x))のとき

φが他の原子論理式の場合も同様である

一瞬述語記号とか関数記号が無限個あったら困りそうな気がしたけど、可算無限なら帰納法で対処できるから問題ないのか

2章見たら、こんな感じの記述ありました

ただし、定数・関数・命題・述語記号がもっと多くてもそれらが可算で明確に列挙されている限り本書の内容と記述はそのまま通用する

述語に関する帰納法は別に回さなくてもよい。

φが複合論理式の場合

φがψ∧ρという形の場合

ψ,ρともに複雑さはφよりも小さい

このことと∧の真理値の定義を用いて題意を示す

上記が全部同値変形になっているので、真でないというふうにしていける

φが∀yψという形の場合

yとxが同じ変数記号である

実は∀xψのような状態になっているとする

φ中にxは自由出現しないので、題意は成り立つ

xは今回自由出現していない。つまり代入不可能の定義を満たさないので、xに項を代入可能

(しかしφは∀xψという形の論理式なので、φ中のxは全て束縛されている)

φ中にxは自由出現しないので、一つも変数の置き換えは起きない

したがって、自由出現していない変数に代入操作をしようとしても、何も変化しないといえる？

p55で∀xφ = φ* というのはこういうこと？

p55まだ読んでないけど

yとxが同じ変数記号でない

aを対象領域Dの任意の要素の名前とする

このことと∀の真理値の定義を用いて題意を示す

論理式の複雑さに関する帰納法？

これが成り立つのはxとyが異なる変数であるからじゃないか？

帰納法の仮定を使っている

φが他の複合論理式の場合も同様である

φが¬ψという形の場合

ψの複雑さはφよりも小さい

このことと¬の真理値の定義を用いて題意を示す

ここで帰納法の仮定を使っている

φがψ∨ρという形の場合

ψ,ρともに複雑さはφよりも小さい

このことと∨の真理値の定義を用いて題意を示す

ここで帰納法の仮定を使っている

φがψ→ρという形の場合

ψ,ρともに複雑さはφよりも小さい

このことと→の真理値の定義を用いて題意を示す

ここで帰納法の仮定を使っている

φが∃yψという形の場合

yとxが同じ変数記号である

φ中にxは自由出現しないので、題意は成り立つ

yとxが同じ変数記号でない

aを対象領域Dのあるの要素の名前とする

このことと∃の真理値の定義を用いて題意を示す

代入の順番の入れ替え

帰納法の仮定を使用

代入の順番の入れ替え

閉論理式の3つの分類

1. どんなストラクチャーでも真であるもの

2. あるストラクチャーでは真で、別のあるストラクチャーでは偽であるもの

3. どんなストラクチャーにおいても偽であるもの

意味は伝わると思うけど、あんまり使いはしない

閉論理式φがすべてのストラクチャーMに対して、M(φ) = 真 となっているとき、φは恒真であるという

定義3.3.2 モデル、充足可能性

閉論理式の集合Γ

有限でも無限でも可能

ストラクチャーM

Γのすべての要素φに対してM(φ)=真となるとき、Mのことを「Γのモデル」あるいは「Γを充足するストラクチャー」という

Γのモデルが存在することを「Γはモデルを持つ」あるいは「Γは充足可能である」という

恒真な論理式の例

A∨¬A

恒真な式の代表例

M(A)の値の組み合わせは2通りある

M(A)=真

M(¬A)=偽

M(A∨¬A)=真

M(A)=偽

M(¬A)=真

M(A∨¬A)=真

(A∧(A→B))→B

M(A)とM(B)の値の組み合わせは4通りの可能性がある

恒真であることを示す

M(A)=真, M(B)=真のとき

M(A→B)=真

M(A∧(A→B))=真

M((A∧(A→B))→B)=真

M(A)=真, M(B)=偽のとき

M(A→B)=偽

M(A∧(A→B))=偽

M((A∧(A→B))→B)=真

M(A)=偽, M(B)=真のとき

M(A→B)=真

M(A∧(A→B))=偽

M((A∧(A→B))→B)=真

M(A)=偽, M(B)=偽のとき

M(A→B)=真

M(A∧(A→B))=偽

M((A∧(A→B))→B)=真

恒真であると示された

( (∀xP(x))∨(∀xQ(x)) )→∀x(P(x)∨Q(x))

∀x∀y((x=y)→suc(x)=suc(y))

恒真な論理式の形をした文章は内容によらず形だけから正しいといえる文章といってよい

例

A∨¬Aの形をした文章

火星に生命が存在する。または火星には生命は存在しない

P≠NPまたはP=NPである

火星探査や計算量理論の研究をしなくても、単に文章の形だけから正しいと断言できる

(正しいけど、有用な情報は伝えていない)

論理的に正しい文章とは何か？

それは「恒真な論理式の形をした文章」　のことだ

というのが最も単純で強力な答であろう

充足可能な閉論理式の集合の例

群の公理

論理式の集合Γ_G

∀x∀y∀z((x⊙y)⊙z = x⊙(y⊙z))

∀x(unity⊙x = x)

∀x∃y(y⊙x = unity)

ストラクチャーMがΓ_Gを充足するということは

対象領域D上の要素unity^Mと2項演算⊙^Mが「⊙^Mは結合法則を満たし、unity^Mは左単位元であり、どんな要素にも左逆元が存在すること」

MはΓ_Gのモデルであることは以下と同値

⇔ 〈D, ⊙^M ,unity^M〉は群である

なんでもいいから群を持ってくれば充足できるので、Γ_Gは充足可能

∀をallって適当に呼んでいたけど、for allと呼んだほうが伝わりやすい？

適当に読んでいい

∃もexistって適当に呼んでいたけど、there existsと呼んだほうが伝わりやすい？

それともfor existって読むのか？

φ,ψを論理式として、FVar(φ)∪FVar(ψ) = {x1,x2,…,xn}とする

このとき閉論理式∀x1,∀x2,…,∀xn((φ→ψ) ∧ (ψ→φ))が恒真であることを

φとψは同値であるという

φ≈ψと表記する

(φ→ψ) ∧ (ψ→φ)

論理式の一部分をその部分と同値な別の論理式で置き換えること

【定理】同値変形は論理式の真理値を変えない変形である

φ≈ψであり、閉論理式ρが…φ… , ρ'が…ψ…という形であるならば(ρ中のφを同値なψに置き換えたものがρ')、どんなストラクチャーMに対してもM(ρ)=M(p')になる

証明

定理3.2.5と同様に示せるらしい(教科書曰く)

ρの複雑さからφの複雑さを引いたものに関する帰納法によって証明する

φ中の論理記号の出現を除く、ρの論理記号の出現数

これは、ψ中の論理記号の出現を除く、ρ'の論理記号の出現数とも一致する

φの外側の複雑さに関する帰納法？

φに対するρの複雑さに関する帰納法？

φに対するρの複雑さが0である時

ρはφと一致する

M(ρ) = M(φ)

ρは閉論理式なので、φも閉論理式である

ρ'はψと一致する

M(ρ') = M(ψ)

ρ'は閉論理式なので、ψも閉論理式である

φ,ψは閉論理式で、φ≈ψであるから、M(φ)=M(ψ)である

φは閉論理式とは限らないので、φに真理値が定義されているとは限らない

よって、M(ρ)=M(p')

M(ρ)=M(φ)=M(ψ)=M(p')

φに対するρの複雑さが0でないとき

ρが¬(…φ…)という形の場合

(…φ…)の複雑さはρより小さい

帰納法の仮定より、どんなストラクチャーMに対してもM(…φ…)=M(…ψ…)になる

このことと¬の真理値の定義を用いて題意を示す

M(ρ) = 真

⇔ M(¬(…φ…)) = 真

⇔ M(…φ…) = 偽

⇔ M(…ψ…) = 偽

⇔ M(¬(…ψ…)) = 真

⇔ M(ρ') = 真

M(ρ) = 真 ⇔ M(ρ') = 真 であり、各論理式は真か偽のどちらかの真理値しか持たない

よって、M(ρ)= M(ρ')

(…φ…)の複雑さはρより小さい

帰納法の仮定より、どんなストラクチャーMに対してもM(…φ…)=M(…ψ…)になる

このことと∨の真理値の定義を用いて題意を示す

M(ρ) = 真

⇔ M(ρ''∨(…φ…)) = 真

⇔ M(ρ'') = 真 または M(…φ…) = 真

⇔ M(ρ'') = 真 または M(…ψ…) = 真

⇔ M(ρ''∨(…ψ…)) = 真

⇔ M(ρ') = 真

M(ρ) = 真 ⇔ M(ρ') = 真 であり、各論理式は真か偽のどちらかの真理値しか持たない

よって、M(ρ )= M(ρ')

ρが(…φ…)∨ρ''、ρ'が(…ψ…)∨ρ''という形の場合

省略

ρがρ''∧(…φ…)、ρ'がρ''∧(…ψ…)という形の場合

省略

ρが(…φ…)∧ρ''、ρ'が(…ψ…)∧ρ''という形の場合

省略

ρがρ''→(…φ…)、ρ'がρ''→(…ψ…)という形の場合

省略

ρが(…φ…)→ρ''、ρ'が(…ψ…)→ρ''という形の場合

省略

ρが∀x(…φ…)という形の場合

場合わけいらない(代入はxがあってもなくてもできる)

4通りに分ける理由メモ

∀x(F(x)∨¬F(x)) ∀x¬⊥

F(x)∨¬F(x)と¬⊥

xが(…φ…),(…ψ…)の中に出現しない場合

(…φ…),(…ψ…)は閉論理式である

(…φ…)の複雑さはρより小さく、(…ψ…)の複雑さはρ'より小さい

帰納法の仮定より、どんなストラクチャーMに対してもM(…φ…)=M(…ψ…)になる

よって題意は示せた

xが(…φ…)に出現せず、(…ψ…)に出現する場合

証明省略

こういう場合分けをする必要がある。ρが∀x¬⊥、p'が∀x(F(x)∨¬F(x))という場合、¬⊥は閉論理式であるが、F(x)∨¬F(x))はそうではないため

xが(…φ…)に出現し、(…ψ…)場合に出現しない場合

証明省略

xが(…φ…),(…ψ…)の中に出現する場合((…φ…), (…ψ…)が閉論理式でない場合)

aを対象領域Dの任意の要素の名前とする

このことと∀の真理値の定義を用いて題意を示す

M(ρ) = 真

⇔ M(∀x(…φ…)) = 真

帰納法の仮定より

⇔ M(∀x(…ψ…)) = 真

⇔ M(p') = 真

M(ρ) = 真 ⇔ M(ρ') = 真 であり、各論理式は真か偽のどちらかの真理値しか持たない

よって、M(ρ )= M(ρ')

ρが∃x(…φ…)、ρ'が∃x(…ψ…)という形の場合

xが(…φ…)の中に出現する場合((…φ…), (…ψ…)が閉論理式でない場合)

aを対象領域Dのあるの要素の名前とする

このことと∃の真理値の定義を用いて題意を示す

M(ρ) = 真

⇔ M(∃x(…φ…)) = 真

帰納法の仮定より

⇔ M(∃x(…ψ…)) = 真

⇔ M(p') = 真

M(ρ) = 真 ⇔ M(ρ') = 真 であり、各論理式は真か偽のどちらかの真理値しか持たない

よって、M(ρ)= M(ρ')

証明終了

なりそうだけど…どうだろ？(やっぱりならなそう)

M(ρ)=M(ρ')となるとき

閉論理式ρが…φ… , ρ'が…ψ…であり、どんなストラクチャーMに対してもM(ρ)=M(p')になるならば、φ≈ψとなる

ρがφ∨⊥、ρ'がφ∨¬⊥であるとき、どんなストラクチャーMに対してもM(ρ)=M(p')になるけれど、

⊥≈¬⊥とはならないしね

同値な論理式の組

φ*は変数記号xの自由出現を持たない論理式

¬に関するもの

⊥ ≈ φ∧¬φ

¬¬φ ≈ φ

∧に関するもの

φ ≈ φ ∧ φ

φ ∧ ψ ≈ ψ ∧ φ

φ ∧ (ψ ∧ ρ) ≈ (φ ∧ ψ) ∧ ρ

φ ∧ ⊥ ≈ ⊥

φ ∧ ¬⊥ ≈ φ

φ ∧ ψ ≈ ¬(¬φ ∨ ¬ψ)

¬(φ ∧ ψ) ≈ ¬(¬φ ∨ ¬ψ)

∨に関するもの

φ ≈ φ ∨ φ

φ ∨ ψ ≈ ψ ∨ φ

φ ∨ (ψ ∨ ρ) ≈ (φ ∨ ψ) ∨ ρ

φ ∨ ⊥ ≈ φ

φ ∨ ¬⊥ ≈ ¬⊥

φ ∨ ψ ≈ ¬(¬φ ∧ ¬ψ)

¬(φ ∨ ψ) ≈ ¬(¬φ ∧ ¬ψ)

∨と∧の分配に関するもの

φ ∧ (ψ ∨ ρ) ≈ (φ ∧ ψ) ∨ (φ ∧ ρ)

φ ∨ (ψ ∧ ρ) ≈ (φ ∨ ψ) ∧ (φ ∨ ρ)

→に関するもの

φ→ψ ≈ ¬φ∨ψ

¬(φ→ψ) ≈ φ∧¬ψ

φ→(ψ→ρ) ≈ (φ∧ψ)→ρ ≈ (φ→ρ) ∨ (ψ→ρ)

(φ→ρ) ∨ (ψ→ρ)が成り立つなら、(φ∧ψ)→ρは成り立ちそう。だけど(φ∧ψ)→ρは成り立っても(φ→ρ) ∨ (ψ→ρ)は成り立たないような論理はあるのかな

φ→(ψ∨ρ) ≈ (φ→ψ) ∨ (φ→ρ)

∀に関するもの

∀xφ ≈ ¬∃x¬φ

¬∀xφ ≈ ∃x¬φ

∀xφ* ≈ φ

∀x(φ∧ψ) ≈ ∀xφ ∧ ∀xψ

∀x(φ∨ψ*) ≈∀xφ ∨ ψ*

∃に関するもの

∃xφ ≈ ¬∀x¬φ

¬∃xφ ≈ ∀x¬φ

∃xφ* ≈ φ

∃x(φ∨ψ) ≈ ∃xφ ∨ ∃xψ

∃x(φ∧ψ*) ≈ ∃xφ ∧ ψ*

演習問題

3.1

p48を参考にして、要素数だけに真理値が依存する以下の論理式を書け

対象領域の要素の個数がn以上である

∃x1∃x2…∃xn

(¬(x1=x2) ∧ ¬(x1=x3) ∧ … ¬(x1=xn)∧

¬(x2=x3) ∧ ¬(x2=x4) ∧ … ¬(x2=xn)∧

……

¬(xn-2=xn-1) ∧ ¬(xn-2=xn) ∧

¬(xn-1= xn))

対象領域の要素の個数がn以下である

∀x1∀x2…∀xn∀xn+1

((x1=x2) ∨ (x1=x3) ∨ … (x1=xn)∨

(x2=x3) ∨ (x2=x4) ∨ … (x1=xn)∨

……

(xn-1=xn) ∨ (xn-1=xn+1) ∨

(xn = xn+1))

全射みを感じる

変数から対象領域の要素に対応させた時に必ず、同じ要素を指すものが現れるように変数の数をn+1個にしている感じ

対象領域の個数がちょうどnである

さっきの論理式を∧で結べばOKだと思うけど、もっと別の書き方もあったはず…

∃x1∃x2…∃xn

(¬(x1=x2) ∧ ¬(x1=x3) ∧ … ¬(x1=xn)∧

¬(x2=x3) ∧ ¬(x2=x4) ∧ … ¬(x1=xn)∧

……

¬(xn-2=xn-1) ∧ ¬(xn-2=xn) ∧

¬(xn-1= xn))

∧

∀x1∀x2…∀xn∀xn+1

((x1=x2) ∨ (x1=x3) ∨ … (x1=xn)∨

(x2=x3) ∨ (x2=x4) ∨ … (x1=xn)∨

……

(xn-1=xn) ∨ (xn-1=xn+1) ∨

(xn-1= xn))

他の書き方の例(ちょうど2個)

¬(∀x1∀x2∀x3((x1=x2) ∨ (x1=x3)∨ (x2=x3)) → ∀x1∀x2(x1=x2) )

2個以下なら1個以下ではないみたいな記述

¬(∃x1∃x2¬(x1=x2) → ∃x1∃x2∃x3(¬(x1=x2) ∧ ¬(x1=x3) ∧ ¬(x2=x3)))

2個以上なら3個以上ではないみたいな記述

∀x1∀x2∀x3((x1=x2) ∨ (x1=x3) ∨ (x2=x3)) ∧ ∃x1∃x2¬(x1=x2)

3個未満かつ1個より多い

ここに書いてあったやつ

∃x1∃x2(¬(x1=x2)∧∀x3(x3=x1∨x3=x2))

この論理式がちょうど2個っぽく感じる

3.2

以下の閉論理式がそれぞれ恒真であるか否かを述べ、恒真でない場合はそれを偽にするストラクチャーを示せ

健全性定理使えば、閉論理式の証明を書ければ良さそう。

あとは閉論理式が偽となるようなストラクチャーがあると仮定して背理法かな？

まだこの章だと健全性定理証明してないし、この方法でできるのだろうか？

任意のストラクチャーに対して、恒真であることを示す

ア ((A→B)→A)→A)

恒真である

イ (A→B)∨(B→A)

恒真である

ウ (A→B)→(B→A)

恒真でない

M(A) = 偽

M(B) = 真

エ ∀x∃yR(x,y) → ∃y∀xR(x,y)

恒真でない

M

対象領域{a,b}

M(R(a,a)) = 真

M(R(a,b)) = 偽

M(R(b,a)) = 真

M(R(b,b)) = 偽

オ ∃y∀xR(x,y)→∀x∃yR(x,y)

恒真である

恒真であることどう示せばいいんだろ？(恒真っぽそうだなとはわかるけど)

モデルならいくらでも作れはするけど…

∃y∀xR(x,y)→∀x∃yR(x,y)を偽にするストラクチャーがあると仮定して矛盾させるとか？

⊢∃y∀xR(x,y)→∀x∃yR(x,y) をして、健全性定理を使うぐらいしか浮かばない

カ ∃x(P(x)∧Q(x)) → ∃xP(x)∧∃xQ(x)

恒真である

キ ∃xP(x)∧∃xQ(x) → ∃x(P(x)∧Q(x))

恒真でない

M

対象領域{a,b}

M(P(a)) = 真

M(Q(a)) = 偽

M(P(b)) = 偽

M(Q(b)) = 真

ク ∃x(P(x)∨Q(x))→(∃xP(x)∨∃Q(x))

恒真である

恒真でない

M

対象領域{a,b}

M(P(a)) = 真

M(Q(a)) = 偽

M(P(b)) = 偽

M(Q(b)) = 偽

ケ (∃xP(x)∨∃Q(x))→∃x(P(x)∨Q(x))

恒真である

コ

∀x(P(x)→Q(x))→(∀xP(x)→∀xQ(x))

恒真である

サ

(∀xP(x)→∀xQ(x))→∀x(P(x)→Q(x))

恒真である

恒真でない

M

対象領域{a,b}

M(P(a)) = 真

M(Q(a)) = 偽

M(P(b)) = 偽

M(Q(b)) = 偽