当前位置：文档之家 › 南昌大学本科离散试卷及答案

南昌大学本科离散试卷及答案

  • 格式：doc
  • 大小：127.00 KB
  • 文档页数：6
2、求命题公式(p→q)∧r的主合取范式并求命题公式的成假赋值
3、将下列命题符号化。并讨论它们的真值
（1）凡是人都要休息。
（2）每个自然数都有比它大的自然数。
4、用CP规则证明。
(x)(F(x)→R(x))(x)F(x)→(x)R(x)
5、设A=1,2,3,4,5，A上的等价关系R定义为：
R=1,2,2,1,3,4,4,3∪IA
2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。
一、填空题(每题4分，共20分)
ห้องสมุดไป่ตู้得分
评阅人
1、使得公式q∧(p→q)→p成真的赋值是：
使得公式q∧(p→q)→p成假的赋值是：
2、设A=a,b，B=1,2,3，求：A×B=
B×A=
3、一棵无向树T有2个4度结点，3个3度结点，其余的结点都是树叶，问T有 片树叶?
4、指出公式(z) (P(x)∧(x)R(x,z)→(y)Q(x,y))∨R(x,y)中
的约束变元 和 自由变元。
5、.A=1,2,3,4，A上二元关系R和S分别为：
R=1,2,2,4,3,3S=1,3,2,4,4,2
R S =
二、综合题(每小题10分，共80分)
得分
评阅人
1、用等价演算证明：
p→(q→r)(p∧q)→r
p∨(q∨r)(条件等价式)
(p∨q)∨r(结合律)
(p∧q)∨r(德·摩根律)
(p∧q)→r
2、(p→q)∧r
(p∨q)∧r
(p∨q∨r)∧(p∨q∨r)∧(p∨r)∧(p∨r)
(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)
(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)∧(p∨q∨r)
画出关系图，找出所有等价类，总结等价类和关系图的关系。
.
6、无向图G如图所示。
⑴写出G的邻接矩阵。
⑶求G中长度为3的路的总数，其中有多少条回路。
⑷求G的连通矩阵。
7、求带权3,4,5,6,7,8,9的最优二叉树T。
8、某单位按编制有7个工作空缺：p1，p2，…，p7，有10个申请者：a1，a2，…，a10。它们能胜任的工作集合依次是p1, p5, p6，p2, p6, p7，p3, p4，p1, p5，p6, p7，p3，p2, p3，p1, p3，p1，p5。如果规定每个申请者最多只能安排一个工作。试给出一种方案使分配到工作的申请者最多。
离散数学B卷答案
一填空题
1成真的赋值是：00，10，11成假的赋值是：01
2、A×B=a,1,a,2,a,3,b,1,b,2,b,3
B×A=1,a,1,b,2,a,2,b,3,a,3,b
3、T有9片叶子
4、约束变元：x，y，z，自由变元：x，y
5、1,2,1,3,3,3,4,2
二、综合题
1、p→(q→r)
8、解：按题意构造一个二部图G=<X,E,Y>，其中X=p1，p2，…，p7，Y=a1，a2，…，a10，E表示合格工作岗位关系。如图所示。
在图中可以求得一个最大匹配：
M=(p1,a9),(p2,a2),(p3,a6), (p4,a3),(p5,a4),(p6,a1),(p7,a5)
南昌大学2007～2008学年第一学期期末考试试卷
试卷编号：( B)卷
课程编号：课程名称：离散数学考试形式：闭卷
适用班级：姓名：学号：班级：
学院：专业：考试日期：
题号
一
二
三
四
五
六
七
八
九
十
总分
累分人签名
题分
20
80
100
得分
考生注意事项：1、本试卷共4页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。
∏0,2,4,5,6
使得命题公式(p→q)∧r成假的赋值是：000,010,100,101,110。
3、（1）设R(x)：x是人。S(x)：x要休息。
“凡是人都要休息。”符号化为：(x)(R(x)→S(x))
它的真值为：真。
（2）解：设N(x)：x是自然数。G(x,y)：x比y大。
“每个自然数都有比它大的自然数。”符号化为：(x)(N(x)→(y)(N(y)∧G(y,x)))
关系图每一个连通分支的结点构成的集合是一个等价类。或者说，每一个等价类导出了关系图的一个连通分支。
6、解：⑴邻接矩阵
（2）A= ，A2= =
A3= =
长度为3的路的总条数66条，其中回路12条。
（3）C4=A0+A1+A2+A3= ，G的连通矩阵为P=
7、最优树的权为：W(T)=(3＋4)×4＋7×3＋(5＋6)×3＋(8＋9)×2=116。
它的真值为：真
4、证明：
⑴(x)F(x)P(附加前提)
⑵F(c)US⑴
⑶(x)(F(x)→R(x))P
⑷F(c)→R(c)US⑶
⑸R(c)T⑵⑷假言推理
⑹(x)R(x)UG⑸
⑺(x)F(x)→(x)R(x)CP
5、解：R的关系图如图4.34所示。
[1]R=[2]R=1,2，[3]R=[4]R=3,4，[5]R=5

合集下载

大学《离散数学》题库及答案

大学《离散数学》题库及答案

《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式∀x A和∃x A中，称x为指导变元，A为量词的辖域。

在∀x A和∃x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。

于是A(x)、B(y，x)和∃z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。

若是，给出命题的真值。

( )(1)北京是中华人民共和国的首都。

(2) 陕西师大是一座工厂。

