《离散数学 第2版 教学课件 ppt 作者 尤枫 第02章 谓词逻辑》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 尤枫 第02章 谓词逻辑（84页珍藏版）》请在金锄头文库上搜索。
1、第2章 谓词逻辑,第2章 谓 词 逻 辑,2.1.1 谓词的概念和表示,第2章 谓 词 逻 辑,定义2-1 表示主体或客体（即名词）成分的词称为 个体。 定义2-2 表示一个个体性质或多个个体之间关系 的词（通常是谓语）称为谓词。表示一个 个体性质的谓词称为一元谓词，表示n个 个体之间关系的谓词称为n元谓词。,2.1.1 谓词的概念和表示,第2章 谓 词 逻 辑,谓词也有常元和变元之分，具有确定意义的谓 词称为谓词常元，意义不确定的谓词称为谓词变元， 谓词一般用大写英文字母P,Q,R等来表示。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,定义2-3 一个由n元谓词P和n个个体变元x1,
2、x2,xn 组成的符号串称为原子命题函数，表示成 P(x1,x2,xn)的形式。而由一个或多个原子 命题函数以及逻辑联结词组合而成的表达式 称为复合命题函数。统称原子命题函数和复 合命题函数为命题函数。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,定义2-4 在命题函数中，个体变元的论述范围称为 个体域或论域。 例如，令P(x)表示x2+y2=0，若x和y的个体域均为全 体正数，则对x,y的任何取值，P(x,y)为假；若x和y 的个体域均为全体实数，则除P(0,0)是一个真值为 真的命题外，其余情形均是真值为假的命题。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,在命题中除了个
3、体词和谓词外，有时还会出现一些表示数量的词，这些词称为量词。 在谓词逻辑中，量词被分为三种，其中表示“所有”、“一切”和“任意的”等数量的词称为全称量词，用符号表示；表示“存在一些”、“有一个”和“至少有一个”等数量的词称为存在量词，用符号表示；表示“存在着唯一的”和“恰有一个”等数量的词称为存在唯一量词，用符号!表示。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,【例2-1】将下列命题符号化，要求分析出量词、个 体词和谓词。 (1) 所有的大学生都会说英语。 (2) 有一些大学生会说英语。 (3) 凡自然数都是整数。 (4) 有些老虎是白色的。 (5) 存在着唯一的偶素数。,2.1.
4、2 命题函数和量词,第2章 谓 词 逻 辑,解 (1) 命题符号化为xE(x)。其中，x的个体域为全 体大学生，E(x)：x会说英语。 (2) 命题符号化为xE (x)。其中：x的个体域为全体 大学生，E (x)：x会说英语。 (3) 命题符号化为xI(x)。其中：x的个体域为自然 数集合，I(x)：x是整数。 (4) 命题符号化为xW(x)。其中：x的个体域为所有 的老虎，W(x)：x是白色的。 (5) 命题符号化为!xR(x)。其中：x的个体域为偶数 集合，R(x)：x是素数。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,定义2-5 一个命题函数中所有个体的论域组合在一 起构成的论
5、域，称为命题函数的全总论域。 有了全总论域，为深入研究命题提供了方便，一般约定，当一个命题没有指明其个体的个体域时，一般都把全总论域作为其个体域，并定义全总论域为一切事，而对每个个体变元的真正取值范围，需使用一个谓词来加以限制，这个谓词称为特性谓词。,2.1.2 命题函数和量词,第2章 谓 词 逻 辑,例如，若令S(x)：x是大学生；N(x)：x是自然数；M(x)：x是老虎；Q(x)：x是偶数，则例2-1中的五个命题可分别符号化为： (1) x(S(x)E(x) (2) x(S(x)E(x) (3) x(N(x)I(x) (4) x(M(x)W(x) (5) !x(Q(x)R(x),2.1.2
6、 命题函数和量词,第2章 谓 词 逻 辑,【例2-2】用L(x)表示“x+37”，若个体域分别为： (1) -3,-2,-1,0,1,2 (2) -5,0,3,5,6 (3) 10,15,24,30 考察命题xL(x)及xL(x)的真值。 解 当个体域取为(1)时，命题xL(x)为F，xL(x)为F； 当个体域取为(2)时，命题xL(x)为F，xL(x)为T； 当个体域取为(3)时，命题xL(x)为T，xL(x)为T。,2.2.1 谓词公式,第2章 谓 词 逻 辑,定义2-6 个体项由下列规则形成： (1) 个体常元和个体变元是个体项； (2) 若f是n元函数，且t1,t2,tn是个体项， 则
7、f(t1,t2,tn)是个体项； (3) 所有个体项均由(1)和(2)生成。,2.2.1 谓词公式,第2章 谓 词 逻 辑,有了个体项的概念，个体常元和个体变元就可 用函数的形式来表示了。 例如，令f(x,y)表示x+y，命题函数N(x)表示x是自然数，则f(1,2)表示个体常元3，而N(f(1,2)表示3是自然数。,2.2.1 谓词公式,第2章 谓 词 逻 辑,定义2-7 令P是n元谓词，t1,t2,tn是个体项， 则P(t1,t2,tn)称为原子谓词公式。 特别地，当n=0时，原子谓词公式P(t1,t2,tn)就是 命题常元或命题变元P，因此命题常元和命题变元也 是原子谓词公式。,2.2.
8、1 谓词公式,第2章 谓 词 逻 辑,定义2-8 谓词公式（简称公式）递归定义如下： (1) 原子谓词公式是谓词公式； (2) 如果A是谓词公式，则A也是谓词公式； (3) 如果A,B是谓词公式，则AB,AB,AB 和AB也是谓词公式； (4) 如果A是谓词公式，x是个体变元， 则xA和xA也是谓词公式； (5) 只有有限次使用规则(1)(4)所得到的由原子谓 词公式、逻辑联结词、量词和圆括号组成的符号 串才是谓词公式。,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,把一个用自然语言描述的命题表示成谓词公式的形式，称为谓词逻辑中命题的翻译或命题的符号化。 【例2-3】设个体域为实数
9、集合， 试将下列命题符号化。 (1) 任一实数或者是有理数，或者是无理数。 (2) 对于每个实数x都存在一个实数y，使x+y =0。 解 (1) 命题符号化为x(U(x)V(x), 其中U(x)：x是有理数，V(x)：x是无理数。 (2) 命题符号化为xyE(x,y)， 其中E(x,y)：x+y=0。,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,谓词逻辑中命题翻译一般经过如下三个步骤： (1) 找出命题中各原子命题和联结词。 (2) 分解出每个原子命题的个体、谓词和量词。 (3) 确定每个个体的个体域，若在全总论域中讨论， 给出相应的特性谓词。 (4) 按照谓词公式的表示规则将命
10、题翻译出来。,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,【例2-4】用谓词公式表示微积分中 极限定义 。 极限的定义为：对任一实数0，存在一 个实数0，使得对每一个x， 当0y，x和y的个体域均为实数集，则 f(x)=b的谓词公式表示为：,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,(P(,0) (P(,0)x(P(|x-a|,0)P(,|x-a|)P(,|f(x)-b|) 极限的这一定义也可用表示为： (0) (0)x(0|x-a|)(|f(x)-b|) 其中,和x的个体域为实数集合。 或表示为 x( 0|x-a|f(x)-b|) 其中和的个体域为正实数集合，x
11、的个体域为实数集合。,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,【例2-5】将下列命题符号化。 (1) 所有的大象都长着一个长鼻子。 (2) 并非所有的人都是勇敢的。 (3) 所有的人都喜欢某些动物， 有些人喜欢所有的动物。 (4) 有些整数能被2整除，但不能被4整除。 解 (1) 命题符号化为x(E(x)S(x)， 其中E(x)：x是大象，S(x)：x长着一个长鼻子。,2.2.2 谓词逻辑中命题的翻译,第2章 谓 词 逻 辑,(2) 命题符号化为x(M(x)B(x)或符号化为 (x)(M(x)B(x)， 其中M(x)：x是人，B(x)：x是勇敢的。 (3) 命题符号化为 x(
12、M(x)y(N(y)L(x,y)x(M(x)y(N(y)L(x,y) 其中M(x)：x是人，N(x)：x是动物，L(x,y)：x喜欢y。 (4) 命题符号化为x(I(x)D(x,2)D(x,4), 其中I(x)：x是整数，D(x,y)：x能被y整除。,2.2.3 变元的约束,第2章 谓 词 逻 辑,定义2-9 给定谓词公式A，其中形如xP(x)或 xP(x)的部分，称为谓词公式A的x约束 部分，P(x)称为相应量词或的辖域。X 在谓词公式A的x约束部分任一出现都称 为x的约束出现，并称x为约束变元。在谓 词公式中当x的出现不是约束出现时，称x 的出现是自由出现，称自由出现的变元为 自由变元。,
13、2.2.3 变元的约束,第2章 谓 词 逻 辑,【例2-6】指出下列谓词公式中各量词的辖域和 变元约束的情况。 (1) x(P(x)Q(x) (2) x(P(x)yQ(x,y,z)R(x) (3) xy(P(x,y)(Q(x)R(y) (4) x(P(x,y)Q(y)yR(x,y) (5) xP(y,z)yQ(y) 解 (1) x的辖域是P(x)Q(x)，x是约束变元。,2.2.3 变元的约束,第2章 谓 词 逻 辑,(2) x的辖域是P(x)yQ(x,y,z)，y的辖域 是Q(x,y,z)，x和y是约束变元，z是自由变元； R(x)中的x是自由变元。在整个谓词公式中，x即 是约束出现又是自由
14、出现，y为约束出现，z为自 由出现。 (3) x的辖域是y(P(x,y)(Q(x)R(y)，y的辖 域是P(x,y)(Q(x)R(y)，x和y是约束变元。 在整个谓词公式中，x和y为约束出现。,2.2.3 变元的约束,第2章 谓 词 逻 辑,(4) x的辖域为P(x,y)Q(y)，x是约束变元，y是自 由变元；y的辖域是R(x,y)，x是自由变元，y是 约束变元。在整个谓词公式中，x和y为既是自由 出现又是约束出现。 (5) x的辖域是P(y,z)，y和z是自由变元；y的辖域 是Q(y)，y是约束变元。在整个谓词公式中，z为 自由出现，y是约束出现。,2.2.3 变元的约束,第2章 谓 词 逻
15、 辑,在一个谓词公式中，个体变元即可作为自由变元，又可作为约束变元，也可同时作为自由变元和约束变元出现。为避免一个变元在一个谓词公式中既约束出现又自由出现而引起概念上的混淆，可对约束变元进行换名，使每个个体变元在一个谓词公式中只以一种形式出现，或是自由出现或是约束出现。由于一个约束变元在谓词公式中所使用的名称符号是不重要的，所以变元使用符号的更改并不改变谓词公式的含义。,2.2.3 变元的约束,第2章 谓 词 逻 辑,约束变元的换名规则： (1)对于约束变元的换名，其换名范围是量词辖域中 的某个约束出现的个体变元及相应的指导变元， 谓词公式中的其他部分不变。 (2) 换名时要换成在辖域中未曾出现的符号，最好是 谓词公式中未出现过的符号。,2.2.3 变元的约束,第2章 谓 词 逻 辑,【例2-7】对谓词公式x(P(x)Q(x,y)S(x)的约 束变元换名。 解 换名为z(P(z)Q(z,y)S(x)，是将约束变元x 换为z，S(x)中的x是自由变元，不能换名。 但不能改为 y(P(y)Q(y,y)S(x) 或 z(P(z)Q(x,y)S(x)， 因为它们改变了量词的约束范围。,2.2.3 变元的约束,第2章 谓 词 逻 辑,对于谓词公式中的自由变元，也允许换名，这 称为自由变元代入。 自由变元的代入规则： (1)对于谓词公式中的自由变元可
