离散期末复习资料

离散复习资料

作者：。。。

第一章 考点：

1、证明一个公式的真值？ 方法：第一，真值表 第二，等值演算

例题：判断(p ? q) ? (r ? s) ? (p ? r ? q ? s)的真值？

(p?q)?(r?s)?(p?r?q?s)

?(?p?q)?(?r?s)?p?r?q?s ?(?p?q)?p?(?r?s)?r?q?s ?q?p?s?r?q?s?1

2、通过等值演算求一个公式的主范式？ 例题：

3、证明一个完全集是极小完全集？

见课本18页定理1.8 第二章 考点

1、将一组命题符号化？ 例题：见课本51页

1、每个人都有自己喜欢的职业。

取论域为所有事物的集合。令

M(x):x是人， J(x):x是职业， L(x,y):x喜欢y。

“每个人都有自己喜欢的职业” 可以符号化为?x(M(x)??y(J(y)?L(x,y))) 2、有些职业是所有人都喜欢的。

取论域为所有事物的集合。令

M(x):x是人， J(x):x是职业， L(x,y):x喜欢y。

“有些职业是所有的人都喜欢的”可以符号化为

?x(J(x)??y(M(y)?L(y,x)))。

2、给定一组解释和赋值，计算出公式的真值？

带入解释和赋值

例题：

给定解释I和I中赋值v如下：

DI?{1,2}，aI?1，bI?2，fI(1)?2，fI(2)?1

PI(1,1)?PI(1,2)?1，PI(2,1)?PI(2,2)?0，v(x)?1，v(y)?1

计算下列公式在解释I和赋值I中v下的真值。

(1) P(a,f(x))?P(x,f(b))?P(f(y),x) 答案：0 (2) ?x?yP(y,x) 答案：1

3、判断一个公式是否为永真式？

方法一：对于蕴含式，取一组解释和赋值，让命题的前件为1，判断命题的后件 例题：判断?xP(x)??xQ(x)??x(P(x)?Q(x))是否为永真式？

解答： 若解释I使得I(?xP(x)??xQ(x))?1，则I(?xP(x))?1或I(?xQ(x))?1。 ① 若I(?xP(x))?1，则存在d?DI使得PI(d)?1，PI(d)?QI(d)?1。 ② 若I(?xQ(x))?1，则存在d?DI使得QI(d)?1，PI(d)?QI(d)?1。 因此，I(?x(P(x)?Q(x)))?1。 对于等值式

例子：(2) ??xA??x?A 任取解释I和I中赋值v，

I(??xA)(v)?1 当且仅当 I(?xA)(v)?0

当且仅当 存在d?DI使得I(A)(v[x/d])?0 当且仅当 存在d?DI使得I(?A)(v[x/d])?1 当且仅当 I(?x?A)(v)?1

这表明??xA??x?A是永真式。

方法二：对于蕴含式，取一组解释和赋值，让命题的后件为0，判断命题的前件 例题：判断?x(P(x)?Q(x))?(?xP(x)??xQ(x))是否为永真式？

若解释I使得I((?xP(x)??xQ(x)))?0，则I(?xP(x))?1且I(?xQ(x))?0。存在

d?DI使得PI(d)?1，又因为I(?xQ(x))?0，所以QI(d)?0，PI(d)?QI(d)?0。

因此，I(?x(P(x)?Q(x)))?0。

原式为永真式。

方法三：试着取几组解释和赋值做实验，若取得一组解释，使得命题为假，则命题为非永真

式。

例题： 判断?xP(x)??xQ(x)??x(P(x)?Q(x))是否为永真式。 给定解释I如下

DI?{d}， PI(d)?1， QI(d)?1

则I(?xP(x)??xQ(x)??x(P(x)?Q(x)))?1。 给定解释I?如下

DI??{a,b}，PI?(a)?1，PI?(b)?0，QI?(a)?0，QI?(b)?1

则I?(?xP(x)??xQ(x)??x(P(x)?Q(x)))?0。

原式为非永真可满足式。

方法四：对于嵌套的蕴含式，也采取去解释让前件为一的方法

例题：判断?x(A?B)?(A??xB)，其中x不是A的自由变元。是否为永真式？ 任取解释I和I中赋值v，若I(?x(A?B))(v)?I(A)(v)?1，则对于每个d?DI，

I(A?B)(v[x/d])?1，因为x不是A的自由变元，所以I(A)(v[x/d])?I(A)(v)?1，

