离散数学考试题及详细参考答案.docx

文档介绍：该【离散数学考试题及详细参考答案 】是由【飞行的大山】上传分享，文档一共【4】页，该文档可以免费在线阅读，需要了解更多关于【离散数学考试题及详细参考答案 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。失散数学考试题(后附详细答案)
一、命题符号化(共6小题,每题3分,共计18分)
用命题逻辑把以下命题符号化
若是上午不下雨,我去看电影,否则就在家里读书或看报。
我今天进城,除非下雨。
仅当你走,我将留下。
用谓词逻辑把以下命题符号化
有些实数不是有理数
关于所有非零实数x,总存在y使得xy=1。
c)
f是从A到B的函数当且仅当关于每个
a∈A存在唯一的b∈B,使得f(a)=b.
二、简答题(共6道题,共
32分)
1.
求命题公式(P→(Q→R))
(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋
值。(5分)
2.
设个体域为{1,2,3},求以下命题的真值(
4
分)
a)
x
y(x+y=4)
b)
y
x(x+y=4)
3.
x(F(x)→G(x))→(
xF(x)
xG(x))
的前束范式。(4分)
4.
判断下面命题的真假,并说明原因。
(每题
2分,共4分)
a)
(A
B)-C=(A-B)
(A-C)
若f是从会集A到会集B的入射函数,则|A|≤|B|
设A是有穷集,|A|=5,问(每题2分,共4分)
A上有多少种不同样的等价关系?
从A到A的不同样双射函数有多少个?
设有偏序集<A,≤>,其哈斯图如图1,求子集B={b,d,e}的最小元,最大元、极大元、
极小元、上界会集、下界会集、上确界、下确界,
(5分)
fg
de
c
a
图1
7.
已知有限集
S={a1,a
2,,an},N
为自然数会集,
R为实数会集,求以下会集的基数
S;P(S);N,Nn;P(N);R,R
×R,{o,1}
N(写出即可)(6
分)
三、证明题(共
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)
2.
设R1是A上的等价关系,R2
是B上的等价关系,A
B
R满足:
<<x1,y1>,<x2,y2>>∈R,当且仅当<x1,x2>∈R1且<y1,y2>∈R2。试证明:R是A×B上的
等价关系。(10分)
3.
用伯恩斯坦定理证明(
0,1]和(a,b)等势。(10
分)
设R是会集A上的等价关系,A的元素个数为n,R作为会集有s个元素,若A关于R的商集A/R有r个元素,证明:rs≥n2。(10分)
四、应用题(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→
所能够到达的所有其他城市。
失散数学考试题答案
一、命题符号化(共6小题,每题3分,共计18分)
用命题逻辑把以下命题符号化
设P表示命题“上午下雨”,Q表示命题“我去看电影”,R表示命题“在家里读书”,S
表示命题“在家看报”,命题符号化为:

P?Q

(P?R

S)
b)设

P表示命题“我今天进城”,Q表示命题“天下雨”

Q→P

P→
Q
设P表示命题“你走”,Q表示命题“我留下”,命题符号化为:Q→P
用谓词逻辑把以下命题符号化
设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))))
设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
QR)→(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,
故主析取范式为
PQR
PQR
PQR
PQR
PQR
(PQR
2.
a)T
b)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))
yz(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)52
b)5!=120
6.
B的最小元是
b,无最大元、极大元是
d和e、极小元是b、上界会集是{g}、下界会集
是{a,b}、上确界是g、下确界是b.
[S]=n;K[P(S)]=2n;K[N]=0,K[Nn]=0,K[P(N)]=;K[R]=,K=[R×R]=
,K[{0,1}N]=
三、证明题(共3小题,共计40分)
1.
a)
证
(1)B
P(
附加条件)
(2)B→(A
S)
P
(3)
A
S
T(1)(2)I
(4)
A
T(3)I
(5)
A
→(B∧C)P
(6)
B
∧C
T(4)(5)I
(7)
C
T(6)I
(8)
(E
F)
CP
(9)
(E
F)
T(7)(8)I
(10)E
∧F
T(9)E
(11)E
T(10)I
(12)B
→E
CP
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)
证任取<x,y>,
<x,y>∈A×B
x∈Ay∈B
<x,x>∈R1
<y,y>∈R2
<<x,y>,<x,y>>∈R,故R是自反的
任取<<x,y>,<u,v>>,
<<x,y>,<u,v>>∈R<x,u>∈R1
<y,v>∈R2
<u,x>∈R1
<v,y>∈R2<<u,v>,<x,y>>∈R.
故R是对称的。
任取<<x,y>,<u,v>>,<<u,v>,<s,t>>
∈R
<<x,y>,<u,v>>,<<u,v>,<s,t>>
∈R<x,u>∈R1<y,v>∈R2
<u,s>∈R1
<v,t>∈R2
(<x,u>∈R1
<u,s>∈R1)
(<y,v>∈R2<v,t>∈R2)<x,s>R1
<y,t>∈R2
<<x,y>,<s,t>>
∈R,故R是传达的。
综上所述R是A×B上的等价关系。
:(0,1]
→(a,b)
a
b
,f(x)=x
,显然f是入射函数
2
2
构造函数g:(a,b)
→(0,1]
x
a
,g(x)
,显然g是入射函数,
b
a
故(0,1]和(a,b)等势。
m12
m22
mr2
m1
m2
mr
2
sn
2
,所以
由于
r
r
rr
2

m1,m2,,mr,由于一个划分对应一个等
价关系,m1+m2++mr=n,m12
m22
mr2
s
由于m12
m22
mr2
m1
m2
mr
2
(r个数的平方的平均值大于等于这
r
r
s
n2
,即rs
2
r个数的平均值的平方),所以
2
n
r
r
四、应用题(
10分)
解把8个城市作为会集
A的元素,即A={a,b,c,d,e,,f,g,h}
,在A上定义二元关系R,<x,y>
∈R当且仅当从x到y有直接连接的道路,即
R={<a,b>,<a,c>,<b,g>,<g,b>,<c,f>,<f,e>,<b,d>,<d,f>}
那么该问题即变为求R的传达闭包。
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
利用Warshal算法,求得t(R)=
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
那么从城市
x出发能到达的城市为(t(R)IA)[{x}]{y|x,y
t(R)xy},
故有(t(R)
IA)[{a}]{b,c,d,e,f,g}
(t(R)
IA)[{b}]
{d,e,f,g}
(t(R)
IA)[{c}]
{e,f}
(t(R)
IA)[{d}]
{e,f}
(t(R)
IA)[{f}]
{e}
(t(R)
IA)[{g}]
{b,d,e,f}
(t(R)
IA)[{e}]
(t(R)IA)[{e}]