第二章 逻辑和证明 谓词和量词 命题在表达逻辑推理时有局限性：没有进一步分析原子命题的构成方式 苏格拉底三段论在命题的框架下无法分析 凡人都是要死的 苏格拉底是人 所以，苏格拉底是要死的 “命题函数”：含变量的判断（陈述句、“命题”） x+1>3，x+y=z*x，x是夜大学生 不是命题（为什么？），但表示了某种命题的结构 一旦给变量赋予具体值后，它们就成为命题

2.3.1 谓词 陈述句可分解为两个组成成分：主语和谓语 （原子）“命题函数”进一步分解为两个组成成分： 变量（如x,y等）和谓词（P(x), Q(x,y)等） 变量表示某个对象，谓词表示对象的性质或相互之间的关系 例1 语句(“命题函数”)“x>3”可用P(x)表示，P(x) 是一元谓词：x>3 P(x)不是命题，是“命题函数” P(2) 、P(3)、 P(4) 和P(100)都是命题 P(2) 和P(3)为假， P(4) 和P(100)为真

例2 语句(“命题函数”)“x=y+3”可表示为Q(x,y) Q(x,y)是二元谓词：x=y+3 Q(x,y)、Q(3,y)、Q(x,100)都不是命题，是“命题函数” Q(1,2)、Q(5,8)、Q(2,1)和Q(5,4)都是命题 Q(1,2)和Q(5,8)为假， Q(2,1)和Q(5,4)为真

例 语句(“命题函数”)“x=y+3且x>3”可表示为Q(x,y) P(x) P是一元谓词，Q是二元谓词，如上 Q(x,y) P(x)不是命题，是“命题函数” Q(1,2) P(1)、Q(5,8) P(5)、Q(2,1) P(2)和Q(5,4) P(5)都是命题 Q(1,2) P(1)、Q(5,8) P(5)和Q(2,1) P(2) 为假，Q(5,4) P(5)为真 n元谓词P：形为P(x1,x2,…,xn)的语句， 表示“命题函数”在n元组(x1,x2,…,xn)上的值

2.3.2 量词 从“命题函数”得到的命题的有两种方式：变量赋值、变量量化 例 语句“对所有的x，x>3”是命题，它是“命题函数”“x>3”的量化， 即对P(x)中的变量x的量化结果 语句“存在x，x>3”也是命题，它也是“命题函数”“x>3”的量化， P(x)两类量化：全称量化、存在量化

定义1 全称量化（）真值表判定法 “命题函数”P(x)的全称量化是命题:“P(x)对x在其论域的所有值为真” 这个命题表示为xP(x) 称为全称量词 命题xP(x)的等价含义： “对所有x，P(x)” “对每个x，P(x)” 变量的论域：在所讨论的问题范围内，变量所可能取的值的集合

例6 谓词P(x)：x+1>x，“命题函数”P(x)全称量化后得到命题 xP(x) 若论域是实数集合，则此命题为真 全称量化命题xP(x)的真假性判断 若论域是有限集{x1,x2,…,xn }，则 xP(x)为真当且仅当命题P(x1)、P(x2)、…、P(xn)都为真，也即命题P(x1)P(x2)  …  P(xn) 为真 例8 判断谓词P(x)：x2<10的真假 若论域是不超过3的正整数的集合，则 xP(x)为真（P(1)  P(2)  P(3)为真） 若论域是不超过4的正整数的集合，则 xP(x)为真（P(1)  P(2)  P(3)  P(4)为假） 若论域是整数集，则 xP(x)为假

例 谓词P(x)：x2≥0，“命题函数”P(x)全称量化后得到命题 xP(x) 若论域是实数集合，则此命题为真 若论域是复数集合，则此命题为假 命题符号化的方法往往不止一种，与论域也有关 例5 为表示“本班每一个学生都已学过微积分” 定义谓词P(x)：“x已学过微积分” 上述语句表示为 xP(x) 当论域由本班全体学生组成时，为真命题 当论域由ECNU全体学生组成时，为假命题 （接下页）

