离散数学第2章 谓词逻辑.ppt

* 　　例2-2.3 指出下列公式中的量词辖域、个体变元的约束出现和自由出现。 　　（1） (?x)(P(x)→(?y)Q(x，y)) 解： (?x)的辖域是(P(x)→(?y)Q(x，y)),(?y)的辖域为Q(x，y)； 对于(?y)的辖域而言，y为约束出现，x为自由出现。 对于(?x)的辖域来说，x和y均为约束出现。 对于整个公式来说，x约束出现1次，y约束出现2次。 * 例2-2.3 指出下列公式中的量词辖域、个体变元的约束出现和自由出现。　　 （2）(?x)H(x)∧L(x，y) 　解： (?x)的辖域是H(x)，x为约束出现， L(x，y)中的x和y都为自由出现。 对于整个公式来说，x既为约束出现又为自由出现，y自由出现1次。 * 例2-2.3 指出下列公式中的量词辖域、个体变元的约束出现和自由出现。 　　 （3）(?x)(?y)(P(x，y)∨Q(y，z))∧(?x)R(x，y) 　　 　解： (?x)的辖域为(?y)(P(x，y)∨Q(y，z))，(?y)的辖域为(P(x，y)∨Q(y，z))，x和y为约束出现，z为自由出现。 (?x)的辖域是R(x，y)，x为约束出现，y为自由出现。 对于整个公式来说，x为约束出现，y既为约束出现又为自由出现，z为自由出现。 * 　定义2-2.5 设A为任意一个公式，若A中无自由出现的个体变元，则称A为封闭的合式公式，简称闭式。 练习 指出下列公式量词的辖域和变元的约束出现和自由出现： (1) ?x(P(x)∨Q(y)∨H(x,z)) (2) ?x(P(x)∨Q(y))∨H(x,z) (3) ?x?y(P(x)→Q(x,y)) 解： (1)(P(x)∨Q(y)∨H(x,z))为量词?x的辖域，其中x是约束变元，y，z是自由变元 (2) P(x)∨Q(y)是量词?x的辖域，x是约束变元，y是自由变元，而H(x,z)中的x，z都是自由变元； 在同一个公式中，变元的出现可以既是约束出现也可以自由出现。要注意辖域：关键是有括号与无括号的区别 (3) ?x?y(P(x)→Q(x,y))：P(x)→Q(x,y)是量词?x，?y的辖域，x，y都是约束出现，无自由出现的变元，这是一个闭式. * * §2-2-3 谓词公式的解释 　　 　　定义2-2.6 一个解释I由下面4部分组成。 (1)非空个体域D； (2)D中一部分特定元素（用来解释个体常元）； (3)D上一些特定的函数（用来解释出现的函数变元）； (4)D上一些特定谓词（用来解释谓词变元）。 　　设公式A，取个体域D，把A中的个体常元符号、函数符号、谓词符号分别替换成它们在I中的解释，称所得到的公式A’为A在I下的解释，或A在I下被解释成A’。 * Table1 量词 描述 真 假 ?xP(x) 对于所有的x，P(x)都为真。 至少存在一个x，使得P(x)为假。 ?xP(x) 至少存在一个x，使得P(x)为真。 对于所有的x，P(x)都为假。 * Table2 两个变量的量词 描述 真 假 ?x?yP(x,y) ?y?xP(x,y) 对于任意一组x和y，P(x,y)为真 存在一组x和y，使得P(x,y)为假 ?x?yP(x,y) 对于任意x，存在y，使得P(x,y)为真 存在x，对于任意y，P(x,y)为假 ?x?yP(x,y) 存在x，对于任意y，P(x,y)为真 对于任意x，存在y，使得P(x,y)为假 ?x?yP(x,y) ?y?xP(x,y) 存在一组x和y，使得P(x,y)为真 对于任意一组x和y，P(x,y)为假 * 　　例2-2.5 讨论?x?yP(x，y)在P(x，y)具有下列意义下的真值情况。个体域为实数集合。 　　（1）P(x，y)：x+y=0； 真命题 　　（2）P(x，y)：x×y=0； 真命题 　　（3）P(x，y)：x+y=1； 真命题 　　（4）P(x，y)：x×y=1。 假命题 　　 相同个体域内，谓词不同的解释导致其真值可能不同（也可能相同） * 　　例2-2.6 将命题“存在数x，使得x+7=5”符号化，并讨论真值，分别取个体域为 　　（1）D1=N 　　（2）D2=R 　　（3）D3为全总个体域 　　解：设H(x)：x+7=5 　　（1）(?x)H(x) 在D1=N中为假 　　（2）(?x)H(x) 在D2=R中为真 　　（3）又设F(x)：x为数。命题符号化为(?x)(F(x)∧H(x))，在D3中为真。 不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）。 * 　　例2-2.7 给定解释I如下： 　　① DI?=R； 　　② DI中特定元素a=0； 　　③ DI上特定函数f(x，