《 离散数学》期中考试试卷(2006—2007学年第2学期)

2007下学期期中考试试卷姓名___________________学号 _____________________三总分一二(15) (16.1) (16.2) (17)(18)(19)(20)(21)(22)(23)一 选择题（20%）:将所选择的答案填入下面表格中。

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)(1) 下面“p→q”的等价说法，不正确的是( )：(A) p是q的充分条件；(B) q是p的必要条件；(C) q仅当p；(D) 只有q才p。

(2) 下面不是命题的是：(A) ∀xP(x) (B) x∈{x}∪{{x}} (C) A-B=∅⇔A=B (D) ∀x(P(x)∨P(y))(3) 谓词公式∀x∃yP(x,y)的否定式为( )：(A) ∀x∃y(¬P(x,y)) (B) ∀x∀y(¬P(x,y)) (C) ∃x∀y(¬P(x,y)) (D) ∃x∃y(¬P(x,y))(4) 下面是一些运算的分配性表达式，不成立是( )(A) A∩(B⊕C) = (A∩B)⊕ (A∩C) (B) A∪ (B⊕C) = (A∪B)⊕ (A∪C)(C) (A⊕B)×C = (A×C)⊕(B×C) (D) (A－B)×C = (A×C)－(B×C)(5) 有关关系的逆关系的说法不正确的是( )：等价关系和相容关系的逆关系就是其本身；(A)(B) 偏序关系的逆关系仍然是偏序关系；全序关系的逆关系仍然是全序关系；(C)(D) 良序关系的逆关系仍然是良序关系；(6) 下面推理中，不正确的是(A) p⇒ p∨q (B) q⇒p→q (C) ¬q∧( p→q) ⇒q (D) ¬(p→q) ⇒¬q(7) 命题公式(p→q) ∨( p→q)的成真赋值有___个：(A) 1 (B) 2 (C) 3 (D) 4(8) 下列集合运算中( )是正确的。

《离散数学》期中试题姓名：______________ 学号：______________ 一、确定下列各命题的真、假；（1）∅⊆∅（2）∅⊂∅（3）∅∈∅（4）∅⊆｛∅｝（5）∅∈｛∅｝（6）｛a, b｝⊆｛a , b , c,｛a，b，c｝｝（7）｛a, b｝∈｛a，b，c，｛a，b，c｝｝（8）｛a, b｝⊆｛｛a，b｝，｛｛a，b｝｝｝（9）｛a, b｝∈｛｛a，b｝，｛｛a，b｝｝｝（10）{{a, b}}⊂｛｛a，b｝，｛｛a，b｝｝｝（11）对任意集合A，B，C，、若A∈B，B ⊆ C则A∈C。

（12）对任意集合A，B，C，若A∈B，B ⊆C则A ⊆ C。

（13）对任意集合A，B，C，若A ⊆ B，B∈ C则A ∈ C。

（l4）对任意集合A，B，C，若A ⊆ B，B ∈ C则A ⊆ C。

二、对任意集合A，B，C，证明：（1）（A - B）⊕ B = A ⋃ B （2）（A ⊗ B）⋃ C =（A ⋃ C）⊗（B ⋃ C）（3）A ⋃ B = A ⊕（B ⊕（A ⋂ B））证三、归纳定义下列集合：（1）谓词公式。

（2）命题公式（3）十进制非负有穷小数。

（4）全体十进制有理数。

解四、判断下列语句是否是命题，若是命题则请将其形式化：（1）x>0（2）所有的人都是要死的，但有人不怕死。

（3）我明天或后天去苏州的说法是谣传。

（4）如果买不到飞机票，我哪儿也不去。

（5）除非你陪伴我或代我雇辆车子，否则我不去。

（6）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。

五、用四种不同方法证明下列逻辑等价式：（1）A→(A→B)┝┥A→B（2）A→(B→C)┝┥(A→B)→(A→C)六、用四种不同方法证明下列逻辑蕴涵式：（1）A∧B┝ A↔B（2）(A→B)→A┝ A七、. 设整数集为个体域，判定下列公式的真值(*表示数乘运算)：（1）∀x ∃y(x*y=x)（2）∀x∃y (x*y=1)（3）∀x ∃y(x+y=1)八、. 用谓词公式将下列语句形式化：（1）高斯是数学家，但不是文学家。

