离散复习资料

本文格式为Word版，下载可任意编辑——离散复习资料

离散复习资料

：姓名不详……

第一章考点：

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是可代入的。

x|??xi?A??Ati

公理四重言式

xx|?(?xi?A??Ati)?(Ati???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∈AX∈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}

2488121047213521

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

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