数理逻辑-谓词逻辑.ppt

《数理逻辑-谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《数理逻辑-谓词逻辑.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数理逻辑数理逻辑谓词逻辑教师：孙继荣电话：87768609Email:数理逻辑数理逻辑谓词逻辑n学习内容学习内容n谓词逻辑基本概念 n谓词，个体词，命题函数n量词，自由变元和约束变元n谓词的合式公式，谓词的解释n自然语句的形式化n谓词逻辑的等值和推理演算 n谓词逻辑的等值式n范式，基本推理公式n推理演算。数理逻辑数理逻辑谓词逻辑n教学要求n理解谓词、量词、变元、个体域等概念n掌握用谓词、量词、联结词构造谓词逻辑公式的方法n掌握谓词公式在给定解释下求真值的方法n会将谓词逻辑化为前束公式n会将谓词逻辑作为工具，将命题符号化，并能用推理规则进行逻辑证明。2.1 谓词逻辑基本概念n个体词与谓词n在谓词

2、逻辑中，原子命题分解成个体词和谓词n定义：个体词个体词是可以独立存在的客体，它可以是具体事物或抽象的概念；个体域个体域是个体（客体）的取值范围；谓词谓词是用来刻划个体词的性质或事物之间的关系的词 n大写字母表示谓词，小写字母表示个体（客体）n注意：单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.2.1 谓词逻辑基本概念n个体词与谓词n谓词也称为命题函数命题函数或简单命题函数n相关概念：零元谓词，n元谓词，全总个体域，复合命题函数n命题是谓词的特殊情况2.1 谓词逻辑基本概念n全称量词与存在量词n量词是在命题中表示数量的词n量词有两类：n全称量词，表示“所有的”，“任何的”，或“每一

3、个”；n存在量词，表示“存在某个”或“至少有一个”.n命题符号化必须指明个体域2.1 谓词逻辑基本概念n全称量词与存在量词n对于一个谓词，如果其中每个变量都有一个量词作用之下，则它就不再是命题函数，而是一个命题了。n在谓词逻辑，使用量词应注意以下几点：n在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。n在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。n 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。2.1 谓词逻辑基本概念n课堂练习：将下列命题符号化n(1)每个母亲都爱自己的孩子；n(2)所有的人都呼吸；n(3)有某些实数是有理数.2.2 谓词

4、公式n谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题.所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.n学习这一部分内容要侧重于能将谓词逻辑公式表达式中，消除量词写成与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和量词的作用下变元的自由性、约束性和更名规则、代入规则等.2.2 谓词公式n字母表的意义n个体常项：a,b,c,a0,a1,a2,n个体变项：x,y,z,x0,x1,x2,n函数符号：f,g,h,f0,f1,f2,n谓词符号：P,Q,R,S0,S1,S2,n量词符号：，n逻辑符号：，n括号与逗号：(,)2.2

