最新离散数学考试题详细答案.docx

最新离散数学考试题详细答案.docx

《最新离散数学考试题详细答案.docx》由会员分享，可在线阅读，更多相关《最新离散数学考试题详细答案.docx（11页珍藏版）》请在冰点文库上搜索。

最新离散数学考试题详细答案

离散数学考试题（后附详细答案）

一、命题符号化（共6小题，每小题3分，共计18分）

1.用命题逻辑把下列命题符号化

a）假如上午不下雨，我去看电影，否则就在家里读书或看报。

设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：

（ØP⇄Q）Ù（P⇄RÚS）

b）我今天进城，除非下雨。

设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：

ØQ→P或ØP→Q

c）仅当你走，我将留下。

设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：

Q→P

2.用谓词逻辑把下列命题符号化

a）有些实数不是有理数

设R（x）表示“x是实数”，Q（x）表示“x是有理数”，命题符号化为：

$x（R（x）ÙØQ（x））或Ø"x（R（x）→Q（x））

b）对于所有非零实数x，总存在y使得xy=1。

设R（x）表示“x是实数”，E（x,y）表示“x=y”,f（x,y）=xy,命题符号化为：

"x（R（x）ÙØE（x,0）→$y（R（y）ÙE（f（x,y）,1））））

c）f是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f（a）=b.

设F（f）表示“f是从A到B的函数”,A（x）表示“x∈A”,B（x）表示“x∈B”,E（x,y）表示“x=y”,命题符号化为：

F（f）⇄a（A（a）→b（B（b）E（f（a）,b）c（S（c）E（f（a）,c）→E（a,b））））

二、简答题（共6道题，共32分）

1.求命题公式（P→（Q→R））«（R→（Q→P））的主析取范式、主合取范式，并写出所有成真赋值。

（5分）

（P→（Q→R））«（R→（Q→P））Û（ØPÚØQÚR）«（PÚØQÚØR）

Û（（ØPÚØQÚR）→（PÚØQÚØR））（（PÚØQÚØR）→（ØPÚØQÚR））.

Û（（PQØR）Ú（PÚØQÚØR））（（ØPQR）Ú（ØPÚØQÚR））

Û（PÚØQÚØR）（ØPÚØQÚR）这是主合取范式

公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为

（ØPØQØRÚ（ØPØQRÚ（ØPQØRÚ（PØQØRÚ（PØQRÚ（PQR

2.设个体域为{1,2,3}，求下列命题的真值（4分）

a）"x$y（x+y=4）

b）$y"x（x+y=4）

a）Tb）F

3.求"x（F（x）→G（x））→（$xF（x）→$xG（x））的前束范式。

（4分）

"x（F（x）→G（x））→（$xF（x）→$xG（x））Û"x（F（x）→G（x））→（$yF（y）→$zG（z））

Û"x（F（x）→G（x））→"y$z（F（y）→G（z））Û$x"y$z（（F（x）→G（x））→（F（y）→G（z）））

4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）

a）（AÈB）－C=（A-B）È（A-C）

b）若f是从集合A到集合B的入射函数，则|A|≤|B|

a）真命题。

因为（AÈB）－C=（AÈB）Ç~C=（AÇ~C）È（BÇ~C）=（A-C）È（B-C）

b）真命题。

因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfÍB,故命题成立。

5.设A是有穷集，|A|=5，问（每小题2分，共4分）

a）A上有多少种不同的等价关系？

b）从A到A的不同双射函数有多少个？

a）52b）5!

=120

6.设有偏序集，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，（5分）

fg

de

bc

a

图1

B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.

7.已知有限集S={a1,a2,…,an},N为自然数集合，R为实数集合，求下列集合的基数S;P（S）;N,Nn;P（N）;R,R×R,{o,1}N（写出即可）（6分）

K[S]=n;K[P（S）]=

;K[N]=À0,K[Nn]=À0,K[P（N）]=À;K[R]=À,K=[R×R]=À,K[{0,1}N]=À

三、证明题（共3小题，共计40分）

