量词转换律优秀课件.ppt

《量词转换律优秀课件.ppt》由会员分享，可在线阅读，更多相关《量词转换律优秀课件.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、量词转换律第1页，本讲稿共33页两个谓词公式的个体变元必须有相同的两个谓词公式的个体变元必须有相同的个体域才能讨论其是否等价。个体域才能讨论其是否等价。回回 顾顾定义定义2-13 两个有相同个体域两个有相同个体域E的谓词公式的谓词公式A和和B，若对两个谓词公式所有变元的任一组赋值，所得若对两个谓词公式所有变元的任一组赋值，所得命题真值相同，则称这两个谓词公式在指定个体命题真值相同，则称这两个谓词公式在指定个体域域E上等价。记为上等价。记为 。第2页，本讲稿共33页（一）命题公式的推广（一）命题公式的推广 第3页，本讲稿共33页（二）量词转换律（二）量词转换律 我们将否定符移到量词后面时，全称量

2、词变为存在量词，存在量词变为全称量词。反之，量词后面的否定符移到量词的前面时，也要作相应的改变，这种量词与否定的关系是普遍成立的，人们习惯称之为量词转换律量词转换律第4页，本讲稿共33页（三）量词辖域的扩张和收缩（三）量词辖域的扩张和收缩（1）若量词辖域中是合取式或析取式，则不受约束的谓词公）若量词辖域中是合取式或析取式，则不受约束的谓词公式可以直接进入和退出该辖域。式可以直接进入和退出该辖域。（2）若量词辖域是条件命题的前件，则作为后件的不受约束的谓词）若量词辖域是条件命题的前件，则作为后件的不受约束的谓词公式不能直接进出该辖域。公式不能直接进出该辖域。（3）若量词辖域是条件命题后件，则作为

3、前件不受约束的谓）若量词辖域是条件命题后件，则作为前件不受约束的谓词公式可以直接进出该辖域。词公式可以直接进出该辖域。第5页，本讲稿共33页（四）含量词的合取式、析取式的等价式（四）含量词的合取式、析取式的等价式 （1）全称量词可以对合取式进行分配）全称量词可以对合取式进行分配.（2）存在量词可对析取式进行分配。）存在量词可对析取式进行分配。【说明】全称量词可以合取式进行分配，存在量词可以对析【说明】全称量词可以合取式进行分配，存在量词可以对析取式进行分配，但全称量词不能对析取式进行分配，存在量取式进行分配，但全称量词不能对析取式进行分配，存在量词不能对合取式进行分配。词不能对合取式进行分配。

4、由以上四点我们可以得到一组常用的谓词等价公式如由以上四点我们可以得到一组常用的谓词等价公式如下：下：第6页，本讲稿共33页 E16 E17 E18 E19 E20 E21 E22 E23E24E25E26 E27 第7页，本讲稿共33页第8页，本讲稿共33页第9页，本讲稿共33页第10页，本讲稿共33页课后作业P54：2.6（2）2.10（1）2.12（1）第11页，本讲稿共33页 2.5 谓词演算中的永真蕴含公式谓词演算中的永真蕴含公式 定义定义2-18 设设P、Q为谓词公式，若为谓词公式，若PQ为永真式，则为永真式，则称称P永真蕴含永真蕴含Q，简称为，简称为P蕴含蕴含Q，记为，记为PQ。前

