当前位置：文档之家 › 第二章 谓词逻辑

第二章 谓词逻辑

  • 格式：ppt
  • 大小：584.51 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

第二章 谓词逻辑

第二章 谓词逻辑

同理可证, x(A(x)⋁B(x)) x A(x)⋁x B(x)
4/16/2014 5:10 PM chapter2 21
2.2 谓词公式中的等价与蕴含
(5)量词分配的蕴含关系
Predicate Logic 谓词逻辑
x A(x) ⋁ x B(x)x(A(x)⋁B(x))
x(A(x)⋀B(x))x A(x) ⋀ x B(x)
4/16/2014 5:10 PM chapter2 13
2.1 谓词及相关的概念
Predicate Logic 谓词逻辑
【例4】 将下列命题形式化为谓词逻辑中的命题：
(1)所有的病人都相信医生。
(2)有的病人相信所有的医生。 (3)有的病人相信某些医生。 (4)所有的病人都相信某些医生。 解: 设F(x)：x是病人，G(y)：y是医生，H(x，y)：x相信y。
4/16/2014 5:10 PM chapter2 19
2.2 谓词公式中的等价与蕴含
Predicate Logic 谓词逻辑
x(A(x)→B) x A(x) → B 不成立(×)
x(A(x)→B) x(┒A(x)⋁B)
x ┒A(x)⋁B ┒x A(x)⋁B x A(x) → B 同理, x(A(x)→B) x A(x) → B
2.1 谓词及相关的概念
Predicate Logic 谓词逻辑
全总个体域
全总个体域
要死的
人
活一百岁以上
人
4/16/2014 5:10 PM
chapter2
12
2.1 谓词及相关的概念
Predicate Logic 谓词逻辑
【例2】将下列命题形式化为谓词逻辑中的命题 (a) 没有不犯错误的人。

第02章谓词逻辑

第02章谓词逻辑

然而，(P∧Q)R并不是永真式，故上述 推理形式又是错误的。一个推理，得出矛盾的 结论
问题在哪里呢? ? ?
问题就在于这类推理中，各命题之间的逻辑关系 不是体现在原子命题之间，而是体现在构成原子命题 的内部成分之间，即体现在命题结构的更深层次上。
对此，命题逻辑是无能为力的。 所以，在研究某些推理时，有必要对原子命题作
③符号!称为存在唯一量词符，用来表达 “恰有一个”、“存在唯一”等词语；!x称为 存在唯一量词，称 x 为指导变元。
全称量词、存在量词、存在唯一量词统称量 词。
量词记号是由逻辑学家Fray引入的，有了量 词之后，用逻辑符号表示命题的能力大大加强了。
例：(1) 所有的人都是要死的。
(2) 有的人活百岁以上。 一、考虑个体域 D 为人类集合
列规则形成的符号串： P60 ① 原子谓词公式是谓词合式公式；
② 若A是谓词合式公式，则(¬A)是谓词合式公式； ③ 若A、B是谓词合式公式，则(A∧B)，(A∨B)， (AB)和(AB)都是谓词合式公式； ④ 若A是谓词合式公式，x是个体变元，则(x)A、 (x)A都是谓词合式公式； ⑤ 只有经过有限项次地使用①、②、③、④形成的 才是谓词合式公式。——简称为谓词公式。
例如：令 f(x,y) 表示 x+y，谓词 N(x) 表示x是 自然数，那么 f(2,3) 表示个体自然数 5，而 N(f(2,3))表示 5是自然数。
这里函数是就广义而言的。
例如：P(x): x是教授，f(x): x的父亲，c: 张 强，那么 P(f(c)) 便是表示“张强的父亲是教授” 这一命题。
客体——是指可以独立存在的，它可以是具体
的事物，也可以是抽象的概念。
如：李明，计算机，玫瑰花，自然数，思想，定 理等。

离散数学第2章 谓词逻辑

离散数学第2章 谓词逻辑
命题“凡人要死。”符号化为：(x)F (x) ⑵ 令G(x)：x是研究生。 命题“有的人是研究生。”符号化为：(x)G(x)
在命题函数前加上量词(x)和(x)分别叫做个体变元x 被全称量化和存在量化。一般地说，命题函数不是命题， 如果对命题函数中所有命题变元进行全称量化或存在量化， 该函数就变成了命题。这一结论在例2.3中得到验证。
为假。 ⑵ 如果5大于3，则2大于6。 解：设G(x,y)： x大于y a：5，b：3，c：2，d：6 该命题符号化为：G(a,b)→G(c,d) G(a,b)表示5大于3，它是真命题。G(c,d)表示2大于6，
ห้องสมุดไป่ตู้这是个假命题。所以G(a,b)→G(c,d)为假。
(3) 2 是无理数, 而 3 是有理数 解 ：设F(x): x是无理数, G(x): x是有理数 符号化为 F( 2) G( 3) 真值为 0 (4) 如果2>3，则3<4 解：设 F(x,y): x>y, G(x,y): x<y, 符号化为 F(2,3)G(3,4) 真值为1
谓词：刻划个体性质或个体之间相互关系的模式叫做谓词。谓 词常用大写英文字母表示，叫做谓词标识符。
例如可以用F，G，H表示上面三个命题中谓词： F：„是优秀共产党员。 G：„比„高。 H：„坐在„和„的中间。
第2章 谓词逻辑
一元谓词：与一个个体相关联的谓词。如上例中的F。 二元谓词：与两个个体相关联的谓词。如上例中的G。 三元谓词：与三个个体相关联的谓词。如上例中的H。
返回章目录
第2章 谓词逻辑
课外作业
• 教材P59-60页: 练习题（需要做在练习本上） （1） （2） a)、c) 、d)、e)、 f)、i)、k)、l)
返回章目录

