离散数学 练习题及答案

离散数学试题第一部分选择题一、单项选择题1．下列是两个命题变元p，q的小项是（ C ）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列语句中是命题的只有（ A ）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（ C ）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．(∀x)(∀y)(A(x)→B(y))⇔(∃x)A(x)→(∀y)B(y)5．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x的辖域是（ C ）A．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B．Q(x,z)→(∀y)R(x,y,z)C．Q(x,z)→(∃x)(∀y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（ D ）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（ A ）A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（ A ）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)02324# 离散数学试题第1 页共4页02324# 离散数学试题 第 2 页 共4页D ．a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( A ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系第二部分 非选择题二、填空题1．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。

离散数学试题及答案一、选择题1. 设A、B、C为三个集合，下列哪个式子是成立的？A) \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)B) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)C) \(A \cup (B \cup C) = (A \cup B) \cup (A \cup C)\)答案：B2. 对于一个有n个元素的集合S，S的幂集中包含多少个元素？A) \(n\)B) \(2^n\)C) \(2 \times n\)答案：B二、判断题1. 对于两个关系R和S，若S是自反的，则R ∩ S也是自反的。

答案：错误2. 若一个关系R是反对称的，则R一定是反自反的。

答案：正确三、填空题1. 有一个集合A，其中包含元素1、2、3、4和5，求集合A的幂集的大小。

答案：322. 设a和b是实数，若a \(\neq\) b，则a和b之间的关系是\(\__\_\)关系。

答案：不等四、解答题1. 证明：如果关系R是自反且传递的，则R一定是反自反的。

解答：假设关系R是自反的且传递的，即对于集合A中的任意元素x，都有(x, x) ∈ R，并且当(x, y) ∈ R和(y, z) ∈ R时，(x, z) ∈ R。

反证法：假设R不是反自反的，即存在一个元素a∈A，使得(a, a) ∉ R。

由于R是自反的，所以(a, a) ∈ R，与假设矛盾。

因此，R一定是反自反的。

答案完整证明了该结论。

2. 已知集合A={1, 2, 3}，集合B={2, 3, 4}，求集合A和B的笛卡尔积。

解答：集合A和B的笛卡尔积定义为{(a, b) | a∈A，b∈B}。