合肥学院2007至2008学年第二学期《离散数学》课程考试（ A ）卷计算机 系 06 级 网络工程 专业 学号 姓名一、选择题：(每小题2分，计22分)1.前提,,p q q r r ⌝∨⌝∨⌝的结论是（A.qB.p ⌝C. p q ∨D p q ⌝→2.集合A={1，2，3，4}，下列关系R 中不是等价关系的是（ ） A. {1,1,2,2,3,3}R =〈〉〈〉〈〉；B.{1,1,2,2,3,3,3,2,2,3}R =〈〉〈〉〈〉〈〉〈〉；C.{1,1,2,2,3,3,1,4}R =〈〉〈〉〈〉〈〉；D.{1,2,2,1,1,3,3,1,2,3,3,2}A R I =〈〉〈〉〈〉〈〉〈〉〈〉⋃。

. 3.下列语句中哪个是命题（ ）A.我正在说谎。

B. 5x y + 。

C.地球之外还存在有智慧的动物。

D.请勿践踏草地！ 4．设F(x)：x 是火车，G(x)：y 是汽车，H(x,y)：x 比y 快。

命题“某些汽车比所有的火车慢”的符号化公式是（ ）.(()(()(,)))A y G y x F x H x y ∃→∀∧ .(()(()(,)B y G y x F x H x y ∃∧∀→ .(()(()(,)))C x y G y F x H x y ∀∃→∧ .(()(()(,)D y G y x F x H x y ∃→∀→ 5．利用谓词的约束变元的更名规则和自由变元的代人规则，可将公式(()(,))(,)x P x Q x y R x y ∀→∧改写为（ ）。

.(()(,))(,)A x P y Q x y R z s ∀→∧ .(()(,))(,)B z P z Q z s R x s ∀→∧ .(()(,))(,)C x P s Q x s R x s ∀→∧ .(()(,))(,)D z P s Q z s R z s ∀→∧6.下列公式中正确的等价式是（ ）。

.()()A xA x x A x ∃⇔∃⌝ .()()B xA x x A x ⌝∀⇔∃⌝.(,)(,)C x yA x y y xA x y ∀∃⇔∃∀.(()())(()())D x A x B x x A x B x ∀∧⇔∀∨7．设{},(())A B P P A =∅=，以下不正确的式子是（ ）。

离散数学期中考试试卷班级————姓名————学号————一、单项选择题（每题４分，共３２分。

）1、前提┐P∨Q, ┐Q∨R, ┐R的结论是（）。

A. QB. ┐PC. P∨QD. ┐P→R2、下列语句为命题的是（）。

Ａ．暮春三月，江南草长。

Ｂ．这是多么可爱的风景啊！Ｃ．大家想做什么，就做什么，行吗？Ｄ．请勿践踏草坪！3、下列复合命题为真命题的是（）。

A．如果３＋３≠６，则３是奇数。

B．３是有理数当且仅当加拿大在亚洲。

C．只要乌鸦是黑色的，就有中国是世界上面积最大的国家。

D．２是偶素数是不对的。

４、下列关于谓词公式的论述不正确的是（）。

A．闭式在任何解释下都是命题。

B．可满足式是指存在一个解释使得在该解释下对任一赋值公式都为真。

C．命题公式中的重言式的代换实例是永真式。

D．命题公式中的矛盾式的代换实例是矛盾式。

，Ｂ＝P(P(A))，以下不正确的是（）。

Ａ．｛｝∈ＢＢ．｛｝∈ＢＣ．｛｝包含于ＢＤ．｛｛｛｝｝｝包含于Ｂ６、设集合｛１，２，３｝，下列关系Ｒ中不是等价关系的是（）。

Ａ．Ｒ＝｛（１,１），（２,２），（３,３）｝Ｂ．Ｒ＝｛（１,１），（２,２），（３,３）,（３,２），（２,３）｝Ｃ．Ｒ＝｛（１,１），（２,２），（３,３）, （1, 4）｝Ｄ．Ｒ＝｛（１,１），（２,２），（１,２）,（２,１），（１,３），（３,１）,（３,３），（３,２）,（２,３）｝７、对于如下某个偏序集的哈斯图，其中集合{a,b,c,e}的最大元是（）。

A．c B．d C．e D．无８、命题公式A和B是等值的，是指（）。

A．A和B有相同的命题变项。

B．A和B都是可满足的。

C．当A对某一赋值为真时，B对该赋值也为真。

D．A和B有相同的真值表。

二、填空题（每题３分，共15 分。

）1、设R为非空集合A上的二元关系，如果R满足（）、（）、（），则称R为A上的一个偏序关系。

２、若集合A={1, 2, 3}上的二元关系R1和R2的关系图如下所示，则R1o R2 =（），R2o R1=（）。

《离散数学》期中考试参考答案一、填空题（本题共10个空，每空2分，共20分）1. 设A为任意的公式，B为重言式，则A∨B的公式类型为重言式。

2. 设个体域为非负实数集，A(x,y)表示x+y=y，则∃x∀yA(x,y)的真值为 T ，∀x∃yA(x,y)的真值为 F 。

3. ∀x∃yA(x,y)的否定式是∃x∀y⌝A(x,y) 。

4. 命题公式P→(Q∧⌝R)的成真赋值有 000, 001, 010, 011, 110 ，成假赋值有 100, 101, 111 。

5. {⌝,∧}，或{⌝,∧}，或{↑} 或{↓} 或{⌝,→} 是一个最小联结词组。

6. 由n个命题变元组成不等价的命题公式的个数为22n。

7. 设A是含有n(n≥1)个命题变元的公式，若A为重演式，则A的主析取范式含有2n个小项。

8. 设解释I为：个体域D={a,b},F(x)与G(x)为2个一元谓词，且F(a)=0,G(b)=1,G(a)=1,G(b)=0.在I下，公式∀x(F(x)→G(x))的真值为 F 。

二、简答题（本大题共5个小题，共计60分）1. 在命题逻辑中，把下列命题符号化（每个小题5分，共25分）（1）除非天下大雨，否则小王不会迟到。

P: 天下大雨，Q：小王迟到。

[2分]Q→P [3分]（后面的相同）（2）仅当你走，我将留下。

P: 你走，Q：我留下。

Q→P（3）他一面吃饭，一面听音乐。

P: 他吃饭，Q：他听音乐。

P ∧ Q（4）老王是山东人或河北人。

P: 老王是山东人，Q：老王是河北人。

P∨Q 或 (P∧⌝Q)∨(⌝P∧Q) 或 P∨Q （5）一个数是素数当且仅当它只能被1和它自身整除。

P: 一个数是素数，Q：一个数被1整除，R：一个数被它自身整除。

S：一个数能被除1和它自身以外的数整除P ⇄（Q∧R∧⌝S）2. 在一阶谓词逻辑中，把下列命题符号化（每个小题5分，共10分）（1）尽管有人聪明，但未必一切人都聪明.M(x):x是人，P(x):x聪明。

第 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,B⊆C,则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=<V,E>中,结点总度数与边数的关系是（ ）（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. 有向图中的边无方向性，无向图中的边有方向性。

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}，请计算它的幂集，并列出所有元素。

得分得分成都理工大学2006－2007学年第二学期《离散数学》考试试卷一、填空题（本大题共10小题，每小题2分，共20分）1. 解释（0，0）使命题公式的真值为 0 。

2. 若命题公式在各种解释下取值均为真，则称为 重言式 。

3. 设是人，是花，喜欢，则“有些人喜欢所有的花”可符号化为 。

4.设F(x):x 是人，H(x,y):x 与y 一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_____________________________________。

5. A 上的关系R 是对称的 ⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽。

6. A 上的关系R 是自反的、对称和传递的，称R 是A 上的⎽⎽等价关系⎽⎽⎽⎽⎽⎽⎽⎽⎽。

7. 群是一个存在二元运算可结合，存在⎽⎽⎽单位元⎽⎽⎽⎽⎽⎽⎽，每个元素存在⎽⎽⎽⎽⎽⎽⎽逆元⎽⎽⎽⎽⎽的代数。

8. 若h 是A=〈S ，↑〉到A ′=〈S ′，↑′〉的同态，则h （a ↑b ）=⎽h （a ）↑′h （b ）。

9. 〈R ，+，∙〉是环，则〈R ，+〉是 交换 群，〈R ，∙〉是⎽半群⎽。

10．一个无向图的欧拉回路要求经过图中___每条_边_____一次且仅一次，哈密尔顿回路要求经过图中___每个 顶点______一次且仅一次。

二、选择题（本大题共10小题，每小题1分，共10分）1．下列语句中，（ ）是命题。

q q p p A →→∨=))((A A x x F :)(()y y G :x y x H :),(yA．请把门关上。

B．这朵花多好看呀！7C．下午有会吗？D．2是常数。

2．下述命题为真（）。

A．{a,b}∈{a,b,{{a,b}}} B．{a,b}⊆{a,b,c,{a,b,c}}C．{a,b}∈{{a,b,c},a} D．{φ}⊆φ3．下述不是偏序集合的是（）。

A．〈I，≤〉B．〈R，<〉C．〈{1，2，3，6} 整除〉D．〈{2，4，8，16}，倍数〉4．设R为实数集，函数f：R→R，f(x)=2x，则f是（）A．满射函数 B．单射函数C．双射函数 D．非单射非满5. 设个体域为整数，下列公式中真值为1的是( )。

离散数学考试题目及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={3,4,5}，则A∩B的元素个数为：A. 0B. 1C. 2D. 3答案：B2. 函数f: X→Y是一个双射，当且仅当：A. f是单射且满射B. f是单射C. f是满射D. f是双射答案：A3. 命题p: "x是偶数"，命题q: "x是3的倍数"，下列逻辑运算中，表示"x是6的倍数"的是：A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案：A4. 有向图G中，若存在从顶点u到顶点v的有向路径，则称顶点u可达顶点v。

若G中任意两个顶点都相互可达，则称G为：A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案：A5. 在二进制数系统中，下列哪个数的值最大？A. 1010B. 1100C. 1110D. 1101答案：C6. 布尔代数中，逻辑或运算符表示为：A. ∧B. ∨C. ¬D. →答案：B7. 有限自动机中，状态q0是初始状态，状态q1是接受状态。

若存在从q0到q1的ε-转移，则该自动机：A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案：C8. 命题逻辑中，若命题p和q都为真，则p∧q的真值是：A. 真B. 假C. 可能为真，也可能为假D. 无法确定答案：A9. 集合{1,2,3}的子集个数为：A. 4B. 6C. 7D. 8答案：D10. 若关系R在集合A上是自反的，则对于A中的任意元素a，有：A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案：A二、填空题（每题3分，共15分）1. 集合A={1,2,3}的幂集包含__个元素。

答案：82. 若函数f: X→Y是满射，则对于Y中的任意元素y，至少存在X中的一个元素x，使得f(x)=__。

离散数学基础期中考试题（参考答案）学 期：2007－2008学年第2学期 学生班级：信科0601-04考试时间：2008.4.21 10:10-12:00am学号：姓名：班级：□必修□选修一、填空题（共10分，每空1分）1. 我们称能够表达判断，并且具有确定真值的陈述句为命题。

2. 在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。

3. 把命题公式在其所有解释下所取真值列成一个表，称为G 的真值表。

4. 命题公式G=（P ∧Q ）→R ，则G 共有8个不同的解释；解释（F ，T ，F ）使G 的真值为T 。

5. 在推理理论中，前提在推导过程中的任何时候都可以引入使用，这一推理规则叫做（ P 规则 ）。

6. 设集合}}{,{φφ=A ，A 的幂集{}(),{},{{}},{,{}}A ρφφφφφ=。

7. 设R 是集合A 上的二元关系，如果R 是自反的，则它的关系矩阵的主对角线元素（ 全是1 ）。

8. 设R 是集合A 上的二元关系，R -1是R 的逆关系，则R 的关系矩阵与R -1的关系矩阵具有的关系是（ 互为转置矩阵 ）。

9. 设R 是集合A 上的二元关系，如果关系R 同时具有自反性、反对称性和传递性，则称R 是A 上的一个偏序关系。

二、选择一个正确答案的代号，填入括号中。

（共20分，每小题2分）1. 下列语句中不能成为命题的是（D ）。

A ．地球外的星球上也有人；B ．小王是我的同学，也是我的好朋友；C ．11+1=100；D ．我正在说慌。

2. 下列谓词公式中（ C ）不是命题。

A ．(∀x)P(x)； B ．(∃x)P(x)； C ．(∀x)(P(x)∨P(y))； D ．(∃x)(∃y)(P(x)→R(y)) 3. 个体域为整数集合，下列公式中（ C ）不是命题。

A ．(∀x)(∀y)(x *y=y)； B ．(∀x)(∃y)(x *y=1)； C ．(∀x)(x *y=x)； D ．(∃x)(∃y)(x *y=2) 4. 下列谓词公式中（ A ）不正确。

离散数学考试题及答案一、选择题（每题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. 集合论题目(1) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∪B的结果。

答案：A∪B={1,2,3,4,5,6,7}(2) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A∩B的结果。

答案：A∩B={3,4,5}(3) 设A={1,2,3,4,5}，B={3,4,5,6,7}，求A-B的结果。

答案：A-B={1,2}2. 图论题目(1) 给定一个无向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(A,C),(B,D),(C,D),(D,E)}，求该图的邻接矩阵。

答案：邻接矩阵为：A B C D EA 0 1 1 0 0B 1 0 0 1 0C 1 0 0 1 0D 0 1 1 0 1E 0 0 0 1 0(2) 给定一个有向图G，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(B,C),(C,D),(D,E),(E,A)}，求该图的邻接表。

答案：邻接表为：A ->B ->C ->D ->E -> AB -> CC -> DD -> EE -> A3. 命题逻辑题目(1) 判断以下命题是否为永真式：(p∨q)∧(¬p∨r)∧(¬q∨¬r)。

答案：是永真式。

(2) 给定命题p：如果天晴，那么我去游泳；命题q：我没有去游泳。

请判断以下命题的真假：(¬p∨q)∧(p∨¬q)。

答案：是真命题。

4. 关系代数题目(1) 给定关系R(A,B,C)和S(B,C,D)，求R⋈S的结果。

离散数学考试试题及答案一、单项选择题（每题5分，共20分）1. 在离散数学中，以下哪个概念不是布尔代数的基本元素？A. 逻辑与B. 逻辑或C. 逻辑非D. 逻辑异或答案：D2. 下列哪个命题不是命题逻辑中的命题？A. 所有学生都是勤奋的B. 有些学生是勤奋的C. 学生是勤奋的D. 勤奋的学生答案：D3. 在集合论中，以下哪个符号表示集合的并集？A. ∩B. ∪C. ⊆D. ⊂答案：B4. 以下哪个图不是无向图？A. 简单图B. 完全图C. 有向图D. 多重图答案：C二、填空题（每题5分，共20分）1. 如果一个命题的逆否命题为真，则原命题的________为真。

答案：逆命题2. 在图论中，如果一个图的任意两个顶点都由一条边连接，则称这个图为________图。

答案：完全3. 一个集合的幂集是指包含该集合的所有________的集合。

答案：子集4. 如果一个函数的定义域和值域都是有限集合，那么这个函数被称为________函数。

答案：有限三、简答题（每题10分，共30分）1. 请简述什么是图的欧拉路径。

答案：欧拉路径是一条通过图中每条边恰好一次的路径。

2. 解释什么是二元关系，并给出一个例子。

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

例如，小于关系就是一个二元关系。

3. 请说明什么是递归函数，并给出一个简单的例子。

答案：递归函数是一种通过自身定义来计算函数值的函数。

例如，阶乘函数就是一个递归函数，定义为：n! = n * (n-1)!，其中n! = 1当n=0时。

四、计算题（每题10分，共30分）1. 计算以下逻辑表达式：(P ∧ Q) ∨ ¬R答案：首先计算P ∧ Q，然后计算¬R，最后计算两者的逻辑或。

2. 给定集合A = {1, 2, 3}，B = {2, 3, 4}，求A ∪ B。

答案：A ∪ B = {1, 2, 3, 4}3. 已知函数f(x) = 2x + 3，求f(5)。

黄冈师范学院2007—2008学年度第二学期期中试卷考试课程：离散数学 考试形式：闭卷出卷教师：崔艳莉 考试专业：计科、软工、网工 考试班级：计科200701-03班、软工200701班一、单项选择题（每小题2分，共20分。

）1.设A={1,2,3}，A 上二元关系R 的关系图如右：R 具有的性质是A.自反性B.对称性C.传递性D.反自反性2.设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( )A.R ∪I AB.RC.R ∪{〈c,a 〉}D.R ∩I A3.下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅4.设解释R 如下：论域D 为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R 下为真的是( )A.( ∀ x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z))B.( ∀x)A(f(a,x),a)C.(∀x)(∀y)（A(f(x,y),x))D.(∀x)(∀y)(A(x,y)→A(f(x,a),a))5. 下列等价式正确的是（ ）A ．┐)()(x A x ∃⇔∃┐AB ．A y x A y x ))(())((∀∃⇔∀∀C ．┐)()(x A x ∃⇔∀┐AD ．)()()()())()()((x B x x A x x B x A x ∀∨∀⇔∧∀6.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元7.若P ：他聪明；Q ：他用功；则“他虽聪明，但不用功”，可符号化为( )A.P ∨QB.P ∧┐QC.P →┐QD.P ∨┐Q8.以下命题公式中，为永假式的是( )A.p →(p ∨q ∨r)B.(p →┐p)→┐pC.┐(q →q)∧pD.┐(q ∨┐p)→(p ∧┐p)9.下列语句中不是．．命题的只有（ ） A ．这个语句是假的。

安徽大学2006—2007学年第 二 学期 《 离散数学 》考试试卷（B 卷）（时间120分钟）院/系 专业 姓名 学号题 号 一 二 三 四 五 六 七 总分得分一、选择题（每小题2分，共20分）1．在自然数集合N 上，下列运算中可结合的是（ ） A. b a b a -=*； B. ),max(*b a b a =； C. b a b a 2*+=； D. b a b a -=*。

2．R 为实数集，运算*定义为：R b a ∈,，||*b a b a ⋅=，则代数系统<R,*>是（ ） A. 半群； B. 独异点； C. 群； D. 阿贝尔群。

3．下列代数系统中，哪个是独异点（ ）A. <R,ο>，其中22b a b a +=ο；B. <R,ο>，其中333b a b a +=ο；C. <I,max>，其中max 为求两数中较大数；D. <I +,GCD>，其中GCD 为最大公约数。

（R ：实数集，I ：整数集，I +：正整数集）4．下列集合对于指定运算，构成群的为（ ）A. 非负整数集关于数的加法运算；B. 整数集关于数的减法运算；C. 正实数关于数的除法运算；D. 一元实系数多项式集合关于多项式加法。

5．下面哪个集合关于指定运算构成整环（ ） A. },|2{3Z b a b a ∈+，关于数的加法和乘法； B. {n 阶实数矩阵}，关于矩阵的加法和乘法； C. },|2{Z b a b a ∈+，关于数的加法和乘法；D. },|{Z b a a b b a ∈⎪⎪⎭⎫ ⎝⎛，关于矩阵的加法和乘法。

6．下面给出了一些偏序集的哈斯图，其中哪个不是格（ ）A.；B.；C.；D.。

7. 下面哈斯图（图1-7）表示的格中哪个元素无补元（ ）？ A. a ； B. c ； C. e ； D. f 。

得分图1-78．给定平面图G如图1-8所示，则G中面的个数及面的总次数分别为（）A. 4，20 ；B. 4，22 ；C. 5，22 ；D. 5，24 。

离散数学考试试题及答案一、选择题（每题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. 简述命题逻辑中的等价命题是什么？答案：等价命题是指两个命题在所有可能的真值赋值下都具有相同真值的命题。

离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（P⇄Q）(P⇄R S)b)我今天进城，除非下雨。

设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。

设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P2.用谓词逻辑把下列命题符号化a)有些实数不是有理数设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：x(R(x) Q(x)) 或x(R(x) →Q(x))b)对于所有非零实数x，总存在y使得xy=1。

