讨论对象——个体的全体称为个体域（domain of i ndividuals），常用字母D表示。约定任何D都至少 含有一个成员 当讨论对象遍及一切客体时，个体域特称为全总域 （universe），用字母U表示 表示个体域上个体间运算的运算符与个体常元、变 元组成个体项（terms），例如a+b、x2+2、f(x)等
第13讲 谓词演算基本概念
-26-
谓词的自然语句形式化
由于确定了个体域，语句的形式化相对简单 当语句涉及不同类的个体时，给语句的形式化带来 一点复杂性
涉及全总个体域的某个局部的所有个体或某些个体时，要 使用限定谓词限定该局部 限定谓词与其他谓词之间应使用适当的联接词
━ 当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件 ━ 当限定谓词用于限定存在量词时，它必须作为合取词的合取 项
p: 2是偶数，可以表示成：O（2） q: 4是偶数，可以表示成：O（4）
第13讲 谓词演算基本概念
-5-
示例
6大于4 5大于3 2大于5 三个独立的原子命题，在命题演算中不能再分解 模式是：（ ）大于（ ）,大于是两个数之间的关系 L（x，y）：“x大于y”
6大于4 ，可以表示成：L（6，4）
如果个体域是复数集合，求x(x2<0)的真值
第13讲 谓词演算基本概念
-20-
谓词公式（predicate formula）
定义：以下条款规定的符号串称谓词公式，简称公式
(1)谓词填充式是公式，命题常元是公式(看作零元谓词)；
(2)如果A，B是公式，x为任一变元，那么(┐A)，(A→B)， (xA)，(x A)
命题推理能 力的局限性
第13讲 谓词演算基本概念 -3-
命题演算的局限
p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的
(所有人都)是要死的 (苏格拉底)是人 (苏格拉底)是要死的
1、命题演算将对确定对象进行判断的具有明确真值的陈述句 作为一个整体进行分析和处理，忽略了陈述句内部的结构
F(x): x怕死
当x的个体域是人类时
x ┐F(x)
当x的个体域是所有对象(全总域)时
H(x)：x是人（限定谓词,特性谓词） x(H(x)∧┐F(x))
x(H(x)→┐F(x)) ×
第13讲 谓词演算基本概念
-19-
存在量词(existential quantifier)
如果x的个体域是整数，P(x)表示“x=x+1”， 求xP(x)的真值 如果x的个体域是实数集合，求x(x2<0)的真 值；
x(P(x) ∧Q(x)) ∧ xS(x) →T(x) 对x(P(x) ∧Q(x)) ： 全称量词：；指导变元：x，作用域：P(x)∧Q(x)，其中x为约束 变元 对确定的个体域和谓词P、Q， x(P(x) ∧Q(x))是一个命题：个体 域中的任一对象，都具有谓词 P和Q定义的性质 1、给定了个体域和谓词的意义，那么谓词公式的真值只 取决于自由变元的取值，与约束变元无关。 (P(x 1) ∧Q(x1)) ∧ (P(x2) ∧Q(x2)) ∧ … ∧ (P(xn) ∧Q(xn)) 、给谓词公式中每一自由变元都指定具体的个体时，谓 对2 xS(x) ：
第13讲 谓词演算基本概念
-25-
谓词的自然语句形式化
例5.4
设个体域是人类
有人勇敢，但不是所有的人都勇敢
B(x)：x是勇敢的 x B(x) ∧ ┐ x B(x)
我为人人， 人人为我
H(x,y)：x为(帮助)y x H(我,x) ∧ x H(x,我)
勇敢者未必都是成功者
B(x)：x是勇敢的 ┐x (B(x) →S(x)) S(x)：x是成功的
━ P(0)∧P(1)∧P(2)∧P(3) ∧ …
第13讲 谓词演算基本概念
-14-
问题 P(x): x2 >= 6 P(0)、P(1)、P(2)为假，P(3)为真 存在不超过3的自然数x，使x2 >= 6 ━ P(0)∨P(1)∨P(2)∨P(3) 存在自然数x，使x2 >= 6 ━ P(0)∨P(1)∨P(2)∨P(3) ∨ …
-24-
第13讲 谓词演算基本概念
谓词公式的表述
P(x)：x每天花2小时学习英语，x的个 体域是学生的集合
xP(x) x┐P(x) xP(x) x┐P(x) ┐xP(x) ┐xP(x)
有的学生每天花2小时学习英语
有的学生每天不花2小时学习英语
所有学生每天都花2小时学习英语 所有学生每天都不花2小时学习英语 没有学生每天花2小时学习英语 不是所有的学生每天花2小时学习英语
词公式成为关于个体域的一个命题，可判定其真值 存在量词： ；指导变元：x，作用域：S(x) ，其中x为约束变元 对确定的个体域和谓词S， xS(x)是一个命题：个体域中有一个 对象，具有谓词S定义的性质 S(x1) ∨S(x2) ∨ … ∨ S(xn)
第13讲 谓词演算基本概念
对T(x) ：x没有任何量词约束，且x是个体变元，称为自由变元
2+x+1,0) yE(y2+y+1,0) yE(y （3） 表示：有一个实数x，满足x2+x+1=0 真值：假
xE(x2+x+1,0)
yE(y2,y) （4） xE(x2,y) zE(z2,y) 表示：有一个实数x，满足x2=y 真值：当y大于等于0时，为真；当y小于0时，为假；
第13讲 谓词演算基本概念 -23-
S(x)：x聪明 M(x)：x是人 x (M(x) ∧S(x)) ∧ ┐x (M(x) → S(x))
第13讲 谓词演算基本概念
-28-
谓词的自然语句形式化
所有步行的、骑马的或乘车的人，凡是口渴的，都 喝泉水
2+4=8 ，可以表示成： S（2，4，8）
第13讲 谓词演算基本概念
-7-
《离散数学》第13讲
谓词演算基本概念
Textbook Page 79 to 85
内容提要
谓词演算基本概念
个体、个体域 谓词 全称量词、存在量词 约束变元、自由变元
谓词公式 自然语句的形式化
第13讲 谓词演算基本概念
谓词命名式中的变元仅仅是谓词形式表示的一部分，没有 独立意义
第13讲 谓词演算基本概念
-12-
谓词填式
在谓词的空位处填入具体的个体常元或变元后得到 一个关于该个体的语句，这时它被称为谓词填式， 如M(scorates)，R(x)等 当谓词填式中所填个体都是常元时，得到一个命题， 有确定的真值
第13讲 谓词演算基本概念
-11-
谓词 （predicate）
刻画个体（或客体）的性质，或个体之间的关系的 模式称之为谓词
谓词是由谓语和空位所组成的，一个空位是一元谓 词，两个空位是二元谓词，三个空位是三元谓词 为增强可读性，常用变元来代替空位，如H(x)，L （x，y），S（x，y，z）等，这些式子叫做谓词命 名式，简称谓词
2、上述句子讨论事物的性质，并涉及所讨论的对象在全体和 个体上的联系
性质1：……是要死的：所有人都具有“要死的”性质
性质2：……是人： 苏格拉底 “是人”
两种主体：苏格拉底是所有人的组成部分 (元素)，因此也具有“要死 的”性质
第13讲 谓词演算基本概念 -4-
示例
2是偶数 4是偶数 p: 2是偶数;q:4是偶数 p、q是两个独立的原子命题 模式是：（ ）是偶数 O(x)：x是偶数
-22-
谓词公式的真值
设D为实数域，E(x，y)表示D上的关系“x=y”，L (x，y)表示“x < y”，则有
2+1) yL(0, y （1）xL(0, 表示：所有的实数x，满足0<x2+1
x2+1)
真值：真
xE(y2-2y-1,0) yE(y2-2y-1,0) （2） xE(x2-2x-1,0) 表示：有一个实数x，满足x2-2x-1=0 真值：真
如果x的个体域包含超过4的正整数，P(x)表示 “x2<10”， 求xP(x)的真值 如果x的个体域是实数集合， 求x(x2>=0)的真 值；
如果个体域是复数集合，求x(x2>=0)的真值
第13讲 谓词演算基本概念
-18-
存在量词(existential quantifier)
有的人不怕死
否定
每个同学都学过高等数学 P(x)：x学过高等数学；xP(x) 不是每个同学都学过高等数学 ┐xP(x) 有的同学学过法语 P(x)：x学过法语； xP(x) 并没有同学学过法语 ┐ xP(x)
有的同学没有学过高等数学
x ┐P(x)
语句 xP(x) 等价语句 ┐ x ┐P(x)
计算机专业基础课程
1.
授课人：张桂芸 dyxy1999@
PowerPoint Template_Sub
1
谓词演算基本概念
谓词演算永真式
2 3
谓词公式的前束范式
-2-
第13讲 谓词演算基本概念
命题演算的局限
所有人都是要死的，苏格拉底是人，那么苏格 拉底也是要死的。
p：所有人都是要死的 q：苏格拉底是人 r：苏格拉底是要死的 p∧q┝r：p∧q→r为永真式吗？
所有的人都是要死的 D(x): x是要死的 当x的个体域是人类时
xD(x)
当x的个体域是所有对象的集合(全总域)时
H(x)：x是人（限定谓词,特性谓词） x(H(x)→D(x)) x(H(x)∧D(x)) ×
第13讲 谓词演算基本概念
-17-
全称量词(universal quantifier)
5大于3 ，可以表示成： L（5，3） 2大于5 ，可以表示成： L（2，5）
第13讲 谓词演算基本概念 -6-