离散数学考试题详细答案

离散数学考试题(后附详细答案)一、命题符号化（共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(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）).(（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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)))a4.判断下面命题的真假，并说明原因。（每小题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!=1206.设有偏序集A,≤，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)fgdebc图1B的最小元是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)]=n2;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→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(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满足：x1,y1,x2,y2∈R，当且仅当x1,x2∈R1且y1,y2∈R2。试证明：R是A×B上的等价关系。（10分）证任取x,y,x,y∈A×Bx∈Ay∈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∈Rx,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,sR1y,t∈R2x,y,s,t∈R,故R是传递的。综上所述R是A×B上的等价关系。3.用伯恩斯坦定理证明（0,1]和(a,b)等势。（10分）证构造函数f：（0,1]→(a,b)，f(x)=22bxa,显然f是入射函数构造函数g:(a,b)→（0,1]，abaxxg)(,显然g是入射函数，故（0,1]和(a,b)等势。由于22122221rmmmrmmmrr，所以22rnrs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，smmmr22221由于22122221rmmmrmmmrr（r个数的平方的平均值大于等于这r个数的平均值的平方），所以22rnrs，即2nrs四、应用题（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，x,y∈R当且仅当从x到y有直接连接的道路，即R={a,b,a,c,b,g,g,b,c,f,f,e,b,d,d,f}那么该问题即变为求R的传递闭包。利用Warshal算法，求得t(R)=0000000001111010000100000000000000110000001100000111100001111110那么从城市x出发能到达的城市为})(,|{}])[{)((yxRtyxyxIRtA，故有},,,,,{}])[{)((gfedcbaIRtA},,,{}])[{)((gfedbIRtA},{}])[{)((fecIRtA},{}])[{)((fedIRtA}{}])[{)((efIRtA},,,{}])[{)((fedbgIRtA}])[{)((}])[{)((eIRteIRtAA离散数学考试题答案一、命题符号化（共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(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）).(（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R（PQR（PQR（PQR（PQR（PQR2.a)Tb)F3.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!=1206.B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.7.K[S]=n;K[P(S)]=n2;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→ECPb)证(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