离散数学复习题
一、单项选择题
1．对任意集合A 、B 、C ，下述论断正确的是 【 A 】
（A ）若A ∈B ，B ?C ，则 A ∈C （B ）若A ∈B ，B ?C ，则 A ?C
（C ）若A ?B ，B ∈C ，则 A ∈C （D ）若A ?B ，B ∈C ，则 A ?C
2．设{}
{}a a A ,=，则下列选项错误的是 【 B 】 （A ）{})(A P a ∈ （B ）{})(A P a ? （C ）{}{
})(A P A ∈ （D ）{}{})(A P A ? 3．设{}c b a A ,,=上的关系如下，有传递关系的有 【 D 】
（A ）{}><><><><=a b b a a c c a R ,,,,,,,1 （B ）{}><><=a c c a R ,,,2
（C ）{}><><><><=c b a b c c b a R ,,,,,,,3 （D ）{},,4><=a a R
4．R 是A 上的自反关系，则 【 B 】
（A ）R R R ?ο （B ）R R R ο? （C ）A I R R =I （D ）A I R R =ο
5．4K 中含3条边的不同构生成子图有 【 C 】
（A ）1个 （B ）2个 （C ）3个 （D ）4个
6．设E V G ,=为无向图，V v u ∈,,若v u ,连通，则 【 D 】
（A ）0),(>v u d （B ）0),(=v u d （C ）0),( 7．欧拉回路是 【 B 】 （A ）路径 （B ）简单回路 （C ）既是基本回路也是简单回路 （D ）既非基本回路也非简单回路 8．5阶无向完全图的边数是 【 B 】： （A ）5 （B ）10 （C ）15 （D ）20 9．设A ＝{}c b a ,, ，B ＝{}e d c b ,,, ，C ＝{}c b ,，则（A ∪B ）⊕ C 为 【 C 】 （A ）{}b a , （B ）{}c b , （C ）{}e d a ,, （D ）{}c b a ,, 10．设{ }φ=A ，))((A P P B =则下列选项错误的是 【 D 】 （A ）B ∈φ （B ）{ }B ∈φ （C ）{}{}B ∈φ （D ）{}{})(,A P ∈φφ 11．集合{ }10,,2,1Λ=A 上的关系{}A y A x y x y x R ∈∈=+><=,,10|,, 则R 的性质为 【 B 】 （A ）自反的 （B ）对称的 （C ）传递的、对称的 （D ）反自反的、传递的 12．设R 是非空集A 上的二元关系，则R 的对称闭包s(R)＝ 【 B 】 （A ）A I R ? （B ）R R ~? （C ）A I R - （D ）R R ~? 13．若简单图G 与其补图G 同构，称G 为自补图，则含有5个结点不同构的无向自补图的 个数为 【 C 】 （A ）0 （B ）1 （C ）2 （D ）3 14．设E V G ,=为无向图，V v u ∈,,若v u ,连通，则 【 D 】 （A ）0),(>v u d （B ）0),(=v u d （C ）0),( 15．欧拉回路是 【 B 】 （A ）路径 （B ）简单回路 （C ）既是基本回路也是简单回路 （D ）既非基本回路也非简单回路 16．n 个结点的无向完全图的边数是 【 D 】： （A ）)1(-n n （B ）2n （C ）n 2 （D ）2/)1(-n n 17．设P:我将去镇上,Q:我有时间。命题“我将去镇上,仅当我有时间时”符号化为【 A 】 (A) P →Q, (B) Q →P , (C) Q ?P , (D) ?Q ∨?P 18．下面哪个命题是命题“2是偶数或－3是负数”的否定？ 【 C 】 (A) 2是偶数或－3不是负数, (B) 2是奇数或－3不是负数, (C) 2不是偶数且－3不是负数, (D) 2是奇数且－3是不负数, 19．下面哪个联结词运算不可交换 : 【 B 】 (A) ∧, (B) → , (C) ∨ , (D) ? 20． 命题公式(P ∧(P →Q))→Q 是 ; 【 C 】 (A) 矛盾式, (B) 蕴含式, (C) 重言式 , (D) 等值式 21．下列命题联结词集合中,哪个是最小联结词组; 【 C 】 (A) {}??,, (B) {}∧∨?,, (C) {} ↑ (D) {}→∧, 22．下面那一个命题是假命题; 【 A 】 (A) 如果2是偶数,那么一个公式的析取范式唯一, (B) 如果2是偶数,那么一个公式的析取范式不唯一, (C) 如果2是奇数,那么一个公式的析取范式唯一, (D) 如果2是奇数,那么一个公式的析取范式不唯一 23．谓词公式)())()((x Q y yR x P x →?∨?中变元x 是; 【 D 】 （A ）自由变元, (B) 约束变元, (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元 24．设)(x A :x 是人, )(x B :x 犯错误,命题“没有不犯错误的人”符号化为; 【 D 】 (A)))()((x B x A x ∧?, (B)))()((x B x A x ?→??, (C) ))()((x B x A x ∧??, (D) ))()((x B x A x ?∧?? 25．命题公式? (P ∧Q)→R 的成真赋值为; 【 B 】 (A)000, 001,110 (B) 001, 011, 101,110,111 (C)全体赋值 (D) 无 26．下面语句中哪个是真命题； 【 D 】 (A) 我在说谎, (B) 严禁吸烟 , (C) 如果1+2=3,那么雪是黑的, (D) 如果1+2=5,那么雪是黑的 27．设P:我们划船,Q:我们跑步。命题“我们不能既划船又跑步”符号化为【 B 】 (A) ?P ∧?Q, (B) ?P ∨?Q , (C) ?（P ?Q ）, (D) P ??Q 28．下面哪个命题是命题“2是偶数或－3是负数”的否定？【 C 】。 (B) 2是偶数或－3不是负数, (B) 2是奇数或－3不是负数, (C) 2不是偶数且－3不是负数, (D) 2是奇数且－3是不负数, 29．下面哪个联结词运算不可交换【 C 】。 (A) ∧, (B) ∨, (C) →, (D) ? 30． 下面哪个命题公式是重言式 【 B 】。 (A) (P →Q)∧(Q →P), (B) (P ∧Q)→P, (C) (?P ∨Q)∧?(?P ∧?Q) , (D) ?（P ∨Q ） 31．下列命题联结词集合中,哪个不是最小联结词组【 C 】。 (A) {}∧?,, (B) {}→∧, (C) {}∧∨?,, (D) {} ↑ 32．命题公式P →Q ∧R 的对偶式是【 D 】。 (C) P →（Q ∨R ）, （B ）P ∧（Q ∨R ）， （C ）?P ∨（Q ∧R ）， （D ）?P ∧（Q ∨R ） 33．谓词公式)())()((x Q y yR x P x →?∨?中变元x 是【 D 】。 （A ）自由变元, (B) 约束变元, (C) 既不是自由变元也不是约束变元, (D) 既是自由变元也是约束变元 34．设)(x C :x 是运动员, )(x G :x 是强壮的,命题“没有一个运动员不是强壮的”符号化为 【 C 】。 (A)))()((x G x C x ?∧??, (B)))()((x G x C x ?→??, (C) ))()((x G x C x ?∧??, (D) ))()((x G x C x ?→?? 35．),(y x yP x ??的否定是【 B 】。 (A) ),(y x P y x ???， (B) ),(y x P y x ??? ，(C) ),(y x P y x ???， (D) ),(y x P y x ??? 36．在谓词演算中，下列各式正确的是【 A 】： (A) ),(),(y x xA y y x yA x ?????, (B) ),(),(y x xA y y x yA x ?????, (C) ),(),(y x xB y y x yA x ?????, (D) ),(),(y x yA x y x yA x ????? 二、填空题 1.若集合A 的基数10=A ，则其幂集的基数=)(A p 1024 。 2.设{}Z x Z n n x x x A ∈∈+=<<=,,37,200100|，则=||A 15 。 3.设N 表示非负整数集，，R ：N →N ，xRy 定义为x+2y ＝10，则Dom(R)＝{0,2,4,6,8,10} Ran(R)＝{5,4,3,2,1,0} 4.A ={}24,12,10,8,6,5,4,3,2,R 是A 上的整除关系，那么A 的极大元是 10，24 ,极小元是 2， 3，5 ,。 5.设A={ }3,2,1上的关系{}><><><><=3,3,3,1,2,1,1,1R ，则R 具备 反对称性 、传递性，R 不具备 自反性、反自反性和对称性。 6.设G=（n,m ）是简单图,v 是G 中度数为k 的结点，e 是G 中的一条边，则G －e 中有n 个 结点，m －1 条边。 7. 3个结点可构成 4 个不同构的简单无向图。 8.具有p 个顶点的完全图K p 有2-p p 个生成树，p ≥2。 9.设G 是一个有k 个支的图，如果S 是G 的割集，则G-S 恰有 k+1 个支。 10.设A={ }2,1 ，则A ⊕A=Φ ，=A 2 。 11.集合{}{ }a A ，φ=的幂集=)(A P {}{}{}{}{}{}a a ,,,,φφφ 。 12.设R 是集合{ }10,,2,1Λ上的模7同余关系，则. []=R 2 {}9,2 。 13. A={}24,12,10,8,6,5,4,3,2,R 是A 上的整除关系，那么A 的极大元是 10，24 ,极小元是 2， 3，5 ,。 14.整数集上的小于关系“＜”具有 反自反 、 反对称 和 传递 性。 15.设G=（n,m ）是简单图,v 是G 中度数为k 的结点，e 是G 中的一条边，则G －v 中有n －1 个结点，m －k 条边。 16.3个结点可构成 4 个不同构的简单无向图。 17.具有p 个顶点的完全图K p 有2-p p 个生成树，p ≥2。 18.设S 是连通图G=（V ，E ）的割集，则G-S 恰有 2 个支。 19.设P:我生病,Q:我去学校看电影 (1) 命题“我虽然生病但我仍去学校”符号化为 P ∧Q 。 (2) 命题“只有在生病的时候，我才不去学校”符号化为P ??Q 。 20. 设P 、Q 为两个命题，德摩根律可表示为Q P Q P ?∨??∧?)(，（或 Q P Q P ?∧??∨?)(） ， 吸收律可表示为P Q P p ?∨∧)( （或P Q P p ?∧∨)(）。 21.公式)(Q P →?的主析取范式为Q P ?∧, 主合取范式的编码表示为310M M M ∧∧。 22.),()),(),((y x xP z y G y x F y x ?∧∧??中,x ?的作用域为)),(),((z y G y x F y ∧?, y ?的作用域为 )),(),((z y G y x F ∧, x ?的作用域为),(y x P 。 23.谓词公式)()(x xG x xF ?∧?的前束范式为)()((y G x F y x ∧??。 24.设P:我有钱,Q:我去看电影 (1) 命题“如果我有钱, 那么我就去看电影”符号化为Q P →。 (2) 命题“虽然我有钱, 但我不去看电影”符号化为Q P ?∧。 25.命题公式)(S Q P ?∧∨的成真赋值为 010， 100， 101， 110，111 , 成假赋值为 000， 001，011。 26. 公式)(Q P →?的主析取范式为Q P ?∧, 主合取范式的编码表示为310M M M ∧∧。 27. ),()),(),((y x xP z y Q y x P y x ?∧∧??中,x ?的作用域为)),(),((z y Q y x P y ∧?, y ?的作用域为 )),(),((z y Q y x P ∧, x ?的作用域为),(y x P 。 28.谓词公式)()()(y yR x xQ x xP ?∨?→?的前束范式为))()()((y R z Q x P y z x ∨→???。 三、计算题 1、用等值演算法化简并判断下列公式的类型(?P ∧(?Q ∧R))∨(Q ∧R)∨(P ∧Q) 解：原式=(?P ∧(?Q ∧R))∨((Q ∨P)∧R) =((?P ∧?Q)∧R))∨((Q ∨P)∧R) =(?(P ∨Q)∧R))∨((Q ∨P)∧R) =(?(P ∨Q)∨(Q ∨P))∧R) =(?(P ∨Q)∨(P ∨Q))∧R) = T ∧R =R 故原式为可满足式 2、求命题公式(?p ∨?q)→（p ??q ）的合取范式、析取范式、主合取范式和主析取范 式。 解：合取范式： (?p ∨?q)→（p ??q ）=?(?p ∨?q)∨（（p →?q ）∧（?q →p ）） =?(?p ∨?q)∨（?p ∨?q ）∧（p ∨??q ） = (p ∧q)∨（?p ∨?q ）∧（p ∨q ） = p ∨q 析取范式： (?p ∨?q)→（p ??q ）=?(?p ∨?q)∨（（p ∧?q ）∨（?p ∧q ）） = (p ∧q)∨（p ∧?q ）∨（?p ∧q ） 主合取范式：(?p ∨?q)→（p ??q ）= p ∨q （=0M ） 主析取范式：(?p ∨?q)→（p ??q ）=(p ∧q)∨（p ∧?q ）∨（?p ∧q ）=2 10m m m ∨∨ 3、给定集合A ＝{}3,2,1.0，且A 中有关系：R={}2/1,,|,i j i j A j i j i =+=∈或 S={} 2,,|,+=∈j i A j i j i ，计算R оS 4、在120名学生参加考试，这次考试有A ，B ，C 共3道题，考试结果如下：有12人3道题 都做对了，20人做对了A 题和B 题，16人做对了A 题和C 题，28人做对了B 题和C 题，做 对了A 题的有48人，做对了B 题的有56人，还有16人一道题也没做对，求做对了C 题的 有多少人？ 解：设A,B,C 分别为做对A 题、B 题、C 题的人构成的集合， 故由题意有： ,48=A 56=B ,20=B A I ,16=C A I ,28=C B I 16=C B A Y Y 10416120=-=C B A Y Y 根据包含排斥原理可知： ,C B A C B C A B A C B A C B A I I I I I Y Y +---++= C ＝20+16+ 28+104 —12—48—56 ＝52 故做对C 题的有52人。 5、在1000名大学毕业生的调查中，有804人掌握了英语，205人掌握了日语，190人掌 握了俄语，125人既掌握了英语又掌握了日语，57人既掌握了日语又掌握了俄语，85人既 掌握了英语又掌握了俄语，求这1000名大学生中，英语、日语、俄语全掌握的有多少人。 解：设A,B,C 分别为掌握了英语、日语、俄语的人的集合， 则1000A B C =U U ， A B I 为既掌握英语又掌握日语的集；A C I 为掌握英语和俄语，B C I 为掌握日语和 俄语的人的集合，A B C I I 为三种都掌握的人的集合， 故由题意得： ,804=A ,250=B ,190=C ,125=B A I ,85=C A I ,57=C B I 1000A B C =U U ,C B C A B A C B A C B A C B A I I I Y Y I I +++---= ＝1000－804－ 250－190 ＋125＋85＋57 ＝23 于是，英语、日语、俄语全掌握的只有23人。 6、设集合A={}e d c b a ,,,,上的二元关系为, R={}??????????????????????????e e e d d d e c c c e b c b b b e a d a c a b a a a ,,,,,,,,,,,,,,,,,,,,,,,, （1）写出R 的关系矩阵。（2）验证（A ，R ）是偏续集。（3）画出Hasse 图。 7、（1）设集合A={}c b a ,,,)(A P 是集合A 的幂集，画出（)(A P ，?）的Hasse 图。 （2）设X={ }4,3,2,1，R={}??????????????????2,1,2,4,1,4,3,4,2,3,3,33,1,1,3,1,1，写出R 的关系矩阵，画出关系图。 8、已知有向图D ＝ 求 :（1）D 的邻接矩阵； （2）D 中1v 到4v 长度为4的通路数为多少？ （3）D 中长度小于等于4的通路有多少？其中有多少条是回路？ 9、已知图G ＝ 求G 的可达性矩阵P 。 10、用真值表法求命题公式((p →(p ∨q)) →(q ∧r)) ?(?p ∨r ）的主析取范式和主合取 范式。 四、证明题 1、设A ，B ，C 为任意三个集合，证明A ∩（B\C ）＝（A ∩B ）\（A ∩C ） 证：? (\)x A B C ?∈I ，则x A ∈且\x B C ∈ 即而x A ∈且x B ∈但x C ∈， 于是x A B ∈I 但x A C ∈I ，即()\()x A B A C ∈I I 。 从而 (\)()\()A B C A B A C ?I I I ?反之，()\()x A B A C ?∈I I ，有x A B ∈I 但x A C ∈I ，即x A ∈且x B ∈但 x C ∈。 于是\x B C ∈且，即(\)x A B C ∈I ， 从而 ()\()(\)A B A C A B C ?I I I 。 由集合相等的定义得：(\)()\()A B C A B A C =I I I 3 e 7 2、设A ，B ，C 为任意三个集合，证明： A －（B ∪C ）=（A －B ）∩（A －C ） 证：对任意的x ∈x A －（B ∪C ）?∈x A ∧?x B ∪C ?∈x A ∧)(C x B x ∈∨∈? ?∈x A ∧)(C x B x ∈?∧∈? ?∈x A ∧C x B x ?∧? ?（∈x A ∧)()C x A x B x ?∧∈∧? ?∈x A －B ∧)C A x -∈ ?∈x （A －B ）∩)(C A - 所以 A －（B ∪C ）=（A －B ）∩（A －C ） 3、写出下面推理的形式证明：如果数a 是实数，则它不是有理数就是无理数。如果a 不能表示成分数，则它不是有理数。a 是实数且它不能表示成分数，所以a 是无理数。 解 设命题，p ：a 是实数， q ：a 是有理数， r ：a 是无理数， s ： a 能表示成分数。 前提：)(r q p ∨→,q s ?→?, s p ?∧ 结论：r 证明：① s p ?∧ 前提引入 ② p ① 化简 ③ s ? ②化简 ④ )(r q p ∨→ 前提引入 ⑤ r q ∨ ②④假言推理 ⑥ q s ?→? 前提引入 ⑦ q ? ③⑥假言推理 ⑧ r ⑤⑦析取三段论 4、写出下面推理的形式证明：如果今天是星期一，则要进行英语或离散数学考试。如果今 天英语老师有会，则不考英语。今天是星期一，英语老师有会。所以今天进行离散数学考试。 解 符号化题目中的命题，设p ：今天是星期一，q ：进行英语考试，r ：进行离散数学考试，s ：英语老师有会。 前提：)(r q p ∨→,q s ?→, p, s 结论：r 证明：①)(r q p ∨→ 前提引入 ②p 前提引入 ③r q ∨ ①②假言推理 ④q s ?→ 前提引入 ⑤s 前提引入 ⑥q ? ④⑤假言推理 ⑦r ③⑥析取三段论 5、在自然推理系统P 中，用附加前提引入法构造下面的推理证明： 前提：P →(Q →S)，? R ∨P , Q 结论：R →S 证明： (1)?R ∨P 前提引人 (2) R →P (1)置换 (3)R 附加前提引人 (4)P (2)(3)分离 (5)P →(Q →S) 前提引入 (6)Q →S (4)(5)分离 (7)Q 前提引人 (8)S (6)(7)分离 (9)R →S 条件证明规则 6、在自然推理系统P 中，构造下面的推理证明： 前提：P ∨Q ，P →R ，Q →S ， 结论：S ∨R 证明: (1) P ∨Q 前提引入 (2)?P →Q (1)置换 (3) Q →S 前提引入 (4) →S (2)(3)三段论 (5)?S →P (4)置换 (6) P →R 前提引入 (7) ?SR (5)(6)三段论 (8)S ∨R (7)置换 7、书上114页定理7.9及证明过程。 8、设无向图G 中只有两个奇度顶点u 与v ，试证明u 与v 必连通。 证明：用反证法。假设u 与v 不连通，即u 与v 之间无通路，则u 与v 处于G 的不同连通分支中。不妨设u 在G1，v 在G2中。于是，G1与G2作为G 的子图，他们中均只含有一个奇度顶点，这与握手定理的推论矛盾。 9、设n 阶无向简单图G 有m 条边，已知m ≥2 1(n-1)(n-2)+1，证明G 必连通。 证明： （1）任何n 阶简单图的 边数m 均小于等于完全图Kn 的边数2 1n(n-1)。 （2）若G 中无孤立点，则δ(G)≥1。用归纳法。 ① n=1时，G 为平凡图，显然G 连通。 ② n=2时，m ≥2 1(n-1)(n-2)+1=1，此时G 为K2，当然连通。 ③ 设n=k(k ≥2)， m ≥21(k-1)(k-2)+1时结论成立，要证明当n=k+1,m ≥2 1k(k-1)+1时结 论也成立。 (i) 若G 为K k+1，G 当然连通。 (ii) 若G 中含孤立点，一定推出矛盾。删去G 中的孤立点，记作G1。则G1的边数m ≥ 2 1k(k-1)+1，这与G1为阶数小于等于k 的简单图矛盾，故G 中不可能含孤立点。 (iii) 由(i)、(ii)可知，只需对G 不为完全图、又不含孤立点的情况加以证明。 G 中存在v0，使1≤d(v0)≤k-1（G 中无孤立点，又不是k+1阶完全图）， 令G'=G-v0，则G'为k 阶简单图，且G'的边数 m'≥21 k(k-1)+1-(k-1) =(21 k(k-1)-(k-1))+1 =2 1(k-1)(k-2)+1 由归纳假设可知，G'是连通图，而G'为G 的子图，故G 也连通。 10、设G 为n 阶无向简单图，证明以下题目： （1）当δ(G)≥2 n 时，证明G 连通。 证明（1）用反证法。假设G 至少有两个连通分支，设G1,G2为其中的两个，并设G1,G2的阶数分别为n1和n2，则n1+n2≤n ，且min{n1,n2}≤?? ????2n 。于是，对任意的 v ∈V(G1)， dG1(V)= dG(V)≤?? ????2n -1<2n ，这与δ(G)≥2n 矛盾，所以G 连通。 （2）当δ(G)≥2 1(n+k-1)时，证明G 是k-连通图。 证明：设V'为V(G)的任意子集，且|V'|=k-1。令 G'=G-V'，则G'为n-(k-1)=n-k+1=n'阶无向简单图，而 δ(G')≥δ(G)-(k-1) ≥2 1 (n+k-1)-(k-1) = 2 1 (n+k-1-2k+2) = 2 1 (n-k+1) =2 1n' 由当δ(G)≥2 n 时，G 连通可知，G'连通，故G'为k-连通图。 离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ 3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={ 离散数学试题（A卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧()) 下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。 2017年11月上交的离散数学形考任务一 本课程的教学内容分为三个单元，其中第三单元的名称是（A ）． 选择一项： A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 答案已保存 满分10.00 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D ）． 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 题目3 答案已保存 满分10.00 标记题目 题干 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 D. 17 题目4 答案已保存 满分10.00 标记题目 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（ C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分10.00 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 满分10.00 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 答案已保存 满分10.00 标记题目 题干 ―教学活动资料‖版块是课程学习平台右侧的第（A）个版块． 选择一项： A. 6 B. 7 C. 8 D. 9 题目8 答案已保存 满分10.00 标记题目 题干 课程学习平台中―课程复习‖版块下，放有本课程历年考试试卷的栏目名称是：（D ）． 选择一项： A. 复习指导 B. 视频 C. 课件 D. 自测 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交． 解答：学习计划 学习离散数学任务目标： 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f 2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 2017年11月上交的离散数学形考任务一本课程的教学内容分为三个单元，其中第三单元的名称是（ A ）． 选择一项： ， A. 数理逻辑 B. 集合论 C. 图论 D. 谓词逻辑 题目2 . 答案已保存 满分 标记题目 题干 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（ D ）． ) 选择一项： A. 函数 B. 关系的概念及其运算 C. 关系的性质与闭包运算 D. 几个重要关系 < 题目3 答案已保存 满分 标记题目 题干 ； 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． 选择一项： A. 18 B. 20 C. 19 ， D. 17 题目4 答案已保存 满分 标记题目 … 题干 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）．选择一项： A. 集合恒等式与等价关系的判定 B. 图论部分书面作业 ~ C. 集合论部分书面作业 D. 网上学习问答 题目5 答案已保存 满分 " 标记题目 题干 课程学习平台左侧第1个版块名称是：（C）． 选择一项： A. 课程导学 … B. 课程公告 C. 课程信息 D. 使用帮助 题目6 答案已保存 ^ 满分 标记题目 题干 课程学习平台右侧第5个版块名称是：（D）． 选择一项： % A. 典型例题 B. 视频课堂 C. VOD点播 D. 常见问题 题目7 《 答案已保存 满分 标记题目 题干 “教学活动资料”版块是课程学习平台右侧的第（ A ）个版块． 、 选择一项： A. 6 B. 7 C. 8 D. 9 @ 题目8 答案已保存 满分 标记题目 题干 ( 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D ）．选择一项： 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 一、单项选择题（共 10 道试题，共 100 分。） 1. 设集合A = {1, a }，则P(A) = ( D )． A. {{1}, {a}} B. { ,{1}, {a}} C. {{1}, {a}, {1, a }} D. { ,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（C ）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( C )． A. {a，{a}} A B. {1，2} A C. {a} A D. A 4. 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}， 则h =（ A ）． A. f?g C. f?f D. g?g 5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（ C ）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系￡是A上的整除关系，则偏序集上的元素5是集合A的（ C ）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（ A ）． 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸，将答题过程手工书写，并拍照上传． 一、填空题 1．已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15 ． 2．设给定图G(如右由图所示)，则图G的点割集是 { f }，{ e,c} ． 3．设G是一个图，结点集合为V，边集合为E，则 G的结点度数之和等于边数的两倍． 4．无向图G存在欧拉回路，当且仅当G连通且不含奇数度结 点． 5．设G= 8．结点数v与边数e满足e=v - 1 关系的无向连通图就是树． 9．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树． 10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．） 1．如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路． 答：错误。应叙述为：“如果图G是无向连通图，且其结点度数均为偶数，则图G存在一条欧拉回路。” 2．如下图所示的图G存在一条欧拉回路． 答：错误。因为图中存在奇数度结点，所以不存在欧拉回路。 3．如下图所示的图G不是欧拉图而是汉密尔顿图． 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 电大离散数学本形考任 务 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} A B ==，P(A)-P(B )={{3},{1,3},{2,3},{1,2,3}}，A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} x∈ y y > <那么R－1＝{<6,3>,<8,4>}． x = ∈ 2 , , x , {B A y 5．设集合A=｛a, b, c, d｝，A上的二元关系R={离散数学形成性考核作业4题目与答案
(完整版)离散数学试卷及答案
离散数学期末试题
离散数学模拟题一套及答案
离散数学形考任务1-7试题及答案完整版
离散数学试题与答案
离散数学模拟试题讲解
离散数学形考任务1-7试题及答案完整版
离散数学期末试题及答案完整版
离散数学模拟试卷和答案
204电大离散数学,形考任务2
离散数学期末试卷及答案
离散数学期末试卷A卷及答案
离散数学模拟试题及答案
2018国家开放大学离散数学本形考任务答案
离散数学试卷及答案
离散数学考试试题(A、B卷及答案)
电大离散数学本形考任务完整版