资源描述：
《大连理工大学软件学院 离散数学 第二章 谓词逻辑-2nd.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2/44离散数学第二章谓词逻辑2/43回顾谓词、个体、量词一元、多元、域、全称、存在合式谓词公式定义：5条自由变元和约束变元含有量词的等价式和永真蕴含式谓词公式的解释3/43记忆规律4/432.2谓词逻辑中的推理规则推理规则5/43规则1：约束变元的改名规则对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现。规则如下：欲改名之变元应是某量词作用范围内的变元，且应同时更改该变元在此量词辖域内的所有约束出现，而公式的其余部分不变。新的变元符号应是此量词辖域内原先没有使用过的，最好是公式中未出现过的符号。6/43规则1：约束变元的改
2、名规则例：对公式进行换名，使各变元只呈一种形式出现。解：需要对约束变元x，y进行换名不对的：~~7/43规则2：自由变元的代入规则对公式中自由变元的更改叫做代入。规则如下：欲改变自由变元的名，必改在公式中的每一处自由出现。新变元不应在原公式中以任何约束形式出现。例：对公式的变元x,y的自由出现用w,t代入，得8/43例如对公式(x)(P(x)→Q(x))∨(x)(P(x)→R(x))为清楚起见，可对第二个约束变元x进行换名(x)(P(x)→Q(x))∨(y)(P(y)→R(y))又例如对公式(x)(P(x)→R(x,y))∧Q(x,y)
3、可对约束变元x进行换名，得(z)(P(z)→R(z,y))∧Q(x,y)(z)(P(z)→R(x,y))∧Q(x,y)(y)(P(y)→R(y,y))∧Q(x,y)错误：~~~~9/43规则3：命题变元的代换规则用任一谓词公式Ai代换永真公式Ｂ中某一命题变元Pi的所有出现，所得到的新公式B´仍然是永真式（但在Ai的个体变元中不应有Ｂ中的约束变元出现）,并有。10/43规则4：取代规则设都是含n个自由变元的谓词公式，且A´是A的子公式。若在A中用B´取代A´的一处或多处出现后所得的新公式是B，则有。如果A为永真式，则B也是永真式。11/4
4、3谓词逻辑的推理在谓词逻辑中，推理的形式结构仍为若是永真式，则称由前提逻辑的推出结论C，在此,C均为谓词公式。12/43规则5：量词的增加和删除规则全称特指规则US：从可得出结论A(y)，其中y是个体域中任一个体，即：注意：y不能和A(x)中其它指导变元重名。存在特指规则ES：从可得出结论A(a)，其中a是和在此之前不曾出现过的个体常量，即：注意：a不能和指定前提中任一自由变元同名，也不能和使用本规则以前任一推导步骤上得到的公式的自由变元同名。13/43规则5：量词的增加和删除规则存在推广规则EG：从A(x)可得出结论，其中x是个体域中
5、的某一个个体，即：注意：y不和A(x)中其他自由变元或指导变元同名。全称推广规则UG：从A(x)可得出结论，其中x是个体域中的任意个体，即：使用条件:(1)x不是给定前提中任一公式的自由变元；(2)x不是在前面推导步骤中使用ES规则引入的变元；(3)若在前面推导过程中使用ES规则引入新变元u时，x是自由变元，那么在A(x)中，u应约束出现。UG-------UniversalGeneralizationEG-------ExistentialGeneralizationUI-------UniversalInstantiationEI-
6、------ExistentialInstantiationUS-------UniversalSpecialisationES-------ExistentialSpecialisation15/43谓词逻辑中的推理例1：证明：16/43谓词逻辑中的推理例2：试证明证明：17/43谓词逻辑中的推理例3：证明：18/43谓词逻辑中的推理接上页19/43例4指出下面推理的错误.设D(x,y)表示“x可被y整除”,个体域为{5,7,10,11}.因为D(5，5)和D(10,5)为真，所以xD(x,5)为真.因为D(7，5)和D(11,5)为
7、假，所以xD(x,5)为假.但有下面的推理过程：(1)xD(x,5)前提(2)D(z,5)(1);ES(3)xD(x,5)(2);UG因此，xD(x,5)xD(x,5).错！20/43反证法举例例5：证明：21/43反证法举例接上页22/43谓词逻辑中的推理例6：使用CP规则证明证明：因此原来的证明转化为证明下式：23/43谓词逻辑中的推理证明24/43例7对多个量词的使用情况，观察下列推理过程.证明（1）前提（2）（1）；US（3）（2）；ES（4）（3）；UG（5）（4）；EG推出错误结论：与可交换.注意：公式(2)中z有两种可能1
8、)若z是自由个体变元，则此时y的值是随z的变化而变化的，因此不能用ES规则将y改为个体常元d。2)若z是个体常元，则公式(3)没错，但此时不能用UG规则得到(4)。错！错！25/43谓词逻辑求解实际问题步骤
