离散数学代数系统部分练习题参考答案2018春

第四节 代数系统1 A={所有实数},ο： （a ，b ） a ＋2b ＝a οb这个代数运算是否满足结合律？解：(a οb)oc=(a ＋2b)oc=a+2b+2c ≠ao(b οc)=ao(b+2c)=a+2b+4c ，所以不满足结合律.2 A={1,2,3,…,100},找一个A ×A 到A 的映射。

解：o:aob=max{a,b},是一个从A ×A 到A 的映射。

3 A={a,b,c,d},由表a b c da abc db b d a cc c a b dd d c d b所给的代数运算是否满足交换律?是否有单位元？是否有零元？解：满足交换律，a 是单位元，没有零元？4 全体整数的集合对于普通减法来说是否构成一个群。

解：全体整数的集合对于普通减法来说不构成一个群，因为不满足结合律，即a-(b-c)≠(a-b)-c5 举一个有两个元的群的例子。

解：A={0，1}，运算“*”的运算表为 * 0 10 0 11 1 0其中0是单位元，1的逆元为自身。

实际上运算“*”是模为2的同余加法运算。

6 设G 是整数集，对G 规定一个运算“о”a оb ＝a ＋b －2证明，（G ，о）是一个群。

证明：显然运算“o ”是封闭的。

（1）满足结合律：ao(boc)=ao(b+c-2)=a+b+c-4=（aob ）oc=(a+b-2)oc（2）存在单位元“2”：2oa=2+a-2=a,ao2=a+2-2=a;(3) 存在逆元：ao(2-a)=(2-a)oa=a+2-a=2,即a 的逆元是2-a.所以（G ，о）是一个群。

