离散数学章练习题及复习资料

《离散数学》综合复习资料一、判断题1． A 、B 、C 是任意命题公式，如果A ∧C ⇔B ∧C ，一定有A ⇔B 。

（ ）2．设<A ，*>是一个代数系统，且集合A 中元素的个数大于1。

如果该代数系统中存在幺元e 和零元θ，则e ≠θ。

（ ）3． A 、B 、C 为任意集合，已知A ⋃B=A ⋃C ，必须有B=C 。

（ ） 4． 自然数集是可数的。

（ ）5． 命题联结词{⌝，∧，∨}是最小联结词组。

（ ） 6． 有理数集是可数的。

（ ） 7． 交换群必是循环群。

（ ）8． 图G 的邻接矩阵A ，A l 中的i 行j 列表示结点v i 到v j 长度为l 路的数目。

（ ） 二、解答题1．求命题公式⌝(P →Q)的主析取范式。

2．举出A={a,b,c}上的二元关系R 和S 满足：（1）R 既不是自反的又不是反自反的，既是对称的又是反对称的； （2）S 既不是对称的又不是反对称的，是传递的。

3．以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。

（1） f: N →Q, f(x) = 1/x（2） f: R ⨯R →R ⨯R, f(x,y)=<y+1,x+1> 4．判断下列代数系统是否是群，并说明理由：(1) <R ，->：实数集关于减法； (2) <I ，+>：整数集关于加法；5.构造一非空偏序集，它存在一子集有上界，但没有最小上界。

它还有一子集，存在最大下界但没有最小元。

6.画一个有欧拉回路，但没有汉密尔顿回路的图。

d ︒ b ︒︒e ︒c︒a7.将下列命题符号化（1）如果张三和李四都不去，她就去。

（（⌝P ∧⌝Q ）→R ） （2）今天要么是晴天，要么是雨天。

（P ∀Q ） 8.设G=<V,E>，V={V1,V2,V3,V4}的邻接矩阵：（1）试画出该图。

（2）V2的入度d -(V2)和出度d +(V2)是多少？（3）利用邻接矩阵的性质求从V1到V2长度为3的路有几条？ 9.将下列命题符号化（1）除非你走否则我留下。

离散数学试题第一部分选择题一、单项选择题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的交集表示为A∩B，它包含所有既属于A又属于B的元素。

请写出集合{1, 2, 3}和{2, 3, 4}的交集。

答案：{2, 3}2. 逻辑运算设命题p为“今天是周一”，命题q为“明天是周三”。

请判断复合命题“p且q”的真值。

答案：假3. 图论初步在无向图中，若存在一条路径使得起点和终点相同，则称该图为欧拉图。

请判断一个有5个顶点且每个顶点的度均为2的无向图是否一定是欧拉图。

答案：是4. 组合数学从5个不同的球中选取3个，有多少种不同的选取方法？答案：10种5. 布尔代数在布尔代数中，逻辑或运算符表示为∨，逻辑与运算符表示为∧。

请计算表达式(A∨B)∧(¬A∨¬B)的值。

答案：¬(A∧B)6. 归纳与递归给定递归关系式T(n) = 2T(n-1) + 1，初始条件为T(1) = 1，求T(3)的值。

答案：T(3) = 2T(2) + 1 = 2(2T(1) + 1) + 1 = 2(2*1 + 1) + 1 =2(3) + 1 = 77. 有限状态机在有限状态机中，状态转移可以通过一个转移函数来描述。

若状态转移函数定义为δ(q, a) = q'，其中q和q'是状态，a是输入符号，请说明该函数的作用。

答案：该函数定义了在给定当前状态q和输入符号a的情况下，有限状态机将转移到新的状态q'。

8. 正则表达式正则表达式用于描述字符串的模式。

请写出匹配任意长度的数字串的正则表达式。

答案：\d*9. 命题逻辑命题逻辑中的等价关系是指两个命题逻辑表达式在所有可能的真值赋值下具有相同的真值。

请判断命题p∨¬p和命题¬(p∧¬p)是否等价。

答案：是10. 树的遍历在计算机科学中，树的遍历有前序、中序和后序三种方式。

请简述后序遍历的步骤。

答案：后序遍历的步骤是先访问左子树，然后访问右子树，最后访问根节点。

