离散习题代数系统部分答案1

离散数学（1）复习题一、单项选择题1、下列命题正确的是（ A ）。

A. φ⋂{φ}=φB. φ⋃{φ}=φC. {a}∈{a，b，c}D. φ∈{a，b，c}2、设集合｛1 2 3 4 ｝，A上的关系R=｛（1 1）（2 3）（2 4）（3 4）｝则R具有（ B ）。

A. 自反性B. 传递性C. 对称性D. 以上答案都不对3、设Z是整数集，函数f定义为：Z Z→, f(x)=|x|-2x,则f是（ A ）。

A. 单射B. 满射C. 双射D. 非单射也非满射4、设R为实数集，定义R上4个二元运算，不满足结合律的是（ B ）。

A. f1(x,y)= x+y B. f2(x,y)=x-yC. f3(x,y)=xy D. f4(x,y)=max{x,y}5、设(A,≤) 是一个有界格，它也是有补格，只要满足（ B ）。

A. 每个元素都有一个补元B. 每个元素至少有一个补元C. 每个元素都无补元D. 每个元素都有多个补元6、图G和'G的结点和边分别存在一一对应关系是G和'G同构的（ B ）。

A. 充分条件B. 必要条件C. 充要条件D. 既不充分也不必要条件7、集合上A的等价关系R，其等价类集合{ [a] 天津大学考试题库及答案R| a∈A }称为（ C ）。

A. A与R的并集，记作A Y RB. A与R的交集，记作A I RC. A关于R的商集，记作A/RD. A与R的差集，记作A—R8、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ C ）。

A. 2B. 3C. 4D. 59、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。

A. 析取范式B. 合取范式C. 主析取范式D. 以上答案都不对10、设谓词():Q x x犯错误，命题“没有不犯错误的人”符号化为P x x是人，():（ D ）。

A. (()())⌝∃→⌝x P x Q x ∀∧ B. (()())x P x Q xC. (()())⌝∃∧⌝x P x Q x ⌝∃∧ D. (()())x P x Q x11、设 |A|=m，|B|=n，则 |ρ(A×B) | 等于（ C ）。

