1、第二章 逻辑和证明,谓词和量词命题在表达逻辑推理时有局限性：没有进一步分析原子命题的构成方式苏格拉底三段论在命题的框架下无法分析 凡人都是要死的 苏格拉底是人 所以，苏格拉底是要死的“命题函数”：含变量的判断（陈述句、“命题”） x+13，x+y=z*x，x是夜大学生 不是命题（为什么？），但表示了某种命题的结构 一旦给变量赋予具体值后，它们就成为命题,2.3.1 谓词 陈述句可分解为两个组成成分：主语和谓语（原子）“命题函数”进一步分解为两个组成成分：变量（如x,y等）和谓词（P(x), Q(x,y)等） 变量表示某个对象，谓词表示对象的性质或相互之间的关系 例1 语句(“命题函数”)“x3
2、”可用P(x)表示，P(x) 是一元谓词：x3 P(x)不是命题，是“命题函数”P(2) 、P(3)、 P(4) 和P(100)都是命题 P(2) 和P(3)为假， P(4) 和P(100)为真,例 语句(“命题函数”)“x=y+3且x3”可表示为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)
3、的语句，表示“命题函数”在n元组(x1,x2,xn)上的值,2.3.2 量词 从“命题函数”得到的命题的有两种方式：变量赋值、变量量化 例 语句“对所有的x，x3”是命题，它是“命题函数”“x3”的量化， 即对P(x)中的变量x的量化结果 语句“存在x，x3”也是命题，它也是“命题函数”“x3”的量化， 即对P(x)中的变量x的量化结果 P(x)两类量化：全称量化、存在量化,定义1 全称量化（）真值表判定法“命题函数”P(x)的全称量化是命题:“P(x)对x在其论域的所有值为真”这个命题表示为xP(x)称为全称量词命题xP(x)的等价含义：“对所有x，P(x)”“对每个x，P(x)” 变量的论
4、域：在所讨论的问题范围内，变量所可能取的值的集合,例6 谓词P(x)：x+1x，“命题函数”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)：x23，“命题函数”P(x)存在量化后得到命题xP(x) 若论域是实数集合，则此命题为真值是 存在量化命题xP(x)的真假性判断 若论域是有限集x1,x2,xn ，则xP(x)为真当且仅当 命题P(x1)、P(x2)、P(x
5、n)至少有一个为真，也即命题P(x1) P(x2) P(xn) 为真例11谓词P(x)：x210，若论域是不超过3的正整数的集合，则 xP(x)为真（P(1) P(2) P(3)为真）若论域是不超过4的正整数的集合，则 xP(x)为真（P(1) P(2) P(3) P(4)为真）若论域是47之间的正整数的集合，则 xP(x)为假（P(4) P(5) P(6) P(7)为假）若论域是整数集，则xP(x)为真,变量全称量词和存在量词的含义总结 约束变量：被量词作用或被赋值的变量 自由变量：非约束的变量 命题中不能含有自由变量 命题函数转变为命题时，出现在命题函数中的所有变量都必须被约束,2.3.3
6、 翻译语句为逻辑表达式 全称量化往往需要使用蕴涵式 存在量化往往需要使用合取式 例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去过加拿大”。语句“这个班上某个学生去过墨西哥”可
7、表示为xM(x).语句“这个班上每个学生或去过加拿大，或去过墨西哥”可表示为x(C(x)M(x). 例16 把语句“每人恰有一个最好的朋友”表示为逻辑表达 式。 解 令B(x,y)为语句“ y 是x 的最好朋友”。注意本例中的句子说的是，对每个x 都有另一人y 是x 的最好朋友，而且如果z 是不同于y 的另一人，则z 不是x 的最好朋友。于是可以把这个语句翻译为 xyz(B(x,y)(zy)B(x,z),苏格拉底三段论的翻译例19（需要微积分知识）用量词表示极限的定义。,例20 考虑下面这些语句，其中头两句称为前提，第三句称为结论。作为一个整体，他们被称为论证。 “所有狮子都是凶猛的。” “有
8、些狮子不喝咖啡。” “有些凶猛的动物不喝咖啡。”令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”，量化语句xyP(x,y)真值是什么？ 解 量化语句 xyP(x,y) 表示的命题是 “
9、对所有实数x和所有实数y，x+y=y+x成立。” 因为P(x,y)对所有实数x 和y 成真，xyP(x,y)成真。,例23 令Q(x,y)表示“”，量化语句yxQ(x,y)和xyQ(x,y)的真值是什么？ 解 量化语句yxQ(x,y)表示的命题是“有个实数y能使Q(x,y)对每个实数x成立。”不管y取什么值，只有一个x的值能使x+y=0成立。因为没有实数y能使x+y=0对所有实数x成立，语句yxQ(x,y)为假。 量化语句xyQ(x,y)表示的命题是“对每个实数x都有一个实数y使Q(x,y)成立。”给定一个实数x，总有一个实数y能使x+y=0，这个实数就是y=-x。因此语句xyQ(x,y)为真
10、。 两个变量的量化的顺序 xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y) xyP(x,y) yxP(x,y),量化表达式的否定 xP(x) xP(x)xP(x) xP(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）消除、和
11、以外的联接词，用 AB替换 AB 替换AB4）将内移到谓词前。用xA(x)替换 xA(x) xA(x)替换 xA(x) AB替换 (AB) AB替换 (AB) 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重新
12、命名为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）xyz(xy)(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)改为前束范式。,