(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。

(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。

）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

离散数学本科试题及答案

离散数学本科试题及答案

离散数学本科试题及答案一、单项选择题（每题2分，共20分）1. 集合{1,2,3}的子集个数是（）。

A. 4B. 6C. 7D. 8答案：D2. 若A={x|x^2-3x+2=0}，则集合A的元素个数为（）。

A. 0B. 1C. 2D. 3答案：C3. 命题“若x>0，则x^2>0”的逆否命题是（）。

A. 若x≤0，则x^2≤0B. 若x^2≤0，则x≤0C. 若x≤0，则x^2>0D. 若x^2>0，则x>0答案：B4. 函数f(x)=x^2在区间[-1,1]上的值域是（）。

A. [-1,1]B. [0,1]C. [0,4]D. [-1,4]答案：B5. 有限集合A={1,2,3}，B={2,3,4}，则A∩B=（）。

A. {1}B. {2,3}C. {3,4}D. {4}答案：B6. 命题“若x>0，则x^2>0”的逆命题是（）。

A. 若x>0，则x^2>0B. 若x^2>0，则x>0C. 若x≤0，则x^2≤0D. 若x^2≤0，则x≤0答案：B7. 函数f(x)=x^2在区间[-1,1]上是（）。

A. 增函数B. 减函数C. 非单调函数D. 常数函数答案：C8. 集合{1,2,3}的真子集个数是（）。

A. 4B. 6C. 7D. 8答案：B9. 命题“若x>0，则x^2>0”的否命题是（）。

A. 若x>0，则x^2>0B. 若x^2>0，则x>0C. 若x≤0，则x^2≤0D. 若x^2≤0，则x≤0答案：C10. 有限集合A={1,2,3}，B={2,3,4}，则A∪B=（）。

A. {1,2,3}B. {2,3}C. {1,2,3,4}D. {4}答案：C二、填空题（每题2分，共20分）1. 集合{1,2,3}的幂集是{∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}。

离散B 期末考试试题及参考答案

离散B 期末考试试题及参考答案

青岛理工大学试卷纸共2页第2页
二（15分）
R={<1,1> , <1,2>,<2,1>, <2,2>，<2,3>,<3,1>, <3,3>}
S={<1,1> , <1,2>,<1,3>, <2,3>}
关系图略
关系R：自反； 关系S：反对称，传递
三（20分）（1）(pqq)
所以该式是矛盾式。
2）(P∨Q)R(P∨Q)∨R(P∧Q)∨R
9．整数集合上关于普通加法运算所构成的群〈Z，＋〉中，元素(-2)-3＝_____
10设A={a，b，c}，A上二元关系R={< a, a > , < a, b>,< a, c>, < c, c>},
则自反闭包r（R）=。
11一个班有45个人，在第一次考试中有26人得优秀，在第二次考试中有21人得优秀，如果两次考试都得优秀的有14人，问两次考试都没有得优秀的有_____人？
(pqq)
（2）10分)
求下列公式的主合取范式及主析取范式
(P∨Q)R
四.(10分)设集合A＝{1, 2, 3, 4, 6, 8, 12}，R是A上的整除关系，
（1）画出偏序集(A, R)的哈斯图；
（2）写出集合A的极大元，极小元，最大元，最小元。
青岛理工大学试卷纸共2页第1页
试题要求：1、试题后标注本题得分；2、试卷应附有评卷用标准答案，并有每题每步得分标准；3、试卷必须装订，拆散无效；4、试卷必须用碳素笔楷书，以便誉印；5、考试前到指定地点领取试卷。
其中量词( x)的辖域是_____________。
离散考试试题及答案

离散考试试题及答案

离散考试试题及答案一、单项选择题（每题2分，共10分）1. 在离散数学中，以下哪个概念不是命题逻辑的一部分？A. 命题B. 谓词C. 函数D. 真值表答案：C2. 集合{1, 2, 3}和{3, 2, 1}是否相等？A. 是B. 否答案：A3. 在图论中，一个连通图至少需要多少个顶点？A. 1B. 2C. 3D. 4答案：B4. 以下哪个选项不是关系的性质？A. 自反性B. 对称性C. 传递性D. 互异性答案：D5. 有限自动机和正则表达式之间的关系是什么？A. 它们是等价的B. 它们是完全不相关的C. 有限自动机比正则表达式更强大D. 正则表达式比有限自动机更强大答案：A二、填空题（每题3分，共15分）1. 如果一个命题的否定为真，则该命题为______。

答案：假2. 在集合论中，空集用符号______表示。

答案：∅3. 如果一个图的任意两个顶点都由一条边连接，则称该图为______图。

答案：完全4. 在关系数据库中，一个表的主键必须满足______和唯一性两个条件。

答案：非空5. 一个有n个状态的确定性有限自动机至少需要______个状态来表示其逆。

答案：2^n三、简答题（每题10分，共20分）1. 请简述归纳推理和演绎推理的区别。

答案：归纳推理是从特殊到一般的推理过程，它通过观察特定的实例来推断一般性的结论。

演绎推理则是从一般到特殊的推理过程，它从已知的前提出发，通过逻辑推理得出具体的结论。

2. 什么是二元关系？请给出一个例子。

答案：二元关系是定义在两个集合之间的一种关系，它将第一个集合中的元素与第二个集合中的元素联系起来。

例如，小于关系是实数集上的一个二元关系，它将每一对实数(x, y)联系起来，当且仅当x小于y。

四、计算题（每题15分，共30分）1. 给定一个函数f: {1, 2, 3} → {a, b}，其中f(1) = a，f(2) = b，求f(3)的可能值。

答案：f(3)的可能值为a或b。