第七章谓词逻辑ppt课件

1、离散数学离散数学第七章第七章 谓词逻辑谓词逻辑广东工业大学计算机学院广东工业大学计算机学院为何引入谓词逻辑v 只用命题无法描画一切的推理过程。只用命题无法描画一切的推理过程。v 苏格拉底三段论：苏格拉底三段论：v 一切的人都是要死的，一切的人都是要死的，v 苏格拉底是人，苏格拉底是人，v 所以苏格拉底是要死的。所以苏格拉底是要死的。v 众所周知，这是真命题。众所周知，这是真命题。v 命题逻辑中的求解：令命题逻辑中的求解：令v P:P:一切的人都是要死的，一切的人都是要死的，v Q:Q:苏格拉底是人，苏格拉底是人，v R:R:所以苏格拉底是要死的。所以苏格拉底是要死的。v 在命题逻辑中，将只能用

2、在命题逻辑中，将只能用 (P Q) (P Q) R R 表示上述命题，无表示上述命题，无法证明法证明(PQ)(PQ)R R 。v 所以，这个简单而著名的结论就无法用命题逻辑予以推证。所以，这个简单而著名的结论就无法用命题逻辑予以推证。为何引入谓词逻辑v命题逻辑无法准确描画苏格拉底三段论的根本命题逻辑无法准确描画苏格拉底三段论的根本缘由是：缘由是：P,Q,RP,Q,R这样的命题表示太粗略，没有这样的命题表示太粗略，没有把命题之间的内在联络反映出来。把命题之间的内在联络反映出来。v要反映这种内在联络，就要对原子命题作进一要反映这种内在联络，就要对原子命题作进一步的细化，分析出其中的客体、谓词、量词

3、等，步的细化，分析出其中的客体、谓词、量词等，研讨它们之间的方式构造及逻辑关系，这就是研讨它们之间的方式构造及逻辑关系，这就是谓词逻辑所研讨的内容。谓词逻辑所研讨的内容。v谓词逻辑也叫一阶逻辑。谓词逻辑也叫一阶逻辑。谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数v 谓词谓词v7.1.2 7.1.2 量词量词v1. 1. 全称量词全称量词v2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自在元约束元与自在元v改名规那么改名规那么1. 谓词谓词v 定义定义 个体词客体个体词客体v 命题所陈说的对象命题所陈说的对象v

4、可以是一个详细的事物可以是一个详细的事物v 也可以是一个笼统的概念也可以是一个笼统的概念v 例如：例如：v 刘德华是香港人。刘德华是香港人。v 自然数集是整数集的子集。自然数集是整数集的子集。v 定义定义 谓词谓词v 描写个体词的性质或个体词之间的关系的词描写个体词的性质或个体词之间的关系的词v 例如：例如：v “ “是香港人是香港人 是谓词，表示个体词的性质：是谓词，表示个体词的性质：v “ “是是的子集的子集 是谓词，描画个体词之间的关系是谓词，描画个体词之间的关系个体词的分类个体词的分类v 定义定义 个体常量个体常量v表示详细的或特定的个体表示详细的或特定的个体v普通用小写字母普通用小写

5、字母a a、b b、c c等表示等表示v 定义定义 个体变元个体变元v表示笼统的或泛指的个体的词表示笼统的或泛指的个体的词v常用小写字母常用小写字母x x、y y、z z等表示等表示v例如：例如：v x x是香港人。是香港人。v y y是是z z的子集。的子集。个体域或论述域个体域或论述域v 定义定义 个体域个体域v 个体变元的取值范围。个体变元的取值范围。v可以是有限个体的集合可以是有限个体的集合v如：如：aa、b b、cc、 计算机学院的学生计算机学院的学生 v也可以是无限个体的集合也可以是无限个体的集合v如：实数集合、自然数集合如：实数集合、自然数集合v全总个体域：全总个体域：v宇宙间的