7证明:一个有限群的每个元的阶都是有限的.证明：设有限群（G ，o ）中|G|=n ，则任取一元素a ∈G ，显然na a a a ,,,321 中至少有两个表示同一个元素，（否则就不是有限群）设j i a a j i <=,，又I a a a a a i j i j i i ===---)()(11（其中I 是群的单位元），因此 a a oa a i j i j ==+--1)(，显然j-i+1为有限，所以a 的阶是有限的。

《离散数学》代数结构部分练习题2018年6月班级学号姓名一、填空题1.在代数系统（N ，+）中，其单位元是0，仅有有逆元.2.设A 是非空集合，集合代数),),(( A P 中，)(A P 对运算 的单位元是，零元是.)(A P 对运算 的单位元是.3.设Z 为整数集，若1,,-+=∈∀b a b a Z b a ，则Z a ∈∀，a 的逆元=-1a .4.设}3,2,1,0{4=Z ，⊗为模4乘法，即4mod )(xy y x =⊗，4,Z y x ∈∀.则4Z 上运算⊗的运算表为.二、选择题1.设集合{}10,...,3,2,1=A ,在集合A 上定义运算,不是封闭的为()(A){}b a lcm b a A b a ,,,=∙∈∀(最小公倍数)(B){}b a ged b a A b a ,,,=∙∈∀(最大公约数)(C){}b a b a A b a ,max ,,=∙∈∀(D){}b a b a A b a ,min ,,=∙∈∀2.在自然数集N 上定义的二元运算∙,满足结合律的是()(A)b a b a -=∙(B)b a b a 2+=∙(C){}b a b a ,max =∙(D)ba b a -=∙三、计算题1.通常数的乘法运算是否可以看成是下列集合上的二元运算，说明理由.（1）{}2,1=A （2）{}是质数x x B =（3）{}是偶数x x C =（4）{}N n D n ∈=22.实数集R 上的下列二元运算是否满足结合律与交换律？（1）212121r r r r r r -+=*（2）2/)(2121r r r r += 3.实数集R 上的二元关系212121r r r r r r -+=*中，运算*是否有单位元，零元和幂等元？若有单位元的话，那些元素有逆元？4.给定正整数,m 令{}Z k km G ∈=，(1)判断普通加法在G 上是否满足结合律，并说明理由；(2)求普通加法运算的单位元、所有可逆元素的逆元.5.设>< ,Z 中运算 为2,,-+=∈∀b a b a Z b a ，(1)判断普通加法在G 上是否满足结合律，并说明理由；(2)求普通加法运算的单位元、所有可逆元素的逆元.。

《离散数学》题库及标准答案《离散数学》题库及答案————————————————————————————————作者：————————————————————————————————日期：《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( )(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条边。

2018年10月高等教育自学考试全国统一命题考试离散数学试卷(课程代码02324)本试卷共4页，满分l00分，考试时间l50分钟。

考生答题注意事项：1．本卷所有试题必须在答题卡上作答。

答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

4．合理安排答题空间，超出答题区域无效。

第一部分选择题一、单项选择题：本大题共l5小题，每小题l分，共l5分。

在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。

1．下列命题公式为矛盾式的是A．P→ (P ∨ Q ∨ R) B．(P→￢P) →￢QC．￢(Q叶R)∧R D．(P→Q) →(￢Q→￢P)2．命题公式A中含n个命题变项，A为重言式的条件是A的主析取范式含A．2“个极大项 B．1个极大项 C．2ｎ个极小项 D．1个极小项3．设R为集合A上的关系，则下列叙述不正确的是4．设F(x)：x是兔子，G(y)：y是乌龟，H(x，y)：x比y跑得快。

命题“并不是所有兔子都比乌龟跑得快”可符号化为5．设集合X={a，{a}}，则下列陈述不正确的是7．设A={1，{l}，{1，{ l}}}，则其幂集P(A)的元素总个数为A 1 8．4 C．8 D．168.描述偏序集的是A．哈密顿图 B．哈斯图 C．欧拉图 D.树9．在整数集z上，下列定义的运算能构成一个群的是A．a*b=max{a，b} B．a*b=|a-b|C．a*b=a+b+1 D．a*b= ab10．设f:X→Y，，g：Y→Z是函数，则下列陈述不正确的是A．若f和g都是单射的，则f。

g也是单射的B．若f和g都是双射的，则f。

g也是双射的C．若g和f。

g是满射的，则厂也是满射的D.若，和9都是满射的，则f。

g也是满射的11．由4阶3条边构成的无向简单图的结点最大度数为A．1 8．2 C．3 D．412．下列为一颗6阶无向树的度数列，对应不止一颗同构树的是A．1，1，1，l，2，4 B．1，l，1，2，2，3C．1，1，2，2，2，2 D．1，1，1，l，3，314．下列关于整数集合上的小于关系性质描述不正确的是A．反自反的 B．对称的 C．反对称的 D．传递的15．分别记Z、N、Q、R为整数、自然数、有理数、实数集合，下列关于普通加法的代数系统不是群的是A．<Z,+> B.<N,+> C.<Q，+> D．<R，+>第二部分非选择题二、填空题：本大题共l0小题，每小题2分，共20分。

离散数学章节练习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,*>含有零元，则称为独异点。

离散数学（本）2018年10月份试题（含答案）离散数学（本）2018年10月份试题一、单项选择题（每小题3分，本题共15分）1．若集合A＝{1,2,3}，则下列表述不正确的是（）．A．1ÎAB．{1}ÌAC．ÆÎAD．{2}ÍA2．设A={2,3｝，B={3,4}，A到B的关系R={|xÎA,yÎB，且x不大于y｝，则R=（）．A．{<3,3>,<4,4>}B．{<2,3>,<2,4>,<3,3>,<3,4>}C．{<2,3>,<2,4>,<3,4>}D．{<2,2>,<3,3>,<4,4>}3．无向图G的结点的度数之和是24，则图G的边数为（）．A．12B．24C．48D．234．设连通平面图G有v个结点，e条边，r个面，则（）．A．v+e–r=–B．v+er=4C．v+er=2D．r+ve=25．设个体域D是实数集合，则命题($x)(“y)(x´y =y)的真值是（）．A．TB．FC．由y的取值确定D．不确定二、填空题（每小题3分，本题共15分）6．设集合A={a,b}，B={b,c}，C={c,d}，则(AÈB)–(BÇC)=．7．设A={3，6}，B={1，6}，C={3，5}，从A到B的函数f={<3,1>,<6,6>}，从B到C的函数g={<1，3>,<6，5>}，则Dom(g°f)=．8．结点数相等是两个图同构的条件．9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G-S中的连通分支数不超过．10．设个体域D＝{a,b}，则谓词公式(“x)Q(x)消去量词后的等值式为．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“昨天是公休日，今天也是公休日．”翻译成命题公式．12．将语句“如果今天是周五，则明天是周四．”翻译成命题公式．四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）13．如果A是集合B的元素，则A不可能是B的子集．14．(“x)(A(x)→(B(y)→C(z)))中的约束变元为y．五．计算题（每小题12分，本题共36分）15．设A={1，2，3}，R={|xÎA，yÎA且xy}，S={|xÎA，yÎA且x£y}，试求R，S，R-1，s(S)．16．设图G=，其中，结点集V={a,b,c,d,e}，边集E={(a,c),(a,e),(b,d),(b,e),(c,e),(d,e)}，对应边的权值依次为2、3、3、4、1及5，请画出G的图形、写出G的邻接矩阵并求出G权最小的生成树及其权值．17．画一棵带权为1,2,3,4,5的最优二叉树,并计算该最优二叉树的权．六、证明题（本题共8分）18．试证明：P→QÞP→(P∧Q)．离散数学（本）2018年10月份试题参考解答一、单项选择题（每小题3分，本题共15分）1．C2．B3．A4．D5．A二、填空题（每小题3分，本题共15分）6．{a,b}7．{3，6}8．必要9．410．Q(a)∧Q(b)三、逻辑公式翻译（每小题6分，本题共12分）11．设P：昨天是公休日，Q：今天是公休日．（2分）则命题公式为：P∧Q．（6分）12．设P：今天是周五，Q：明天是周四．（2分）则命题公式为：P→Q．（6分）四、判断说明题（每小题7分，本题共14分）13．错误．（3分）反例：设A={1}，B={1,{1}}，则A是B的元素，也是B的子集．（7分）说明：举出符合条件的反例均给分．14．错误．（3分）(“x)(A(x)→(B(y)→C(z)))中的y是自由变元，约束变元为x．（7分）五．计算题（每小题12分，本题共36分）15．R={<2,1>,<3,1>,<3,2>}（3分）S={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}（6分）R-1={<1,2>,<1,3>,<2,3>}（9分）s(S)={<1,1>,<2,1>,<1,2>,<3,1>,<1,3>,<2,2>,<3,2>,<2,3>,<3,3>} （12分）说明：对于每一个求解项，如果基本求出了解，可以给对应1分．16．G的图形表示为：（3分）邻接矩阵：（6分）如下为最小的生成树，权为10：（9分）（12分）17．（10分）权为1´3+2´3+3´2+4´2+5´2=33（12分）六、证明题（本题共8分）18．证明：（1）P→QP（1分）（2）PP（附加前提）（3分）（3）QT（1）（2）I（5分）（4）P∧QT（2）（3）I（7分）（5）P→(P∧Q)CP规则（8分）说明1：因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分。

一、填空题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 时，有 个双射。

离散习题代数系统部分答案1(共3页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《离散数学》代数系统1.以下集合和运算是否构成代数系统如果构成，说明该系统是否满足结合律、交换律求出该运算的幺元、零元和所有可逆元素的逆元.1)P(B)关于对称差运算⊕，其中P(B)为幂集.构成代数系统；满足结合律、交换律；幺元φ；无零元；逆元为自身。

2)A={a,b,c}，*运算如下表所示：构成代数系统；满足结合律、交换律；无幺元；无逆元；零元b.2.设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算（2）在A上可以定义多少不同的具有交换律的二元运算24个不同的二元运算；23个不同的具有交换律的二元运算3.设A={1,2},B是A上的等价关系的集合.1)列出B的元素.2元集合上只有2种划分，因此只有2个等价关系，即B={I A，E A}2)给出代数系统V=<B,∩>的运算表.3)求出V的幺元、零元和所有可逆元素的逆元.幺元E A、零元I A；只有E A可逆，其逆元为E A.4)说明V是否为半群、独异点和群V是为半群、独异点，不是群4.设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律.1)给出关于*运算的一个运算表.其中表中位置可以是a、b、c。

