第七章谓词逻辑.ppt

《第七章谓词逻辑.ppt》由会员分享，可在线阅读，更多相关《第七章谓词逻辑.ppt（40页珍藏版）》请在三一文库上搜索。

1、第七章 谓词逻辑,广东工业大学计算机学院,2,为何引入谓词逻辑,只用命题无法描述所有的推理过程。 苏格拉底三段论： 所有的人都是要死的， 苏格拉底是人， 所以苏格拉底是要死的。 众所周知，这是真命题。 命题逻辑中的求解：令 P:所有的人都是要死的， Q:苏格拉底是人， R:所以苏格拉底是要死的。 在命题逻辑中，将只能用 (P Q) R 表示上述命题，无法证明(PQ)R 。 所以，这个简单而著名的论断就无法用命题逻辑予以推证。,3,为何引入谓词逻辑,命题逻辑无法精确描述苏格拉底三段论的根本原因是：P,Q,R这样的命题表示太粗略，没有把命题之间的内在联系反映出来。 要反映这种内在联系，就要对原子命

2、题作进一步的细化，分析出其中的客体、谓词、量词等，研究它们之间的形式结构及逻辑关系，这就是谓词逻辑所研究的内容。 谓词逻辑也叫一阶逻辑。,4,谓词逻辑,7.1.1 谓词与命题函数 谓词 7.1.2 量词 1. 全称量词 2. 存在量词 7.1.3 谓词合式 7.1.4 约束元与自由元 改名规则,5,1. 谓词,定义个体词（客体） 命题所陈述的对象 可以是一个具体的事物 也可以是一个抽象的概念 例如： 刘德华是香港人。 自然数集是整数集的子集。 定义谓词 刻画个体词的性质或个体词之间的关系的词 例如： “是香港人” 是谓词，表示个体词的性质： “是的子集” 是谓词，描述个体词之间的关系,6,个体

3、词的分类,定义个体常量 表示具体的或特定的个体 一般用小写字母a、b、c等表示 定义个体变元 表示抽象的或泛指的个体的词 常用小写字母x、y、z等表示 例如： x是香港人。 y是z的子集。,7,个体域（或论述域）,定义个体域 个体变元的取值范围。 可以是有限个体的集合 如：a、b、c、计算机学院的学生 也可以是无限个体的集合 如：实数集合、自然数集合 全总个体域： 宇宙间的一切事物和概念构成的集合。当没有特别声明时，将全总个体域作为个体域。,8,谓词的函数表示,谓词可用大写英文字母表示 例如： A：是香港人。 B：年轻20岁。 谓词的函数表示 用不同的个体变元取代谓词表示中要填入的个体词 例如

4、： A(x)：x是香港人。 B(x,y)：x比y年轻20岁。 这样的函数称为(简单)命题函数（原子公式）。,9,复合命题函数,复合命题函数 由简单命题函数与联结词运算后构成 举例：A(x): x有一条足够长的杠杆 B(x): x能够翘起整个地球 则A(x) B(x) 表示：如果x有一条足够长的杠杆，则x能够翘起整个地球。,10,n元谓词元数,定义 n元谓词 含有n个个体变元的谓词。 一元谓词表示个体词的性质 多元谓词反映个体词之间的关系 0元谓词是命题。 例如： A(x)：x是香港人。 (一元谓词) B(x,y)：x比y年轻20岁。(二元谓词),11,命题函数与命题,当n1，命题函数(n元谓词

5、)P(x1, , xn)不是命题，因为真值无法确定。 只有当用n 个个体词代替 x1, x2, , xn之后，才是命题。 举例： L(x,y)：表示“x小于y”的二元谓词，它的真值不能确定。 L(2,3) 是命题“2小于3”,12,命题函数的定义域和值域,命题函数的定义域（个体域）： 命题函数包含的所有个体变元的取值范围。 例如： R(x): x是大学生。 x的定义域可为：所有人/某大学的所有学生/某中学的所有学生 注意：(1)定义域不同，对命题的真值有影响。 (2)若无特殊说明，个体变元的定义域为全总个体域。 命题函数的值域： 对命题函数每种可能的赋值所生成的命题的集合。 例如： x的定义域

