离散数学第二章谓词逻辑--节优秀PPT.ppt

《离散数学第二章谓词逻辑--节优秀PPT.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑--节优秀PPT.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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、学习的是第5页，共57页变元混淆变元混淆 指导指导变元变元(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

7、(x)A(x)nx以两种形式出现。可以对约束变元以两种形式出现。可以对约束变元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)

8、(R(x)A(x)对自由变对自由变元元x作代入，改成作代入，改成 (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

11、)(4)b)(5)a)n量词的辖域、约束变元、自由变元。量词的辖域、约束变元、自由变元。n变元的改名变元的改名（重点掌握）（重点掌握）p约束变元的换名。约束变元的换名。p自由变元的代入。自由变元的代入。现在学习的是第11页，共57页2-5 2-5 谓词演算的等价式和蕴含式谓词演算的等价式和蕴含式要要求求：理理解解谓谓词词公公式式赋赋值值、等等价价、有有效效（永永真真）、不不可可满满足足、可可满满足足等等概概念念，掌掌握握一一些些谓谓词词演演算算的的等价式和蕴含式。等价式和蕴含式。重点：重点：谓词公式的等价和永真谓词公式的等价和永真。难点：难点：多个量词的使用。多个量词的使用。现在学习的是第12

12、页，共57页一、对谓词公式赋值一、对谓词公式赋值定义定义：对公式中的变量制定具体的常量去替代。：对公式中的变量制定具体的常量去替代。n将将命题变元命题变元，用确定的命题代替，用确定的命题代替，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

14、(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(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的真值为真

15、，的真值为真，则称公式则称公式A在个体域在个体域E上是永真的（有效的）上是永真的（有效的）。定义定义2-5.2：A为不可满足的为不可满足的:p一个谓词公式一个谓词公式A，如果在所有赋值下都为假，如果在所有赋值下都为假，则称则称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)。解解

16、无无论论在在何何个个体体域域中中，无无论论对对变变元元作作何何种种赋赋值值，公公式式(1)(1)，(2)(2)均取真值均取真值T T，而公式，而公式(3)(3)均取真值均取真值F F。从从而而(1)(1)，(2)(2)就就是是关关于于一一切切个个体体域域与与一一切切赋赋值值下下恒恒取取“T T”值值的的谓谓词词公公式式，(3)(3)就就是是关关于于一一切切个个体体域域与与一一切切赋赋值下恒取值下恒取“F F”值的谓词公式。值的谓词公式。现在学习的是第17页，共57页三、谓词公式的等价公式定义三、谓词公式的等价公式定义定义定义2-5.42-5.4：A A与与B B在个体域在个体域E E上是等价的

17、。上是等价的。p给定谓词公式给定谓词公式A A、B B，E E是它们的共同个体域是它们的共同个体域，如果不论对，如果不论对公式公式A A、B B作任何赋值，作任何赋值，都使得都使得A A与与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

18、):,N(x):表示表示x x是自然数，是自然数，p假设个体域假设个体域E E是自然数集合，公式是自然数集合，公式I(x)I(x)与与N(x)N(x)在在E E上是等价的。上是等价的。p 而公式而公式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是它们的个体域，如

19、果不论对公式是它们的个体域，如果不论对公式A、B作任何赋值，都使得作任何赋值，都使得AB为重言式，则称为重言式，则称在个体在个体域域E上上公式公式A蕴含蕴含B。定义定义：公式公式A蕴含蕴含B。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)就是与个体域无关的重言式，就是与个体域无关的重言式，所