6、一切事物和概念构成的集合。当没宇宙间的一切事物和概念构成的集合。当没有特别声明时，将全总个体域作为个体域。有特别声明时，将全总个体域作为个体域。谓词的函数表示谓词的函数表示v谓词可用大写英文字母表示谓词可用大写英文字母表示v 例如：例如：v A A：是香港人。：是香港人。v B B：年轻：年轻2020岁。岁。v v谓词的函数表示谓词的函数表示v用不同的个体变元取代谓词表示中要填入的个体词用不同的个体变元取代谓词表示中要填入的个体词v 例如：例如：v A(x) A(x)：x x是香港人。是香港人。v B(x,y) B(x,y)：x x比比y y年轻年轻2020岁。岁。v这样的函数称为这样的函数称

7、为( (简单简单) )命题函数原子公式。命题函数原子公式。复合命题函数复合命题函数 复合命题函数复合命题函数 由简单命题函数与结合词运算后构成由简单命题函数与结合词运算后构成举例：举例：A(x): xA(x): x有一条足够长的杠杆有一条足够长的杠杆 B(x): x B(x): x可以翘起整个地球可以翘起整个地球 那么那么A(x)A(x) B(x) B(x) 表示：假设表示：假设x x有一条足够长的杠有一条足够长的杠杆，那么杆，那么x x可以翘起整个地球。可以翘起整个地球。n n元谓词元数元谓词元数定义定义 n元谓词元谓词含有含有n个个体变元的谓词。个个体变元的谓词。一元谓词表示个体词的性质一