6、为：张三、李四 则R(x)的值域为：张三是大学生，李四是大学生,13,谓词逻辑,7.1.1 谓词与命题函数 谓词 7.1.2 量词 1. 全称量词 2. 存在量词 7.1.3 谓词合式 7.1.4 约束元与自由元 改名规则,14,量词的引入,为了用谓词表示若干个体词或全体个体词具有某种性质或具有某种关系，需要引入量词。 例如： (1) 某些人会跳舞； (2) 所有人都会跳舞；,15,量词,定义量词 表示数量的词 1.全称量词: 表示任意的,所有的,每一个，凡是 x 表示对个体域中所有的x 2.存在量词: 表示存在, 有的, 至少有一个，有些 x 表示在个体域中存在x 在x A(x)和x A(x

7、)中： 紧跟量词的x称为量词的指导变元或作用变元 A称为量词的辖域或作用域,16,量词举例,(1) 所有的鱼都生活在水中。 F(x)：x是鱼 W(x)：x生活在水中 所有的鱼都生活在水中：(x)(F(x) W(x) 。 (2) 有些人会讲粤语 M(x)：x是人 Y(x): x会讲粤语 有些人会讲粤语：(x) (M(x) Y(x)。,17,全称量词和存在量词与联结词的搭配,描述某类个体中包含的所有个体具有某种性质 与 搭配 例如：设：S(x)：x是学生。 P(x)：x通过了考试。 所有学生都通过了考试 (x)(S(x)P(x) (x)(S(x)P(x)？ 因为个体域必须是学生时，(x)(S(x)

8、P(x)才为真 某类个体中部分个体具有某种性质 与 搭配 例：有些学生通过了考试。 (x)(S(x)P(x) (x)(S(x)P(x)？ 因为只要个体域中有非学生的个体(x)(S(x)P(x)为真,18,个体域与命题的符号化,(1) 人都爱美 (2) 有人用左手写字 分别取不同的个体域集合： (a) 个体域为人类集合, (b) 个体域为全总个体域 （宇宙中的一切事物）. 解：设M(x)：x是人; F(x)：x爱美； G(x)：x用左手写字 (a) 个体域为人类集合的情况下： (1) x F(x) 或 x (M(x) F(x) (2) x G(x) 或 x (M(x) G(x) (b)个体域为全

9、总个体域的情况下： (1) x (M(x) F(x) (2) x (M(x) G(x),说明：（1）个体域不同，同一个命题符号化的结果不同。,19,量化的命题函数与命题,命题函数不是命题，但仅包含被量化的变量的命题函数是命题。 如： M(x)：x是人。 A(x)：x是聪明的。 B(x)：x要呼吸。 (1) M(x)B(x) (2) (x)(M(x)B(x) (3) M(x) A(x) (4) (x)(M(x)A(x),不是命题,是命题,不是命题,是命题,20,量词的顺序,量词顺序一般不要随便颠倒，颠倒后表示的含义可能会改变。 例： 命题：对于任一给定的实数x，都存在着一个实数y，使得x + y

10、 = 0 取个体域为实数集合， H(x, y): x + y = 0， 则命题可符号化为：xy H(x, y) y x H(x, y) 则表示： 存在着一个实数y，对于任一实数x，使得x + y = 0 x y H(x, y)是真命题，而y x H(x, y) 假命题,21,带量词的命题符号化举例（1）,请将下列命题符号化： (1) 某些实数是有理数。 (2) 没有不犯错误的人。 (3) 尽管有人聪明，但未必一切人都聪明。 解：(1) R(x)：x是实数。Q(x)：x是有理数。 (x)(R(x)Q(x) ) (2) M(x)：x是人。F(x)：x犯错误。 (x)(M(x)F(x) (3) M(

11、x)：x是人。S(x)：x聪明。 (x)(M(x)S(x) (x)(M(x)S(x),22,带量词的命题符号化举例（2）,(4) 正数都大于负数。 (5) 直线a与b平行当且仅当a与b不相交。 解： (4) 令F(x): x为正数。 G(y): y为负数。 L(x,y): x大于 y。 xy (F(x) G(y) L(x,y) (5) 令L(x): x是直线。 P(x,y): x与y平行。 G(x,y): x与y不相交, (x)(y)(L(x)L(y)(P(x,y) G(x,y),23,命题符号化举例（3）,只使用全称量词，将下列命题符号化。 某些实数是有理数，但并非所有实数都是有理数。 解：

12、原语句等价于：并非所有实数都不是有理数，并且并非所有实数都是有理数。 R(x)：x是实数。 Q(x)：x是有理数。 (x)(R(x)Q(x) (x)(R(x)Q(x),24,消去量词,当个体域为有限集时，如D=a1, a2, an，对于任意的谓词A(x)，都有： x (A(x) A(a1) A(a2) A(an) x (A(x) A(a1) A(a2) A(an) 这两个等价式称为消去量词等价式。,25,消除量词举例,设个体域D=a,b,请消除下列谓词中的量词。 (1) (x)(A(x) B(x) (2) (x)(A(x)B(x) (3) (x)(y)R(x,y) (4) (y)(x)R(x,

13、y) 解： (1) (A(a)B(a) (A(b)B(b) (2) (A(a)B(a) (A(b)B(b) (3) (x)(R(x,a) R(x,b) (R(a,a)R(a,b) (R(b,a)R(b,b) (4) (y)(R(a,y) R(b,y) (R(a,a) R(b,a) (R(a,b) R(b,b),26,量化的谓词函数的翻译例,设个体域为整数集，令 P(x, y): x + y = 1 Q(x, y): xy 0 说明下列命题的意义，并指出哪些为真命题。 (1) x y P(x, y) (2) xy Q(x, y) (3) x y (Q(x, y) P(x, y),对于任意整数x，

14、存在整数y，使得x + y = 1,存在整数x，对于任意整数y，使得xy 0,对于任意整数x，存在整数y，使得x + y = 1时当且仅当xy0,27,谓词逻辑,7.1.1 谓词与命题函数 1. 谓词 7.1.2 量词 1. 全称量词 2. 存在量词 7.1.3 谓词合式 7.1.4 约束元与自由元 改名规则,28,谓词演算的原子公式,定义原子公式 不含任何联结词和量词的简单命题函数称为原子公式。 举例： M(x)：x是人 Y(x): x会讲粤语,29,谓词合式,定义谓词合式/公式 由简单命题函数、逻辑联结词和量词组合成的谓词表达式。 合式公式的形式化定义： (1) 原子公式是合式公式； (2

15、) 若A是合式公式，则(A)是合式公式； (3) 若A、B是合式公式，则(AB)、(AB)、(AB)、(A B)是合式公式； (4) 若A是合式公式，则x A(x)、x A(x)是合式公式; (5) 只有经过有限次地应用规则(1)(4)构成的符号串才是合式公式。,30,谓词合式举例,判断下列符号串是否谓词合式 (1) x(A(x) B(x) (2) x (A(x) B(x) x C(x) (3) (x) A(x) (x) B(x) (4) (x) (y) P(x,y) 回答：(1)(2)是谓词合式。,31,谓词逻辑,7.1.1 谓词与命题函数 1. 谓词 2. 命题函数 7.1.2 量词 1.

16、 全称量词 2. 存在量词 7.1.3 谓词合式 7.1.4 约束元与自由元 改名规则,32,约束元和自由元,在谓词公式x A(x)和x A(x)中： 紧跟量词的x称为量词的指导变元或作用变元 A称为量词的辖域或作用域 辖域中x的所有出现称为约束出现， x称为约束变元 除去约束变元以外所其它变元的出现称“自由出现”，这种变元称为自由变元 举例：x(P(x) Q(y)R(y) 的辖域是P(x)Q(y)，指导变元是x。 整个公式中，x 是约束出现，受x 的约束，y是自由出现,33,约束元与自由元举例（1）,讨论下列合式公式中的约束元及自由元 2) (x P(x,y) R(y,z) y Q(y) 解

17、： 的指导变元是 ，辖域是 , (x P(x, y) R(y, z)中，是 约束出现且受x 的约束， 是自由出现。 y Q(y)中，的指导变元是 ，辖域是 ， 是约束出现。 整个公式中， 约束出现， 既有约束出现又有自由出现， 是自由出现。,x,P(x,y),x,y、z,y,Q(y),y,x,y,z,34,变元的约束讨论,从约束变元的概念可以看出，P(x1,x2, ,xn)是n元谓词，它有n个相互独立的自由变元。 若对其中k个变元进行约束，则P成为n-k元谓词。 当k = n，即谓词公式中没有自由变元出现时，则该公式就成为一个命题。 例如： x P(x,y,z)是二元谓词。 y x P(x,y

18、,z)是一元谓词。 z y x P(x,y,z)是零元谓词，即命题。,35,谓词逻辑,7.1.1 谓词与命题函数 1. 谓词 2. 命题函数 7.1.2 量词 1. 全称量词 2. 存在量词 7.1.3 谓词合式 7.1.4 约束元与自由元 改名规则,36,约束变元的改名规则,一个变元在公式中可以同时为约束变元与自由变元，因此有可能引起语义上的混乱。所以产生改名的必要性。 例如：(x P(x, y) R(y, z) y Q(y) y既是自由变元又是约束变元。 原理：一个公式的约束变元所使用的名称符号对公式所表示的意义没有影响。 (x) P(x)与(y) P(y)具有相同的意义。 (x) P(x

19、)与(y) P(y)具有相同的意义。 例如：设A(x)：x不小于0，则在实数域中(x)P(x)，(y)P(y), (z)P(z)都表示 “一切实数均不小于0”,37,约束变元的改名规则,约束变元的改名规则: 将量词辖域中出现的某个约束变元及相应的指导变元，换成一个在辖域中未曾出现过的个体变元名。公式的其余部分不变。 举例： (x P(x,y)R(y,z) )y Q(y) 用代替y Q(y)中出现的y,变成 (x P(x,y)R(y,z) )Q(),38,自由变元的代入规则,更改自由变元的符号称为自由变元的代入。 自由变元的代入规则: 对于谓词公式中出现该自由变元的每一处，都使用同一个未在公式中出现过的变元替代。 举例： (x P(x,y)R(y,z) y Q(y) 用代替(x P(x,y)R(y,z)中的y： (x P(x, )R(, z) )y Q(y),39,课堂练习：,P285: 1、4,40,作业：,P285-286: 3、5、8,