所以，集合A和B的笛卡尔积为{(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}。

数理逻辑习题判断题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．飞碟来自地球外的星球。

离散数学练习题(含答案)题目1. 对于集合 $A={1,2,3,...,10}$ 和 $B={n|n是偶数，2<n<8}$，求 $A \cap B$ 的元素。

2. 存在三个可识别的状态A,B,C。

置换群 $S_3$ 作用在状态集上。

定义四个动作：$α: A → C, β: A → B, γ: C→ A, δ: B→ C$。

确定式子，描述 $\{α,β,γ,δ\}$ 的乘法表。

3. 证明 $\forall n \in \mathbb{N}$，合数的个数不小于$n$。

4. 给定一个无向带权图，图中每个节点编号分别是$1,2,...,n$，证明下列结论：a. 如果从节点$i$到$j$只有一条权值最小的路径，则这条路径的任意子路径都是最短路径。

b. 如果从节点$i$到$j$有两条或两条以上权值相等的路径，则从$i$到$j$的最短路径可能不唯一。

答案1. $A \cap B = \{2,4,6\}$。

2. 乘法表：3. 对于任意$n$，我们可以选择$n+1$个连续的自然数$k+1,k+2,...,k+n,k+n+1$中的$n$个数，其中$k \in \mathbb{Z}$。

这$n$个数构成的$n$个正整数均为合数，因为它们都至少有一个小于它自身的因子，所以不是质数。

所以合数的个数不小于任意$n$。

4.a. 根据题意，从$i$到$j$只有一条权值最小的路径，即这条最短路径已被确定。

如果从这条路径中任意取出一段子路径，假设这段子路径不是这个节点到$j$的最短路径，那么存在其他从$i$到$j$的路径比这段子路径更优，又因为这条路径是最短路径，所以这段子路径也一定不优于最短路径，矛盾。

所以从这条路径中任意取出的子路径都是最短路径。

b. 如果从节点$i$到$j$有多条权值相等的路径，则这些路径权值都是最短路径的权值。

因为所有最短路径的权值相等，所以这些路径的权值就是最短路径的权值。

所以从$i$到$j$的最短路径可能不唯一。

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

离散数学试题与答案试卷一一、填空20% （每小题2分）1．设}7|{)},5()(|{<∈=<∈=+xExxBxNxxA且且（+=⋃BA{0，1，2，3，4，6} 。

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为。

3R，S的真值为1，则)()))(((SRPRQP⌝∨→⌝∧→∨⌝的真值= 1 。

4．公式PRSRP⌝∨∧∨∧)()(的主合取范式为)()(RSPRSP∨⌝∨⌝∧∨∨⌝。

5．若解释I的论域D仅包含一个元素，则)()(xxPxxP∀→∃在I下真值为1 。

6．设A={1，2，3，4}，A上关系图为则R2 = {<a.b>,<a,c>,<a,d>,<b,d>,<c,d> 。

7．设A={a，b，c，d}，其上偏序关系R的哈斯图为则R= {<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} I A。

8．图的补图为9．设A={a，b，c，d} ，A上二元运算如下：那么代数系统<A，*>的幺元是 a ，有逆元的元素为a , b , c ,d，它们的逆元分别为 a , d , c , d 。

10．下图所示的偏序集中，是格的为 c 。

二、选择20% （每小题2分）1、下列是真命题的有（CD）A．}}{{}{aa⊆；B．}}{,{}}{{ΦΦ∈Φ；C．}},{{ΦΦ∈Φ；D．}}{{}{Φ∈Φ。

2、下列集合中相等的有（BC ）A．{4，3}Φ⋃；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。

3、设A={1，2，3}，则A上的二元关系有（ C ）个。

A．23 ；B．32 ；C．332⨯；D．223⨯。

4、设R，S是集合A上的关系，则下列说法正确的是（A ）A．若R，S 是自反的，则SR 是自反的；B．若R，S 是反自反的，则SR 是反自反的；C ．若R ，S 是对称的， 则S R是对称的；D ．若R ，S 是传递的， 则S 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}，请计算它的幂集，并列出所有元素。

一、填空题1、集合的表示方法有两种： 法和 法。

请把“奇整数集合”表示出来{ }。

1、列举；描述；}12|{Z k k x x ∈+=，2、无向连通图G 含有欧拉回路的充分必要条件是不含有奇数度结点.2*、连通有向图D 含有欧拉回路的充分必要条件是D 中每个结点的入度＝出度. 3、设R 是集合A 上的等价关系，则R 所具有的关系的三个特性是 、自反性、对称性、传递性.4、有限图G 是树的一个等价定义是：连通无回路（或任一等价定义）.5、设N (x )：x 是自然数，Z (y )；y 是整数，则命题“自然数都是整数，而有的整数不是自然数”符号化为∀x (N (x )→Z (x ))∧∃x (Z (x )∧⌝N (x ))6、在有向图的邻接矩阵中，第i 行元素之和,第j 列元素之和分别为 、结点v i 的出度和结点v j 的入度． 7、设A ，B 为任意命题公式，C 为重言式，若C B C A ∧⇔∧，那么命题B A ↔是重言式的真值是 1 ．8、命题公式)(Q P →⌝的主析取范式为P ∧⌝Q ．9、 设图G ＝<V ，E >和G '＝<V ',E '>,若 ，则G '是G 的真子图，若V '=V ,E '⊆E ，则G '是G 的生成子图. E E V V E E V V ⊆'='⊂'⊂',;或 10、在平面图>=<E V G ,中,则∑=ri ir 1)deg(＝2∣E ∣,其中r i(i =1,2,…,r )是G 的面．11、设}2,1{},,{==B b a A ，则从A 到B 的所有映射是11、σ1={（a ，1），（b ，1）}；σ2={（a ，2），（b ，2）}；σ3={（a ，1），（b ，2）}；σ4={（a ，2），（b ，1）}12、表达式∀x ∃yL （x ，y ）中谓词的定义域是{a ，b ，c }，将其中的量词消除，写成与之等价的命题公式为 12、（L （a ，a ）∨L （a ，b ）∨L （a ，c ））∧（L （b ，a ）∨L （b ，b ）∨L （b ，c ））∧（L （c ，a ）∨L （c ，b ）∨L （c ，c ）） 12*、设个体域D ＝{a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为 (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b )))13、含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 14、设R ，S 都是集合A 上的等价关系，则对称闭包s (R ⋂S )= R ⋂S15、设G 是连通平面图，v ,e ,r 分别表示G 的结点数，边数和面数，则v ,e 和r 满足的关系式是2=-+e r v16、设G 是n 个结点的简单图，若G 中每对结点的度数之和≥n ，则G 一定是哈密顿图. 17、一个有向树T 称为根树，若 ，其中 ，称为树根，称为树叶. 若有向图T 恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点.18、图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路. 通路长度；初级；简单. 19、设A 和B 为有限集，|A|=m ，|B|=n ，则有 个从A 到B 的关系，有 个从A 到B 的函数，其中当m ≤n 时有 个入射，当m=n 时，有 个双射。

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

离散数学试题及答案解析一、选择题1. 在集合{1,2,3,4}中，含有3个元素的子集有多少个？A. 4B. 8C. 16D. 32答案：B解析：含有3个元素的子集可以通过组合数公式C(n, k) = n! / [k!(n-k)!]来计算，其中n为集合的元素个数，k为子集中的元素个数。

在本题中，n=4，k=3，所以C(4, 3) = 4! / [3!(4-3)!] = 4。

2. 下列哪个命题是真命题？A. 所有偶数都是整数。

B. 所有整数都是偶数。

C. 所有整数都是奇数。

D. 所有奇数都是整数。

答案：A解析：偶数是指能被2整除的整数，因此所有偶数都是整数，选项A是真命题。

选项B、C和D都是错误的，因为并非所有整数都是偶数或奇数。

二、填空题1. 逻辑运算符“非”（NOT）的真值表是：当输入为真时，输出为______；当输入为假时，输出为真。

答案：假解析：逻辑运算符“非”（NOT）是一元运算符，它将输入的真值取反。

如果输入为真，则输出为假；如果输入为假，则输出为真。

2. 命题逻辑中，合取词“与”（AND）的真值表是：当两个命题都为真时，输出为真；否则输出为______。

答案：假解析：合取词“与”（AND）是二元运算符，只有当两个命题都为真时，输出才为真；如果其中一个或两个命题为假，则输出为假。

三、简答题1. 解释什么是等价关系，并给出一个例子。

答案：等价关系是定义在集合上的一个二元关系，它满足自反性、对称性和传递性。

例如，考虑整数集合上的“同余”关系。

对于任意整数a，b，如果a和b除以同一个正整数n后余数相同，则称a和b模n同余。

这个关系是自反的（a同余a），对称的（如果a同余b，则b同余a），并且是传递的（如果a同余b且b同余c，则a同余c）。

2. 什么是图的连通性？一个图是连通的需要满足什么条件？答案：图的连通性是指在无向图中，任意两个顶点之间都存在一条路径。

一个图是连通的需要满足以下条件：图中的任意两个顶点v和w，都可以通过图中的边相互到达。

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

离散数学习题答案习题一及答案：（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 →⌝→⌝解：列出公式的真值表，如下所示：由真值表可以看出公式有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。

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

离散数学试题及答案一、选择题（每题2分，共20分）1. 集合A={x|x<5}，集合B={x|x>2}，则A∩B为：A. {x|x>2}B. {x|x<2}C. {x|2<x<5}D. {x|x≥5}2. 命题p："x>0"是命题q："x^2>0"的：A. 必要条件B. 充分条件C. 充分必要条件D. 无关条件3. 函数f(x)=x^2+3x-2的值域是：A. (-∞, -1]B. [1, +∞)C. (-∞, 4]D. (-∞, 2]4. 逻辑表达式((P∨Q)∧(¬P))的真值表中，当P为真时，表达式的值为：A. 真B. 假C. 不确定D. 无法判断5. 已知二元关系R定义在集合A上，若对于任意a,b,c∈A，若aRb且bRc，则aRc，那么R是：A. 自反的B. 对称的C. 传递的D. 完全的6. 有限状态自动机（DFA）与确定有限状态自动机（DFA）的区别在于：A. DFA可以识别非正则语言B. DFA可以有多个起始状态C. DFA可以有多个接受状态D. DFA可以有多个状态7. 命题逻辑中，若命题P的否定为P'，则P和P'的关系是：A. 互为对立B. 互为矛盾C. 互为等价D. 互为同一律8. 集合{1,2,3}的子集个数是：A. 3B. 4C. 7D. 89. 一个命题逻辑公式的真值表中，若存在一行结果为假，则该公式：A. 总是假B. 有时真，有时假C. 总是真D. 无法判断10. 布尔代数中，逻辑与（AND）操作的特点是：A. 有0则0B. 有1则1C. 非0即1D. 非1即0二、简答题（每题5分，共10分）1. 简述集合论中的幂集概念。

2. 描述图的邻接矩阵表示方法。

三、计算题（每题10分，共30分）1. 证明函数f(x)=x^3-3x^2+2x-1在R上是单调递增的。

离散数学试题及答案解析一、单项选择题（每题2分，共10分）1. 集合A={1,2,3}，集合B={2,3,4}，则A∩B等于：A. {1,2,3}B. {2,3}C. {1,4}D. {3,4}答案：B2. 以下哪个命题是真命题？A. 所有天鹅都是白色的。

B. 有些天鹅不是白色的。

C. 所有天鹅都不是白色的。

D. 没有天鹅是白色的。

答案：B3. 函数f: A→B的定义域是A，值域是B，那么f是：A. 单射B. 满射C. 双射D. 既不是单射也不是满射答案：D4. 逻辑表达式(p∧q)→r的逆否命题是：A. ¬r→¬(p∧q)B. ¬r→¬p∨¬qC. r→(p∧q)D. ¬r∧¬p∨¬q答案：B5. 有限集合A={a, b, c}的子集个数为：A. 3B. 4C. 7D. 8答案：D二、填空题（每题3分，共15分）1. 如果一个关系R在集合A上是自反的，那么对于A中的每一个元素a，都有___________。

答案：(a, a)∈R2. 命题逻辑中，合取（AND）的逻辑运算符用___________表示。

答案：∧3. 在图论中，一个连通图是指图中任意两个顶点之间都存在___________。

答案：路径4. 集合{1, 2, 3}的幂集包含___________个元素。

答案：85. 如果一个函数f是单射，那么对于任意的x1, x2∈A，如果f(x1)=f(x2)，则x1___________x2。

答案：=三、解答题（每题10分，共20分）1. 证明：若p是q的充分条件，q是r的充分条件，则p是r的充分条件。

证明：假设p成立，由于p是q的充分条件，所以q成立。

又因为q是r的充分条件，所以r成立。

因此，p成立可以推出r成立，即p是r的充分条件。

2. 给定一个有向图，其中包含顶点A、B、C、D，边为(A, B)，(B, C)，(C, D)，(D, A)，(A, C)。

离散数学经典测试题及答案第一题: 命题逻辑与真值表根据下列命题符号表示的逻辑表达式，填写真值表。

1. \(p \land q\)2. \((\lnot p \lor q) \land (p \implies q)\)答案1. \(p \land q\)2. \((\lnot p \lor q) \land (p \implies q)\)第二题: 数学归纳法证明使用数学归纳法证明下列等式对于所有\(n \geq 1\)成立。

\(\sum_{i=1}^{n}(2i-1) = n^2\)证明1. 基础步骤：当\(n=1\)时，左边等式为\(1\), 右边等式为\(1^2 = 1\), 成立。

2. 归纳假设：假设当\(n=k\)时等式成立，即\(\sum_{i=1}^{k}(2i-1) = k^2\)。

3. 归纳步骤：考虑\(n=k+1\)的情况，- 左边等式为\(\sum_{i=1}^{k+1}(2i-1) = \sum_{i=1}^{k}(2i-1) + (2(k+1)-1)\)- 右边等式为\((k+1)^2 = k^2 + 2k + 1\)现在我们可以利用归纳假设，将左边等式展开：\(\sum_{i=1}^{k}(2i-1) + (2(k+1)-1) = k^2 + 2k + 1\)然后，化简左边的部分可以得到：\(k^2 + (2k - 1) + (2(k+1) - 1) = k^2 + 2k + 1\)这个等式成立，证明完毕。

第三题: 集合论给定两个集合A和B，证明下列恒等式成立：\(A \cup (B - A) = A \cup B\)证明我们可以使用集合论的定义来证明这个恒等式。

1. 证明\(A \cup (B - A) \subseteq A \cup B\)- 对于任意\(x \in A \cup (B - A)\)，有两种情况：- 如果\(x \in A\)，则\(x \in A \cup B\)，因为\(A \subseteq A \cupB\)。