下载文档原格式
离散数学试题（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 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。
数理逻辑习题判断题1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →⌝→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧⌝∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →∃=→∀ （ √ ）6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ）8．))()((x G x F x →∀是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ∃→∀是永真式（ √ ）11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ）13．))()((x G x F x →∀是永假式 （ × ）14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨⌝ （ × ） 18．命题公式 )(r q p →∨⌝的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →∀是闭式（ × ）单项选择题1． 下述不是命题的是（ A ）A．花儿真美啊! B．明天是阴天。
C．2是偶数。
D．铅球是方的。
2．谓词公式（∀y）（∀x）（P（x）→R（x,y））∧∃yQ（x,y）中变元y （B）A．是自由变元但不是约束变元B．是约束变元但不是自由变元C．既是自由变元又是约束变元D．既不是自由变元又不是约束变元3．下列命题公式为重言式的是（ A ）A．p→ （p∨q）B．（p∨┐p）→qC．q∧┐q D．p→┐q4．下列语句中不是．．命题的只有（A ）A．花儿为什么这样红？B．2+2=0C．飞碟来自地球外的星球。
南京邮电大学2016/2017学年第一学期《离散数学》期末试卷（A 卷答案）院(系)班级学号姓名题号一二三四总分得分一、填空题（20分，每空2分）1、A×B={<1,1>,<2,2>,<3,1>,<3,2>,<1,2>,<2,1>}，P (B )是B 的幂集，则P (B )={∅,{1},{2},{1,2}}，|P (P (B ))|=16。
2、设集合A ={x|x 是book 中的字母}，B ={x|x 是black 中的字母}，则A B ={b ,k }，A-B ={o }。
3、设P ：我今天进城，Q ：今天下雨，则命题“我今天进城，除非下雨。
”可符号化为¬Q →P 或P ∨Q 或¬P →Q 。
4、设A={1,2,3}，P (A )是A 的幂集，代数系统(),P A <> 的幺元为∅，零元为A 或{1,2,3}。
5、无向图G =<V ,E >，如图1所示，则该无向图的点连通度()k G =2，边连通度()G λ=2，结点v 1到v 1的长度小于等于3的回路的数目=7。
二、判断题，正确的记“T”，错误的记“F”。
（20分，每题2分）1、Q P P Q ⌝∨⇔→（F ）2、命题函数是命题。
（F）3、{|()()}x P x P x φ=∧⌝，其中()P x 是任意谓词。
（T ）4、A 和B 为两个不相等的非空集合，则一定有A B B A ⨯≠⨯。
（T ）5、若R 为集合A 上的关系，且R 不是对称的，则R 一定是反对称的。
（F ）6、无向完全图K n (n >2)一定是汉密尔顿图。
（T）7、在代数系统中，若元素a 既有左逆元，又有右逆元，则a 一定有逆元。
（F ）8、存在不同构的8元布尔格。
（F ）9、有补格一定是有界格且每个元素都存在一个或多个补元。
（T）得分得分装订线内不要答题自觉遵守考试规则，诚信考试，绝不作弊10、结点的度全为偶数的无向简单图一定可以一笔画。
离散数学试题与答案试卷一一、填空 20% （每小题2分）1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =⋃B A 。
2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。
3．设P ，Q 的真值为0，R ，S 的真值为1，则)()))(((S R P R Q P ⌝∨→⌝∧→∨⌝的真值= 。
4．公式P R S R P ⌝∨∧∨∧)()(的主合取范式为 。
5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ∀→∃ 在I 下真值为 。
6．设A={1，2，3，4}，A 上关系图为则 R 2 = 。
7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则 R= 。
8．图的补图为 。
9．设A={a ，b ，c ，d} ，A 上二元运算如下：A BC* a b c d a b c da b c d b c d a c d a b d a b c那么代数系统<A ，*>的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。
10．下图所示的偏序集中，是格的为 。
二、选择 20% （每小题 2分）1、下列是真命题的有（ ） A ． }}{{}{a a ⊆；B ．}}{,{}}{{ΦΦ∈Φ；C ． }},{{ΦΦ∈Φ；D ． }}{{}{Φ∈Φ。
2、下列集合中相等的有（ ）A ．{4，3}Φ⋃；B ．{Φ，3，4}；C ．{4，Φ，3，3}；D ． {3，4}。
3、设A={1，2，3}，则A 上的二元关系有（ ）个。
A ． 23 ； B ． 32 ； C ． 332⨯； D ． 223⨯。
4、设R ，S 是集合A 上的关系，则下列说法正确的是（ ） A ．若R ，S 是自反的， 则S R 是自反的； B ．若R ，S 是反自反的， 则S R 是反自反的； C ．若R ，S 是对称的， 则S R 是对称的； D ．若R ，S 是传递的， 则S R 是传递的。
贵州大学计算机科学与技术专业2016-2017学年第一学期考试试卷(A)离散数学及其应用注意事项：1. 请考生按要求在试卷装订线内填写姓名、学号和年级专业。
2. 请仔细阅读各种题目的回答要求，在规定的位置填写答案。
3. 不要在试卷上乱写乱画，不要在装订线内填写无关的内容。
4. 满分100分，考试时间为120分钟。
一．单项选择题（每小题2分，共20分）1. p：他努力学习，q：他取得好成绩，则命题“如果他努力学习，他一定取得好成绩”的符号化为（）。
A．q→p B．p→q C．p∨q D．p∧ q2．设论域是集合｛a ,b｝,消去公式（∃x）P(x)→（∃y）Q(y）中的量词后得（）。
A．P(a)→Q(a） B．P(b)→Q(b）C．(P(a)∧P(b))→(Q(a)∧Q(b)) D．(P(a)∨P(b))→(Q(a)∨Q(b)) 3．f是A到B的双射，则f满足（）。
A．单射 B．满射 C．单射和满射 D．以上说法都不对4.设A={1，2，3},R={<1,1>,<2,2>,<1,2>,<2,1>,<2,3>,<3,3>}是A上的二元关系,则下列说法正确的是（）。
A.R是反自反的B. R是对称的C.R是可传递的D. R是自反的5. N为自然数集，〈N，+〉（其中+为普通加法）不能构成（）。
A．半群 B．独异点 C．交换半群 D．群6．设S={a, b}，P(S)为S的幂集合，则P(S)×S = （）。
A. S×SB. S×P(S)C. {<S, a>, <S, b>}D. {<φ,a>, <φ,b>, <{a},a>, <{a},b>, <{b},a>, <{b},b>, <S,a>, <S,b>}7. 设A={1,2,3,4}，R={<1,1>,<1,4>,<2,1>,<3,4>,<4,1>}为A上的二元关系，则R R 中有（）个有序对。
离散数学考试题及答案一、选择题1. 关于图论的基本概念，以下哪个说法是正确的？A. 无向图中的边无方向性，有向图中的边有方向性。
B. 有向图中的边无方向性，无向图中的边有方向性。
C. 无向图和有向图都是由顶点和边组成的。
D. 无向图和有向图都只由边组成。
答案：A2. “若顶点集合为V，边集合为E，那么图G可以表示为G(V, E)”是关于图的哪个基本概念的描述？A. 图的顶点B. 图的边C. 图的邻接D. 图的表示方法答案：D3. 以下哪个命题是正确的？A. 若集合A和B互相包含，则A和B相等。
B. 若集合A和B相交为空集，则A和B相等。
C. 若集合A和B相等，则A和B互相包含。
D. 若集合A和B相等，则A和B相交为空集。
答案：C二、填空题1. 有一个集合A = {1, 2, 3, 4}，则集合A的幂集的元素个数为__________。
答案：162. 设A = {a, b, c}，B = {c, d, e}，则集合A和B的笛卡尔积为__________。
答案：{(a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, c), (c, d), (c, e)}3. 若p为真命题，q、r为假命题，则合取范式(p ∨ q ∨ r)的值为__________。
答案：真三、计算题1. 计算集合A = {1, 2, 3, 4}和集合B = {3, 4, 5, 6}的交集、并集和差集。
答案：交集：{3, 4}并集：{1, 2, 3, 4, 5, 6}差集：{1, 2}2. 计算下列命题的真值：(~p ∨ q) ∧ (p ∨ ~q)，其中p为真命题，q为假命题。
答案：真四、证明题证明：对于任意集合A和B，如果A和B互相包含，则A和B相等。
证明过程：假设A和B互相包含，即A包含于B且B包含于A。
设x为集合A中的任意元素，则x也必然存在于集合B中，即x属于B。
同理，对于集合B中的任意元素y，y也属于集合A。
离散数学考试题及答案一、选择题（每题5分，共20分）1. 下列哪个选项不是离散数学的研究对象？A. 图论B. 组合数学C. 微积分D. 逻辑学答案：C2. 在逻辑学中，下列哪个命题是真命题？A. 如果今天是周一，那么明天是周二。
B. 如果今天是周一，那么明天是周三。
C. 如果今天是周一，那么明天是周四。
D. 如果今天是周一，那么明天是周五。
答案：A3. 在集合论中，下列哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 在图论中，下列哪个术语描述的是图中的顶点集合？A. 边B. 路径C. 子图D. 顶点答案：D二、填空题（每题5分，共20分）1. 如果一个集合A包含5个元素，那么它的子集个数是______。
答案：322. 在逻辑学中，如果命题P和命题Q都是真命题，那么复合命题“P且Q”的真值是______。
答案：真3. 在图论中，如果一个图的顶点数为n，那么它的最大边数是______。
答案：n(n-1)/24. 如果一个二叉树的深度为3，那么它最多包含______个节点。
答案：7三、简答题（每题10分，共30分）1. 请简述什么是图的连通性，并给出一个例子。
答案：图的连通性是指在图中任意两个顶点之间都存在一条路径。
例如，在一个完全图K3中，任意两个顶点之间都可以通过一条边直接连接，因此它是连通的。
2. 解释什么是逻辑蕴含，并给出一个例子。
答案：逻辑蕴含是指如果一个命题P为真，则另一个命题Q也必须为真。
例如，命题P：“如果今天是周一”，命题Q：“明天是周二”。
如果今天是周一，那么根据逻辑蕴含，明天必须是周二。
3. 请描述什么是二叉搜索树，并给出它的一个性质。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点的数，右子树只包含大于当前节点的数。
它的一个性质是中序遍历可以得到一个有序序列。
四、计算题（每题15分，共30分）1. 给定一个集合A={1, 2, 3, 4, 5}，请计算它的幂集，并列出所有元素。
离散数学一、填空题(本大题共48分，共16小题，每小题3分)1.--公式为之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2.无向图G具有是生成树，当且仅当的，若G为(n,m)连通图，要确定G的一棵生成树必删掉G的条边。
3.一个无向图的欧拉回路要求经过图中一次且仅一次，汉密顿图要求经过图中一次且仅一次。
4.设P：我生病，Q：我去学校(1)命题“我虽然生病但我仍去学校”符号化为o (2)命题“只有生病的时候，我才不去学校”符号化为o (3)命题"如果我生病，那么我不去学校”符号化为o5.设有33盏灯，拟公用一个电源，则至少需要5个插头的接线板数6.若HlAH2A-AHn是 ,则称Hl, H2, -Hn是相容的，若HlAH2A-AHn是 ,则称H1.H2, -Hn是不相容的7.设f,g,h 是N 到N上的函数(N 为自然数集合),f(n)=n+l;g(n)=2n;h(n)=0；贝lj(fdg)oh=8.K5的点连通度为 ,边连通度为o9.A={1, 2, 3, 4, 5, 6, 8, 10, 24, 36}, R 是A 上的整除关系。
子B={1, 2, 3, 4},那么B的上界是； B的下界是；：6的上确界是; B的下确界为10.命题公式P-*QAR的对偶式为11.设入={1, {2}, <t>},则A的幕集有元素个。
12.设A={0, 1,2, 3}, B={4,6, 7}, C={8, 9, 12, 14}, R1 是由A 到B 的关系,R2 是由B到C原关系，分别定义为Rl={<2, 6>, <3, 4>, <0, 7>} ;R2={<4, 8>, <4, 12>, <6, 12>,〈7, 14〉},则复合关系RloR2 为：13.设A= {<i)}, B={<t>, (<!>}},贝i]P(A) nP(B)= 。
2016注意事项:1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。
２、第二遍复习按照考试大纲的总结把重点内容再做复习。
另外，把大纲中指定的例题及书后习题认真做一做。
检验一下主要内容的掌握情况。
３、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。
离散数学综合练习题一、选择题1．令p : 今天下雪了,q ：路滑，ｒ:他迟到了。
则命题“下雪路滑,他迟到了” 可符号化为( Ａ ）。
Ａ． p q r ∧→ﻩB. p q r ∨→C. p q r ∧∧D. p q r ∨↔２.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为( Ｂ )。
A. (()((),0))x P x L f x ∀∧B. (()((),0))x P x L f x ∀→C ． ()((),0)xP x L f x ∀∧ﻩD. ()((),0)xP x L f x ∀→３.设()F x ：x 是人,()G x :x 犯错误,命题“没有不犯错误的人”符号化为(D ）。
A ．(()())x F x G x ∀∧B ． (()())x F x G x ⌝∃→⌝Ｃ．(()())x F x G x ⌝∃∧ﻩD. (()())x F x G x ⌝∃∧⌝＊4.下列命题公式不是永真式的是（ A )。
A ． ()p q p →→ﻩＢ. ()p q p →→C . ()p q p ⌝∨→D . ()p q p →∨5．设p ：我们划船，ｑ:我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是( B )。
Ａ. p q ∧ ﻩＢ. ()p q ⌝∧Ｃ． p q ⌝∧⌝ﻩﻩﻩD. p q ⌝∧6．设()R x :ｘ为有理数；()Q x :x 为实数。
命题“任何有理数都是实数”的符号化为( A ）A ．()(()())∀→x R x Q x ﻩB ．()(()())∀∧x R x Q xC.()(()())x R x Q x ∃∧D.(()())x R x Q x ∃→7. 设个体域{,}D a b =,与公式()xA x ∃等价的命题公式是（ Ｃ )A.()()A a A b ∧ﻩB ．()()A a A b →C ．()()A a A b ∨Ｄ．()()A b A a → 8.无向图G 有２０条边,4个6度顶点,2个５度顶点，其余均为2度顶点,则Ｇ一共有（ Ｃ )个顶点。
离散数学考试题及答案一、选择题（每题2分，共20分）1. 在集合论中，下列哪个符号表示属于关系？A. ∈B. ∉C. ⊆D. ∩答案：A2. 对于命题逻辑，下列哪个是真值表的表示方法？A. 真值表B. 逻辑图C. 布尔代数D. 集合论答案：A3. 以下哪个是图论中的基本单位？A. 点B. 线C. 面D. 体答案：A4. 函数f(x) = x^2 + 3x + 2在x=-1处的值是：A. 0C. 4D. 6答案：C5. 在关系数据库中，以下哪个操作用于删除表中的记录？A. SELECTB. INSERTC. UPDATED. DELETE答案：D6. 以下哪个是离散数学中的归纳法证明方法？A. 直接证明法B. 反证法C. 归纳法D. 构造性证明法答案：C7. 在逻辑中，以下哪个是析取命题？A. P ∧ QB. P ∨ QC. ¬PD. P → Q答案：B8. 以下哪个是图的遍历算法？B. BFSC. Dijkstra算法D. Floyd算法答案：B9. 在集合{1, 2, 3}上，以下哪个是幂集？A. {∅, {1}}B. {1, 2}C. {1, 2, 3}D. 所有选项答案：D10. 以下哪个是递归算法的特点？A. 不能自我调用B. 必须有一个终止条件C. 必须有一个基本情况D. 所有选项答案：D二、填空题（每空2分，共20分）1. 在离散数学中，_________ 表示一个命题的否定。
答案：¬P2. 如果集合A和集合B的交集为空集，那么A和B被称为_________。
答案：不相交3. 一个函数f: A → B是_________，如果对于集合B中的每个元素b，集合A中至少有一个元素a与之对应。
答案：满射4. 在图论中，一个没有环的连通图被称为_________。
答案：树5. 一个命题逻辑公式是_________，如果它在所有可能的真值分配下都是真的。
答案：重言式6. 一个关系R在集合A上是_________，如果对于A中的任意两个元素a和b，如果(a, b)属于R，则(b, a)也属于R。
1.(单选题)A．明年“五一”是晴天。
B．这朵花多好看呀！。
C．这个男孩真勇敢啊！ D．明天下午有会吗？答题： A. B. C. D. （已提交）参考答案：A问题解析：2.(单选题) 在上面句子中，是命题的是( )A．1＋101＝110 B．中国人民是伟大的。
C．这朵花多好看呀！ D．计算机机房有空位吗？答题： A. B. C. D. （已提交）参考答案：B问题解析：3.(单选题) 在上面句子中，是命题的是( )A．如果天气好，那么我去散步。
B．天气多好呀！C．x=3。
D．明天下午有会吗？答题： A. B. C. D. （已提交）参考答案：A问题解析：4.(单选题) 在上面句子中( )是命题下面的命题不是简单命题的是( )A．3 是素数或4 是素数B．2018 年元旦下大雪C．刘宏与魏新是同学 D．圆的面积等于半径的平方与π之积答题： A. B. C. D. （已提交）参考答案：A问题解析：5.(单选题) 下面的表述与众不一致的一个是( )A．P ：广州是一个大城市 B．ØP ：广州是一个不大的城市C．ØP ：广州是一个很不小的城市 D．ØP ：广州不是一个大城市答题： A. B. C. D. （已提交）参考答案：C问题解析：6.(单选题) 设，P：他聪明；Q：他用功。
在命题逻辑中，命题：“他既聪明又用功。
”可符号化为：()A．PÙQ B．P®QC．PÚØQ D．PÙØQ答题： A. B. C. D. （已提交）参考答案：A问题解析：7.(单选题) 设：P ：刘平聪明。
Q：刘平用功。
在命题逻辑中，命题：“刘平不但聪明，而且用功”可符号化为：()A．PÙQ B．ØPÚQC．PÚØQ D．PÙØQ答题： A. B. C. D. （已提交）参考答案：A问题解析：8.(单选题)设：P：他聪明；Q：他用功。
《离散数学》考试试卷（试卷库14卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分考试时限：120 分钟⼀、选择题（每题2分，共20分）1. 下述命题公式中，是重⾔式的为( )（A ）)()(q p q p ∨→∧（B ）q p ∨))()((p q q p →∨→?（C ）q q p ∧→?)(（D ）q q p →?∧)(2. 对任意集合A,B,C,下列结论正确的是（）（A ）若A ?B,B ∈C,则A ?C ；（B ）若A ∈B,BC,则A ?C ；（C ）若A ?B,B ∈C,则A ∈C ；（D ）若A ∈B,B ?C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系, ,则由R 产⽣的S S ?上⼀个划分共有( )个分块。
（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是⼀棵树当且仅当G 中( )（A ）有些边是割边（B ）每条边都是割边（C ）所有边都不是割边（D ）图中存在⼀条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平⾯图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下⾯命题公式中真值为1的是（）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=中,结点总度数与边数的关系是（）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公⽤⼀个电源,则⾄少需有五插头的接线板数（）（A ）７（B ）８（C ）９（D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（）（A ）11 （B ）14 （C ）17（D ）15⼆、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。
离散数学试题与答案【篇一：离散数学试题及答案】一、填空题1 设集合a,b，其中a＝{1,2,3}, b= {1,2}, 则a - b＝____________________;＝ __________________________ .3. 设集合a = {a, b}, b = {1, 2}, 则从a到b的所有映射是__________________________ _____________, 其中双射的是__________________________.4. 已知命题公式g＝?(p?q)∧r，则g的主析取范式是_____________________________________________________________________________________ ____.5.设g是完全二叉树，g有7个点，其中4个叶点，则g的总度数为__________，分枝点数为________________.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 =____________________________,=________________________.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 变成完全图。
精品文档离散数学考试试题（A卷及答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？1)((P?Q)∧Q)?((Q∨R)∧Q) 2)?((Q?P)∨?P)∧(P∨R)3)((?P∨Q)?R)?((P∧Q)∨R)解：1)永真式；2）永假式；3)可满足式。
二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。
解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4））?（0∨0）∧（0∨1）?1∧1?0三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。
因为|BA|=|B||A|=mn，所以A到B的函数mn个。
（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
四、解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>}s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>}t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>}五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。
离散数学考试试题及答案一、选择题（每题2分，共20分）1. 在集合论中，以下哪个选项表示“属于”关系？A. ⊆B. ⊂C. ∈D. ⊇答案：C2. 以下哪个命题是真命题？A. p ∧ ¬pB. p ∨ ¬pC. p → ¬pD. ¬(p → q) → p答案：B3. 以下哪个选项是命题逻辑中的德摩根定律？A. ¬(p ∨ q) = ¬p ∧ ¬qB. ¬(p ∧ q) = ¬p ∨ ¬qC. ¬(p → q) = p ∧ ¬qD. ¬(p ∨ q) = ¬p ∨ ¬q答案：A4. 以下哪个选项是命题逻辑中的蕴含等价？A. p → q ≡ ¬p ∨ qB. p → q ≡ ¬q → ¬pC. p → q ≡ p ∨ ¬qD. p → q ≡ ¬p ∧ q答案：A5. 以下哪个选项是关系的性质？A. 反身性B. 对称性C. 传递性D. 所有选项都是答案：D6. 以下哪个选项是图论中的有向图？A. 无向图中的边没有方向B. 有向图中的边有方向C. 混合图中的边既有方向也有无方向D. 所有选项都是答案：B7. 在图论中，以下哪个选项是树的性质？A. 树是无环的B. 树是连通的C. 树是无向图D. 所有选项都是答案：D8. 以下哪个选项是布尔代数的基本运算？A. 与（AND）B. 或（OR）C. 非（NOT）D. 所有选项都是答案：D9. 以下哪个选项是组合数学中的排列？A. 从n个不同元素中取出m个元素的组合B. 从n个不同元素中取出m个元素的排列C. 从n个相同元素中取出m个元素的组合D. 从n个相同元素中取出m个元素的排列答案：B10. 以下哪个选项是集合论中的幂集？A. 一个集合的所有子集的集合B. 一个集合的所有真子集的集合C. 一个集合的所有超集的集合D. 一个集合的所有子集的个数答案：A二、简答题（每题10分，共30分）1. 简述命题逻辑中的等价命题是什么？答案：等价命题是指两个命题在所有可能的真值赋值下都具有相同真值的命题。
