离散数学及其应用课件第2章第1节

离散数学及其应用1第2章谓词逻辑2.1谓词逻辑的基本概念2.2谓词合式公式2.3谓词公式的解释和分类2.4谓词演算的关系式2.5前束范式2.6谓词演算的推理22.1谓词逻辑的基本概念2.1.1个体词和谓词定义2.1.1个体词是指可以独立存在的客体，可以是一个具体的事物或抽象的概念，是原子命题所描述的对象。

谓词是用来说明个体的性质或个体间的关系。例如，小王是个大学生

3大于23谓词个体词个体词个体词谓词谓词

形如“b是A”类型的命题可表达为A(b)；表示多个个体间关系的命题，可表达为B(a，b)，或P(a，b，c)定义2.1.2

和一个个体相联系的谓词称为一元谓词，和二个个体相联系的谓词称为二元谓词，和n个个体相联系的谓词称为n元谓词。

个体常元

表示具体的或特定的个体，如a，b，c，

等；个体变元

表示抽象的或泛指的个体，如x，y，z，

等。

谓词常项

表示具体性质或关系的谓词，R(a)表示a是人；

谓词变项

表示抽象或泛指的谓词

，如：P(a)表示a具有P性质。4谓词表达式和命题函数定义2.1.3

一个原子命题可以用一个谓词常项P和几个个体常元，如a，b，c，

，表示成P(a，b，c，

)的形式。称P(a，b，c，

)为原子命题或命题的谓词表达式。

一个谓词常项P和几个个体变元如x，y，z，

表示成P(x，y，z，

)的形式，称为命题函数，其中的个体变元可以代表任意一个个体。注意：命题的谓词表达式是有真值的，命题函数的真值是不确定的。5例题写出下列命题的谓词表达式。

1.小王和小李是大学生。解：设A(x)：x是大学生。a：小王，b：小李。

A(a)

A(b)2.

北京是中国的首都。解：设F(x，y)：x是y的首都。a：北京，b：中国。F(a，b)3.如果你来，他就走。解：设P(x)：x来。Q(x)：x走。a：你，b：他。

P(a)

Q(b)6例题（续）4.如果3

2，2

1，则3

1。解：设B(x，y)：x

y。a：3，b：2，c：1。则

：

B(a，b)

B(b，c)

B(a，c)武汉位于北京和广州之间。解：设Q(x，y，z)：y位于x和z之间。a：北京，b：广州，c：武汉。Q(a，c，b)7个体域定义2.1.4命题函数中，个体变元的取值范围称为个体域或论述域。

个体域可以是有限的，也可以是无限的。把宇宙中一切事物作为对象的的集合称为全总个体域。通常，没有特别说明时，个体变元的论述域是指全总个体域。如：A(x)表示：x是大学生。个体域：华工计科1班学生，则A(x)是永真式。个体域：华工附中1班学生，则A(x)是永假式。个体域：xx公司员工，其中有些是大学生，有些不是大学生，则对有些人，A(x)为真，对有些人，A(x)为假。8例题给出执行语句“If

P(x)then

x：=1”以后x的值，其中P(x)为语句“x

1”，且执行到该语句时x的值如下：1)x=02)x=13)x=2解1)若x=0，P(x)为语句“0

1”，真值为0，不执行赋值语句“x：=1”，所以x=0。2)若x=1，P(x)为语句“1

1”，真值为0，不执行赋值语句“x：=1”，所以x=1。3)若x=2，P(x)为语句“2

1”，真值为1，执行赋值语句“x：=1”，所以x=1。92.1.2量词定义2.1.5表示个体常元或个体变元之间数量关系的词称为量词。量词有两种：全称量词

符号：

x表示对个体域“所有的x”，“每一个x”，“一切x”等。存在量词

符号：

x表示个体域中“存在这样的x”，“某个x”，“至少有一个x”或“有一些x”等。

xF(x)表示个体域中所有个体都有性质F

xF(x)表示个体域中存在个体有性质F10例题假设F(x)表示x选修离散数学，x的个体域是这个班的同学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

当个体域是这个班的同学时：

xF(x)

xF(x)若个体域是全总个体域时，要引入一个新的谓词表示个体的取值范围。称这个表示个体范围的谓词为特性谓词。11例题假设F(x)表示x选修离散数学，将下面的两个命题符号化。这个班的所有学生都选修离散数学这个班有些学生选修离散数学解

（没有特别说明时个体域是全总个体域）设特性谓词S(x)：表示x是这个班的同学，

x(S(x)

F(x))

x(S(x)

F(x))注意：在使用全称量词时，

特性谓词和表示个体性质的谓词构成条件关系式；

在使用存在量词时，特性谓词和表示个体性质的谓词构成合取关系式。12例题在个体域分别为：(a):自然数集合，(b):实数集合时，将下列命题符号化，并给出它们的真值。对于任意的x，均有x2−3x+2=(x−1)(x−2);存在x，使得x+5=2。解

假设F(x)：x2−3x+2=(x−1)(x−2)，G(x)：x+5=2。(a)个体域为自然数集合。符号化为：

xF(x)，真值为1。符号化为：

xG(x)，真值为0。(b)个体域为实数集合。符号化为：

xF(x)，真值为1。符号化为：

xG(x)，真值为1。13例题用谓词逻辑将下列命题符号化。所有的偶数均能被2整除。解

设A(x)：x是偶数，B(x)：x能被2整除。

x(A(x)

B(x))这个班有些学生有电脑。解设A(x)：x是这个班的学生，B(x)：x有电脑。

x(A(x)

B(x))。14例题（续）没有不犯错误的人。解设A(x)：x是人，B(x)：x犯错误。

x(A(x)

B(x))。尽管有人聪明，但未必一切人都聪明。解设A(x)：x是人，B(x)：x聪明。

x(A(x)

B(x))

x(A(x)

B(x))15例题（续）5.有些人喜欢某些体育运动。解

设A(x)：x是人，B(y)：y是体育运动，

C(x，y)：x喜欢y。

x(A(x)

y(B(y)

C(x，y)))。6.并非所有的工作都可以由一些机器人来完成。解设A(x)：x是工作，B(x，y)：x可以由y来完成，

R(x)：x是机器人。

x(A(x)

y(R(y)

B(x，y)))。16量词当论述域中的元素个数有限时，例如，论述域为n个元素的集合{a1，a2，a3，

an}时，有

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)

x

A(x)

A(a1)

A(a2)

A(a3)

A(an)17例题若P(x)是语句“x2>10”，论述域为不超过4的正整数，

xP(x)和

x

P(x)的真值是什么？

解

由于论述域为{1，2，3，4}，命题

xP(x)为

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(1)即“12>10”为假，所以

x

P(x)为假。命题

xP(x)为

x

P(x)

P(1)

P(2)

P(3)

P(4)而P(4)即“42>10”为真，所以

x

P(x)为真。18例题设P(x，y)表示“x+y>10”，论述域为实数，

x

yP(x，y)和

y

xP