《离散数学》全程练习册(2011)答案(讲解用)

第1章 命题逻辑一、单项选择题1．下列语句中不是命题的有（ C ）. A 9+5≤12 ； B. 1+3=5；C. 我用的计算机CPU 主频是1G 吗？；D.我要努力学习。

2. 下列语句是真命题为( C )．A. 1+2=5当且仅当2是偶数B. 如果1+2=3，则2是奇数C. 如果1+2=5，则2是奇数D. 你上网了吗？ 3. 设命题公式G ：)(R Q P ∧→⌝,则使公式G 取真值为1的P ，Q ，R 赋值分别是( D )0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A (4. 命题公式Q Q P→∨)(为 ( B )(A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 下列命题公式等值的是( C )BB A A QP Q Q P Q B A A B A A QP Q P ),()D (),()C ()(),()B (,)A (∧∨⌝∨∨⌝∨→→→⌝→→∨⌝∧⌝6. 设P ：我将去市里，Q ：我有时间．命题“我将去市里，仅当我有时间时”符号化为( B )QP Q P Q P P Q ⌝∨⌝↔→→)D ()C ()B ()A (7．设P ：我听课，Q ：我看小说．命题“我不能一边听课，一边看小说”的符号为（D ） A. Q P ⌝→ ； B. Q P →⌝； C. P Q ⌝∧⌝ ； D. )(Q P ∧⌝8. 命题公式)(Q P →⌝的主析取范式是( A )．(A) Q P ⌝∧ (B) Q P ∧⌝(C) Q P ∨⌝ (D) Q P ⌝∨9. 前提为：P Q P ,⌝→；则有效结论是( A,D )． (A) P (B) ⌝P (C) Q (D)⌝Q 10．下列表达式正确的有（ A, C ）A.Q Q P ⌝⇒→⌝)(； B. P Q P ⇒∨C.P Q P Q P⇔⌝∧∨∧)()(D. ()1P P Q →→⇔11．n 个命题变元可产生（ D ）个互不等值的极小项。

A ． n ； B ．n 2 ； C ． 2n ； D ． 2n二、填空题1. 设命题公式G ：P →⌝ (Q →P)，则使公式G2. 设P ：我们划船，G ：我们跑步，那么命题“我们不能既划船又跑步”可符号化为3. 设P ：他生病了，Q ：他出差了．R ：我会同意他请假. 则命题“如果他生病或出差了，4. 含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是5. 若命题变项P ，Q ，R 赋值为(1,0,1)，则命题公式G ＝)())((Q P R Q P ∨⌝↔→∧6. 命题公式P →⌝(P ∧Q )7. P,Q 为两个命题，当且仅当1，当且仅当P ∨Q 的真值为0．8. 给定两个命题公式A ，B ，若A ↔B ⇔1, 则称A 和B 时等值的，记作A ⇔B ． 9. 任意两个不同极小项的合取为永假式 ，全体极小项的析取式为永真式． 三、计算题1. 判断命题公式的类型.(1) (P ∧Q →R)→P ∧Q ∧⌝R ； (2) P →(P ∨Q ∨R)2. 通过求命题公式(P ∨Q)→R 的主合、析取范式，求其真值为0的真值指派． 解 方法1．等值演算法．(P ∨Q)→R ⇔⌝(P ∨Q)∨R ⇔(⌝P ∧⌝Q)∨R ⇔(⌝P ∨R)∧(⌝Q ∨R)⇔(⌝P ∨(Q ∧⌝Q)∨R)∧((P ∧⌝P)∨⌝Q ∨R) ⇔)()()()(R Q P R Q P R Q P R Q P ∨⌝∨⌝∧∨⌝∨∧∨⌝∨⌝∧∨∨⌝⇔)()()(R Q P R Q P R Q P ∨⌝∨∧∨⌝∨⌝∧∨∨⌝于是主合取范式为：(P ∨Q)→R ⇔ M 2∧ M 4∧M 6⇔)6,4,2(∏成真赋值000，001，011，101，111转为十进制数分别为0，1，3，5，7；分别对应于极小项m 0，m 1，m 3，m 5 ，m 7于是主析取范式为：(P ∨Q)→R ⇔ m 0∨m 1∨m 3∨m 5∨m 7⇔)7,5,3,1,0(∑四、构造下面推理的证明：1.前提：R →⌝Q ，R ∨S ，S →⌝Q ，P →Q ．结论：⌝P ． 证明 ① R →⌝Q 前提引入 ②S →⌝Q 前提引入 ③ R ∨S 前提引入 ④⌝Q ∨ ⌝Q ①②③构造性二难 ⑤⌝Q ④置换⑥ P →Q 前提引入⑦ ⌝P ⑤⑥拒取式 2.Q S P PR R Q S ⌝→⇒⌝∨⌝→∧,,)(证明①P ⌝前提引入 ②P R ∨⌝前提引入③R ⌝①②析取三段论 ④R Q S→∧)(前提引入 ⑤)(Q S ∧⌝③④拒取式 ⑥Q S ⌝∨⌝⑤置换 ⑦S附加前提引入 ⑧Q ⌝⑥⑦析取三段论3.F A F E D D C B A →⇒→∨∧→∨,证明： ①A 附加前提引入②B A ∨①附加 ③D C B A ∧→∨前提引入 ④D C ∧②③假言推理 ⑤D④化简 ⑥E D ∨⑤附加 ⑦F E D →∨前提引入 ⑧F⑥⑦假言推理第3章 集合及其运算一、单项选择题1. 设集合A={1,a}，则P(A)=( C )． A. {{1},{a}}B. {∅,{1},{a}}C. {∅,{1},{a,},{1,a}}D. {{1},{a},{1,a}}2. 设A,B,C 为任意三个集合，下列命题正确的是( C )． A. 若A ⋃B=A ⋃C ，则B=C B. 若A ⋂B=A ⋂C ，则B=CC. 若～A ⋃B=E 且A ⊇B ，则A=BD. 若A －B ＝∅，则A=B 3. 设A,B,C,D 为任意四个集合，下列命题正确是( A )．.A. (B ⋃C)×A=(B ×A)⋃(C ×A)B. (A ×B)×C ＝A ×(B ×C)C. (B ⋂C)×A=(B ×A)⋃(C ×A)D. A ⊆C 且B ⊆D ，则A ×C ＝B ×D4. 设a 是集合A 的元素，则以下正确的是( B )Aa A a A a a a ∈⊆⊆⊆}){D ()C (}){B (}){A (5. 设集合A={1,2,3,4},B ＝{2,4,6,9}，那么集合A ，B 的对称差A ⊕B ＝( C )(A) {1,3} (B) {2,4,6} (C) {1,3,6,9} (D) {1,2,3,4,6,9}6. 设集合A ＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是(B )(A) 1∈A (B) {{4,5}}⊂A(C) {1,2,3}⊆A (D) ∅∈A7. 设A, B, C 都是集合，如果A ⋂C ＝B ⋂C ，则有( C ) (A) A ＝B (B) A ≠B(C) 当A －C ＝B －C 时,有A=B (D) 当C=U 时, 有A ≠B8. 设集合A ＝{∅，a}，则P(A)＝ ( D )}},{},{},{,){D (}}}},{,{},{},{,){C (}},{},{},){{B (}},{},{,){A (a a A a a a a a a ∅∅∅∅∅∅∅∅∅∅9. 设A={1，2，3}，B={2，3，4，5}，C={2，3}，则（A ∪B ）⊕C 为（ C ） (A) {1，2} (B) {2，3} (C) {1，4，5} (D) {1，2，3} 二、填空题1.设A, B 代表集合，命题A -B =∅⇔A=B2. 设A, B 为任意集合，命题A -B =∅⇔A⊆B3. 设集合A={∅,{a}}，则A的幂集 4. 设集合5. 设集合A ＝{1,2,3,4}，B={a 6 由集合的吸收律，(A ⋃B)⋂7 有序对<a,b>=<x,y>三、计算题 1.设},{},,,{},,{},,,,,{42=521=41=54321=C B A E ,求 (A ⋂B)⋃~C ，P(A)－P(B)，A ⊕B ． (A ⋂B)⋃~C={1,3,5} P(A)－P(B) ={{4},{1,4}} A ⊕B={2,4,5}第4章 二元关系与函数一、单项选择题1. 设集合A={1,2,3,4}，A 上的二元关系R={<1,2>,<1,4>,<2,4>,<3,3>}，S={<1,4>,<2,3>,<2,4>,<3,2>}． 则关系( B )={<1,4>,<2,4>} A. R ⋃S B. R ⋂S C. R －S D. S －R2. 设集合A={a,b}上的二元关系R={<a,a>,<b,b>}，则R ( C )． A. 是等价关系但不是偏序关系 B 是偏序关系但不是等价关系C. 既是是等价关系又是偏序关系D. 既不是等价关系又不是偏序关系 3. 设函数f ：R →R ，f(a)=2a+1；g ：R →R ，g(a)=a 2，则( C )有反函数． A. g ⋅f B. f ⋅g C.f D. g ⋅4. 设集合A ＝{0,b},B={1,b,3},则A ⋃B 上的恒等关系是 ( B ). (A) {<0,0>,<1,1>,<3,3>} (B){<0,0>,<1,1>,<b,b>,<3,3>} (C) {<1,1>,<b,b>,<3,3>} (D) {<0,1>,<1,b><b,3>,<3,0>}5. 已知集合A ＝{a,b,c}上的二元关系R 的关系矩阵M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001011010，那么R ＝( D )，(A) {<a,b>,<b,a>,<b,b>,<a,c>} (B) {<a,b>,<b,a>,<b,b>,<c,b>}(C) {<a,b>,<a,a>,<b,b>,<c,a>} (D) {<a,b>,<b,a>,<b,b>,<c,a>} 6. 设A={a ，b ，c}，R={<a ，a >，<b ，b >}，则R 具有性质（ C ）(A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的7. 设R 是集合A 上的二元关系，I A 是A 上的恒等关系，如果R ⊂I A ，则下面四个命题中为真的是（ A ）(A) R 不是自反的 (B) R 不是传递的 (C) R 不是对称的 (D) R 不是反对称的8 设函数f ：N →N ，f(n)=n+1，下面四个命题中为真的是（ C ）(A) f 是满射的 (B) f 是双射的 (C) f 是单射函数 (D) f 存在反函数 9.设A={Φ，{1}，{1，3}，{1，2，3}}则A 上包含关系“⊆”的哈斯图为（ C ）二、填空题1. 设集合A={a,b,c,d}，A 上的二元关系R={<a,a>,<a,b>,<b,d>}，S={<a,d>,<b,c>, <b,d>,<c,b>}．则R ⋅S={<c,d>}；， R 2= {<a,a>,<a,b>,<a,d>}．2. 设集合A={1,2,3,4}，A 上的二元关系R={<1,1>,<1,3>,<2,1>,<3,3>,<3,4>,<4,3>}，则逆关系R－1的关系矩阵1-R M =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100110100000011．R－1的关系图为 ．3. 设集合A={a,b,c}上的二元关系R 的关系矩阵M R=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡000100011，则R 具有的性质是反对称性 且对称闭包M=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡01101011 4. 设集合A={a,b}，B={1,2}，则从A 到B 的所有函数是f 1={<a,1>,<b,1>}, f 2={<a,1>,<b,2>},f 3={<a,2>,<b,1>}, f 4={<a,2>,<b,2>}；其中双射有f 2={<a,1>,<b,2>}, f 3={<a,2>,<b,1>}5. 设A ，B 为有限集，且|A|=m,|B|=n,那末A 与B 间存在双射，当且仅当 m=n ．6. 如果关系R 是传递的， 则R •R ⊆ R ．7. 设集合A={1,2,3,4 }, B={6,8,12}, A 到B 的关系R ＝},,2,{B y A x x y y x ∈∈=><,那么R －1＝{<6,3>,<8,4>}1 4三、计算题1. 设集合A={a,b,c,d}上二元关系R 的关系矩阵为M R =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000011010001，求r(R)，s(R)，t(R)并画出R ，r(R)，s(R)，t(R)的关系图． 解 由M R 写出R 的集合表达式， R={<a,a>,<b,a>,<b,c>,<b,d>}．于是r(R)={ <a,a>,<b,a>,<b,c>,<b,d>,<b,b>,<c,c>,<d,d>} r(R)的关系图为 s(R)={ <a,a>,<b,a>,<b,c>,<b,d>，<a,b>,<c,b>,<d,b>} S(R)的关系图为 t(R)=R ⋃R 2⋃R 3 = ={ <a,a>,<b,a>,<b,c>,<b,d>}⋃{ <a,a>,<b,a>,}⋃{ <a,a>,<b,a>}={ <a,a>,<b,a>,<b,c>,<b,d>} t(R)的关系图为解:哈斯图如右．极大元：1,5, 6 极小元：0 最大元：无 最小元：03 设集合A={0,1,2,3,4}，定义A 上的二元关系R ＝{<x,y>⎪x,y ∈A ∧(x=y ∨x+y ∈A)} 试写出二元关系R 的集合表达式，并指出R 具有的性质． 解: 由题设， R ＝I A ⋃{<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<0,4>,<4,0>,<1,2>,<2,1>,<1,3>,<3,1>} 易知，R 具有自反性和对称性． 4.设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A 的一个分划，求由S 导出的等价关系. 解: R ＝I A ⋃{<2,3>,<3,2>} 5 设Ｚ为整数集，关系)}(mod ,|,{k b a Z b a b a R ≡∧∈><=为Z上等价关系，求R 的模K 等价关系的商集Z/R. Z/R={[0],[1],…,[k-1]}6设A={1，2，3，4，5}，A 上的偏序关系为求A 的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。