下载文档原格式
第2次作业一、单项选择题(本大题共40分，共20小题，每小题2分)1.假设A={a, b, c, d},考虑子集S= {{a, b}, {b, c}, {d}},则下列选项正确的是()oA.S是A的覆盖B.S是A的划分C.s既不是划分也不是覆盖D.以上选项都不正确2.设h是群G上的一个同态，|G|二12,山(G)|二3,则|K| (K是h的核)二_________________ ()A.1B.2C.D.3.L23 ), 设G是连通(n,m)的平面图，有r个面，且每个面的次数至少为L( 则A.m>3n-6B.Hl <c.m+n-r=2D.m+r-n二24.如果小王和小张都不去，则小李去。
设P：小王去。
Q：小张去。
R：小李去。
则命题符号化为_________ oA.-I QA-i PVRB.(Q->P)ARC.(n PAn QLRD.(PAQ)-R5.没有不犯错误的人。
M(x)： x为人。
F (x) : x犯错误。
则命题可表示为()OA.(Vx) (M(x) F (x)B.(3x) (M(x) AF(x)C.(Vx) (M(x)AF(x))D.(3x) (M(x)-F(x)6.(1)燕子北冋，春天来了。
设P:燕了北回。
Q：春天來了。
则(1)可以表示为___________ oP->QQ-PC.UQD.P VQ7.命题公式(P->QA-i P)的类型是___________ 。
A.重言式B.矛盾式C.可满足式D.永真式6.一阶逻辑公式Vx(F(x, y)AG(y, z) )—VzF(z, y)是()前束范式封闭公式C.永真式D.永假式7.谓词公式(3x)P(x, y) A (Vx) (Q(x, z)-> Gx) (Vy)R(x, y, z)中的量词Vx 的辖域是()。
A.(Vx)(Q(x,z)->(3 x)( Vy)R(x,y ,z)B.Q(x, z)-> (Vy)R(x, y, z)C.Q (x, z) —(3x) (Vy) R (x, y, z)D.Q(x, z)8.关于半群的性质，下面说法不正确的是()A.若〈S,*>S且*在8上是封闭的，那么匸是一个半群，B<B, *>也是一个半群。
精品文档离散数学习题答案习题一及答案：（ P14-15 ）14、将下列命题符号化：（ 5）李辛与李末是兄弟解：设 p：李辛与李末是兄弟，则命题符号化的结果是p（ 6）王强与刘威都学过法语解：设 p：王强学过法语； q：刘威学过法语；则命题符号化的结果是p q （ 9）只有天下大雨，他才乘班车上班解：设 p：天下大雨； q：他乘班车上班；则命题符号化的结果是q p（ 11）下雪路滑，他迟到了解：设 p：下雪； q：路滑； r ：他迟到了；则命题符号化的结果是( p q)r15、设 p： 2+3=5.q：大熊猫产在中国 .r：太阳从西方升起 .求下列复合命题的真值：（ 4）(p q r )(( p q)r )解： p=1， q=1，r=0 ，(p q r )(110)1，((p q)r )((11)0)(00)1(p q r )(( p q)r ) 1 1119、用真值表判断下列公式的类型：（ 2）( p p)q解：列出公式的真值表，如下所示：p q p qp) ( p p)q( p001111011010100101110001由真值表可以看出公式有 3 个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：精品文档（ 4）( p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：( p q)1p0q0q0所以公式的成真赋值有： 01，10， 11。
习题二及答案：（ P38）5、求下列公式的主析取范式，并求成真赋值：（ 2）(p q) (q r )解：原式( p q) q r q r( p p) q r( p q r ) ( p q r )m3m7，此即公式的主析取范式，所以成真赋值为011， 111。
6、求下列公式的主合取范式，并求成假赋值：（ 2）( p q) ( p r )解：原式( pp r ) ( p q r )( p q r )M 4，此即公式的主合取范式，所以成假赋值为 100。
离散数学作业2离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。
．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。
．要求：将此作业用A4纸打印出来，并在03任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，要求2009年4月5日前完成并后上交任课教师（不收电子稿）。
．并在03任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、单项选择题1．若集合A ＝{2，a ，{ a }，4}，则下列表述正确的是( B )．A ．{a ，{a }}∈AB ．{ a }⊆AC ．{2}∈AD ．∅∈A2．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ B ）．A ．{2}∈B B ．{2, {2}, 3, 4}⊂BC ．{2}⊂BD ．{2, {2}}⊂B3．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ D ）．A ．B ⊂ A B ．A ⊂ BC ．B ∉ AD ．B ∈ A4．设集合A = {1, a }，则P (A ) = ( C )．A ．{{1}, {a }}B ．{∅,{1}, {a }}C ．{∅,{1}, {a }, {1, a }}D ．{{1}, {a }, {1, a }}5．设集合A = {1，2，3}，R 是A 上的二元关系，R ={<a , b >⎢a ∈A ，b ∈ A 且1=-b a }则R 具有的性质为（ B ）．A ．自反的B ．对称的C ．传递的D ．反对称的6．设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b >⎢a , b ∈A ，且a =b }，则R 具有的性质为（ D ）．A ．不是自反的B ．不是对称的C ．反自反的D ．传递的7．设集合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 ．以上都不对8．设集合A ={a , b }，则A 上的二元关系R={<a , a >，<b , b >}是A 上的( D )关系．A ．是等价关系但不是偏序关系B ．是偏序关系但不是等价关系C ．既是等价关系又是偏序关系D ．不是等价关系也不是偏序关系9．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如右图所示,若A 的子集B = {3 , 4 , 5}，则元素3为B 的（ C ）．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对10．设集合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 （B ）g ◦f （C ）f ◦f （D ）g ◦g二一、填空题1．设集合{1,2,3},{1,2}A B ==，则A B = A ，A B = B ．21．设集合{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>} ．32．设集合A 有10个元素，那么A 的幂集合P (A )的元素个数为210 ．43．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为:{<2,2>,<2,3>,<3,2>,<3,3>}设集合A = {1，2，3，4，5 }，B = {1，2，3}，R 从A 到B 的二元关系，R ={<a , b >⎢a ∈A ，b ∈B 且2≤a + b则R 的有序对集合为:A ⨯B 。
离散数学试题及答案一、填空题1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝; ρ(A) - ρ(B) ＝.2. 设有限集合A, |A| = n, 则|ρ(A×A)| = .3.设集合A = {a, b}, B = {1, 2}, 则从A 到B 的所有映射是, 其中双射的是.4.已知命题公式G＝⌝(P→Q)∧R，则G 的主析取范式是.5.设G 是完全二叉树，G 有7 个点，其中4 个叶点，则G 的总度数为，分枝点数为.6 设A、B 为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝; A⋃B＝;A－B＝.7.设R 是集合A 上的等价关系，则R 所具有的关系的三个特性是,, .8.设命题公式G＝⌝(P→(Q∧R))，则使公式G 为真的解释有，, .9. 设集合 A＝{1,2,3,4}, A 上的关系 R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1•R2 =,R2•R1 = , R12= .10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = .11 设A,B,R 是三个集合，其中R 是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = , B-A = ,A∩B = , .13.设集合A＝{2, 3, 4, 5, 6}，R 是A 上的整除，则R 以集合形式(列举法)记为.14.设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G 的前束范式是.15.设G 是具有8 个顶点的树，则G 中增加条边才能把G 变成完全图。
16.设谓词的定义域为{a, b},将表达式∀xR(x)→∃xS(x)中量词消除，写成与之对应的命题公式是.17. 设集合 A＝{1, 2, 3, 4}，A 上的二元关系 R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。
图G如图三所示，以下说法正确的是( )．选择一项：A. {c}是点割集B. a是割点C. {b, d}是点割集D. {b, c}是点割集反馈你的回答不正确正确答案是：{b, c}是点割集题目2标记题目题干如图二所示，以下说法正确的是( )．图二选择一项：A. {b, e}是点割集B. {a, e}是点割集C. {d}是点割集D. e是割点反馈你的回答不正确正确答案是：e是割点题目3未回答满分5.00标记题目题干已知无向图G的邻接矩阵为，则G有（）．选择一项：A. 6点，7边B. 5点，7边C. 6点，8边D. 5点，8边反馈你的回答不正确正确答案是：5点，7边题目4未回答满分5.00标记题目题干若G是一个欧拉图，则G一定是( )．选择一项：A. 汉密尔顿图B. 平面图C. 连通图D. 对偶图反馈你的回答不正确正确答案是：连通图题目5未回答满分5.00标记题目题干设无向图G的邻接矩阵为，则G的边数为( )．A. 3B. 4C. 5D. 6反馈你的回答不正确正确答案是：5题目6未回答满分5.00标记题目题干设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树．A.B.C.D.反馈你的回答不正确正确答案是：题目7未回答满分5.00标记题目题干设无向图G的邻接矩阵为，则G的边数为( )．选择一项：A. 1B. 7C. 6D. 14反馈你的回答不正确正确答案是：7题目8题干无向简单图G是棵树，当且仅当( )．选择一项：A. G连通且边数比结点数少1B. G的边数比结点数少1C. G连通且结点数比边数少1D. G中没有回路．反馈你的回答不正确正确答案是：G连通且边数比结点数少1 题目9未回答满分5.00题干设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．图五选择一项：A. （b）是强连通的B. （a）是强连通的C. （c）是强连通的D. （d）是强连通的反馈你的回答不正确正确答案是：（a）是强连通的题目10未回答满分5.00标记题目题干无向完全图K4是（）．选择一项：A. 非平面图B. 树C. 欧拉图D. 汉密尔顿图反馈你的回答不正确正确答案是：汉密尔顿图标记题目信息文本判断题题目11未回答满分5.00标记题目题干设G是一个图，结点集合为V，边集合为E，则．( )选择一项：对错反馈正确的答案是“对”。
离散数学第二次作业参考答案学号： 姓名： 班级： 总分：1、 (每空5分，共30分)(1) 已知公式A 含有3个命题变项p , q , r ,并且它的成真赋值为000，011，110，那么命题公式A 的成假赋值为 001,010,100,101,111 ,主析取范式为 , 主合取范式为 M 1∧M 2∧M 4∧M 5∧M 7 。
(2) 已知公式A 含有3个命题变项，并且公式A 的主合取范式为134M M M ∧∧，那么公式A 的成真赋值为 000, 010,101,110,111 ，成假赋值为 001, 011, 100 ，公式A 的主析取范式为 。
2、(12分)用真值表法计算公式()p q r ⌝∨∧的主析取范式和主合取范式解：真值表为p q r p q ⌝∨ ()p q r ⌝∨∧0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 1 0 1 0 1 1 111主析取范式：137m m m ∨∨主合取范式：02456M M M M M ∧∧∧∧3、(14分)甲、乙、丙、丁4人中有且仅有2个人参加围棋比赛。
关于谁参加了比赛，下列判断都是正确的：(1) 甲和乙只有一人参加。
(2) 若丙参加，则丁必参加。
(3) 乙或者丁至多参加一人。
(4) 丁不参加，则甲也不会参加。
问：哪两个人参加了比赛。
解：其它解题方法，只要解释清楚，答案正确就给分① 设p : 甲参加，q :乙参加，r :丙参加，s :丁参加。
② 4个条件分别符号化为()()p q p q ⌝∧∨∧⌝，()r s →，()q s ⌝∨⌝，()s p ⌝→⌝ 根据题意可得公式[()()]()()()p q p q r s q s s p ⌝∧∨∧⌝∧→∧⌝∨⌝∧⌝→⌝ 该公式的成真赋值为可能可行的方案。
③经过演算可得[()()]()()()()()()()()p q p q r s q s s p p q p q r s q s p s ⌝∧∨∧⌝∧→∧⌝∨⌝∧⌝→⌝⇔⌝∨⌝∧∨∧⌝∨∧⌝∨⌝∧⌝∨④由于p 和q 有且仅有一个为1，因此公式的成真赋值只能是10XX 或者01XX 。
离散数学(第2版)_在线作业_2一、单选题（每题5分，共20道小题，总分值100分）1.设R是实数集合，R上的运算*定义为，则为()。
（5分）A半群B代数系统C非代数系统D群正确答案您的答案是B回答正确展开2.无向图G具有一条欧拉回路，则G中所有点的度数都是()。
（5分）A偶数B1C奇数D素数正确答案您的答案是A回答正确展开3.下列语句中不是命题的是()。
（5分）明天是个阴天请不要生气！3是素数昨天是星期四正确答案您的答案是B回答正确展开4.谓词公式中变元()。
（5分）A不是自由出现，是约束出现B既不是自由出现又不是约束出现C是自由出现，不是约束出现D既是自由出现又是约束出现正确答案您的答案是D回答正确展开5.设上的关系，则R的定义域等于()。
（5分）ABCD正确答案您的答案是A回答正确展开6.集合的交运算不满足()。
（5分）A交换律B幂等律C结合律D消去律正确答案您的答案是D回答正确展开7.集合的并运算不满足()。
（5分）A幂等律B交换律C消去律D结合律正确答案您的答案是C回答正确展开8.设，下面命题为假的是()。
（5分）ABCD正确答案您的答案是B回答正确展开9.前提，，的逻辑结论不会是()。
（5分）ABCD正确答案您的答案是C回答正确展开10.下列是谓词公式的是()。
（5分）ABCD正确答案您的答案是B回答正确展开11.下列语句中是命题的是()。
（5分）A请不要随地吐痰B我真快乐！C今天是阴天D你身体好吗？正确答案您的答案是C回答正确展开12.下列公式是前束范式的是()。
（5分）ABCD正确答案您的答案是B回答正确展开13.设和都是A上的双射函数，则为()。
（5分）ABCD正确答案您的答案是D回答错误展开( 应该选B )14.设R是实数集合，函数，和,则复合函数是()。
（5分）ABCD正确答案您的答案是D回答正确展开15.下列公式是非永真式的可满足式的是()。
（5分）ABCD正确答案您的答案是B回答正确展开16.设上的关系，则R具有性质()。
离散数学第一次作业——参考答案(总2页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)⇔(p→(q∧r))(4)(p∧⌝q)∨(⌝p∧q)⇔(p∨q) ∧⌝(p∧q)证明（2）(p→q)∧(p→r)⇔ (⌝p∨q)∧(⌝p∨r)⇔⌝p∨(q∧r))⇔p→(q∧r)（4）(p∧⌝q)∨(⌝p∧q)⇔(p∨(⌝p∧q)) ∧(⌝q∨(⌝p∧q)) ⇔(p∨⌝p)∧(p∨q)∧(⌝q∨⌝p) ∧(⌝q∨q)⇔1∧(p∨q)∧⌝(p∧q)∧1⇔(p∨q)∧⌝(p∧q)14.在自然推理系统P中构造下面推理的证明：(4)前提：q→p,q↔s,s↔t,t∧r结论：p∧q证明：②t∧r 前提引入②t ①化简律③q↔s 前提引入④s↔t 前提引入⑤q↔t ③④等价三段论⑥（q→t）∧(t→q) ⑤置换⑦（t→q）⑥化简⑧q ②⑥假言推理⑨q→p 前提引入⑩p ⑧⑨假言推理○11p∧q ⑧⑩合取P59. 18. 在自然推理系统P中构造下面推理证明（1）如果今天是星期六，我们就要到颐和园或圆明园去玩，如果颐和园游人太多，我们就不去颐和园玩，今天是周末颐和园游人太多，所以我们去圆明园玩。
证明：设p：今天是星期六，q：我们到颐和园玩，r:我们到圆明园玩，s:颐和园游人太多前提：p → (q∨r), s →⌝q ,p ,s结论：r推理：①s →⌝q 前提引入②s 前提引入③⌝q ①②假言推理④ p 前提引入⑤ p → (q∨r) 前提引入⑥ q∨r ④⑤假言推理⑦ r ③⑥析取三段论P86. 22. 在自然推理系统N中，构造下列推理的证明。
£（1）偶数都能被2整除。
6是偶数。
所以6能被2整除。
设：F（x）:x为偶数，G（x）:x能被2整除，a：6前提： x(F(x) →G(x)), F(a)结论：G（a）证明：①任意x（F（x）—>G（x））前提引入②F（a）—>G（a）①全称量词消去规则③F（a）前提引入④G（a）假言推理。
