西安交通大学离散数学期末考试高分题库全集含答案

离散数学期末考试试题(配答案)1. 谓词公式)()(x xQ x xP ∃→∀的前束范式是___________。

2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =____；=A _____；=B A Y __ _____3. 设{}{}b a B c b a A ,,,,==；则=-)()(B A ρρ__ __________；=-)()(A B ρρ_____ ______。

二．选择题（每小题2分；共10分）1. 与命题公式)(R Q P →→等价的公式是（ ）（A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=；A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 三．计算题（共43分）1. 求命题公式r q p ∨∧的主合取范式与主析取范式。

（6分）2. 设集合{}d c b a A ,,,=上的二元关系R 的关系矩阵为⎪⎪⎪⎪⎪⎭⎫⎝⎛=1000000011010001R M ；求)(),(),(R t R s R r 的关系矩阵；并画出R ；)(),(),(R t R s R r 的关系图。

（10分）5. 试判断),(≤z 是否为格？说明理由。

（5分）（注：什么是格？Z 是整数；格：任两个元素；有最小上界和最大下界的偏序）四．证明题（共37分）1. 用推理规则证明D D A C C B B A ⌝⇒∧⌝⌝⌝∧∨⌝→)(,)(,。

（10分）2. 设R 是实数集；b a b a f R R R f +=→⨯),(,:；ab b a g R R R g =→⨯),(,:。

求证：g f 和都是满射；但不是单射。

（10分）一；1； _ ∃x ∃y¬P(x)∨Q(y)2； {2} {4；5} {1；3；4；5}3； {{c}；{a ；c}；{b ；c}；{a ；b ；c}} Φ_ 二；B D三；解：主合取方式：p ∧q ∨r ⇔(p ∨q ∨r)∧(p ∨¬q ∨r)∧(¬p ∨q ∨r)= ∏0.2.4主析取范式：p ∧q ∨r ⇔(p ∧q ∧r) ∨(p ∧q ∧¬r) ∨(¬p ∧q ∧r) ∨(¬p ∧¬q ∧r) ∨(p ∧¬q ∧r)= ∑1.3.5.6.7 四；1；证明：编号 公式 依据 （1） （¬B∨C ）∧¬C 前提 （2） ¬B∨C ；¬C （1） （3） ¬B （2） （4） A →B （3） （5） ¬A （3）（4） （6） ¬（¬A∧D ） 前提 （7） A ∨¬D （6） （8）¬D （5）（6）2；证明：要证f 是满射；即∀y ∈R ；都存在（x1；x2）∈R ×R ；使f （x1；x2）=y ；而f （x1；x2）=x1+x2；可取x1=0；x2=y ；即证得；再证g 是满射；即∀y ∈R ；；都存在（x1；x2）∈R ×R ；使g （x1；x2）=y ；而g （x1；x2）=x1x2；可取x1=1；x2=y ；即证得；最后证f 不是单射；f （x1；x2）=f （x2；x1）取x1≠x2；即证得；同理：g （x1；x2）=g （x2；x1）；取x1≠x2；即证得。

离散数学考试题及答案一、选择题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。

《离散数学》题库及答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答：（1），（4）2、下列公式中哪些是永真式？()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答：（2），（3），（4）3、设有下列公式，请问哪几个是永真蕴涵式()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答：（2），（3），（4），（5），（6）4、公式某((A(某)B(y，某))zC(y，z))D(某)中，自由变元是(变元是()。

答：某,y,某,z5、判断下列语句是不是命题。

若是，给出命题的真值。

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

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

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

(5)前进！(6)给我一杯水吧！答：（1）是，T（2）是，F（3）不是（4）是，T（5）不是（6）不是6、命题“存在一些人是大学生”的否定是()，而命题“所有的人都是要死的”的否定是()。

答：所有人都不是大学生，有些人不会死7、设P：我生病，Q：我去学校，则下列命题可符号化为()。

(1)只有在生病时，我才不去学校(2)若我生病，则我不去学校(3)当且仅当我生病时，我才不去学校(4)若我不生病，则我一定去学校答：（1）QP（2）PQ（3）PQ（4）PQ8、设个体域为整数集，则下列公式的意义是()。

(1)某y(某+y=0)(2)y某(某+y=0)答：（1）对任一整数某存在整数y满足某+y=0（2）存在整数y对任一整数某满足某+y=09、设全体域D是正整数集合，确定下列命题的真值：(1)某y(某y=y)()(2)某y(某+y=y)()(3)某y(某+y=某)()(4)某y(y=2某)()答：（1）F（2）F（3）F（4）T10、设谓词P(某)：某是奇数，Q(某)：某是偶数，谓词公式某(P(某)Q(某))在哪个个体域中为真()2(1)自然数(2)实数(3)复数(4)(1)--(3)均成立答：（1）11、命题“2是偶数或-3是负数”的否定是（）。

离散考试试题及答案一、选择题（每题5分，共20分）1. 在离散数学中，下列哪个概念不是布尔代数的基本运算？A. 与B. 或C. 非D. 模答案：D2. 集合论中，下列哪个符号表示“属于”关系？A. ∈B. ∉C. ⊆D. ⊂答案：A3. 命题逻辑中，下列哪个符号表示“蕴含”关系？A. ∧B. ∨C. →D. ↔答案：C4. 关系R在集合A上是自反的，意味着什么？A. 对于所有a∈A，(a, a)∈RB. 对于所有a∈A，(a, a)∉RC. 对于所有a∈A，(a, b)∈RD. 对于所有a∈A，(a, b)∉R答案：A二、填空题（每题5分，共20分）1. 一个集合的基数是集合中元素的________。

答案：数量2. 在有向图中，如果存在一条从顶点u到顶点v的路径，则称顶点v 是顶点u的________。

答案：可达的3. 一个图是连通的，当且仅当图中任意两个顶点都是________。

答案：连通的4. 在命题逻辑中，一个命题的否定是________。

答案：它的对立命题三、简答题（每题10分，共30分）1. 请解释什么是图的哈密顿回路。

答案：哈密顿回路是一个图中的闭合回路，它恰好访问图中的每个顶点一次。

2. 描述一下什么是二元关系，并给出一个例子。

答案：二元关系是定义在两个集合上的一个关系，它关联了第一个集合中的元素和第二个集合中的元素。

例如，小于关系是数字集合上的一个二元关系。

3. 什么是图的生成树？答案：图的生成树是图的一个子图，它包含图中的所有顶点，并且是一棵树，即它是连通的且没有环。

四、计算题（每题15分，共30分）1. 给定一个集合A={1,2,3,4,5}，计算它的幂集。

答案：幂集P(A)={∅, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5},{1,2,3}, {1,2,4}, {1,2,5}, {1,3,4}, {1,3,5}, {1,4,5}, {2,3,4}, {2,3,5}, {2,4,5}, {3,4,5}, {1,2,3,4}, {1,2,3,5}, {1,2,4,5}, {1,3,4,5}, {2,3,4,5}, {1,2,3,4,5}, 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}，请计算它的幂集，并列出所有元素。

离散数学试题总汇及答案一、单项选择题（每题2分，共20分）1. 在集合{1,2,3}和{3,4,5}的笛卡尔积中，元素(2,4)是否存在？A. 存在B. 不存在C. 无法确定D. 以上都不对2. 函数f: A→B是单射的，当且仅当对于任意的a1, a2∈A，若f(a1)=f(a2)，则a1=a2。

A. 正确B. 错误C. 无法确定D. 以上都不对3. 以下哪个命题是真命题？A. 所有的狗都会游泳。

B. 有些狗不会游泳。

C. 所有的狗都不会游泳。

D. 以上都不是真命题。

4. 如果p蕴含q为假，那么p和q的真值可以是？A. p为真，q为假B. p为假，q为真C. p为真，q为真D. p为假，q为假5. 以下哪个图是连通图？A. 一个孤立点B. 两个不相连的点C. 一个包含三个点且每对点都相连的图D. 以上都不是连通图6. 在有向图中，如果存在从顶点u到顶点v的路径，那么称v是u的后继顶点。

A. 正确B. 错误C. 无法确定D. 以上都不对7. 以下哪个等价关系是集合{1,2,3}上的？A. {(1,1), (2,2), (3,3)}B. {(1,2), (2,1), (2,2), (3,3)}C. {(1,1), (2,3), (3,2), (3,3)}D. {(1,1), (2,2), (3,3), (1,3)}8. 以下哪个命题是假命题？A. 所有的鸟都有羽毛。

B. 有些鸟不会飞。

C. 所有的哺乳动物都是温血动物。

D. 以上都不是假命题。

9. 在图论中，一个图的生成树是包含图中所有顶点的最小连通子图。

A. 正确B. 错误C. 无法确定D. 以上都不对10. 如果命题p和q互为逆否命题，那么它们具有相同的真值。

A. 正确B. 错误C. 无法确定D. 以上都不对二、填空题（每题2分，共20分）1. 集合{1,2,3}和{3,4,5}的并集是________。

2. 函数f: A→B是满射的，当且仅当对于任意的b∈B，存在a∈A，使得f(a)=________。

交大_离散_期末考卷lisan200704a一、选择题（每题1分，共5分）A. 整数分解B. 背包问题C. 确定图是否是连通的D. 确定图是否有哈密顿回路2. 在离散数学中，下列哪个关系是自反的？A. 小于关系B. 整除关系C. 约等于关系D. 矩阵乘法关系A. R1={(1,1), (2,2), (3,3), (1,2)}B. R2={(1,1), (2,2), (3,3), (2,1)}C. R3={(1,1), (2,2), (3,3), (3,1)}D. R4={(1,1), (2,2), (3,3), (1,3)}A. 一个有6个顶点的完全图B. 一个有5个顶点的环图C. 一个有4个顶点的完全二部图D. 一个有3个顶点的路径图5. 在图论中，一个有n个顶点的树有多少条边？A. nB. n1C. n+1D. 2n二、判断题（每题1分，共5分）1. 离散数学中的图论部分主要研究网络的性质和结构。

（）2. 所有的图都至少有一个哈密顿回路。

（）3. 在一个有向图中，每个顶点的入度等于出度。

（）4. 离散数学中的逻辑部分不涉及命题逻辑和谓词逻辑。

（）5. 欧拉定理可以用来判断一个图是否存在欧拉回路。

（）三、填空题（每题1分，共5分）1. 一个有n个顶点的连通图至少有______条边。

2. 在一个无向图中，如果任意两个顶点都相邻，则称该图为______。

3. 命题“如果今天下雨，那么我不去公园”的逆否命题是“如果我去公园，那么今天______”。

4. 一个集合的幂集是指该集合所有______的集合。

5. 在图论中，两个顶点之间的路径长度是指连接这两个顶点的路径上边的______。

四、简答题（每题2分，共10分）1. 简述什么是离散数学。

2. 解释什么是哈密顿回路。

3. 简述集合的笛卡尔积。

4. 什么是命题逻辑中的蕴含关系？5. 解释什么是图的同构。

五、应用题（每题2分，共10分）1. 给定集合A={1,2,3,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。

离散数学试题(B卷答案1）一、证明题（10分）1)(⌝P∧(⌝Q∧R))∨(Q∧R)∨(P∧R)⇔R证明: 左端⇔(⌝P∧⌝Q∧R)∨((Q∨P)∧R)⇔((⌝P∧⌝Q)∧R))∨((Q∨P)∧R)⇔(⌝(P∨Q)∧R)∨((Q∨P)∧R)⇔(⌝(P∨Q)∨(Q∨P))∧R⇔(⌝(P∨Q)∨(P∨Q))∧R⇔T∧R(置换)⇔R2) ∃x (A(x)→B(x))⇔∀xA(x)→∃xB(x)证明：∃x(A(x)→B(x))⇔∃x(⌝A(x)∨B(x))⇔∃x⌝A(x)∨∃xB(x)⇔⌝∀xA(x)∨∃xB(x)⇔∀xA(x)→∃xB(x)二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。