离散数学复习资料一、填空1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，yx y x L >:),(则命题的逻辑谓词公式为 。

2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不但是100米冠军，而且是500米冠军”的符号化形式为 。

命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。

3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 。

4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。

则谓词(()(()(,)))x P x y O y N y x ∀→∃∧ 的自然语言是 对于任意一个素数都存在一个奇数使该素数都能被整除 。

5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ∀⌝∨∀写成不含量词的形式是 。

6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ∀∀∃∧→∃的前束范式为 。

7. 命题公式)))(((R Q Q P P A →⌝∧→⌝∨⇔的主合取范式为 ，其编码表示为 。

8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ，～Φ= 。

9. 设={256},{234},{134}A B C ==，，，，，，，则A-B= ，A ⊕B = ，A ×C = 。

10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =，}},,{{4c b a S =，}}{},{},{{5c b a S =，}},{},{{6c a a S =则A 的覆盖有 ，A 的划分有 。

离散数学章节练习4K E Y(总5页)-CAL-FENGHAI.-(YICAI)-Company One1-CAL-本页仅作为文档封面，使用请直接删除离散数学 章节练习 4范围：代数系统一、单项选择题 1. <G,*>是群，则对* ( A ) A 、有单位元，可结合 B 、满足结合律、交换律 C 、有单位元、可交换 D 、有逆元、可交换2. 设N 和Z 分别表示自然数和整数集合，则对减法运算封闭的是 ( B )A 、NB 、{x ÷2|x ∈Z}C 、{x|x ∈N 且x 是素数}D 、{2x+1| x ∈Z }3. 设Z 为整数集，A 为集合，A 的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是群的代数系统的有 ( B ) A.〈Z ，+，÷〉 B.〈Z ，÷〉 C.〈Z ，－，÷〉 D.〈P(A)，⋂〉 4. 设S={0，1}，*为普通乘法，则< S , * >是 ( B ) A 、半群，但不是独异点； B 、只是独异点，但不是群； C 、群； D 、环，但不是群。

5. 设f 是由群<G,☆>到群<G ',*>的同态映射，则ker (f)是 ( B ) A 、G '的子群 B 、G 的子群 C 、包含G ' D 、包含G 6. 在整数集Z 上,下列哪种运算不是封闭的 ( C ) A + B - C ÷ D X 7. 设S={0，1}，*为普通乘法，则< S , * >是 ( B )A 、半群，但不是独异点；B 、只是独异点，但不是群；C 、群；D 、环，但不是群。

8. 设R 是实数集合，“⨯”为普通乘法，则代数系统<R ，×> 是（ A ）。

A ．群； B ．环； C ．半群 Ｄ.都不是 9. 设︒是集合S 上的二元运算，如果集合S 中的某元素eL,对∀x ∈S 都有 eL ︒x=x ,则称eL 为 ( C ) A 、右单位元 B 、右零元 C 、左单位元 D 、左零元 10. <Z,+> 整数集上的加法系统中0是 ( A ) A 单位元 B 逆元 C 零元 D 陪集 11. 若V=<S,︒>是半群，则它具有下列那些性质 ( A ) A 、封闭性、结合性 B 、封闭性、交换性 C 、有单位元 D 、有零元 二、判断题 1．若半群<S,*>含有零元，则称为独异点。

总复习题（一）一．单选题1 (C)。

一连通的平面图，5个顶点3个面，则边数为（）。

、4 、5 、6 、72、 (A)。

如果一个简单图，则称为自补图，非同构的无向4阶自补图有（）个。

、1 、2 、3 、43、 (D)。

为无环有向图，为的关联矩阵，则（）。

、是的终点、与不关联、与关联、是的始点4、 (B)。

一连通的平面图，8个顶点4个面，则边数为。

、9 、10 、11 、125、 (D)。

如果一个简单图，则称为自补图，非同构的3阶有向完全图的子图中自补图有个。

、1 、2 、3 、46、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。

、13 、12 、11 、107、 (D)。

有向图的通路包括。

、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路8、 (D)。

一连通的平面图，9个顶点5个面，则边数为。

、9 、10 、11 、12A B C D G G ≅G A B C D E ,V D =[]m n ij m ⨯D 1m ij =A i v j e B i v j e C i v j e D i v j e A B C D G G ≅G A B C D A B C D A B C D A B C D9、21条边，3个4度顶点，其余顶点为3度的无向图共有个顶点。

、13 、12 、11 、1010、 (D)。

有向图的通路包括。

、简单通路、初级通路、复杂通路、简单通路、初级通路和复杂通路11、 (D)。

一连通的平面图，9个顶点5个面，则边数为。

、9 、10 、11 、1212、 (B)。

为有向图，为的邻接矩阵，则。

、邻接到的边的条数是５、接到的长度为４的通路数是５、长度为４的通路总数是５、长度为４的回路总数是５13、 (C)。

在无向完全图中有个结点，则该图的边数为（）。

A 、B 、C 、D 、14、 (C)。

任意平面图最多是（）色的。

A 、3B 、4C 、5D 、615、 (A)。

对与10个结点的完全图，对其着色时，需要的最少颜色数为（）。

《离散数学》考试复习题《离散数学》复习题⼀、填空题： 1、“明年的10⽉1⽇。

”是真命题。

（对、错） 2、命题可分为三类，则P ∧（P ∨Q ）是式。

3、P ↑Q= （在{?，∨}中表⽰）。

4、P ∧（P ∨Q ）的对偶式是。

5、若A 为任意⼀公式，若A 中⽆⾃由出现的个体变项，则称A 为。

6、??xA （x ）? A （x ）。

7、P （{?，{1}}）= 。

8、若A ?B 且B ?A ，则A B 。

9、│A ⊕B │= 。

10、A 、B 、C 分别为集合，则（A ×B ）×C A ×（B ×C ）。

（=、≠）11、设F={（x ，y ）│x ，y ∈N ∧y=x 2}，则F ↑{1，2}= 。

12、设F ，G ，H 为任意的关系，则有F ?（G ?H ） F ?G ∩F ?H 。

（关系） 13、若R 具有⾃反性、、，则R 是等价关系。

14、序列（3，4，4，1，0）是⽆向简单图的度数序列。

（对、错）⼆、选择题：1、设P:我们划船，Q:我们跑步。

命题“我们不能既划船⼜跑步”符号化为（） A 、P Q ?∧? B 、P Q ?∨? C 、()P Q ?? D 、P Q ??2、下⾯哪个联结词运算不可交换？（）3、谓词公式(()())()x P x yR y Q x ?∨?→中量词x ?的作⽤域是（） A 、∧ B 、→ C 、∨ D 、?4、在0 ?之间填上正确的符号。

（） A ．?B ．∈C ．?D ．＝5、幂集()()()P P P ?为（） A ．{}{}{}{}{}{},,,B ．{}{}{}{},,,C ．{}{}{}{},, D ．{}{}{},,6、集合{}1,2,10A = 上的关系{},|10,,R x y x y x A y A =+=∈∈，则R 的性质为（） A ．⾃反的 B ．传递的，对称的 C ．对称的 D ．反⾃反的，传递的7、设R 和S 是集合A 上的任意关系，则下列命题为真的是（） A ．若R 和S 是传递的，则R S 也是传递的 B ．若R 和S 是反⾃反的，则R S 也是反⾃反的C ．若R 和S 是对称的，则R S 也是对称的D ．若R 和S 是⾃反的，则R S 也是⾃反的8、设R 和S 是集合A 上的等价关系，则R S ?的对称性（） A ．不可能成⽴ B ．⼀定不成⽴ C ．不⼀定成⽴ D ．⼀定成⽴9、集合A 上的关系R 是相容关系的必要条件是（） A ．⾃反、反对称的 B ．反⾃反、对称的 C ．传递、⾃反的 D ．⾃反、对称的10、设集合A 中有4个元素，则A 上的不同的等价关系的个数为（） A ．11个 B ．14个 C ．15个 D ．17个 11、下⾯哪个是最⼩命题联结词集（）A 、{,}??B 、{,,}?∧∨C 、{}↑D 、{,}∧→ 12、重⾔式的否定式是（）A 、重⾔式B 、⽭盾式C 、可满⾜式D 、蕴含式 13、下⾯哪个是真命题？（）A 、1+2=5B 、雪是⿊的C 、如果1+2=3，那么雪是⿊的D 、如果1+2=5，那么雪是⿊的 14、任何⽆向图中结点间的连通关系是（） A ．偏序关系 B ．相容关系 C ．等价关系 D ．拟序关系 15、设1,,V D VE = 是强连通图，当且仅当（）A ．D 中有通过每个结点⾄少⼀次的回路B ．D 中⾄少有⼀条回路C ．D 中有通过每个结点⾄少⼀次的通路 D ． D 中⾄少有⼀条通路 16、含5个结点、3条边的不同构的简单图有（） A ．2个 B ．3个 C ．4个 D ．5个17、给定下列序列，可构成⽆向简单图的结点度数序列是（） A ．（1，1，2，2，2） B ．（1，1，2，2，3） C ．（0，1，3，3，3） D ．（1，3，4，4，5）18、图G 和图G '的结点和边分别存在⼀⼀对应关系是G 和G '同构的（） A ．充分条件 B ．既不充分也不必要条件C ．充要条件D ．必要条件19、K 4中含3条边的不同构⽣成⼦图有（） A ．1个 B ．4个 C ．3个 D ．2个 20、在有n 个结点的连通图中，其边数（）A ．最多有1n -条B ．到少有n 条C ．最多有n 条D ．到少有1n -条 21、欧拉回路是（） A ．简单回路 B ．路径 C ．既是基本回路也是简单回路 D ．既⾮基本回路也⾮简单回路22、哈密尔顿回路是（）A ．路径B ．简单回路C ．既是基本回路也是简单回路D ．既⾮基本回路也⾮简单回路23、设集合{}1,2,3,10A = ，半序关系≤是A 上的整除关系，则半序集(),A ≤上元素10是集合A 的（）A ．最⼤元B ．最⼩元C ．极⼩元D ．极⼤元24、设R 1，R 2是集合{}1,2,3,4A =上的两个关系，基中 ()()()(){}11,1,2,2,2,34,4R = ()()()()(){}21,1,2,2,2,3,3,24,4R = 则R 2是R 1的（）闭包。

1.证明永真公式Q14,Q15,Q16,Q17和Q18。

2.证明P(x)∧任意xQ(x)==>存在x(P(x)∧Q(x))3.设论述域是{a1,a2,a3,…an},试证明下列关系式。

(a) 任意xA(x)∧P<==>任意x(A(x)∧P)(b) 任意x(A(x)∧B(x))<==>任意xA(x)∧任意xB(x)(c) 存在x(A(x)∧B(x))<==>存在xA(x)∧存在xB(x)4.证明下列关系式(a) 任意x任意y(P(x)∨P(y))<==>任意xP(x)∨任意yP(y)(b) 存在x存在y(P(x)∧Q(y))==>存在xP(x)(c) 任意x任意y(P(x)∧Q(y))<==>任意xP(x)∧任意yQ(y)(d) 存在x存在y(P(x)－＞P(y)) <==>任意xP(x)－＞存在yP(y)(e) 任意x任意y(P(x) －＞Q(y)) <==>(存在xP(x)－＞任意yQ(y))5.写出limf(x)=k的定义的符号形式，并用形成定理两边的否定的方法，找出limf(x)不等x->c x->c于k的条件。

6.给定自然数集合N的下列子集：A={1,2,7,8}B={i|i平方<50}C={i|i可被30整除}D={i|i=2的k次方∧k∈I∧0≤k≤6}求下列集合(a)A∪(B∪(C∪D))(b)A∩(B∩(C∩D))(c)B-(A∪C)(d)(非A∩B) ∪D7.假定A≠空集和A∪B=A∪C，证明这不能得出B=C，假设中增加A∩B=A∩C，你能得出B=C吗？8．(a)证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A-B≠B-A。

(b)A-B=B-A可能吗？刻划上式出现的全部条件。

(c)“相对补”是一个可结合的运算马？证明你的断言。

9.证明下列恒等式(a)A∪(A∩B)=A(b)A∩(A∪B)=A(c)A-B=A∩非B(d)A∪(非A∩B)=A∪B(e)A∩(非A∪B)=A∩B10.设Sn={a0,a1,…,an}和Sn+1={a0,a1, …,an,an+1},试用p(Sn)和an+1表达出p(Sn+1)。

离散数学试题及答案解析一、选择题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，都可以通过图中的边相互到达。