离散数学复习题及答案

① r?s前提引入

② ?s前提引入

③ ?r ①②拒取式 ④ (p?q)?r前提引入

⑤ ?(p?q) ③④拒取式 ⑥ ?p??q ⑤置换

(2)2是素数或合数. 若2是素数,则 是无理数. 若 是无理数,则4不是素数. 所以,如果4是素数,则2是合数. 解 用附加前提证明法构造证明

(1) 设 p:2是素数,q:2是合数, r: 是无理数,s:4是素数 (2) 推理的形式结构

前提:p?q, p?r, r??s 结论:s?q

(3) 证明

① s附加前提引入 ② p?r前提引入 ③ r??s前提引入

④ p??s ②③假言三段论 ⑤ ?p ①④拒取式 ⑥ p?q前提引入

⑦ q ⑤⑥析取三段论 (3)前提:?(p?q)?r, r?s, ?s, p 结论:?q 证明 用归缪法 ① q结论否定引入 ② r?s前提引入 ③ ?s前提引入

④ ?r ②③拒取式 ⑤ ?(p?q)?r前提引入

⑥ ?(p?q) ④⑤析取三段论 ⑦ ?p??q ⑥置换

⑧ ?p ①⑦析取三段论

⑨ p前提引入

??p?p ⑧⑨合取

(4) (P?(Q∨R))∧(┐S?┐Q)∧(P∧┐S)?R. 证:(1) P∧┐S P

(2) P T(1) I1 (3) ┐S T(1) I1 (4) P?(Q∨R) P

(5) Q∨R T (2),(4) I11 (6) ┐S?┐Q P

(7) ┐Q T(3),(6) I11 (8) R T(5),(7) I11

四.求下列公式的前束范式。

解:

(1)(?x)F(x)??(?x)G(x)

?(?x)F(x)?(?x)?G(x)(量词转换律)

?(?x)(F(x)??G(x))(量词分配)

(?x)F(x)??(?x)G(x) (2) ?(?x)F(x)?(?x)?G(x)(量词转换律) ?(?x)F(x)?(?y)?G(y)(换名) ?(?x)(F(x)?(?y)?G(y))(辖域扩张) ?(?x)(?y)(F(x)??G(y))(辖域扩张)

五.将下列命题符号化。

(1) 所有的人都长着黑头发;(2)有的人登上过月球;

(3) 没有人登上过木星; (4)在美国留学的学生未必都是亚洲人。 解:令M(x):x 为人。

(1) 令F(x):x长着黑头发。则?x (M(x)→ F(x))。

(2) 令G(x):x登上过月球。则?x (M(x)∧G(x))。 (3) 令H(x):x登上过木星。则

┐?x (M(x)∧H(x))。

(4) 令F(x):x是在美国留学的学生; G(x):x是亚洲人。则

┐?x (F(x)→ G(x))。

六.给定解释I 如下:

(a) 个体域D= {2,3}; (b) D中特定元素,a=2; (c) D上特定函数f (x) 为:f (2)=3, f (3)=2。 (d) D上特定谓词:

G(x,y): G(2,2)=G(2,3)=G(3,2)=1, G(3,3)=0; L(x,y): L(2,2)= L(3,3)=1, L(2,3)= L(3,2) =0; F(x):F(2)=0, F(3)=1 在I下求下列各式的真值。 (1) ?x(F(x)∧G(x,a));

(2) ?x(F(f(x)∧G(x,f(x))); (3) ?x?y L(x,y); (4) ?y?x L(x,y)

解:设公式(1)为A, 则

A ?(F(2)∧G(2,2))∧(F(3)∧G(3,2))

?(0∧1)∧(1∧1) ?0

(2) B ?(F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) ?(F(3)∧G(2,3))∨(F(2)∧G(3,2)) ? (1∧1)∨(0∧1) ? 1

(3) C ? (L(2, 2) ∨L(2,3))∧(L(3,2)∨L(3,3)) ? (1∨0)∧(0∨1) ? 1

(4) D ? (L(2,2) ∧ L(2,3))∨(L(3,2)∧L(3,3)) ? (1∧0)∨(0∧1) ? 0

七.求1到1000之间(包含1和1000在内)既不能被5和6整除,也不能被8整除的数有多少个? 解:

S = { x | x?Z∧1?x?1000 }

A = { x | x?S∧x可被5整除}

B = { x | x?S∧x可被6整除}

C = { x | x?S∧x可被8整除}

|A| = int(1000/5) = 200

|B| = int(1000/6) = 166

|C| = int(1000/8) = 125

|A∩B| = int(1000/lcm(5,6)) = 33

|A∩C| = int(1000/lcm(5,8)) = 25 |B∩C| = int(1000/lcm(6,8)) = 41 |A∩B∩C| = int(1000/lcm(5,6,8)) = 8 1000-(200+100+33+67)=600

八.A={1,2,3,4}, R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},求关系的定义域、值域与域并求 R的关系矩阵MR和关系图GR

?1100?

?0011?解: ?MR?? ?0000???

?0100?

关系图为

domR={1, 2, 4} ranR={1,2, 3, 4} fldR={1, 2, 3, 4}

九.设A={a,b,c,d}, R={,,,,},求 R和r(R), s(R), t(R)的关系图

R

r(R)

s(R)

t(R)

十.给出 A={1,2,3}上所有的等价关系 解:先求出A的所有划分:

?1={{1, 2, 3}}; ?2={{1}, {2, 3}}; ?3={{2}, {1, 3}}; ?4={{3}, {1, 2}}; ?5={ {1}, {2}, {3}}。

与这些划分一一对应的等价关系是: ?1: → 全域关系EA

?2: → R2={<2, 3>, <3, 2>}∪IA ?3: → R3={<1, 3>, <3, 1>}∪IA ?4: → R4={<1, 2>, <2, 1>}∪IA ?5: → 恒等关系IA

十一.设偏序集,用集合表示偏序关系,求A及它的极小元、最小元、极大元、最大元,设B={ b,c,d}, 求B的下界、上界、下确界、上确界.

解 A={ a, b, c, d, e, f, g, h }

R={,,,,,,,,}∪IA

极小元:a, b, c, g; 极大元:a, f, h; 没有最小元与最大元.

B的下界和最大下界都不存在; 上界有 d 和 f, 最小上界为 d.

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4