离散数学第一章课件.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,绿色荧光蛋白,21世纪的显微镜,2008诺贝尔化学奖,OsamuShimomura,MartinChalfie,钱永健,一 阶 逻 辑,Predicate Logic,任 明,中国人民大学信息资源管理学院,命题：偶数都可以被2整除，6是偶数，所以6可以被2整除。,令P：偶数都可以被2整除；,Q：6是偶数；,R：6可以被2整除。,则在命题逻辑下将原问题符号化为,PQ,R。,注意该式不是重言式，这个推理（在命题逻辑下）被认为是错误的,究其原因，是命题逻辑不再对原子命题中的句子成分细分，,不考虑命题之间的内在联系和数量关系，,导致有一些逻辑问题无法解决。,本节内容,3.1 一阶逻辑基本概念,3.1.2 个体词、谓词、量词,3.1.3 一阶逻辑命题符号化,3.1.4 一阶逻辑公式与分类,3.2 一阶逻辑等值演算,3.2.1 一阶逻辑等值式与置换规则,3.2.2 一阶逻辑前束范式,基本概念,个体词,个体常项,个体变项,论域,谓词,谓词常项,谓词变项,命题函数,量词,基本概念(cont.),谓词,是用来刻画个体词的性质及个体词之间关系的词。,表示具体性质或关系的谓词称为,谓词常项,，表示抽象的、泛指的性质或关系的谓词称为,谓词变项,。,它们都用F,G,H表示。,(1)是无理数。(2)x是有理数。(3)小王与小李同岁。(4)x与y具有关系L.,基本概念,(cont.),令谓词S(x):x是大学生，括号内填入不同的人名，就得到不同的命题，故谓词S(x)相当于一个函数，称之为,命题函数,。,n,元谓词P(x,1,x,2,x,n,)可以看成是以个体域为定义域，以0,1为值域的n元函数。它不是命题，要使它成为命题，必须用谓词常项取代P，用个体常项a,i,取代x,i,，或加量词。,当n=0 时，例如F(a)，P(a,1,a,2,a,n,)，称为0元谓词。当F,P为谓词常项时，成为命题。,基本概念(cont.),将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。,例：给定简单命题函数：,A(x)：x身体好，,B(x)：x学习好，,C(x)：x工作好，,可有复合命题函数,A(x)(,B(x),C(x),基本概念(cont.),例：张华的父亲是教师。,设P(x)：表示x是教师。,a：表示张华的父亲。,则原命题符号化为：P(a)。,设f(x):表示x的父亲。,a：表示张华。,则原命题符号化为：P(f(a)。,这里，f(x)是一个个体函数。,个体函数中的个体变元用个体带入后的结果依然,是个个体,；而谓词中的个体变元用确定的客体带入后就,变成了命题,，其真值为或者为。,基本概念,(cont.),例如：有些人是大学生。,所有事物都是发展变化的。,任何一个有理数都可以用分数形式表示。,在命题中表示对客体数量化的词称为,量词,。量词可分为全称量词和存在量词两种。,基本概念,(cont.),存在量词,主合取范式,xF(x),表示存在着客体域中的客体具有性质F。,当且仅当论域中至少有一个x0使得F(x0)为T时，xF(x)为真。,xF(x),表示客体域里所有的客体都有性质F。,当且仅当对论域中所有的x来说，F(x)均为T时，xF(x)为真。,全称量词,量词后边要有一个个体变元，指明对哪个个体变元量化，称此客体变元是,量词后的指导变元,。,本节内容,3.1 一阶逻辑基本概念,3.1.2 个体词、谓词、量词,3.1.3 一阶逻辑命题符号化,3.1.4 一阶逻辑公式与分类,3.2 一阶逻辑等值演算,3.2.1 一阶逻辑等值式与置换规则,3.2.2 一阶逻辑前束范式,在谓词演算中，,命题的符号表达式与论域有关,。,例如“每个自然数都是整数”。,(1).个体域是自然数集合,N,，令 I(x)：x是整数，则命题的表达式为,xI(x),(2).个体域扩大为,全总个体域,时，上述表达式,xI(x)表示“所有客体都是整数”，显然这是假的命题，此表达式已经不能表达原命题了。因此需要添加谓词N(x)：x是自然数，用于表明x的特性，于是命题的符号表达式为,x(N(x)I(x)。这样的谓词称为,特性谓词,。,命题符号化,再如，“有些人用左手写字”。,(1).个体域是人类集合令A(x)：x用左手写字，则命题的表达式为,xA(x),(2).个体域扩大为,全总个体域,则需添加谓词S(x):x是人，于是命题的表达式为,x(S(x)A(x),思考：表示成,x(S(x)A(x)正确吗？,1.每个自然数都是整数。2.有些人用左手写字。,xI(x),x(N(x)I(x),xA(x),x(S(x)A(x),为什么要这些特性谓词？,因为需要将自然数、人从其他事物中区别出来。,3.所有大学生都喜欢一些歌星。,令S(x)：x是大学生，T(x)：x是歌星，,L(x,y)：x喜欢y。则命题的表达式为,x(S(x),y(T(y)L(x,y),4.没有不犯错误的人。,令P(x)：x是人，F(x)：x犯错误，,此命题的表达式为,x(P(x),F(x),或,x(P(x)F(x),5.不是所有的自然数都是偶数。,令N(x)：x是自然数，E(x)：x是偶数，,命题的表达式为:,x(N(x)E(x),或,x(N(x),E(x),6.每个人都有一个生母。,设 P(x):x是人。M(x,y):y是x的生母。命题可表达为,x,(P(x),y,(P(y)M(x,y),7.如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。,令A(x)：x是人，B(x,y)：y是x说的话，,C(x):x,是谎话，D(x)：x是可以相信的,命题的表达式为:,x(A(x)(,y(B(x,y)C(y),z(B(x,z)D(z),8.不管白猫黑猫，抓到老鼠就是好猫。,设C(x)：x是猫 B(x)：x是黑的,W(x)：x是白的 G(x)：x是好的,M(y)：y是老鼠 K(x,y)：x抓住y,命题的表达式为:,x(C(x),(W(x),B(x)(,y,(M(y)K(x,y)G(x),9.平面上任意两个不同的点，有且仅有一条直线通过这两点。P(x)：x是一个点L(x)：x是一条直线R(x,y,z)：z通过x和yE(x,y)：x=y,xy(P(x)P(y),E(x,y)z(L(z)R(x,y,z)u(L(u)R(x,y,u)E(z,u),10.兔子比乌龟跑得快。有的兔子比所有乌龟跑得快。,并不是所有的兔子都比乌龟跑得快。,没有跑得一样快递两只兔子。,令F(x)：x是兔子，G(y)：y是乌龟，,H(x,y):x比y跑得快，L(x,y):x和y跑得一样快,N(x,y):x和y不同,命题的表达式为:,x,y(F(x)G(y)H(x,y),x,y(F(x)G(y)H(x,y),x,y(F(x)G(y)H(x,y),x,y(F(x)F(y)L(x,y)N(x,y),几点说明,分析命题中表示性质和关系的谓词，分别符号化为1元和n元谓词；,根据命题的实际意义选用全称量词和存在量词；,多个量词同时出现时，它们的顺序不可随意调换；,有些命题的符号化形式可不仅一种。,本节内容,3.1 一阶逻辑基本概念,3.1.2 个体词、谓词、量词,3.1.3 一阶逻辑命题符号化,3.1.4 一阶逻辑公式与分类,3.2 一阶逻辑等值演算,3.2.1 一阶逻辑等值式与置换规则,3.2.2 一阶逻辑前束范式,基本概念,n元谓词P(x,1,x,2,.,x,n,),称为,原子谓词公式,。,例如 P、Q(x)、A(x,f(x)、B(x,y,a),谓词,合式公式,递归定义如下：,1.原子谓词公式是合式公式。,2.如果A是合式公式，则,A也是合式公式。,3.如果A、B是合式公式，则(AB)、(AB)、(AB)、(A,B)都是合式公式。,4.,如果A是合式公式，x是中的任何客体变元，则,x和,x也是合式公式。,5.只有有限次地应用1至4构成的符号串才是合式公式。,试判断下面哪些符号串是合式公式：,P、PQ、Q(x)P、,x(A(x)B(x)、,xC(x)、x,y,P(x)、P(,x)Q(x),x,为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。,在,xA和,xA中，称x为指导变元，A为相应量词的,辖域,。,例如，,xA(x)，,x(P(x)Q(x),yR(x,y)，,x,y,z(A(x,y)B(x,y,z)C(t)，,x(F(x,y),yP(y)Q(z),在,x和,x的辖域中，x的所有出现都是约束出现，并称x在此辖域内是,约束变元,。A中不是约束出现的其他变项均称为自由出现，称x是,自由变元,。,基本概念(cont.),对约束变元用什么符号表示无关紧要，也就是说,xA(x)与,yA(y)是一样的。,一个n元谓词P(x,1,x,2,x,n,)，若在前边添加k个量词，使其中的 k个客体变元变成约束变元，则此 n元谓词就变成了n-k元谓词。,一个谓词公式如果无自由变元，它在任何解释下都变成命题。,几点说明,谓词公式的分类,设A为一个公式，如果A在任何赋值下都是真的，则称A为,永真式,(或逻辑有效式)；如果A在任何赋值下都是假的，则称A为,矛盾式,（或永假式）；若至少存在一个赋值使A为真，则称A是,可满足式,。,由于谓词公式的复杂性和赋值的多样性，公式的可满足性是不可判断的，即，不存在一个可行的算法判断任一公式是可满足的或不可满足的。,xF(x)xF(x),xyF(x,y)xyF(x,y),个体域自然数 F(x,y)：x=y则命题为假。,若F(x,y)：xy 则命题为真。,