离散数学习题与解答

作业题与解答第一章19 、4)、6) 21 1、2)、3)19、2)解答: p→┐p→┐q真值表如下:pq┐p┐qp→┐pp→┐p→┐q00111101101010010111000119、4)

所以公式p→┐q→┐q为可满足式解答: p→q)→┐q→┐p)真值表如下:pq┐p┐qp→q┐q→┐pp→q→┐q→┐p)0011111011011110010011100111所以公式p→q→┐q→┐p为永真式19、6解答: p→q∧q→r))→p→r)真值表如下:pqrp→qq→rp→rp→q∧q→r)p→q∧q→r))→p→r)0001111100111111010101010111111110001001101011011101000111111111所以公式p→q∧q→r)→(p→r为永真式21、1解答: ┐┐p∧q∨┐r真值表如下:pqr┐p┐r┐p∧q┐┐p∧q)┐┐p∧q∨┐r0001101100110011010111010111010010001011101000111100101111100011所以成假赋值为0121、2)解答: ┐q∨r∧p→q真值表如下:pqr┐q┐q∨rp→q┐q∨r∧p→q)00011110011111010001001101111001100101110011000101110111所以成假赋值为010101011021、3解答: p→q∧┐(p∧r∨p真值表如下:pqrp→qp∧r┐p∧r)┐p∧r∨pp→q∧┐p∧r∨p)0001011100110111010101110111011110000110101010101101011111111011所以成假赋值为10011第二章 5、1)2)3) 6、1)2)3) 7、1)2) 8、1)2)3)5、求下列公式的主析取范式并求成真赋值1) ┐p→q→┐q∨p)┐┐p→q)∨(┐q∨p)┐┐┐p)∨q)∨┐q∨p)┐p∧┐q)∨┐q∨p)┐p∧┐q)∨p∧┐q∨p∧q)0∨m2∨3，所以00，10，1为成真赋值。2) (┐p→q∧q∧r)┐┐p∨q∧q∧r)p∨q∧q∧r)p∧q∧r∨q∧r)p∧q∧r∨p∧q∧r∨┐p∧q∧r)p∧q∧r∨┐p∧q∧r)3∨m7，所以01，1为成真赋值。3) p∨q∧r)→p∨q∨r)┐p∨q∧r)∨(p∨q∨r)┐p∧┐q∨┐r∨p∨q∨r)┐p∧┐q∨┐p∧┐r∨p∨q∨r)┐p∧┐q∨┐p∧┐r∨p∨q∨r)┐p∧┐q∨┐p∨p∨q∨r∧(┐r∨p∨q∨r))┐p∧┐q∨1∧1)┐p∧┐q∨110∨1∨m2∨3∨4∨5∨m6∨m7，所以000,001,00,01,100,11,10,1为成真赋值。7、求下列公式的主析取范式，再用主析取范式求主合取范式1) p∧q∨r(p∧q∧r∨(p∧q∧┐r∨p∧r∨┐p∧r)(p∧q∧r∨(p∧q∧┐r∨p∧r∧q∨p∧r∧┐q)∨┐p∧r∧q)∨┐p∧r∧┐q)(p∧q∧r∨(p∧q∧┐r∨p∧┐q∧r∨┐p∧q∧r)∨┐p∧┐q∧r)1∨3∨5∨6∨7由主析取范式和主合取范式之间的关系，所以公式的主合取范式为：p∧q∨rM0∧M2∧M42)(p→q)∧(q→r)┐p∨q∧┐q∨r)┐p∧┐q∨r∨q∧┐q∨r)┐p∧┐q∨┐p∧r∨(q∧┐q∨q∧r)┐p∧┐q∨(┐p∧r∨q∧r)┐p∧┐q∧┐r∨┐p∧┐q∧r)∨┐p∧q∧r)∨┐p∧┐q∧r)∨p∧q∧r∨┐p∧q∧r)┐p∧┐q∧┐r∨┐p∧┐q∧r)∨┐p∧q∧r)∨p∧q∧r)0∨1∨3∨7由主析取范式和主合取范式之间的关系，所以公式的主合取范式为：(p→q)∧(q→r)M2∧M4∧M∧M68、求下列公式的主合取范式，再用主合取范式求主析取范式(1)(p∧q)→q┐p∧q∨q┐p∨┐q∨q┐p∨┐q∨q)┐p∨11该公式无主合取范式，所以公式的主析取范式为：(p∧q)→q0∨1∨2∨3(2)(pq)→r┐┐p∨q∧p∨┐q)∨rp∧┐q)∨┐p∧q∨rp∨┐p∧q)∧(┐q∨┐p∧q)∨rp∨┐p)∧(p∨q∧(┐∨┐p∧(┐q∨∨r(p∨q∧(┐q∨┐p∨r(p∨q∨r∧(┐p∨┐q∨r)M0∧M6由主合取范式和主析取范式之间的关系，所以公式的主析取范式为：(pq)→r1∨2∨3∨4∨5∨7(3)┐r→p∧p∧q┐┐r∨p∧p∧qr∧┐p∧p∧qr∧┐p∧p∧qr∧0∧q0M0∧M1∧M2∧M3∧M∧M5∧M6∧M7该公式无主析取范式第三章 14 2、4、5) 15 1、2) 16 1)14、在自然推理系统P中构造下面推理的证明(2)前提：p→q,┐(q∧r),r结论：┐p证明：①┐(q∧r) 前提引入②┐q∨┐r ①置换③r 前提引入④┐q ②③析取三段论⑤p→q 前提引入⑥┐p ④⑤拒取式（4）前提：q→p,q s,s t,t∧r结论：p∧q证明：①s t 前提引入②(s→t)∧(t→s) ①置换③t→s ②化简④t∧r 前提引入⑤t ④化简⑥s ③⑤假言推理⑦q s 前提引入⑧(s→q)∧(q→s) ⑦置换⑨s→q ⑧化简⑩q ⑥⑨假言推理q→p 前提引入p ⑩假言推理p∧q ⑩合取（5）前提：p→r,q→s,p∧q结论：r∧s证明:①p∧q 前提引入②p ①化简③q ①化简④p→r 前提引入⑤r ②④假言推理⑥q→s 前提引入⑦s ③⑥假言推理⑧r∧s ⑤⑦合取15、在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p→(q→r),s→p,q结论：s→r证明：①s 附加前提引入②s→p 前提引入③p ①②假言推理④p→(q→r)前提引入⑤q→r ③④假言推理⑥q 前提引入⑦r ⑤⑥假言推理(2)前提：(p∨q)→(r∧s),(s∨t)→u结论：p→u证明：①p 附加前提引入②p∨q ①附加③(p∨q)→(r∧s) 前提引入④r∧s ②③假言推理⑤s ④化简⑥s∨t ⑤附加⑦(s∨t)→u 前提引入⑧u ⑥⑦假言推理16、在自然推理系统P中用归谬法证明下面推理：(1)前提：p→┐q,┐r∨q,r∧┐s结论：┐p证明:①p 结论否定引入②p→┐q 前提引入③┐q ①②假言推理④┐r∨q 前提引入⑤┐r ③④析取三段论⑥r∧┐s 前提引入⑦r ⑥化简⑧┐r∧r ⑤⑦合取(矛盾)⑧为矛盾式，由归谬法可知，推理正确。第四章 5、(1)(2)(3)(4) 10、(2)(4) 11、(2)(6)5、在一阶逻辑中将下列命题符号化：(1)火车都比轮船快。xy(F(x)∧G(y)→H(x,y))，其中，F(x)：x是火车，G(y)：y是轮船，H(x,y):x比y快。(2)有的火车比有的汽车快。xy(F(x)∧G(y)∧H(x,y))，其中，F(x):x是火车，G(y)：y是汽车，H(x,y):x比y快。(3)不存在比所有火车都快的汽车。┐x(F(x)∧y(G(y)→H(x,y)))或x(F(x)→y(G(y)∧┐H(x,y)))，其中，F(x):x是汽车，G(y)：y是火车，H(x,y):x比y快。(4)说凡是汽车就比火车慢是不对的。┐xy(F(x)∧G(y)→H(x,y))或xy(F(x)∧G(y)∧┐H(x,y))，其中，F(x):x是汽车，G(y)：y是火车，H(x,y):x比y慢。10、给定解释I如下：（a）个体域D=N（N为自然数）。（b）D中特定元素=2。（c）D上函数(x,y)=x＋y，(x,y)=x·y。D上谓词(x,y)：x=y。(2)xy(F(f(x,a),y)→F(f(y,a),x))xy((x+2=y)→(y+2=x))，真值为0。(4)xF(f(x,x),g(x,x))x(x+x=x·x),真值为1。11、判断下列各式的类型(2)x(F(x)→F(x))→y(G(y)∧┐G(y)))此谓词公式前件永为真，而后件永为假，即公式为(1→0),此公式为矛盾式，所以原谓词公式为矛盾式。(6)┐(xF(x)→yG(y))∧yG(y)此谓词公式是命题公式┐(p→q)∧q的代换实例而该命题公式是矛盾式，所以此谓词公式是矛盾式。第五章 15(1)(2)(3)(4) 20(1)(2) 23(1)(2)15、在自然推理系统F中构造下面推理的证明：(1)前提:xF(x)→y((F(y)∨G(y))→R(y)),xF(x)结论：xR(x)证明：①xF(x)→y((F(y)∨G(y))→R(y))(前提引入)②xF(x) (前提引入)③y((F(y)∨G(y))→R(y)) (①②假言言推理)④F(c) (②EI规则)⑤F(c)∨G(c)→R(c) (③UI规则⑥F(c)∨G(c) (④附加律)⑦R(c) (⑤⑥假言言推理)⑧xR(x) (⑦EG规则)(2)前提：x(F(x)→(G(a)∧R(x)))，xF(x)结论：x(F(x)∧R(x))证明：①xF(x) 前提引入②F(c) ①-③x(F(x)→(G(a)∧R(x))) 前提引入④F(c)→(G(a)∧R(c)) ④-⑤G(a)∧R(c) ②④假言推理⑥R(c) ⑤化简⑦F(c)∧R(c) ②⑥合取⑧x(F(x)∧R(x)) ⑥+(3)前提：x(F(x)∨G(x))，┐xG(x)结论：xF(x)证明:①┐xx) 前提引入②x┐x) ①置换③┐c) ②-④xx∨x)

