
真假值集合:{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)递归地定义如下:
并且
。找出所有使
为重言式的k。
解:
直接将第(2)问中的到
的真值表列出:

(1)(((α→β) →α) →α)即为
从上表中可以看出v((((α→β) →α) →α))恒为T,所以是重言式
(2)从上表可以看出,v()和v(
)恒等,所以
的真值变化周期应为2
又因为是重言式
所以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满足公式
当且仅当在1≤i≤n中对偶数多个i,
证:
对n进行数学归纳法:
① n=1时,公式即为
此时如果偶数个,那就只能是0个,也就是
如果是奇数个,那就只能是1个,也就是
所以此时结论成立。
② 假设当n=k时结论成立,则n=k+1时:
记
则
(i)如果,则根据假设,1≤i≤k中有偶数个
此时,
如果,则1≤i≤k+1中有奇数个
,且此时
,也即v不满足公式
如果,则1≤i≤k+1中仍有偶数个
,且此时
,也即v满足公式
所以时,结论成立
(ii)如果,则根据假设,1≤i≤k中有奇数个
同理可得此时结论也成立
综合(i)(ii)知,n=k+1时结论也成立
综合①②和数学归纳法即可得到原结论
证毕
