离散数学考试题(后附详细答案)一、命题符号化(共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) 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))→∀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) 52 b) 5!=1206. 设有偏序集<A,≤>,其哈斯图如图1,求子集B={b,d,e}的最小元,最大元、极大元、极小元、上界集合、下界集合、上确界、下确界,(5分)f gB 的最小元就是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)]=n 2; 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)),∃x ⌝R(x) ⇒∃x ⌝P(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) ∃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. 设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 ×B ⇒x ∈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表示命题“在家瞧报”,命题符号化为:(⌝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))、⇔((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) 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))→∀y∃z(F(y)→G(z)) ⇔∃x∀y∃z((F(x)→G(x))→ (F(y)→G(z)))4.a) 真命题。