前提引入⑤c∨c) ④-⑥c) ③⑤析取三段论⑦xx) ⑥+(4)前提:x(F(x)∨G(y)),x(┐G(x)∨┐R(x)),xR(x)结论：xF(x)证明：①xR(x) 前提引入②R(c) ①-③x(┐G(x)∨┐R(x)) 前提引入④┐G(c)∨┐R(c) ③-⑤┐G(c) ②④析取三段论⑥x(F(x)∨G(y)) 前提引入⑦F(c)∨G(c) ⑥-⑧F(c) ⑤⑦析取三段论⑨xx) ⑧+20、在自然推理系统F中，构造下面推理的证明：(可以使用附加前提证明法)(1)前提：x(F(x)→G(x))结论：xF(x)→xG(x)证明：①xF(x) 附加前提②F(y) ①-③x(F(x)→G(x)) 前提引入④F(y)→G(y) ③-⑤G(y) ②④假言推理⑥xG(x) ⑤+(2) 前提：x(F(x)∨G(x))结论：┐xF(x)→xG(x)证明：①┐xF(x) 附加前提②x┐F(x) ①等值演算③┐F(c) ②-④x(F(x)∨G(x)) 前提引入⑤F(c)∨G(c) ④-⑥G(c) ③⑤析取三段论⑦xG(x) ⑥+23、在自然推理系统F中，证明下面推理：(1)每个有理数都是实数，有的有理数是整数，因此有的实数是整数。设F(x):x为有理数，R(x):x为实数，G(x):x是整数。前提：x(F(x)→R(x))，x(F(x)∧G(x))结论：x(R(x)∧G(x))证明：①x(F(x)∧G(x)) 提引入②F(c)∧G(c) ①-③F(c) ②化简④G(c) ②化简⑤x(F(x)→R(x)) 前提引入⑥F(c)→R(c) ⑤-⑦R(c) ③⑥假言推理⑧R(c)∧G(c) ④⑦合取⑨x(R(x)∧G(x)) ⑧+(2)有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不是无理数。设：F(x):x为有理数，G(x):x为无理数，R(x)为实数，H(x)为虚数前提：x((F(x)∨G(x))→R(x)),x(H(x)→┐R(x))结论：x(H(x)→(┐F(x)∧┐G(x)))证明：①x((F(x)∨G(x)→R(x)) 前提引入②F(y)∨G(y))→R(y) ①-③x(H(x)→┐R(x)) 前提引入④H(y)→┐R(y)③-⑤⑥⑦⑧┐R(y)→┐(F(y)∨G(y))H(y)→┐(F(y)∨G(y))H(y)→(┐F(y)∧┐G(y))x(H(x)→(┐F(x)∧┐G(x)))②置换④⑤假言三段论⑥置换⑦+第六章 31，32、(1)(2)(3)，41，42，4531、设A、B为任意集合，证明：(A-B)∪(B-A)=(A∪B)-(A∩B)证明：由于(A-B)∪(B-A)=(A∩～B)∪(B∩～A)=((A∩～B)∪B)∩((A∩～B)∪～A)=((A∪B)∩(～B∪B))∩((A∪～A)∩(～B∪～A))=(A∪B)∩(～B∪～A)=(A∪B)∩～(B∩A)=(A∪B)∩～(A∩B)=(A∪B)-(A∩B)所以原式成立。32、设A、B、C为任意集合，证明：（1）(A-B)-C=A-(B∪C)证明：由于(A-B)-C=(A∩～B)∩～C=A∩(～B∩～C)=A∩～(B∪C)=A–(B∪C) 所以原式成立。（2）(A-B)-C=(A-C)-(B-C)证明：由于(A-C)-(B-C)=(A∩～C)∩～(B∩～C)=(A∩～C)∩(～B∪C)=((A∩～C)∩～B)∪((A∩～C)∩C)=(A∩～C)∩～B=(A∩～B)∩～C=(A-B)∩～C=(A-B)-C 所以原式成立。（3）(A-B)-C=(A-C)-B证明: 由于(A-B)-C=(A∩～B)∩～C=(A∩～C)∩～B=(A-C)-B所以原式成立。41、设A、B、C为任意集合，证明：A∩CB∩C∧A-CB-C AB证明：x∈A(1)若x∈C则则x∈A∩C，而A∩CB∩C所以x∈B∩C因此x∈B(2)若xC则x∈A-C，而A-CB-C所以x∈B-C因此x∈B综上所述，AB42、设A、B、C为任意集合，证明：A∪B=A∪C ∧ A∩B=A∩C B=C证明：(1)先证 BCx∈B①若x∈A则x∈A∩B，而A∩B=A∩C所以x∈A∩C因此x∈C②若xA则则x∈A∪B，而A∪B=A∪C所以x∈A∪C因此x∈C综上所述知BC(2)再证CB 同理可证所以B=C45、设A、B为任意任意集合，证明：(1)P(A)∩P(B)=P(A∩B)(2)P(A)∪P(B)P(A∪B)(3)针对(2)举一反例，说明P(A)∪P(B)=P(A∪B)对某些集合A和B是不成立的。证明：(1)①先证 P(A)∩P(B)P(A∩B)x∈P(A)∩P(B)则x∈P(A) ∧x∈P(B)所以xA∧xB所以xA∩B所以x∈P(A∩B)因此P(A)∩P(B)P(A∩B)②②再证P(A∩B)P(A)∩P(B)x∈P(A∩B)则xA∩B所以xA∧xB所以x∈P(A) ∧x∈P(B)所以x∈P(A)∩P(B)因此P(A∩B)P(A)∩P(B)综上所述P(A∩B)=P(A)∩P(B)(2)x∈P(A)∪P(B)则x∈P(A) ∨x∈P(B)所以xA∨xB①若xA则xA∪B所以x∈P(A∪B)②若xB则xA∪B所以x∈P(A∪B)因因此P(A)∪P(B)P(A∪B)(3)举例：令A={1},B={2}则A∪B={1，2}则P(A)={，{1}}，P(B)={，{2}}而P(A∪B)={，{1},{2},{1,2}}显然P(A)∪P(B)=P(A∪B)不成立.第七章 20、25、32、36、38、40、41、42、48、49、5020、设R1的R2为A上的关系，证明:2-1(1)(R1∪R22-1

=R1

-∪R-1-111()(R1∩-111

=R1

∩R2-1证明:(1)<x,y>∈(R1∪R2-1<y,x>∈R1∪R2<y,x>∈R1∨<y,x>∈R22<x,y>∈R12

-1∨<x,y>∈R-1-1-1<x,y>∈-1-1

∪R2-1-11所以(R1∪-1-11

=R1

∪R2-1(2)<x,y>∈(R1∩R2-1<y,x>∈R1∩R2<y,x>∈R1∧<y,x>∈R22<x,y>∈R12

-1∧<x,y>∈R-1-1-1<x,y>∈-1-1

∩R2-1-11所以(R1∩-1-11

=R1

∩R225设R的关系图如图所示，试给出r(R),s(R),t(R)的关系图a b d ecR系图解：a b d ecR)关图a b d ecR)关图a b d ecR)关图32、对于给的A和R，判断R是否为A上的等价关系。(1)A为为实数集，x,y∈A,xRy x-y=2.解:R不是A上的等价关系，因为R不自反.(2)A={1,2,3},x,y∈A,xRy x+y≠3解:R不是A上的等价关系，因为R不传递.(3)A=Z+,即正整数集，x,y∈A,xRy xy是奇数。解:R不是A上的等价关系，因为R不自反.(4)A=P(X),|X|≥2,x,y∈A,xRyxy∨yx解:R不是A上的等价关系，因为R不传递.(5)A=P(X),CX,x,y∈A,xRyx⊕yC解:R是A上的等价关系.36、设A={1，2，3，4}，在A×A上定义二元关系R<u,v>,<x,y>∈A×A,<u,v>R<x,y>u+y=x+v(1)证明R是A×A上的等价关系。(2)确定由R引起的对A×A的划分。证明：(1)①先证R具有自反性<x,y>∈A×A由于x+y=x+y再根据R的定义知<<x,y>,<x,y>>∈R所以R具有自反性.②再证R具有对称性<u,v>,<x,y>∈A×A,若<<u,v>,<x,y>>∈R则由R的定义知：u+y=x+v所以x+v=u+y再由R的定义知<<x,y>,<u,v>>∈R所以R具有对称性.③再证R具有传递性<u,v>,<x,y>,<s,t>∈A×A,若<<u,v>,<x,y>>∈R并且<<x,y>,<s,t>>∈R则由R的定义知：u+y=x+v并且x+t=s+y根据上述两式知:u+t=s+v再根据R的定义知<<u,v>,<s,t>>∈R所以R具有传递性。综上所述R为A×A上的等价关系。(2)A×A/R={{<1,4>},{<1,3>,<2,4>},{<1,2>,<2,3>,<3,4>},{<1,1>,<2,2>,<3,3>,<4,4>},{<2,1>,<3,2>,<4,3>},{<3,1>,<4,2>},{<4,1>}}38、设R为A上的自反和传递的关系，证明R∩R-1是A上的等价关系。证明：①先证R∩R-1具有自反性x∈A由于R为A上的自反关系所以<x,x>∈R,再由逆关系的定义知<x,x>∈R-1所以<x,x>∈R∩R-1因此R具有自反性。②再证R∩R-1具有对称性<x,y>∈R∩R-1所以<x,y>∈R并且<x,y>∈R-1由逆关系的定义知<y,x>∈R-1并且<y,x>∈R所以<y,x>∈R-∩R即<y,x>∈R∩R-1所以R具有对称性。③再证R具有有传递性x,y,z∈A，并且<x,y>,<y,z>∈R∩R-1所以<x,y>∈R并且<x,y>∈R-1并且<y,z>∈R并且<y,z>∈R-1所以<x,y>∈R并且<y,x>∈R并且<y,z>∈R并且<z,y>∈R由R的传递性知<x,z>∈R并且<z,x>∈R所以<x,z>∈R并且<x,z>∈R-1所以<x,z>∈R∩R-1所以R∩R-1具有传递性。综上所述知R∩R-1为A上的等价关系。40、设R为N×N上的二元关系，<a,b>,<c,d>∈N×N<a,b>R<c,d>b=d(1)证明R为等价关系(2)求商集N×N/R证明：(1)①先证R具有自反性<a,b>∈N×N因为b=b由R的定义知<a,b>R<a,b>所以R具有自反性。②再证R具有对称性<a,b>,<c,d>∈N×N，若<a,b>R<c,d>由R的定义知b=d再由R的定义知<c,d>R<a,b>所以R具有对称性。③再证R具有传递性<a,b>,<c,d>，<e,f>∈N×N，若<a,b>R<c,d>并且<c,d>R<e,f>由R的定义知b=d,d=f所以b=f再由R的定义知<a,b>R<e,f>所以R具有传递性综上所述知R为N×N上的等价关系。(2)N×N/R={{<0,0>,<1,0>,<2,0>,<3,0>…},{<0,1>,<1,1>,<2,1>,<3,1>…},{<0,2>,<1,2>,<2,2>,<3,2>…},…………………}41、设A={1，2，3，4}，在A×A上定义二元关系R<a,b>,<c,d>∈A×A,<a,b>R<c,d>a+b=c+d(1)证明R为等价关系。(2)求R导出的划分。证明：(1)①先证R具有自反性<a,b>∈A×A由于a+b=a+b再根据R的定义知<<a,b>,<a,b>>∈R所以R具有自反性.②再证R具有对称性<a,b>,<c,d>∈A×A,若<<a,b>,<c,d>>∈R则由R的定义知：a+b=c+d所以c+d=a+b再由R的定义知<<c,d>,<a,b>>∈R所以R具有对称性.③再③再证R具有传递性<a,b>,<c,d>,<e,f>∈A×A,若<<a,b>,<c,d>>∈R并且<<c,d>,<e,f>>∈R则由R的定义知：a+b=c+d并且c+d=e+f根据上述两式知:a+b=e+f再根据R的定义知<<a,b>,<e,f>>∈R所以R具有传递性。综上所述R为A×A上的等价关系。(2)A×A/R={{<1,1>},{<2,1>,<1,2>},{<3,1>,<2,2>,<1,3>},{<4,1>,<3,2>,<2,3>,<1,4>},{<4,2>,<3,3>,<2,4>},{<4,3>,<3,4>},{<4,4>}}42、设R是A上的自反和传递关系，如下定义A上的关系T，使得x,y∈A <x,y>∈T<x,y>∈R∧<y,x>∈R证明：T是A上的等价关系。证明：①先证T具有自反性x∈A由于R是A上自反关系所以所以<x,x>∈R即<x,x>∈R∧<x,x>∈R由T的定义知：<x,x>∈T所以T具有自反性②再证T具有对称性x,y∈A,若<x,y>∈T由T的定义知：<x,y>∈R∧<y,x>∈R即<y,x>∈R∧<x,y>∈R再由T的定义知：<y,x>∈T所以T具有对称性③再证T具有传递性x,y，z∈A,若<x,y>∈T∧<y,z>∈T由T的定义知：<x,y>∈R∧<y,x>∈R并且<y,z>∈R∧<z,y>∈R再由R具有传递性知:<x,z>∈R∧<z,x>∈R再根据T的定义知:<x,z>∈T所以T具有传递性。综上所述知T为A上的等价关系。48、设<A，R>和<B，S>为偏序集，在集合A×B上定义关系T如下：<a1,b1>,<a2,b2∈A×B,<a1,b1>T<a2,b2>a1Ra2∧b1Sb2证明：T为A×B上的偏序关系证明：①先证T具有自反性<a1,b1>∈A×B所以a1∈A并且b1∈B由于R和S分别是A和B上的偏序关系,所以R和S具有自反性所以a1Ra1∧b1Sb1由T的定义知:<a1,b1>T<a1,b1>所以T具有自反性。②再证T具有反对称性<a1,b1>,<a2,b2>∈A×B,若<a1,b1>T<a2,b2>并且<a2,b2>T<a1,b1>则由T的定义知:a1Ra2∧b1Sb2并且a2Ra1∧b2Sb1由于R和S是偏序关系，所以R和S反对称所以a1=a2并且b1=b2所以<a1,b1>=<a2,b2>因此T具有反对称性。③再证T具有传递性<a1,b1>,<a2,b2>，<a3,b>∈A×B,若<a1,b1>T<a2,b2>并且<a2,b2>T<a3,b3>由T的定义知:a1Ra2∧b1Sb2并且a2Ra3∧b2Sb3由于R和S是偏序关系,所以R和S具有传递性所以a1Ra3∧b1Sb3再由T的定义知:<a1,b1>T<a3,b3>所以T具有传递性。综上所述T为A上的偏序关系。49、设<A,R>为偏序集，在A上定义新的关系S如下：x,y∈A xSyxRy 称S为R的对偶关系(1)证明S也是A上的偏序关系。(2)如果R是整数集合上的小于或等于关系，那么S是什么关系？如果R是正整数集合上的整除关系，那么S是什么关系?(3)偏序集<A,R>和<A，S>中的极大元、极小元、最大元、最小元等之间有什么关系？证明：(1)①先证S具有自反性x∈A由于R具有自反性，所以<x,x>∈R由S的定义知：<x,x>∈S所以S具有自反性。②再证S具有反对称性x，y∈A,若<x,y>∈S并且<y,x>∈S那么由S的定义知：<y,x>∈R并且<x,y>∈R由于R是偏序关系，所以R具有反对称性所以x=y所以S具有反对称性。③再证S具有传递性x，y，z∈A,若<x,y>∈S并且<y,z>∈S由S的定义知：<y,x>∈R并且<z,y>∈R又因R为偏序关系，所以R具有传递性所以<z,x>∈R再由S的定义知：<x,z>∈S所以S具有传递性。综上所述S为A上的偏序关系。(2)如果R是整数集合上的小于或等于关系，那么S是A上的大于或等于关系。如果R是正整数集合上的整除关系，那么S是正整数集合上的倍数关系。(3)偏序集<A,R>极大元是<A，S>中的极小元，偏序集<A,R>极小元是<A，S>中的极大元、偏序集<A,R>最大元是<A，S>中的最小元，偏序集<A,R>最小元是<A，S>中的最大元。第八章 21、22、25、29、30、34、3521、设f:N→N×N,f(x)=<x,x+1>(1)说明f是否为单射和满射并说明理由；(2)f的反函数是否存在，如果存在，求出f的反函数；(3)求ranf解:(1)f为单射，证明如下：x1,x2∈N,若f(x1)=f(x2)则<x1,x1+1>=<x2,x2+1>根据有序对相等的概念知：x1=x2所以f为单射，但f不是满射，因为<00>ranf(2)f的反函数不存在(3)ranf={<n,n+1>|n∈N}22、设f:Z→Z，f(x)=(x)modn,在Z上定义等价关系R，x,y∈Z <xy>∈Rf(x)=f(y)(1)计算f(Z)；(2)确定商集Z/R解:(1)f(Z)={0，1，...,n-1}(2)Z/R={{nk+i|k∈Z}|i=0,1,...n-1}25、设f:R×R→R×R,f(<x,y>)=<(x+y)/2,(x-y)/2>证明f是双射证明：（1）先证f是单射<x,y>，<u,v>∈R×R,若f(<x,y>)=f(<u,v>)则<(x+y)/2,(x-y)/2>=<(u+v)/2,(u-v)/2>所以(x+y)/2=(u+v)/2(x-y)/2=(u-v)/2所以x=u,y=v所以<x,y>=<u,v>所以f为单射（2）再证f是满射<u,v>∈R×R存在<u+v,u-v>∈R×R且f<u+v,u-v>=<u,v>所以f为满射综上所述f为双射。29、设A=ab,c}B=2A由定义证明A≈2A证明:方法一:A={,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}2A={f,f

f,f,f,f,f,f}0 1 2

3 4 5 6 70={<a,0>,<b,0>,<c,0>} f1={<a,1>,<b,0>,<c,0>}2={<a,0>,<b,1>,<c,0>} f3={<a,0>,<b,0>,<c,1>}4={<a,1>,<b,1>,<c,0>} f5={<a,1>,<b,0>,<c,1>}f6={<a,0>,<b,1>,<c,1>} f7={<a,1>,<b,1>,<c,1>}如下构造双射函数ff()=f0,f({a})=f1,f({b})=f2,f({c})=f3,f({a,b})=f4,f({a,c})=f5,f({b,c})=f6,f({a,b,c})=f7,根据等势定义有A≈2A方法2证明：构造函数f:P(A)→2AA1∈P(A),f(A1)=x1可以证明f为一一映射。①先证f为单射A1，A2 ，若A1≠A2则存在元素x,x∈A1,且xA2或者xA1,且x∈A2不论那种情况，则x1,x2至少有一个元素对应不同。所以1≠2所以f为单射。②再证f为满射∈2A，则为A到{0，1}的函数，构造集合A3={x|x∈A∧(x)=1}显然A3∈P(A),且f(A3)=3=φ所以f为满射。所以f为一一映射，因此P(A)≈2A30、设[1,2]和[0,1]是实数区间，由定义证明[1,2]≈[0,1]证明：令f:[1,2]→[0,1],f(x)=x-1,而f为双射函数（显然成立）所以[1,2]≈[0,1]34、设A、B、C、D是集合，且A≈C,B≈D,证明:A×B≈C×D证明:由于A≈C，所以存在一一映射f。由于B≈D，所以存在一一映射g。构造A×B到C×D函数φ：A×B→C×D<x,y>∈A×B, φ(<x,y>)=<f(x),g(y)>显然<f(x),g(y)>∈C×D，下面证明φ为双射函数①先证φ为单射<x,y>,<u,v>∈A×B,若φ(<x,y>)=φ(<u,v>)即<f(x),g(y)>=<f(u),g(v)>所以f(x)=f(u)且g(y)=g(v)而f,g为一一映射，所以x=u且y=v所以<x,y>=<u,v>所以φ为单射②再证φ为满射<s,t>∈C×D则s∈C,t∈D由于f,g是一一函数，所以存在x∈A,y∈B,使得f(x)=s,g(y)=t显然<x,y>∈A×B,且φ(<x,y>)=<s,t>所以φ为满射。因此φ为双射函数。所以A×B≈C×D35、找出三个不同的N的真子集，使得它们都与N等势解:A={2n|n∈N}={2n+1|n∈N}={2n|n∈N}则A,B,C是三个不同的N的真子集,且它们都与N等势第九章 4、11、15、164、判断下列集合对所给的二元运算是否封闭：(1)整数集合Z和普通的减法运算(2)非零整数集合Z*和普通的除法运算(3)全体n×n实矩阵集合Mn(R)和矩阵加法及乘法运算，其中n≥2(4)全体n×n实可逆矩阵集合关于矩阵加法和乘法运算，其中n≥2(5)正实数集合R+和 运算，其中 运算定义为：ａ,ｂ∈R+,a b=ab-a-b(6)n∈Z+,nZ={nz|z∈Z}.nZ关于普通的加法和乘法运算。(7)A={a1,a2,...,an},n≥2. 运算定义如下： ai,aj∈A,ai aj=ai.(8)S={2x-1|x∈Z+}关于普通的加法和乘法运算。(9)S={0,1},S关于普通的加法和乘法运算。(10)S={x|x=2n,n∈Z+}，S关于普通的加法和乘法运算。解：(1)封闭 (2)不封闭 (3)封闭 (4)不封闭、封闭(5)不封闭(6)封闭 (7)封闭 (8)不封闭、封闭(9)不封闭、封闭 (10)不封闭、封闭11、设S={1,2,...,10},问下面定义的运算能否与S构成代数系统<S,*>?如果能构成代数系统则说明*运算是否满足交换律结合律并求*运算的单位元和零元。(1)x*y=gcd(x,y),gcd(x,y)是x与y的最大公约数。(2)x*y=lcm(x,y),lcm(x,y)是x与y的最小公倍数。(3)x*y=大于等于x和y的最小整数。(4)x*y=质数p的个数，其中x≤p≤y.解：(1)能构成代数系统，且*运算满足交换律、结合律，*运算不存在单位元，零元为1。(2)不能构成代数系统。(3)能构成代数系统，且*运算满足交换律、结合律，*运算的单位元为1，零元为10。(4)不能构成代数系统。14、下面各集合都是N的子集，它们能否构成代数系统V=<N,+>的子代数：(1){x|x∈N∧x可以被16整除}(2){x|x∈N∧x与8互质}(3){x|x∈N∧x是40的因子}(4){x|x∈N∧x是30的倍数}解：(1)是(2)不是(3)不是(4)是16、设V=<Z,+,·>，其中+和·分别代表普通加法和乘法，对下面给定的每个集合确定它是否构成V的子代数，为什么？(1)S1={2n|n∈Z}(2)S2={2n＋1|n∈Z}(3)S3={－1，0，1}解：(1)S1不能构成V的子代数，因为乘法的单位元不在S1中。(2)S2不能构成V的子代数，因为加法运算不封闭。(3)S3不能构成V的子代数，因为加法运算不封闭。第十章 15、17、18、21、22、24、27、28、29。15、设G为群，若x∈G有x2=e,证明G为交换群证明：a,b∈G由条件x∈G有x2=e所以a2=e,b2=e(ab)2=e,即(ab)(ab)=e所以a-1=a,b-1=b,ba=a-1b-1所以ba=ab,即ab=ba，因此G为交换群。17、设G为群，a,b,c∈G,证明：|abc|=|bca|=|cab|证明：设|abc|=r,|bca|=t，则(abc)r=e, (bca)t=e由于(abc)t=(abc)(abc)……(abc)=a(bca)(bca)……(bca)a-1=a(bca)ta-1=aea-1=aa-1=e由定理知：r|t又由于(bca)r=(bca)(bca)……(bca)=a-1(abc)(abc)……(abc)a=a-1(abc)ra=a-1ea=a-1a=e由定理知：t|r综上所述:r=t,即|abc|=|bca|同理可证：|bca|=|cab|所以|abc|=|bca|=|cab|18、证明偶数阶群必含2阶元证明：设偶数阶群为G，不妨设|G|=2n下面按元素的阶进行划分：①元素的阶为1,只有单位元e,所以个数为1。②元素的阶为2，设其构成的集合为：A③元素的阶大于2，设其构成的集合为：B则B的个数一定为偶数。因为a∈G，若|a|﹥2则由定理知|a|=|a-1|，且a≠a-1所以阶大于2的元素成对出现。因此B的个数一定为偶数。所以|G|=1+|A|+|B|，即|A|=|G|-1-|B|≥1，所以偶数阶群必含2阶元。21、设G为群，a是G中给定元素，a的正规化子Na表示G中与a可交换的元素构成的集合，即Na=x|x∈G∧aax}证明：Na是G的子群证明:1)a∈Na,所以Na非空(因为a∈G∧aa=a)2)xy∈Na)则xa=x yaay在ya=y两边分别乘以1得ya1=ay由于y1a=xy1a=xa1y)1=xya1)1=xay1)=xay1=axy1=axy1)所以y1a=axy1)由判定定理知Na是G的子群22、设H是群G的子群,x∈G,令xHx-1={xhx-1|h∈H},证明：xHx-1是G的子群,称为H的共轭子群。证明：e是xHx-1中的元素,因此xHx-1非空。u,v∈xHx-1则存在h,k∈H,使得u=xhx-1,v=xkx-1,则有uv-1=(xhx-)(xkx-1)-1=(xhx-1(xk-1x1)=x(hk-1)x-1因为H为子群,hk-1属于H,从而x(hk-1)x-1属于xHx-1.即uv-1∈xHx-1由判定定理，所以xHx-1是G的子群。24、设H和K分别为群G的r,s阶子群，若r和s互素，证明：H∩K={e}证明：①由于H和K分别为群G的子群，显然e∈H∩K。②假若x∈H∩K,且x≠e则x∈H∧x∈K则<x>≤H,<x>≤K由拉格朗日定理知：|<x>|整除H和K的阶。而H和K的阶分别为r,s，且r和s互素所以|<x>|为1，所以x=e，与假设矛盾。综上所述H∩K={e}27、设G1为循环群,f是群G1到G2的同态,证明f(G)也是循环群。证明：由于G1为循环群，不妨设G1=<a>,首先由定理群在同态映射下的像仍是群，所以f(G1)是群。下面证明φ(G1)是是循环群y∈f(G1),x∈G1,使得f(x)=y.而G1=<a>所以存在r使得x=ar则y=f(x)=f(ar)=f(a)f(a)……f(a)=(f(a))r这证明了f(a)为f(G1)的生成元。即f(G1)=<(a)>所以f(G1)为循环群。28、设G=<a>是15阶循环群。(1)求出G的所有的生成元。(2)求出G的所有子群。解：(1)生成元为:a,a2,a4,a7,a,a11,a13,a14(2)G的所有子群:共4个子群<e>, <a3>={e,a3,a6,a9,a12}, <a5>={e,a5,a10}, G29、设σ,τ是5元置换,且12 3214

4 5

12 3 4 3 4 51(1)计算στ,τσ,σ-1,τ-1,σ-1τσ(2)将στ,τ1,σ-1τσ表成不交的轮换之积。(3)将(2)中的置换表示成对换之积,并说明哪些为奇置换,哪些为偶置换。解:(1)(2)(3)στ为奇置换,τ-1,σ-1τσ为偶置换。第十一章 2、6、12、13、14、16、172、下列各集合对于整除关系都构成偏序集,判断哪些偏序集是格。(1)L={1,2,3,4,5}(2)L={1,2,3,6,12}(3)L={1,2,3,4,6,9,12,18,36}(4)L={1,2,22,...,2n},n∈Z+解：(1)不是格,因为{3,4}无上确界(2)、(3)、(4)都是格。6、设L是格，a,b,c∈L,且a≤b≤c,证明：a∨b=b∧c证明：由于L是格，a,b,c∈L,且a≤b≤c所以a∨b=b,b∧c=b因此a∨b=b∧c12、对以下各小题给定的集合和运算判断它们是哪一类代数系统(半群,独异点,群,环,域,格,布尔代数),并说明理由。1 1(1)S=1 1

1,2,2

1,3,3

1,4，运算为普通乘法。4 (2)S2={a1,a2,...,an}, ai,aj∈S2,ai*aj=ai.这里的n是给定的正整数,且n≥2.(3)S3={0,1},*为普通乘法。(4)S4={1,2,3,6},x,y∈S4,x y和x*y分别表示求最小公倍数和最大公约数运算。(5)S5={0,1},*为模2加法, 为模2乘法。解：(1)不是代数系统，对于乘法不封闭。(2)半群，运算封闭，有结合律，没有单位元。(3)半群与独异点，乘法封闭，有结合律，单位元是1，但是0没有逆元。(4)格与布尔代数。两个运算满足交换、相互分配、同一律、补元律。(5)环与域，{0,1}关于模2加法构成交换群、{1}关于模2乘法构成交换群，模2乘法关于模2加法有分配律。13、设B是布尔代数,B中的表达式f是(a∧b)∨(a∧b∧c)∨(b∧c)(1)化简f.(2)求f的对偶式f*。解：(1)由于(a∧b)∨(a∧b∧c)∨(b∧c)=(a∧b)∨(b∧c)=(b∧a)∨(b∧c)=b∧(a∨c)(2)f*=(a∨b)∧(b∨c)14、设B是布尔代数，a,b∈B,证明：≤ba∧b’=0a’∨b=1证明：①若a≤b则a∨b=b所以a∧b’=a∧(a∨b)’=a∧(a’∧b’)=(a∧a’)∧b’=0∧b’=0因此a∧b’=0②若a∧b’=0两边分别求补元，即(a∧b’)’=0’所以a’∨b=1③若a’∨b=1则a=a∧1=a∧(a’∨b)=(a∧a’)∨(a∧b)=0∨(a∧b)=a∧b所以a∧b=a由定理知a≤b16、设<B,∧,∨,＇,0,1>是布尔代数,在B上定义二元运算,x,y∈B有 xy=(x∧y＇)∨(x＇∧y)问<B, >能否构成代数系统？如果能,指出是哪一种代数系统。为什么？解：构成群，运算封闭。a,b,c∈B(a)c(ab')(a')c(ab')(a')c')(ab')(a')')(ab'c')(a'bc')(ab')'(a')'c)(ab'c')(a'bc')(a')(a')c)(ab'c')(a'bc')(a'ac)(a'b')bac)bb'c)(ab'c')(a'bc')0(a'b')(abc)0(ab'c')(a'bc')(a'b'c)(abc)同理有a)cab)a'')'b')'')ab)易见结合律成立。由于 a0(a0')(a')(a)0a所以0为单位元。由于 aa(aa')(a'a)000所以a的逆元为a。因此<B,>能构成群。17、设B是布尔代数，a,b,c∈B,若a≤c,则有a∨(b∧c)=(a∨b)∧c称这个等式为模律，证明布尔代数适合模律。证明：a,b,c∈B,若a≤c则a∨c=c所以a∨(b∧c)=(a∨b)∧(a∨c)=(a∨b)∧c因此a∨(b∧c)=(a∨b)∧c第十四章 6、16、25、29、44、45、506、(1)设n阶图G中有m条边，证明:(G)2m/n(G)(2)n阶非连通的简单图的边数最多可为多少？最少呢？证明：(1)由G)d(i)G),根据握手定理有nG)d(i)nG)i1得到G)

2mG)n2)n阶非连通的简单图至少有2个连通分支，边数最多的情况是由Kn-1和一个孤立点构成它的边数为(n-1)(n-2)/2.边数最少的非连通图当然是n阶零图边数m=0,由n