因此I(B)(v[x/d])?1，I(?xB)(v)?1。这表明?x(A?B)?(A??xB)是永真式。 第三章 考点：

1、用公理系统的方法证明一个公式是永真式（带谓词的公式） 方法：构造重言式，并且应用5条公理（见课本60页） 例题：证明：|?Atxi??xiA，其中t对于A中的xi是可代入的。

公理四 重言式

|??xi?A??Atxi

|?(?xi?A??Atxi)?(Atxi???xi?A)

即|?Atxi??xiA

注意：课后题的结论以及习题的结论都可以直接应用！ 第四章 考点：

1、用归结法证明一个公式是永真式（带谓词的公式） 重点：谓词逻辑的归结法

例题： 1、证明：?x(P(x)?Q(x))|?/?xP(x)??xQ(x)

由语句?x(P(x)?Q(x))得到子句P(x)?Q(x)，由语句?(?xP(x)??xQ(x))得到子句

?P(a)和?Q(b)。显然，由这三个子句只能归结出子句Q(a)和P(b)。因此，

?x(P(x)?Q(x))|?/?xP(x)??xQ(x)

2、（重点） 任何喜欢步行的人都不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因此，有的人不喜欢步行。 解 首先将前提和结论符号化。取个体域为人的集合。

W(x)：x 喜欢步行。C(x)：x 喜欢乘汽车。B(x)：x 喜欢骑自行车。

“任何喜欢步行的人都不喜欢乘汽车”符号化为 ?x(W(x) ? ?C(x))

“每个人或者喜欢乘汽车或者喜欢骑自行车”符号化为 ?x(C(x) ? B(x))

“有的人不喜欢骑自行车”符号化为 ?x?B(x)。 “有的人不喜欢步行”符号化为 ?x?W(x)。

需要证明

?x(W(x) ? ?C(x))，?x(C(x) ? B(x))，?x?B(x) |= ?x?W(x) 将 ?x(W(x) ? ?C(x)) 化为斯科伦范式 ?x(?W(x) ? ?C(x))， 得出子句 ?W(x) ? ?C(x)。

?x(C(x) ? B(x)) 本身即是斯科伦范式，得出子句 C(x) ? B(x)。 将 ?x?B(x) 化为斯科伦范式 ?B(a)，得出子句 ?B(a)。 将 ??x?W(x) 化为斯科伦范式 ?xW(x)，得出子句 W(x)。

构造子句集 {?W(x) ? ?C(x)，C(x) ? B(x)，?B(a)，W(x)} 的一个反驳如下： ① ?W(x) ? ?C(x)

② ③ ④ ⑤

C(x) ? B(x) ?B(a) W(x) ?C(x)

由 ① 和 ④

⑥ B(x) 由 ② 和 ⑤ ⑦ □ 由 ③ 和 ⑥{x/a}

第五章 考点：

1、证明两个集合相等？

方法一:若对于任意X，X∈A<-->X∈B,则两个集合相等

方法二：若对于任意X，X∈A——>X∈B ∧ X∈B——>X∈A=1，则两个集合相等 方法三：集合的运算性质（最主要的是补交转换律） 方法四：集合的特征函数（不建议用）。 第六章 考点

1、给定一个关系图，写出它具有的性质（或给定一个关系，画出它的关系图） 例题：5．设A = {1, 2, 3}，A上的关系R1, R2, R3, R4, R5分别由图6.17给出，试 问：R1, R2, R3, R4, R5各有哪些性质？

解

R1：自反、对称、反对称、传递。 R2：对称。

R3：反自反、反对称。

R4：反自反、对称、反对称、传递。 R5：自反、传递。

2、给定一个关系，判断它是否为偏序，若为偏序（那是肯定的），写出它的8个元素（最大元、最小元、极大元、极小元、上界、下界，上确界、下确界），并可以画出哈斯图。 偏序定义：集合X上的关系R称为X上的偏序关系或偏序，当且仅当R是自反的、反对称的和传递的。

例题：18. 对于下列集合上的整除关系，画出哈斯图。对于集合｛2，3，4｝，求它的8个元素

(1) A = {1, 2, 3, 4, 6, 8, 12, 24} (2) B = {1, 2, 3,?, 12}

24 8 8 12 10 4 7 3 1

(1) {2, 3, 4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12和24，上确界为12，下界为1，下确界为1。

(2) {2, 3, 4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12，上确界为12，下界为1， …… 此处隐藏：1991字，全部文档内容请下载后查看。喜欢就下载吧 ……