离散数学（第二版） 课件 邹丽娜 3.2谓词公式

离散数学第3章谓词逻辑3.1谓词逻辑概述目录3.2谓词公式与解释3.3谓词公式的等值演算3.4谓词推理自然语言用谓词公式表示命题谓词个体量词个体常量个体变元函数用谓词公式表示命题【用谓词公式表示命题的一般步骤】用谓词公式表示不含量词的简单命题的方法和步骤：(1)找出命题中的谓词，用符号表示；(2)找出命题的主要个体对象，并用符号表示；(3)谓词公式，用逻辑连接词连接谓词；(4)检查所写的谓词公式是否表达了原命题的内容。例如：马丽的父亲与苏珊的父亲是同事

个体常量：a表示玛丽，b表示苏珊

函数：f(x)表示x的父亲

谓词：P(x,y)表示x和y是同事

原命题表示为：P(f(a),f(c))用谓词公式表示命题用谓词公式表示下列命题（不含量词）：

(1)3是素数。(2)2是奇数。

(3)张明和刘浩是同学。(4)李岚是长跑冠军。用谓词公式表示命题例:将下列命题谓词符号化2既是素数又是偶数F(x)：x是素数G(x)：x是偶数a:2F(a)G(a)如果杨庆是北京大学的学生，陈明也是北京大学的学生，那么杨庆与陈明是校友。

F(x):是北京大学的学生G(x,y):x与y是校友a:杨庆,b:陈明F(a)

F(b)G(a,b)练习将下列命题在一阶逻辑中用谓词符号化(1)周杰伦是一个男歌星．(2)若６大于４且４大于２，则６大于２．解(1)令F(x):x是一个男人,G(x):x是歌星

a:周杰伦

符号化:F(a)

G(a).

(2)令G(x,y):x大于y

a:6,b:4,c:2

符号化:G(a,b)

G(b,c)→G(a,c).在谓词前加上量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。3.2谓词公式思考：

xF(x),xF(x),F(x)的联系、区别？F(x)是不能确定真值的谓词

xF(x),xF(x)都是命题x称为约束变元谓词公式表示含量词的命题的方法和步骤(1)找出量词，确定辖域；(2)表示全称量词及其辖域所描述的命题，具体如下：a)用A(x)表示所属范围；b)用B(x)表示去掉量词后的命题；c)用形如

的公式表示原命题，(3)表示存在量词及其辖域所描述的命题，具体如下：a)用A(x)表示所属范围；b)用B(x)表示去掉量词后的命题；

c)用形如

的公式表示原命题(4)用逻辑联结词联结各个子公式。(5)检查例（1）所有人都呼吸.

（2）有的人吸烟.

含有量词的命题（讨论域为全总个体域）个体域为全总个体域.

设M(x):x是人；F(x):x呼吸；G(x):x吸烟（1）符号化为

x(M(x)

F(x))（真命题）

（2）符号化为

x(M(x)

G(x))（真命题）例（1）所有人都呼吸.

（2）有的人吸烟.个体域为人类集合（1）符号化为

xF(x)，其中F(x)：x呼吸（真命题）（2）符号化为

xG(x)，其中G(x)：x吸烟（真命题）

含有量词的命题（讨论域为具体域）3.2谓词公式谓词逻辑符号化几点说明不同的个体域，符号化形式可能不一样，命题真值也可能不同例如：

xG(x),其中G(x):x+9=6,当个体域取自然数集时真值为０；当个体域取实数集时真值为１.一般默认是全总个体域，即包含一切个体特性谓词：描述个体变元取值范围的谓词全称量化中，特性谓词常作为蕴涵式的前件

x（M(x)F(x))存在量化中，特性谓词常作为合取项之一

x(M(x)G(x))例

用谓词公式表示下列命题：(1)每个计算机系的学生都学离散数学。(2)有人喜欢吃苹果。例3.4

用谓词公式表示下列命题：所有人都吃饭存在不吃饭的人(3)没有不吃饭的人(4)不是所有的人都吃饭