8、元谓词表示个体词的性质多元谓词反映个体词之间的关系多元谓词反映个体词之间的关系0元谓词是命题。元谓词是命题。例如：例如： A(x)：x是香港人。是香港人。 (一元谓词一元谓词) B(x,y)：x比比y年轻年轻20岁。岁。(二元谓二元谓词词)命题函数与命题命题函数与命题v当当n n1 1，命题函数，命题函数(n(n元谓词元谓词)P(x1, , xn)P(x1, , xn)不是命不是命题，由于真值无法确定。题，由于真值无法确定。v只需当用只需当用n n 个个体词替代个个体词替代 x1, x2, , xn x1, x2, , xn之后，才之后，才是命题。是命题。v举例：举例：v L(x,y) L(x

9、,y)：表示：表示“x“x小于小于y y的二元谓词，它的真值的二元谓词，它的真值不能确定。不能确定。v L(2,3) L(2,3) 是命题是命题“2“2小于小于3 3命题函数的定义域和值域命题函数的定义域和值域v 命题函数的定义域个体域：命题函数的定义域个体域：v 命题函数包含的一切个体变元的取值范围。命题函数包含的一切个体变元的取值范围。v 例如：例如：v R(x): x R(x): x是大学生。是大学生。v x x的定义域可为：一切人的定义域可为：一切人/ /某大学的一切学生某大学的一切学生/ /某中学的一某中学的一切学生切学生v 留意：留意：(1)(1)定义域不同，对命题的真值有影响。定

10、义域不同，对命题的真值有影响。v (2) (2)假设无特殊阐明，个体变元的定义域为全总个体假设无特殊阐明，个体变元的定义域为全总个体域。域。v 命题函数的值域：命题函数的值域：v 对命题函数每种能够的赋值所生成的命题的集合。对命题函数每种能够的赋值所生成的命题的集合。v 例如：例如：v x x的定义域为：张三、李四的定义域为：张三、李四v 那么那么R(x)R(x)的值域为：的值域为： 张三是大学生，李四是大学生张三是大学生，李四是大学生 谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数v 谓词谓词v7.1.2 7.1.2 量词量词v1. 1. 全称量词全称量词v2. 2

11、. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自在元约束元与自在元v改名规那么改名规那么量词的引入量词的引入v为了用谓词表示假设干个体词或全体个体词具为了用谓词表示假设干个体词或全体个体词具有某种性质或具有某种关系，需求引入量词。有某种性质或具有某种关系，需求引入量词。v v 例如：例如：v (1) (1) 某些人会跳舞；某些人会跳舞；v (2) (2) 一切人都会跳舞；一切人都会跳舞；量词量词v 定义定义 量词量词v 表示数量的词表示数量的词v 1. 1.全称量词全称量词: : v 表示恣意的表示恣意的, ,一切的一切的, ,每一个，凡是每一

12、个，凡是v x x 表示对个体域中一切的表示对个体域中一切的xxv 2. 2.存在量词存在量词: : v 表示存在表示存在, , 有的有的, , 至少有一个，有些至少有一个，有些v x x 表示在个体域中存在表示在个体域中存在xxv 在在x A(x)x A(x)和和x A(x)x A(x)中：中：v 紧跟量词的紧跟量词的x x称为量词的指点变元或作用变元称为量词的指点变元或作用变元v A A称为量词的辖域或作用域称为量词的辖域或作用域v 量词举例量词举例(1) (1) 一切的鱼都生活在水中。一切的鱼都生活在水中。 F(x) F(x)：x x是鱼是鱼 W(x) W(x)：x x生活在水中生活在水

13、中 一切的鱼都生活在水中：一切的鱼都生活在水中：( (x)(F(x) x)(F(x) W(x) W(x) 。(2) (2) 有些人会讲粤语有些人会讲粤语 M(x) M(x)：x x是人是人 Y(x): x Y(x): x会讲粤语会讲粤语 有些人会讲粤语：有些人会讲粤语：( (x) (M(x) x) (M(x) Y(x) Y(x)。全称量词和存在量词与结合词的搭配全称量词和存在量词与结合词的搭配v 描画某类个体中包含的一切个体具有某种性质描画某类个体中包含的一切个体具有某种性质v 与与 搭配搭配v 例如：设：例如：设：S(x)：x是学生。是学生。v P(x)：x经过了考试。经过了考试。v 一切学

14、生都经过了考试一切学生都经过了考试 v (x)(S(x)P(x)v (x)(S(x)P(x)？v 由于个体域必需是学生时，由于个体域必需是学生时，(x)(S(x)P(x)才为真才为真v 某类个体中部分个体具有某种性质某类个体中部分个体具有某种性质v 与与 搭配搭配v 例：有些学生经过了考试。例：有些学生经过了考试。v (x)(S(x)P(x)v (x)(S(x)P(x)？v 由于只需个体域中有非学生的个体由于只需个体域中有非学生的个体(x)(S(x)P(x)为真为真个体域与命题的符号化个体域与命题的符号化 (1) (1) 人都爱美人都爱美 (2) (2) 有人用左手写字有人用左手写字 分别取不

15、同的个体域集合：分别取不同的个体域集合： (a) (a) 个体域为人类集合个体域为人类集合, , (b) (b) 个体域为全总个体域个体域为全总个体域 宇宙中的一切事物宇宙中的一切事物. .解：设解：设M(x)M(x)：x x是人是人; F(x); F(x)：x x爱美；爱美； G(x) G(x)：x x用左手写字用左手写字 (a) (a) 个体域为人类集合的情况下：个体域为人类集合的情况下： (1) (1) x F(x) x F(x) 或或 x (M(x)x (M(x) F(x) F(x) (2) (2) x G(x) x G(x) 或或 x (M(x) x (M(x) G(x) G(x)

16、(b) (b)个体域为全总个体域的情况下：个体域为全总个体域的情况下： (1) (1) x (M(x)x (M(x) F(x) F(x) (2) (2) x (M(x) x (M(x) G(x) G(x)阐明：阐明：1个体域不同，同一个个体域不同，同一个命题符号化的结果不同。命题符号化的结果不同。量化的命题函数与命题量化的命题函数与命题v 命题函数不是命题，但仅包含被量化的变量的命题命题函数不是命题，但仅包含被量化的变量的命题函数是命题。函数是命题。v 如：如： M(x)：x是人。是人。v A(x)：x是聪明的。是聪明的。v B(x)：x要呼吸。要呼吸。v (1) M(x)B(x)v (2)

17、(x)(M(x)B(x)v (3) M(x) A(x) v (4) (x)(M(x)A(x)不是命题不是命题是命题是命题不是命不是命题题是命题是命题量词的顺序量词的顺序v 量词顺序普通不要随意颠倒，颠倒后表示的含义能够会改动。量词顺序普通不要随意颠倒，颠倒后表示的含义能够会改动。v 例：例：v 命题：对于任一给定的实数命题：对于任一给定的实数x，都存在着一个实数，都存在着一个实数y，使得，使得x + y = 0v 取个体域为实数集合，取个体域为实数集合， H(x, y): x + y = 0，v 那么命题可符号化为：那么命题可符号化为：xy H(x, y)v y x H(x, y) 那么表示：

18、那么表示：v 存在着一个实数存在着一个实数y，对于任一实数，对于任一实数x，使得，使得x + y = 0v x y H(x, y)是真命题，而是真命题，而y x H(x, y) 假命题假命题带量词的命题符号化举例带量词的命题符号化举例1请将以下命题符号化：请将以下命题符号化： (1) (1) 某些实数是有理数。某些实数是有理数。 (2) (2) 没有不犯错误的人。没有不犯错误的人。 (3) (3) 虽然有人聪明，但未必一切人都聪明。虽然有人聪明，但未必一切人都聪明。解：解：(1) R(x)(1) R(x)：x x是实数。是实数。Q(x)Q(x)：x x是有理数。是有理数。 ( (x)(R(x)

19、x)(R(x)Q(x) )Q(x) ) (2) M(x) (2) M(x)：x x是人。是人。F(x)F(x)：x x犯错误。犯错误。 ( (x)(M(x)x)(M(x)F(x)F(x) (3) M(x) (3) M(x)：x x是人。是人。S(x)S(x)：x x聪明。聪明。 ( (x)(M(x)x)(M(x)S(x) S(x) ( (x)(M(x)x)(M(x)S(x)S(x) 带量词的命题符号化举例带量词的命题符号化举例2 2 (4) (4) 正数都大于负数。正数都大于负数。 (5) (5) 直线直线a a与与b b平行当且仅当平行当且仅当a a与与b b不相交。不相交。解：解： (4)

20、 (4) 令令F(x): xF(x): x为正数。为正数。 G(y): y G(y): y为负数。为负数。 L(x,y): x L(x,y): x大于大于 y y。 x xy (F(x) y (F(x) G(y) G(y) L(x,y) L(x,y) (5) (5) 令令L(x): xL(x): x是直线。是直线。 P(x,y): x P(x,y): x与与y y平行。平行。 G(x,y): x G(x,y): x与与y y不相交不相交, , ( (x)(x)(y)(L(x)y)(L(x)L(y)L(y)(P(x,y) (P(x,y) G(x,y)G(x,y)命题符号化举例命题符号化举例3v只

21、运用全称量词，将以下命题符号化。只运用全称量词，将以下命题符号化。v 某些实数是有理数，但并非一切实数都是有理某些实数是有理数，但并非一切实数都是有理数。数。v解：原语句等价于：并非一切实数都不是有理数，解：原语句等价于：并非一切实数都不是有理数，并且并非一切实数都是有理数。并且并非一切实数都是有理数。v R(x) R(x)：x x是实数。是实数。v Q(x) Q(x)：x x是有理数。是有理数。v ( (x)(R(x)x)(R(x)Q(x)Q(x) ( (x)(R(x)x)(R(x)Q(x)Q(x)v 消去量词v当个体域为有限集时，如D=a1, a2, an，对于恣意的谓词A(x)，都有：v

22、x (A(x) A(a1) A(a2) A(an)vx (A(x) A(a1) A(a2) A(an)v这两个等价式称为消去量词等价式。消除量词举例消除量词举例v 设个体域设个体域D=a,b,D=a,b,请消除以下谓词中的量词。请消除以下谓词中的量词。v (1) ( (1) (x)(A(x)x)(A(x) B(x) B(x)v (2) ( (2) (x)(A(x)x)(A(x)B(x)B(x)v (3) ( (3) (x)(x)(y)R(x,y)y)R(x,y)v (4) ( (4) (y)(y)(x)R(x,y)x)R(x,y)v 解：解：v (1) (1) (A(a) (A(a)B(a)

23、B(a) (A(b) (A(b)B(b)B(b)v (2) (2) (A(a) (A(a)B(a) B(a) (A(b) (A(b)B(b)B(b)v (3) (3) ( (x)(R(x,a) x)(R(x,a) R(x,b) R(x,b)v (R(a,a)(R(a,a)R(a,b) R(a,b) (R(b,a) (R(b,a)R(b,b)R(b,b)v (4) (4) ( (y)(R(a,y) y)(R(a,y) R(b,y) R(b,y)v (R(a,a) (R(a,a) R(b,a) R(b,a) (R(a,b) (R(a,b) R(b,b) R(b,b)v 量化的谓词函数的翻译例量化的

24、谓词函数的翻译例v 设个体域为整数集，令设个体域为整数集，令v P(x, y): x + y = 1P(x, y): x + y = 1v Q(x, y): xy 0Q(x, y): xy 0v 阐明以下命题的意义，并指出哪些为真命题。阐明以下命题的意义，并指出哪些为真命题。v (1) (1) x x y P(x, y)y P(x, y)v v (2) (2) x xy Q(x, y) y Q(x, y) v (3) (3) x x y (Q(x, y) y (Q(x, y) P(x, y) P(x, y)对于恣意整数对于恣意整数x x，存在整数，存在整数y y，使，使得得x + y = 1x

25、 + y = 1存在整数存在整数x x，对于恣意整数，对于恣意整数y y，使得，使得xy 0 xy 0对于恣意整数对于恣意整数x x，存在整数，存在整数y y，使得，使得x + y = 1x + y = 1时当且仅当时当且仅当xy0 xy0谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数v1. 1. 谓词谓词v7.1.2 7.1.2 量词量词v1. 1. 全称量词全称量词v2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自在元约束元与自在元v改名规那么改名规那么谓词演算的原子公式谓词演算的原子公式v 定义定义 原子

26、公式原子公式v 不含任何结合词和量词的简单命题函数称不含任何结合词和量词的简单命题函数称为原子公式。为原子公式。v 举例：举例：v M(x) M(x)：x x是人是人 v Y(x): x Y(x): x会讲粤语会讲粤语谓词合式谓词合式v 定义定义 谓词合式谓词合式/ /公式公式v 由简单命题函数、逻辑结合词和量词组合成的谓词表达式。由简单命题函数、逻辑结合词和量词组合成的谓词表达式。v 合式公式的方式化定义：合式公式的方式化定义：v (1) (1) 原子公式是合式公式；原子公式是合式公式；v (2) (2) 假设假设A A是合式公式，那么是合式公式，那么( (A)A)是合式公式；是合式公式；v

27、 (3) (3) 假设假设A A、B B是合式公式，那么是合式公式，那么(AB)(AB)、(AB)(AB)、(AB)(AB)、(A (A B) B)是合式公式；是合式公式；v (4) (4) 假设假设A A是合式公式，那么是合式公式，那么x A(x)x A(x)、x A(x)x A(x)是合式公式是合式公式; ;v (5) (5) 只需经过有限次地运用规那么只需经过有限次地运用规那么(1)(1)(4)(4)构成的符号串才是构成的符号串才是合式公式。合式公式。谓词合式举例谓词合式举例v判别以下符号串能否谓词合式判别以下符号串能否谓词合式v (1) (1) x(A(x) B(x) x(A(x) B

28、(x) v (2) (2) x (A(x) B(x) x (A(x) B(x) x C(x) x C(x) v (3) ( (3) (x) A(x) (x) A(x) (x) B(x)x) B(x)v (4) ( (4) (x) (x) (y) P(y) P(x,y)x,y)v回答：回答：(1)(2)(1)(2)是谓词合式。是谓词合式。谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数v1. 1. 谓词谓词v2. 2. 命题函数命题函数v7.1.2 7.1.2 量词量词v1. 1. 全称量词全称量词v2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v

29、7.1.4 7.1.4 约束元与自在元约束元与自在元v改名规那么改名规那么约束元和自在元约束元和自在元v 在谓词公式在谓词公式x A(x)x A(x)和和x A(x)x A(x)中：中：v 紧跟量词的紧跟量词的x x称为量词的指点变元或作用变元称为量词的指点变元或作用变元v A A称为量词的辖域或作用域称为量词的辖域或作用域v 辖域中辖域中x x的一切出现称为约束出现，的一切出现称为约束出现， x x称为约束变元称为约束变元v 除去约束变元以外所其它变元的出现称除去约束变元以外所其它变元的出现称“自在出现自在出现，这种，这种变元称为自在变元变元称为自在变元v 举例：举例：x(P(x) Q(y)

30、R(y)x(P(x) Q(y)R(y)v 的辖域是的辖域是P(x)Q(y)P(x)Q(y)，指点变元是，指点变元是x x。v 整个公式中，整个公式中，x x 是约束出现，受是约束出现，受x x 的约束，的约束，y y是自在是自在出现出现约束元与自在元举例约束元与自在元举例1讨论以下合式公式中的约束元及自在元讨论以下合式公式中的约束元及自在元2) (2) (x P(x,y) R(y,z) x P(x,y) R(y,z) y Q(y)y Q(y)解：解： 的指点变元是的指点变元是 ，辖域是，辖域是 , , ( (x P(x, y) R(y, z)x P(x, y) R(y, z)中，是中，是 约束

31、出现且受约束出现且受x x 的约束，的约束， 是自在出现。是自在出现。 y Q(y)y Q(y)中，中，的指点变元是的指点变元是 ，辖域是，辖域是 ， 是约束出现。是约束出现。 整个公式中，整个公式中， 约束出现，约束出现， 既有约束出现又有既有约束出现又有自在出现，自在出现， 是自在出现。是自在出现。x xP(x,y)P(x,y)x xy y、z zy yQ(y)Q(y)y yx xy yz z变元的约束讨论v 从约束变元的概念可以看出，从约束变元的概念可以看出，P(x1,x2, ,xn)P(x1,x2, ,xn)是是n n元谓词，元谓词，它有它有n n个相互独立的自在变元。个相互独立的自在

32、变元。v 假设对其中假设对其中k k个变元进展约束，那么个变元进展约束，那么P P成为成为n-kn-k元谓词。元谓词。v 当当k = nk = n，即谓词公式中没有自在变元出现时，那么该公式，即谓词公式中没有自在变元出现时，那么该公式就成为一个命题。就成为一个命题。v 例如：例如： x P(x,y,z)x P(x,y,z)是二元谓词。是二元谓词。v y y x P(x,y,z)x P(x,y,z)是一元谓词。是一元谓词。v z z y y x P(x,y,z)x P(x,y,z)是零元谓词，即命题。是零元谓词，即命题。谓词逻辑谓词逻辑 v7.1.1 7.1.1 谓词与命题函数谓词与命题函数v1. 1. 谓词谓词v2. 2. 命题函数命题函数v7.1.2 7.1.2 量词量词v1. 1. 全称量词全称量词v2. 2. 存在量词存在量词v7.1.3 7.1.3 谓词合式谓词合式v7.1.4 7.1.4 约束元与自在元约束元与自在元v改名规那么改名规那么约束变元的改名规那么约束变元的改名规那么v 一个变元在公式中可以同时为约束变元与自在变元，因此有一个变元在公式中可以同时为约束变元与自在变元，因此有能够引起