左孝凌离散数学课件2.3谓词公式与翻译.ppt

1、1,离散数学(Discrete Mathematics),2,第二章 谓词逻辑,2.1谓词的概念与表示 2.2命题函数与量词 2.3谓词公式与翻译 2.4变元的约束 2.5谓词演算的等价式与蕴含式 2.6前束范式 2.7谓词演算的推理理论,3,2.3谓词公式与翻译,定义1：n元谓词A(x1，x2.xn) 称为谓词演算的原子公式。 定义2：谓词演算的合式公式,可由下述各条组成: 原子公式是合式公式。 若A 是合式公式，则(A)也是合式公式。 若A，B是合式公式，则(A B)，(A B)，(A B)，(A B)也是合式公式。 若A是合式公式，x是A中出现的任何变元,则(x)A , (x)A，也是合

2、式公式。 只有有限次应用(1)(4)得到的公式是合式公式. 约定：最外层括号可以省略；量词后面如果有括号，则不能省略,一、谓词公式,二、谓词公式的翻译（符号化）,把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化；一般，符号化的步骤如下： (1)正确理解给定命题。必要时把命题改述，使其中每个原子命题、原子命题之间的关系明显表达出来。 (2)把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。 (3)找出恰当量词。应注意全称量词后跟条件式，存在量词后跟合取式。 (4)用恰当的联结词把给定命题表示出来。,2.3谓词公式与翻译,例题1 并非每个实数都是有理数。,

3、设 R(x)：x是实数。 Q（x）：X是有理数。 每个实数都是有理数表示为：,并非每个实数都是有理数表示为：,例题2 没有不犯错误的人,设 M(x)：x 是人。 F(x)：x犯错误。 “存在不犯错误的人”表示为：,等价于“任何人都要犯错误”或“所有人都要犯错误”。所以此命题也可符号化为：,解 本语句即为“不存在不犯错误的人”。,“不存在不犯错误的人”表示为：,例题3 尽管有人聪明，但未必一切人都聪明。,解 设 M(x)：x是人。 P(x)：x是聪明的。 命题符号化为：,由于人们对命题的文字叙述含意理解的不同，强调的重点不同，会影响到命题符号化的形式不同。见例题4。,例题4 这只大红书柜摆满了那

4、些古书。,解法1 这只大红书柜摆满了那些古书。,x,y,设 F(x,y)：x摆满了y,再对x和y加以限制,R(x)：x是大红书柜,Q(y)：y是古书,a：这只 b：那些,此时可把命题符号化为：,解法2,设 A(x)：x是书柜,B(x)：x是大的,C(x)：x是红的,D(y)：y是古老的,E(y)：y是图书,F(x,y)：x摆满了y,a ：这只 b：那些,此时可把命题符号化为：,解法1中R(x)表示x是大红书柜,解法2中A(x) B(x) C(x)也可表示大红书柜,但用A(x) B(x) C(x)将更方便于对书柜的大小颜色进行讨论,对个体刻划深度的不同就可翻译成不同的谓词公式.,8,练习,例1：

5、在谓词逻辑中将下列命题符号化. （1）凡正数都大于零。 （2）存在小于2的素数。 （3）没有不能表示成分数的有理数。 （4）并不是所有参加考试的人都能取得好成绩。 解：,（1）凡正数都大于零 解：令M(x):x是正数。F(x): x大于零。则符号化为：（x）(M(x)F(x) （2）存在小于2的素数。 解：令E(x): x小于2。S(x):x是素数。则符号化为： （x)(E(x)S(x)真值为0。,10,练习1,（3）没有不能表示成分数的有理数。 解：令D(x): x是有理数。F(x):x能表示成分数。 则符号化为： (x)(D(x) F(x) 或 (x)(D(x) F(x) 真值为。 （4）

6、并不是所有参加考试的人都能取得好成绩。 解：令M(x)：x是人.Q(x):x参加考试。H(x):x能取得好成绩。则符号化为： (x)( (M(x)Q(x)H(x) ) 或 (x)( (M(x)Q(x) H(x) ),11,练习2,1、 在谓词逻辑中将下列命题符号化. （1）所有运动员都钦佩某些教练. （2）有些运动员不钦佩教练. 设：L(x):x是运动员 J(y):y是教练 A(x,y):x钦佩y (1) (x)(L(x) （y)(J(y)A(x,y) (2)（x)(L(x) (y)(J(y)A(x,y),12,练习2,2、在谓词逻辑中将下列命题符号化. （1） P63 (6)那位戴眼镜的用功

7、的大学生在看这本大而厚的巨著. （2）P63 (7) :f在a点连续，当且仅当对每个0，存在一个0，使得对所有x，若x-a ,则f(x)-f(a)。 解: (1)设：S(x):x是大学生. A(x):x戴眼镜. B(x):x用功. E(y):y是大的. G(y):y是厚的. D(y):y是巨著. F(x,y):x看y.a:那位 b:这本 (1)符号化为: A(a)B(a)S(a)E(b)G(b)D(b)F(a,b),13,练习2,（2）设：P(x,y):x在y连续. Q(x,y):x大于y. (2)符号化为: P(f,a)()(Q(,0) ()Q(,0) (x)(Q(, x-a)Q(, f(x)-f(a) ) 当且仅当： 每个0: ()Q(,0) 存在0：() Q(,0) 对所有x，若x-a ,则f(x)-f(a)： (x)(Q(, x-a)Q(, f(x)-f(a),1,2,3,f在a点连续，当且仅当对每个0，存在一个0，使得对所有x，若x-a ,则f(x)-f(a)。,14,第