2)*运算是否满足结合律，为什么不满足结合律；a*（b*b）=c ≠（a*b）*b=b5.设<R，*>是一个代数系统。

*是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法).证明：:<R，*> 是独异点.6.如果<S,*>是半群，且*是可交换的.证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b.(a*b)*(a*b)= a*(b*a)*b 结合律= a*( a*b)*b 交换律= (a* a)*(b*b)= a*b.7.设<G,·,–1,e>是一个群,则a,b,c∈S。

《离散数学(本科)》2018期末试题及答案一、单项选择题（每小题3分，本题共15分）1．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( )．A ．2⊂AB ．{1}⊂AC ．1∉AD ．2 ∈ A2．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( )．A ．6B ．4C ．3D ．53．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110 则G 的边数为( )．A ．1B ．7C ．6D ．14 4．设集合A ={a }，则A 的幂集为( )．A ．{{a }}B ．{a ，{a }}C ．{∅，{a }}D ．{∅，a }5．下列公式中 ( )为永真式．A ．⌝A ∧⌝B ↔ ⌝A ∨⌝B B ．⌝A ∧⌝B ↔ ⌝(A ∨B )C ．⌝A ∧⌝B ↔ A ∨BD ．⌝A ∧⌝B ↔ ⌝(A ∧B )二、填空题（每小题3分，本题共15分）6．命题公式P P ⌝∧的真值是 ．7．若无向树T 有5个结点，则T 的边数为 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 ，就可使新得到的关系为对称的．10．(∀x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 ．三、逻辑公式翻译（每小题6分，本题共12分）11．将语句“今天上课．”翻译成命题公式．12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．14．设G是一个有4个结点10条边的连通图，则G为平面图．五．计算题（每小题12分，本题共36分）15．试求出（P∨Q）→（R∨Q）的析取范式．16．设A={{1}, 1, 2}，B={1, {2}}，试计算（1）（A∩B）（2）（A∪B）（3）A （A∩B）．17．图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，对应边的权值依次为1、2、3、1、4及5，试（1）画出G的图形；（2）写出G的邻接矩阵；（3）求出G权最小的生成树及其权值．六、证明题（本题共8分）18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．试题解答一、单项选择题（每小题3分，本题共15分）1．B 2．D 3．B 4．C 5．B二、填空题（每小题3分，本题共15分）6．假（或F，或0）7．48．t-19． <2, 1>10．z ，y三、逻辑公式翻译（每小题6分，本题共12分）11．设P ：今天上课， （2分） 则命题公式为：P ． （6分）12．设 P ：他去操场锻炼，Q ：他有时间， （2分） 则命题公式为：P →Q ． （6分）四、判断说明题（每小题7分，本题共14分）13．错误． （3分） 因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数． （7分）14．错误． （3分） 不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v -6．” （7分）五．计算题（每小题12分，本题共36分）15．（P ∨Q ）→（R ∨Q ）⇔ ┐(P ∨Q )∨（R ∨Q ） （4分）⇔ (┐P ∧┐Q )∨（R ∨Q ） （8分）⇔ (┐P ∧┐Q )∨R ∨Q （析取范式） （12分）16．（1）（A ∩B ）={1} （4分）（2）（A ∪B ）={1, 2, {1}, {2}} （8分）（3） A -（A ∩B ）={{1}, 1, 2} （12分）17．（1）G 的图形表示如图一所示：（3分）（2）邻接矩阵：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101111011110 （6分） 图一 ο ο ο ο a b c d1 12 4 53（3）最小的生成树如图二中的粗线所示：（10分） 权为：1+1+3=5 （12分）六、证明题（本题共8分）18．证明：设∀x ∈A ，因为R 自反，所以x R x ，即< x , x >∈R ；又因为S 自反，所以x R x ，即< x , x >∈S ．（4分） 即< x , x >∈R ∩S（6分） 故R ∩S 自反．（8分） 图二 ο ο ο ο a b c d 1 1 2 4 5 3。

第九章 特殊的代数系统习题9.11．解 ⑴是半群。

显然，二元运算“ ”在N 上是封闭的， 所以，>< ,N 是一个代数系统， 另一方面，,,,N c b a ∈∀有(){}{}c b a c b a c b a ,,max ,max == ，而(){}{}c b a c b a c b a ,,m ax ,m ax == ，因此，()()c b a c b a =，所以，运算“ ”满足结合律的，故>< ,N 是半群；⑵是半群。

显然，二元运算“ ”在N 上是封闭的， 所以，>< ,N 是一个代数系统， 另一方面，N c b a ∈∀,,，有()c c b c b a == ，而()c c a c b a == ，则()()c b a c b a =，所以，运算“ ”满足结合律，故><,N 是半群；⑶是半群。

显然，二元运算“ ”在N 上是封闭的， 所以，>< ,N 是一个代数系统， 另一方面，N c b a ∈∀,,，有()abc c ab c ab c b a 4)2(2)2(=== ，()()abc bc a bc a c b a 422)2(=== ，即()()c b a c b a = ，所以，运算“ ”满足结合律，故>< ,N 是半群。

⑷不是半群。

虽然，二元运算“ ”在N 上是封闭的，即>< ,N 是一个代数系统，但是 对于5，3，6，因为，()4635635635=--=-= ，而2635635)63(5=--=-= ，即())63(5635 ≠，所以，运算“ ”不满足结合律，故>< ,N 不是半群。

2．解 ⑴正确。

因为，运算显然封闭。

⑵正确。

abc bc ac ab c b a c ab b a c b a ++++++=++= )()(， bc ac ab c b a bc c b a c b a +++++=++=)()( ，即是()()c b a c b a =，所以︒满足结合律。

全国2018年7月高等教育自学考试离散数学试题课程代码：02324一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题1分，共14分)1.下列语句不是．．命题的是( )。

