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

P F F T T Q F T F T P↔Q T F F T
每当Ｐ和Ｑ的真值相同时，则（Ｐ↔Ｑ）的真值 为“Ｔ”，否则（Ｐ↔Ｑ）的真值为“Ｆ”。
（３）举例：
▪ 春天来了当且仅当燕子飞回来了。 ▪平面上二直线平行，当且仅当这二直线不相交。 ▪２＋２＝４当且仅当雪是白色的。 （两者没有关系，但是确实命题）
举例： （a）P：王华的成绩很好 Q：王华的品德很好。 则ＰΛＱ：王华的成绩很好并且品德很好。 （b P：我们去种树 Q：房间里有一台电视机 则ＰΛＱ：我们去种树与房间里有一台电视机。 (c) P：今天下大雨 Q：3+3=6 则ＰΛＱ：今天下大雨和3+3=6
３．析取词（或运算） （１）符号“∨” 设Ｐ、Ｑ为二个命题，则 （Ｐ∨Ｑ）称作Ｐ与Ｑ的“析取”，读作： “Ｐ或Ｑ”。
（a）P：我拿起一本书 Q：我一口气读完了这本书 P→Q：如果我拿起一本书，则我一口气读完了这本书。 （b）P：月亮出来了 Q：3×3=9 P→Q：如果月亮出来了，则 3×3=9。（善意推定）
５．双条件联结词（“等价”词、“同”联结词、 “等同”词） （１）符号“↔”设Ｐ、Ｑ为二个命题，则Ｐ↔ Ｑ读作：“Ｐ当且仅当Ｑ”，“Ｐ等价 Ｑ”,“Ｐ是Ｑ的充分必要条件”。 （２）定义（见真值表）：
（４）Ｐ,Ｑ中，Ｐ、Ｑ的地位是平等的，Ｐ、Ｑ 交换位置不会改变真值表中的值。
６．命题联结词在使用中的优先级 （１）先括号内，后括号外 （２）运算时联结词的优先次序为： ¬ Λ → ↔ （由高到低） （３）联结词按从左到右的次序进行运算
∨
¬Ｐ∨（Ｑ∨Ｒ）可省去括号，因为“Ｖ”运算是可结合的。 （ ¬Ｐ∨Ｑ）∨Ｒ可省去括号，因为符合上述规定 而Ｐ→（Ｑ→Ｒ）中的括号不能省去，因为“→”不满足结合律。

参考答案试卷一一、选择填空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。

