【数理逻辑】学习笔记 008 命题逻辑的语言
一紙 痕
2021年09月26日 11:53
收录于文集
共32篇

【语言】

在这节的学习之前首先要抛弃我们已经学过的一些逻辑知识,比如“当且仅当a和b都为真时,a且b才为真”,在这里先要把“且”当成一个无意义的符号。

有点像是一个机器人去学习,它不知道“且”是什么意思,只会根据你教给它的一些语法来说一些没有语法错误的话。

这里说的“语法”就好比我们在学语文或英语的时候会学习“主+谓+宾”结构,它告诉了我们一个完整的句子要怎么说。当我们知道了哪些词可以作为主语,哪些词可以作为谓语,哪些词可以作为宾语后,就算我们不知道每个词的含义,我们也能套进这个结构里来组成一句没有语法错误的话。

 

命题逻辑的语言的元素包括以下3部分:

看着挺复杂,其实就相当于我们中学里学的简单命题(这里叫原子命题)和复合命题。第一排的命题符号就可以用来表示各种简单命题,简单命题通过联词和括号就组成了复杂命题。

只不过在数理逻辑中,给几个命题联词各取了一个专业的名字。

用上表中的各个元素进行随意的排列组合成一串,就能得到一个表达式,例如“%C2%ACA_0 ”,“(→”。

当然,表达式是任意的,不用考虑任何语法规则。

下一段要讲的合式公式会定义出什么样的表达式是符合语法的。

 

【合式公式】

 

全体合式公式的集合(记作PROP):命题逻辑语言全体合式公式的集合是满足以下条件的表达式最小集合

(1)每个命题符号都是合式公式

(2)封闭性:如果α和β是合式公式,则(¬α) , (α∧β) , (α∨β) , (α→β) , (α↔β)都是合式公式

 

其实就相当于我们中学学过的所有简单命题和复合命题组成的集合。

如果用上一章学过的“关系​”的角度来说,把全体合式公式的集合记为𝓛,那么:

¬是𝓛×𝓛上的一个二元关系

∧, ∨, →, ↔是𝓛×𝓛×𝓛上的四个三元关系

 

在这个定义中,“封闭性”规定了哪些表达式必须属于𝓛,而“最小集合”则规定了只有哪些表达式能属于𝓛。

 

合式公式也可以简称公式。

 

构造序列:如果一个表达式的有穷序列(%CE%B1_0%2C%20%CE%B1_1%2C%20%E2%80%A6%E2%80%A6%2C%20%CE%B1_n)满足

(1)%CE%B1_n%20%3D%CE%B1

(2)对每一个%CE%B1_i,满足“%CE%B1_i是一个命题符号”或者“存在j, k<i 使得%CE%B1_i%3D(%C2%AC%CE%B1_j)或者%CE%B1_i%3D(%CE%B1_j*%CE%B1_k)”

就称(%CE%B1_0%2C%20%CE%B1_1%2C%20%E2%80%A6%E2%80%A6%2C%20%CE%B1_n)为α的一个构造序列

 

注:第(2)条中的*代表了∧,∨,→,↔这四种二元联词中可以任取

 

例如:

这两个都是((%C2%ACA_1)%20%E2%88%A8A_2)的构造序列,可以一一对照定义来看每一个元素是否都满足。

从这两个例子也可以看出:每个合式公式都可以由多种不同的构造序列。

【归纳原理】

 

定理8.1(归纳原理):令P(α)为一个关于合式公式的性质。假设

(1)对所有的命题符号A_i,性质P(A_i)成立

(2)对所有的合式公式α和β,如果P(α)和P(β)成立,则P((¬α))和P((α*β))都成立

(这里“*”的含义同上)

那么P(α)对所有的合式公式α都成立

 

归纳原理和数学归纳法的核心思想其实都一样:用一个起点(满足性质P)和一些运算可以遍历某个集合内的所有的元素,并且保证每次运算后P能够保持,就可以证明这个集合内的元素都满足性质P。

【习题选解】

 

习题2.2.3 证明归纳原理。

证:采用反证法,假设归纳原理不成立,则存在一个合式公式r,使得P(r)不成立

假设r的构造序列为(r_0%2C%20r_1%2C%20%E2%80%A6%E2%80%A6%2C%20r_n),r不成立即rn不成立

根据构造序列的定义和归纳原理的条件(2),必定存在一个i<n,使得不成立

由于i,n都是自然数,所以i≤n-1

以上步骤可以无限重复,而r的构造序列为一个有穷序列

所以最终会推导出P(r_0)不成立

根据构造序列的定义,P(r_i)必是一个命题符号(因为不可能有r_0之前的元素来构成它)

这与归纳原理的条件(1)矛盾

所以假设不成立,归纳原理正确

证毕

 

习题2.2.4 证明没有长度为0,2,3或6的合式公式,但其他长度皆有可能。

证:

① 令性质P为长度不等于0,2,3,6

因为每个命题符号长度都是1,所以对所有命题符号A_i,P(A_i)成立

② 如果合式公式α和β满足P(α)和P(β),那么:

如果 (¬α)或者 (α*β)的长度为6

可以推出(i)或(ii)

(i)α的长度为3,因为(¬α)相较α而言多了3个元素:“(”、“)”、“¬”

(ii)α和β的长度之和为3,原因同上

因为P(α)和P(β)成立,所以(i)(ii)都不可能

所以(¬α)和 (α*β)的长度都不为6

同理,可以推出(¬α)和 (α*β)的长度也不为0,2,3

也就是说,P((¬α))和P((α*β))都成立

由①②和归纳原理得,P对任何合式公式都成立,也即没有长度为0,2,3或6的合式公式

A_1、(A_1%E2%88%A7A_2)%20、(A_1%E2%88%A7(A_1%E2%88%A7A_2))的长度分别为1,5,9

由任何一个合式公式α,只要取(¬α)就能使长度增加3,不难看出,从上面3个合式公式经过不停取¬就能获得长度0,2,3,6以外任意长度的合式公式

证毕

 

习题2.2.5 已知公式α中一元联词¬出现的次数为m,其他4个二元联词出现的总次数为n。找出α的长度。

解:

设公式里共出现r次命题符号

可以用归纳原理证明,一个合式公式中,二元联词出现的次数比命题符号出现的次数少1次(证明过程略)。

那么就有n=r-1,即r=n+1

每个联词必定和一对括号对应,所以括号出现的次数为2(m+n)

出现一次¬,公式除了括号以外长度增加1

所以公式的总长度应为命题符号出现次数、括号出现次数、联词出现次数的总和,也即有

α的长度=r+2(m+n)+n+m

将r=n+1代入上式即得到α的长度为3m+4n+1

(可以把上一题中举的几个例子带入验证)

 

习题2.2.8 给定公式α的一个构造序列,其中α不包含命题符号A_4。在此构造序列中删除所有包含A_4的项,证明删除后的序列仍是α的一个构造序列。

证:

用反证法,假设删除A_4后的序列不是α的构造序列

① 从有穷的α的构造序列中删除包含A_4的项后得到的序列也必定是有穷的

② 由于α不包含命题符号A_4,所以序列的最后一项必定还是α

③ 令原序列为(%CE%B1_0%2C%20%CE%B1_1%2C%20%E2%80%A6%E2%80%A6%2C%20%CE%B1_n),删除包含A_4的项后的序列为(%CE%B2_0%2C%20%CE%B2_1%2C%20%E2%80%A6%E2%80%A6%2C%20%CE%B2_m)

任取一个%CE%B2_i取自元序列中的%CE%B1_r,如果%CE%B2_i不是命题符号

则应存在s, t<r,使得%CE%B1_r%3D(%C2%AC%CE%B1_s)或者%CE%B1_r%3D(%CE%B1_s*%CE%B1_t)

由于%CE%B1_r没有被删除,所以αr中不包含A_4

那么下列两种情况至少有一种成立:

(i)%CE%B1_s不包含A_4且%CE%B1_r%3D(%C2%AC%CE%B1_s)

(ii)%CE%B1_s和%CE%B1_t都不包含A_4且%CE%B1_r%3D(%CE%B1_s*%CE%B1_t)

如果(i)成立,则%CE%B1_s不会被删除,它会保留到删除后的序列中,变成%CE%B2_j,由于保序性,应有j<i,即有存在j<i使得%CE%B2_i%3D(%C2%AC%CE%B2_j)

同理,如果(ii)成立,应有存在j, k<i,使得%CE%B2_i%3D(%CE%B2_j*%CE%B2_k)

所以删除后的序列中任何一个βi或者是命题符号,或者存在j, k<i 使得%CE%B2_i%3D(%C2%AC%CE%B2_j)或者%CE%B2_i%3D(%CE%B2_j*%CE%B2_k)

根据①②③,删除后的序列仍是α的一个构造序列

证毕

【词汇中英日对照表】