A.黄金是非金属。

B.要是他不上场，我们就不会输。

C.他跑100米只用了10秒钟，你说他是不是运动健将呢?D.他跑100米只用了10秒钟，他是一个真正的运动健将。

2.关于命题变元P和Q的大项M01表示( )。

A.┐P∧QB.┐P∨QC.P∨┐QD.P∧┐Q3.公式(∀x)(∃y)(P(x,z)→Q(y))S(x,y)中的(∀x)的辖域是( )。

A.(∃y)(P(x,z)→Q(y))B.P(x,z)→Q(y)C.P(x,z)D.S(x,z)4.下列等价式不成立．．．的是( )。

A.┐(∃x)A(x)⇔(∀x)┐A(x)B.┐(∀x)A(x)⇔(∃x)┐A(x)C.(∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)D.(∀x)(A(x)∨B(x))⇔(∀x)A(x)∨(∀x)B(x)5.公式(∃x)(∀y)(P(x,y)∧Q(z))→R(x)中的x( )。

A.只是约束变元B.只是自由变元C.既是约束变元又是自由变元D.既非约束变元又非自由变元6.设A={a,{a}}，则下列各式正确的是( )。

A.{a}∈p(A)(A的幂集)B.{a}⊆p(A)C.{{a}}⊆p(A)D.{a,{a}}⊆p(A)7.集合的以下运算律不成立．．．的是( )。