x(M(x)E(x))命题符号化例：将下列命题符号化凡是学生都需要学习和考试F(x):x是学生；G(x):x学习；H(x):x考试

x(F(x)G(x)H(x))所有的汽车都比马车跑得快P(x)：x是汽车；Q(y)：y是马车；G(x,y)：x比y跑得快。

x

y(P(x)

Q(y)

G(x,y))

1.将下列命题符号化所有的汽车都比马车跑得快有的汽车比有的马车跑得快所有汽车比有的马车跑得快有的汽车比所有马车跑的快有的汽车不比所有马车跑得快并非所有汽车都比所有马车跑的快P(x)：x是汽车；Q(y)：y是马车；G(x,y)：x比y跑得快。2.找出下列公式中的量词辖域、是否存在自由变元，公式是否为闭公式(1)兔子比乌龟跑得快．(2)并非所有的兔子比所有的乌龟跑得快．(3)有的兔子比有的乌龟跑得快．设F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快.(1)

x

y(F(x)

G(y)→H(x,y))(2)

x

y(F(x)

G(y)→H(x,y))或

x

y(F(x)

G(y)

H(x,y))(3)

x

y(F(x)

G(y)

H(x,y))例题3.5：命题符号化例3.5：将下列命题符号化(4)有的兔子不比有的乌龟跑得快．设F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快.(4)

x

y(F(x)

G(y)

H(x,y))(5)没有两个跑得同样快的兔子F(x):x是兔子，L(x,y):x和y跑得同样快

xy(F(x)F(y)L(x,y))命题符号化注意事项根据命题的实际意义选取全称量词或存在量词多个量词同时出现时，不能随意颠倒顺序符号化：对任意的x，存在着y，使得x+y=5给定实数域F(x,y)：x+y=5

xyF(x,y)不同于y

xF(x,y)TF(1)存在小于５的奇数(2)并非每个实数都是有理数(3)没有不犯错误的人F(x):x<5,G(x):x是奇数

x(F(x)

G(x))(2)R(x):x是实数,Q(x):x是有理数

x(R(x)→Q(x))或

x(R(x)

Q(x))

(3)M(x):x是人,F(x):x犯错误

x(M(x)

F(x))或

x(M(x)→F(x))练习(4)参加考试的人未必都能取得好成绩．(5)有学生选修过本校开设的每一门数学课。练习F(x):x是参加考试的人,G(x):x取得好成绩

x(F(x)→G(x))或

x(F(x)

G(x))(5)s(x):x是学生,M(y):y是本校开设的数学课,E(x,y):x选修y

x(s(x)

y(M(y)→E(x,y)))

量词的辖域【量词的辖域】含有量词的公式中，被某个量词量化的子公式(或整个公式)称为该量词的辖域。在

x和

x的辖域中，x的所有出现都称为约束变元，A中不是约束出现的其它变项均称为自由变元.

x(P(x,y)

Q(x,z))

R(x)

x(F(x,y,z)

yG(x,y))

例

指出下列公式的约束变元、自由变元及量词的辖域练习是闭公式不是闭公式闭公式的意义：任何一个闭公式都表示一个命题；一个含有自由变元的公式不能表示一个命题。3.7练习谓词公式的解释（由符号到自然语言）3.8DI={安娜,布朗,比尔,卡特,查理,戴西,戴维,杜威}

F(x):x是一个学生；G(x,y):x与y是老乡,H(x,y):x与y是同学；F(x),G(a,y)及H(x,y)含有自由变元，即不是闭公式，因而不是命题。解释：令a=安娜，F(a):

安娜是一个学生；

x

yG(x,y)

:在论域中有两个对象是老乡；

xF(x)

:在论域中的所有对象都是学生；3.9练习去取经都会遇到妖怪(())构造一个可以使公式为真的解释和一个为假的解释解释I１：个体域D1为整数集Z;

H(x,y)：x大于y解释：对D中的每一个数，都存在一个比它小的数。是真命题

解释I2：个体域D2为正整数集Z+;

H(x,