【数理逻辑】学习笔记 009 真值指派
一紙 痕
2021年09月28日 16:09
收录于文集
共32篇

上一篇:【数理逻辑】学习笔记 008 命题逻辑的语言​

【真值指派】

 

真假值集合:{T, F}

其中,T(True)代表“真”,F(False)代表“假”

 

真值指派:如果一个合式公式的集合S为满足以下两点的最小集合:

(1)如果α∈S,则(¬α)也属于S

(2)如果α, β∈S,则α*β也属于S(*可以是四种二元联词中的任意一种)

并且一个从S到{T, F}的映射v满足:对任意两个合式公式α, β∈S,v((¬α)),v(α*β)的值与v(α), v(β)的值之间的关系如下表所示

就称v是S上的一个真值指派。

 

在有的书上,真值指派也叫语义赋值或简称赋值。

 

通过真值指派后,上一节的合式公式才有了“意义”。

 

定义看着比较复杂,举个例子就好懂了:

给出2个原子命题:

A:今天下雨

B:今天周二

那么如果今天是个晴空万里的周二,就有

v(A)=F

v(B)=T

当然,光是A和B,并不能组成一个定义中所说的S,各种通过A、B还有联词和括号能够组成的合式公式都需要属于S,并且这些合式公式都要通过v按照上面的表格映射到真假值集合上。最终就得到如下的映射:

【语义后承】

 

如果v(α)=T,就称v满足α

 

重言蕴含:如果Σ中所有公式的真值指派都满足α,就称“Σ重言蕴含α”或者“α是Σ的语义后承”,记作Σ⊨α。

(Σ是一个合式公式的集合)

 

简单理解就是:用Σ里的合式公式可以推出α

 

比如侦探小说里,我们令

A:X是犯人

B:Y是犯人

C:Z是犯人

现在我们得到3条线索:

(X∨Y):X或者Y是犯人

(X∨Z):X或者Z是犯人

(¬(Y∨Z)):不可能Y或者Z是犯人

可以令Σ={(X∨Y), (X∨Z), (¬(Y∨Z))}

此时把真值表列出来就可以发现:

只有表中红色的那一行才能同时满足Σ中的所有合式公式。

而此时A必是被满足的,就有Σ⊨A

那也就是说,只要这3条线索都成立,就能断定犯人是A。

【重言】

 

重言式:如果合式公式α是空集的语义后承,即∅⊨α,就称α是一个重言式(也叫永真式)。

 

不管怎样的真值指派,空集中的所有合式公式必定是被满足的(因为根本就没有),所以不管怎样的真值指派都能满足α,也即α永远为真。

 

最典型的重言式就是今天下雨或者不下雨了,当然,得用逻辑的语言来写:(A∨(¬A))

 (A表示今天下雨)。

 

当Σ中只有一个元素β,也即Σ={β}时,可以把Σ⊨α简写成β⊨α。

 

重言等价:如果β⊨α且α⊨β,则称α和β重言等价。

 

以下是一些重言式的例子:

 

(1)结合律

((α∨(β∨γ))↔((α∨β)∨γ))

((α∧(β∧γ))↔((α∧β) ∧γ))

(2)交换律

((α∨β) ↔(β∨α))

((α∧β) ↔(β∧α))

(3)分配律

((α∧(β∨γ))↔((α∧β)∨(α∧γ)))

((α∨(β∧γ))↔((α∨β)∧(α∨γ)))

(4)双重否定

((¬ (¬α))↔α)

(5)德摩根律

((¬(α∨β)) ↔((¬α) ∧(¬β)))

((¬(α∧β)) ↔((¬α) ∨(¬β)))

(6)排中律

(α∨(¬α))

(7)矛盾律

(¬(α∧(¬α)))

(8)逆否一致性

((α→β) ↔((¬β) →(¬α)))

 

【习题选解】

习题2.3.1 证明下列两公式互不重言蕴含:

(α↔(β↔γ)) , ((α∧(β∧γ))∨((¬α)∧((¬β)∧(¬γ))))

证:

① 取v(α)=T,v(β)=F,v(γ)=F

则v(左边)=T,v(右边)=F

所以左边不重言蕴含右边

② 取v(α)=F,v(β)=F,v(γ)=F

则v(左边)=F,v(右边)=T

所以右边不重言蕴含左边

 

综合①②,两式互不重言蕴含

习题2.3.2 回答以下问题:

(1)公式(((α→β) →α) →α)是重言式吗?

(2)递归地定义%CE%B3_k如下:%CE%B3_0%3D(%CE%B1%E2%86%92%CE%B2)并且%CE%B3_%7Bk%2B1%7D%3D(%CE%B3_k%E2%86%92%CE%B1)。找出所有使%CE%B3_k为重言式的k。

解:

直接将第(2)问中的%CE%B3_0到%CE%B3_3的真值表列出:

(1)(((α→β) →α) →α)即为%CE%B3_2

从上表中可以看出v((((α→β) →α) →α))恒为T,所以是重言式

(2)从上表可以看出,v(%CE%B3_1)和v(%CE%B3_3)恒等,所以%CE%B3_k的真值变化周期应为2

又因为是%CE%B3_2重言式

所以k为正偶数时,%CE%B3_k为重言式

 

习题2.3.5 证明Σ∪{α}⊨β当且仅当Σ⊨(α→β)。

证:

对任意一种真值指派v,令X=(v(α)=T),Y=(v(β)=T),Z=(v(σi)=T)

(σi表示Σ中的任一元素)

则左边等价于((X∧Z) →Y)

右边等价于(Z→(X→Y))

由真值表知,左边右边等价

证毕

 

习题2.3.9 证明一个真值指派v满足公式

(%E2%80%A6%E2%80%A6%EF%BC%88%EF%BC%88A_1%E2%86%94A_2)%E2%86%94A_3)%E2%80%A6%E2%80%A6%E2%86%94A_n)

当且仅当在1≤i≤n中对偶数多个i,v(A_i)%3DF

证:

对n进行数学归纳法:

① n=1时,公式即为A_1

此时如果偶数个v(A_i)%3DF,那就只能是0个,也就是v(A_1)%3DT

如果是奇数个v(A_i)%3DF,那就只能是1个,也就是v(A_1)%3DF

所以此时结论成立。

② 假设当n=k时结论成立,则n=k+1时:

记B_k%3D(%E2%80%A6%E2%80%A6%EF%BC%88%EF%BC%88A_1%E2%86%94A_2)%E2%86%94A_3)%E2%80%A6%E2%80%A6%E2%86%94A_k)

则B_%7Bk%2B1%7D%3D(B_k%E2%86%94A_%7Bk%2B1%7D)

(i)如果v(B_k)%3DT,则根据假设,1≤i≤k中有偶数个v(A_i)%3DF

此时,v(B_%7Bk%2B1%7D)%3Dv(A_%7Bk%2B1%7D)

如果v(A_%7Bk%2B1%7D)%3DF,则1≤i≤k+1中有奇数个v(A_i)%3DF,且此时v(B_%7Bk%2B1%7D)%3DF,也即v不满足公式

如果v(A_%7Bk%2B1%7D)%3DT,则1≤i≤k+1中仍有偶数个v(A_i)%3DF,且此时v(B_%7Bk%2B1%7D)%3DT,也即v满足公式

所以v(B_k)%3DT时,结论成立

(ii)如果v(B_k)%3DF,则根据假设,1≤i≤k中有奇数个v(A_i)%3DF

同理可得此时结论也成立

综合(i)(ii)知,n=k+1时结论也成立

综合①②和数学归纳法即可得到原结论

证毕

 

【词汇中英日对照表】