另：定义谓词P(x)：“x已学过微积分”，谓词S(x)：“x属于本班” 上述语句表示为x(S(x) P(x)) 论域由本班全体学生组成、由ECNU全体学生组成、 或全体人学生组成时，都为真命题 定义2 存在量化（） “命题函数”P(x)的全称量化是命题:“论域中存在一个元素x，使P(x)为真” 这个命题表示为xP(x) 称为存在量词 命题xP(x)的等价含义：“有一个x，使得P(x)” “至少有一个x，使得P(x)” “对某个x，P(x)”

例9 谓词P(x)：x>3，“命题函数”P(x)存在量化后得到命题xP(x) 若论域是实数集合，则此命题为真值是 存在量化命题xP(x)的真假性判断 若论域是有限集{x1,x2,…,xn }，则xP(x)为真当且仅当 命题P(x1)、P(x2)、…、P(xn)至少有一个为真，也即命题P(x1) P(x2) …P(xn) 为真 例11谓词P(x)：x2<10， 若论域是不超过3的正整数的集合，则 xP(x)为真（P(1) P(2) P(3)为真） 若论域是不超过4的正整数的集合，则 xP(x)为真（P(1) P(2) P(3) P(4)为真） 若论域是4—7之间的正整数的集合，则 xP(x)为假（P(4) P(5) P(6) P(7)为假） 若论域是整数集，则xP(x)为真

变量全称量词和存在量词的含义总结 约束变量：被量词作用或被赋值的变量 自由变量：非约束的变量 命题中不能含有自由变量 命题函数转变为命题时，出现在命题函数中的所有变量都必须被约束

2.3.3 翻译语句为逻辑表达式 全称量化往往需要使用蕴涵式 存在量化往往需要使用合取式 例14 符号化“有些实数是有理数”，“实数都是有理数” 解 令变量x的论域为所有的实数集合，令R(x)为语句“x为实数”，Q(x)为语句“x为有理数”。则语句“有些实数是有理数”可表示为x(R(x)∧Q(x))；语句“实数都是有理数”可表示为x(R(x)∧Q(x)). 例15 用量词表达语句“这个班上某个学生去过墨西哥”和 “这个班上每个学生或去过加拿大，或去过墨西哥”。 （接下页）

解 令变量x的论域为这个班所有学生的集合，令M(x)为语句“x去过墨西哥”，C(x)为语句“x去过加拿大”。语句“这个班上某个学生去过墨西哥”可表示为xM(x).语句“这个班上每个学生或去过加拿大，或去过墨西哥”可表示为x(C(x)M(x)). 例16 把语句“每人恰有一个最好的朋友”表示为逻辑表达 式。 解 令B(x,y)为语句“ y 是x 的最好朋友”。注意本例中的句子说的是，对每个x 都有另一人y 是x 的最好朋友，而且如果z 是不同于y 的另一人，则z 不是x 的最好朋友。于 是可以把这个语句翻译为 xyz(B(x,y)∧((z≠y)→¬B(x,z)))

苏格拉底三段论的翻译 例19（需要微积分知识）用量词表示极限的定义。

例20 考虑下面这些语句，其中头两句称为前提，第三句称为结论。作为一个整体，他们被称为论证。 “所有狮子都是凶猛的。” “有些狮子不喝咖啡。” “有些凶猛的动物不喝咖啡。” 令P(x),Q(x),R(x)分别为语句“x是狮子”，“x是凶猛的”，“x喝咖啡”。假定所有动物的集合为论域，用量词及P(x),Q(x),R(x)表示上述语句。 解 可以将这些句子表示为： x(P(x) Q(x)) x(P(x)) R(x)) x(Q(x)  R(x))

