离散数学 教案 第2章 复习总结

第二章一阶逻辑复习总结1一、本章主要内容及学习要求一阶逻辑演算是命题演算的继续和深入，它不仅研究命题间的逻辑结构，而且要考察命题间的内部性质。在命题演算中，基本组成单位是原子命题，并且把它看成是不可分解的。在谓词演算中，对于命题的内部逻辑结构作了进一步刻画分析，并由此引进了个体和谓词概念。在讨论谓词公式时引入量词及其辖域的概念，对于量词的谓词公式，也存在公式变换和推理理论。本章重点是带量词的公式变换，即前束范式；谓词演算的推理理论2二、典型题例分析例1

在一阶逻辑中将下列命题符号化：

(1)

每列火车都比某些汽车快。(2)某些汽车比所有的火车慢。(3)有一个且仅有一个偶数质数。(4)将符号!xP(x)表达成仅用、和谓词=构成的式子。3解：令F(x)：x是火车。G(x)：x是汽车。

H(x,y)：x比y快，则有：（1）.或者

（2）.或者

4解：令E(x)：x是偶数。P(x)：x是质数。则有：（3）.!x(E(x)∧P(x))

或者

x(E(x)∧P(x)∧y(E(y)∧P(y)→y=x))（4）.

!xP(x)x(P(x)∧yP((y)→y=x))5例2判断下面谓词公式的类型：1.

2.

3.

4.

5.

6.

7.

8.

9.

10.答案：1、4、5、8、9是永真式；2、10是矛盾式；其他是可满足式。6例3证明公式：xP(x)∧yP(y)是永假式。证明：假设公式xP(x)∧yP(y)不是永假式，那么至少存在一个个体域D几D上谓词的一种解释，使xP(x)与yP(y)同时为真。因为xP(x)为真，故在D中对任意个体x，P(x)都为真。yP(y)为真，则在D中，至少有某个个体c，使得P(c)为真，因而在此解释下，P(c)为假。但由xP(x)为真，可得P(c)为真，矛盾。因此，xP(x)∧yP(y)必是永假式。7例4求谓词公式的前束范式。

x(P(x)→Q(x))→(xP(x)→xQ(x))

解：x(P(x)→Q(x))→(xP(x)→xQ(x))

x(P(x)∨Q(x))→(xP(x)∨xQ(x))

x(P(x)∨Q(x))∨(xP(x)∨xQ(x))

x(P(x)∧Q(x))∨(xP(x)∨xQ(x))

x(P(x)∧Q(x))∨yP(y)∨zQ(z)xyz(P(x)∧Q(x))∨P(y)∨Q(z))8例5

判断下面两个推理的正误，并指出错误所在？1.①

前提引入②由①，US③

前提引入④由③，ES⑤

由②④，假言推理⑥

UG

分析在该推理过程中，对xF(x)

消去存在量词时，要求用特定的个体常项取代x，而不能用变项y取代x，所以③

～④步有错。92.①前提引入②由①，US③

由②，ES④

由③，UG⑤

由④，EG分析在该推理过程中，因yF(z,y)

中存在自由出现的个体变元z，因而不能使用ES规则，所以②～③步错了。10例4符号化下列命题，并推证其结论：任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。(个体域为人类集合)解：

设P(x)：x喜欢步行；Q(x)：x喜欢乘汽车；R(x)：x喜欢骑自行车。则本题可符号化为：x(P(x)→Q(x)),x(Q(x)∨R(x))，xR(x)xP(x)11证明：①xR(x)

前提引入

②R(c)

由①，ES

③x(Q(x)∨R(x))

前提引入

④Q(c)∨R(c)由③，US

⑤Q(c)

由②、④，析取三段论

⑥x(P(x)→Q(x)