5、面介绍了全称量词可以对合取式进行分配，存在量词可以对析前面介绍了全称量词可以对合取式进行分配，存在量词可以对析取式进行分配。我们不觉要问，全称量词对析取式、存在量词对合取取式进行分配。我们不觉要问，全称量词对析取式、存在量词对合取式究竟有什么关系呢？式究竟有什么关系呢？（1）存在量词对合取式的蕴含式）存在量词对合取式的蕴含式 证明：假设前件证明：假设前件x(P(x)Q(x)为真，则论域中至少存在一个个体为真，则论域中至少存在一个个体c，使得，使得P(c)Q(c)为真。所以为真。所以P(c)为真、为真、Q(c)也为真也为真。即即xP(x)为真、为真、xQ(x)也为真也为真。因此，。因此，xP(x

6、)xQ(x)为真。为真。第12页，本讲稿共33页 例如例如 设论域为自然数。设论域为自然数。因为存在一个自然数因为存在一个自然数2，2既是偶数又是素数，所以公式既是偶数又是素数，所以公式成立。成立。反之若设反之若设 则则xP(x)xQ(x)为真，但论域中不存在一个自然数既为真，但论域中不存在一个自然数既是偶数又是奇数，使得是偶数又是奇数，使得x(P(x)Q(x)为真，所以为真，所以 不成立。不成立。第13页，本讲稿共33页（2）全称量词对析取式的蕴含式证明：证明：第14页，本讲稿共33页（3）其它蕴含式）其它蕴含式 证明：设论域为证明：设论域为D，xP(x)若为真，则对于论域中的任一个体若为真

7、，则对于论域中的任一个体c，P(c)为真。根据定义为真。根据定义xP(x)为真。所以蕴含式成立。为真。所以蕴含式成立。例例2-14 证明证明 证明：证明：（4）多重量化及其等价式和蕴含式）多重量化及其等价式和蕴含式 谓词公式中往往不只包含一个个体变元，为了使命题函数成谓词公式中往往不只包含一个个体变元，为了使命题函数成为命题，必须对各个个体变元进行量化，这样便出现多重量化的为命题，必须对各个个体变元进行量化，这样便出现多重量化的问题。如何解决多重量化问题，我们以两重量化为例加以说明，问题。如何解决多重量化问题，我们以两重量化为例加以说明，多重量化与此类同。对于二元谓词如果不考虑自由变元，可以有

8、多重量化与此类同。对于二元谓词如果不考虑自由变元，可以有以下八种情况：以下八种情况：第15页，本讲稿共33页 其中其中 和和 含义相同，含义相同，和和 含义相同。后面四种情况经过换名后实际上只有两种情况。含义相同。后面四种情况经过换名后实际上只有两种情况。即即 和和 。例如例如 设设x的个体域为甲班，的个体域为甲班，y 的个体域为乙班。的个体域为乙班。：表示同姓。则：表示同姓。则：表示甲班每个人和乙班所有人同姓。：表示甲班每个人和乙班所有人同姓。：表示乙班每个人和甲班所有人同姓。：表示乙班每个人和甲班所有人同姓。所以甲班和乙班所有人同姓，即所以甲班和乙班所有人同姓，即同理可得：同理可得：第16

9、页，本讲稿共33页仍以上述例子讨论其它两种情况：仍以上述例子讨论其它两种情况：甲班每个人在乙班中可以找到同姓的人。：甲班每个人在乙班中可以找到同姓的人。：甲班有人与乙班中所有人同姓。此时乙班所有人都同姓。：甲班有人与乙班中所有人同姓。此时乙班所有人都同姓。从上述例子中可知，相同量词的出现顺序可以交换，而不同量词从上述例子中可知，相同量词的出现顺序可以交换，而不同量词出现的顺序不可以交换，但它们之间存在着蕴含关系。出现的顺序不可以交换，但它们之间存在着蕴含关系。证明：设证明：设 为真，则至少存在一个个体为真，则至少存在一个个体 ，使得对于所有，使得对于所有 为真。即为真。即 为真，所以为真，所以

10、 为真，为真，为真。为真。该公式的逆反命题为：该公式的逆反命题为：第17页，本讲稿共33页所以有两个量词的谓词公式有如下的蕴含关系：所以有两个量词的谓词公式有如下的蕴含关系：第18页，本讲稿共33页谓词演算中常用的等价式和蕴含式谓词演算中常用的等价式和蕴含式 E16 E17 E18 E19 E20 E21 E22 E23E24E25E26 E27 I14 I15 I16第19页，本讲稿共33页例例2-15用谓词演算的等价式和蕴含式证明用谓词演算的等价式和蕴含式证明（1）（2）（3）（4）证明证明(1)：证明证明(2)：第20页，本讲稿共33页证明证明(3)：要证明：要证明 ，只须证明，只须证明

11、 为真即可。为真即可。第21页，本讲稿共33页证明证明(4)：第22页，本讲稿共33页 26谓词演算的推理理论谓词演算的推理理论 谓词演算可以看作命题演算的推广，因为谓词演算的等价谓词演算可以看作命题演算的推广，因为谓词演算的等价式和蕴含式很多是命题演算中有关公式的推广，所以命题演算式和蕴含式很多是命题演算中有关公式的推广，所以命题演算中的推理规则，如中的推理规则，如P、T和和CP规则在谓词演算中仍适用。由于谓规则在谓词演算中仍适用。由于谓词逻辑中存在量词，所以在谓词演算中的某些前提和结论可能受词逻辑中存在量词，所以在谓词演算中的某些前提和结论可能受到量词的约束。为了使谓词演算的推理过程使用命

12、题逻辑有关的到量词的约束。为了使谓词演算的推理过程使用命题逻辑有关的等价式和蕴含式，使整个推理过程按命题演算的推理过程进行，等价式和蕴含式，使整个推理过程按命题演算的推理过程进行，必须在谓词演算过程中消去和添加量词，这样就必须有相应的规必须在谓词演算过程中消去和添加量词，这样就必须有相应的规则。则。（1）全称指定规则（）全称指定规则（US）该规则中，该规则中，c是个体域是个体域D中的任意一个个体。该推理规则中的任意一个个体。该推理规则的横线下面是结论的横线下面是结论A(c)。该规则表明，如果个体域。该规则表明，如果个体域D中全部中全部个体都满足个体都满足A(x)，则对个体域，则对个体域D中的某

13、个个体中的某个个体c，c肯定满足肯定满足A(x)。第23页，本讲稿共33页（2）全称推广规则（）全称推广规则（UG）如果论域如果论域D中的任意一个个体中的任意一个个体c，都能使都能使A(c)成立，则由该成立，则由该规则可得结论成立。注意，此时的个体规则可得结论成立。注意，此时的个体c不是论域中某一特定的个体，不是论域中某一特定的个体，而是泛指论域中所有的个体。而是泛指论域中所有的个体。（3）存在指定规则（存在指定规则（ES）该规则中，该规则中，c是个体域是个体域D中使中使A(x)为真的个体，而不是任意取的一为真的个体，而不是任意取的一个个体。个个体。（4）存在推广规则（）存在推广规则（EG）该

14、规则的前提中的该规则的前提中的c是个体域是个体域D中使中使A(x)为真的个体，即只为真的个体，即只要个体要个体D中至少存在一个个体使得为真，则为真。中至少存在一个个体使得为真，则为真。第24页，本讲稿共33页例例2-16：证明苏格拉底三段论的正确性。：证明苏格拉底三段论的正确性。所有的人都要死。所有的人都要死。苏格拉底是人。苏格拉底是人。所以苏格拉底要死。所以苏格拉底要死。证明证明 首先将命题符号化。设个体域是全总个体域。首先将命题符号化。设个体域是全总个体域。令令H(x)：x是人。是人。D(x)：x是要死的。是要死的。c：苏格拉底。：苏格拉底。则有前提：则有前提：结论：结论：D(c)以下是证

15、明过程：以下是证明过程：（1）（2）（3）H(c)（4）D(c)PUS(1)PT(2)(3)I11 假言推论假言推论第25页，本讲稿共33页例例2-17证明下列推理的正确性。证明下列推理的正确性。所有的有理数都是实数。某些有理数是整数。因此某些实数是所有的有理数都是实数。某些有理数是整数。因此某些实数是整数。整数。解解 首先将命题符号化。设个体域是全总个体域。首先将命题符号化。设个体域是全总个体域。令令P(x)：x是实数。是实数。Q(x)：x是有理数。是有理数。R(x)：x是整数。是整数。则有前提：则有前提：结论：结论：第26页，本讲稿共33页证：（证：（1）（2）（3）（4）（5）（6）（7

16、）（8）（9）PES(1)T(2)I1 化简公式化简公式PUS(4)T(3)(5)I2 化简公式化简公式T(2)I2 化简公式化简公式T(6)(7)I9EG(8)第27页，本讲稿共33页例例2-18证明证明证明：证明：（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）PES(1)T(2)I1PUS(4)T(3)(5)I11 假言推论假言推论T(6)I1 化简公式化简公式T(2)I2 化简公式化简公式T(7)(8)I9EG(9)第28页，本讲稿共33页例例2-18证明证明注意注意：使用同一个个体进行全称指定和存在指定时，必须先使用同一个个体进行全称指定和存在指定时，必须先做存在指定，

17、后做全称指定。因为使存在量词辖域中的谓做存在指定，后做全称指定。因为使存在量词辖域中的谓词公式为真个体，在全称指定中肯定为真，反之则不然。词公式为真个体，在全称指定中肯定为真，反之则不然。上述述问题若推理如下：上述述问题若推理如下：第29页，本讲稿共33页证明：证明：（1）P（2）US(2)（3）P（4）US(3)（5）这个推证是错误的，因为使这个推证是错误的，因为使 为真的为真的个体，个体，不见得为真。不见得为真。第30页，本讲稿共33页例例2-19证明证明证明：证明：（1）（2）（3）（4）（5）（6）（7）PUS(1)T(2)E11 联结词归化联结词归化PUS(4)T(3)(6)I11

18、假言推论假言推论EG(6)第31页，本讲稿共33页例例2-20计算机学会的所有成员中，若不是硬件专家便是软件专计算机学会的所有成员中，若不是硬件专家便是软件专家家.所有硬件专家擅长电路设计，擅长电路设计的人一定精通电子学，所有硬件专家擅长电路设计，擅长电路设计的人一定精通电子学，计算机学会中有人不懂电子学。因此，计算机学会中有软件专家。论计算机学会中有人不懂电子学。因此，计算机学会中有软件专家。论域计算机学会成员。域计算机学会成员。解解 论域论域D：计算机学会全体会员：计算机学会全体会员 为硬件专家。为硬件专家。为软件专家。为软件专家。擅长电路设计。擅长电路设计。精通电子学。精通电子学。命题形式化为：命题形式化为：第32页，本讲稿共33页证明：证明：（1）（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）P ES(1)PUS(3)T(2)(4)I12 拒取式拒取式PUS(6)T(5)(7)I12 拒取式拒取式PUS(9)T(8)(10)I11 假言推论假言推论EG(11)第33页，本讲稿共33页