资源描述：
《离散数学考试题（卷）详细答案解析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（ØP⇄Q）Ù(P⇄RÚS)b)我今天进城，除非下雨。设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：ØQ→P或ØP→Qc)仅当你走，我将留下。设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P2.用谓词逻辑把下列命题符号化a)有些实数不是有理数设R(x)表示“x是实数”，Q
2、(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
3、(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）).Û(（PÙQÙØR）Ú(PÚØQÚØR))Ù((ØPÙQÙR)Ú（ØPÚØQÚR）)Û(PÚØQÚØR)Ù(ØPÚØQÚR)这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（ØPÙØQÙØ
4、R)Ú（ØPÙØQÙR)Ú（ØPÙQÙØR)Ú（PÙØQÙØR)Ú（PÙØQÙR)Ú（PÙQÙR)2.设个体域为{1,2,3}，求下列命题的真值（4分）a)"x$y(x+y=4)b)$y"x(x+y=4)a)Tb)F3.求"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)))1.判断下面命题的真假，并说明原因。（每小题2
5、分，共4分）a)（AÈB）－C=(A-B)È(A-C)b)若f是从集合A到集合B的入射函数，则
6、A
7、≤
8、B
9、a)真命题。因为（AÈB）－C=（AÈB）Ç~C=（AÇ~C）È（BÇ~C）=（A-C）È（B-C）b)真命题。因为如果f是从集合A到集合B的入射函数，则
10、ranf
11、=
12、A
13、，且ranfÍB,故命题成立。2.设A是有穷集，
14、A
15、=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？a)52b)5!=1203.设有偏序集，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下
16、确界，(5分)fgdebca图1B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.4.已知有限集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→Ø
17、F)→ØC,B→(A∧ØS)ÞB→Eb)"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→ECPb)证(1)$xØR(x)P(2)ØR(c)ES(
