下载文档原格式
最新国家开放大学电大《离散数学》形考任务1试题及答案最新国家开放大学电大《离散数学》形考任务1试题及答.形考任务1（集合论部分概念及性质）单项选择.题目.若集合A＝.a, {a}, {1, 2}}, 则下列表述正确的是（）.选择一项:A.{a, {a}}.B..C.{1, 2..D.{a..题目.设函数f: N→N, f(n)=n+1, 下列表述正确的是.）.选择一项: A.f是满射.B.f存在反函.C.f是单射函.D.f是双射.题目.设集合A={1, 2, 3, 4, 5}, 偏序关系是A上的整除关系, 则偏序集<A, >上的元素5是集合A的.）.选择一项:A.极小.B.极大.C.最大.D.最小.题目.设A={a, b}, B={1, 2}, C={4, 5}, 从A到B的函数f={<a,1>.<b, 2>}, 从B到C的函数g={<1, 5>.<2, 4>}, 则下列表述正确的是.）.选择一项:A.g..={<a, 5>.<b, 4>.B.g..={<5, .>.<4, .>.C.f°.={<5, .>.<4, .>.D.f°.={<a, 5>.<b, 4>.题目.集合A={1.2.3.4}上的关系R={<x, y>|x=y且x.yA}, 则R的性质为.）.选择一项:A.传递.B.不是对称.C.反自.D.不是自反.题目.设集合..{1..}, 则P(A...).选择一项:A.{{1}.{a}.{1..}.B.{{1}.{a}.C.{,{1}.{a}.D.{,{1}.{a}.{1..}.题目.若集合A={1, 2}, B={1, 2, {1, 2}},则下列表述正确的是.).选择一项:A.AB, 且A.B.AB, 且A.C.BA, 且A.D.AB, 且A.题目.设集合A={1.2.3}, B={3.4.5}, C={5.6.7},则A∪B–.=.).选择一项:A.{1.2.3.4.B.{4.5.6.7.C.{2.3.4.5.D.{1.2.3.5.题目.设集合..{1.2.3.4.5}上的偏序关系的哈斯图如右图所示, 若A的子集..{3.4.5}, 则元素3为B的.）.选择一项:A.最小上.B.下.C.最大下.D.最小.题目1.如果R1和R2是A上的自反关系, 则R1∪R2, R1∩R2, R1-R2中自反关系有.）个.选择一项:A..B..C..D..以下资料为赠送资料:《滴水之中见精神》主题班会教案活动目的: 教育学生懂得“水”这一宝贵资源对于我们来说是极为珍贵的, 每个人都要保护它, 做到节约每一滴水, 造福子孙万代。
作业参考答案——10-特殊图1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是哈密顿图。
2.根据给定条件建立一个无向图G=<V,E>，其中：V={a,b,c,d,e,f,g}E={(u,v)|u,v∈V,且u和v有共同语言}从而图G如下图所示。
abcd e fg将这7个人围圆桌排位，使得每个人都能与他两边的人交谈，就是在图G 中找哈密顿回路，经观察上图可得到两条可能的哈密顿回路，即两种方案：abdfgeca和acbdfgea。
3.证明（法一）：根据已知条件，每个结点的度数均为n，则任何两个不相邻的结点v i,v j的度数之和为2n，而图中总共有2n个结点，即deg(v i)+ deg(v j)⩾2n，满足哈密顿图的充分条件，从而图中存在一条哈密顿回路，当然，这就说明图G是连通图。
证明（法二）：用反证法，假设G不是连通图，设H是G的一个连通分支，由于图G是简单图且每个结点的度数为n，则子图H与G-H中均至少有n+1个结点。
所以G的结点数大于等于2n+2，这与G中结点数为2n矛盾。
所以假设不成立，从而G是连通图。
4.将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在代表他们的结点之间连一条线，得到一个偶图G，假设它的互补结点子集V1、V2分别表示n位男士和n位女士，由题意可知V1中的每个结点度1数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。
5.此平面图具有五个面，如下图所示。
ab c d ef gr1r2r3r4r5•r1，边界为abca，D(r1)=3;•r2，边界为acga，D(r2)=3;•r3，边界为cegc，D(r3)=3;•r4，边界为cdec，D(r4)=3;•r5，边界为abcdefega，D(r5)=8;无限面6.设该连通简单平面图的面数为r，由欧拉公式可得，6−12+r=2，所以r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。
离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。
b)我今天进城，除非下雨。
c)仅当你走，我将留下。
2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。
c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。
（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。
（4分）4.判断下面命题的真假，并说明原因。
（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。
（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。
1-1，1-2（1） 解：a) 是命题，真值为T。
b) 不是命题。
c) 是命题，真值要根据具体情况确定。
d) 不是命题。
e) 是命题，真值为T。
f) 是命题，真值为T。
g) 是命题，真值为F。
h) 不是命题。
i) 不是命题。
（2） 解：原子命题：我爱北京天安门。
A（3） 解：a) (┓P ∧R)→Qb) Q→Rc) ┓Pd) P→┓Q（4） 解：a)设Q:我将去参加舞会。
R:我有时间。
P:天下雨。
Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。
b)设R:我在看电视。
Q:我在吃苹果。
R∧Q:我在看电视边吃苹果。
c) 设Q:一个数是奇数。
R:一个数不能被2除。
（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。
(5) 解：a) 设P：王强身体很好。
Q：王强成绩很好。
P∧Qb) 设P：小李看书。
Q：小李听音乐。
P∧Qc) 设P：气候很好。
Q：气候很热。
P∨Qd) 设P： a和b是偶数。
Q：a+b是偶数。
P→Qe) 设P：四边形ABCD是平行四边形。
Q ：四边形ABCD的对边平行。
PQf) 设P：语法错误。
Q：程序错误。
R：停机。
（P∨ Q）→ R(6) 解：a) P:天气炎热。
Q:正在下雨。
P∧Qb) P:天气炎热。
R:湿度较低。
P∧Rc) R:天正在下雨。
S:湿度很高。
R∨Sd) A:刘英上山。
B:李进上山。
A∧Be) M:老王是革新者。
N:小李是革新者。
M∨Nf) L:你看电影。
M:我看电影。
┓L→┓Mg) P:我不看电视。
Q:我不外出。
R:我在睡觉。
P∧Q∧Rh) P:控制台打字机作输入设备。
Q:控制台打字机作输出设备。
P∧Q1-3（1）解：a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可作为合式公式）b) 是合式公式c) 不是合式公式（括弧不配对）d) 不是合式公式（R和S之间缺少联结词）e) 是合式公式。
（2）解：a） A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。
离散数学习题答案习题一及答案：（P14-15）14、将下列命题符号化：（5）李辛与李末是兄弟解：设p ：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是p q∧（9）只有天下大雨，他才乘班车上班解：设p ：天下大雨；q ：他乘班车上班；则命题符号化的结果是q p →（11）下雪路滑，他迟到了解：设p ：下雪；q ：路滑；r ：他迟到了；则命题符号化的结果是()p q r∧→15、设p ：2+3=5. q ：大熊猫产在中国. r ：太阳从西方升起.求下列复合命题的真值：（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→解：p=1，q=1，r=0，，()(110)1p q r ∧∧⌝⇔∧∧⌝⇔(())((11)0)(00)1p q r ⌝∨⌝→⇔⌝∨⌝→⇔→⇔()(())111p q r p q r ∴∧∧⌝↔⌝∨⌝→⇔↔⇔19、用真值表判断下列公式的类型：（2）()p p q→⌝→⌝解：列出公式的真值表，如下所示：p qp⌝q⌝()p p →⌝()p p q→⌝→⌝001111011010100101110001由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。
20、求下列公式的成真赋值：（4）()p q q⌝∨→解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：()10p q q ⌝∨⇔⎧⎨⇔⎩⇒0p q ⇔⎧⎨⇔⎩所以公式的成真赋值有：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 ⇔⌝∧∧∨∧∧37m m ⇔∨所以成真赋值为011，111。
*6、求下列公式的主合取范式，并求成假赋值：（2）()()p q p r ∧∨⌝∨解：原式，此即公式的主合取范式，()()p p r p q r ⇔∨⌝∨∧⌝∨∨()p q r ⇔⌝∨∨4M ⇔所以成假赋值为100。
《离散数学》题库大全及答案为离散数学领域的经典教材,全世界几乎所有知名的院校都曾经使用本书作为教材.以我个人观点看来,这本书可以称之为离散数学百科.书中不但介绍了离散数学的理论和方法,还有丰富的历史资料和相关学习网站资源.更为令人激动的便是这本书少有的将离散数学理论与应用结合得如此的好.你可以看到离散数学理论在逻辑电路,程序设计,商业和互联网等诸多领域的应用实例.本书的英文版(第六版)当中更增添了相当多的数学和计算机科学家的传记,是计算机科学历史不可多得的参考资料.作为教材这本书配有相当数量的练习.每一章后面还有一组课题,把学生已经学到的计算和离散数学的内容结合在一起进行训练.这本书也是我个人在学习离散数学时读的唯一的英文教材,实为一本值得推荐的好书。
《离散数学》题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P答：（1），（4）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P答：（2），（3），（4），（5），（6）4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。
最新国家开放大学电大《离散数学(本)》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。
该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。
做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。
本文库还有其他网核及教学考一体化答案，敬请查看。
《离散数学》题库及答案一一、单项选择题（每小题3分，本题共15分）1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）．A．A⊂B，且A∈B B．A∈B，但A⊄BC．A⊂B，但A∉B D．A⊄B，且A∉B2．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={<x，y>|x+y=10且x, y∈A}，则R的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的3．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．A．0 B．2 C．1 D．34．如图一所示，以下说法正确的是( ) ．A．{(a, e)}是割边B．{(a, e)}是边割集C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集图一5．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（）．A．(∀x)(A(x)∧B(x)) B．┐(∃x)(A(x)∧B(x))C．┐(∀x)(A(x) →B(x)) D．┐(∃x)(A(x)∧┐B(x))二、填空题（每小题3分，本题共15分）6．若集合A的元素个数为10，则其幂集的元素个数为．7．设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为．8．若A={1,2}，R={<x, y>|x∈A, y∈A, x+y=10}，则R的自反闭包为．9．结点数v与边数e满足关系的无向连通图就是树．10．设个体域D＝{a, b, c}，则谓词公式(∀x)A(x)消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．12．将语句“今天没有下雨．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．下面的推理是否正确，试予以说明．(1) （∀x）F（x）→G（x）前提引入(2) F（y）→G（y）US（1）．14．若偏序集<A，R>的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．图二五．计算题（每小题12分，本题共36分）15．求（P∨Q）→（R∨Q）的合取范式．16．设A={0，1，2，3，4}，R={<x，y>|x∈A，y∈A且x+y<0}，S={<x，y>|x∈A，y∈A且x+y≤3}，试求R，S，R•S，R-1，S-1，r(R)．17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．六、证明题（本题共8分）18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G 是G的补图)．试题解答一、单项选择题（每小题3分，本题共15分） 1．A 2．B 3．B 4．D 5．C 二、填空题（每小题3分，本题共15分） 6．1024 7．88．{<1,1>,<2,2>} 9．e=v -110．A (a ) ∧A (b )∧A （c ）三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：他接受了这个任务，Q ：他完成好了这个任务， （2分）P ∧⌝ Q ． （6分）12．设P ：今天下雨， （2分）⌝ P ． （6分）四、判断说明题（每小题7分，本题共14分）13．错误． （3分） （2）应为F （y ）→G （x ），换名时，约束变元与自由变元不能混淆． （7分） 14．错误． （3分） 集合A 的最大元不存在，a 是极大元． （7分） 五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔⌝（P ∨Q ）∨（R ∨Q ） （4分） ⇔(⌝P ∧⌝Q )∨（R ∨Q ）⇔(⌝P ∨R ∨Q )∧(⌝Q ∨R ∨Q )⇔(⌝P ∨R ∨Q ) ∧R 合取范式 （12分） 16．R =∅, （2分） S ={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分） R •S =∅， （6分）R -1=∅， （8分） S -1= S ， （10分） r (R )=I A ． （12分） 17．（10分）权为1⨯3+2⨯3+2⨯2+3⨯2+4⨯2=27 （12分）六、证明题（本题共8分）18．证明：因为n 是奇数，所以n 阶完全图每个顶点度数为偶数， （3分） 因此，若G 中顶点v 的度数为奇数，则在G 中v 的度数一定也是奇数， （6分）ο οο ο ο ο ο ο ο 1 2 23 34 75 12所以G 与G 中的奇数度顶点个数相等． （8分）《离散数学》题库及答案二一、单项选择题（每小题3分，本题共15分）1．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( )． A ．2⊂A B ．{1}⊂AC ．1∉AD ．2 ∈ A2．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )． A ．6 B ．4 C ．3 D ．53．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110 则G 的边数为( )． A ．1 B ．7 C ．6 D ．144．设集合A ={a }，则A 的幂集为( )．A ．{{a }}B ．{a ，{a }}C ．{∅，{a }}D ．{∅，a }5．下列公式中 ( )为永真式．A ．⌝A ∧⌝B ↔ ⌝A ∨⌝B B ．⌝A ∧⌝B ↔ ⌝(A ∨B )C ．⌝A ∧⌝B ↔ A ∨BD ．⌝A ∧⌝B ↔ ⌝(A ∧B )二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∧的真值是 ． 7．若无向树T 有5个结点，则T 的边数为 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 ，就可使新得到的关系为对称的．10．(∀x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．14．设G是一个有4个结点10条边的连通图，则G为平面图．五．计算题（每小题12分，本题共36分）15．试求出（P∨Q）→（R∨Q）的析取范式．16．设A={{1}, 1, 2}，B={1, {2}}，试计算（1）（A∩B）（2）（A∪B）（3）A （A∩B）．17．图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．试题解答一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 5．B二、填空题（每小题3分，本题共15分）6．假（或F，或0）7．48．t-19．<2, 1>10．z，y三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：今天上课， （2分） 则命题公式为：P ． （6分） 12．设 P ：他去操场锻炼，Q ：他有时间， （2分） 则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分） 因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数． （7分） 14．错误． （3分） 不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．” （7分）五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔ ┐(P ∨Q )∨（R ∨Q ） （4分）⇔ (┐P ∧┐Q )∨（R ∨Q ） （8分）⇔ (┐P ∧┐Q )∨R ∨Q （析取范式） （12分）16．（1）（A ∩B ）={1} （4分）（2）（A ∪B ）={1, 2, {1}, {2}} （8分） （3） A -（A ∩B ）={{1}, 1, 2} （12分）17．（1）G 的图形表示如图一所示：（3分）（2）邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110 （6分） （3）最小的生成树如图二中的粗线所示：图一 ο ο ο ο a b c d1 124 53 图二ο ο ο ο a b cd1 1 2453（10分）权为：1+1+3=5 （12分）六、证明题（本题共8分）18．证明：设∀x∈A，因为R自反，所以x R x，即< x, x>∈R；又因为S自反，所以x R x，即< x, x >∈S．（4分）即< x, x>∈R∩S （6分）故R∩S自反．（8分）《离散数学》题库及答案三一、单项选择题（每小题3分，本题共15分）1．若集合A＝{ a，{a}}，则下列表述正确的是( )．A．{a}⊆A B．{{{a}}}⊆AC．{a，{a}}∈A D．∅∈A2．命题公式（P∨Q）的合取范式是( )A．（P∧Q）B．（P∧Q）∨（P∨Q）C．（P∨Q）D．⌝（⌝P∧⌝Q）3．无向树T有8个结点，则T的边数为( )．A．6 B．7 C．8 D．9 4．图G如图一所示，以下说法正确的是( )．A．a是割点B．{b,c}是点割集C．{b, d}是点割集D．{c}是点割集图一5．下列公式成立的为( )．A．⌝P∧⌝Q ⇔P∨Q B．P→⌝Q⇔⌝P→QC．Q→P⇒ P D．⌝P∧(P∨Q)⇒Q二、填空题（每小题3分，本题共15分）6．设集合A ={2, 3, 4}，B ={1, 2, 3, 4}，R 是A 到B 的二元关系，},{y x B y A x y x R ≤∈∈><=且且则R 的有序对集合为 ．7．如果R 是非空集合A 上的等价关系，a ∈A ，b ∈A ，则可推知R 中至少包含 等元素． 8．设G ＝<V , E >是有4个结点，8条边的无向连通图，则从G 中删去 条边，可以确定图G 的一棵生成树．9．设G 是具有n 个结点m 条边k 个面的连通平面图，则m 等于 10．设个体域D ＝{1, 2}，A (x )为“x 大于1”，则谓词公式()()x A x ∃的真值为 三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“今天考试，明天放假．”翻译成命题公式． 12．将语句“我去旅游，仅当我有时间．”翻译成命题公式． 四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．如果图G 是无向图，且其结点度数均为偶数，则图G 是欧拉图．14．若偏序集<A ，R >的哈斯图如图二所示，则集合A 的最大元为a ，最小元是f ．图二五．计算题（每小题12分，本题共36分）15．设谓词公式)),,()(),()((z x y B z y x A x ∀→∃，试（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元． 16．设集合A ={{1},1,2}，B ={1,{1,2}}，试计算（1）（A -B ）； （2）（A ∩B ）； （3）A ×B ．17．设G =<V ，E >，V ={ v 1，v 2，v 3，v 4 }，E ={ (v 1,v 3)，(v 2,v 3)，(v 2,v 4)，(v 3,v 4) }，试 （1）给出G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形． 六、证明题（本题共8分）18．设A ，B 是任意集合，试证明：若A ⨯A=B ⨯B ，则A=B ．试题解答(供参考)一、单项选择题（每小题3分，本题共15分） 1．A 2．C 3．B 4．B 5．D 二、填空题（每小题3分，本题共15分）6．{<2, 2>，<2, 3>，<2, 4>，<3, 3>}，<3, 4>，<4, 4>} 7．<a , a >，< b , b > 8．5 9．n +k -210．真（或T ，或1）三、逻辑公式翻译（每小题4分，本题共12分）11．设P ：今天考试，Q ：明天放假． （2分） 则命题公式为：P ∧Q ． （6分）12．设P ：我去旅游，Q ：我有时间， （2分）则命题公式为：P →Q ． （6分） 四、判断说明题（每小题7分，本题共14分）13．错误． （3分）当图G 不连通时图G 不为欧拉图． （7分） 14．错误． （3分） 集合A 的最大元与最小元不存在，a 是极大元，f 是极小元，． （7分） 五．计算题（每小题12分，本题共36分）15．（1）∃x 量词的辖域为)),,()(),((z x y B z y x A ∀→， （3分）∀z 量词的辖域为),,(z x y B , （6分） （2）自由变元为)),,()(),((z x y B z y x A ∀→中的y ， （9分）约束变元为x 与z ． （12分）16．（1）A -B ={{1},2} （4分）（2）A ∩B ={1} （8分） （3）A ×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分） 17．（1）G 的图形表示为(如图三)：（3分）图三 （2）邻接矩阵：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0110101111000100（6分） （3）v 1，v 2，v 3，v 4结点的度数依次为1，2，3，2 （9分） （4）补图如图四所示：（12分）图四六、证明题（本题共8分）18．证明：设x ∈A ，则<x ，x >∈A ⨯A ， （1分） 因为A ⨯A=B ⨯B ，故<x ，x >∈B ⨯B ，则有x ∈B ， （3分） 所以A ⊆B ． （5分） 设x ∈B ，则<x ，x >∈B ⨯B ， （6分） 因为A ⨯A=B ⨯B ，故<x ，x >∈A ⨯A ，则有x ∈A ，所以B ⊆A ． （7分） 故得A=B ． （8分）《离散数学》题库及答案四一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“如果他掌握了计算机的用法，那么他就能完成这项工作．”翻译成命题公式．12．将语句“前天下雨，昨天还是下雨．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案《离散数学》题库及答案五一、单项选择题（每小题3分，本题共15分）试题及答案《离散数学》题库及答案六一、单项选择题（每小题3分，本题共15分）二、填空题（每小题3分，本题共15分）三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“昨天下雨”翻译成命题公式．12．将语句“小王今天上午或者去看电影或者去打球”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）五、计算题（每小题12分，本题共36分）六、证明题（本题共8分）试题答案及评分标准（供参考）。
第一章命题逻辑内容：命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法等证明方法。
教学目的：1. 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。
2. 熟练掌握常用的基本等价式及其应用。
3. 熟练掌握（主）析/合取范式的求法及其应用。
4. 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。
5. 熟练掌握形式演绎的方法。
教学重点：1 .命题的概念及判断2 .联结词，命题的翻译3. 主析（合）取范式的求法4. 逻辑推理教学难点：1. 主析（合）取范式的求法2. 逻辑推理1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示命题通常使用大写字母 A , B,…，Z或带下标的大写字母或数字表示,如A i, [10], R等，例如A1：我是一名大学生。
A1：我是一名大学生.[10]:我是一名大学生。
R：我是一名大学生。
1.2命题联结词1.2.1否定联结词「P1.2.2合取联结词A1.2.3 析取联结词V1.2.4 条件联结词—125126 与非联结词T性质：(1)P T P=「( PAP)二「P；(2)(P T Q)T( P T Q) -「( P T Q) - PAQ；(3)( P T P)T( Q TQ) -「P T「Q= P V Q。
127 或非联结词J性质:(1) P J P=「( P V Q) =「P;(2)( P J Q )；( P J Q) =「( P J Q) = P V Q;(3)( P J P)J( Q J Q) =「P Q=P V-Q) = PAQ1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2 ）如果P是公式，则「P是公式；（3）如果P、Q是公式,则PAQ、PVQ、P > Q、P Q都是公式；（4）当且仅当能够有限次的应用（1）、（2）、（3）所得到的包括命题变元、联结词和括号的符号串是公式。
可编辑修改精选全文完整版离散数学习题答案习题一：P121.判断下列句子哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？(1)中国有四大发明。
(2)5是无理数。
(3)3是素数或4是素数。
(4)x2+3<5，其中x是任意实数。
(5)你去图书馆吗？(6)2与3都是偶数。
(7)刘红与魏新是同学。
(8)这朵玫瑰花多美丽呀！(9)吸烟请到吸烟室去！(10)圆的面积等于半径的平方乘π。
(11)只有6是偶数，3才能是2的倍数。
(12)8是偶数的充分必要条件是8能被3整除。
(13)2025年元旦下大雪。
1、2、3、6、7、10、11、12、13是命题。
在上面的命题中，1、2、7、10、13是简单命题；1、2、10是真命题；7的真值现在还不知道。
2.将上题中是简单命题的命题符号化。
(1)p：中国有四大发明。
(2)q：5是无理数。
(7)r：刘红与魏新是同学。
(10)s：圆的面积等于半径的平方乘π。
(1)t：2025年元旦下大雪。
3.写出下列各命题的否定式，并将原命题及其否定式都符号化，最后指出各否定式的真值。
“5是有理数”的否定式是“5不是有理数”。
解：原命题可符号化为：p：5是有理数。
其否定式为：非p。
非p的真值为1。
4.将下列命题符号化，并指出真值。
(1)2与5都是素数。
(2)不但π是无理数，而且自然对数的底e也是无理数。
(3)虽然2是最小的素数，但2不是最小的自然数。
(4)3是偶素数。
(5)4既不是素数，也不是偶数。
a：2是素数。
b：5是素数。
c：π是无理数。
d：e是无理数。
f：2是最小的素数。
g：2是最小的自然数。
h：3是偶数。
i：3是素数。
j：4是素数。
k：4是偶数。
解：（1）到（5）的符号化形式分别为a∧b，c∧d，f∧非g，h∧i，非j∧非k。
这五个复合命题的真值分别为1，1，1，0，0。
5.将下列命题符号化，并指出真值。
a：2是偶数。
b：3是偶数。
c：4是偶数。
离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。
b)我今天进城，除非下雨。
c)仅当你走，我将留下。
2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。
c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R))↔(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。
（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)∀x∃y(x+y=4)b)∃y∀x (x+y=4)3.求∀x(F(x)→G(x))→(∃xF(x)→∃xG(x))的前束范式。
（4分）4.判断下面命题的真假，并说明原因。
（每小题2分，共4分）a)（A⋃B）－C=(A-B) ⋃(A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。
（每小题5分，共10分）a)A→(B∧C),(E→⌝F)→⌝C, B→(A∧⌝S)⇒B→Eb)∀x(P(x)→⌝Q(x)), ∀x(Q(x)∨R(x))，∃x⌝R(x) ⇒∃x⌝P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠∅且B≠∅，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。