20、以所以(G(x)N(x)N(x)。现在学习的是第19页，共57页五、对偶定理五、对偶定理定义：定义：设在公式设在公式A中没有联结词中没有联结词和和，与与，、，命命题题常常量量F和和T互互换换，得得到到的的公公式式A*称为称为A的对偶式。的对偶式。定定理理2-5.1（对对偶偶定定理理）设设有有等等价价式式AB，并并在在A,B中没有联结词中没有联结词和和，则必有，则必有A*B*现在学习的是第20页，共57页六、重要公式六、重要公式讨论重要的谓词等价公式和重言蕴含式。讨论重要的谓词等价公式和重言蕴含式。由命题公式推广出的公式由命题公式推广出的公式消去量词等值式消去量词等值式 量词否定等值式量词否定等

21、值式 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 量词分配等值式量词分配等值式 现在学习的是第21页，共57页（一）（一）由命题公式推广出的公式由命题公式推广出的公式n因因一一个个不不含含自自由由变变元元的的谓谓词词公公式式本本身身如如(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页（二）量词否定公式（二）量词否定公

23、式例：例：(x)表示表示x是优等生，个体域是某班级的学生集合。是优等生，个体域是某班级的学生集合。p(x)A(x)表示：所有人都是优等生。表示：所有人都是优等生。p(x)A(x)表示：有些人是优等生。表示：有些人是优等生。p(x)A(x)表示：表示：不是所有人都是优等生。不是所有人都是优等生。p(x)A(x)表示：表示：有些人不是优等生。有些人不是优等生。p (x)A(x)表示：表示：不存在有人是优等生。不存在有人是优等生。p(x)A(x)表示：表示：所有人都不是优等生。所有人都不是优等生。从这个例子可以看出从这个例子可以看出p“不是所有人都是优等生不是所有人都是优等生”与与“有些人不是优等生

24、有些人不是优等生”是等价的。是等价的。p“不存在有人是优等生不存在有人是优等生”与与“所有人都不是优等生所有人都不是优等生”是等价的。于是有：是等价的。于是有：现在学习的是第24页，共57页证明证明1.(x)A(x)(x)A(x)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对于非量化命题的否定只需将动词否定，而对于量化命题对于

25、非量化命题的否定只需将动词否定，而对于量化命题的否定，需要对动词和量词同时否定。的否定，需要对动词和量词同时否定。(x)的否定变为的否定变为(x)(x)的否定变为的否定变为(x)n所以我们也把这两个公式称为所以我们也把这两个公式称为量词转换公式量词转换公式。现在学习的是第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

26、)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)现在学习的是第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