5、 谓词公式n相关概念：n字母表n项：递归定义 P43n原子公式2.2 谓词公式n合式公式n递归定义：P43n命题常数0，1，一个命题和命题变元以及一个命题函数P(x1,x2,xn)，统称原子公式n由原子公式、联结词和量词可构成谓词公式(严格定义见教材).n命题的符号化结果都是谓词公式。n例子：x(F(x)G(x)，x(F(x)G(x)，xy(F(x)F(y)L(x,y)H(x,y)等都是谓词公式.2.2 谓词公式n变元与辖域变元与辖域n在谓词公式xA和xA中，x是指导变元指导变元，A是相应量词的辖域辖域.n在x和x的辖域A中，x的所有出现都是约束出现，即x是约束变元约束变元，不是约束出现的变元

6、，就是自由变元自由变元.也就是说，量词后面的式子是辖域辖域.量词只对辖域内的同一变元有效.2.2 谓词公式n变元与辖域变元与辖域n自由变元有时会在量词辖域中出现，但是它不受相应量词指导变元的约束。n当谓词公式中没有自由变元时，它就是一个命题。n出现n个自由变元就是n元谓词。n变元可以既是约束出现又是自由出现。n例子：P442.2 谓词公式n换名规则：换名规则：n对约束变元进行换名n就是把公式中量词的指导变元及其该量词辖域中的约束变元换成该公式中没有出现的个体变元，公式的其余部分不变.n代入规则：代入规则：n对自由变元进行代入n就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且

7、要把该公式中所有的该自由变元都换成新引入的该符号.n经过换名或代入后，公式的意义不应该改变2.2 谓词公式n课堂练习n对P44 例1中公式用换名或代入规则n重要公式nxA(x)A(a1)A(a2)A(an)nxA(x)A(a1)A(a2)A(an)2.3 谓词的等值演算n解释解释(赋值赋值)：n谓词公式的个体域D是非空集合n(1)每一个常项指定D中一个元素；n(2)每一个n元函数指定Dn到D的一个函数；n(3)每一个n元谓词指定Dn到0,1的一个谓词.n解释就是对各个变项指定特殊的常项去代替，有四部分组成：n(1)非空个体域D；n(2)D中有一部分特定元素，用来解释个体常项；n(3)D上一些特

8、定函数，用来解释出现的函数变项；n(4)D上一些特定谓词，用来解释谓词变项。2.3 谓词的等值演算n例子：P46n课堂练习：n给定解释I：n D2,3;n D中特定元素a=2；n 函数为n 谓词F(x)为F(2)=0,F(3)=1 G(x,y)为G(2,2)=G(2,3)=G(3,2)=0,G(3,3)=1 L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0n求在解释I下各公式的真值.n(1)x(F(x)G(x,a)n(2)xy L(x,y)2.3 谓词的等值演算n谓词公式分类谓词公式分类n在任何解释下，谓词公式A取真值1，公式A为逻辑有效式(永真式)；n在任何解释下

9、谓词公式A取真值0，公式A为永假式；n至少有一个解释是公式A取真值1，公式A称为可满足式。2.3 谓词的等值演算n谓词演算的等值式和重言蕴含式谓词演算的等值式和重言蕴含式 n(1)命题公式的推广；n(2)量词否定式的等值式；n(3)量词辖域扩张和收缩的等值式；n(4)量词与联结词，的等值式；n(5)量词与联结词的重言蕴含式；n(6)两个量词公式间的等值式与重言蕴含式。2.4 前束范式 n前束范式:n若一个谓词公式F等值地转化成Q1x1Q2x2 QkxkB,那么就是F的前束范式，其中Qi只能是量词或，而x1,x2,xk是个体变元，B是不含量词的谓词公式.n量词均在全式的开头，其作用域延伸到整个公

10、式的末尾2.4 前束范式n前束范式的重要性质n性质1：P49n性质2：P50n证明忽略2.4 前束范式n每个谓词公式F都可以变换成与它等值的前束范式.其步骤如下：n 消去联结词，；n 将联结词移至原子谓词公式之前；n 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；n将x,x移至整个公式最左边；n 将公式化为前束范式。n一般地，前束范式不是唯一地。2.4 前束范式n谓词公式-前束范式n例子：P51n课堂练习：练习2.4（B）32.5 谓词逻辑地推理理论n谓词演算的推理是命题演算推理的推广和扩充n命题演算中的一些规则，如基本等值公式，重言蕴含式以及P，T，CP规

11、则在谓词演算中仍然使用.2.5 谓词逻辑地推理理论n在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和添加量词的规则，以便使谓词演算公式的推理过程可类似于命题演算的推理进行 nUS规则规则(全称量词消去规则)nUG规则规则(全称量词附加规则)nES规则规则(存在量词消去规则)nEG规则规则(存在量词附加规则)等2.5 谓词逻辑地推理理论n课堂练习本章小结n本章重点本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明 n主要概念：谓词 个体词 量词 变元前束范式 推理规则n主要方法：推理规则（US规则规则 UG规则规则 ES规则规则 EG规则）规则）n主要公式：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词，的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式