资源描述：
《离散数学第2章第2节ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学DiscreteMathematics山东科技大学信息科学与工程学院内容回顾谓词逻辑的基本概念：谓词、谓词填式、n元谓词、命题函数、复合命题函数、个体域、全称量词、存在量词等谓词合式公式：递归式定义；命题翻译举例：(x)P(x,y)量词量词1、指导变元、作用域、约束变元、自由变元量词指导变元辖域约束变元自由变元2-4变元的约束通常，一个量词的辖域是公式的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：若量词后有括号，则括号内的子公式就是该量词的辖域；若量词后无括号，则
2、与量词邻接的子公式为该量词的辖域。判定给定公式中个体变元是约束变元还是自由变元，关键是要看它在公式中是约束出现，还是自由出现。约束变元的判断就近原则：变元受最近量词的约束；由里向外原则：对于复杂公式的判断，由里向往逐层判断；约束变元判断的两个原则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说明以下各式的作用域与变元约束
3、的情况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说
4、明以下各式的作用域与变元约束的情况约束变元判断约束变元判断方法：要求熟练掌握课外作业：能否程序实现约束变元的判断？输入：谓词公式输出：指导变元、作用域、约束变元、自由变元2、闭式由闭式定义可知，闭式中所有个体变元均为约束出现。2、闭式c)(x)(y)(P(x,y)∧Q(y,z))∧(x)P(x,y)例题1说明以下各式的作用域与变元约束的情况约束变元自由变元x：有两种约束y：既有约束出现又有自由出现z：自由出现在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换
5、名或自由变元代入。二、约束变元换名和自由变元代入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、自由变元代入规则：对某自由出现的个体变元可用与原公式中所有个体变元不同的个体变元去代入
6、，且代入时需对公式中出现该自由变元的每一处进行。例题3：对(x)(P(y)∧R(x,y))代入解：对y实施代入，经代入后公式为(x)(P(z)∧R(x,z))三、有限论域客体变元的枚举量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代是可枚举的。根据上面的等价关系，可以消去公式中的量词。四、量词的次序注意：量词对变元的约束，往往与量词的次序有关，量词的次序不能颠倒。(x)(y)(父子(x,y)):任何人都有儿子(y)(x)(父子(x,y)):存在一人是所有人的儿子约定：对命题中的
7、多个量词，约定从左到右的次序读出。§2—5谓词演算的等价式和蕴含式命题逻辑的等价式：¬¬PP命题逻辑的蕴含式：P∧QP一、谓词公式的赋值在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值的命题。二、谓词公式的等价定义2-5.1给定任何两个谓词公式wffA和wffB，设它们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式A和B在E上是等价的，并记作：AB例如：
8、设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一