离散数学考试试题（A卷及答案）一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？(1)若A去，则C和D中要去1个人；(2)B和C不能都去；(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。

则根据题意应有：A→C⊕D，⌝(B ∧C)，C→⌝D必须同时成立。

因此(A→C⊕D)∧⌝(B∧C)∧(C→⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧(⌝B∨⌝C)∧(⌝C∨⌝D)⇔(⌝A∨(C∧⌝ D)∨(⌝C∧D))∧((⌝B∧⌝C)∨(⌝B∧⌝D)∨⌝C∨(⌝C∧⌝D))⇔(⌝A∧⌝B∧⌝C)∨(⌝A∧⌝B∧⌝D)∨(⌝A∧⌝C)∨(⌝A∧⌝C∧⌝D)∨(C∧⌝ D∧⌝B∧⌝C)∨(C∧⌝ D∧⌝B∧⌝D)∨(C∧⌝ D∧⌝C)∨(C∧⌝ D∧⌝C∧⌝D)∨(⌝C∧D∧⌝B∧⌝C)∨(⌝C∧D∧⌝B∧⌝D)∨(⌝C∧D∧⌝C)∨(⌝C∧D∧⌝C∧⌝D)⇔F∨F∨(⌝A∧⌝C)∨F∨F∨(C∧⌝ D∧⌝B)∨F∨F∨(⌝C∧D∧⌝B)∨F∨(⌝C∧D)∨F⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D∧⌝B)∨(⌝C∧D)⇔(⌝A∧⌝C)∨(⌝B∧C∧⌝ D)∨(⌝C∧D)⇔T故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。

S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：∀x(S(x)∧W(x))，∃x Y(x)∃x(S(x)∧Y(x))下面给出证明：(1)∃x Y(x) P(2)Y(c) T(1)，ES(3)∀x(S(x)∧W(x)) P(4)S( c)∧W( c) T(3)，US(5)S( c) T(4)，I(6)S( c)∧Y(c) T(2)(5)，I(7)∃x S((x)∧Y(x)) T(6) ，EG三、（10分）设A、B和C是三个集合，则A⊂B⇒⌝(B⊂A)。

(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校
(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校
答：（1） Q P （2） P Q （3） P Q （4） P Q
8、设个体域为整数集，则下列公式的意义是( )。
(1) xy(x+y=0) (2) yx(x+y=0)
答：2 不是偶数且-3 不是负数。
12、永真式的否定是（ ）
(1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
答：（2）
13、公式( P Q) ( P Q)化简为（
），公式 Q (P (P Q))可化简为
（ ）。
答： P ，Q P
14、谓词公式x(P(x) yR(y)) Q(x)中量词x 的辖域是（ ）。
(5) 前进！
(6) 给我一杯水吧！
答：（1） 是，T （4） 是，T
（2） 是，F （5） 不是
（3） 不是 （6） 不是
6、命题“存在一些人是大学生”的否定是(
)，而命题“所有的人都是要
死的”的否定是(
)。
答：所有人都不是大学生，有些人不会死
1
7、设 P：我生病，Q：我去学校，则下列命题可符号化为( )。
R (2) R-1 。
答：（1）R={<1,1>,<4,2>} (2) R 1 ={<1,1>,<2,4>}
29、举出集合 A 上的既是等价关系又是偏序关系的一个例子。( )
答：A 上的恒等关系
30、集合 A 上的等价关系的三个性质是什么？(
)
答：自反性、对称性和传递性
31、集合 A 上的偏序关系的三个性质是什么？(

北京科技大学远程教育学院《离散数学》综合练习(一)参考答案数理逻辑一、判断下列句子是否是命题，若是命题判断真值，并将其符号化。

1、今天天气真好！解：不是命题。

2、王华和张民是同学。

解：是命题。

真值视实际情况而定。

p：王华和张民是同学。

3、我一边吃饭，一边看电视。

解：是命题。

真值视实际情况而定。

p：我吃饭。

q：我看电视。

p∧q 4、没有不呼吸的人。

解：是命题。

真值为1。

M(x)：x是人。

F(x)：x呼吸。

∀x(M(x)→F(x))二、求命题公式的真值表和成真赋值、成假赋值。

p→∧qr∧→(p])[(r)解：成真赋值：000，001，010，011，101，111；成假赋值100，110三、用真值表、等值演算两种方法判别公式类型。

1、r q q p →∧→])[( 解：rq q p r q q q p r q q p rq q p r q q p r q q p ∨⌝∧⌝∨⇔∨⌝∨⌝∧⌝∨⇔∨⌝∨⌝∧⇔∨⌝∨∨⌝⌝⇔∨∧∨⌝⌝⇔→∧→])[()]()[()()(])[(])[(可满足式2、))((p q p q ∧∨⌝⌝∨ 解：))((p q p q A ∧∨⌝⌝∨=1)()()())((⇔∨⌝∨∨⌝⌝⇔⌝∨∨⌝⌝∨⇔∧∨⌝⌝∨q p q p p q p q p q p q永真式四、求命题公式的主析取范式和成真赋值、成假赋值。

)(r q p →→ 解：∑=→→），，，，，，7543210()(r q p 成真赋值：000，001，010，011，100，101，111；成假赋值110 五、解释I 如下：D 是实数集，特定元素a =0；特定函数f (x ，y )=x -y ；特定谓词F (x ，y )：x<y 。

在解释I 下判别公式真、假。

1、)])(([x y x f F y x ，，⌝∀∀ 解：)])[()])(([)]([)])(([x y x y x x y x y x x y x F y x x y x f F y x ≥-∀∀⇔<-⌝∀∀⇔-⌝∀∀⇔⌝∀∀，，，真值为假2、)]()([)({z y f z x f F y x F z y x ，，，，→∀∀∀ 解：)]()()[()]}()([)({z y z x y x z y x z y f z x f F y x F z y x -<-→<∀∀∀⇔→∀∀∀，，，，真值为真 六、1、求前束范式)()(y x yG x xF ，∀→⌝∃ 解：)]()([)()()()()()(y t G x F y x y t yG x xF y x yG x xF y x yG x xF ，，，，∨∀∃⇔∀∨∃⇔∀∨∃⇔∀→⌝∃2、证明：B x xA B x A x →∀⇔→∃)())(( 证明：Bx xA Bx xA B x A x B x A x B x A x →∀⇔∨⌝∀⇔∨⌝∃⇔∨⌝∃⇔→∃)()()())(())((七、写出下面推理的证明，要求写出前提、结论，并注明推理规则。

离散数学习题答案离散数学习题答案习题⼀及答案：（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 ?∨p 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。

离散数学习题解代数系统习题四 第四章代数系统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 上的一个二元运算。

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( )A.汉密尔顿回路B.欧拉回路C.汉密尔顿通路D.初级回路2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( )A.10B.12C.16D.143.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( )A.b∧(a∨c)B.(a∧b)∨(a’∧b)C.(a∨b)∧(a∨b∨c)∧(b∨c)D.(b∨c)∧(a∨c)4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( )A.<{1},·>B.〈{-1},·〉C.〈{i},·〉D.〈{-i},·〉5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运算，下列系统中是代数系统的有( )A.〈Z，+，/〉B.〈Z，/〉C.〈Z，-，/〉D.〈P(A)，∩〉6.下列各代数系统中不含有零元素的是( )A.〈Q，*〉Q是全体有理数集，*是数的乘法运算B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C.〈Z， 〉，Z是整数集， 定义为x xy=xy,∀x,y∈ZD.〈Z，+〉，Z是整数集，+是数的加法运算7.设A={1,2,3}，A上二元关系R的关系图如下：R具有的性质是A.自反性B.对称性C.传递性D.反自反性8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( )A.R∪I AB.RC.R∪{〈c,a〉}D.R∩I A9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的等价关系，R应取( )A.｛〈c,a〉，〈a,c〉｝B.{〈c,b〉，〈b,a〉}C.{〈c,a〉，〈b,a〉}D.{〈a,c〉，〈c,b〉}10.下列式子正确的是( )A. ∅∈∅B.∅⊆∅C.{∅}⊆∅D.{∅}∈∅11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x<y.下列公式在R下为真的是( )A.( ∀x)( ∀y)( ∀z)(A(x,y))→A(f(x,z),f(y,z))B.( ∀x)A(f(a,x),a)C.(∀x)(∀y)（A(f(x,y),x))D.(∀x)(∀y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(∀x)(A(x)→B)等价于( )A.(∃x)A(x)→BB.(∀x)A(x)→BC.A(x)→BD.(∀x)A(x)→(∀x)B13.谓词公式(∀x)(P(x,y))→(∃z)Q(x,z)∧(∀y)R(x,y)中变元x( )A.是自由变元但不是约束变元B.既不是自由变元又不是约束变元C.既是自由变元又是约束变元D.是约束变元但不是自由变元14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )A.P∨QB.P∧┐QC.P→┐QD.P∨┐Q15.以下命题公式中，为永假式的是( )A.p→(p∨q∨r)B.(p→┐p)→┐pC.┐(q→q)∧pD.┐(q∨┐p)→(p∧┐p)二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。

第十章
15、17、18、21、22、24、27、28、29。
2
15、设 G 为群，若 x ∈G 有 x =e, 证明 G 为交换群 证明： a, b ∈G 由条件 x ∈G 有 x =e
2
所以 a =e ,b =e (ab) =e ,即(ab)(ab)=e 所以 a =a, b =b, ba= a b
下面证明 φ(G1)是是循环群 y∈f(G1), x ∈G1 , 使得 f(x)=y. 而 G1=<a> 所以 存在 r 使得 x= a
r r
则 y = f(x) = f(a ) = f(a)f(a)……f(a) =(f(a)) 这证明了 f(a)为 f(G1)的生成元。即 f(G1)=< f(a)> 所以 f(G1)为循环群。 28、设 G=<a>是 15 阶循环群。 (1) 求出 G 的所有的生成元。 (2) 求出 G 的所有子群。 解：(1) 生成元为: a,a ,a ,a ,a ,a ,a ,a (2) G 的所有子群: 共 4 个子群 <e>, <a >={e,a ,a ,a ,a },
-1 -1
21、设 G 为群，a 是 G 中给定元素，a 的正规化子 N(a)表示 G 中与 a 可交换的元素构成的集合，即 N(a)={x| x∈G∧xa=ax } 证明：N(a)是 G 的子群 证明: (1) a∈N(a), 所以 N(a)非空(因为 a∈G∧aa=aa) (2) x,y ∈N(a) 则 xa=ax ya=ay
-1
-1
-1
=-a
-1 -1
-1
(2) 由于 (ab)(b a )= a(bb )a = aa = 1 所以 (ab)