A.A∩B=B∩AB.A∪B=B∪AC.A⊕B=B⊕AD.A-B=B-A8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。

A.入射B.满射C.双射D.非以上三种的一般函数9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。

A.交换律B.结合律12C.有幂等元D.有零元10.若(A ，*)是一个代数系统，且满足结合律，则(A ，*)必为( )。

离散数学习题解代数系统习题四 第四章代数系统1．设I 为整数集合。

判断下面的二元关系是否是I 上的二元运算a ）+=｛（x ，y ），z|x ，y ，zI 且z=x+y}b ）－={（（x ，y ），z ）｜x,y ，zI 且z=x －y}c ）×={（（x,y)，z ）｜x ，y ，zI 且z=x ×y}d ）/={(（x ，y)，z)|x ，y ，zI 且z=x/y ｝e ）R={（（x,y ），z)｜x,y,zI 且z=x y｝f ）=｛（（x ，y),z ）｜x ，y ，zI 且z=yx }g)min = ｛(（x ，y ），z ）|x ，y ，zI 且z=max （x ，y)} h ）min = {（（x,y ），z)|x,y,zI 且z=min （x ，y ）} i ）GCD = {（(x ，y ），z ）｜x ，y ，zI 且z= GCD(x ，y ）} j ）LCM={（（x ，y ）,z ）｜x ，y ，z ∈I 且z= LCM （x ，y ）｝[解］ a ）是。

由于两个整数之和仍为整数，且结果唯一,故知+：I 2→I 是I 上的一个二元运算. b ）是。

由于两个整数之差仍为整数，且结果唯一,故知一：I 2→I 是I 上的一个二元运算。

c ）是.由于两个整数这积仍为整数,且结果唯一，故知x ：I 2→I 是I 上的一个二元运算。

d ）不是:例如若x=5，y=6,则z=x/y=5/6∉I;当y=0时z=x|y=x/0无定义. e ）不是。

例如若x=2,y= —2，则z=x y=2–2=221=I 41∉；若x=y=0，则z=x y=0,则z=I 2x ∉=χ; g ）是。

由于两个整数中最大者仍为整数，且结果唯一。

故知max ：I 2→I 是I 上的一个二元运算。

h ）是。

由于两个整数中最小者仍为整数，且结果唯一。

故知min ：I 2→I 是I 上的一个二元运算。

第八章 代数系统习题8.11．解 ⑴是，⑵不是，⑶是，⑷不是。

2．解 若﹡对 是可分配的，则有任意a,b,c ∈*I,均有a ﹡(b c)=(a ﹡b) (a ﹡c)= a b ac =( a b ⋅ a c )= a b+c而a ﹡(b c)=a ﹡(b ⋅c)= a b ⋅c ≠a b+c 故﹡对 是不可分配的。

3．解 ⑴对于任意A ∈P(S), 因为A ⊆S ，所以，A ⋃S =S ，因此，S 是关于⋃运算的零元； ⑵对于任意A ∈P(S), 因为A ⊆S ，所以，A ⋂S = A ，因此，S 是关于⋃运算的零元单。

4．解 ⑴①因为x*y=xy-2x-2y+6，则y*x=yx-2y-2x+6= x*y ，满足交换律； ②任意x,y,z ∈R 有x*(y*z)=x*(yz-2y-2 z +6)=x(yz-2y-2 z +6)-2x-2(yz-2y-2z+6)+6 =xyz-2xy-2xz+6x-2x -2yz+4y+4z-12+6= xyz-2xy-2xz-2yz+4x+4y+4z-6. (x*y)*z=(xy-2x-2y+6) *z =(xy-2x-2y+6)z-2(xy-2x-2y+6)-2z+6 =xyz-2xz-2yz+6z-2xy+4x+4y-2z-6=x*(y*z). 故满足结合律。

(2) ①设任意a ∈R,存在e ∈R,要e*a= ea-2e-2a+6=a ，由于a 的任意性则e=3。

因此e=3是其单位元;②设任意b ∈R, z ∈R ，要有z*b= zb-2 z-2b+6= z ，由于b 的任意性则z=2，因此 z=2是其零元。

（3）因为*是满足交换律，对于x ∈R ，要存在1-x ∈R ，须有x*1-x= x 1-x-2x-21-x+6= e=3, 当x ≠2时，2321--=-x x x。

即对于任意的x ，当x ≠2时x 都是可逆的，且2321--=-x x x。

5．解 f 1,f 2,f 3都满足交换律，f 4满足等幂率，f 2有单位元a ，f 1有零元a ，f 3有零元b 。

全国2018年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．下列命题公式为重言式的是（）A．p→(p∨q) B．(p∨┐p)→qC．q∧┐q D．p→┐q2．下列语句中不是．．命题的只有（）A．这个语句是假的。

B．1+1=1.0C．飞碟来自地球外的星球。

D．凡石头都可练成金。

3．设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是（）A．┐p∧q B．┐p→qC．┐p→┐q D．p→┐q4．下列等价式正确的是（）A．┐)x∃A⇔∃┐A()(xB．A(∀∃)(∀)∀⇔x)Axyy)((C．┐)⇔∀┐Ax∃A)(x(D．)BxxxxAAx⇔∧∀∨x∀∀()(()())))((x()(B5．在公式)QyPzyxP∧∀→x∃y∃中变元y是（）)(()))y,(((z)((),A．自由变元B．约束变元C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元6．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（）A．自反关系B．反自反关系C．对称关系D．传递关系7．设集合X为人的全体，在X上定义关系R、S为R={<a，b|a，b∈X∧a是b的父亲}，1S={<a，b>|a，b∈X∧a是b的母亲}，那么关系{<a，b>|a，b∈x∧a是b的祖母}的表达式为（）A．RοS B．R-1οSC．SοR D．RοS-18．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩({2，3，4，6}×{2，3，4，6})=（）A．O/B．{<3，3>}C．{<3，3>，<6，2>}D．{<3，3>，<6，2>，<9，1>}9．下列式子不正确的是（）A．(A-B)-C=(A-C)-B B．(A-B)-C=A-(B∪C)C．(A-B)-C=(A-C)-(B-C) D．A-(B∪C)=(A-B)∪C10．下列命题正确的是（）A．{l，2}⊆{{1，2}，{l，2，3}，1}B．{1，2}⊆{1，{l，2}，{l，2，3}，2}C．{1，2}⊆{{1}，{2}，{1，2}}D．{1，2}∈{1，2，{2}，{l，2，3}}11．在下列代数系统中，不是环的只有（）A．<Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。

试卷二十二试题与答案一、单项选择题：（每小题1分，本大题共15分）1．设A={1，2，3，4，5}，下面（ ）集合等于A 。

A 、{1，2，3，4，5，6}；B 、}25{2≤x x x 是整数且； C 、}5{≤x x x 是正整数且； D 、}5{≤x x x 是正有理数且。

2．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。

A 、A ⊆Φ；B 、{6，7，8}∈A ；C 、{{4，5}}⊂A ；D 、{1，2，3}⊂A 。

3．六阶群的子群的阶数可以是（ ）。

A 、1，2，5；B 、2，4；C 、3，6，7；D 、2，3 。

4．设B A S ⨯⊆，下列各式中（ ）是正确的。

A 、 domS ⊆B ； B 、domS ⊆A ；C 、ranS ⊆A ；D 、domS ⋃ ranS = S 。

5．设集合Φ≠X ，则空关系X Φ不具备的性质是（ ）。

A 、自反性；B 、反自反性；C 、对称性；D 、传递性。

6．下列函数中，（ ）是入射函数。

A 、世界上每个人与其年龄的序偶集；B 、、世界上每个人与其性别的序偶集；B 、 一个作者的专著与其作者的序偶集； D 、每个国家与其国旗的序偶集。

7．><,*G 是群，则对*（ ）。

A 、满足结合律、交换律；B 、有单位元，可结合；C 、有单位元、可交换；D 、每元有逆元，有零元。

8．下面（ ）哈斯图所描述的偏序关系构成分配格。

9．下列（ ）中的运算符都是可交换的。

A 、→∨∧,,；B 、↔→,；C 、⨯⋂⋃,,；D 、∧∨,。

10．设G 是n 个结点、m 条边和r 个面的连通平面图，则m 等于（ ）。

A 、n+r-2 ；B 、n-r+2 ；C 、n-r-2 ；D 、n+r+2 。

11．n 个结点的无向完全图n K 的边数为（ ）。

A 、)1(+n n ；B 、2)1(+n n ；C 、)1(-n n ；D 、2)1(-n n 。