离散数学第2章第2节.

离散数学DiscreteMathematics山东科技大学信息科学与工程学院内容回顾谓词逻辑的基本概念：谓词、谓词填式、n元谓词、命题函数、复合命题函数、个体域、全称量词、存在量词等谓词合式公式：递归式定义；命题翻译举例：(x)P(x,y)量词量词1、指导变元、作用域、约束变元、自由变元()(,)xPxy量词指导变元辖域约束变元自由变元2-4变元的约束通常，一个量词的辖域是公式的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：若量词后有括号，则括号内的子公式就是该量词的辖域；若量词后无括号，则与量词邻接的子公式为该量词的辖域。判定给定公式中个体变元是约束变元还是自由变元，关键是要看它在公式中是约束出现，还是自由出现。约束变元的判断就近原则：变元受最近量词的约束；由里向外原则：对于复杂公式的判断，由里向往逐层判断；约束变元判断的两个原则a)(x)(P(x)Q(x))b)(x)(P(x)(y)R(x,y))c)(x)(y)(P(x,y)∧Q(y,z))∧(x)P(x,y)d)(x)(P(x)∧(x)Q(x,z)(y)R(x,y))∨Q(x,y)例题1说明以下各式的作用域与变元约束的情况a)(x)(P(x)Q(x))例题1说明以下各式的作用域与变元约束的情况指导变元辖域约束变元b)(x)(P(x)(y)R(x,y))例题1说明以下各式的作用域与变元约束的情况指导变元辖域约束变元指导变元辖域约束变元c)(x)(y)(P(x,y)∧Q(y,z))∧(x)P(x,y)例题1说明以下各式的作用域与变元约束的情况指导变元辖域约束变元自由变元x：有两种约束y：既有约束出现又有自由出现z：自由出现d)(x)(P(x)∧(x)Q(x,z)(y)R(x,y))∨Q(x,y)例题1说明以下各式的作用域与变元约束的情况约束变元判断约束变元判断方法：要求熟练掌握课外作业：能否程序实现约束变元的判断？输入：谓词公式输出：指导变元、作用域、约束变元、自由变元2、闭式由闭式定义可知，闭式中所有个体变元均为约束出现。2、闭式在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。二、约束变元换名和自由变元代入c)(x)(y)(P(x,y)∧Q(y,z))∧(x)P(x,y)约束变元自由变元x：有两种约束y：既有约束出现又有自由出现z：自由出现规则：将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。解可换名为例题2：对(x)(P(x)R(x,y))∧Q(x,y)换名(z)(P(z)R(z,y))∧Q(x,y)1、约束变元换名2、自由变元代入规则：对某自由出现的个体变元可用与原公式中所有个体变元不同的个体变元去代入，且代入时需对公式中出现该自由变元的每一处进行。例题3：对(x)(P(y)∧R(x,y))代入解：对y实施代入，经代入后公式为(x)(P(z)∧R(x,z))三、有限论域客体变元的枚举量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代是可枚举的。12()()()()()nxAxAaAaAa根据上面的等价关系，可以消去公式中的量词。四、量词的次序注意：量词对变元的约束，往往与量词的次序有关，量词的次序不能颠倒。(x)(y)(父子(x,y)):任何人都有儿子(y)(x)(父子(x,y)):存在一人是所有人的儿子约定：对命题中的多个量词，约定从左到右的次序读出。§2—5谓词演算的等价式和蕴含式命题逻辑的等价式：¬¬PP命题逻辑的蕴含式：P∧QP一、谓词公式的赋值在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值的命题。二、谓词公式的等价定义2-5.1给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式A和B在E上是等价的，并记作：AB例如：设P,Q为任意谓词变元;x为全总个体域上的个体变元,则谓词公式A=¬P(x)∧¬Q(x)与B=¬(P(x)∨Q(x))逻辑等价.三、谓词公式的分类定义2-5.2给定任意谓词公式wffA，其个体域为E，对于A的所有赋值，wffA都为真，则称wffA在E上是有效的（或永真的）。定义2-5.3一个谓词公式wffA，如果在所有赋值下都为假，则称wffA为不可满足的（或永假的）。定义2-5.4一个谓词公式wffA，如果至少在一种赋值下为真，则称wffA为可满足的。与命题公式真值讨论类似，可描述谓词公式在指定变量后的真值情况，进而划分出永真公式或永假公式。四、谓词演算的等价式和蕴含式1、命题公式的推广定理：在命题演算中，任一永真公式，其中同一命题变元，用同一公式取代时，其结果也是永真公式。推广：当谓词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式即为永真式。结论：命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。四、谓词演算的等价式和蕴含式1、命题公式的推广结论：命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。PQPQ()(()())()(()())xPxQxxPxQx()()()(,)(()(()()(,))xPxyRxyxPxyRxy()PQPQPPF()(,)()(,)xHxyxHxyF命题演算的等价式谓词演算的等价式2、量词与联结词¬之间的关系将量词前面¬的移到量词后面去时，存在量词改为全称量词，全称量词改为存在量词；反之，将量词后面的¬移到量词前面去时，也要做相应的改变。¬(x)P(x)(x)¬P(x)¬(x)P(x)(x)¬P(x)量词的否定与德摩根律--与的对偶性当个体域为有限集{x1,…,xn}时,¬(x)P(x)(x)¬P(x)可表为¬(P(x1)∧…∧P(xn))¬P(x1)∨…∨¬P(xn);¬(x)P(x)(x)¬P(x)可表为¬(P(x1)∨…∨P(xn))¬P(x1)∧…∧¬P(xn).这正是熟知的摩根律.而当个体域不为有限集时,量词否定可视为摩根律的推广.这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。3、量词扩张/收缩律(1)量词的作用域中常有合取项和析取项，如果其中一个为命题，可将该命题移至量词之外。证明当B为真时,左右两边都为真;否则,B为假,此时左右两边都等价于(x)A(x),证迄.提示：也可以利用谓词公式的可满足的定义来推理证明上述等价式成立。(x)A(x)∨B(x)(A(x)∨B)3、量词扩张/收缩律(2)()()()(())xAxBxAxB()()()(())xAxBxAxB()()()(())BxAxxBAx()()()(())BxAxxBAx这里A(x)是任意包括个体变元x的谓词公式，B是不包括个体变元x的任意谓词公式。证明(x)A(x)B(x)(A(x)B)(B不含x)证(x)A(x)B¬(x)A(x)∨B条件表达式(x)¬A(x)∨B量词否定(x)(¬A(x)∨B)量词辖域扩张(x)(A(x)B)条件表达式证明B(x)A(x)(x)(BA(x))(B不含x)证B(x)A(x)¬B∨(x)A(x)条件表达式(x)(¬B∨A(x))量词辖域扩张(x)(BA(x))条件表达式当谓词的变元与量词的指导变元不同时，有类似于上述的公式。(x)(P(x)∨Q(y))((x)P(x))∨Q(y)(x)((y)P(x,y)∧Q(z))((x)(y)P(x,y)∧Q(z))4、量词与命题联结词之间的一些等价式量词分配律(x)(A(x)B(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)∧(x)B(x)在有限个体域E上证明(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)和(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)两个等价式。(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)(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)证明(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)5、量词与命题联结词之间的一些蕴含式(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))(x)(A(x)B(x))(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)∨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)∨(x)B(x)(x)(A(x)∨B(x))表2―1谓词演算中常用的等价式和蕴含式6、多个量词的使用考虑两个量词的情况。更多量词的使用方法与其类似。对于二元谓词如果不考虑自由变元，可以有以下八种情况。()()(,)xyAxy()()(,)yxAxy()()(,)yxAxy()()(,)yxAxy()()(,)xyAxy()()(,)xyAxy()()(,)xyAxy()()(,)yxAxy全称量词与存在量词在公式中出现的次序，不能随意更换。用双向箭头表示等价，单向箭头表示蕴含，见它们之间的关系。()()(,)()()(,)xyAxyyxAxy()()(,)()()(,)xyAxyyxAxy有两个等价关系：()()(,)()()(,)xyAxyyxAxy()()(,)()()(,)yxAxyxyAxy()()(,)()()(,)yxAxyxyAxy()()(,)()()(,)xyAxyyxAxy()()(,)()()(,)yxAxyxyAxy()()(,)()()(,)xyAxyyxAxy具有两个量词的谓词公式有如下一些蕴含关系：小结指导变元、作用域、约束变元、自由变元、闭式约束变元换名和自由变元代入有限论域客体变元的枚举谓词公式赋值、谓词公式等价、永真式、不可满足式、可满足式谓词公式的等价式和蕴含式作业P66:3,4,5P72:2a),4,7下次课前束范式前束析取范式前束合取范式谓词逻辑的推理理论