设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为：x(R(x) E(x,0) →y(R(y) E(f(x,y),1))))c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)⇄∀a(A(a)→∃b(B(b) ∧ E(f(a),b) ∧∀c(S(c) ∧ E(f(a),c) →E(a,b))))二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）(P→(Q→R))(R→(Q→P))（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) ∧(P Q R) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)a) T b) F3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。

《离散数学一》期中考试题学院：软件学院级：07级专业：通软/计应一．填空（共20分）：1. 设集合A={a,b,c,d,e,f,g}，A上的一个划分π={{a,b},{c,d,e},{f,g}}，则π所对应的等价关系有_____个二元组。

（2分）Let A be {a,b,c,d,e,f,g} and a partition πof A be {{a,b},{c,d,e},{f,g}}.There are____ ordered pairs in the equivalent relation corresponding to π.答：172.某一计算机系统的标号标识符是由一个英文字母后跟3个数字组成，如果允许重复，那么不同的标号标识符可能有多少种？________ （2分）A label identifier, for a computer system, consists of one letter followed by three digits. If repetitions are allowed, how many distinct label identifiers are possible?________答：26×10×10×10即26 000种。

3.从20个女士和30个男士中选出3个女士和4个男士构成7人委员会，那么能形成多少种不同的7人委员会？________ （2分）How many different seven-person committees can be formed each containing three women from an available set of 20 women and four men from an available set of 30 men?_______答：20C3×30C4或者1140×27405或者31 241 700.4.从10个志愿者中产生三人委员会。