1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）

a）A→（B∧C）,（E→ØF）→ØC,B→（A∧ØS）ÞB→E

b）"x（P（x）→ØQ（x））,"x（Q（x）∨R（x）），$xØR（x）Þ$xØP（x）

a）证

（1）BP（附加条件）

（2）B→（A∧ØS）P

（3）A∧ØST

（1）

（2）I

（4）AT（3）I

（5）A→（B∧C）P

（6）B∧CT（4）（5）I

（7）CT（6）I

（8）（E→ØF）→ØCP

（9）Ø（E→ØF）T（7）（8）I

（10）E∧FT（9）E

（11）ET（10）I

（12）B→ECP

b）证

（1）$xØR（x）P

（2）ØR（c）ES

（1）

（3）"x（Q（x）∨R（x））P

（4）Q（c）∨R（c）US（3）

（5）Q（c）T

（2）（4）I

（6）"x（P（x）→ØQ（x））P

（7）P（c）→ØQ（c）US（6）

（8）ØP（c）T（5）（7）I

（9）$xØP（x）EG（8）

2.设R1是A上的等价关系，R2是B上的等价关系，A≠Æ且B≠Æ，关系R满足：

<,>∈R，当且仅当∈R1且∈R2。

试证明：

R是A×B上的等价关系。

（10分）

证任取,

∈A×BÞx∈AÙy∈BÞ∈R1Ù∈R2Þ<,>∈R，故R是自反的

任取<,>,

<,>∈RÞ∈R1Ù∈R2Þ∈R1Ù∈R2Þ<,>∈R.故R是对称的。

任取<,>,<,>∈R

<,>,<,>∈RÞ∈R1Ù∈R2Ù∈R1Ù∈R2Þ（∈R1Ù∈R1）Ù（∈R2Ù∈R2）ÞR1Ù∈R2Þ<,>∈R,故R是传递的。

综上所述R是A×B上的等价关系。

3.用伯恩斯坦定理证明（0,1]和（a,b）等势。

（10分）

证构造函数f：

（0,1]→（a,b），f（x）=

显然f是入射函数

构造函数g:

（a,b）→（0,1]，

显然g是入射函数，

故（0,1]和（a,b）等势。

由于

，所以

4.设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：

rs≥n2。

（10分）

证设商集A/R的r个等价类的元素个数分别为m1,m2,…,mr，由于一个划分对应一个等价关系，m1+m2+…+mr=n，

由于

（r个数的平方的平均值大于等于这r个数的平均值的平方），所以

，即

四、应用题（10分）

在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f,g,h。

城市之间的直接连接的道路是单向的，有a→b,a→c,b→g,g→b,c→f,f→e,b→d,d→f.对每一个城市求出从它出发所能够到达的所有其他城市。

解把8个城市作为集合A的元素，即A={a,b,c,d,e,,f,g,h}，在A上定义二元关系R，∈R当且仅当从x到y有直接连接的道路，即

R={,,,,,,,}

那么该问题即变为求R的传递闭包。

利用Warshal算法，求得t（R）=

那么从城市x出发能到达的城市为

，

故有

离散数学考试题答案

一、命题符号化（共6小题，每小题3分，共计18分）

1.用命题逻辑把下列命题符号化

a）设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：

（ØP⇄Q）Ù（P⇄RÚS）

b）设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：

ØQ→P或ØP→Q

c）设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：

Q→P

2.用谓词逻辑把下列命题符号化

a）设R（x）表示“x是实数”，Q（x）表示“x是有理数”，命题符号化为：

$x（R（x）ÙØQ（x））或Ø"x（R（x）→Q（x））

b）设R（x）表示“x是实数”，E（x,y）表示“x=y”,f（x,y）=xy,命题符号化为：

"x（R（x）ÙØE（x,0）→$y（R（y）ÙE（f（x,y）,1））））

c）设F（f）表示“f是从A到B的函数”,A（x）表示“x∈A”,B（x）表示“x∈B”,E（x,y）表示“x=y”,命题符号化为：