第二章 谓词逻辑

第二章 谓词逻辑

例6 设个体域是人类，
每个人都有人爱，但没有人为所有人爱。 用L(x,y)表示“x爱y” 它可译为 x yL(y,x) ∧┐y x L(x,y)
例7 每人都有自己喜欢的水果，有人喜欢所有的水果。 F(x)：x是水果 M(x):x是人 L(x,y):x喜欢y x(M(x)→y (F(y)∧L(x,y)))∧x(M(x)∧y(F(y)→L(x,y)))
F(x,y)x摆满了y。 R(x)x是大红书柜。 Q(y)y是古书。
a这只 b那些 R(a)Q(b)F(a,b)
例5 所有运动员都钦佩一些教练员。
设：S（x）：x是运动员； J（x）：x是教练员； L（x,y）：x钦佩y。 谓词符号化为： (x)(S(x)→(y)(J(y)∧L(x,y)))
A(x)中的约束出现；约束出现的变元称为约束变元； A(x)中不是约束出现的其它变元称为该变元的自由 出现，自由出现的变元成为自由变元。
例1(x)(A(x)(y)Q(x,y)) 解：由x后的（），x是指导变元，x的辖域是 后面整个式子，y是指导变元，辖域仅Q（x，y） 此部分。x两次出现均是约束出现，y的一次出现 是约束出现，故x，y是约束变元，而不是自由变 元。 例2(x)F(x)G(x,y) 解：x的辖域仅F(x),x是指导变元，变元x第一次 出现是约束出现，第二次出现是自由出现，y的出 现是自由出现。所以第一个x是约束变元，第二个x 是自由变元，本质上这两个x的含义是不同的；而y 仅是自由变元。
关于特性谓词的说明
M(x):x是人 B(x):x勇敢 D(x):x是要死的 x (M(x)∧B(x))（有人勇敢) x(M(x)→D(x))（所有人都是要死的） 对全总个体域而言，“有人勇敢”即“有个体不仅 是人而且勇敢”，M(x)与B(x)合取是当然的； 而“所有的人都是要死的”则是指“全总域中是人 的那部分个体都是要死的”，即“是人则要死” 因而M(x)与D(x)是条件关系。

第2章 谓词逻辑

