离散数学第二章谓词逻辑-4-6节.ppt

,2-4 变元的约束,一、指导变元、辖域、约束出现、自由出现 辖域：紧接在量词后面的谓词公式，即量词的作用范 围称之为量词的作用域或辖域。,指出下列公式中各量词的辖域 (x)(y)(z)(A(x,y)B(x,y,z)C(t),(x)的辖域,(z)的辖域,(y)的辖域,量词辖域的确定方法： （1）若量词后有括号，则括号内的公式为该量词的辖域； （2）若量词后无括号，则与量词邻接的公式为该量词的辖域。 如：(x) P(x,y)。 （3）若多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。,约束变元/指导变元/作用变元：在量词的辖域内，且在量词后面出现的变元。 约束出现：在(x)和(x)的辖域中，x的所有出现。 自由变元：不受量词约束的变元。 自由出现：A中不是约束出现的其他变元。,量词,约束变元,辖域,约束变元,自由变元,(x)P(x,y),例,确定以下公式各量词的辖域以及各客体变量为自由变元还是约束变元。 （1）(x)(y)(P(x, y)Q(y, z)(x)R(x,y) P(x, y)、Q(y, z)中的x, y为约束变元，z为自由变元，R(x,y)中的x为约束变元，但y为自由变元。,(y)的辖域,(x)的辖域,指导变元,(x)的辖域,约束变元,约束变元,自由变元,约束变元,自由变元,对约束变元和自由变元的说明,(1)对约束变元用什么符号表示无关紧要。 就是说(x)A(x)与yA(y)是一样的。这类似于计算积分与积分变元无关，即积分f(x)dx 与f(y)dy 相同。 (2)一个谓词公式如果无自由变元，它就表示一个命题。 例如：A(x)表示x是个大学生。(x)A(x)或者(y)A(x)就是命题，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。 谓词公式中有自由变元，则为命题函数。,对约束变元和自由变元的说明（续）,3、P(x1,x2,xn)是 n 元谓词,有 n 个独立的自由变元。若对其中 k 个变元进行约束，则成为 n-k 元谓词。 若对n个变元进行约束即没有自由变量出现则成为0元谓词，即成为命题。,例：,(x)P(x,y,z) 是二元谓词,(y) (x)P(x,y,z)是一元谓词,P(x,y,z)是三元谓词,(y) (z) (x)P(x,y,z)是命题,变元混淆,(y)的辖域,(x)的辖域,指导变元,(x)的辖域,约束变元,约束变元,自由变元,约束变元,自由变元,（1）(x)(y)(P(x, y)Q(y, z)(x)R(x,y),在一个公式中，某一个变元的出现即可以是自由的，又可以是约束的。 为了使得我们的研究更方便，而不致引起混淆，同时为了使其式子给大家以一目了然的结果，采用对客体变元更改名称，使得变元只以一种形式出现。,约束变元,自由变元,二、约束变元换名和自由变元代入,1、约束变元的换名规则： 含义：对约束变元更改名称。 改名的范围是：该变元在量词及该量词的辖域中的所有出现必须一起更改。 改名的规则：改名时用的客体变元名称不能与该量词辖域内的其它变元名称相同。 例如 (x)(P(x)Q(x,y)(R(x)A(x) x以两种形式出现。可以对约束变元x改名。 (z)(P(z)Q(z,y)(R(x)A(x),2、对自由变元的代入规则： 含义：对自由变元更换名称。 改名的范围是：对整个公式中出现该自由变元的每一处进行更改。 改名的规则：对该自由变元可用客体常量或用与原公式中所有客体变元不同的客体变元去更改。 上例 (x)(P(x)Q(x,y)(R(x)A(x)对自由变元x作代入，改成 (x)(P(x)Q(x,y)(R(z)A(z),改名规则和代入规则的关系,相同点：不改变约束关系。 不同点： (1)实施对象不同 换名规则是对约束变元实施的， 代入规则是对自由变元实施的。 (2)实施范围不同 换名规则可对公式中一个量词及其作用域内实施，即只对公式的一个子公式实施； 代入规则是整个公式的同一自由变元都实施。 (3)实施后结果不同 换名后，公式含义不变，因为约束变元只改名为另一个客体变元，约束关系不改变，约束变元不能改名为客体常量； 代入后，不仅可用另一个客体变元进行代入，并且也可用客体常量去代入，从而使公式由具有普遍意义变为仅对该客体常量有意义，即公式的含义改变了。,例 对以下公式分别利用换名和代入规则改写,例(x)(A(x)B(x,y)C(x) D(x,w) 换名：,(x)(A(x)B(x，y)C(y) D(y,w),错,(x)(A(x)B(x，y)C(w) D(w,w),错,(x)(A(x)B(x，y)C(u) D(x,w),对,代入：,(y)(A(y)B(y,y)C(x) D(x,w),(z)(A(z)B(z,y)C(x) D(x,w),(w)(A(w)B(w，y)C(x) D(x,w),错,对,对,(x)(A(x)B(x，y)C(u) D(u,w),错,小结,作业 65页 (4) b) (5) a),量词的辖域、约束变元、自由变元。 变元的改名（重点掌握） 约束变元的换名。 自由变元的代入。,2-5 谓词演算的等价式和蕴含式,要求：理解谓词公式赋值、等价、有效（永真）、不可满足、可满足等概念，掌握一些谓词演算的等价式和蕴含式。 重点：谓词公式的等价和永真。 难点：多个量词的使用。,一、对谓词公式赋值,定义：对公式中的变量制定具体的常量去替代。 将命题变元，用确定的命题代替， 对公式中的客体变元用个体域中的客体代替， 这个过程就称之为对谓词公式作指派，或者 称之为对谓词公式赋值或解释。 例如公式 PN(x) N(x)：x是自然数，个体域为实数集合R， 赋值：令P：21， x=4时，公式为PN(4)，真值是“真”。 谓词公式经过赋值以后，成为具有确定真值的命题。,确定的命题,客体变元,个体域中的客体,命题变元,带量词的公式在个体域内的展开式,个体域有限时,去掉量词公式，当个体域有限时，如个体域D=x1,，xn,由量词意义可知，对任意A(x),都有: 1. (x) G(x)G(x1)G(x2)G(xn) 2. (x) G(x)G(x1)G(x2)G(xn),例,对以下公式赋值后求真值。 (x)(P(x)Q(f(x),a) (x)(P(x)Q(x,a) 其中，个体域D=1，2，a=1,(x)(P(x)Q(f(x),a) (P(1)Q(f(1),1)(P(2)Q(f(2),1) (F Q(2,1) (T Q(1,1) T T T,(x)(P(x)Q(x,a) (P(1)Q(1,1)(P(2)Q(2,1) (FT)(TF) F,二、谓词合式公式的分类,定义2-5.1： A在个体域E上是永真的（有效的）: 给定的任何谓词公式A，E是其个体域，如果不论对公式A作任何赋值，都使得A的真值为真，则称公式A在个体域E上是永真的（有效的）。 定义2-5.2： A为不可满足的: 一个谓词公式A，如果在所有赋值下都为假，则称A为不可满足的。 定义2-5.3： A是可满足的: 一个谓词公式A，如果至少在一种赋值下为真，则称A是可满足的。,例,判断下列公式的真假。 （1）P(x, y)Q(x,y)P(x, y)； （2）P(x, y)P(x, y)； （3）P(x, y)P(x, y)。,解 无论在何个体域中，无论对变元作何种赋值，公式(1)，(2)均取真值T，而公式(3)均取真值F。 从而(1)，(2)就是关于一切个体域与一切赋值下恒取“T”值的谓词公式，(3)就是关于一切个体域与一切赋值下恒取“F”值的谓词公式。,三、谓词公式的等价公式定义,定义2-5.4：A与B在个体域E上是等价的。 给定谓词公式A、B，E是它们的共同个体域，如果不论对公式A、B作任何赋值，都使得A与B的真值相同(或者说AB是重言式)，则称公式A与B在个体域E上是等价的。 定义： A与B等价 如果不论对什么个体域E，都使得公式A与B等价，则称A与B等价，记作AB。 例 I(x):表示x是整数,N(x):表示x是自然数， 假设个体域E是自然数集合，公式I(x)与N(x)在E上是等价的。 而公式N(x)I(x) 与N(x)I(x)就是与个体域无关的等价的公式，即 N(x)I(x)N(x)I(x)。,四、谓词公式的蕴含式定义,定义2-5.5：在个体域E上公式A蕴含B。 给定谓词公式A、B，E是它们的个体域，如果不论对公式A、B作任何赋值，都使得AB为重言式，则称在个体域E上公式A蕴含B。 定义：公式A蕴含B。 如果不论对什么个体域E，都使得公式AB为重言式，则称A蕴含B，记作AB。 例如，G(x)：表示x大于5，N(x)：表示x是自然数，个体域E=-1,-2,6,7,8,9,， 在E上公式G(x)N(x)是重言式。 而公式(G(x)N(x)N(x)就是与个体域无关的重言式，所以(G(x)N(x)N(x)。,五、对偶定理,定义： 设在公式A中没有联结词和 ， 与，、，命题常量F和T互换，得到的公式A*称为A的对偶式。 定理2-5.1（对偶定理）设有等价式AB，并在A,B中没有联结词和 ，则必有A* B*,六、重要公式,讨论重要的谓词等价公式和重言蕴含式。 由命题公式推广出的公式 消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式,（一）由命题公式推广出的公式,因一个不含自由变元的谓词公式本身如(x) A(x)、(x)B(x)就是命题。 一个含有n个自由变元的谓词公式，赋予个体域中的n个指定客体后就变成命题(例如S(a)、G(3,1)等)。因此可以把此公式看成一个命题变元。 所以在命题演算的重言式中，将其中的同一个命题变元，用同一个谓词公式代替，所得到的公式也是重言式。这样就可以将命题演算中的等价公式和蕴含式推广到谓词演算中使用。,（一）由命题公式推广出的公式-例,例如 命题逻辑 谓词逻辑 PQPQ (PQ)PQ PPQ,(x)(A(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) A(x)A(x)B(x),（二）量词否定公式,例：(x)表示x是优等生，个体域是某班级的学生集合。 (x)A(x)表示：所有人都是优等生。 (x)A(x)表示：有些人是优等生。 (x)A(x)表示：不是所有人都是优等生。 (x)A(x)表示：有些人不是优等生。 (x)A(x)表示：不存在有人是优等生。 (x)A(x)表示：所有人都不是优等生。 从这个例子可以看出 “不是所有人都是优等生”与“有些人不是优等生”是等价的。 “不存在有人是优等生”与“所有人都不是优等生”是等价的。于是有：,证明,1. (x)A(x)(x)A(x) E26 2. (x)A(x)(x)A(x) E25 对这两个公式可以证明如下： 证明：设个体域为a1,a2,an，则 (x)A(x)(A(a1)A(a2).A(an) A(a1)A(a2).A(an)(x)A(x) 类似可以证明另一个公式。,结论： 对于非量化命题的否定只需将动词否定，而对于量化命题的否定，需要对动词和量词同时否定。 (x)的否定变为(x) (x)的否定变为(x) 所以我们也把这两个公式称为量词转换公式。,（三）量词辖域的扩充与收缩公式,若B是谓词公式， (1)不在(x)和(x)的辖域内，(2)不含客体变元x， 可以将B放入(x)和(x)的辖域内。 1. (x)A(x)B(x)(A(x)B) E27 2. (x)A(x)B(x)(A(x)B) 3. (x)A(x)B(x)(A(x)B) 4. (x)A(x)B(x)(x)B) E28 证：1.(x)A(x)B (x)(x) 证明：假设个体域为a1,a2,an， (x)A(x)B(A(a1)A(a2).A(an)B (A(a1)B)(A(a2)B).(A(an)B) (x)(x),（三）量词辖域的扩充与收缩公式（续）,5. B(x)A(x)(x)(BA(x) E32 6. B(x)A(x)(x)(BA(x) E33 7. (x)A(x)B(x)(A(x)B) E30 8. (x)A(x)B(x)(A(x)B) E31 证：6. B(x)A(x)(x)(BA(x) 证明：B(x)A(x)B(x)A(x)(x)(BA(x) (x)(BA(x) 证：7. (x)A(x)B(x)(A(x)B) (x)A(x)B(x)A(x)B(x)A(x)B (x)(A(x)B)(x)(A(x)B),在使用公式7.、8.时，要特别注意，量词的辖域扩充后，量词发生了变化。,例,(x)F(x)(y)G(y,x) (x)F(x)(y)G(y,z) (x)(F(x)(y)G(y,z) (x)(y)(F(x)G(y,z) (x)(y)(F(x)G(y,z) (x)(y)(F(x)G(y) (x)(y)(F(x)G(y) (x)(F(x)(y)G(y) (x)F(x)(y)G(y),（四）量词分配公式(等价式和蕴含式),1. (x)(A(x)B(x)(x)A(x)(x)B(x) E23 2. (x)(A(x)B(x)(x)A(x)(x)B(x) E24 我们称(1)为“对满足分配律” ， (2)为“对满足分配律” 。 但是要注意：“对”以及“对”不存在分配等价式。 即, (x)(A(x)B(x)(x)A(x)(x)B(x) (x)(A(x)B(x)(x)A(x)(x)B(x) 3. (x)(A(x)B(x)(x)A(x)(x)B(x) I18 4. (x)A(x)(x)B(x)(x)(A(x)B(x) I17,例,1、(x)(A(x)B(x) (x)A(x)(x)B(x) 解释：个体域是party中的人。 A(x)：x唱歌， B(x) ：x跳舞 则(x)(A(x)B(x)表示： party里的所有人既唱歌又跳舞； (x)A(x)(x)B(x)表示： party里的所有人唱歌且party里的所有人都跳舞。 两者意义是相同的。 即有： (x)(A(x)B(x) (x)A(x)(x)B(x),例,2.(x)(A(x)B(x) (x)A(x)(x)B(x) 解释：个体域是party中的人。 A(x)：x唱歌， B(x) ：x跳舞 则(x)(A(x)B(x)表示： Party中有些人唱歌或跳舞； (x)A(x)(x)B(x)表示： Party中有些人唱歌或Party中有些人跳舞。 两者意义是相同的。 所以,(x)(A(x)B(x) (x)A(x)(x)B(x),注意公式3.和4.不是等价公式，是重言蕴含式。,3. (x)(A(x)B(x)(x)A(x)(x)B(x) 解释：个体域是party中的人。 A(x)：x唱歌， B(x) ：x跳舞 (x)A(x)(x)B(x)： Party中有人唱歌，且有人跳舞。 (x)(A(x)B(x)： Party中有人既唱歌又跳舞。,(x)(A(x)B(x)(x)A(x)(x)B(x),所以说 (x)(A(x)B(x)与(x)A(x)(x)B(x) 不等价。,公式4,4. (x)A(x)(x)B(x)(x)(A(x)B(x) 解释：个体域是party中的人。 A(x)：x唱歌， B(x) ：x跳舞 (x)A(x)(x)B(x)： 所有人都唱歌或者所有人都跳舞。 (x)(A(x)B(x)： 所有人都唱歌或跳舞。,(x)A(x)(x)B(x)(x)(A(x)B(x),(x)(A(x)B(x) (x)A(x)(x)B(x),所以， x)A(x)(x)B(x) 与 (x)(A(x)B(x)不等价。,公式1的证明(自学),求证 1. (x)(A(x)B(x)(x)A(x)(x)B(x) 证明：设个体域为a1,a2,an， (x)(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2)(A(an)B(an) (A(a1)A(a2).A(an)(B(a1)B(a2).B(an) (x)A(x)(x)B(x),公式3的证明（自学）,证明3.(x)(A(x)B(x)(x)A(x)(x)B(x),如果(x)(A(x) B(x)为真,故该a使A(a)为真，,该a使B(a)为真,所以(x)A(x)为真，,所以(x)B(x)为真，,故(x)A(x) (x)B(x)为真,证明： 假设前件(x)(A(x)B(x)为真， 则个体域中至少有一个客体a，使得A(a)B(a)为真， 于是A(a)和B(a)都为真， 所以有(x)A(x)以及(x)B(x)为真 进而得(x)A(x)(x)B(x)为真。 于是有 (x)(A(x)B(x)(x)A(x)(x)B(x),且,公式4的证明（自学）,4. (x)A(x)(x)B(x)(x)(A(x)B(x),如果(x)(A(x)B(x)为假,(x)A(x)为假,(x) B(x) 为假,则必有客体a,使A(a)B(a)为假,A(a)为假,B(a)为假,则 (x) A(x)(x)B(x)为假,证明： 如果(x)(A(x)B(x)为假，则必有客体a,使A(a)B(a)为假; 若(x)(A(x)B(x)为假, 则必有客体a, 使A(a)B(a)为假; 因此A(a), B(a)皆为假, 所以(x)A(x)和(x)B(x)为假， 即 (x)A(x)(x)B(x)为假。 故(x)A(x)(x)B(x)(x)(A(x)B(x),且,（四）量词分配公式(等价式和蕴含式),利用公式3证明公式4。 4. (x)A(x)(x)B(x)(x)(A(x)B(x) 证明：因为公式3 (x)(A(x)B(x)(x)A(x)(x)B(x) 应用公式 PQQP 得 (x)(A(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) 所以:(x)(A(x)B(x)(x)A(x)(x)B(x) 应用公式 PQQP 得 (x)A(x)(x)B(x)(x)(A(x)B(x),量词分配公式总结,全称量词“”对“”无分配律。 存在量词“”对“”无分配律。 当B(x)换成没有x出现的B时，则有 (x)(A(x)B) (x)A(x)B (x)(A(x)B) (x)A(x)B,说明,1. (x)(A(x)B(x)(x)A(x)(x)B(x) 2. (x)(A(x)B(x)(x)A(x)(x)B(x) 3. (x)(A(x)B(x)(x)A(x)(x)B(x) 4. (x)A(x)(x)B(x)(x)(A(x)B(x),（五）其它公式,1. (x)A(x)(x)B(x)(x)(A(x)B(x) I29 2. (x)A(x)(x)B(x)(x)(A(x)B(x) I19 证明1. (x)A(x)(x)B(x)(x)(A(x)B(x) I29 (x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x),（五）其它公式,证明2. (x)A(x)(x)B(x)(x)(A(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)(A(x)B(x) 故(x)(A(x)B(x)(x)A(x)(x)B(x),（五）其它公式,3.(x)(A(x) B(x)(x)A(x)(x)B(x) 4.(x)A(x) (x)A(x) 量词的添加与删除 5. (x)A(x) A(x) 6. A(x) (x)A(x),(x)(y)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(x)(y)A(x,y),例：A(x,y)表示x和y同姓，个体域：x是甲村人，y是乙村人 甲村所有人与乙村所有人同姓。 乙村所有人与甲村所有人同姓。 甲村和乙村有人同姓。 乙村和甲村有人同姓。 存在一个(些)甲村的人，乙村所有人与之同姓。 乙村所有人，甲村都有人与之同姓 存在一个(些)乙村的人，甲村所有人与之同姓。 甲村所有人，乙村都有人与之同姓,(x)(y)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),（六）多个量词的公式(主要讨论两个量词),(x)(y)A(x,y),(y)(x)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),(y)(x)A(x,y),(x)(y)A(x,y),总结： 1、全称量词可以移到存在量词前面，反之不行。 2、全称量词可推出存在量词，反之不行。,(x)(y)A(x,y)(y)(x)A(x,y)证明,用谓词逻辑推理方法很容易证明上面的重言蕴含式。下面证明公式1：(x)(y)A(x,y)(y)(x)A(x,y) 。,证明：设个体域为a1,a2,an，则 (x)(y)A(x,y) (y)A(a1,y)(y)A(a2,y)(y)A(an,y) (A(a1,a1)A(a1,a2)A(a1,an) (A(a2,a1)A(a2,a2)A(a2,an) (A(an,a1)A(an,a2)A(an,an) (A(a1,a1)A(a2,a1)A(an,a1) (A(a1,a2)A(a2,a2)A(an,a2) (A(a1,an)(A(a2,an)A(an,an) (x)A(x,a1)(x)A(x,a2)(x)A(x,an) (y)(x)A(x,y),演算,(P(a1，a1) P(a2，a1)(P(a1，a2) P(a2，a2) (P(a1，a1) (P(a1，a2) (P(a1，a1) P(a2，a2) (P(a2，a1) P(a1，a2) (P(a2，a1) P(a2，a2) (P(a1，a1) P(a1，a2) (P(a2，a1) P(a2，a2),(y)(x)P(x，y) (x)(y)P(x，y)证明,(y)(x)P(x，y) (y)(P(a1，y) P(a2，y) P(an，y) (P(a1，a1) P(a2，a1) P(an，a1) (P(a1，a2) P(a2，a2) P(an，a2) ) (P(a1，an) P(a2，an) P(an，an) (P(a1，a1) P(a1，a2) P(a1，an) (P(a2，a1) P(a2，a2) P(a2，an) (P(an，a1) P(an，a2) P(an，an) (y)P(a1，y) (y)P(a2，y) (y)P(an，y) (x)(y)P(x，y),例,(x)(y)(z)(x+z=y) (x)(yz(x+z=y) (x)(y)(z(x+z=y) (x)(y)(z)(x+z=y) (x)(y)(z)(x+zy),本节小结,熟练掌握谓词等价公式和重言蕴含式的证明方法及应用。 作业题： P66 (3) b) P71 (2) d), (6),2-6 前束范式,与命题公式一样，我们对谓词公式也要讨论范式，但在谓词逻辑中我们讨论的是前束范式。因为在定理的机器证明中，需要消除谓词公式中的量词，因而需要将谓词公式中的量词前束化，即把公式中的量词均提取到公式的前部。 即前束范式主要是对量词的位置有要求，而对联结词无要求，这一点与命题逻辑不同。 本节掌握：前束范式的求法,一、前束范式定义,定义2-6.1：前束范式： 一个公式，若量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。 前束范式的形式： (v1)(v2).(vn)A 其中可能是量词或量词，vi(i=1,2,n)是客体变元，A是没有量词的谓词公式。 一个谓词公式的前束范式符合下面条件： (1)所有量词前面都没有联结词； (2)所有量词都在公式的左面； (3)所有量词的辖域都延伸到公式的末尾。 例如:,(y)(x)(z)(A(x)(B(x,y)C(x,y,z) (x)(x)B(x) 、 (x)A(x)B、 (x)(y)(A(x)(B(x,y)(z)C(z),前束范式,不是前束范式,前束范式,不是前束范式,前束范式存在定理,定理2-6.1(前束范式存在定理) 任意公式A都有与之等价的前束范式。,二、前束范式的写法,定理2-6.1的证明给出了将任意一个谓词公式化为与之等价的前束范式的方法。步骤如下： 1)消除多余量词； 2)消去公式中的联结词和(为了便于量词辖域的扩充)； 3) 后移 如果量词前有“”，则用量词否定公式将“”后移。再用摩根定律或求公式的否定公式，将“”后移到原子