F（f）⇄a（A（a）→b（B（b）E（f（a）,b）c（S（c）E（f（a）,c）→E（a,b））））

二、简答题（共6道题，共32分）

1.（P→（Q→R））«（R→（Q→P））Û（ØPÚØQÚR）«（PÚØQÚØR）

Û（（ØPÚØQÚR）→（PÚØQÚØR））（（PÚØQÚØR）→（ØPÚØQÚR））.

Û（（PQØR）Ú（PÚØQÚØR））（（ØPQR）Ú（ØPÚØQÚR））

Û（PÚØQÚØR）（ØPÚØQÚR）这是主合取范式

公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为

（ØPØQØRÚ（ØPØQRÚ（ØPQØRÚ（PØQØRÚ（PØQRÚ（PQR

2.a）Tb）F

3."x（F（x）→G（x））→（$xF（x）→$xG（x））Û"x（F（x）→G（x））→（$yF（y）→$zG（z））

Û"x（F（x）→G（x））→"y$z（F（y）→G（z））Û$x"y$z（（F（x）→G（x））→（F（y）→G（z）））

4.a）真命题。

因为（AÈB）－C=（AÈB）Ç~C=（AÇ~C）È（BÇ~C）=（A-C）È（B-C）

b）真命题。

因为如果f是从集合A到集合B的入射函数，则|ranf|=|A|，且ranfÍB,故命题成立。

5.a）52b）5!

=120

6.B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.

7.K[S]=n;K[P（S）]=

;K[N]=À0,K[Nn]=À0,K[P（N）]=À;K[R]=À,K=[R×R]=À,K[{0,1}N]=À

三、证明题（共3小题，共计40分）

1.a）证

（1）BP（附加条件）

（2）B→（A∧ØS）P

（3）A∧ØST

（1）

（2）I

（4）AT（3）I

（5）A→（B∧C）P

（6）B∧CT（4）（5）I

（7）CT（6）I

（8）（E→ØF）→ØCP

（9）Ø（E→ØF）T（7）（8）I

（10）E∧FT（9）E

（11）ET（10）I

（12）B→ECP

b）证

（1）$xØR（x）P

（2）ØR（c）ES

（1）

（3）"x（Q（x）∨R（x））P

（4）Q（c）∨R（c）US（3）

（5）Q（c）T

（2）（4）I

（6）"x（P（x）→ØQ（x））P

（7）P（c）→ØQ（c）US（6）

（8）ØP（c）T（5）（7）I

（9）$xØP（x）EG（8）

2.证任取,

∈A×BÞx∈AÙy∈BÞ∈R1Ù∈R2Þ<,>∈R，故R是自反的

任取<,>,

<,>∈RÞ∈R1Ù∈R2Þ∈R1Ù∈R2Þ<,>∈R.故R是对称的。

任取<,>,<,>∈R

<,>,<,>∈RÞ∈R1Ù∈R2Ù∈R1Ù∈R2Þ（∈R1Ù∈R1）Ù（∈R2Ù∈R2）ÞR1Ù∈R2Þ<,>∈R,故R是传递的。

综上所述R是A×B上的等价关系。

3.证构造函数f：

（0,1]→（a,b），f（x）=

显然f是入射函数

构造函数g:

（a,b）→（0,1]，

显然g是入射函数，

故（0,1]和（a,b）等势。

由于

，所以

4.证设商集A/R的r个等价类的元素个数分别为m1,m2,…,mr，由于一个划分对应一个等价关系，m1+m2+…+mr=n，

由于

（r个数的平方的平均值大于等于这r个数的平均值的平方），所以

，即

四、应用题（10分）

解把8个城市作为集合A的元素，即A={a,b,c,d,e,,f,g,h}，在A上定义二元关系R，∈R当且仅当从x到y有直接连接的道路，即

R={,,,,,,,}

那么该问题即变为求R的传递闭包。

利用Warshal算法，求得t（R）=

那么从城市x出发能到达的城市为

，

故有