离散数学第二章谓词逻辑-2-3节.ppt

《离散数学第二章谓词逻辑-2-3节.ppt》由会员分享，可在线阅读，更多相关《离散数学第二章谓词逻辑-2-3节.ppt（40页珍藏版）》请在三一办公上搜索。

1、,2-2 命题函数与量词,一、命题函数1、命题函数客体在谓词表达式中可以是任意的名词等。单独一个谓词不是命题，只有当这个谓词后面紧跟具体客体后才是命题。例，设P表示“是大学生”，a:张三，b:老虎，c：桌子。则P(a)、P(b)和P(c)均表达了命题。P表示“是大学生”，x表示变元(客体变元)，则P(x)表示“x是大学生”,，称P(x)是命题函数，P(x)不是命题。,命题函数,命题函数分为简单命题函数与复合命题函数。定义2-2.1：简单命题函数：一个谓词，一些客体变元组成的表达式，实质是n元谓词P(x1,x2,xn)。0元谓词：命题函数P(x1,x2,xn)中n=0，表示不含有客体变元的谓词，

2、它本身就是一个命题变元。规定：若用任何具体客体去取代客体变元之后，则命题函数就变为命题。复合命题函数。将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。逻辑联结词、的意义与命题演算中的解释完全类似。n元谓词就是有n个客体变元的命题函数。,将命题函数命题的两种方法,1）将变元取定具体的值，如P(a),P(b)。2）将谓词量化。如(x)P(x),(x)P(x)。,命题函数举例,例.设S(x)表示“x学习很好”,W(x)表示“x工作很 好”,A(x)表示“x身体好”S(x)表示“x学习不是很好”,S(x)W(x)表示“x学习和工作都很好”。A(x)(S(x)W(x)表示“如

3、果x身体不好，则x的学习与工作都不会好”。S(x),W(x)是简单命题函数,而S(x),S(x)W(x),A(x)(S(x)W(x)是复合命题函数。,2、个体域(论域),命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。定义2-2.2 个体域（论域）：在命题函数中，客体变元的取值范围称为个体域（论域）。客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。例P(x):x是大学生,若x在某大学的一个班级内取,则P(x)为真。若x在某中学的一个班级内取,则P(x)为假。若x在一个剧场中的观众内取,则P(x)真假不定。,个体域(论域),个体域的给定形式有两种：（1）具体

4、给定。如：a,b,c（2）全总个体域/任意域。所有个体域的总和，即世间一切万物的主体。,3、量词：在命题中表示客体数量的词，称之为量词。,：全称量词 Anyone：存在量词 Exit,x：客体词，称为量词的指导变元,F(x)：辖域,(x)F(x)(x)F(x),有些x；至少有一个x；某一些x；存在x；等等。,所有的x；任意的x；一切的x；每一个x；等等。,读法：若xM（个体域）(x)F(x)读作：任意x属于M，有F(x)成立。(x)F(x)读作：存在一个x属于M，使得F(x)成立。,（1）所有的老虎都要吃人；（2）每一个大学生都会说英语；（3）所有的人都长着黑头发；（4）有一些人登上过月球；（

5、5）有一些自然数是素数。,例 存在一个人。M(x):x是人。(x)M(x),(x)P(x)x 老虎(x)Q(x)x大学生(x)R(x)x人(x)S(x)x人(x)T(x)x自然数。,P(x)：x会吃人则有：所有的x，P(x)x 老虎Q(x)：x会说英语则有：每一个x，Q(x)x大学生R(x)：x长着黑头发则有：所有的x，R(x)x人S(x)：x登上过月球则有：有一些x，S(x)x人T(x)：x是素数则有：有一些x，T(x)x自然数,不便之处,从书写上十分不便，总要特别注明个体域；无法清晰表达不同的个体域：在同一个比较复杂的句子中，对于不同命题函数中的客体可能属于不同的个体域，此时无法清晰表达；

6、如例(1)和(4)的合取(x)P(x)(x)R(x),x人,x老虎,（1）所有的老虎都要吃人；(x)P(x)（4）有一些人登上过月球；(x)R(x),不便之处(续),若个体域的注明不清楚，将造成无法确定其真值。即对于同一个n元谓词，不同的个体域有可能带来不同的真值。例如 对于语句“(x)(x+6=5)”可表示为：“有一些x，使得x+6=5”。该语句在下面两种个体域下有不同的真值：(1)在实数范围内时，确有x=-1使得x+6=5，因此，(x)(x+6=5)为“真”；(2)在正整数范围内时，则找不到任何x，使得x+6=5为“真”，所以，(x)(x+6=5)为“假”。,不便之处的根源,因为需要额外特

7、别标注出每个谓词的个体域所致！,所有的老虎都要吃人。(x)P(x),x 老虎,用谓词指出客体变元的取值范围。,特性谓词,新的问题出现了，U(x)如何与(x)P(x)结合才符合逻辑呢？,所有的老虎都要吃人；(x)P(x)x 老虎,用来限定客体变元的取值范围。,特性谓词的例子,例，符号化“所有的老虎都要吃人”这个命题。,含义：“对于任意的x（全总论域），如果x是老虎，则x会吃人。若P(x)：x会吃人。U(x)：x是老虎。则符号化的正确形式应该是(x)(U(x)P(x),若符号化为(x)(U(x)P(x)它的含义是：“对于任意的x，x是老虎，并且x会吃人”，与原命题“所有的老虎都要吃人”的逻辑含义不

8、符。,P,U,P包含U(x)(U(x)P(x),特性谓词的例子（续）,有一些大学生吸烟。它的含义是：“存在一些x,x是大学生，且x吸烟”，S(x)：x吸烟。U(x)：x是大学生。则符号化的正确形式应该是(x)（U(x)S(x),若符号化为(x)(U(x)P(x)它的含义是：“存在一些x,若x是大学生，则x吸烟”，与原命题“有些大学生吸烟”的逻辑含义不符。,U,S,(x)(U(x)S(x),（2）每一个大学生都会说英语；无特性谓词：Q(x):x会说英语。(x)Q(x)x大学生（3）有一些自然数是素数。无特性谓词：T(x)：x是素数。(x)T(x)x自然数,例,Q(x):x会说英语。U(x):x是

9、大学生。(x)(U(x)Q(x)T(x)：x是素数。U(x)：x是自然数。(x)(U(x)T(x),谓词逻辑符号化的两条规则,统一个体域为全总个体域，而对每一个句子中客体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：,（1）对于全称量词(x)，刻划其对应个体域的特性谓词作为条件式之前件加入。,（2）对于存在量词(x)，刻划其对应个体域的特性谓词作为合取式之合取项加入。,带量词的公式在论域内的展开式,个体域有限时,去掉量词公式，当个体域有限时，如个体域D=a1,，an，由量词意义可知，对任意A(x)，都有:1.(x)A(x)A(a1)A(a2).A(an)

10、2.(x)B(x)B(a1)B(a2).B(an),作业,59页(1),(2),2-3 谓词公式及命题符号化,命题逻辑中有命题公式，类似地，在谓词逻辑中，要研究由简单命题函数与逻辑联结词组合成的谓词公式。要求：对自然语言与逻辑语言能进行翻译。重点：用谓词公式表达自然语言中的命题。,谓词公式涉及的符号（共七种）：,（1）联结词：、。（2）量词：、。（3）括号、逗号：逗号用以区分客体。,谓词公式涉及的符号（共七种）：,（4）客体常量符号：用带或不带下标的小写英文字母a,b,c,a1,b1,c1,来表示。当个体域名称集合D给出时，它可以是D中的某个元素；（5）客体变量符号：用带或不带下标的小写英文字

11、母x,y,z,.,x1,y1,z1,.来表示。当个体域名称集合D给出时，它可以是D中的任意元素；（6）谓词符号：用带或不带下标的大写英文字母P,Q,R,.,P1,Q1,R1.来表示。当个体域名称集合D给出时，n元谓词符号P(x1,x2,xn)可以是任意一个谓词。（7）客体函数符号：用带或不带下标的小写英文字母f,g,h,.,f1,g1,h1,.来表示。当个体域名称集合D给出时，n元函数符号f(x1,x2,xn)可以是DnD的任意一个函数；,描述客体之间的关系。,为何需要客体函数符号？,例如 符号化“小王比他的父亲高”：T(x，y)：x比y高a：小王b：小王的父亲T(a，b)解决方法：定义体现客

12、体与客体关系的函数。f(x)=x的父亲T(a，f(a),个体域：人,无法显示客体之间的依赖关系,注意：客体函数刻划了客体与客体之间的关系，不单独使用，要嵌入在谓词中。,函数的使用给谓词逻辑中的客体词表示带来了很大的方便。,客体函数与谓词的区别客体函数中的客体变元用客体带入后的结果依然是客体。f(a)=小王的父亲谓词中的个体变元用确定的个体带入后就变成了命题。其真值为或者为。M(x)：x是人M(a)：小王是人函词是个体域到个体域的映射f:DD谓词是从个体域到T,F的映射M:D T,F,例，用谓词表示命题：,对任意整数x，x2-1=(x+1)(x-1)。令I(x):x是整数,E(x,y):x=y,

13、f(x)=x2-1,g(x)=(x+1)(x-1),则该命题符号化为:(x)(I(x)E(f(x),g(x),合式公式,一、谓词演算的原子公式定义2-3.1：称n元谓词P(x1,x2,.,xn)为原子谓词公式，简称原子公式。即不出现命题联结词和量词。例如 P、Q(x)、A(x,f(x),a)都是谓词演算的原子公式。二、谓词演算的合式公式(WFF)(Well Formed formulas)定义2-3.2：谓词合式公式递归定义如下：(1)原子谓词公式是合式公式。(2)如果A、B是合式公式，则A、(AB)、(AB)、(AB)、(AB)都是合式公式。(3)如果A是合式公式，x是客体变元，则(x)和(

14、x)A也是合式公式。(4)只有有限次地按规则(1)-(3)求得的公式才是合式公式。谓词合式公式也叫谓词公式，简称公式。,合式公式判断,下面都是合式公式：P、(PQ)、(Q(x)P)、(x)(A(x)B(x)、(x)C(x)而下面都不是合式公式：x(y)P(x)、P(x)Q(x)(x)为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。注意：公式(x)(A(x)B(x)中(x)后边的括号不是最外层括号，所以不可以省略。,谓词逻辑的翻译,把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化。符号化的步骤如下：(1)正确理解给定命题：必要时把命题改叙，使每个原子命题及

15、原子命题之间的关系能明显表达出来。(2)分析原子命题：把每个原子命题分解成客体、谓词和量词，在全总论域中讨论时，要给出特性谓词。注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。多个量词出现时，顺序不可随意调换。(3)用恰当的联结词把给定命题表示出来。注意：符号化形式不唯一。,例 谓词逻辑符号化,（1）没有人登上过木星。设M(x)：x登上过木星；H(x)：x是人(x)(H(x)M(x)或者(x)(H(x)M(x)；（2）在美国留学的学生未必都是亚洲人 设A(x)：x是亚洲人 H(x)：x是在美国留学的学生，则：(x)(H(x)A(x)或者(x)(H(x)A(x)；,例 谓词逻辑符号化,(

16、3)没有不犯错误的人(没有人不犯错误）设F(x)：x是犯错误的。M(x)：x是人。则(x)(M(x)F(x)(x)(M(x)F(x),例 谓词逻辑符号化,（4）天下乌鸦一般黑设 G(x,y)：x与y一般黑F(x)：x是乌鸦；(x)(y)(F(x)F(y)G(x,y)或者(x)(y)(F(x)F(y)G(x,y)（5）每个实数都存在比它大的实数设L(x,y)：x小于y R(x)：x是实数；(x)(R(x)(y)(R(y)L(x,y),例 谓词逻辑符号化,（6）对于任意给定的0，必存在着0，使得对任意的x，只要|x-a|0)()(0)(x)(|x-a|)(|f(x)-f(a)|),例 谓词逻辑符号

17、化,（7）不管黑猫白猫,抓住老鼠就是好猫。设 K(x,y):x抓住y,G(x):x是好的,C(x):x是猫,B(x):x黑的 W(x):x是白的,M(x):x是老鼠,则原命题符号化为:,(C(x)M(y)K(x,y)G(x),(B(x)W(x),(x)(y),例 谓词逻辑符号化,（8）每个自然数都有唯一的后继数。（每个自然数都有后继数且是唯一的）。设 A(x,y)：y是x的后继数，E(x,y)：x=y N(x)：x是自然数，自然数x都有后继数y 唯一的则命题的表达式为,(x)(N(x)(y)(N(y)A(x,y)(z)(N(z)A(x,z)E(y,z),A(x,y),(y)(N(y),(z)(

18、N(z),A(x,z)E(y,z),思考,每个人都有一个生母。设 P(x):x是个人。M(x,y):y是x的生母。,例 谓词逻辑符号化,（9）如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。设C(x):x是谎话，B(x,y)：y是x说的话 D(x)：x是可以相信的 A(x)：x是人，一个人x只是说谎话(y)(B(x,y)C(y)他所说的每句话没有一句是可以相信的。(z)(B(x,z)D(z)或(z)(B(x,z)D(z)命题的表达式为:(x)(A(x)(y)(B(x,y)C(y)(z)(B(x,z)D(z),例 将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑

19、得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。,解：令 H(x,y):x比y跑得快。L(x,y):x与y跑得同样快。F(x):x是兔子，G(y):y是乌龟。（1）(x)(y)(F(x)G(y)H(x,y)（2）(x)(F(x)(y)(G(y)H(x,y)（3）(x)(y)(F(x)G(y)H(x,y)（4）(x)(y)(F(x)F(y)L(x,y),谓词翻译难点,一元谓词用以描述某一个客体的某种特性，而n元谓词则用以描述n个客体之间的关系；如有多个量词，则读的顺序按从左到右的顺序；另外，量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值，

20、此时对多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原有的含义。,谓词翻译难点（续）,3.根据命题的实际意义，选用全称量词或存在量词。全称量词加入时，其刻划个体域的特性谓词将以条件式的前件加入，存在量词加入时，其刻划个体域的特性谓词将以合取项加入；有时给定命题中有些量词没有明确给出，要仔细分析并写出这隐含的量词。4.如果量词前有否定符号，如“没有.”“不是所有的.”等，可以按照字面直译。如“(x)”“(x).”。5.有些命题在进行符号化时，由于语言叙述不同，可能翻译不同，但它们表示的意思是相同的，即句子符号化形式可不止一种。,(x)(S(x)O(x),例,符号化下述一组语句：只要是需要室外活动的课，郝亮都喜欢；所有的公共体育课都是需要室外活动的课；篮球是一门公共体育课；郝亮喜欢篮球这门课。解：设 O(x)：表示x是需要室外活动的课；L(x,y)：表示x喜欢y；S(x)：表示x是一门公共体育课；Hao：表示郝亮；Ball：表示篮球。,S(ball),L(Hao,Ball),(x)(O(x)L(Hao,x),作业,62页(2),(3)b),c),(5)b)(6),