27、)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.时，时，要特别注意，量词的要特别注意，量词的辖域扩充后，量词发辖域扩充后，量词发生了变化。生了变化。现在学习的是第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(

28、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)E232.(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

29、.(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中的人。中的人。A(x)：x唱歌，唱歌，B(x)：x跳舞跳舞 则则(x)(A(x)B(x)表示：表示：p party里的所有人既唱歌又跳舞；里的所有人既唱歌又跳舞；(x)A(x)(x)B(x)表示：表示：pparty里的所有人唱歌且里的所有人唱歌且party里的所有人都跳舞。里的所有人都跳舞。两者意义是相同的两者意义是相同的。即有：即有：(x)(A

30、(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)表示：表示：pParty中有些人唱歌或跳舞；中有些人唱歌或跳舞；(x)A(x)(x)B(x)表示：表示：pParty中有些人唱歌或中有些人唱歌或Party中有些人跳舞。中有些人跳舞。两者意义是相同的。两者意义是相同的。所以所以,(x)(A(x)B(x)(x)A(x)(x)B(x)现在学习的是第31页，共57页注意注意公式公式3.和和4.不是

31、等价公式，不是等价公式，是重言蕴含式。是重言蕴含式。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中有人唱歌，且有人跳舞。中有人唱歌，且有人跳舞。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页公

32、式公式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(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

33、)(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)现在学习的是第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)为真，为

34、真，所以所以(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所以有所以有(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)如果如果(

35、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)为为假，则必有客体假，则必有客体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)和

36、和(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)x)(A(A(x)(x)B B(x)(x)且且现在学习的是第36页，共57页（四）量词分配公式（四）量词分配公式(等价式和蕴含式等价式和蕴含式)利用公式利用公式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

37、)(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页量词分配公式总结量词分配公式总结全称量词全称量词“”对对“”无分配律。无分配律。存在量词存在量词“”对对“”无分配律。无分配律。当当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)(

38、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)(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页（五）其它公式（五）其它

39、公式证明证明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)(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)

40、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是乙村人是乙村人n 甲村所有人与甲村所有人与乙村所有人同姓。乙村所有人同姓。n 乙村所有人与乙村所有人与甲村所有人同姓。甲村所有人同姓。n 甲村和甲村和乙乙村有人同姓。村有人同姓。n 乙村和甲乙村和甲村村有人同姓。有人同姓。n 存在一个存在一个(些些)甲村的人，乙村

41、所有人与甲村的人，乙村所有人与之同姓。之同姓。n 乙村所有人，乙村所有人，甲村都有人与之同姓甲村都有人与之同姓n 存在一个存在一个(些些)乙村的人，甲村所有人与之同乙村的人，甲村所有人与之同姓。姓。n 甲村所有人，乙甲村所有人，乙村都有人与之同姓村都有人与之同姓(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

42、)(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页，共57页(x)(y)A(x,y)(y)(x)A(x,y)证明证明用用谓谓词词

43、逻逻辑辑推推理理方方法法很很容容易易证证明明上上面面的的重重言言蕴蕴含含式式。下下面面证证明明公公式式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,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,

44、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(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

45、(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页，共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页本节小结本节小结熟熟练练掌掌握握谓

46、谓词词等等价价公公式式和和重重言言蕴蕴含含式式的的证证明明方方法法及应用。及应用。作业题：作业题：P66(3)b)P71(2)d),(6)现在学习的是第47页，共57页2-62-6 前束范式前束范式与与命命题题公公式式一一样样，我我们们对对谓谓词词公公式式也也要要讨讨论论范范式式，但但在在谓谓词词逻逻辑辑中中我我们们讨讨论论的的是是前前束束范范式式。因因为为在在定定理理的的机机器器证证明明中中，需需要要消消除除谓谓词词公公式式中中的的量量词词，因因而而需需要要将将谓谓词词公公式式中中的的量量词词前前束束化化，即即把把公公式式中中的的量词均提取到公式的前部。量词均提取到公式的前部。即即前前束束范

47、范式式主主要要是是对对量量词词的的位位置置有有要要求求，而而对对联联结结词无要求词无要求，这一点与命题逻辑不同。，这一点与命题逻辑不同。本节掌握本节掌握：前束范式的求法：前束范式的求法现在学习的是第48页，共57页 一、前束范式定义一、前束范式定义定义定义2-6.12-6.1：前束范式：前束范式：p一个公式，若一个公式，若量词量词均在全式的均在全式的开头开头，它们的作用域延伸到整个公，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。式的末尾，则该公式叫做前束范式。前束范式的形式：前束范式的形式：p(v1)(v2).(vn)An其中其中可能是量词可能是量词 或量词或量词，vi(i=1,2

48、,n)是客体变元，是客体变元，A是是没有量词的谓词公式。没有量词的谓词公式。一个谓词公式的前束范式符合下面条件：一个谓词公式的前束范式符合下面条件：p(1)(1)所有量词前面都没有联结词；所有量词前面都没有联结词；p(2)(2)所有量词都在公式的左面；所有量词都在公式的左面；p(3)(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)前束范式前束范式不是前束范式不是前束范式前束范式前束范式不是前束范式不是前束范式现在

49、学习的是第49页，共57页前束范式存在定理前束范式存在定理定定理理2-6.1(2-6.1(前前束束范范式式存存在在定定理理)任任意意公公式式A A都都有有与与之之等等价价的前束范式。的前束范式。现在学习的是第50页，共57页二、前束范式的写法二、前束范式的写法定定理理2-6.1的的证证明明给给出出了了将将任任意意一一个个谓谓词词公公式式化化为为与与之之等等价价的的前前束束范范式式的的方法。步骤如下：方法。步骤如下：1)消除多余量词；消除多余量词；2)消去公式中的联结词消去公式中的联结词和和(为了便于量词辖域的扩充为了便于量词辖域的扩充)；3)后移后移p如果量词前有如果量词前有“”，则用量词否定

50、公式将，则用量词否定公式将“”后移后移。再用。再用摩根定律或求公式的否定公式，将摩根定律或求公式的否定公式，将“”后移到原子谓词公式后移到原子谓词公式之前。之前。4)变元换名变元换名p用约束变元的改名规则或自由变元的代入规则对用约束变元的改名规则或自由变元的代入规则对变元换名变元换名(为量为量词辖域扩充作准备词辖域扩充作准备)；5)提取量词提取量词p用量词辖域扩充公式用量词辖域扩充公式提取量词提取量词，使之成为前束范式形式。，使之成为前束范式形式。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)现在学习的是