证明：(P∨(Q∧R))→(P∧Q∧R)⇔⌝(P∨(Q∧R))∨(P∧Q∧R))⇔（⌝P∧(⌝Q∨⌝R)）∨(P∧Q∧R)⇔(⌝P∧⌝Q)∨(⌝P∧⌝R))∨(P∧Q∧R)⇔(⌝P∧⌝Q∧R)∨(⌝P∧⌝Q∧⌝R)∨(⌝P∧Q∧⌝R))∨(⌝P∧⌝Q∧⌝R))∨(P∧Q∧R)⇔m0∨m1∨m2∨m7⇔M3∨M4∨M5∨M6三、推理证明题（10分）1）C∨D， (C∨D)→⌝E，⌝E→(A∧⌝B)， (A∧⌝B)→(R∨S)⇒R∨S 证明：(1) (C∨D)→⌝E P(2) ⌝E→(A∧⌝B) P(3) (C∨D)→(A∧⌝B) T(1)(2)，I(4) (A∧⌝B)→(R∨S) P(5) (C∨D)→(R∨S) T(3)(4)， I(6) C∨D P(7) R∨S T(5)，I2) ∀x(P(x)→Q(y)∧R(x))，∃xP(x)⇒Q(y)∧∃x(P(x)∧R(x))证明(1)∃xP(x) P(2)P(a) T(1)，ES(3)∀x(P(x)→Q(y)∧R(x)) P(4)P(a)→Q(y)∧R(a) T(3)，US(5)Q(y)∧R(a) T(2)(4)，I(6)Q(y) T(5)，I(7)R(a) T(5)，I(8)P(a)∧R(a) T(2)(7)，I(9)∃x(P(x)∧R(x)) T(8)，EG(10)Q(y)∧∃x(P(x)∧R(x)) T(6)(9)，I四、某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。