第2章 谓词逻辑
将推理形式化为(P∧Q) → R，不是永真式，不能判断推理的
有效性。为了克服命题逻辑的局限性，将命题细分。
3
第二章 谓词逻辑
§2-1-2 谓词逻辑三要素
个体词、谓 词和量词
命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主 语和谓语两部分组成。一般主语充当个体词，谓语充当谓词。
（1）个体词
个体词：在原子命题中，可以独立存在的客体。
量词分为以下两种： –全称量词：“”（一切、所有的、任意的…） –x：个体域的所有个体 –xF(x)：个体域的所有个体都有性质F。 –存在量词：“”(存在、有一个、至少…） –x：存在个体域的个体 –xF(x)：存在个体域的个体具有性质F。
11
第二章 谓词逻辑
几点注意： 1.谓词的记法
设论域A中元素a,b,c ∈A,
（2）设二元谓词G(x,y)：x大于y。a：4，b：5，c：6. 命题符号化为G(b,a)→G(a,c)。 由于前件为真，后件为假，所以该命题为假。
10
第二章 谓词逻辑
（3）量词 有了个体词和谓词的概念后，对有些命题来说，还是不能 准确地符号化，原因是还缺少表示个体常元或变元之间数 量关系的词。 量词：表示个体常元或变元之间数量关系的词。
例如，在命题“张明是个大学生”中，“张明”是个体，“是个大 学生”是谓词，它刻划了“张明”的性质。 设S：是大学生，c：张明，则“张明是个大学生”可表示为S(c)。
5
第二章 谓词逻辑
通常，把一个n元谓词中的每个个体的论域综合在一起作 为它的论域，称为n元谓词的全总论域。
当一个命题没有指明论域时，一般都以全总个体域作为其 论域。
例2-1.2 令S(x)：x是聪明的。讨论范围可以有：

离散数学第二章谓词逻辑

离散数学第二章谓词逻辑
一般来说，当多个量词同时出现时， 它们的顺序不能随意调换。
*
第二章 谓 词 逻 辑 命题函数与量词
当个体域为有限集合时，如D={a1, a2 …, an}，对任意谓词A(x)，有 xA(x)A(a1)∧A(a2)∧…∧A(an ) xA(x)A(a1)∨A(a2)∨…∨A(an )
特性谓词常作合取项，如x(M(x)∧ G(x))。
第二章 谓 词 逻 辑
命题函数与量词
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
例如：在实数域上用H(x,y)表示x+y=5，则命题“对于任意的x，都存在y使得x+y=5”可符号化为：xyH(x,y)，其真值为1。若调换量词顺序后为： yxH(x,y) , 其真值为0。
*
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
令S(x): x吸烟。则符号化为：
（x）(M(x)∧S(x))
令D(x): x登上过木星。则符号化为：
令Q(x):x是清华大学的学生。H(x):x是高
第二章 谓 词 逻 辑 2.2 命题函数与量词
*
小结:本节介绍了n元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。
添加标题
x(M(x) F(x)).
添加标题
第二章 谓 词 逻 辑
添加标题
命题函数与量词
*
当个体域为全体学生的集合时：
01
令P(x): x要参加考试。则（2）符号化为
02
xP(x).
03
当个体域为全总个体域时：
04
令S(x): x是学生。则（2）符号化为
05
x(S(x) P(x)).

离散数学第2章 谓词逻辑

离散数学第2章 谓词逻辑
例4：某些人对某些食物过敏。 设F(x,y)：x对y过敏。 M(x)：x是人。 G(y)：y是食物。 (x) (y) (M(x) ∧ G(y) ∧ F(x,y))
33
§3 谓词公式与翻译
例5：凡是实数不是大于0，就是等于0或者小于0。 设R(x)：x是实数。 P(x,0)：x大于0。 Q(x,0)：x等于0。 S(x,0)：x小于0。 (x) (R(x) → ( P(x,0) Q(x,0) S(x,0) ) )
例：所有的人都是会死的。
设M(x)：x是人。S(x)：x是会死的。
个体域约定为{人类}：(x) (S(x))
全总个体域：
(x) ( M(x) → S(x) )
例：有一些人是不怕死的。
设M(x)：x是人。F(x)：x是不怕死的。
个体域约定为{人类}：(x) (F(x))
全总个体域：
(x) ( M(x) ∧ F(x) )
定义：在反映判断的句子中，用以刻划客体的性质或 关系的即是谓词。
5
§1 谓词的概念与表示法
客体，是指可以独立存在的事物，它可以是具体 的，也可以是抽象的，如张明，计算机，精神等。
表示特定的个体，称为客体常元，以a，b，c… 或带下标的ai，bi，ci…表示；
表示不确定的个体，称为客体变元，以x，y， z…或xi，yi，zi…表示。
4. 谓词中通常只写客体变元，因此不是命题，仅当 所有客体变元做出具体指定时，谓词才成为命题， 才有真值。
12
第二章 谓词逻辑
§1 谓词的概念与表示法 §2 命题函数与量词 §3 谓词公式与翻译 §4 变元的约束 §5 谓词演算的等价式与蕴含式 §6 前束范式 §7 谓词演算的推理理论
13
§2 命题函数与量词

第二章 谓词逻辑

第二章 谓词逻辑

离散数学
第一章
例3 设Q(x,y)表示“x比y重”。 当x,y指人或物时，它是一个命题，但 若x,y指实数时，Q(x,y)就不是一个命题。
离散数学
第一章
例4 R(x)表示“x是大学生”。 如果x的讨论范围为某大学里班级中的学 生，则R(x)是永真式。 如果x的讨论范围为某中学里班级中的学 生，则R(x)是永假式。 如果x的讨论范围为一个剧场中的观众， 观众中有大学生也有非大学生，那么，对某些 观众，R(x)为真，对另一些观众，R(x)为假。 真值不理，若L(x,y)表示x小于y，那么 L(2,3) 表示一个命题：“2小于3”, 为真。 而 L(5,1) 表示一个命题：“5小于1”, 为假。 又如,A(x,y,z)表示一个关系“x加上y等于z” 则 A(3,2,5) 表示了真命题“3+2=5”，而A(1,2,4)表示了一个假命题 “1+2=4”。 从上述三个例子中可以看到 H(x)，L(x,y)，A(x,y,z) 中的x，y，z等都是客体变元。 它们很象数学中的函数，这种函数就是命题函数。
离散数学
第一章
3. 量词 使用上面所讲的一些概念，还不能用符号很好地表达 日常生活中的各种命题。 例如：S(x)表示x是大学生，而x的个体域为某单位的 职工。那么S(x)可以表示某单位职工都是大学生，也可以 表示某单位存在一些职工是大学生。 为了避免这种理解上的混乱，需要引入量词，以刻划 “所有的”和“存在一些’的不同概念。 例如: (1) 所有的人都是要呼吸的。 (2) 每个学生都要参加考试。 (3) 任何整数或是正的或是负的。 这三个例子都需要表示“对所有的x”这样的概念，为此 ，引入符号： (x) 或 (x) 表示“对所有的x”。
离散数学
第一章

第2章 谓词逻辑

第2章 谓词逻辑

第2章谓词逻辑本章主要内容包括谓词逻辑的基本概念、谓词逻辑命题的符号化，谓词公式及其真值，谓词公式的前束范式，重言蕴含式与推理规则等。

下面就此作一简要介绍。

一、谓词逻辑的基本概念及其符号化个体是指可以独立存在的客观实体，它可以是具体的，也可以是抽象的。

具体的特定个体称为个体常量；抽象的、泛指的或在一定范围内变化的个体称为个体变量，也称为个体变元；个体变量的取值范围称为个体域(或论域)；在命题中，表示一个个体性质、特征或多个个体之间关系的成份称为谓词；表示具体性质或关系的谓词称为谓词常量或常谓词，否则称为谓词变量。

一般用大写字母F、G、H等表示谓词，而用X、Y、Z等表示谓词变量。

表示一个个体性质的谓词称为一元谓词：表示多个个体之间关系的谓词称为多元谓词。

在命题中除了个体和谓词外，有时还出现表示数量的词称为量词。

我们讨论的量词有两个，即存在量词和全称量词。

全称量词对应于汉语中的“每个”、“所有的”、“任意的”等，用符号“∀”表示。

存在量词对应于汉语中的“有的”、“至少有一个”、“存在”等，用符号“∃”表示。

在个体域事先给定的情形下，我们只有将个体域中的每个具体的个体代入到F(x)中去确定其真假，才能断定∀xF(x)的真假。

当每一个个体都使得F(x)=1时，就有∀xF(x)=l；否则∀xF(x)=0。

对于∃F(x)，我们只要发现个体域中有(一个或多个)个体使得F(x)=1时，就有∃xF(x)=1；否则(即任何个体都使得F(x)=O)∃xF(x)=0。

在用量词符号化命题时，首先强调的是个体域，同一命题在不同的个体域内可能有不同的符号化形式，同时也可能有不同的真值，因此必须先清楚个体域，不先确定所考虑的个体域就不能准确地表达原命题的意思。

为了解决这一问题，使得符号化表达式有确定的含义而不需事先考虑个体域，我们在符号化表达式中增加一个指出个体变量的变化范围的谓词，这样就可以不需事先考虑个体域而能够准确地把命题的意思表示出来。

第2章 谓词逻辑

第2章 谓词逻辑

（3）不是所有的人都喜欢看电影。 解：令F(x)：x是人，G(x)：x喜欢看电影。 则命题表示为：(x)(F(x)G(x))
21
第二章 谓词逻辑
练习
在谓词逻辑中将下列命题符号化（个体域为全体鸟类）： (1) 所有蜂鸟都有鲜艳的羽毛。 (2) 没有大鸟以蜂蜜为食。 (3) 不以蜂蜜为食的鸟类有灰暗的羽毛。 (4) 蜂鸟是小鸟。 解：设P(x)：x是蜂鸟， Q(x)：x是大鸟，R(x)：x以蜂蜜为 食。S(x)：x有鲜艳的羽毛。
16
第二章 谓词逻辑
6. 多个量词同时出现时,不能随意颠倒它们 的顺序，颠倒后会改变原命题的含义
例：取个体域为实数集：
考虑命题： 对任意的x，存在着y，使得x+y=5
H(x,y): x+y=5 真命题 符号化为：∀x∃yH(x,y)，
但颠倒量词顺序得：∃y∀xH(x,y)，表示的含义：
存在着y，对任意的x，都有x+y=5，假命题
18
第二章 谓词逻辑
§2-1-3 谓词逻辑命题符号化
例2-1.3 用谓词逻辑符号化下列命题。 （1）所有大学生都爱学习。 解：令S(x)：x是大学生，L(x)：x爱学习，(x)(S(x)L(x)) （2）每个自然数都是实数。 解：令N(x)：x是自然数，R(x)：x是实数，(x)(N(x)R(x))
6
第二章 谓词逻辑 定义2-1.1 一个原子命题用一个谓词（如P）和n个有次 序的个体常元（如a1，a2，…，an）表示成P(a1，a2，…， an)，称它为该原子命题的谓词形式或命题的谓词形式。 定义2-1.2 由一个谓词（如P）和n个体变元（如x1， x2，…，xn）组成的P(x1，x2，…，xn)，称为n元原子谓词 或n元命题函数，简称n元谓词。 • n=1，一元谓词——表示性质 • n2，多元谓词——表示事物之间的关系， • 例如：L(x,y)：xy • 0元谓词——不含个体变元的谓词——命题常元或变元； 例如：ab:a取为2,b取为3 命题看成谓词的特殊情况，命题逻辑的联结词均可应用。

离散数学_谓词逻辑

离散数学_谓词逻辑

(3) 当个体域为全体整数的集合时： 令P(x): x是正的。N(x): x是负的。则（3）符 号化为 （x）(P(x)∨N(x)) 当个体域为全总个体域时： 令I(x): x是整数。则（3）符号化为 （x）(I(x)(P(x)∨N(x))).
全称量词的一些重要性质： 设P是任意的命题，F(x)与A(x,y)均为谓词， 则有：
【例】设 P 表示命题：张辉是工人。 Q 表示命题：李明是工人。 仅仅从命题符号 P 和 Q 看不出张辉和李明 都是工人这一特性。 【例】 x=3 ? x+y=z ? f(x)=0 ?
第二章 谓词逻辑（Predicate Logic）
2.1 谓词的概念与表示(Predicate and Its Expression)
2.1 谓词的概念与表示(Predicate and Its Expression) 谓词：用来刻划个体的性质或个体之间的相互关系的词。 例如在下面命题中： （1）张明是个劳动模范。 （2）李华是个劳动模范。 刻划客体的性质 （3）王红是个大学生。 （4）小李比小赵高2cm。 （5）点a在b与c之间。 刻划客体之间的相互关系 （6）阿杜与阿寺同岁。 （7） x与y具有关系L。 “是个劳动模范”、“是个大学生”、“…比…高2cm”、 “… 在…与…之间”、“…与…具有关系L”都是谓词。
2.1 谓词的概念与表示(Predicate and Its Expression)

（2）当个体域为人类集合时： 令G(x): x活百岁以上。则（2）符号化为 （ x）G(x) 当个体域为全总个体域时： 令M(x): x是人。则（2）符号化为 （x） (M(x) ∧ G(x))
存在量词的一些重要性质： 设P是任意的命题，F(x)与A(x,y)均为谓词， 则有：

第二章 谓词逻辑

第二章 谓词逻辑
2-7
第２章 谓词逻辑
【例2.1.1】 将下列语句形式化为谓词逻辑 】 中的命题或命题函数。 中的命题或命题函数。 （1）小王是二年级大学生。 ）小王是二年级大学生。 （2）小王是李老师的学生。 ）小王是李老师的学生。 （3）如果 且y≤x，则x=y。 ）如果x≤y且 ， 。 是大学生； （ ） 解：（1）令F（x）：x是大学生；G（x）：x ） （ ） 是大学生 是二年级的； ：小王。则原句形式化为： 是二年级的；a：小王。则原句形式化为： F（a）∧G（a）。 （ ） （ ）
（ （ ） （ ）） ∀ x（H（x）→F（x））
2-13
第２章 谓词逻辑
（ 2） 引入特性谓词 （ x） ： x是我们班 ） 引入特性谓词W（ ） 是我们班 的人。 （ ） 会吸烟。 的人。 G（x） ：x会吸烟。 会吸烟 "我们班有人吸烟 的涵义可以这样理解： 我们班有人吸烟"的涵义可以这样理解 ： 我们班有人吸烟 的涵义可以这样理解 在宇宙间的万物（全总个体域） 在宇宙间的万物（全总个体域）中，有一个子 我们班， 吸烟的人。 集 --我们班 ， 还有另一个子集 吸烟的人 。 强 我们班 还有另一个子集--吸烟的人 调的是既在我们班，又吸烟的的人， 调的是既在我们班，又吸烟的的人，所以是两 个子集的交集。特性谓词用合取项加入。 个子集的交集。特性谓词用合取项加入。则原 句可形式化为： 句可形式化为：
2-9
第２章 谓词逻辑
前两句均是命题， 前两句均是命题 ， 第三句因为含有变元 所以是命题函数。 但实际上我们知道， 所以是命题函数 。 但实际上我们知道 ， 只要 限制在数的范围内， 将 x、 y限制在数的范围内 ， 第三句是定理 ， 、 限制在数的范围内 第三句是定理， 是永真的。 这就涉及到了个体域。 是永真的 。 这就涉及到了个体域 。 在简单命 题中，常有一些表示数量关系的词语，诸如" 题中，常有一些表示数量关系的词语，诸如 所有的"、 有一些 等等， 有一些"等等 所有的 、"有一些 等等，用来表示论域中的 全体或部分个体， 在谓词逻辑中， 我们用量 全体或部分个体 ， 在谓词逻辑中 ， 词把它们形式化。 词把它们形式化。

第二章谓词逻辑

第二章谓词逻辑

第二章 谓词逻辑
2.1 谓词的概念与表示
苏格拉底三段论：
所有人都是要死的，苏格拉底是人，所以苏格拉底 是要死的。
用P,Q,R分别表示以上三个命题。 则得到推理的形式结构为：
(P∧Q)→R
第二章 谓词逻辑
2.1 谓词的概念与表示
谓词逻辑命题符号化的三个基本要素：客体词、 谓词、量词。 反映判断的句子由主语和谓语组成。
第二章 谓词逻辑
2.2 命题函数与量词
每个由量词确定的表达式都与个体域有关。为了方便，
将所有命题函数的个体域全部统一，使用全总个体域，之
后，对每一个客体变元的变化范围，用特性谓词加以限制。 特性谓词：从全总个体域中分离出一个集合，定义的
谓词。
对全称量词，特性谓词常作蕴含的前件，对存在量 词，特性谓词常作合取项。
则: (1) x (M(x) → F(x));
(2) x (M(x)∧ G(x)).
第二章 谓词逻辑
由上面例子可见：
（1）在不同个体域中，同一个命题的符号化形式可能不同。 一般地，对全称量词，特性谓词应作为蕴含式的前件。
一般地，对存在量词，特性谓词应作为合取式的一项。 （2）同一个命题，在不同个体域中的真值也可能不同。
组成的表达式为复合命题函数。
逻辑联结词组、∧、∨、—>、<—>的意义与 命题演算中的解释完全类同。
第二章 谓词逻辑
2.2 命题函数与量词
有了个体词和谓词的概念之后，有些命题还是不能准确地符号化 。 以前面所讨论的三段论为例： 令：P(x)：x是偶数。 S(x) ： x能被2整除。 a：6。
符号化为： (1)P(x)→S(x) (2)P(a) (3)S(a) 我们知道，“凡偶数都能被2整除。”是一个真命题， 而“P(x)→S(x)”是一个一元函数，不是一个命题。原因是 “P(x)→S(x)”没有把命题(1) 中“凡”的意思表示出来。 即缺少表示个体常项或变项的数量关系的词。所以还要引入量 词的概念。

第二章谓词逻辑

第二章谓词逻辑
特性谓词在加入到命题函数中式遵循如下规 则：
(1).对应全称量词，刻划其对应个体域的特性 谓词作为蕴含式的前件加入；
(2).对应存在量词，刻划其对应个体域的特性 危险作为合取项加入。
16/86
2.1 谓词逻辑的基本概念与表示
•例2-5：符号化下列语句。
(1).天下乌鸦一般黑； (2).那位身体强健的，用功的，肯于思考问题的大学
9/86
Hale Waihona Puke 2.1 谓词逻辑的基本概念与表示
•例2-2：符号化如下命题。
P：上海是一个现代化城市； Q：甲是乙的父亲； R：3介于2和5之间； T：布什和萨达姆是同班同学。
• 注意：
(1).谓词中个体词的顺序是十分重要的，不能随意变 更。如前面的F (b, c)与F (c, b)的真值就不同；
(2).一元谓词用以描述一个个体的某种特性，而n元 谓词则用以描述n个个体之间的关系；
19/86
2.1 谓词逻辑的基本概念与表示
2.1.3谓词的语言翻译
设G (x)是关于x的一元谓词，D是其个体域， 任取x0∈D，则G (x0)是一个命题。
(x)G(x)是这样的一个命题:“对任意x， x∈D，G(x)都成立”其真值规定如下：
1对所 x 有 D ，的 都 G( 有 x 1) ( x)G (x) 0否则。
任意的n个项，则f(t1, t2, …, tn)是项； (3).所有的项都是有限次使用(1)，(2)得到的。
25/86
2.2 谓词的合式公式及解释
我们定义的项，包括了常量，变量及函数。 例如，x，a，f(x, a)，f(g(x, a),b)，h(x)均是项。
函数的使用，能给谓词表示带来很大的方便。
5/86

第二章 谓词逻辑

第二章 谓词逻辑

14
第二章 谓词逻辑
2.2
2.2.2 例2.7
谓词逻辑公式与解释
约束变元与自由变元 指出下列各式量词的辖域及变元的约束情况： 指出下列各式量词的辖域及变元的约束情况：
（1）x（F（x，y）→ G（x，z）） （2）x（P（x）→y R（x，y）） ））→ （3）x（F（x）→ G（y））→ y（H（x）∧M（x，y，z））
12
第二章 谓词逻辑
2.2
2.2.1 例2.6
谓词逻辑公式与解释
谓词逻辑的合式公式 将下列命题符号化。 将下列命题符号化。
（1）尽管有人聪明，但并非所有人都聪明。 尽管有人聪明，但并非所有人都聪明。 （2）这只大红书柜摆满了那些古书。 这只大红书柜摆满了那些古书。 解 （1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符 聪明； 是人。则命题（ x（M（x）∧C（x））∧x（M（x）→C（x）） ））∧ （2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）: 摆满了y 是大红书柜； x是古书；a：这只；b：那些。则命题（2）可符号化为 是古书； 这只； 那些。则命题（
15
第二章 谓词逻辑
2.2
2.2.2
谓词逻辑公式与解释
约束变元与自由变元
对于 的辖域是A= A=（ ））， 解 （1）对于x的辖域是A=（F（x，y）→ G（x，z）），在A 中，x是约束出现的，而且约束出现两次，y，z均为自由出现， 是约束出现的，而且约束出现两次， 均为自由出现， 而且各自由出现一次。 而且各自由出现一次。 ））， （2）对于x的辖域是（P（x）→y R（x，y）），y的辖域是 对于 的辖域是（ R（x，y），x，y均是约束出现的。 均是约束出现的。 ）），其中x （3）对于x的辖域是（F（x）→ G（y）），其中x是约束出现 对于 的辖域是（ 的，而y是自由出现的。对y的辖域是（H（x）∧M（x，y， 是自由出现的。 的辖域是（ z）），其中y是约束出现的，而x，z是自由出现的。在整个公式 ）），其中y是约束出现的， 是自由出现的。 中，x约束出现一次，自由出现两次，y约束出现一次，自由出现 约束出现一次，自由出现两次， 约束出现一次，

离散数学第二章谓词逻辑

离散数学第二章谓词逻辑

则xP和xP都是谓词公式
(5)当且仅当能够有限次地应用(1)－(4)所得到的
式子是谓词公式
二、谓词公式的概念

谓词公式是命题公式的扩展，约定最外层圆括号可 以省略，但量词后面若有括号则不省略。

例如 (P(x,y)→(Q(x)→R(y,z)))
P(x,y,z)∧(P(x,y,z)→Q)
y((A(x)∧A(y))→F(x,y,0))
2.2 命题函数与量词

例2.2.6 翻译命题
甲村人与乙村人都同姓。
解 设A(x)：x是甲村人。 B(y)：y是乙村人。 P(x,y)：x与y同姓。 (1)全总个体域 xy((A(x)∧B(y))→P(x,y)) (2)x的论域:甲村人 xy(P(x,y)) y的论域:乙村人
1.令F(x)：x是金属。G(y)：y是液体。H(x,y)：x可以溶解在y 中。则命题“任何金属可以溶解在某种液体中。”可翻译 为（ ）。 A．x(F(x)∧y(G(y)∧H(x,y))) B．xy(F(x)→(G(y)→H(x,y))) C．x(F(x)→y(G(y)∧H(x,y))) D．x(F(x)→y(G(y)→H(x,y))) 2.令F(x)：x是火车。G(y)：y是汽车。H(x,y)：x比y快。则命 题“某些汽车比所有火车慢。”可翻译为（ ）。 A.y(G(y)→x(F(x) ∧H(x,y))) B.y(G(y)∧x(F(x)→H(x,y))) C.xy(G(y)→(F(x)∧H(x,y))) D.y(G(y)→x(F(x)→H(x,y)))
由一个谓词常量或谓词变量A，n(n≥0)个个体变量 x1,x2,…,xn组成的表达式A(x1,x2,…,xn) 注意：0元谓词是命题，谓词逻辑是命题逻辑的扩 展。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

α中连续的符号串且也是谓词公
式，则称β是α的子公式。
2.2 谓 词
例如， α=x(P(x)y(Q(y)R(x,y))) ，β=y(Q(y)R(x,y))，则β是
公
α的子公式。而P(x)y不是谓
式
词公式，因而也不是α的子公式
。
2.2.2 自由变元与约束变元
定义2.11 设α是一个谓词公式
，xβ(x)和xγ(x)是α的子公
词
个体性质以及各个个体间的关系，确定
公
谓词；
式
（3）根据表示数量的词确定量词；
（4）利用联结词将整个命题符号化。
2.2.1 谓词公式与翻译
例2.5 将下列命题符号化。
（1）教室里有同学在讲话。
2.2 解 因为题中没有特别指明个体域
谓
，所以这里采用全总个体域。
词
令S(x)：x是同学， R(x)：x
公
公
题可符号化为：
式
x(N(x)y(N(y)G(y,x)))。
2.2.1 谓词公式与翻译
（4）今天有雨雪，有些人会跌跤。
解 令R：今天下雨， S：今天下雪
2.2 谓 词
，M(x)：x是人，F(x)：x会跌跤 ，则命题可符号化为： (RS)x(M(x)F(x))。
公 式
2.2.1 谓词公式与翻译
定义2.11 设α是谓词公式，β是
第2章 谓词逻辑
在命题逻辑中，我们把命题分解到
原子命题为止，认为原子命题是不能再
分解的，仅仅研究以原子命题为基本单
第
位的复合命题之间的逻辑关系和推理。
2
实际上，简单命题还可以进行分解
章
，例如，“王平是大学生”这一简单命 题可以分解为主语(王平)和谓语(是大学
谓
生)，命题逻辑反映不出这一特点。
词 逻
谓
的原子谓词公式，简称原子公式
词
。
公 式
由定义可知，一个命题或一 个命题变元也称为原子公式，也 就是说，当n=0时，P(x1，x2，…
，xn)为原子命题P。
2.2.1 谓词公式与翻译
定义2.10 谓词公式归纳定义如下：
（1）原子公式是谓词公式；
（2）如果α是谓词公式，则α也是谓
2.2 谓
词公式； （3）如果α和β是谓词公式，则αβ ，αβ，β→α和αβ也都是谓词
词
（2）令Q(x)：x是奇数，则命题可表示 为：xQ(x)。
和 （3）令R(x)：x是偶数，S(x)：x是素数
量
，则命题可表示为！x(R(x)S(x))。
词
2.1.3 量词
定义2.8 若一个谓词P(x)是用来
2.1 限制个体变元的取值范围，那么
个
称谓词P(x)为特性谓词。
体
在使用全总个体域时，对个
式，则称xβ(x)与xγ(x)是α
2.2
的约束部分，x称为是约束出现的
谓
。约束出现的变元称为约束变元
词
，不是约束出现的变元称为自由
公
变元。β(x)称为是x在α中的辖
式
域（或作用域），γ(x)称为是x
在α中的辖域。
2.2.2 自由变元与约束变元
确定一个量词的辖域即是找出位于
该量词之后的相邻接的子公式，具体地 讲：
公
并要求改名后的式子与原式同真假。
式 ❖所谓代入就是把一变元代以公式(公式
的值的变域应与变元的变域相同)，并
要求代入后的公式为原式的特例。
2.2.2 自由变元与约束变元
改名的规则如下：
(1)改名只对约束变元进行，不对自由变元进
词
解 “x”与“y”是个体变元，谓
和
词为R。这里的谓词是二元谓词，
量 属于谓词变元。
词
2.1.2 谓词
例2.2 用个体，谓词表示下列命题。
2.1 （1）张华是大学生。
个
解 令a：张华； S(x)：x是大学生。整 个命题可表示为：S(a)。
体
说明：
、
①若x的个体域为某大学计算机系
谓 词
的全体学生，则S(a)为真； ②若x的个体域为某中学的全体学
谓
命题公式是谓词公式的一个特例
词
。
公 式
为叙述方便，我们下面讨论
只含“x”和“x”的谓词公式 ，事实上，量词“！x”可以通
过量词“x”和“x”来表示。
2.2.1 谓词公式与翻译
一般来说，将自然语言翻译成谓词公 式主要有以下几个步骤：
（1）确定个体域，如无特别说明，一般
2.2
使用全总个体域；
谓
（2）根据个体域，分析命题中的个体、
其次，如下两个简单命题“王平是
大学生”和“李明是大学生”，有一个 共同特点——是大学生，这一共性在命
辑
题逻辑中也表示不出来。因此，有必要
推广命题逻辑。
第三，有些简单而正确的推理过程 在命题演算里不能得到证明。例如著名 的苏格拉底三段论：
第
“人都是要死的，苏格拉底是人， 所以苏格拉底是要死的。”
2
在命题逻辑中，三个原子命题分别
、 体变化的真正取值范围，用特性
谓
谓词加以限制。一般地，对全称
词
量词，将特性谓词作蕴含的前件
和
；对存在量词，将特性谓词作合
量
取项。
词
2.1.3 量词
例2.4 用全总个体域对例2.3中
2.1 的所有命题进行符号化。
个 体
解 在例2.3的基础上增加一个特 性谓词I(x)：x是整数。则各命题
、 可表示为：
章
用P，Q，R表示，现在要证明PQR，
即证明PQR是重言式，但这在命题
谓
逻辑中是不可能的。因此从推理的角度
词
看，也有必要推广命题逻辑。
逻
谓词逻辑就是命题逻辑的自然推广 。本章介绍的谓词逻辑内容仅限于一阶
辑
谓词逻辑或狭义谓词逻辑，即谓词中的
变元不再是谓词变元。
本章内容提要：
第
1.个体、谓词和量词的概念
2
2.谓词演算公式
章
3.谓词演算的等值公式
谓
4.前束范式
词
5.推理理论
逻
6.谓词逻辑在计算机科学中的应用
辑
2.1.1 个体
定义2.1 可以独立存在的物体称为个
2.1
体，它可以是一个具体的事物，也可以 是一个抽象的概念。
个
如王平，李明，计算机，离散数学
体
，精神等都可以作为个体。
、
定义2.2 将表示具体的或确定的个体称 为个体常元，而将表示抽象的或泛指的
谓
量关系的词叫存在量词，用符号“”
词
表示；表示“存在惟一”，“恰有一个
和
”等数量关系的词叫存在惟一量词，用
量
符号“！”表示。
词
2.1.3 量词
2.1
注意：量词的优先级高于任
个
何联结词，所以
体
(x)P(x1,x2,…,xn)、
、 (x)P(x1,x2,…,xn)、可分别写成
谓
xP(x1,x2,…,xn)、
体
个体域可以是有穷集合，例如
、 谓
{1,2,3,4,5}，{a,b,c}等，也可以是无 穷集合，例如自然数集，实数集等。同 时约定，本书在论述或推理中如无指明
词
所采用的个体域，则都是使用全总个体
和
域。
量
词
2.1.2 谓词
定义2.4 表示单个个体的性质或两个
2.1 以上个体关系的词叫谓词。
个 体
定义2.5 表示具体性质或关系的谓词 称为谓词常元，表示抽象的或泛指的性
谓 词
（1）x(I(x)P(x))
和 （2）x(I(x)Q(x))
量 （3）！x(I(x)R(x)S(x))
词
2.1.3 量词
练习 将下列命题符号化。
2.1 个
(1)天下乌鸦一般黑。
体 (2)任何金属都可以溶解在某种液
、
体中。
谓
词
和
量
词
2.1.3 量词
在谓词前加上量词，称为谓 2.1 词的量化。若一个谓词中所有个体 个 变元都量化了，则该谓词就变成了 体 命题。这是因为在谓词被量化后，
生，则S(a)为假；
和
③若x的个体域为某电影院中的观
量 词
众，则S(a)真值不确定。所以个体变元 在哪些个体域取特定的值，对命题的真 值极有影响。
2.1.2 谓词
（2）武汉位于重庆和上海之间。
2.1 个 体
解 令a：武汉； b：重庆； c：上 海； P(x,y,z)：x位于y和z之间。 整个命题可表示为P(a,b,c)。
在教室里，T(x)：x在讲话，则命
式
题可符号化为：
x(S(x)R(x)T(x))。
2.2.1 谓词公式与翻译
（2）在我们班中，并非所有同学 都能取得优秀成绩。
解 令S(x)：x是同学， C(x)：x
2.2 在我们班中， E(x)：x能取得优
谓
秀成绩，则命题可符号化为：
词
x((S(x)C(x))E(x)) 。 或 者
词
公式；
公
（4）如果α是谓词公式，x是个体变元 ，则xα(x)，xα(x)和！xα(x)也
式
都是谓词公式；
（5）只有有限次地应用（1）～（4）构 成的符号串才是谓词公式。
2.2.1 谓词公式与翻译
由定义可知，谓词公式是由
原子公式、命题联结词、量词以
及圆括号按照上述规则组成的一
2.2 个符号串。因此，命题逻辑中的
、
谓 说明：显然P(a,b,c)为真，但
词
P(b,a,c)为假。所以个体变元的顺