东南大学远程教育：《离散数学》课程教学资源（PPT课件讲稿）第二章 数理逻辑（谓词逻辑）

第二章谓词逻辑 §1谓词的概念与表示法 §2命题函数与量词 §3谓词公式与翻译 §4变元的约東 ■§5谓词演算的等价式与蕴含式 §6前束范式 §7谓词演算的推理理论

第二章 谓词逻辑 ◼ §1 谓词的概念与表示法 ◼ §2 命题函数与量词 ◼ §3 谓词公式与翻译 ◼ §4 变元的约束 ◼ §5 谓词演算的等价式与蕴含式 ◼ §6 前束范式 ◼ §7 谓词演算的推理理论

「§1谓词的概念与表示法 在研究命题逻辑中, 原子命题是命题演算中最基本的单位,不再对原子命题进行 分解, 这样会产生二大缺点 (1)不能研究命题的结构,成分和内部逻辑的特征 (2)也不可能表达二个原子命题所具有的共同特征,甚 至在命题逻辑中无法处理一些简单又常见的推理过程。 例:苏格拉底论证是正确的,但不能用命题逻辑的推理规则 推导出来。 “所有的人总是要死的。 ‘苏格拉底是人 “所以苏格拉底是要死的。”C

§1 谓词的概念与表示法 在研究命题逻辑中， 原子命题是命题演算中最基本的单位，不再对原子命题进行 分解， 这样会产生二大缺点： （1）不能研究命题的结构，成分和内部逻辑的特征； （2）也不可能表达二个原子命题所具有的共同特征，甚 至在命题逻辑中无法处理一些简单又常见的推理过程。 例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则 推导出来。 “所有的人总是要死的。 A “苏格拉底是人。 B “所以苏格拉底是要死的。” C

§1谓词的概念与表示法 1谓词: 《定义》:用以刻划客体的性质或关系的即是谓词 我们可把陈述句分解为二部分: 主语(名词,代词)和谓语(动词) 例:张华是学生,李明是学生。则可把它表示成: H:表示“是学生”,:表示“张华”,m:表示“李明”, 则可用下列符号表示上述二个命题:H(),H(m)。 H作为“谓词”(或者谓词字母)用大写英文字母表示, jm.为主语,称为“客体”或称“个体

§1 谓词的概念与表示法 1.谓词： 《定义》：用以刻划客体的性质或关系的即是谓词。 我们可把陈述句分解为二部分： 主语（名词，代词）和谓语（动词）。 例：张华是学生，李明是学生。则可把它表示成： H:表示“是学生”，j:表示“张华”，m:表示“李明”， 则可用下列符号表示上述二个命题：H(j)，H(m)。 H作为“谓词”（或者谓词字母）用大写英文字母表示， j,m为主语，称为“客体”或称“个体

「§1谓词的概念与表示法 (1)谓词填式:谓词字母后填以客体所得的式子。 例:H(a,b) (2)若谓词字母联系着一个客体,则称作一元谓词;若谓 词字母联系着二个客体,则称作二元谓词;若谓词字母联 系着n个客体,则称作n元谓词。 (3)客体的次序必须是有规定的。 例:河南省北接河北省 b 写成二元谓词为:L(n,b),但不能写成L(b,n)

§1 谓词的概念与表示法 （1）谓词填式：谓词字母后填以客体所得的式子。 例：H(a, b) （2）若谓词字母联系着一个客体，则称作一元谓词；若谓 词字母联系着二个客体，则称作二元谓词；若谓词字母联 系着n个客体，则称作n元谓词。 （3）客体的次序必须是有规定的。 例：河南省北接河北省。 n L b 写成二元谓词为：L(n,b)，但不能写成L(b,n)

§2命题函数与量词 1.命题函数 客体在谓词表达式中可以是任意的名词 例:C-“总是要死的。” 张三;t:老虎;e:桌子。 则C(),C(t),C(e)均表达了命题 在上面的例子中,C:表示“总是要死的”;x:表示变元 (客体变元),则C(x)表示“X总是要死的”,则称C(x) 为命题函数。 《定义》由一个谓词字母和一个非空的客体变元的集合所组 成的表达式,称为简单命题函数

§2 命题函数与量词 1. 命题函数 客体在谓词表达式中可以是任意的名词。 例：C—“总是要死的。” j：张三；t：老虎；e：桌子。 则C(j), C(t), C(e)均表达了命题。 在上面的例子中，C：表示“总是要死的”；x：表示变元 （客体变元），则C(x)表示“x总是要死的”，则称C(x) 为命题函数。 《定义》由一个谓词字母和一个非空的客体变元的集合所组 成的表达式，称为简单命题函数

