离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS)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))（PQR）(PQR)(（PQR）→(PQR)) ((PQR) →（PQR）).(（PQR）(PQR)) ((PQR) （PQR）)(PQR)(PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR（PQR（PQR（PQR（PQR（PQR2.设个体域为{1,2,3}，求下列命题的真值（4分）a)xy(x+y=4)b)yx (x+y=4)a) T b) 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))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z)))4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a) （AB ）－C=(A-B) (A-C)b) 若f 是从集合A 到集合B 的入射函数，则|A|≤|B|a) 真命题。

因为（AB ）－C=（AB ）~C=（A~C ）（B~C ）=（A-C ）（B-C ）b) 真命题。

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

5. 设A 是有穷集，|A|=5，问（每小题2分，共4分）a) A 上有多少种不同的等价关系b) 从A 到A 的不同双射函数有多少个a) 52 b) 5!=1206. 设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)fec图1B 的最小元是b ，无最大元、极大元是d 和e 、极小元是b 、上界集合是{g}、下界集合是{a,b}、上确界是g 、下确界是b.7. 已知有限集S={a 1,a 2,…,a n },N 为自然数集合，R 为实数集合，求下列集合的基数S;P(S);N,N n ;P(N);R,R ×R,{o,1}N （写出即可）(6分)K[S]=n; K[P(S)]=n2; K[N]=0,K[N n ]=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))，xR(x) xP(x)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)→C P(9) (E →F) T(7)(8) I(10) E ∧F T(9) E(11) E T(10) I(12) B →E CPb) 证 (1) xR(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) xP(x) EG(8)2. 设R 1是A 上的等价关系，R 2是B 上的等价关系，A ≠且B ≠，关系R 满足：<<x 1,y 1>,<x 2,y 2>>∈R ，当且仅当< x 1, x 2>∈R 1且<y 1,y 2>∈R 2。

试证明：R 是A ×B 上的等价关系。

（10分） 证 任取<x,y>,<x,y>∈A ×Bx ∈A y ∈B<x,x>∈R 1<y,y>∈R 2<<x,y>,<x,y>>∈R ，故R 是自反的任取<<x,y>,<u,v>>,<<x,y>,<u,v>>∈R<x,u>∈R 1<y,v>∈R 2<u,x>∈R 1<v,y>∈R 2<<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>∈R 1<y,v>∈R 2<u,s>∈R 1<v,t>∈R 2(<x,u>∈R 1<u,s>∈R 1)(<y,v>∈R 2<v,t>∈R 2)<x,s> R 1<y,t>∈R 2<<x,y>,<s,t>>∈R, 故R 是传递的。

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

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

（10分）证 构造函数f ：（0,1]→(a,b)，f(x)=22b x a +,显然f 是入射函数 构造函数g: (a,b)→（0,1]，ab a x x g --=)(,显然g 是入射函数， 故（0,1]和(a,b)等势。

由于22122221⎪⎭⎫ ⎝⎛+++≥+++r m m m r m m m r r ΛΛ，所以22r n r s ≥4. 设R 是集合A 上的等价关系，A 的元素个数为n ，R 作为集合有s 个元素，若A 关于R的商集A/R 有r 个元素，证明：rs ≥n 2。

（10分）证 设商集A/R 的r 个等价类的元素个数分别为m 1,m 2,…,m r ，由于一个划分对应一个等价关系，m 1+m 2+…+m r =n ， s m m m r =+++22221Λ 由于22122221⎪⎭⎫ ⎝⎛+++≥+++r m m m r m m m r r ΛΛ（r 个数的平方的平均值大于等于这r 个数的平均值的平方），所以22rn r s ≥，即2n rs ≥四、应用题（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 出发能到达的城市为})(,|{}])[{)((y x R t y x y x I R t A ≠∧>∈<=-， 故有},,,,,{}])[{)((g f e d c b a I R t A =-},,,{}])[{)((g f e d b I R t A =-},{}])[{)((f e c I R t A =-},{}])[{)((f e d I R t A =-}{}])[{)((e f I R t A =-},,,{}])[{)((f e d b g I R t A =-φ=-=-}])[{)((}])[{)((e I R t e I R t A A离散数学 考试题答案一、命题符号化（共6小题，每小题3分，共计18分）1. 用命题逻辑把下列命题符号化a) 设P 表示命题“上午下雨”，Q 表示命题“我去看电影”，R 表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS)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))（PQR）(PQR)(（PQR）→(PQR)) ((PQR) →（PQR）).(（PQR）(PQR)) ((PQR) （PQR）)(PQR)(PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR（PQR（PQR（PQR（PQR（PQR2.a) T b) F3.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)) xyz((F(x)→G(x))→(F(y)→G(z)))4.a) 真命题。