参考答案试卷一一、选择填空1.C2.A3.D4.D5.A6.A7.B8.C9.D 10.B二、填空1.主合取范式)()(q p q p ⌝∨∧∨⌝.前束范式))()((x G x F x →∀或))()((y G x F y x →∀∀ 2. n-k,93.=)(A ρ{Φ,{1}，{2}，{1，2}}，B A ⨯={〈1,a 〉,<1,b>,<2,a>,<2,b>}4. [b]R ={1,2,3}, X/R={{1,2,3},{4},{5}}.5． ,,G y x ∈∀ )()()(y f x f y x f *= 。

6.=-)(1R r { <2,1>,< 4,2>,<1,1>,<3,3>,<2,2>}，=S R {<1,4>,<2,2>}。

7.15，12.8. =τσ⎪⎪⎭⎫ ⎝⎛42134321 =(132) =-1στ⎪⎪⎭⎫ ⎝⎛41324321=(123) 9．0, 45 10．2,0三 1.× 2.√ 3. √ 4.× 5.×四.1．一棵树具有3个2度结点，2个3度结点，2个4度结点，其余为叶。

试求其共有多少个结点？多少片叶？解: 设该树其有x 片叶,则顶点数为x+7, 根据树的性质知,该树有x+6边,由握手定理有:3*2+2*3+2*4+x*1=2(x+6), 得x=8故该树共有15个结点,8 片叶 .2.已知X={a,b,c},给出X 上的所有等价关系。

解:X 的划分其有五种:S 1={{a,b,c}}, S 2={{a,b},{c}}, S 3={{a,c},{b}}, S 4={{a},{b,c}},S 5={{a},{b},{c}},因为X 上划分与等价关系一一对应,故x 上共有五个等价关系，它们是：R 1＝{<a,b>,<b,a>,<a,c><c,a>,<b,c>,<c,b>}X I ⋃R 2＝{<a,b>,<b,a>}X I ⋃, R 3＝{<a,c><c,a>}X I ⋃R 4＝{<b,c>,<c,b>}X I ⋃, R 5＝X I3.．画一棵权为2，3，3，4，5，6，7，8 的最优二叉树，并计算出它的树权。

《离散数学》题库及标准答案《离散数学》题库及答案————————————————————————————————作者：————————————————————————————————日期：《离散数学》题库与答案一、选择或填空（数理逻辑部分）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条边。

第九章 特殊的代数系统习题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 =，所以︒满足结合律。

命题逻辑例1: 下面哪些语句是命题十是一个整数. 真命题北京是一个村庄. 假命题我学英语或法语. 复合命题如果天气好,我就去散步. 复合命题向右看齐! 不是命题您吃饭了吗? 不是命题本命题是假的. 不是命题例2：试以符号形式写出下列命题1） 选小王或小李中的一人当班长。

P: 小王当班长。

Q: 小李当班长。

( P ∧ ⌝ Q) ∨ (⌝ P ∧ Q)2） 小王是计算机系的学生，他生于1982年，他是一个好学生。

P: 小王是计算机系的学生。

Q: 他生于1982年。

R: 他是一名好学生。

P ∧ Q ∧ R3） 只要我上街，我就去书店看看，除非我很累。

P: 我上街。

Q: 我去书店看看。

R: 我很累。

⌝ R →(P → Q)例3 给出下列公式的真值表 成真指派：100，101，110，111例4 试求下面公式的主析取（主合取）范式，并写出成真指派和成假指派。

()()P Q Q P ⌝→→⌝∨例5 证明：P →Q ，⌝Q ∨R ，⌝R ，⌝S ∨P=>⌝S证明：(1) ⌝R 前提(2) ⌝Q ∨R 前提(3) ⌝Q （1），（2）(4) P →Q 前提(5) ⌝P （3），（4）PR Q P →→∧)((6) ⌝S ∨P 前提(7) ⌝S （5），（6）例6 证明：A ，A →B ，A →C ，B →(D → C) => D证明：（1） A 前提（2） A →B 前提（3） B (1)，(2)（4） A →C 前提（5） C (1)，(4)（6） B →(D →⌝C) 前提（7） D →⌝C (3)，(6)（8） ⌝D (5)，(7)例7 证明：⌝B ∨D ，(E →⌝F)→⌝D ，⌝E=>⌝B证明：(1) B 附加前提(2) ⌝B ∨D 前提(3) D （1），（2）(4) (E →⌝F)→⌝D 前提(5) ⌝(E →⌝F) （3），（4）(6) E ∧⌝F （5）(7) E （6）(8) ⌝E 前提(9) E ∧⌝E （7），（8）例8 证明： 谓词逻辑例1 符号化下列命题不是所有的男人都比女人高。

2015春课件作业第一部分集合论第一章集合的基本概念和运算1-1 设集合 A ={{2，3,4}，5，1}，下面命题为真是 A （选择题） [ A ] A．1 ∈A； B．2 ∈ A； C．3 ∈A； D．{3，2,1} ⊆ A。

1-2 A,B,C 为任意集合，则他们的共同子集是 D （选择题） [ D ] A．C； B．A； C．B； D．Ø。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否正确（是非题）（1） N ⊆ Q，Q ∈S，则 N ⊆ S，否［错］（2）-1 ∈Z，Z ∈S，则 -1 ∈S 。

否［错］1-4 设集合 B = {4，3} ∩Ø， C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，E = {x│x ∈R 并且 x2 - 7x + 12 = 0}，F = { 4，Ø，3，3}，试问：集合 B 与那个集合之间可用等号表示 A （选择题） [A ]A. C;B. D;C. E;D. F.1-5 用列元法表示下列集合：A = { x│x ∈N 且 3－x 〈 3 }（选择题） [D ]A. N;B. Z;C. Q;D. Z+1-6 为何说集合的确定具有任意性 ? (简答题)按照所研究的问题来确定集合的元素。

而我们所要研究的问题当然是随意的。

所以，集合的定义（就是集合成分的确定）就带有任意性。

第二章二元关系2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：R = {〈x，y〉x，y ∈X 且 x > y } （综合题）求：(1)domR =?; (2)ranR =?; (3)R 的性质。

所谓谓词表达法，即是将集合中所有元素的共同性质用一个谓词概括起来，如本题几例所示。

有的书上称其为抽象原则。

反过来，列元法则是遵照元素的性质和要求，逐一将他们列出来，以备下用,结果如下：R = {<1,1>,<2,2>,<3,3>}；(1)DomR={R中所有有序对的x}={3,2,1};(2)RanR={R中所有有序对的y}={3,2,1}；(3)R 的性质:自反,对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即R = {〈x，y〉│x，y ∈Z+ 且 x + 3y = 12}，试给出 dom（R 。

离散数学试题与答案试卷一一、填空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、下列公式中与其他公式不等值的是（ d ）。

A：⌝（p↔q）； B：（p∨q）∧⌝（p∧q）；C：（⌝p∧q）∨（p∧⌝q）； D：⌝（p→q）∧⌝（q→p）。

2、取个体域为整数集合，则下列公式中为真命题的是（ a ）。

A：∀x∃y（x y = 0 ）； B：∀x∀y （x y = y ）；C：∃x∀y（x +y = 2y）； D：∀x（ x y = x ）。

3、设集合A={a，b，c}中有下列关系，则其中不具有传递性的是（ E ）。

A: {<a,b>,<a,a>}; B: {<a,a>,<a,b>,<c,a>,<c,b>}; C: { };D:{<a,b>,<a,c>}; E: {<a,a>,<a,b>,<b,a>,<c,c>}; F: {<a,b>}。

4、下列命题中为假的是（ B ）。

A：{a}∈{{a}}； B：{a}⊆{{a}}；C：{a}∈{a，{a}}； D：{a}⊆{a，{a}}。

5、设S = {1，2，3，6}，∘是取两个数的最小公倍数，∗是取两个数的最大公约数，则S是（）。

A：环，不一定是域； B：格，但不是布尔代数；C：布尔代数； D：不构成代数系统。

6、具有如下的代数系统<G,*>哪个不构成群（）A：G={1，10}，*是模11乘法； B：G={1，3，4，5，9}，*是模11乘法；C：G=Q（有理数），*是普通加法；D：G=Q，*是普通乘法7、设F(x)表示x 是火车，G（y）表示y是汽车，H（x,y）表示x比y快，命题“某些汽车比所有火车慢”的符号化公式是（ B ）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)))8、设无向图G中有12条边，已知G中3度结点有6个，其余结点的度数均小于3，则G中结点数至少是（ C ）Ａ． 6 Ｂ．8 Ｃ．9 Ｄ．129、一棵树有2个4度顶点，3个3度顶点，其余是树叶，则该树中树叶的个数是（ B ）A.8B.9C.10D.1110、代数系统<Ａ，＊>的零元素Ｚｔ的定义是( B )A.∀x∈A,∃Ｚｔ∈A,x*Ｚｔ=Ｚｔ*x=xB.∀x∈A,∃Ｚｔ∈A,x*Ｚｔ=Ｚｔ*x=ＺｔC.∃Ｚｔ∈A, ∀x∈A,x*Ｚｔ=Ｚｔ*x=xD.∃Ｚｔ∈A, ∀x∈A,x*Ｚｔ=Ｚｔ*x=Ｚｔ11、在自然数集合Ｎ上，下列定义的运算中可结合的只有（ C ）A a*b=∣a-b∣B a*b=a+2bC a*b=max(a,b)D a*b=a b12、在下列代数系统中，不是群的只有（ D ）A．〈Ｑ，＋〉，这里Ｑ为有理数集，＋为加法运算B．〈Ｒ，＊〉，这里Ｒ为非零实数集，＊为乘法运算C．全体ｎ×ｎ实对称矩阵集合，对于矩阵的加法运算D ．〈Ｑ，＊〉，这里Ｑ为有理数集，＊为乘法运算13、设G = {0，1，2，3}，⨯4为模4乘法，则G 中的2阶元是（ ）。

离散习题代数系统部分答案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。