离散数学第一章4到5节.pptVIP

对这些公式的证明只须应用前面得到的等价式和蕴涵式即可推出 例：证明 ?xA(x)→?xB(x)??x(A(x)→B(x)) (即I19) ?xA(x)→?xB(x) ?┐?xA(x) ? ?xB (x) ??x┐A(x) ??xB(x ) 证明: ??x(┐A(x)?B(x)) 例：证明?xA(x)→B??x(A(x)→B) (即E31) ?xA(x)→B 证明: ?┐?xA(x)?B ??x┐A(x)?B ??x(┐A(x)?B) 量词辖域扩张及收缩律 ??x(A(x)→B) (?x)(?y) (?x)(?y) (?x)(?y) (?x)(?y) (?y)(?x) (? y)(?x) (?y)(?x) (?y)(?x) B1 B6 B4 B2 B3 B5 B7 B8 （1）含有两个量词的等价式和蕴涵式 6.多个量词的使用公式二(蕴涵式): B1: ?x?yP(x,y ) ? ?y ?xP(x,y ) B8: ?y?xP(x,y) ? ?y?xP(x,y) B2: ?x?yP(x，y ) ? y ?xP(x，y ) B3: ?x?yP(x，y ) ? ? x ?yP(x，y ) ? B4: ?y?xP(x，y) ?x?yP(x，y) B5: ?x?yP(x，y) ??y?xP(x，y) ? B6: ?x?yP（x，y） ??x?yP(x，y) B7: ?y?xP（x，y） ??y?xP(x，y) （2）量词的转换律推广到含有多个量词的谓词公式 ┐?x?y?z P(x,y,z) ? ? x ┐?y?z P(x,y,z) ? ? x ? y ┐? z P(x,y,z) ? ?x?y?z ┐P(x,y,z) 多个量词出现时，不能随意颠倒它们的顺序 Homework P65 (1): b), c) (2) c) P66 (4): b) (5): a) P72 (4),(7) 指导变元： 给定A为一个谓词公式，其中有一部分公式为(? x )P(x)或者是(?x)P(x)，这里的?、 ? 后面所跟的x，称为相应量词的指导变元。 作用域（辖域）：给定谓词公式中，形式为(? x )P(x)或(?x)P(x)中的P(x)称为相应量词的作用域（辖域）。 2.4变元的约束 量词的辖域是邻接量词之后的最小子公式，除非辖域是个原子公式，否则应在该子公式的两端有括号。 2.4变元的约束 例：?xP(x)→Q(x) ?x的辖域是P(x) ?x(P(x,y)→Q(x，y) ) ? P(y,z) ?x的辖域是P(x，y)→Q(x，y) 定义:约束变元 在量词?x，?x辖域内变元x的一切出现叫约束出 现，称这样的x为约束变元。 例如, 在公式 ?x(F(x,y)?G(x,z)) 中, A=(F(x,y)?G(x,z))为?x的辖域， x为指导变元, A中x的两次出现均为约束出现， y与z均为自由出现. 定义:自由变元 变元的非约束出现称为自由出现,称这样的变元为自由变元。 通常，一个量词的辖域是某公式A的一部分，称为A的子公式．因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲： ①若量词后有括号，则括号内的子公式就是该量词的辖域； ②若量词后无括号，则与量词邻接的子公式为该量词的辖域． 判定给定公式A中个体变元是约束变元还是自由变元，关键是要看它在A中是约束出现，还是自由出现． 例. 指出下列各合式公式中的量词辖域、个体变元的约束出现和自由出现． ① (?x)(P(x)?(?y)Q(x,y)) ② (?x)H(x)∧L(x,y) ③ (?x)(?y)(P(x,y)∨Q(y,z))∧(?x)R(x,y) 解 ①(?x)的辖域是(P(x)?(?y)Q(x,y)), (?y)的辖域为Q(x,y); 对于(?y)的辖域而言, y为约束出现，x为自由出现．对于(?x)的辖域来说，x和y均为约束出现，x约束出现2次，y约束出现1次． ②(?x)的辖域是H(x)，x为约束出现, L(x,y)中的x和y都为自由出现．对于整个公式来说，x的约束出现1次, 自由出现1次, y自由出现1次． 在(?x)(?y)(P(x,y)Q(y,z))中, (?x)和(?y)的辖域为P(x,y)Q(y,z), x和 y为约束出现, z为自由出现. (?x)的辖域是R(x,y), x为约束出现，y为自由出现．在整个公式中，x为约束出现, y为约束出现又为自由出现，z为自由出现． ③(?x)(?y)(P(x,y)∨Q(y,z))∧(?x)R(x,y) 练习：