《离散数学课件第二章谓词逻辑-1》由会员分享，可在线阅读，更多相关《离散数学课件第二章谓词逻辑-1（49页珍藏版）》请在金锄头文库上搜索。
1、第二章 谓词逻辑,在命题逻辑中，命题是最基本的单位，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。考虑下面的推理: 凡偶数都能被2整除； 6是偶数。 所以，6能被2整除。 这个推理是我们公认的数学推理中的真命题，但是在命题逻辑中却无法判断它的正确性。,因为在命题逻辑中只能将推理中出现的三个简单命题依次符号化为p，q，r，将推理的形式结构符号化为(pq)r。由于上式不是重言式，所以不能由它判断推理的正确性。,为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词，谓词和量词，以期达到表达出个体与总体的内在联系和数
2、量关系，这就是本章所研究的内容。,本章内容,2-1 谓词的概念与表示,命题是具有真假意义的陈述句，从语法上分析，一个陈述句由主语和谓语两部分组成。 设 ：是计算机系的学生 则： P(陈华)表示“陈华是计算机系的学生”； P(张强)表示“张强是计算机系的学生”,定义,谓词(predicate)：用来刻划一个个体的性质或多个个体之间关系的词，相当于句子中的谓语。常用大写字母P, Q, R来表示。 客体：可以独立存在的事物称为客体。 客体的取值范围称为个体域(或论域)，常用D表示。 宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域(Universal Individual Field)。 n
3、元谓词：含有n个变元。,例如： F(x): x是人。 G(x,y): x与y是兄弟。 F(x)是一元谓词， G(x,y)是二元谓词。 一元谓词表达了个体的“性质”, 而多元谓词表达了个体之间的“关系”。,例： 将下列命题符号化： (1) 熊猫是动物。 (2) 上海位于南京与杭州之间。 (3) 2是偶数且是素数。,解： (1) 设 P(x): x是动物, x动物，b: 熊猫，b是个体常元, 则命题可符号化为P(b)或P(熊猫)。 (2) P(x, y, z): x位于y与z之间。a: 上海, b: 南京, c: 杭州, 则命题可符号化为P(a, b, c)或符号化为P(上海, 南京, 杭州)。
4、(3) P(x): x是偶数, Q(x): x是素数, a: 2, 则命题可符号化为P(a)Q(a) 或 P(2)Q(2)。,一般地, 一个由n个个体和n元谓词所组成的命题可表示为P(a1, a2, , an), 其中P表示n元谓词, a1, a2, an 分别表示n个个体。 a1, a2,an 的排列次序通常是重要的。 B(a, b, c)不同于B(b, a, c)。,2-2 命题函数与量词,将下面表示（Socrates 三段论）符号化： 所有的人总是要死的。 Socrates是人。 所以Socrates是要死的。 设：H(x):x是人 M(x):x是要死的 则前提：H(x)M(x) H(S
5、ocrates) 结论：M(Socrates) 需证: (H(x)M(x)H(Socrates)M(Socrates),有了个体词和谓词之后，有些命题还是不能准确的符号化，原因是还缺少表示个体常项或变项之间数量关系的词。称表示个体常项或变项之间数量关系的词为量词。 全称(universal)量词: “所有的”,“全部的”,“任意的”,“每一个”, 存在(existential)量词: “有一些的”,“某些的”,“至少有一个”,“存在”,例：F(x)：x是不怕死的 D(x)：x是要死的 M(x)：x是人 若论述域是全人类： 则:人总是要死的 可译为 （x）D(x) 有些人不怕死 可译为 （x）F
6、(x) 若论述域不是全人类： 则:人总是要死的 可译为 (x)(M(x)D(x) 有些人不怕死 可译为 (x)(M(x) F(x)）,谓词逻辑符号化的两条规则,若个体域为全总个体域，而对每一个句子中个体变量的变化范围必须用一元特性谓词刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：,（1）对于全称量词(x)，刻划其对应个体域的特性谓词作为蕴涵式之前件加入。,（2）对于存在量词(x)，刻划其对应个体域的特性谓词作为合取式之合取项加入。,特性谓词的例子,为什么要这样规定特性谓词加入的原则呢？若不遵循会出现什么样的问题？,例如，符号化“所有的老虎都要吃人”这个命题,若P(x)：x会吃人 U
7、(x)：x是老虎 则符号化的正确形式应该是 (x)(U(x)P(x) 它的含义是：“对于任意的x,如果x是老虎，则x会吃人”，符合原命题的逻辑含义。,若符号化为 (x)(U(x)P(x) 它的含义是：“对于任意的x,x是老虎，并且x会吃人”，与原命题“所有的老虎都要吃人”的逻辑含义不符。,特性谓词举例,例：每一个被2整除的整数都是偶数，并且至少有一个整数不是偶数。,解：设 I(x):x是整数 Q(x,y):x整除y O(x):x是偶数 (x)(I(x)Q(2,x)O(x)(x)(I(x)O(x),2-3 谓词公式与翻译,谓词公式中的符号约定： （1）常量符号：用带或不带下标的小写英文字母a,
8、b, c, , a1, b1, c1, 来表示。当个体域名称集合D给出时，它可以是D中的某个元素； （2）变量符号：用带或不带下标的小写英文字母x, y, z, ., x1, y1, z1,.来表示。当个体域名称集合D给出时，它可以是D中的任意元素； （3）谓词符号：用带或不带下标的大写英文字母P, Q, R,., P1, Q1, R1.来表示。,谓词公式的定义,原子公式：形如 A(x1,x2,xn)的公式 定义2-3.1满足下列条件的表达式，称为合式公式(Wff)，简称公式(Formulae)。 （1）原子公式是合式公式； （2）若G，H是合式公式，则 (G)、(H)、(GH)、(GH)、(
9、GH)、(GH) 也是合式公式； （3）若G是合式公式，x是个体变量，则 (x)G、(x)G 也是合式公式； （4）仅仅由(1)-(3)产生的表达式才是合式公式。,命题符号化举例,例: “存在最小的自然数”。 解1: 设: F(x): x是自然数; G(x,y): x=y; 原命题符号化成: (x)(F(x)(y)(F(y)G(x,y) 解2: 采用全体自然数作为个体域. 设: G(x,y): x=y; 原命题符号化成: (x)(y)G(x,y),命题符号化举例(续),例: “不存在最大的自然数”。 解: 设: F(x): x是自然数; G(x,y): xy; 原命题符号化成: (x)(F(x
10、)(y)(F(y)G(y,x) 或: (x)(F(x)(y)(F(y)G(x,y),命题符号化举例(续),例: “所有的火车比所有的汽车快”。 解: 设: F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 原命题符号化成: (x)(F(x)(y)(G(y)H(x,y) 或: (x)(y)(F(x)G(y)H(x,y),命题符号化举例(续),例: “有的汽车比有的火车快”。 解: 设: F(x): x是汽车; G(x): x是火车; H(x,y): x比y快 原命题符号化成: (x)(F(x)(y)(G(y)H(x,y) 或: (x)(y)(F(x)G(y)H(x,y),
11、命题符号化举例(续),例: “有些病人相信所有的医生”。 解: 设: F(x): x是病人; G(x): x是医生; H(x,y): x相信y 原命题符号化成: (x)(F(x)(y)(G(y)H(x,y),2-4 变元的约束,定义:量词的辖域（作用域）是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两端有括号。,量词辖域的确定方法： （1）若量词后有括号，则括号内的子公式就是该量词的辖域； （2）若量词后无括号，则与量词邻接的子公式为该量词的辖域。,约束变元和自由变元,定义：在量词(x)，(x)辖域内变元x的一切出现叫约束出现，称这样的x为约束变元。 变元的非约束出现称
12、为自由出现,称这样的变元为自由变元。,变元的约束举例,例：指出下列谓词公式中的自由变元和约束变元,并指明量词的辖域。 (x)(P(x) R(x) )(x)P(x) Q(x),解：表达式中的(x)(P(x)R(x)中x的辖域是P(x)R(x),其中的x是约束变元, 表达式(x)P(x)Q(x)中x的辖域是P(x)， P(x)中的x是约束变元，Q(x)中的x是自由变元。,在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可用改名规则对变元改名。,变元改名规则,约束变元的改名规则： 1.若要改名，则该变元在量词及该量词的辖域中的所有出现须一起更改。 2.改名时所选用变元必须是量词辖域内
13、未出现的，最好是公式中未出现的。,自由变元的代入规则： 1.将公式中出现该自由变元的每一处都用新的个体变元替换。 2.新变元不允许在原公式中以任何约束形式出现。,变元改名举例,例1：(x)(P(x，y)(y)R(x，y) ) 可改为 (x)(P(x，y)(z)R(x，z) 例2：(x)P(x) Q(x) 可改为 (y)P(y) Q(x) 例3：(x)(A(x)B(x，y)C(x)D(w) 可改为： (x)(A(x)B(x，y)C(z) D(w) 注意： (Z)(A(Z)B(Z，y)C(x) D(W)不可改为： (y)(A(y)B(y，y)C(x) D(W),量词和命题的关系,1.若论域是有限的
14、，设论域是1， 2，N 则(x)P(x) P(1) P(2) P(N) (x)P(x) P(1) P(2) P(N) 2.若论域是可数无限,设论域是1， 2，N 则(x)P(x) 为P(1) P(2) P(N) (x)P(x) 为P(1) P(2) P(N) ,2-5 谓词演算的等价式与蕴含式,定义2-5.2，2-5.3，2-5.4 （1）公式G称为有效公式（或永真公式），如果G在它所有的赋值下都为“真”。 （2）公式G称为矛盾公式（或不可满足的），如果G在它所有的赋值下都为“假”。 （3）公式G称为可满足公式，如果至少有一种赋值使得G取值为“真”。,公式之间的关系,从上述定义可知三种特殊公式
15、之间的关系： （1）有效公式G的否定G为矛盾公式；矛盾公式G的否定G为有效公式。 （2）有效公式一定为可满足公式。,例：设 A（x） P（x）(x)P（x）, 论域为3，4， P（x）：x是质数。 判定A（x）是否为永真。,解： x P（x） (x)P（x） - 3 1 1 1 4 0 1 0 从真值表可看出，A(x)不是永真式。 注:一般用真值表难以判定谓词公式是否为真;必须使用推导方法。,谓词合式公式的基本等价关系,定义2-5.1 任何两个谓词公式A、B，设他们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值相同，则称A和B在E上是等价的(Equivalent)，记为A = B。,等价的另一定义 设A，B是一阶逻辑中任意两个公式，若A B是永真式，则称A与B是等价（或等值）的。记做A B（或A=B），称A B是等价式（等值式）。,命题演算公式的推广,命题演算中的等价式和蕴含式都可推广到谓词演算中使用。 例：(x)P(x)(x)P(x) F (x)P(x)(x)Q(x) (x)P(x)