离散数学考试试题及答案一、单项选择题（每题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)。

《离散数学》期末考试试题一、单项选择题（每题3分，共30分）1. 在集合论中，以下哪个符号表示“属于”？A. ∈B. ∉C. ⊆D. ∩2. 函数f: A → B是单射的，当且仅当：A. 对于所有a1, a2 ∈ A，如果f(a1) = f(a2)，则a1 = a2B. 对于所有a1, a2 ∈ A，如果a1 ≠ a2，则f(a1) ≠ f(a2)C. 对于所有b ∈ B，存在唯一的a ∈ A，使得f(a) = bD. 以上都是3. 命题逻辑中，以下哪个是合取的表示？A. ∧B. ∨C. →D. ¬4. 在图论中，一个连通图是指：A. 每个顶点至少有一条边B. 任意两个顶点之间都有路径相连C. 图中没有环D. 图中至少有一个环5. 以下哪个是图的遍历算法？A. DFS（深度优先搜索）B. BFS（广度优先搜索）C. Dijkstra算法D. 以上都是6. 以下哪个是布尔代数的基本定理？A. 德摩根定律B. 布尔代数的分配律C. 布尔代数的结合律D. 以上都是7. 以下哪个是关系数据库模型中的基本操作？A. 选择B. 投影C. 连接D. 以上都是8. 以下哪个是有限状态自动机（FSA）的组成部分？A. 状态集合B. 输入符号集合C. 转移函数D. 以上都是9. 在命题逻辑中，以下哪个是析取的表示？A. ∧B. ∨C. →D. ¬10. 以下哪个是图论中的树？A. 无环连通图B. 有环连通图C. 无环不连通图D. 有环不连通图二、简答题（每题10分，共40分）1. 请解释什么是二元关系，并给出一个例子。

2. 请描述什么是正规文法，并给出一个例子。

3. 请解释什么是图的强连通分量，并给出一个例子。

4. 请解释什么是闭包，并给出一个例子。

三、计算题（每题15分，共20分）1. 给定一个有向图G，顶点集合V={A, B, C, D}，边集合E={(A, B), (B, C), (C, D), (D, A), (A, C)}，请找出所有顶点的入度和出度。

离散数学考试题(后附详细答案)一、命题符号化（共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。