2.3.4 命题函数的逻辑等价 命题的等价模式在命题函数中都成立 多重量化中的量词顺序 若两个量词相同，则它们的顺序无关紧要 若两个量词不相同，则它们的顺序是重要的 例22 令P（x,y）为语句“x+y=y+x”，量化语句xyP(x,y)真值是什么？ 解 量化语句 xyP(x,y) 表示的命题是 “对所有实数x和所有实数y，x+y=y+x成立。” 因为P(x,y)对所有实数x 和y 成真，xyP(x,y)成真。

例23 令Q(x,y)表示“ｘ＋ｙ＝０”，量化语句yxQ(x,y)和xyQ(x,y)的真值是什么？ 解 量化语句yxQ(x,y)表示的命题是“有个实数y能使Q(x,y)对每个实数x成立。”不管y取什么值，只有一个x的值能使x+y=0成立。因为没有实数y能使x+y=0对所有实数x成立，语句yxQ(x,y)为假。 量化语句xyQ(x,y)表示的命题是“对每个实数x都有一个实数y使Q(x,y)成立。”给定一个实数x，总有一个实数y能使x+y=0，这个实数就是y=-x。因此语句xyQ(x,y)为真。 两个变量的量化的顺序 xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) xyP(x,y)≠ yxP(x,y)

量化表达式的否定 xP(x)  xP(x) xP(x)  xP(x)

例 “本班每一个学生都已学过微积分” “本班有学生学过微积分 定义谓词P(x)：“x已学过微积分” xP(x)，xP(x) （B不含自由的x） （A(x)不含y）

前束范式: Qx1 Qx2… Qxn P(x1,x2,…,xn) P是不含量词的“命题函数”，Q是量词 “命题函数”→前束范式 1）消去所有没有意义的量词。 2）消除公式中的同名变量。换名，从左向右进行，直到所有的约束变量和自由变量都不同。 3）消除、和以外的联接词，用 AB替换 AB 替换AB 4）将内移到谓词前。用 xA(x)替换 xA(x) xA(x)替换 xA(x) AB替换  (AB) AB替换  (AB) A替换   A

5）将量词左推到前缀所在的位置。用 (x(A(x)∨B))替换 (x(A(x)∨B))替换 (x(A(x)∧B))替换 (x(A(x)∧B))替换 (x(A(x)∧B(x)))替换 ( x)A(x)∧ ( x)B(x) (x(A(x)∨B(x)))替换 (x)A(x)∨(x)B(x) 例24 (x)((( y)A(x)∨(z)B(z,y))→¬(y)C(x,y)的前束范式 解：（1）在A(x) 前面的量词(y)没有意义，可以去掉，得 到 D1 ： （接下页）

（2）将y重新命名为u，得到 D2 ： （3）在D2中消去，得到 D3 ： （4）将D3 中的内移，得到 D4 ： （5）将D4 中的(z)和(u)左移，得到 D5 ：

习题 1. 令P（x）表示语句“单词x含字母a”。下列各项的真值是什么？ 2. 令C(x,y)表示“x注册了y”，其中x的论域是你校全体学生的集合，y的论域是你校开设所有课程的集合。用简单的句子表达下列语句。 a) x(C(x, Math 222)C(x, CS 252)) b）xyz((xy)(C(x,z)C(y,z))) 3.令Q(x,y)为语句“ｘ为ｙ的参赛者”。用Ｑ(x,y)、量词和逻辑连接符表达下列各句，其中x的论域是你校所有学生的集合，y的论域是所有电视智力竞赛节目。 a)每个电视智力竞赛节目都有你校的一名参赛学生。 b)你校至少有两个学生参加了Jeopardy比赛。

4.用量词表达下列语句，然后去该语句的否定并使否定符不在量词的左边。再用简单句表达这否定（不要简单的表达为“不是……”）。 a)班上每人恰恰给另外两个同班同学发过电子邮件。 b)某个学生已完成本书每道练习。 5.证明语句x(P(x)Q(x))和xP(x) xQ(x)有同样的真值。 6.把语句xP(x) xQ(x)改为前束范式。