交大数理逻辑课件4-1谓词逻辑的基本概念.ppt

《交大数理逻辑课件4-1谓词逻辑的基本概念.ppt》由会员分享，可在线阅读，更多相关《交大数理逻辑课件4-1谓词逻辑的基本概念.ppt（29页珍藏版）》请在装配图网上搜索。

1、作业讲评1,第1章习题,P12：2(2)用自然语言叙述：(PQ)设P：今天很冷，Q：正在下雪(PQ)：今天不是既很冷又下雪P13：5(7)形式自然语言：如果水是清的，那么或者张三能见到池底或者他是个近视眼设P：水是清的，Q：张三能见到池底，R：张本是个近视眼P(QR)(QR)P(QR),不可兼或,第1章习题,P13：6将下公式写成波兰式和逆波兰式(1)PQRSPQRSPQRSP(WR)QPWRQ或PWRQPWRQ,第4章谓词逻辑的基本概念,4.1谓词和个体词4.2函数和谓词4.3合式公式4.4自然语句的形式化4.5有限域下公式(x)P(x)、(x)P(x)的表示法4.6公式的普遍有效性和判定问

2、题,一阶逻辑,在命题逻辑中最基本的研究对象是命题一个原子命题是不能再分割的,两个命题之间没有任何内在的联系这种研究方法显然不足以刻划世界上事物间千变万化的逻辑关系就连最古老、最简单的苏格拉底三段论也无法从命题逻辑中推出前提：凡人都是要死的p苏格拉底是人q结论：苏格拉底是要死的r,pqr,谓词演算,谓词演算(一阶谓词演算）是命题演算的扩充和发展一阶谓词演算是重要的符号逻辑系统它是程序设计理论、语义形式化及程序逻辑研究的重要基础，是程序验证、程序分析、综合及自动生成、定理证明和知识表示的有力工具。,4.1谓词和个体词,在谓词演算中，将原子命题分解为谓词和个体两部分。如：张三是人。,个体可以独立存在

3、的东西，它可以是一个具体的事物，也可以是一个抽象的概念。谓词用于刻划个体的性质和个体之间的关系,个体,谓词,个体,考察下面的三个原子命题：李玲是优秀共青团员。张华比李红高。小高坐在小王和小刘的中间。个体的分类个体常项：表示具体或特定个体的标识符如a：李玲，b：张华，c：李红，d：小高，e：小王，f：小刘个体变项：表示任意个体或泛指某类个体的标识符如：偶数、生物，用x,y,z表示个体域D个体变项的变化范围有限个体域：如a,b,c,1,2无限个体域：如N,Z,R,全总个体域:宇宙间一切事物组成（默认的个体域）,谓词,考察下面的三个原子命题：李玲是优秀共青团员。张华比李红高。小高坐在小王和小刘的中间

4、。谓词:用于刻划个体性质或各个个体的关系，常用大写英文字母表示。谓词常项：如：F:是人，则F(a)：a是人谓词变项：如：F:具有性质F，则F(x)：x具有性质F如：可用F，G，H表示上面三个命题中谓词：F：是优秀共青团员。G：比高。H：坐在和的中间。,谓词,考察下面的三个原子命题：李玲是优秀共青团员。张华比李红高。小高坐在小王和小刘的中间。如：可用F，G，H表示上面三个命题中谓词：F：是优秀共青团员。G：比高。H：坐在和的中间。谓词的分类一元谓词:刻划一个个体的性质，如谓词F(x)多元谓词:刻划两个或以上个体间的关系，如L(x,y)：x与y有关系L，L(x,y)：xy，如谓词G(x,y)、H(

5、x,y,z)0元谓词:不含个体变项的谓词,即命题常项或命题变项,F(a),G(b,c),H(d,e,f),a：李玲，b：张华，c：李红，d：小高，e：小王，f：小刘,函数它是某个体域到另一个体域的映射，由一个谓词字母和n个个体变项组成的表达式：F(x,y,z)注意：F(x,y,z)不是命题，它的真值无法确定，要想使它成为命题，必须指定某一谓词常项代替F，同时还要用n个个体常项代替n个个体变项。如：L(x,y)是一个二元谓词，它不是命题。当令L表示“小于”之后，L(x,y)还不是命题。当令a=2，b=3时，L(a,b)才是命题，并且是真命题。当令c=2，d=1时，L(c,d)为假命题。,4.2函

6、数和量词,将下列命题用谓词符号化,(1)如果23，则33，q：3y，G(x,y)：xy,命题符号化为F(2,3)G(3,4),(2)2是素数且是偶数。在命题逻辑中,设p:2是素数,q:2是偶数命题符号化为：pq,这是真命题在一阶逻辑中,设F(x)：x是素数。G(x)：x是偶数。a：2，命题符号化为：F(a)G(a),将下列命题用谓词符号化,(3)如果张明比李民高，李民比李民高，则张明比赵亮高。解：在命题逻辑中，设：p：张明比李民高，q：李民比李民高r：张明比赵亮高则命题符号为：pqr在一阶逻辑中，设H(x,y)：x比y高。a：张明；b：李民；c：赵亮，则命题符号化为：H(a,b)H(b,c)H

7、(a,c),4.2.2量词,引入量词表示个体域中所有个体或部分个体具有某种性质。全称量词:表示任意的,所有的,一切的等如:x表示对个体域中所有的xxF(x)表示个体域里的所有个体都有性质F存在量词:表示存在,有的,至少有一个等如:x表示在个体域中存在xxF(x)表示存在着个体域中的个体具有性质F,（1）每个人都有一双手。（2）有的人很聪明。,（1）每个人都有一双手。（2）有的人很聪明。第一种情况考虑个体域D为人类集合。(1)符号化为：xF(x)，其中F(x)：x都有一双手。这个命题是真命题。(2)符号化为xF(x)，其中F(x)：x很聪明。这个命题也是真命题。,在一阶逻辑中将下面命题符号化,（

8、1）每个人都有一双手。（2）有的人很聪明。第二种情况，考虑个体域D为全总个体域。引出一个新的谓词，将人分离出来:M(x)：x是人。称这个谓词为特性谓词。在全总个体域的情况下，以上两命题可叙述如下(1)对所有个体而言，如果它是人，则它有一双手。(2)存在着个体，它是人并且很聪明。则（1）符号化为x(M(x)F(x)（2）符号化为x(M(x)F(x)，,在一阶逻辑中将下面命题符号化,4.2.3约束变元和自由变元,定义在公式(x)A和(x)A中，称x为指导变元，称A为辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变元均称为是自由变元。如：在公式(x)(F(x,y)G(x,

9、z)中A=(F(x,y)G(x,z)为x的辖域，x是约束变元，y与z均为自由变元。如(x)P(x)(z)Q(x,z)(y)R(x,y)Q(x,y)在x中，x、y、z是约束变元，Q(x,y)中x，y是自由变元。闭式:不含自由变元的公式.,约束变元的换名规则,如：(x)P(x)R(x,y)(x)的辖域为P(x)，x是约束变元R(x,y)中x,y都是自由变元x既可以是约束的、又可以是自由的，容易混淆。换名规则将量词辖域中的某个约束出现的个体变项及对应的指导变项改成公式中未曾出现的个体变项符号，公式中的其余部分不变。注意：改名时一定要更改为辖域中没有出现的变元名称。例如：(x)P(x)R(x,y)改名

10、为：(z)P(z)R(x,y)或(x)P(x)R(z,y),自由变元的代入规则,代替规则对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。注意：用以代入的变项与原公式中所有变项名不能相同如：(x)F(x)G(x,y)利用代替规则：(x)F(x)G(z,y)(x)P(x)(z)Q(x,z)(y)R(x,y)Q(x,y)对Q(x,y)中自由出现的x用t代入，y用s代入则：(x)P(x)(z)Q(x,z)(y)R(x,y)Q(t,s),4.3合式公式(谓词公式),量词的作用范围：量词仅作用于个体变元，不允许作用于命题变项和谓词变项，不出现：(p)(F(x,y)p),

11、(F)(F(x,y)G(x,z)本课程中用到的符号说明：命题变项：p,q,r,pi,qi,ri,i1个体变项：x,y,z,xi,yi,zi,i1个体常项：a,b,c,ai,bi,ci,i1谓词变项：P,Q,R,Pi,Qi,Ri,i1谓词常项：GREAT,ON,函数符号：f,g,h,fi,gi,hi,i1量词符号：,联结词符号：,括号与逗号：(,),，,合式公式(谓词公式),合式公式定义如下：(1)命题常项、命题变项和原子谓词公式（不含联结词的谓词）是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式

12、公式，而x在A中是自由变元，则(x)A,(x)A也是合式公式(5)只有适合以上4条的才是合式公式.如：(x)(M(x)F(x),4.4自然语句的形式化,自然数集的形式描述对每个数，有且仅有一个相继后元解：注意到题目中没给个体域,一律用全总个体域设：谓词E(x,y)：x=y函数f(x)=x+1(表示个体x的相继后元)理解为：对每个x都存在y,y是x的相继后元，且对任一z，若它也是x的相继后元，则必有y=z形式化为：(x)(y)(E(y,f(x)(z)(E(z,f(x)E(y,z),自然语句的形式化,自然数集的形式描述没有这样的数，0是其相继后元解：注意到题目中没给个体域,一律用全总个体域设：谓词

13、E(x,y)：x=y函数f(x)=x+1(表示个体x的相继后元)理解为：不存在x，它的相继后元为0形式化为：(x)(E(0,f(x),自然语句的形式化,自然数集的形式描述对除0外的数，有且仅有一个相继前元解：注意到题目中没给个体域,一律用全总个体域设：谓词E(x,y)：x=y函数g(x)=x-1(表示个体x的相继前元)理解为：对每个x,若x0,都存在y,y是x的相继前元，且对任一z，若它也是x的相继前元，则必有y=z形式化为：(x)(E(x,0)(y)(G(y,f(x)(z)(G(z,f(x)E(y,z),在一阶逻辑中将下面命题符号化,有的自然数无先驱数。解：注意到题目中没给个体域,一律用全总

14、个体域设：F(x)：x是自然数。L(x,y)：x是y的先驱数。此命题符号为：x(F(x)y(F(y)L(y,x)解释为：存在自然数x，对任意的自然数y，y不是x的先驱数,在使用量词时，应注意以下特点,在不同个体域中，命题符号化的形式可能不一样。如“有的人很聪明。”在人类集合个体域中，xF(x)在全总个体域中，x(M(x)F(x)若事先没有给出个体域，都默认为全总个体域。在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的如“有的人很聪明。”x(M(x)F(x)如“每个人都有一双手”x(M(x)F(x),全称量词后是条件式,存在量词后是合取式,在使用量词时，应注意以下特点,个体域和谓词的

15、含义确定之后，n元命题函数要转化为命题至少需要n个量词。当个体域为有限集时，如D=a1,a2,a3,.an。对于任意谓词，都有xA(x)=A(a1)A(a2)A(an)xA(x)=A(a1)A(a2)A(an)这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。多个量词同时出现时，不能随意颠倒它们的顺序。颠倒后可能会改变原命题的含义,随意颠倒量词顺序可能会改变原命题的含义,取个体域为实数集，H（x，y）：x+5=y则xyH（x，y）表示“对任意的x，存在着y，使得x+5=y。”这是个真命题。将量词的顺序颠倒，得，yxH（x，y）表示“存在着y，对任意的x，都有x+5=y”，这是假命题。,作业5,P66:1(1)(5)(7)(10)P67:3P67:5(1)(4)(8)P67:6(1)(8),