《离散数学第二章谓词逻辑--节精.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑--节精.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学第二章谓词逻离散数学第二章谓词逻辑辑-节节第1页，本讲稿共57页 n约约束束变变元元/指指导导变变元元/作作用用变变元元：在在量量词词的的辖辖域域内内，且且在在量词后面出现的变元。量词后面出现的变元。p约束出现约束出现：在在(x)和和(x)的辖域中，的辖域中，x的所有出现。的所有出现。n自由变元：自由变元：不受量词约束的变元。不受量词约束的变元。p自由出现：自由出现：A中不是约束出现的其他变元。中不是约束出现的其他变元。量词量词约束变元约束变元辖域辖域约束变元约束变元自由变元自由变元(x)P(x,y)第2页，本讲稿共57页例例确确定定以以下下公公式式各各量量词词的的辖辖域域以以及及各各
2、客客体体变变量量为为自自由由变变元元还是约束变元。还是约束变元。（1）(x)(y)(P(x,y)Q(y,z)(x)R(x,y)pP(x,y)、Q(y,z)中的中的x,y为约束变元，为约束变元，z为自由变元，为自由变元，R(x,y)中的中的x为约束变元，但为约束变元，但y为自由变元。为自由变元。指导指导变元变元(y)的辖域的辖域(x)的辖域的辖域指导指导变元变元(x)的辖域的辖域约束约束变元变元约束约束变元变元自由自由变元变元约束约束变元变元自由自由变元变元第3页，本讲稿共57页对约束变元和自由变元的对约束变元和自由变元的说明说明(1)对约束变元用什么符号表示无关紧要。对约束变元用什么符号表示无
3、关紧要。p就是说就是说(x)A(x)与与 yA(y)是一样的。这类似于计是一样的。这类似于计算积分与积分变元无关，即积分算积分与积分变元无关，即积分f(x)dx 与与f(y)dy 相相同。同。(2)一个谓词公式如果无自由变元，它就表示一个命题。一个谓词公式如果无自由变元，它就表示一个命题。p例如：例如：A(x)表示表示x是个大学生。是个大学生。(x)A(x)或者或者(y)A(x)就是就是命题命题，因为它们分别表示命题，因为它们分别表示命题“有有些人是大学生些人是大学生”和和“所有人都是大学生所有人都是大学生”。p谓词公式中有自由变元，则为命题函数。谓词公式中有自由变元，则为命题函数。第4页，本
4、讲稿共57页对约束变元和自由变元的对约束变元和自由变元的说明（续）说明（续）n3、P(x1,x2,xn)是是 n 元元谓谓词词,有有 n 个个独独立立的的自自由由变变元元。若对其中若对其中 k 个变元进行约束，则成为个变元进行约束，则成为 n-k 元谓词。元谓词。n若若对对n个个变变元元进进行行约约束束即即没没有有自自由由变变量量出出现现则则成成为为0元元谓词谓词，即成为，即成为命题命题。例：例：(x)P(x,y,z)是二元谓词是二元谓词(y)(x)P(x,y,z)是一元谓词是一元谓词P(x,y,z)是三元谓词是三元谓词(y)(z)(x)P(x,y,z)是命题是命题第5页，本讲稿共57页变元混
5、淆变元混淆 指导指导变元变元(y)的辖域的辖域(x)的辖域的辖域指导指导变元变元(x)的辖域的辖域约束约束变元变元约束约束变元变元自由自由变元变元约束约束变元变元自由自由变元变元（1）(x)(y)(P(x,y)Q(y,z)(x)R(x,y)在一个公式中，某一个变元的出现在一个公式中，某一个变元的出现即可以是自由的，即可以是自由的，又可以是约束的又可以是约束的。为了使得我们的研究更方便，而不致引起混淆为了使得我们的研究更方便，而不致引起混淆，同时，同时为了使其式子给大家以一目了然的结果为了使其式子给大家以一目了然的结果，采用对客体，采用对客体变元更改名称，使得变元只以一种形式出现。变元更改名称，
6、使得变元只以一种形式出现。约束约束变元变元自由自由变元变元第6页，本讲稿共57页二、二、约束变元约束变元换名换名和和自由变元自由变元代入代入1、约束变元的换名规则：、约束变元的换名规则：p含义：含义：对约束变元更改名称。对约束变元更改名称。p改名的范围是：改名的范围是：该该变元变元在在量词量词及该及该量词的辖域量词的辖域中的中的所有出现必须一起更改。所有出现必须一起更改。p改名的规则：改名的规则：改名时用的客体变元名称不能与该量改名时用的客体变元名称不能与该量词辖域内的其它变元名称相同。词辖域内的其它变元名称相同。n 例如例如 (x)(P(x)Q(x,y)(R(x)A(x)nx以两种形式出现。
7、可以对约束变元以两种形式出现。可以对约束变元x改名。改名。n(z)(P(z)Q(z,y)(R(x)A(x)第7页，本讲稿共57页 2、对自由变元的代入规则、对自由变元的代入规则：p含义：含义：对自由变元更换名称。对自由变元更换名称。p改名的范围是：改名的范围是：对整个公式中出现该自由变元的对整个公式中出现该自由变元的每一处进行更改。每一处进行更改。p改名的规则：改名的规则：对该自由变元可用对该自由变元可用客体常量客体常量或用或用与与原公式中原公式中所有客体变元不同所有客体变元不同的客体变元的客体变元去更改。去更改。p上例上例 (x)(P(x)Q(x,y)(R(x)A(x)对自由变对自由变元元x
8、作代入，改成作代入，改成 (x)(P(x)Q(x,y)(R(z)A(z)第8页，本讲稿共57页改名规则和代入规则的关系改名规则和代入规则的关系相同点：相同点：不改变约束关系。不改变约束关系。不同点：不同点：n(1)实施对象不同实施对象不同p换名换名规则规则是对是对约束变元约束变元实施的，实施的，p代入代入规则规则是对是对自由变元自由变元实施的。实施的。n(2)实施范围不同实施范围不同p换名规则可对公式中一个量词及其作用域内实施，即只对公式的一换名规则可对公式中一个量词及其作用域内实施，即只对公式的一个子公式实施；个子公式实施；p代入规则是整个公式的同一自由变元都实施。代入规则是整个公式的同一自
9、由变元都实施。n(3)实施后结果不同实施后结果不同p换名后，换名后，公式含义不变公式含义不变，因为，因为约束变元只改名为另一个客体变元约束变元只改名为另一个客体变元，约束关系不改变，约束关系不改变，约束变元不能改名为客体常量约束变元不能改名为客体常量；p代入后，不仅可用另一个客体变元进行代入，并且也可用代入后，不仅可用另一个客体变元进行代入，并且也可用客体客体常量常量去代入，从而使公式由具有普遍意义变为仅对该客体常量有意义，去代入，从而使公式由具有普遍意义变为仅对该客体常量有意义，即即公式的含义改变公式的含义改变了。了。第9页，本讲稿共57页例例 对以下公式分别利用换名和代入规则改写对以下公式
10、分别利用换名和代入规则改写例例(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)错错第10页，本讲稿共57页小结小结作业作业6565页页 (4)b)(5)a)(4)b)(5)a)n量词的辖域、约束变元、自由变元。n变
11、元的改名（重点掌握）p约束变元的换名。p自由变元的代入。第11页，本讲稿共57页2-5 2-5 谓词演算的等价式和蕴含式谓词演算的等价式和蕴含式要要求求：理理解解谓谓词词公公式式赋赋值值、等等价价、有有效效（永永真真）、不不可可满满足足、可可满满足足等等概概念念，掌掌握握一一些些谓谓词词演演算算的的等价式和蕴含式。等价式和蕴含式。重点：重点：谓词公式的等价和永真谓词公式的等价和永真。难点：难点：多个量词的使用。多个量词的使用。第12页，本讲稿共57页一、对谓词公式赋值一、对谓词公式赋值定义定义：对公式中的变量制定具体的常量去替代。：对公式中的变量制定具体的常量去替代。n将将命题变元命题变元，用
12、确定的命题代替，用确定的命题代替，n对公式中的对公式中的客体变元客体变元用个体域中的客体代替，用个体域中的客体代替，这个过程就称之为这个过程就称之为对谓词公式作指派对谓词公式作指派，或者，或者 称之为称之为对谓词公式赋值或解释对谓词公式赋值或解释。p例如公式例如公式 PN(x)N(x)：x是自然数，个体域为实数集合是自然数，个体域为实数集合R，p赋值：令赋值：令P：21，x=4时时，公式为，公式为PN(4)，真值是，真值是“真真”。n谓词公式经过赋值以后，成为具有确定真值的命题。谓词公式经过赋值以后，成为具有确定真值的命题。确定的命题确定的命题客体变元客体变元个体域中的客体个体域中的客体命题变
13、元命题变元第13页，本讲稿共57页带量词的公式在个体域内的展开式带量词的公式在个体域内的展开式个个体体域域有有限限时时,去去掉掉量量词词公公式式，当当个个体体域域有有限限时时，如如个个体域体域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)第14页，本讲稿共57页例例f(1)f(2)21P(1)P(2)FTQ(1,1)Q(1,2)Q(2,1)Q(2,2)TTFFn (x)(P(x)Q(f(x),a)(P(1)Q(f(1),1)(P(2)Q(f(2),1)(F Q
14、(2,1)(T Q(1,1)T TTn (x)(P(x)Q(x,a)(P(1)Q(1,1)(P(2)Q(2,1)(FT)(TF)F第15页，本讲稿共57页二、谓词合式公式的分类二、谓词合式公式的分类定义定义2-5.1：A在个体域在个体域E上是永真的（有效的）上是永真的（有效的）:p给定的任何谓词公式给定的任何谓词公式A，E是其个体域，如果不是其个体域，如果不论对公式论对公式A作任何赋值，都使得作任何赋值，都使得A的真值为真，的真值为真，则称公式则称公式A在个体域在个体域E上是永真的（有效的）上是永真的（有效的）。定义定义2-5.2：A为不可满足的为不可满足的:p一个谓词公式一个谓词公式A，如果
15、在所有赋值下都为假，如果在所有赋值下都为假，则称则称A为不可满足的为不可满足的。定义定义2-5.3：A是可满足的是可满足的:p一个谓词公式一个谓词公式A，如果至少在一种赋值下为真，如果至少在一种赋值下为真，则称则称A是可满足的是可满足的。第16页，本讲稿共57页例例判断下列公式的真假。判断下列公式的真假。（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)(1)，(2)(2)均取真值均取真值T T，而公式，而公式(3)(3)均取真值均取真值F
16、F。从从而而(1)(1)，(2)(2)就就是是关关于于一一切切个个体体域域与与一一切切赋赋值值下下恒恒取取“T T”值值的的谓谓词词公公式式，(3)(3)就就是是关关于于一一切切个个体体域与一切赋值下恒取域与一切赋值下恒取“F F”值的谓词公式。值的谓词公式。第17页，本讲稿共57页三、谓词公式的等价公式定义三、谓词公式的等价公式定义定义定义2-5.42-5.4：A A与与B B在个体域在个体域E E上是等价的。上是等价的。p给定谓词公式给定谓词公式A A、B B，E E是它们的共同个体域是它们的共同个体域，如果不论对，如果不论对公式公式A A、B B作任何赋值，作任何赋值，都使得都使得A A
17、与与B B的真值相同的真值相同(或者说或者说A AB B是重言式是重言式)，则称公式，则称公式A A与与B B在个体域在个体域E E上是等价的。上是等价的。n定义：定义：A A与与B B等价等价p如果不论对什么个体域如果不论对什么个体域E E，都使得公式，都使得公式A A与与B B等价，则称等价，则称A A与与B B等价等价，记作，记作A AB B。n例例 I(x):I(x):表示表示x x是整数是整数,N(x):,N(x):表示表示x x是自然数，是自然数，p假设个体域假设个体域E E是自然数集合，公式是自然数集合，公式I(x)I(x)与与N(x)N(x)在在E E上是等价上是等价的。的。p
18、 而公式而公式N(x)I(x)N(x)I(x)与与 N(x)I(x)N(x)I(x)就是与个体域无关的就是与个体域无关的等价的公式，即等价的公式，即n N(x)I(x)N(x)I(x)N(x)I(x)N(x)I(x)。第18页，本讲稿共57页四、谓词公式的蕴含式定义四、谓词公式的蕴含式定义定义定义2-5.5：在个体域在个体域E上上公式公式A蕴含蕴含B。p给定谓词公式给定谓词公式A、B，E是它们的个体域，如果不论对公是它们的个体域，如果不论对公式式A、B作任何赋值，都使得作任何赋值，都使得AB为重言式，则称为重言式，则称在个在个体域体域E上上公式公式A蕴含蕴含B。定义定义：公式公式A蕴含蕴含B。
19、p如果不论对什么个体域如果不论对什么个体域E，都使得公式，都使得公式AB为重言式，为重言式，则称则称A蕴含蕴含B，记作，记作AB。n例例如如，G(x)：表表示示x大大于于5，N(x)：表表示示x是是自自然然数数，个个体体域域E=-1,-2,6,7,8,9,.，n在在E上公式上公式G(x)N(x)是重言式。是重言式。而公式而公式(G(x)N(x)N(x)就是与个体域无关的重言式，就是与个体域无关的重言式，所以所以(G(x)N(x)N(x)。第19页，本讲稿共57页五、对偶定理五、对偶定理定义：定义：设在公式设在公式A中没有联结词中没有联结词和和，与与，、，命命题题常常量量F和和T互互换换，得得到
20、到的的公公式式A*称为称为A的对偶式。的对偶式。定定理理2-5.1（对对偶偶定定理理）设设有有等等价价式式AB，并并在在A,B中没有联结词中没有联结词和和，则必有，则必有A*B*第20页，本讲稿共57页六、重要公式六、重要公式讨论重要的谓词等价公式和重言蕴含式。讨论重要的谓词等价公式和重言蕴含式。由命题公式推广出的公式由命题公式推广出的公式消去量词等值式消去量词等值式 量词否定等值式量词否定等值式 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 量词分配等值式量词分配等值式 第21页，本讲稿共57页（一）（一）由命题公式推广出的公式由命题公式推广出的公式n因因一一个个不不含含自自由由变变元元
21、的的谓谓词词公公式式本本身身如如(x)A(x)、(x)B(x)就是命题就是命题。n一一个个含含有有n个个自自由由变变元元的的谓谓词词公公式式，赋赋予予个个体体域域中中的的n个个指指定定客客体体后后就就变变成成命命题题(例例如如S(a)、G(3,1)等等)。因此可以把此公式因此可以把此公式看成一个命题变元看成一个命题变元。n所所以以在在命命题题演演算算的的重重言言式式中中，将将其其中中的的同同一一个个命命题题变变元元，用用同同一一个个谓谓词词公公式式代代替替，所所得得到到的的公公式式也也是是重重言言式式。这这样样就就可可以以将将命命题题演演算算中中的的等等价价公公式式和和蕴蕴含式推广到谓词演算中
22、使用。含式推广到谓词演算中使用。第22页，本讲稿共57页（一）（一）由命题公式推广出的公式由命题公式推广出的公式-例例例如例如命题逻辑命题逻辑 谓词逻辑谓词逻辑PQPQ (PQ)P QPPQ (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)第23页，本讲稿共57页（二）量词否定公式（二）量词否定公式例：例：(x)表示表示x是优等生，个体域是某班级的学生集合。是优等生，个体域是某班级的学生集合。p(x)A(x)表示：所有人都是优等生。表示：所有人都是优等生。p(x)A(x)表示：有些人是优等生。表示：有些人是优等生。
23、p(x)A(x)表示：表示：不是所有人都是优等生。不是所有人都是优等生。p(x)A(x)表示：表示：有些人不是优等生。有些人不是优等生。p (x)A(x)表示：表示：不存在有人是优等生。不存在有人是优等生。p(x)A(x)表示：表示：所有人都不是优等生。所有人都不是优等生。从这个例子可以看出从这个例子可以看出p“不是所有人都是优等生不是所有人都是优等生”与与“有些人不是优等生有些人不是优等生”是等价的。是等价的。p“不存在有人是优等生不存在有人是优等生”与与“所有人都不是优等生所有人都不是优等生”是等价的。于是有：是等价的。于是有：第24页，本讲稿共57页证明证明1.(x)A(x)(x)A(x
24、)E262.(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)类似可以证明另一个公式。类似可以证明另一个公式。n结论：结论：n对于非量化命题的否定只需将动词否定，而对于量化命对于非量化命题的否定只需将动词否定，而对于量化命题的否定，需要对动词和量词同时否定。题的否定，需要对动词和量词同时否定。(x)的否定变为的否定变为(x)(x)的否定变为的否定变为(x)n所以我们也把这两个公式称为所以我们也把这两个公式
25、称为量词转换公式量词转换公式。第25页，本讲稿共57页（三）量词辖域的扩充与收缩公式（三）量词辖域的扩充与收缩公式若若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
26、)B(A(a1)B)(A(a2)B).(A(an)B)(x)(x)第26页，本讲稿共57页（三）量词辖域的扩充与收缩公式（三）量词辖域的扩充与收缩公式（续）（续）5.B(x)A(x)(x)(BA(x)E326.B(x)A(x)(x)(BA(x)E337.(x)A(x)B(x)(A(x)B)E308.(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
27、)在使用公式在使用公式7.、8.时，要特别注意，时，要特别注意，量词的辖域扩充后，量词的辖域扩充后，量词发生了变化。量词发生了变化。第27页，本讲稿共57页例例 (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)第28页，本讲稿共57页（四）量词分配公式（四）量词分配公式(等价式和蕴含式等价式和蕴含式)1.(x)(A(x)B(x)(x)A(x)(x)B(x)E23
28、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)I184.(x)A(x)(x)B(x)(x)(A(x)B(x)I17第29页，本讲稿共57页例例1、(x)(A(x)B(x)(x)A(x)(x)B(x)解释：个体域是解释：个体域是party中的人。
29、中的人。A(x)：x唱歌，唱歌，B(x)：x跳舞跳舞 则则(x)(A(x)B(x)表示：表示：p party里的所有人既唱歌又跳舞；里的所有人既唱歌又跳舞；(x)A(x)(x)B(x)表示：表示：pparty里的所有人唱歌且里的所有人唱歌且party里的所有人都跳舞。里的所有人都跳舞。两者意义是相同的两者意义是相同的。即有：即有：(x)(A(x)B(x)(x)A(x)(x)B(x)第30页，本讲稿共57页例例2.(x)(A(x)B(x)(x)A(x)(x)B(x)解释：个体域是解释：个体域是party中的人。中的人。A(x)：x唱歌，唱歌，B(x)：x跳舞跳舞则则(x)(A(x)B(x)表示：
30、表示：pParty中有些人唱歌或跳舞；中有些人唱歌或跳舞；(x)A(x)(x)B(x)表示：表示：pParty中有些人唱歌或中有些人唱歌或Party中有些人跳舞。中有些人跳舞。两者意义是相同的。两者意义是相同的。所以所以,(x)(A(x)B(x)(x)A(x)(x)B(x)第31页，本讲稿共57页注意注意公式公式3.和和4.不是等价公式，不是等价公式，是重言蕴含式。是重言蕴含式。3.(x)(A(x)B(x)(x)A(x)(x)B(x)解释：个体域是解释：个体域是party中的人。中的人。A(x)：x唱歌，唱歌，B(x)：x跳舞跳舞p(x)A(x)(x)B(x)：nParty中有人唱歌，且有人跳
31、舞。中有人唱歌，且有人跳舞。p(x)(A(x)B(x)：n Party中有人既唱歌又跳舞。中有人既唱歌又跳舞。(x)(A(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)(x)B(x)不等价。不等价。第32页，本讲稿共57页公式公式4 44.(x)A(x)(x)B(x)(x)(A(x)B(x)解释：个体域是解释：个体域是party中的人。中的人。A(x)：x唱歌，唱歌，B(x)：x跳舞跳舞(x)A(x)(x)B(x)：p所有人都唱歌或者所有人都跳舞。所有人都唱歌或者所有人都跳舞。(x)(A(x)B
32、(x)：p所有人都唱歌或跳舞。所有人都唱歌或跳舞。(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)不不等价。等价。第33页，本讲稿共57页公式公式1 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
33、(x)第34页，本讲稿共57页公式公式3 3的证明的证明（自学）（自学）证明证明3.(x)(A(x)B(x)(x)A(x)(x)B(x)如果如果(x)(A(x)B(x)为真为真则存在则存在a使使A(a)B(a)为真，为真，故该故该a使使A(a)为真，为真，该该a使使B(a)为真为真所以所以(x)A(x)为真，为真，所以所以(x)B(x)为真，为真，故故(x)A(x)(x)B(x)为真为真证明证明：n假设前件假设前件(x)(A(x)B(x)为为真，真，n则个体域中至少有一个客体则个体域中至少有一个客体a，使得，使得A(a)B(a)为真，为真，n于是于是A(a)和和B(a)都为真，都为真，n所以有
34、所以有(x)A(x)以及以及(x)B(x)为真为真n进而得进而得(x)A(x)(x)B(x)为真。为真。n于是有于是有 (x)(A(x)B(x)(x)A(x)(x)B(x)且且第35页，本讲稿共57页公式公式4 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)x)B(x)B(x)为假为假证明：证明：v如果如果(x)x)(A(x)(A(x)B(x)B(x)为为假，则必有
35、客体假，则必有客体a a,使使A A(a a)B B(a a)为假为假;v若若(x)(Ax)(A(x)(x)B B(x)(x)为假为假,则必有客体则必有客体a a,使使A A(a a)B B(a a)为假为假;因此因此A A(a a),),B B(a a)皆为假皆为假,v所以所以(x)Ax)A(x)(x)和和(x)x)B(x)B(x)为假，为假，即即 (x)Ax)A(x)(x)(x)x)B(x)B(x)为为假。假。故故(x)Ax)A(x)(x)(x)x)B(x)B(x)(x)(Ax)(A(x)(x)B B(x)(x)且且第36页，本讲稿共57页（四）量词分配公式（四）量词分配公式(等价式和蕴含
36、式等价式和蕴含式)利用公式利用公式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)应用公式应用公式 PQQ P 得得 (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)应用公式应用公式 PQQ P 得得(x)A(x)(x)B(x)(x)(A(x)B(x)第37页，本讲稿共57页量词分配公式总结量词分配公式总结全称量词
37、全称量词“”对对“”无分配律。无分配律。存在量词存在量词“”对对“”无分配律。无分配律。当当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)第38页，本讲稿共57页（五）其它公式（五）其它公式1.(x)A(x)(x)B(x)(x)(A(x)B(x)I292.(x)A(x)(x)B(x)(
38、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)第39页，本讲稿共57页（五）其它公式（五）其它公式证明证明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)第40页，本讲稿共57页（五）其它公式（五）其它公式3.(x
39、)(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)第41页，本讲稿共57页(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是甲村人，是甲村
40、人，y是乙村人是乙村人n 甲村所有甲村所有人与乙村所有人同姓。人与乙村所有人同姓。n 乙村所有人与甲乙村所有人与甲村所有人同姓。村所有人同姓。n 甲村和甲村和乙村有乙村有人同姓。人同姓。n 乙村和甲乙村和甲村有人同姓。村有人同姓。n 存在一个存在一个(些些)甲村的人，乙村所有人与之同姓。甲村的人，乙村所有人与之同姓。n 乙村所有人，甲乙村所有人，甲村都有人与之同姓村都有人与之同姓n 存在一个存在一个(些些)乙村的人，甲村所有人与之同姓。乙村的人，甲村所有人与之同姓。n 甲村所有人，甲村所有人，乙村都有人与之同姓乙村都有人与之同姓(x)(y)A(x,y)(x)(y)A(x,y)(y)(x)A(x
41、,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、全称量词可推出存在量词，反之不、全称量词可推出存在量词，
42、反之不行。行。若两个量若两个量词是相同词是相同的，它们的，它们的次序是的次序是无关紧要，无关紧要，但若不同，但若不同，它们的次它们的次序就不可序就不可以随便交以随便交换。换。第42页，本讲稿共57页(x)(y)A(x,y)(y)(x)A(x,y)证明证明用用谓谓词词逻逻辑辑推推理理方方法法很很容容易易证证明明上上面面的的重重言言蕴蕴含含式式。下下面面证证明明公公式式1：(x)(y)A(x,y)(y)(x)A(x,y)。n证明：证明：设个体域为设个体域为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,a
43、2)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)第43页，本讲稿共57页演算演算(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(
44、a1，a1)P(a1，a2)(P(a2，a1)P(a2，a2)第44页，本讲稿共57页(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
45、)第45页，本讲稿共57页例例 (x)(y)(z)(x+z=y)(x)(y z(x+z=y)(x)(y)(z(x+z=y)(x)(y)(z)(x+z=y)(x)(y)(z)(x+zy)第46页，本讲稿共57页本节小结本节小结熟熟练练掌掌握握谓谓词词等等价价公公式式和和重重言言蕴蕴含含式式的的证证明明方方法法及应用。及应用。作业题：作业题：P66(3)b)P71(2)d),(6)第47页，本讲稿共57页2-62-6 前束范式前束范式与与命命题题公公式式一一样样，我我们们对对谓谓词词公公式式也也要要讨讨论论范范式式，但但在在谓谓词词逻逻辑辑中中我我们们讨讨论论的的是是前前束束范范式式。因因为为在在
46、定定理理的的机机器器证证明明中中，需需要要消消除除谓谓词词公公式式中中的的量量词词，因因而而需需要要将将谓谓词词公公式式中中的的量量词词前前束束化化，即即把把公公式式中中的的量词均提取到公式的前部。量词均提取到公式的前部。即即前前束束范范式式主主要要是是对对量量词词的的位位置置有有要要求求，而而对对联联结结词无要求词无要求，这一点与命题逻辑不同。，这一点与命题逻辑不同。本节掌握本节掌握：前束范式的求法：前束范式的求法第48页，本讲稿共57页 一、前束范式定义一、前束范式定义定义定义2-6.12-6.1：前束范式：前束范式：p一个公式，若一个公式，若量词量词均在全式的均在全式的开头开头，它们的作
47、用域延伸到整个，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。公式的末尾，则该公式叫做前束范式。前束范式的形式：前束范式的形式：p(v1)(v2).(vn)An其中其中可能是量词可能是量词 或量词或量词，vi(i=1,2,n)是客体变元，是客体变元，A是是没有量词的谓词公式。没有量词的谓词公式。一个谓词公式的前束范式符合下面条件：一个谓词公式的前束范式符合下面条件：p(1)(1)所有量词前面都没有联结词；所有量词前面都没有联结词；p(2)(2)所有量词都在公式的左面；所有量词都在公式的左面；p(3)(3)所有量词的辖域都延伸到公式的末尾。所有量词的辖域都延伸到公式的末尾。例如例如:(
48、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)前束范式前束范式不是前束范式不是前束范式前束范式前束范式不是前束范式不是前束范式第49页，本讲稿共57页前束范式存在定理前束范式存在定理定定理理2-6.1(2-6.1(前前束束范范式式存存在在定定理理)任任意意公公式式A A都都有有与与之之等等价的前束范式。价的前束范式。第50页，本讲稿共57页二、前束范式的写法二、前束范式的写法定定理理2-6.1的的证证明明给给出出了了将将任任意意一一个个谓谓词词公公式式化化为为与与之之等等价价的的前前束束范范式式
49、的的方法。步骤如下：方法。步骤如下：1)消除多余量词；消除多余量词；2)消去公式中的联结词消去公式中的联结词和和(为了便于量词辖域的扩充为了便于量词辖域的扩充)；3)后移后移p如果量词前有如果量词前有“”，则用量词否定公式将，则用量词否定公式将“”后移后移。再用摩。再用摩根定律或求公式的否定公式，将根定律或求公式的否定公式，将“”后移到原子谓词公式后移到原子谓词公式之前。之前。4)变元换名变元换名p用约束变元的改名规则或自由变元的代入规则对用约束变元的改名规则或自由变元的代入规则对变元换名变元换名(为为量词辖域扩充作准备量词辖域扩充作准备)；5)提取量词提取量词p用量词辖域扩充公式用量词辖域扩
50、充公式提取量词提取量词，使之成为前束范式形式。，使之成为前束范式形式。B(x)A(x)(x)(BA(x)B(x)A(x)(x)(BA(x)B(x)A(x)(x)(BA(x)B(x)A(x)(x)(BA(x)第51页，本讲稿共57页例例 求求(x)A(x)(x)B(x)的前束范式的前束范式 (x)A(x)(x)B(x)(x)A(x)(x)B(x)(去去)(x)A(x)(x)B(x)(“”后移后移)(x)A(x)(y)B(y)(换元换元)(x)(A(x)(y)B(y)(量词辖域扩充量词辖域扩充)(x)(y)(A(x)B(y)另一个方法：另一个方法：(x)A(x)(x)B(x)(x)A(x)(x)B