§2命题函数与量词 讨论定义: (a)当简单命题函数仅有一个客体变元时,称为一元简 单命题函数 (b)若用任何客体去取代客体变元之后,则命题函数就 变为命题; (c)命题函数中客体变元的取值范围称为个体域(论述 域) 例:P(X)表示x是质数。这是一个命题函数。 其值取决于个体域。 可以将命题函数→命题,有两种方法:

§2 命题函数与量词 讨论定义： （a）当简单命题函数仅有一个客体变元时，称为一元简 单命题函数； （b）若用任何客体去取代客体变元之后，则命题函数就 变为命题； （c）命题函数中客体变元的取值范围称为个体域（论述 域）。 例：P(x)表示x是质数。这是一个命题函数。 其值取决于个体域。 可以将命题函数→命题，有两种方法：

§2命题函数与量词 a)将x取定一个值。如:P(4),P(5) b)将谓词量化。如:VxP(x),彐xP(x) 个体域的给定形式有二种: ①具体给定。 如:{j,e,t} ②全总个体域任意域:所有的个体从该域中取得

§2 命题函数与量词 a)将x取定一个值。如：P(4)，P(5) b)将谓词量化。如：xP(x)，xP(x) 个体域的给定形式有二种： ①具体给定。 如：｛j, e, t｝ ②全总个体域任意域：所有的个体从该域中取得

§2命题函数与量词 2量词 (1)全称量词 y”为全称量词符号,读作“对于所有的 对任 对一切 例:“这里所有的都是苹果” 可写成:VXA(x)或(v×)A(x) 几种形式的读法 VxP(×): “对所有的x,x是..”; XP(x):“对所有X,X不是 xP(x):“并不是对所有的x,ⅹ是.. xP(x):“并不是所有的x,x不是

§2 命题函数与量词 2.量词 （1）全称量词 “”为全称量词符号，读作“对于所有的”，“对任一 个”，“对一切”。 例：“这里所有的都是苹果” 可写成： xA(x)或(x)A(x) 几种形式的读法： · xP(x)： “对所有的x，x是…”； · x¬P(x) ： “对所有x，x不是…”； · ¬xP(x) ： “并不是对所有的x，x是…”； · ¬x¬P(x) ： “并不是所有的x，x不是…

§2命题函数与量词 例:将“对于所有的x和任何的y,如果ⅹ高于y,那么y不高 于x”写成命题表达形式。 解:VXy(G(Xy)->G(y,×) G(xy):X高于y (2)存在量词 “彐”为存在量词符号,读作“存在一个”,“对于 些”,“对于某些”,“至少存在一个”,“这里存在着 这样的”等等 “”表达式的读法: 彐xA(x):存在一个X,使x是 彐XA(x):存在一个X,使X不是…; XA(X):不存在一个x,使x是. xA(x):不存在一个X,使x不是

§2 命题函数与量词 例：将“对于所有的x和任何的y，如果x高于y，那么y不高 于x”写成命题表达形式。 解： x y(G(x,y)→ ¬ G(y,x)) G(x,y)：x高于y （2）存在量词 “”为存在量词符号，读作“存在一个”，“对于一 些”，“对于某些”，“至少存在一个”，“这里存在着 这样的”等等。 “”表达式的读法： ·  x A(x) ：存在一个x,使x是…； ·  x¬A(x) ：存在一个x, 使x不是…； · ¬ x A(x) ：不存在一个x, 使x是…； · ¬ x¬A(x) ：不存在一个x, 使x不是…

§2命题函数与量词 例:(a)存在一个人; (b)某个人很聪明; (c)某些实数是有理数 将(a),(b),(c)写成命题 解:规定:M(x:X是人;C(×):X是很聪明; R1(×):X是实数(特性谓词) R2(×):X是有理数。 则(a)彐xM(x); (b)彐(M(X)∧C(x); (C)彐X(R1(×)∧R2(X)。 (3)量化命题的真值:决定于给定的个体域 给定个体域:{a13以{a1a}中的每一个代入 vxP(×)Q(a1)vvQ(an)

§2 命题函数与量词 例：（a）存在一个人； （b）某个人很聪明； （c）某些实数是有理数 将（a）,（b）,（c）写成命题。 解：规定：M(x)：x是人；C(x)：x是很聪明； R1 (x)：x是实数(特性谓词) R2 (x)：x是有理数。 则 （a）  x M(x) ； （b）  x (M(x) C(x))； （c）  x (R1 (x)  R2 (x)) 。 （3）量化命题的真值：决定于给定的个体域 给定个体域：{a1…an }以{a1…an }中的每一个代入 xP(x)P(a1 )…  P(an ) xQ(x)Q(a1 )…  Q(an )