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

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学

3、习和工作都很好”。 A(x)(S(x)W(x) 表示“如果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在一个剧场中的

4、观众内取,则P(x)真假不定。,个体域 (论域),个体域的给定形式有两种： （1）具体给定。 如：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)

5、成立。,（1）所有的老虎都要吃人； （2）每一个大学生都会说英语； （3）所有的人都长着黑头发； （4）有一些人登上过月球； （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，

6、T(x) x自然数,不便之处,从书写上十分不便，总要特别注明个体域； 无法清晰表达不同的个体域：在同一个比较复杂的句子中，对于不同命题函数中的客体可能属于不同的个体域，此时无法清晰表达； 如例 (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”。 该语句在下面两种个体域下有不同的真值

7、： (1)在实数范围内时，确有x=-1使得x+6=5，因此， (x) (x+6 = 5)为“真”； (2)在正整数范围内时，则找不到任何x，使得x+6=5为“真”，所以，(x)(x+6=5)为“假”。,不便之处的根源,因为需要额外特别标注出每个谓词的个体域所致！,所有的老虎都要吃人。 (x)P(x),x 老虎,用谓词指出客体变元的 取值范围。,特性谓词,新的问题出现了，U(x)如何与(x)P(x)结合才符合逻辑呢？,所有的老虎都要吃人； (x)P(x) x 老虎,用来限定客体变元的取值范围。,特性谓词的例子,例，符号化“所有的老虎都要吃人”这个命题。,含义：“对于任意的x（全总论域），如果x是

8、老虎，则x会吃人。 若P(x)：x会吃人。 U(x)：x是老虎。 则符号化的正确形式应该是 (x)(U(x)P(x),若符号化为 (x)(U(x)P(x) 它的含义是： “对于任意的x，x是老虎，并且x会吃人”， 与原命题“所有的老虎都要吃人”的逻辑含义不符。,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吸烟”，与原命

9、题“有些大学生吸烟”的逻辑含义不符。,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是大学生。 (x) (U(x) Q(x) T(x)：x是素数。U(x)：x是自然数。 (x)(U(x) T(x),谓词逻辑符号化的两条规则,统一个体域为全总个体域，而对每一个句子中客体变量的变化范围用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：,（1）对于全称量词 (x)，刻划其对

10、应个体域的特性谓词作为条件式之前件加入。,（2）对于存在量词(x) ，刻划其对应个体域的特性谓词作为合取式之合取项加入。,带量词的公式在论域内的展开式,个体域有限时,去掉量词公式，当个体域有限时，如个体域D=a1,，an，由量词意义可知，对任意A(x)，都有: 1. (x) A(x)A(a1)A(a2).A(an) 2. (x) B(x)B(a1)B(a2).B(an),作业,59页 (1), (2),2-3 谓词公式及命题符号化,命题逻辑中有命题公式，类似地，在谓词逻辑中，要研究由简单命题函数与逻辑联结词组合成的谓词公式。 要求：对自然语言与逻辑语言能进行翻译。 重点：用谓词公式表达自然语言

11、中的命题。,谓词公式涉及的符号（共七种）：,（1）联结词： 、 、 、 、 。 （2）量词：、。 （3）括号、逗号：逗号用以区分客体。,谓词公式涉及的符号（共七种）：,（4）客体常量符号：用带或不带下标的小写英文字母a, b,c,a1,b1,c1,来表示。当个体域名称集合D给出时，它可以是D中的某个元素； （5）客体变量符号：用带或不带下标的小写英文字母x, y,z,.,x1,y1,z1,.来表示。当个体域名称集合D给出时，它可以是D中的任意元素； （6）谓词符号：用带或不带下标的大写英文字母P, Q,R,.,P1,Q1,R1.来表示。当个体域名称集合D给出时，n元谓词符号P(x1,x2,xn

12、)可以是任意一个谓词。 （7）客体函数符号：用带或不带下标的小写英文字母f,g,h,.,f1,g1,h1,.来表示。当个体域名称集合D给出时，n元函数符号f(x1,x2,xn)可以是DnD的任意一个函数；,描述客体之间的关系。,为何需要客体函数符号？,例如 符号化“小王比他的父亲高”： T(x，y)：x比y高 a：小王 b：小王的父亲 T(a，b) 解决方法：定义体现客体与客体关系的函数。 f(x)=x的父亲 T(a， f(a),个体域：人,无法显示客体之间的依赖关系,注意：客体函数刻划了客体与客体之间的关系，不单独使用，要嵌入在谓词中。,函数的使用给谓词逻辑中的客体词表示带来了很大的方便。,

13、客体函数与谓词的区别 客体函数中的客体变元用客体带入后的结果依然是客体。 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, f(x)=x2-1, g(x)=(x+1)(x-1), 则该命题符号化为: (x)(I(x)E(f(x),g(x),合式公式,一、谓词演算的原子公式 定义2-3.1 ：称n元谓词P(x

14、1,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)和(x)A也是合式公式。 (4)只有有限次地按规则(1)-(3)求得的公式才是合式公式。 谓词合式公式也叫谓词公式，简称公式。,合式公式判断,下面都是合式公式：

15、 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)正确理解给定命题： 必要时把命题改叙，使每个原子命题及原子命题之间的关系能明显表达出来。 (2)分析原子命题： 把每个原子命题分解成客体、谓词和量词，在全总论域中讨论时，要给出特性谓词。

16、注意全称量词(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)；,例 谓词逻辑符号化,(3) 没有不犯错误的人 (没有人不犯错误） 设F(x)：x是犯错误的。 M(x)：x是人。 则(x)(M(

17、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)|),例 谓词逻辑符号化,（7）不管黑猫白猫, 抓住老鼠就是好猫。 设 K(x, y):

18、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)(N(z) ) ),A

19、(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）有的兔子比所有的乌龟跑得快。（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