离散数学考试题详细答案

离散数学 考试题(后附详细答案)

一、命题符号化（共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) 对于所有非零实数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) F

3. 求?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!=120

6. 设有偏序集，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、

极小元、上界集合、下界集合、上确界、下确界，(5分) f g

d e

b c

a

图1

B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合是{a,b}、上确界是g、下确界是b.

7. 已知有限集S={a1,a2,…,an},N为自然数集合，R为实数集合，求下列集合的基数

S;P(S);N,N;P(N);R,R×R,{o,1}（写出即可）(6分)

K[S]=n; K[P(S)]=2; K[N]=?0,K[N]=?0, K[P(N)]=?; K[R]=?, K=[R×R]= ?,K[{0,1}]=

n

n

N

n

N

?

三、证明题（共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) 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 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)

2. 设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?，关系R满足：

<,>∈R，当且仅当< x1, x2>∈R1且∈R2。试证明：R是A×B上的等价关系。（10分） 证 任取,

∈A×B?x∈A? y∈B?∈R1?∈R2?<,>∈R，故R是自反的 任取<,>,

<,>∈R?∈R1?∈R2?∈R1?∈R2?<,>∈R.故R是对称的。

任取<,>,<,>∈R

<,>,<,>∈R?∈R1?∈R2?∈R1?∈R2?(∈R1?∈R1)?(∈R2?∈R2)? R1?∈R2?<,>∈R, 故R是传递的。

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

3. 用伯恩斯坦定理证明（0,1]和(a,b)等势。（10分） 证 构造函数f：（0,1]→(a,b)，f(x)=

abx?,显然f是入射函数 22x?a,显然g是入射函数， b?a2 构造函数g: (a,b)→（0,1]，g(x)? 故（0,1]和(a,b)等势。

2m12?m2???mr2?m1?m2???mr?sn2??由于?，所以?2

rrrr??

4. 设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R

的商集A/R有r个元素，证明：rs≥n2。（10分）

证 设商集A/R的r个等价类的元素个数分别为m1,m2,…,mr，由于一个划分对应一个等价

22关系，m1+m2+…+mr=n， m1?m2???mr2?s

2m12?m2???mr2?m1?m2???mr???由于?（r个数的平方的平均值大于等于这

rr??2sn22r个数的平均值的平方），所以?2，即rs?n

rr

四、应用题（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，∈R当且仅当从x到y有直接连接的道路，即

R={,,,,,,,} 那么该问题即变为求R的传递闭包。

?0?0??0?0?利用Warshal算法，求得t(R)=?0??0?0??0?1000100011001111111111000000000001001011110000000?0??0??0? 0??0?0??0??那么从城市x出发能到达的城市为(t(R)?IA)[{x}]?{y|?x,y??t(R)?x?y}， 故有(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}]??

离散数学 考试题答案

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S

表示命题“在家看报”，命题符号化为：（?P?Q）?(P?R?S) b) c) 2. a)

设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))))

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) 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))→?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) 52 b) 5!=120

6. B的最小元是b，无最大元、极大元是d和e、极小元是b、上界集合是{g}、下界集合

是{a,b}、上确界是g、下确界是b. 7. K[S]=n; K[P(S)]=2

N

n

; K[N]=?0,K[N]=?0, K[P(N)]=?; K[R]=?, K=[R×R]=

n

?,K[{0,1}]= ?

三、证明题（共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)→?C P

(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) 2. 证 任取,

∈A×B?x∈A? y∈B?∈R1?∈R2?<,>∈R，故R是自反的 任取<,>,

<,>∈R?∈R1?∈R2?∈R1?∈R2?<,>∈R.故R是对称的。

任取<,>,<,>∈R

<,>,<,>∈R?∈R1?∈R2?∈R1?∈R2?(∈R1?∈R1)?(∈R2?∈R2)? R1?∈R2?<,>∈R, 故R是传递的。

综上所述R是A×B上的等价关系。 3. 证 构造函数f：（0,1]→(a,b)，f(x)=

abx?,显然f是入射函数 22x?a,显然g是入射函数， b?a2 构造函数g: (a,b)→（0,1]，g(x)? 故（0,1]和(a,b)等势。

2m12?m2???mr2?m1?m2???mr?sn2??由于?，所以?2

rrrr??4. 证 设商集A/R的r个等价类的元素个数分别为m1,m2,…,mr，由于一个划分对应一个等

价关系，m1+m2+…+mr=n， m1?m2???mr?s

2m12?m2???mr2?m1?m2???mr???由于?（r个数的平方的平均值大于等于这

rr??2222sn22r个数的平均值的平方），所以?2，即rs?n

rr四、应用题（10分）

解 把8个城市作为集合A的元素，即A={a,b,c,d,e,,f,g,h}，在A上定义二元关系R，∈R当且仅当从x到y有直接连接的道路，即

R={,,,,,,,} 那么该问题即变为求R的传递闭包。

?0?0??0?0利用Warshal算法，求得t(R)=??0??0?0???01000100011001111111111000000000001001011110000000?0??0??0? ?0?0?0??0??那么从城市x出发能到达的城市为(t(R)?IA)[{x}]?{y|?x,y??t(R)?x?y}， 故有(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}]??

本文来源：https://www.bwwdw.com/article/dd7o.html