离散数学(刘舒华著)电大课后答案

《离散数学(刘舒华著)电大课后答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。课后答案网,用心为你服务!大学答案---中学答案---考研答案---考试答案最全最多的课后习题参考答案,尽在课后答案网(www.khdaw.com)!Khdaw团队一直秉承用心为大家服务的宗旨,以关注学生的学习生活为出发点,旨在为广大学生朋友的自主学习提供一个分享和交流的平台。爱校园(www.aixiaoyuan.com)课后答案网(www.khdaw.com)淘答案(www.taodaan.com)

1资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第一章集合1.集合A={1,{2},3,4},B={a,b,{c}},判定下列各题的正确与错误:(1){1}∈A;(2){c}∈B;(3){1,{2},4}ÍA;(4){a,b,c}ÍB;(5){2}ÍA;(6){c}ÍB;(7)fÌA;(8)fÍ{{2}}ÍA;(9){f}ÍB;(10)f∈{{2},3}.解:(1)不正确。因为{1}是集合,集合与集合之间一般不能有属于关系。(2)正确。虽然{c}是集合,可是它又是B中的元素。(3)正确。虽然{1,{2},4}是A的真子集,可是同时满足子集定义,故能够这样表示。(4)不正确。因为cÏB。(5)不正确。虽然{2}是一个集合,可是它只是A中的一个元素,不能有包含关系。(6)不正确。理由同(5)。(7)正确,符合定义。(8)正确,都符合定义。(9)不正确,因为B中本没有元素f。(10)不正确。f不是{{2},3}是中的元素,不能有属于关系,若写成fÍ{{2},3}则能够。2．确定下列集合的幂集:(1)A={a,{b}};(2)B={1,{2,3}};课后答案网(2)C={f,a,{b}};(4)D=r(f)={f}。解(1)因为A的所有子集为f,{a},{{b}},{a,{b}},所以r(A)={f,{a},{{b}},{a,{b}}}.(2)因为B的所有子集为f,{1},{{2,3}}和{1,{2,3}}。所以r(B)={f,{1},{{2,3}},{1,{2,3}}}(3)因为C的所有子集为f,{f},{a},{{b}},{f,a},{f,{b}},{a,{b}},{f,a,{b}},r(C)={f,{f},{a},{{B}},{f,a},{f,{b}},{a,{b}},{f,a,{b}}}..com因此(4)因为D的子集为f,{f},因此r(D)={f,{f}}.说明欲求一个给定集合的幂集合,首先把这个给定集合的所有子集列出,并检验所2列子集的个数是否等于n个,n为给定集合的元数,当然,熟练者能够省略这一步骤.2.判定以下论断哪些是恒成立的?哪些是恒不成立的?哪些是有时成立的?

2资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(1)若a∈A,则a∈A∪B;(2)若a∈A,,则a∈A∩B;(3)若a∈A∪B,则a∈A;(4)若a∈A∩B,则a∈B;(5)若aÏA,则a∈A∪B;(6)若aÏA,则a∈A∩B;(7)若AÍB,则A∩B=A;(8)若AÍB,则A∩B=B.(1)恒成立.因为AÍA∪B,若a∈A,则a∈A∪B.解(2)有时成立.若a∈A,但aÏB,则aÏA∩B;若a∈A,且a∈B,则a∈A∩B.(3)有时成立.若a∈A∪B,可能有三种情形:a∈A但aÏB,或者aÏA但aÏB,或者aÎA且aÎB,对于第一、三种情形,有a∈A,可是第二种情形,aÏA.。(4)恒成立。因为a∈A∩B,必有a∈A,且a∈B。(5)有时成立。虽然aÏA.,可是,有a∈B或aÏB两种可能,若aÏB,则aÏA∪B;若a∈B,有a∈A∪B。(6)恒不成立。因为aÏA.,即使a∈B,也有aÏA∩B,若aÏB,更有aÏA∩B。(7)恒成立。当AÍB,A是B的子集,当然满足A∩B=A。(8)有时成立。既然AÍB,就有两种可能:A=B或者AÌB。若A=B,则A∩B=B成立;若AÌB,则A∩B=B就不成立。课后答案网4．设全集合E={a,b,c,d,e},A={a,d},B={a,b,e},C={b,d},求下列集合:(1)A∩～B;(2)(A∩B)∪～C;(3)～A∪(B－C);(4)r(A)Çr(B).解(1)A∩～B={a,d}∩{c,d}={d}.(2)(A∩B)∪～C={a}∪{a,c,e}={a,c,e}.(3)～A∪(B－C)={b,c,e}∪{a,e}={a,b,c,e}.(4)r(A)={f,{a},{d},{a,d}}.r(B)={f,{a},{b},{e},{a,b},{a,e},{b,e},{a,b,e}}故r(A)Çr(B).={f,{a}}.5.设A和B是全集E的子集,利用运算律证明:.com(1)(2)证(A∩B)∪(A∩～B)=A;B∪～((～A∪B)∩A)=E.(1)(A∩B)∪(A∩～B)=A∩(B∪～B)=A∩E=AB∪～((～A∪B)∩A)(3)=B∪～((～A∩A)∪(B∩A)(分配律)=B∪～(f∪(B∩A))(互补律)

3资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。=B∪～(B∩A)=B∪(～B∪～A)=(B∪～B)∪～A=E∪～A(同一律)(德·摩根律)(结合律)(互补律)=E.说明利用运算律证明集合恒等式时,后面的运算律名称不一定要求写,只是刚开始做这种类型题时标一下,目的在于熟悉理解运算律内容,稍加熟练后便能够不写.6.设A,B,C是三个任意集合,求证:(1)(A∪B)∩(B∪C)∩(C∪A)=(A∩B)∪(B∩C)∪(C∩A);(2)(A∪B)∩(B∪C)∩(C∪A)=(A∩B)∪(～A∩B∩C)∪(A∩～B∩C).证(1)(A∪B)∩(B∪C)∩(C∪A)=((A∪B)∩(C∪B))∩(A∪C)=((A∩C)∪B)∩(A∪C)=((A∩C)∩(A∪C)∪(B∩(A∪C))=((A∩C∩A)∪(A∩C∩C)∪(B∩A)∪(B∩C)=(A∩C)∪(B∩A)∪(B∩C)=(A∩B)∪(B∩C)∪(C∩A)(3)(A∩B)∪(～A∩B∩C)∪(A∩～B∩C)=(A∩B)∪(((～A∩B)∪(A∩～B))∩C)=(A∩B)∪(((～A∪A)∩(～A∪～B)∩(B∪A)∩(B∪～B))∩C)=(A∩B)∪((～(A∩B)∩(A∪B)∩C)=((A∩B)∪(～(A∩B))∩((A∩B)∩(A∪B))∩((A∩B)∪C)=(((A∩B)∪A)∪B)∩((A∪C)∩(B∪C))课后答案网=(A∪B)∩(B∪C)∩(A∪C).7.利用A－B=A∩～B与吸收律及其它运算律,证明(((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)=～A∩B证(((A∪B∪C)∩(A∪B))－((A∪(B－C))∩A)=((A∪B)∩((A∪B)∪C))－((A∪(B－C))∩A)=(A∪B)－((A∪B)∩(A∪～C)∩A)=(A∪B)－(A∩(A∪B)∩(A∪～C)=(A∪B)－(A∩(A∪～C))=(A∪B)－A=(A∪B)∩～A=(A∩～A)∪(B∩～A)=f∪(～A∩B)=～A∩B..com说明本题证明过程中的第二步、第四步、第五步应用了吸收律,才使运算简便,否则将很繁杂。8．设A,B,C为三个任意集合,试证明(1)若A×A=B×B,则A=B;(2)若A×B=A×C,且A≠f,则B=C.证(1)设任意a∈A,则(a,a)∈A×A,因为A×A=B×B,有(a,a)∈B×B,故a∈B,因此AÍB.

4资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。对任意b∈B,有(b,b)∈B×B,则(b,b)∈A×A,于是b∈A,因此BÍA,因此A=B.(2)若B=f,则A×B=f,因为A×B==A×C,于是A×C=f,而A=f,只有C=f,故B=C.若B≠f,设任意b∈B,因为A≠f,再设a∈A,则(a,b)∈A×B,又因为A×B==A×C,则(a,b)∈A×C,于是b∈C,因此BÍC.同理可证CÍB,故B=C.说明在每一节后面的证明题,若不能应用本节给出的定理,一般要考虑用定义证明.8.在具有x和y轴的笛卡尔坐标系中,若有X={x︱x∈R,且-3≤x≤2},Y={y︱y∈R,且-2≤y≤0},试求出笛卡尔积X×Y,Y×X,画出其图像.解X×Y={(x,y)︱-3≤x≤2,-2≤y≤0,x,y∈R}Y×X={(y,x)︱-2≤y≤0,-3≤x≤2,x,y∈R}X×Y与Y×X的图像如图1-1所示的阴影部分.说明对于笛卡尔积Y×X的图像,从(y,x)∈Y×X,点(y,x)要求第一元素为该点的横坐标,第二元素为该点的纵坐标,因此将图1-1中右图表示两轴的字母换成y,x.2-3-2123-3-2课后答案网-1--图1—1.com

5资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第二章关系与映射1、设集合A={1,2,3,4},A上的二元关系R{x,y|x,yÎA,且x³y},=()求R的关系图与关系矩阵R={(x,y)|x,yÎA,且x³y}解={(1,1),(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(3,3),(4,3),(4,4)}R的关系图如图2-1所示。图2-1é1000ùêú1100ê课后ú答案网MR=êúúû1110ê1111ë22.在由n个元素组成的集合上,能够有多少种不同的二元关系?若集合A,B的元数分别为|A|=m,|B|=n,试问从A到B有多少种不同的二元关系?解因为一个由n个元素组成的集合A上,任何一个二元关系都是A´A的子集,而A´A=A2中共有n2个元素,取0个到n2个元素能够组成2n2子集,因此有2n2个不同的关系。而当|A|=m,|B|=n时,A´B这个全关系中共有m´n个元素,取0个到m´n个元素组成的子集共有2m´n个,因此从A到B共有2m´n种不同的二元关系。3.设集合A={1,2,3,4},A上的二元关系分别为:R={(1,1),(1,2),(2,4),(3,1),(3,3)}.comS={(1,3),(2,2),(3,2),(4,4)}R·SS·R-1S-1-1·S-1R,,并画出其关系图。R2R试用定义求,,,,R·S={(1,3),(1,2),(2,4),(3,3),(3,2)}解(1,1),(1,3),(2,4),(3,4)}S·R={(1,1),(1,2),(1,4),(3,1),(3,2),(3,3)}R2={={(1,1),(1,3),(2,1),(3,3),(4,2)}R-1

6资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。-1={(2,2),(2,3),(3,1),(4,4)}S-1={(1,1),(3,1),(4,2),(4,3)}R-1·S其关系图如图2-2所示。414121233432R2RS-R13232S-1-1R-1·S-1图2-21.当用定义求复合关系时,先将左关系中每个序偶的第二元素作为中介元素,说明到右关系中每个序偶里找与其相同的第一元素,将这个元素去掉,用剩余两个元素组成新序偶成为复合关系中的元素。2.用定义求出的复合关系与逆关系,能够用关系矩阵来验证其正确性。设集合A={x,y,z},集合B={a,b,c,d,e}上的关系,S是A,B上A4.,R是集合课后答案网R={(x,x),(x,z),(y,x),(y,y),(z,x),(z,y),(z,z)}S={(x,a),(x,d),(y,a),(y,c),(y,e),(z,b),(z,d)}的关系。M(R×S)-1=MS-1×MR-1试验证é101ùé10010ùêúúêúúMR=110MS=10101êëêëêúûê01010úû111证MR×S=MR×MSé101ùé10010ùê110úê10101úúêúúê01010êê111ûëúëû.com=é11010ùêú10111úú11111ûêêë=

7资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。éêêêê111011ùúú011ú111ú011ûúêM(R×S)-1=MTR×Së=éêêêêê110ù001úúé111ù010ú101úêêêú011úúMR-1101MS-1010úûëûë==éêêêêêùúúú110001é111ù010êúúú011101êúMS-1×MR-1=MS-1´M=010ê101úëûëûR-1éùú111êêêê101ú011úú111êëú011û=M(R×S)-1=MS-1×MR-1故。图2-3所示的图形是集合课后{1,2,3}答案网R,R,R3,R4的关系图,试根据这些关系图分5.上关系12别写出对应的关系矩阵,并说明每种关系所具有的性质(自反性,对称性,反对称性,传递性)。.com

8资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。112323R1R211332图2-3é100ùêú课后答案网010êúêëúûM001解R1=R1具有自反性,对称性,反对称性与传递性。é100ùêêúú011011êëúûMR2=R2具有对称性与传递性。é010ùêêúú001100êëúûMR3=R具有反对称性。3.comé000ùêêúú000000úûêëMR=4R具有对称性,反对称性与传递性。4说明本题判断关系所具有的性质,主要经过已知关系图与求出的关系矩阵进行,同时对于比较难于判定的传递性,都能够一结合定义进行判定。如果不破坏定义所要求的条件,能够

9资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。认为满足定义要求,如对R4的判定。5.5.下列关系是否具有如下性质:自反性,对称性,反对称性,传递性?⑴R={(x,y)|x,yÎI,x>y};1R2={(x,x)|x³0,且x为实数};⑵⑶A上的恒等关系R3={(x,x)|xÎA};⑷A={1,2,3,×××,10}上的空关系f。R解⑴1具有反对称性与传递性;R⑵2具有反对称性;R⑶3具有自反性,对称性,反对称性与传递性;⑷A上的空关系具有对称性,反对称性与传递性。本题中的前两个小题均为无限集合,第⑶小题也未给定集合A的元数,这样不能得说明到完整的关系图与关系矩阵。可是,能够在草纸上作出部分元素的关系图与关系矩阵进行判断,同时要充分利用定义要求,便具有该种性质。第⑷小题,与上题中⑷题类型一致,只是元数大一些,结果应与上题⑷相同。7.设R1和2是集合A上的任意关系,试证明或用反例推翻下列论断:R⑴若R1和⑵若R1和⑶若R1和⑷若R1和RRRR2都是自反的,则R1×R2也是自反的;2都是对称的,则R1×R2也是对称的;2都是反对称的,则R1×R2也是反对称的;2都是传递的,则R1×R2也是传递的。⑴论断正确。对任意aÎARR都是2网证,若和A上的自反关系,则课后答21案(a,a)ÎR,(a,a)ÎR1因此(a,a)ÎR1×R2,即R1×R2也是自反的。⑵论断不正确。R1={(a,b),(b,a),(c,c)},R2={(b,c),(c,b)}例如,设A={x,y,z},当R,R1与2都是对称的,可是R1×R2={(a,c),(c,b)}已不是对称的,故原论断不正确。⑶论断不正确。R1={(a,a),(b,a),(b,c),(c,a)}R2={(a,b),(b,b)(b,c),(c,c)}例如,设集合A={a,b,c},当R1与2都是反对称的,R可是,R1×R2={(a,b),(b,b),(b,c),(c,b)}已不是反对称的,(因为(b,c),(c,b)ÎR1×R2),故故原论断不正确。⑷论断不正确。R={(a,b),(b,c),(a,c)},R={(b,c),(c,a)(b,a)},A={a,b,c}例如,设集合,当.com12(b,a)ÎR×R,(a,c)ÎR×R不是传递的,因为,而1212,故原论断不正确。证毕。r(R)s(R)和t(R)8.设的关系图如图2-4所示,试画出,的关系图。R×R={(a,a),(a,c),(b,a)}12(b,c)ÏR×R12R

10资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。dcabc图2-4解r(R),s(R),t(R)的关系图如图2-5所示dcabcr(R)dcabcs(R)课后答案网dcabct(R)图2-5.comR⑴对于r(R)的关系图,因为r(R)=ÈRI说明,只要在AR的关系图上对没有自回路r(R)的关系图。R的结点都添加上自回路,使能够画成的自反闭包⑵对于s(R)的关系图,因为s(R)=RÈR-1,只要将的关系图中所有单向弧都画成双向弧,便能够画成R的对称闭包s(R)的关系图。

11资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。nt(R)=ÈRi.在画图时,如果R⑶关系图中从结点x到结点y有一连串带箭头的头尾相接的弧相连着,则在R的关系图上添对于t(R)的关系图,当R是有限集合上的关系时,i=1加一条直接从x到y的弧,便能够画出t(R)的关系图,如图2-5中t(R)关系图上的ac与,a与d,ae与,b与d之间都应画一条有向弧。可是这里要特别注意c,d两个结点,原有两条c到d与d到c的有向弧,这属于总结规律中的特殊情形,作为结点c看成是两个结点的重合,因此结点c处要画一条自回路,表示从结点到结点。同理,结点ccd也要画一条自回路。9.设集合A={1,2,3,4},写出它们的关系矩阵上的关系R={(1,2),(2,3),(3,1),(4,4)}求t(R)和sr(R),并AR={(1,2),(2,3),(3,1),(4,4)}解因为RR2={(1,3),(2,1),(3,2),(4,4)}={(1,1),(2,2),(3,3),(4,4)}因此3R4={(1,2),(2,3),(3,1),(4,4)}t(R)=RÈR2ÈR3ÈR4={(1,1),(1,2),(1,3),(2,1)(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}r(R)=RÈIA={(1,1),(1,2),(2,2),(2,3),(3,1),(3,3),(4,4)}(r(R))-={(1,1),(1,3),(2,1),(2,2),(3,2),(3,3),(4,4)}sr(R)=r(R)È(r(R))-11={(1,1),(1,2),(1,3),(2,1)(2,2),(2,3),(3,1),(3,2),(3,3),(4,4)}课后答案网,故其关系矩阵为此题t(R)=sr(R)é1110ùêêêêúúúúû11101110Mt(R)=Msr(R)0001ë=说明此题t(R)=sr(R),这纯属偶然情况,一般地,t(R)¹sr(R)。10.设R是集合A上的二元关系,若R是传递的,则r(R)也是传递的,而s(R)不一定是传递的。证由§2.4定理1知,R是传递的,当且仅当t(R)=R,故要证r(R)是传递的,只需证明t(r(R))=r(R)。¥t(r(R))=t(RÈI)=t(RÈR0khdaw.com)=È(RÈR0)i(I=R)0Awww.A因为i=1i(RÈR0)i=ÈRj下面用归纳法证明i=1时,左端=j=0RÈR0当=右端k(RÈR0)k=ÈRj假设当i=k时,命题成立,即j=0

12资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。k当i=k+1时,(RÈR0)k+1=(RÈR0)k×(RÈR0)=ÈRj×(RÈR0)j=0由§2.2,习题7的结论,可得kkkÈRj×(RÈR0)ÈRj×RÈÈR×Rj0j=0=j=0j=0k+1k+1=ÈRjÈÈRjj=1j=0k+1=ÈRjj=0¥i¥¥ÈÈRjÈRiÈRiÈR0故t(r(R))====t(R)ÈIA=RÈIA=r(R)i=1j=0i=1i=1即t(r(R))=r(R),故r(R)是传递的。s(R)不一定是传递的。例如设集合A={a,b,c}上的二元关系,当R={(a,b),(b,c),(a,c)},RR是传递的,而={(a,b),(a,c),(b,a),(b,c),(c,a),(c,b)}时,s(R)已经不是传递的。证毕。s(R)=RÈR-111.设R是集合A上的二元关系,判断下列命题是否正确?⑴rt(R)=tr(R);⑵ts(R)=st(R)。解⑴命题正确。由于tr(R)=t(RÈIA),rt(R)=t(R)ÈIA,并利用R×IA=IA×R=R,以及对于一切n(RÈIA)n=IAÈ(ÈRi)自然数n,InA=IA,用数学归纳法的能够证明,因此i=1tr(R)=t(r(R))=t(RÈI)课后答案网È(RÈI)A=(RÈIA)È(RÈI)23È×××AA=IAÈRÈRÈRÈ×××23=IAÈt(R)=r(t(R))=rt(R)。⑵命题不正确。能够证明st(R)Íts(R)。首先证明,当R1ÊR2时,则s(R1)Ês(R2)且t(R1)Êt(R2)。这是因为,s(R1)是对称的且s(R1)ÊR1,可是R1ÊR2,故s(R1)ÊR2。由s(R2)的定义,s(R)s(R1)Ês(R2)。是包含R2的最小对称关系,故2同理可证,t(R1)Êt(R2)。由对称闭包定义,有s(R)ÊR,利用上面证过的结论:ts(R)Êt(R),sts(R)Êst(R)P58例5(2)可知,s(R)是对称的,ts(R)也是对称的,又根据§2.4定理1中(2),ts(R)是对称的,当且仅当sts(R)=ts(R),因此ts(R)Êst(R),即st(R)Íts(R)。st(R)Êts(R)不一定成立。再由教材.com例如,集合A={a,b,c}上关系,R={(a,b),(b,c)}R={(a,c)},R23=f,R-1={(b,a),(c,b)},,则t(R)=RÈRÈR23={(a,b),(b,c),(a,c)}

13资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(t(R))-1={(b,a),(c,b),(c,a)}s(t(R))=t(R)Èt(R)-1={(a,b),(a,c),(b,a)(b,c),(c,a),(c,b)}-1={(a,b),(b,a),(b,c),(c,b)}而s(R)=RÈRs(R)2={(a,a),(a,c),(b,b),(c,a),(c,c)}(s(R))3={(a,b),(b,c),(b,a),(c,b)}。t(s(R))=s(R)Ès(R)={(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)}故s(t(R))不包含t(s(R))Ès(R)23R12.设R1和2是集合A上的二元关系,试判断下列命题是否正确?⑴r(R1ÈR2)=r(R1)Èr(R2);⑵s(R1ÈR2)=s(R1)Ès(R2);⑶t(R1ÈR2)=t(R1)Èt(R2)。解⑴命题正确。因为r(R1ÈR2)=R1ÈR2ÈIA=R1ÈIAÈR2ÈIA=r(R1)Èr(R2)。⑵命题正确。首先证明任取(a,b)Î(R1ÈR2)-,当且仅当(b,a)ÎR1ÈR2,当且仅当(b,a)ÎR1或(b,a)ÎR2,1当且仅当(a,b)ÎR-1(a,b)Î-1,当且仅当(a,b)ÎR-1ÈR2-1,故证得R21,或1课后答案网(R1ÈR2)-1=R1-1ÈR2-1而s(R1ÈR2)=(R1ÈR2)È(R1ÈR2)-1=R1ÈR2ÈR1-1ÈR2-1=(R1ÈR1-1)È(R2ÈR2-1)=s(R1)Ès(R2)⑶命题不正确,能够证明t(R1ÈR2)Êt(R1)Èt(R2)。因为R1ÈR2ÊR1,利用前一例题中⑵证明中证过的结论:当R1ÊR2时,则t(R1)Êt(R2),有t(R1ÈR2)Êt(R1)同理,R1ÈR2ÊR2,有t(R1ÈR2)Êt(R2)t(RÈR)Êt(R)Èt(R)故1212.comt(R)Èt(R)Êt(RÈR)不一定成立。1212例如,设集合A={a,b,c}R和R分别为12A,上的二元关系R={(a,b),(b,c)}R={(a,c),(c,b)}则12R21={(a,c)}={(a,b)}R31R32=fR22=ft(R1)=R1ÈR12ÈR13={(a,b),(a,c),(b,c)}

14资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。t(R2)=R2ÈR22ÈR23={(a,b),(a,c),(c,b)}t(R1)Èt(R2)={(a,b),(a,c),(b,c),(c,b)}而R1ÈR2={(a,b),(a,c),(b,c),(c,b)}2={(a,c),(a,b),(b,b),(c,c)}3={(a,b),(a,c),(b,c),(c,b)}(R1ÈR2)(R1ÈR2)t(R1ÈR2)=(R1ÈR2)È(R1ÈR2)È(R1ÈR2)23={(a,b),(a,c),(b,b),(b,c),(c,b),(c,c)}显然,t(R1)Èt(R2)不包含t(R1ÈR2)13.设集合A={a,b,c,d,e},A上的关系关于等价关系R的等价类为:M1={a,b,c},M2={d,e},试求:⑴等价关系R;⑵写出关系矩阵MR;⑶画出关系图。IAÍR解⑴因为等价关系R具有自反性,因此,IA={(a,a),(b,b),(c,c),(d,d),(e,e)}。又因为a,b,c在同一个等价类中,因此{(a,b),(b,a),(a,c),(c,a)(b,c),(c,b)}ÍR再因为d,e在同一个等价类中,因此{(d,e),(e,d)}ÍRR=IAÈ{(a,b),(b,a),(a,c),(c,a),(b,c),(c,b),(d,e),(e,d)}。因此é11100ù课ê后答案ú网11100êêêêú11100úúMR=00011úê00011úëû⑵R的关系矩阵⑶R的关系图如图2-6所示acdeb.com图2-6RR是非空集合214.设和上的等价关系,下列各式哪些是1AA上的等价关系?哪些A不是上的等价关系?举例说明:A´A-R1R-R;2⑴;⑵1⑶R12;⑷r(R1-R2);⑸R1×R2

15资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。A´A-R1不是A上的等价关系。解⑴R1={(a,a),(b,b)}例如,设集合A={a,b},A上的关系A´A={(a,a),(a,b),(b,a),(b,b)}A´A-R1={(a,b),(b,a)}不具有自反性与传递性,故A´A-R1不是A上的等价关系。⑵R1-R2不是A上的等价关系。例如,设集合A={a,b,c},R1={(a,a),(a,b),(b,a),(b,b),(b,c),(c,b),(c,c)}R2={(a,a),(b,b),(c,c)}R1-R2={(a,b),(b,a),(b,c),(c,b)}不具有自反性和传递性,因此R1-R2不是A上的等价关系。⑶R12是集合A上的等价关系。aÎA,有(a,a)ÎA,而且有R1A因为是集合上的等价关系,任取(a,a)ÎR1×R1=R21R21,因此在集合A上是自反的。任取a,bÎA,若(a,b)ÎR12,则存在cÎA,使得(a,c)ÎR1且(c,b)ÎR1,因为R1是对称的,有(c,a)ÎR1且(b,c)ÎR1,于是(b,a)ÎR21,因此R12是对称的。任取a,b,cÎA,若(a,b)ÎR1(a,d)ÎR1,且(d,b)ÎR1且(b,c)ÎR1,则存在d,eÎA,分别使得22课(b,e)ÎR1,且(e,c)ÎR后答案网1由于R1是传递的,元素a与b之间以d为中介元素,b与c之间以e为中介元素,有(a,b)ÎR1,(b,c)ÎR1,再根据关系的复合,有a,cÎR1×R1=R12()因此R12是可传递的,故R12是集合A上的等价关系r(R1-R)2⑷不是集合A上的等价关系。由⑵题所举例子,R1-R2={(a,b),(b,a),(b,c),(c,b)}有r(R1-R2)=(R1-R2)ÈIA={(a,a),(a,b),(b,a),(b,b),(b,c),(c,b),(c,c)}r(R1-R2)不具有传递性,因此r(R1-R)不是集合A上的等价关系。2⑸R1×R2是集合A上的等价关系。(a,a)ÎR(a,a)ÎR(a,a)ÎR×RR×R是自反的com2aÎAwww对于任意,有.k且Îh,故da,因此w.(a,b)ÎR×R,212121a,bÎA(a,b)R,R(b,a)ÎRR任取,若是对称的,必有(a,b)ÎR,而是自反的,对于1112a,bÎA(a,a)ÎR,(b,b)RÎ(b,b)ÎR,有,由与,得22121(b,a)ÎR(a,a)ÎR(b,a)ÎR×RR×R,因此是对称的。12由与,得(a,b)ÎR1212a,b,cÎA(b,c)ÎRR1是传递的,必有(a,c)ÎR1。由任取,若1,1,于R2是自反的,由

16资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(a,b)ÎR1与(b,b)ÎR2,得(a,b)ÎR1×R2(b,c)ÎR1与(c,c)ÎR2,得(b,c)ÎR1×R2(a,c)ÎR1与(c,c)ÎR2,得(a,c)ÎR1×R2故R1×R2是集合A上的等价关系。15.设集合A={1,2,3,4},A上的四个半序关系分别为:R1={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3),(4,4)}R2={(1,1),(1,2),(2,2),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3),(4,4)}R3={(1,1),(2,2),(2,4),(3,1),(3,3),(4,4)}R4={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}试分别画出它们的哈斯图,并判断起其中哪个具有序关系?哪个具有良序关系?解集合上的半序关系的哈斯图如图2-7所示。1431412243433231R1RR1课2后答案网图2-7R其中关系图R2与4所有元素都排在链上,即任意两个元素之间都有关系存在,因此R2和R4都是序关系。由于2和4中每一非空子集都有最小元,因此也都是良序关系。RR说明此题中的阿拉伯数字已经失去了它们在实数集中的大小关系,应该把它们看成四个不同符号。16.设集合A={2,3,4,6,8,12,24},R为A上的整除关系。⑴画出半序集(A,R)的哈斯图;⑵写出集合A中的最大元,最小元,极大元,极小元;⑶写出A的子集B={2,3,6,12}的上界,下界,最小上界,最大下界。⑴半序集(A,R)的哈斯图如图2-8所示。解.com

17资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。248124263图2-8⑵集合A中的最大元是24,无最小元,极大元也是24,极小元是2和3。⑶集合B的上界是12与24,无下界,最小上界是12,无最大下界说明最大元与极大元的区别在于,最大元是一个集合中的最”大”者,若有则是唯一的;而极大元则是集合中的元素没有比它”大”的,可能不唯一。对于最小元与极小元具有同样情况。这里把”大”字用引号引起来,因为实际上不一定在研究数与数之间的大小关系,而是在研究某种半序关系。17.设R是集合A上的半序关系,且BÍA,试证明RR¢=Ç(B´B)是B上的半序关系。对于aÎB课后答案网ÍAaÎA,故,而R是A上的半序关系,则R在A上具B证任意,因为有自反性,于是(a,a)ÎR,且(a,a)ÎB´B,这样可得(a,a)ÎRÇ(B´B)=R¢即R¢在B上是自反的。任取a,bÎB,且a¹b,若(a,b)ÎR¢,可得(a,b)ÎR且(a,b)ÎB´B,因为R具有反对称性,必有(b,a)ÏR,故(b,a)ÏR¢,即R¢在B上具有反对称性。对于任意a,b,cÎB,因为BÍA,故a,b,cÎA,若(a,b)ÎR¢且(b,c)ÎR¢而R¢=RÇ(B´B),故(a,b)ÎRÇ(B´B),(b,c)ÎRÇ(B´B),由(a,b)ÎRÇ(B´B),可得(a,b)ÎR且(a,b)ÎB´B,即当(a,b)ÎR同时aÎR且bÎR。同理,当(b,c)ÎRÇ(B´B),也有(b,c)ÎR同时bÎR且cÎR。因为R在A上具有传递性,由(a,b)ÎR且(b,c)ÎR,得(a,c)ÎR。又a,b,cÎB,故(a,c)ÎB´B(a,c)ÎRÇ(BB)R,¢´=¢¢awRR.Bcom,因此满足传递性,因此是上的半序关系。A={0,1,2,3,4,5},B={0,1},18设集合sss(2n)=0,s(2n+1)=1,(n=0,1,2),C={2,3}C映射定义为,试求。s:A®BA={0,1,2,3,4,5},B={0,1}aÎA时解因为,,当当n=0,1,2时,a=0,2,4当n=0,1,2时,a=1,3,5ìs(2n)=0s(a)=íîs(2n+1)=1

18资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。而C={2,3}ÍA,设映射t:C®Bìs(2n)=0此时n只取1,a=2t(a)=íîs(2n+1)=1此时n也只取1,a=3ì0a=2t(a)=sC(a)=íî1a=3故即t(2)=0,t(3)=1sC为在上的限制,而s(0)=0,s(2)=0,s(4)=0,s(1)=1,s(3)=1,s(5)=1为t在A上的扩充。19.件是设A和s为满射必要性,当s是单射时,s(A)的元数是n,而s(A)ÍB,B的元数也是n,故是两个有限集合,它们的元数都是n,则s:A®B是单射的充分必要条B证s(A)=B,因此s:A®B是满射。充分性,若s:A®B为满射时,有s(A)=B,则s(A)的元数为n,A的元数也是n,n个原象对应n个象,即不同元素对应不同的象,因此s是A到B的单射。为实数集,s:R´R®R,s(x,y)=x+y,又t:R´R®R,t(x,y)=x×y,试证R20.设明s和t都是满射,而不是单射。证对于任意aÎR,能够使a=x+y成立的x,y有无数对,且(x,y)ÎR´R,也就是s说值域R中每个元素都有无数原象在R´R中,因此=x×y成立的x,y也不止一对实数存在。例如a=6,而x=2,y=3,或x=3,y=2,×××,即象集中每一元素都有原象,而且原象不唯一,因此是满射,而不是单射。对于任意aÎR,能使at是满射,而不是单射。证毕。课后答案网欲证明一个映射为满射时,一般采用取值域中任意元素,按映射对应都有原象存在时,。说明则可确定该映射为满射,或者直接证得s(A)=B欲证一个映射为单射时,按定义一般有两种方法,一是任取a,b属于定义域,且a¹b,能证得s(a)¹s(b)。另一种方法是:取s(a)=s(b)属于值域,证得21.设集合A={a,b,c},s与t为A®A的映射,a=b。若s={(a,c),(b,b),(c,b)},t={(a,b),(b,a),(c,c)},试求t×s与s×t;若s与t为A上的两个二元关系时,t×s与s×t又将怎样呢?根据复合映射的定义,有t×s={(a,c),(b,a),(c,a)},s×t={(a,b),(b,c),(c,b)}解若s与t为A上的两个二元关系时,则t×s={(a,b),(b,c),(c,b)},s×t={(a,c),(b,a),(c,a)}说明上述两种结果,当左端相同时,而右端不同,恰是一种交叉,其原因就是A®A复合关系定义符号的规定不同,请读者再一次仔细对比两种定义的的复合映射与A上的.com符号表示。s(x)=x2-2,t(x)=x+4,j(x)=xR®R的映射。t×ss×t,并分别判定是否为R®R的满射,单射,双射?3-5R22.设为(1)实数集,都是求,j-1(2)问是否存在?如果存在,试求出来。(1)因为s(x)=x2-2,t(x)=x+4解因此(t×s)(x)=(t(s(x))=t(x-2)=x-2+4=x+2222

19资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。按照开口向上的抛物线确定,t×s不是满射,也不是单射,更不是双射。(s×t)(x)=(s(t(x))=s(x-2)=(x+4)-2=x+8x+14222同样以开口向上的抛物线确定,s×t不是满射,不是单射,也不是双射。(3)因为R®R映射j(x)=x3-5是双射,故j-1存在,j-1(x)=3x+5。23．设映射s:A®B,t:B®C,s,t都是双射,求证(t×s)-1=s-1×t-1。证由于s,t都是双射,因此s,t均可逆,分别存在逆映射,s-1:B®A,t-1:C®B故复合映射s-1×t-1:C®A。因为s和t都是双射,因此(t×s)-1:A®C既然s-1×t-1与(t×s)-1都是C从A到的映射,对于任意cÎC,设t×s也是双射,且t×s:A®C,则t×s必有逆映射t-1(c)=b,t-1(b)=a,则有(s-1×t-1)(c)=s-1(t-1(c))=a-1(b)=a而(t×s)(a)=t(s(a))=t(b)=c可得出(t×s)-1(c)=a因此(s-1×t-1)(c)=c(c)由于cÎC是任意的,故有(t×s)-1s-1×t-1证毕。=课后答案网.com

20资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第三章命题逻辑1、判断下列语句是否是命题,如果是命题,指出其真值:(1)2是无理数;(2)存在最大质数;(1)中国是一个人口众多的国家;(2)这座楼真高啊!(3)你喜欢”蓝色的多瑙河”吗?(4)请你关上门。(5)地球以外的星球上也有人。解(1)是命题,真值为1。(1)是命题,真值为0。(2)是命题,真值为1。(3)、(5)、(6)均不是命题。(6)是命题,真值是惟一的,迟早会被指出。说明要判断一个语句是否是命题,首先要判断它是否是陈述句,然后再判断它的真值是否是惟一的。本题中,(4)、(5)、(6)均不是陈述句,无法分辨其真假,故都不是命题。陈述句不一定是命题,这里的关键是:客观上有无真假可言,而不以主观能否判断为标准。2、将下列命题符号化,并确定其真值:(1)5不是偶数;(2)天气炎热但湿度较低;课后答案网(4)如果a和b是偶数,则a+b是偶数;(3)2+3=5或者她游泳;(5)2+2=4,当且仅当3是奇数。解(1)设P:5是偶数。则(1)是:ØP,真值为1。(2)设P:天气炎热。Q:湿度较低。则(2)是:P∧Q。显然,只有在既炎热又湿度较低的情况下,P∧Q的真值为1,否则,其真值皆为0。(3)设P:2+3=5。Q:她游泳。则(3)是:P∨Q,真值为1。(4)设P:a和b是偶数。Q:a+b是偶数。则(4)是P®Q,真值为1。(5)设P:2+2=4。Q:3是奇数。则(5)是:P«Q,真值为1。3、设命题P,Q的真值为1,命题R,S的真值为0,试确定下面命题的真值:(1)G=(P∧Q∧R)∨Ø((P∨Q)∧(R∨S);(2)G=(﹁(P∧Q)∨ØR)∨(((﹁P∧Q)∨﹁R)∧S);(3)G=(Ø(P∧Q)∨ØR)∧((Q«ØP)®(R∨ØS));(4)G=(P∨(Q®(R∧ØP)))«(Q∨ØS)。.com解(1)P1Q1RS0P∧Q∧RP∨QR∨SØ((P∨Q)∧(R∨S)G100101故(1)的真值为1。(2)P1Q1RS0P∧Q(﹁P∧Q)∨ØRG1011

21资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。故(2)的真值为1。(3)P∧QØ(P∧Q)∨ØRQ«ØPR∨ØS(Q«ØP)®(R∨ØSGP1Q1R0S0110111故(3)的真值为1。P1Q1RS0P1P∨(Q®(R∧ØP))Q∨ØSG1011故(4)的真值为1。4、在什么情况下,下面的命题是真的:”说戏院是寒冷的或者是人们常去的地方是不对的,而且说别墅是温暖的或者戏院是讨厌的也是假的。”解设P:戏院是寒冷是;Q:戏院是人们常去的地方;R:别墅是温暖的;S:戏院是讨厌的;于是,题设命题为G=(﹁(P∨Q))∧(﹁(R∨S)),且G的真值为1。由此可知,命题(﹁(P∨Q))与(﹁(R∨S))的真值同时为1,即命题(P∨Q)与(R∨S)的真值同时为0,亦即命题P,Q,R,S的真值同时为0。故当”戏院是温暖的,戏院不是人们常去的地方,别墅是寒冷的,戏院是不讨厌的”时,题设命题是真的。说明比较复杂的复合命题,命题之间往往会同时用多个联结及圆括号加以联结。在确定这种形式命题的真值过程中,必然会涉及到真值计算的次序。如果出现的联结词相同,又无括号时,按从左到右的次序运算;若遇有括号时,优先进行括号中的运算。总之,应按运算次序逐次求出真值的中间结果,直至完成全部计算。5、构造下列公式的真值表,并解释其结果。(1)(P∧(P®Q))®Q;(2)﹁(P®Q)∧Q;(3)(P∨Q)«(Q∨R)课后答案网解(1)的真值表PQP®QP∧(P®Q)(P∧(P®Q))®Q00110101110100011111可见:(P∧(P®Q))®Q是恒真的。(2)的真值表P0011Q0101P®Q﹁(P®Q)﹁(P®Q)∧Q110100100000wwP®Q)∧Q是恒假的。w可见:﹁(.khdaw.com(3)的真值表P00001Q00110RP∨QQ∨R(P∨Q)«(Q∨R)00011101110101101010

22资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。111011101111111111可见:(P∨Q)«(Q∨R)是可满足的。说明从从依照递归形式所给出的公式的定义中,能够看出:公式是一个符号串,设有真值,不是命题,是命题的抽象,仅当我们对其中的各个原子,用确定的真(1)或假(0)代入解释(赋值)时,才得到一个命题。并将公式在其所有解释下所取真值列成的一个表,称为其真值表。构造真值表的步骤如下:(1)找出给定公式G中所有的原子A1,L,An(n≥1),列出所有可能的解释2(n个)。(2)按照从低到高的顺序列出G的各层次,最后为G本身。(3)根据五个逻辑联结词的真值表,计算出各层次的真值,直至计算出G的真值。在本题的三个真值表中,我们还会看到有三种不同类型的最后结果。其中(1)的最后一列全为1(真),(2)的最后一列全为0(假),(3)的最后一列既有1又有0,我们将其分别称为恒真的,恒假的和可满足的。因此,构造公式G的真值表,是判断公式G的类型的一种方法当然,真值表还有其它的用途,而判断公式的类型也还有其它的方法。6、用真值表判断下列公式是恒真?恒假?可满足?(1)(P®﹁P)®﹁P;(2)﹁(P®Q)∧Q;(3)(P∧﹁P)«Q;课后答案网(4)((P®Q)∧(Q®R))®(P®R)解(1)的真值表P﹁P1P®﹁P(P®﹁P)®﹁P0101110故公式(1)为恒真。(2)的真值表P0011Q0101P®Q﹁(P®Q)﹁(P®Q)∧Q110100100000故公式(2)为恒假。3)的真值表w(ww.khdaw.comP0011Q0101﹁P1P∧﹁P(P∧﹁P)«Q00001010100故公式(3)为可满足。(4)的真值表

23资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。P®QQ®R(P®Q)∧(Q®R)P®R((P®Q)∧(Q®R))®(P®R)P00001111Q00110011R010101011111001111011101110100011111010111111111故公式(4)为恒真的。说明设G:公式I:G的所有解释当真值T1(G)≡1时,称G为恒真的。T1(G)≡0时,称G为恒假的。{1T1(G)=时,称G为可满足的。0由定义可知,恒真的和恒假的公式有些很好的特性,如:(1)G∨﹁G恒真;G∧﹁G恒假。(若G表示原子,亦然);(2)G是恒真的«﹁G是恒假的;(3)两个恒真的公式的析取、合取、蕴涵、等值均为恒真的。公式恒真性的判定,是数理逻辑的重要问题。虽然我们能够用真值表法来判定这一问题,可是这种方法,对于原子数较多的公式,相当繁复。利用求与G等价范式的课后答案网方法,来解决判定问题在某些情况下会简单一些。7、证明下面的等价式:(1)(﹁P∧(﹁Q∧R))∨(Q∧R)∨(P∧R)=R;(2)(P∧(Q∧S))∨(﹁P∧(Q∧S))=Q∧S;(3)P®(Q®R)=(P∧Q)®R;(4)﹁(P«Q)=(P∧﹁Q)∨(﹁P∧Q)证(1)(﹁P∧(﹁Q∧R))∨(Q∧R)∨(P∧R)=(﹁P∧(﹁Q∧R))∨(Q∨P)∧R)=((﹁P∧﹁Q)∧R)∨(Q∨P)∧R)=((﹁P∧﹁Q)∨(Q∨P))∧R)=(﹁(P∨Q)∨(P∨Q))∧R(分配律)(结合律)(分配律)(德·摩根律)(互补律)(同一律)=1∧R=R(2)(P∧(Q∧S))∨(﹁P∧(Q∧S)).com=((Q∧S)∧P)∨((Q∧S)∧﹁P)=(Q∧S)∧(P∨﹁P)=(Q∧S)∧1(交换律)(分配律)(互补律)(同一律)=Q∧SP®(Q®R)(3)=﹁P∨(﹁Q∨R)=(﹁P∨﹁Q)∨R(蕴涵律)(结合律)

24资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。=﹁(P∧Q)∨R=(P∧Q)®R(德·摩根律)(蕴涵律)(4)﹁(P«Q)=﹁((P«Q)∧(Q«P)=﹁((﹁P∨Q)∧(﹁Q∨P))=﹁(﹁P∨Q)∨﹁(﹁Q∨P)=(﹁(﹁P)∧﹁Q)∨(﹁(﹁Q)∧﹁P)=(P∧﹁Q)∨(﹁P∧Q)G∨(G∧H)=G(等价律)(蕴涵律)(德·摩根律)(双重否定律)(交换律)8、证明(吸收律)证G∨(G∧H)=G∧1∨(G∧H)(同一律)(互补律)(分配律)(交换律)(等幂律)(分配律)(互补律)(同一律)证毕.=G∧(H∨﹁H)∨(G∧H)=(G∧H)∨(G∧﹁H)∨(G∧H)=(G∧H)∨(G∧H)∨(G∧﹁H)=(G∧H)∨(G∧﹁H)=G∧(H∨﹁H)=G∧1=G9、化简下列各式:(1)A∨(﹁A∨(B∧﹁B));(2)(A∧B∧C)∨(﹁A∧B∧C).解(1)A∨(﹁A∨(B∧﹁B))课后答案网=A∨(﹁A∨0)=A∨﹁A=1(互补律)(同一律)(互补律)(2)(A∧B∧C)∨(﹁A∧B∧C)=(A∧(B∧C))∨(﹁A∧(B∧C))(结合律)(分配律)(互补律)(同一律)=(A∨﹁A)∧(B∧C)=1∧(B∧C)=B∧C说明设有公式G,H,判定它们是否等价(即G=H),一般来说,常见下面的方法:1、真值表法分别瘵G,H的真值表列出,如果它们的真值表完全相同,则G与H等价,否则就不等。可是,当公式很繁杂,或所含符号很多时,真值表法的工作量太大。2、推演法依据基本等价式,在等价的意义下,对G进行推演,得到G=H的形式。.com3、主范式法分别求出G与H的主析(合)取范式,若她们相同,则G与H等价;若它们不同,则G与H不等价。4、范式法判断G«H恒真时,则G与H等价。另外,需要指出的是,公式G的等价形式是不唯一的。10、试将下列公式化为析取范式和合取范式:

25资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(1)P∧(P®Q);(2)﹁(P∨Q)«(P∧Q)(3)((P∨Q)®R)®P;(4)(P®Q)«(﹁Q®﹁P).解(1)P∧(P®Q)=P∧(﹁P∨Q)(蕴涵律)合取范式(分配律)析取范式=(P∧﹁P)∨(P∧Q)(2)﹁(P∨Q)«(P∧Q)=(﹁(P∨Q)®(P∧Q))∧((P∧Q)®﹁(P∨Q))(等值律)=((P∨Q)∨(P∧Q))∧(﹁(P∧Q)∨﹁(P∨Q))(蕴涵律)=(P∨Q)∧(﹁P∨﹁Q)(分配律)合取范式=(﹁P∨P)∨(﹁P∨Q)∨(﹁Q∧P)∨(﹁Q∧Q)(分配律)析取范式(3)((P∨Q)®R)®P=(﹁(P∨Q)∨R)®P=﹁(﹁(P∨Q)∨R)∨P=(﹁﹁(P∨Q)∧﹁R)∨P=((P∨Q)∧﹁R)∨P(蕴涵律)(蕴涵律)(德·摩根律)(双重否定律)(分配律)合取范式(分配律)析取范式=(P∨Q∨P)∧(﹁R∨P)=(P∧﹁R)∨(Q∧﹁R)∨P(4)(P®Q)«(﹁Q®﹁P)=(﹁P∨Q)«(﹁﹁Q∨﹁P)=(﹁P∨Q)«(Q∨﹁P)(蕴涵律)(双重否定律)=((﹁P∨Q)®(Q∨﹁P))∧((Q∨﹁P)®(﹁P∨Q))(等值律)课后答案网=(﹁(﹁P∨Q)∨(Q∨﹁P))∧((﹁Q∧﹁﹁P)∨(﹁P∨Q))(蕴涵律)=((﹁﹁P∧﹁Q)∨(Q∨﹁P))∧((﹁Q∧﹁﹁P)∨(﹁P∨Q))(德·摩根律)=((P∧﹁Q)∨(Q∨﹁P))∧((﹁Q∧P)∨(﹁P∨Q))=(P∨Q∨﹁P)∧(﹁Q∨Q∨﹁P)∧(﹁Q∧﹁P∨Q)∧(P∨﹁P∨Q)合取范式=(P∧﹁Q)∨(Q∧﹁Q∧P)∨(P∧﹁Q∧P)∨(﹁P∨Q)(分配律)析取范式(双重否定律)说明为得到任意一个公式G的范式(合取范式或析取范式)的步骤如下:(1)应用蕴涵律和等值律,删除G中的®和«,使G中只含有∨,∧,﹁。(2)应用双重否定律和(德·摩根律),将G中所有﹁移至原子之前,使G中每个子句和短语中不含﹁或只有一个﹁。(3)重复使用分配律,当欲得到合取范式时,用∨分配律;当欲得到析取范式时,用∧分配律。另外,一个公式的合取范式和析取范式都是不唯一的,当然其真值是相等的。因此利用范式来判定两个公式是否等价,并不方便,可是,任意一个公式和主范式是唯一的,.com解:首先介绍极大项的概念。从而解决了等价公式的判定问题。11、模仿主析取范式概念,引进主合取范式概念,并证明:对任意公式存在唯一一个与其等价的主合取范式。定义设P1,L,Pn是n个原子,一个子句如果恰好包含所有这n个原子及其否定,且排

26资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。列顺序与P1,L,Pn的顺序一致,则称此子句为关于P1P,L,的一个极大项。n例如,对原子P,Q,R而言,P∨﹁Q∨R,﹁P∨﹁Q∨R,P∨Q∨R都是关于的P,Q,R的极大项。可是,P,﹁P∨Q不是P,Q,R的极大项。而﹁P∨Q是关于P,Q的极大项。2显然,对于两个原子P,Q而言,其不同的解释有2个,如表3-4所示:表3-4P0011Q0101P∨QP∨﹁Q﹁P∨Q﹁P∨﹁Q0111101111011110由表3-4能够看出,任何两个不同的极大项都互不等价。并由此可进一步看n个原子P1,L,Pn而言,其不同的解释共有2n个。对于P1P,L,的任一个极大项M,2n个解n释中,有且仅有有个解释使M取0值。例如,对P,Q,R而言,P∨﹁Q∨R是极大项,解释(﹁P,Q,﹁R)使该极大项取0值,其它解释都使该极大项取1值。如果将真值1,0看作数,则第一个解释对应一个n位二进数。假设使极大项M取0值的解释对应的二进数为I,今后将M记为Mi.例如,对P,Q,R而言,P∨﹁Q∨R是极大项,解释(0,1,0)使该极大项取0值,解释(0,1,0)对应的二进数是2,于是,P∨﹁Q∨R记为M2。课后答案网对P,Q,R而言,8个极大项与其对应的解释如表3-5所示:表3-5简释极大项二进数000记法﹁P﹁Q﹁R﹁P﹁Q﹁PQ﹁R﹁PP﹁Q﹁R﹁Q﹁P∨﹁Q∨﹁RM0R﹁P∨﹁Q∨R﹁P∨Q∨﹁R﹁P∨Q∨R001010011100M1M2M3M4QRP∨﹁Q∨﹁RwwPwR.P∨﹁Qk∨Rhd10a1110111w.comM5PPQQ﹁RP∨Q∨﹁RM6RP∨Q∨RM7因此,一般地,对P1,L,Pn而言,2n个极大项为M0,M1,…,2n-1.M

27资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。下面,给出主合取范式的概念。定义设公式G中所有不同原子为PL,Pn,如果G的合取范式G¢中的每个子句都是,1关于PL,Pn关于的一个极大项,则称G¢为G的关于P1P,L,的主合取范式。,1n定理对于任意公式G,都存在等价于它的主合取范式。证因为G=﹁(﹁G)=,由教材第103页定理4知,(﹁G)有唯一的等价的主析取范式,即﹁G=mÚLÚm(Ømi1)ÙLÙ(Øm)ik,于是由德·摩根律,有G=﹁(﹁G)=。iki1这里(Øi1),L,(Øik)是极大项。mm定理设公式G,H是关于原子PL,Pn的两个主合取范式,如果G,H不完全相同,,1则G,H不等价。证因为G,H不完全相同,因此或者G中有一个极大项不在H中;或者相反。不妨设极大项Mi在G中而不在H中,于是根据极大项的性质,二进数I所对应的关于PL,Pn的解释Ii,使MiIMi的极,取0值,从而使公式G取0值,使所有不是1i大项取1值,因此使公式H取1值,故G,H不等价。由上述两个定理可立即得如下定理。定理对任意公式G,都存在唯一一个与G等价的主合取范式。12、(1)已知:若A∨B=A∨C,﹁A∨B=﹁A∨C,则B=C。试写出其对偶式,并予以证明。课后答案网(3)试证明:1o®﹁(P∧Q)(﹁P∨(﹁P∨Q))=﹁P∨Q;2o(P∨Q)∧(﹁P∨(﹁P∨Q))=﹁P∧Q。解(1)对偶式为:若A∧B=A∧C,﹁A∧B=﹁A∧C,则B=C。证明如下:B=B∧(A∨﹁A)=(B∧A)∨(B∧﹁A)=(A∧B)∨(﹁A∧B)=(A∧C)∨(﹁A∧C)=(A∨﹁A)∧C=C。(2)证1o因为﹁(P∧Q)®(﹁P∨(﹁P∨Q))=(P∧Q)∨(﹁P∨(﹁P∨Q))=(P∧Q)∨(﹁P∨Q)=(﹁P∨Q)∨(P∧Q)=﹁P∨(Q∨(P∧Q))=﹁P∨Q.comooo221由之证明及对偶性质,故成立。说明(1)考察公式G与G*是否对偶式,首先要求G与G*®«中不含和,因此,o1在本例(2)中,使用基本等价式将删除。®(2)由对偶的性质:若G=H,则G*H*。于是,我们只须证明G=H,而G*==H*则不证自

28资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。明。13、设公式G的真值表如下,(P,Q,R是出现在G中的所有原子),试求出G的主析取范式和主合取范式。PQ00110011R01010101G1011010000001111解将真值表中最后一列的1左侧的二进数,所对应的极小项写出后,将其析取起来,就得到G的主析取范式。于是,G=(﹁P∧﹁Q∧﹁R)∨(﹁P∧Q∧﹁R)∨(﹁P∧Q∧R)∨(P∧﹁Q∧R)。将真值表中最后一列的0左侧的二进数,所对应的极大项写出后,将其合取起来,就得到G的主合取范式。于是,G=(P∨Q∨﹁R)∧(﹁P∨Q∨R)∧(﹁P∨﹁Q∨R)∧(﹁P∨﹁Q∨﹁R)。说明在写成极大项时,应依据下列规则:若原子的真值为0,则记入该原子;若原子的真值为1,则记入该原子的否定。14、求Q∧(P∨﹁Q)的主合取范式。解方法一(推导法):Q∧(P∨﹁Q)=(Q∨(P∧﹁P))∧(P∨﹁Q)=(P∨Q)∧(﹁P∨Q)∧(P∨﹁Q)课后答案网主合取范式方法二(真值表法):可经过两步来完成。(1)求﹁(Q∧(P∨﹁Q))的主析取范式;(2)求(1)之否定。由﹁(Q∧(P∨﹁Q))的真值表PQ00011011﹁QP∨﹁QQ∧(P∨﹁Q)﹁(Q∧(P∨﹁Q))1010101100011110故﹁(Q∧(P∨﹁Q))的主析取范式为:(﹁P∧﹁Q)∨(﹁P∧Q)∨(P∧﹁Q)因而,Q∧(P∨﹁Q)的主合取范式为:.com﹁((﹁P∧﹁Q)∨(﹁P∧Q)∨(P∧﹁Q))=(P∨Q)∧(﹁P∨Q)∧(P∨﹁Q)15、不使用真值表,试求出公式G=(﹁P®R)∧(Q«P)的主合取范式,并利用其主合取范式,求得其主析取范式。G=(﹁P®R)∧(Q«P)=(﹁P®R)∧(Q®P)∧(P®Q)解=(P∨R)∧(﹁Q∨P)∧(﹁P∨Q)=(P∨R∨(Q∧﹁Q))∧(﹁Q∨P∨(R∧﹁R))∧(﹁P∨Q∨(R∧﹁R))

29资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。=(P∨R∨Q)∧(﹁Q∨P∨R)∧(﹁Q∨P∨﹁R)∧(﹁P∨Q∨R)∧(﹁P∨Q∨﹁R)将在上式中没有出现的三个极大项合取起来,就能够得到﹁G=(P∨Q∨﹁R)∧(﹁P∨﹁Q∨R)∧(﹁P∨﹁Q∨﹁R)。于是,G=﹁(﹁G)=﹁﹁((﹁P®R)∧(Q«P)=﹁((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)(主析取范式)说明事实上,只要掌握了求公式的主析(合)取范式的方法那么求主合(析)取范式也就迎刃而解了。设公式G:P1,L,Pn如果G的主析(合)取范式是已知的,则将一些在G的主析(合)取范式中没有出现的极小项(极大项),析取(合取)起来,便可心得到﹁G的主析(合)取范式。再根据﹁(﹁G),并对﹁G的主析(合)取范式重复使用德·摩根律,就能够得到G的主合(析)取范式。16、试将下列公式化为主析取范式和主合取范式:(1)(P∧Q)∨(﹁P∧R);(2)P∨(﹁P®(Q∨(﹁Q®R)))解(1)(P∧Q)∨(﹁P∧R)的真值表如下:PQ0000010110101111R01010101P∧Q﹁P∧R(P∧Q)∨(﹁P∧R)00001001010011课后答案网0001110000故主析取范式为:(﹁P∧﹁Q∧R)∨(﹁P∧Q∧R)∨(P∧Q∧﹁R)∨(P∧Q∧R)主合取范式为:(P∨R∨Q)∧(﹁Q∨P∨R)∧(﹁P∨Q∨R)∧(﹁P∨Q∨﹁R)(3)P∨(﹁P®(Q∨(﹁Q®R)))(4)=P∨(P∨(Q∨(﹁Q®R)))=P∨Q∨R主合取范式=(﹁P∧﹁Q∧R)∨(﹁P∨Q∨﹁R)∨(﹁P∧Q∧R)∨(P∧﹁Q∧﹁R)∨(P∧Q∧﹁R)∨(P∧Q∧R)主析取范式.com说明(1)对任意一个公式G,都存在唯一一个与G等价的主范式。(2)求公式G的主范式的常见方法:①、推导法;②、真值表法。17、证明:公式G恒真当且仅当至少有一个原子等价于它的合取范式中,每个子句均至少一个原子及其否定。证(引理)子句是恒真的当且仅当至少有一个原子及其否定,同时在此子句中出现。证充分性若有一个原子P及其否定﹁P,同时出现在子句中,则此子句有形式P∨﹁P。显然,不论是什么解释I,P∨﹁P在I下都取1值,于是,此子句在I下取1值,故此子句

30资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。恒真。必要性若子句为恒真,而任意原子及其否定均不同时在此子句中出现。那么,取这样的解释I:指定带有否定符的原子取1值,不带否定符的原子取0值,显然此子句在这个解释I下取0值,与此子句恒真矛盾。设公式G的合取范式如下:G=GÙLÙG,其中是子句,i=1,L,n,显然公式G恒真的充要条件是每个Gi1nG恒真,再根据引理,此定理成立。证毕。i18、利用求公式的范式的方法,判断下列公式是恒真?恒假?可满足?(1)﹁(P®Q)∧Q;(2)((P∨Q)®R)®P(3)(P®Q)®(﹁Q®﹁P)解(1)﹁(P®Q)∧Q=﹁(∨Q)∧Q=(﹁﹁P∧﹁Q)∧Q=P∧﹁Q∧Q于是,原式为恒假。(2)((P∨Q)®R)®P=﹁(﹁(P∨Q)∨R)∨P=(﹁﹁(P∨Q)∧﹁R)∨P=((P∨Q)∧﹁R)∨P=(P∨Q)∧(﹁R∨P)=(P∧﹁R)∨(Q∧﹁R)∨P∨(P∧Q)于是,原式为可满足。(3)(P®Q)®(﹁Q®﹁P)=﹁(﹁(P∨Q)∨(﹁﹁Q∨﹁P)课后答案网=(﹁﹁P∧﹁Q)∨(﹁﹁Q∨﹁P)=(P∧﹁Q)∨(Q∨﹁P)=(P∨Q∨﹁P)∧(﹁Q∨Q∨﹁P)于是,原式为恒真。说明如果在与G等价的合取范式中,每个子句均少包含一个原子及其否定,则该合取范式的每个子句均是恒真的,此时G是恒真的;如果在与G等价的析取范式中,每个短语均至少包含一个原子及其否定,则该析取范式的每个短语均是恒假的,此时G是恒假的。19、证明蕴涵式P®(Q®R)Þ(P®Q)®(P®R)证方法一(真值表法)设S=(P®(Q®R)Þ(P®Q)®(P®R))PQ000001R010Q®RP®(Q®R)P®QP®R(P®Q)®(P®R)S110111111111111111.com011010111110101111011110110011101011110111111从表上观察出:T①对任意解释I,都有1(P®(Q®TR))≤1((P®Q)®(P®R)),故由教材中的蕴

31资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。涵定义1,知P®(Q®R)Þ(P®Q)®(P®R)T②对任意解释I,都有1(P®(Q®TR))=1,则1((P®Q)®(P®R))=1,故由教材中的蕴涵定义2,知P®(Q®R)Þ(P®Q)®(P®R)③从最后一列可知,公式S恒真,故由教材中的蕴涵定义3,知P®(Q®R)Þ(P®Q)®(P®R)方法二(推导法)S=(P®(Q®R)Þ(P®Q)®(P®R))=(﹁P∨(﹁Q∨R))®((﹁P∨Q)®(﹁P∨R)=﹁(﹁P∨﹁Q∨R)∨(﹁(﹁(P∨Q)∨(﹁P∨R)=(P∧Q∧﹁R)∨((﹁P∨P∨R)∧(﹁P∨R∨﹁Q)=(P∧Q∧﹁R)∨(﹁P∨﹁Q∨R)=(P∧Q∧﹁R)∨﹁(P∧Q∧﹁R)因此,S恒真,故由蕴涵定义3,知P®(Q®R)Þ(P®Q)®(P®R)说明要证明公式间的蕴涵关系,即GÞH,可采用真值表法、推导法等办法,而无论采用哪种办法,只须论证它符合GÞH的三种定义即可。20、证明蕴涵式(1)(P®Q)∧﹁QÞ﹁P;(2)(P®Q)®QÞP∨Q;(3)(Q®(﹁P∨P))®(R®(﹁P∨P))Þ(R®Q)(4)P∧(P®Q)ÞQ。证(1)((P®Q)∧﹁Q)®﹁P=﹁((P®Q)∧﹁Q)∨﹁P=﹁(P®Q)∨Q∨﹁P课后答案网=(P∧﹁Q)∨Q∨﹁P=(P∨Q∨﹁P)∧(﹁Q∨Q∨﹁P)因合取范式的每个子句均含某一原子及其否定,因此((P®Q)∧﹁Q)®﹁P恒真。即(P®Q)∧﹁QÞ﹁P(2)((P®Q)®Q)®(P∨Q)=((﹁P∨Q)®Q)®(P∨Q)=(﹁(﹁P∨Q)∨Q)®(P∨Q)=﹁(﹁(﹁P∨Q)∨Q)∨(P∨Q)=(﹁P∨Q∨P)恒真,因此(P®Q)®QÞP∨Q(3)(Q®(﹁P∨P))®(R®(﹁P∨P))®(R®Q)=((﹁Q∨(﹁P∨P))®(﹁R∨(﹁P∨P)))®(R®Q)=((﹁Q)®(﹁R))®(R®Q).com=(Q∨﹁R)®(﹁R∨Q)显然恒真,因此(Q®(﹁P∨P))®(R®(﹁P∨P))Þ(R®Q)(4)设P∧(P®Q)为真,则P与(P®Q)均为真,由此可知,Q必为真,因此P∧(P®Q)®Q为真,故P∧(P®Q)ÞQ证毕。21、试证:设公式G1,G2,G3,如果G1ÞG2,G2ÞGGG3,则有3。Þ1证此题等价于(G®1®G2)∧(G2®G3)ÞG1G3恒真

32资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。假定(G®G2)∧(G®G3)真,G®GGG2与G2G3假,亦即3都®®1121真,G®G3假,则有G3假,G1真。1而当G1真,则因为G®G2真,故当G2为真时,G®GG3为假,这与®2G3真矛盾。证毕12于是,G®GGG33真,即Þ11说明前面,我们已经给出了证明蕴涵的一些方法。可是在前提较多而又公式较复杂时,使用真值表法会相当繁琐,因此,在这种情况下应该更多地采用形式演绎法。例22用形式演绎法证明1.{C∨D,(C∨D)→﹁H,﹁H→(A∧﹁B),(A∧﹁B)→(R∨S)}蕴涵R∨S;2.{P∨Q,P→﹁R,S→t,﹁S→R,﹁t}蕴涵Q;3．{P®Q,R®S,P∨R}蕴涵Q∨S;4．若春暖花开,则燕子就会飞回北方。若燕子飞回北方,则冰雪融化。人民民主冰雪没有融化,则没有春暖花开。证1、{C∨D,(C∨D)→﹁H,﹁H→(A∧﹁B),(A∧﹁B)→(R∨S)}蕴涵R∨S;(1)P、(C∨D)→﹁H(2)﹁H→(A∧﹁B)规则P规则P(3)(C∨D)→(A∧﹁B)规则Q,根据(1),(2)和基本蕴涵式(13)(4)(A∧﹁B)→(R∨S)(5)(C∨D)→(R∨S)(6)C∨D规则P,根据(3),(4)和基本蕴涵式(13)规则Q,根据(3),(4)和基本蕴涵式(13)规则P课后答案网2、{P∨Q,P→﹁R,S→t,﹁S→R,﹁t}蕴涵Q(7)R∨S规则Q,根据(5),(6)和基本蕴涵式(11)(1)S→t(2)﹁t规则P规则P(3)﹁S规则Q,根据(1),(2)和基本蕴涵式(12)(4)﹁S→R(5)R规则P规则Q,根据(3),(4)和基本蕴涵式(11)规则P(6)P→﹁R(7)﹁P规则Q,根据(5),(6)和基本蕴涵式(12)规则P(8)P∨Q(9)Q规则Q,根据(7),(8)和基本蕴涵式(10)3、{P®Q,R®S,P∨R}蕴涵Q∨S(1)P∨R规则P(2)﹁R→P规则Q,根据(1)和基本等价式(蕴涵律).com(3)P®Q(4)﹁R→Q(5)﹁Q→R规则P规则Q,根据(2),(3)和基本蕴涵式(13)规则Q,根据(4)(6)R®S(7)﹁Q→SQ∨S规则P规则Q,根据(5),(6)和基本蕴涵式(13)规则Q,根据(7),(8)和基本等价式(蕴涵律)(8)

33资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第四章一阶逻辑1.用谓词表示式写出下列命题:(1)王文不是学生;(2)2是素数且是偶数;(3)若m是奇数,则2m不是奇数;(4)河北省南接河南省;(5)若2大于3.则2大于4.解(1)P(x):x是学生a:王文于是(1)为:ØP(a).K(2)H(x):x是素数M(x):x是偶数a:2于是(2)为:H(a)ÙM(a)R(x):x是奇数于是(3)为:R(m)®ØR(2m).L(x,y):x南接yc:河北省于是(4)为L(c,d).S(x,y):x大于y(3)(4)d:河南省(5)a:2b:3c:4于是(5)为:S(a,b)®S(a,c).说明从语法上看,每个被视为命题的语句,是由主语和谓语两部分组成的。其中,主语是语句中的主动者,称为个体。谓语是用来表明主语的性质或用来说明几个主语之间的关系,称为谓词。例如前例(1)中的”王文”,(4)中的”河北省”、”河南省”都是个体;而其中的课后答案网”LL南接LL”都是谓词。在一阶逻辑中,表示具体的、特指的个体的词是个体常量;表示抽象的或泛指的或在一定范围内变化的词是个体变量。个体变量的取值范围是定义域。例如前例(2)中的”2”是个体常量;(3)中的”m”是个体变量,它的定义域是整数集。表示个体性质的谓词,一般形如G(x),是一元谓词或一元命题函数。表示n个个体之间关系的谓词,一般形如P(x1,LL,xn),是n元谓词或n元命题函数。谓词函数不是命题,实际上是一种不确定的命题形式,可是当其中的变量x被某个常量替换时,谓词函数便转化为命题。例如,”x是有理数”是一元谓词,记作G(x),其中G表示谓词”L是有理数”,D:实数集,G(x):x是有理数,是一元谓词(不是命题,没有真值)。3ÎD,G(3):3是有理数,是命题,真值为1。.com由于命题逻辑是一阶逻辑的特例(命题可看作是无变量的谓词或0元谓词),因此,命题逻辑中的联结词在一阶逻辑中均可使用。注意,n元谓词中,与谓词想联系着的几个个体名称的次序是不能随意变动的,如前例中的(4)。2.用谓词表示式写出下列命题:(1)凡是有理数都能够写成分数;(2)存在着会说话的机器人;

34资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(3)并非每个实数都是有理数;(4)如果有限个数的乘积为零,那么至少有一个因子等于零;(5)没有不犯错误的人。解(1)G(x):x有理数H(x):x能够写成分数于是(1)为:"x(G(x)®H(x))(2)F(x):x会说话Q(x):x是机器人于是(2)为:$x(F(x)ÙQ(x))。(3)R(x):x是实数Q(x):x是有理数于是(3)为:Ø("x)(R(x)®Q(x))(4)N(x):x是有限个数的乘积(或为:$x(R(x)ÙØQ(x))).Z(y):y为0P(x):x的乘积为0F(y):y为乘积中的一个因子于是(4)为:"x(N(x)ÙP(x))®$y(F(y)ÙZ(y))。(5)M(x):x为人F(x):x犯错误于是(5)为:Ø($x(M(x)ÙØF(x)))(或为:"x(M(x)®F(x))).说明引进了谓词,还要引进量词,这样才能建立起一阶逻辑。全称量词和存在量词统称为量词。全称量词"x表示”对任意x”、”对每一个x”、”对于因此的x”等语句;存在量词$x表示”存在一个x”、”对于一些x”、”至少有一个x”等语句。课后答案网设G(x)是一元谓词,任取x0D则G(x)是一个命题。于是,"xG(x)是命题:Î,0”对任意xÎD,,都有G(x)。命题"xG(x)的真值规定如下:"xG(x)$xG(x)Û对任意xÎD,G(x)都取1值;"xG(x)取0值Û有一个x0ÎD,使得G(x0)取0值;$xG(x)是命题:”存在一个x0ÎD,使得G(x0)成立”。命题$xG(x)的真值规定如下:$xG(x)$xG(x)Û有一个x0ÎD,使得G(x0)取1;$xG(x)取0值Û对所有xÎD,G(x)都取0值。.com在使用量词时,由于定义域的不同,命题符号化的形式可能不一样。如命题”凡是有理数都能够写成分数”。①当定义域D:有理数集H(x):x能够写成分数,则有"xH(x)。②当定义域D:实数集

35资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。G(x):x是有理数H(x):x能够写成分数,则有"xG(x)®H(x))。③当定义域D:非空个体名称集(即一切事物的集合)时,则同②。一般来说,谓词的定义域D能够是有限集,如{1,2,3,4}、{a,b,c}、{狗,5,计算机}等;也能够是无限集,如有理数集、实数集等。不过,这种约定的定义域并不常见。这时,我们认为个体x的定义域是一切事物。3．设谓词的定义域都是{a,b,c},试将下面的表示式中的量词消除,写成与之等价的命题公式。⑴"xP(x);⑵"xR(x)Ù"xS(x);⑶"xR(x)Ù$xS(x);⑷"x(P(x)®Q(x));⑸"xØP(x)Ú"xP(x);⑹"xF(x)®$yG(y);⑺$x"yH(x,y).课后答案网解⑴"xP(x)=P(a)ÙP(b)ÙP(c).⑵"xR(x)Ù"xS(x)=R(a)ÙR(b)ÙR(c)ÙS(a)ÙS(b)ÙS(c).⑶"xR(x)Ù$xS(x)=(R(a)ÙR(b)ÙR(c))Ù(S(a)ÚS(b)ÚS(c)).⑷"x(P(x)®Q(x))=(P(a)®Q(a))Ù(P(b))®Q(b))Ù(P(c)®Q(c)).⑸"xØP(x)Ú"xP(x)=(ØP(a)ØP(b)ÙP(c))Ú(P(a)ÙP(b)ÙP(c)).⑹"xF(x)®$yG(y)=(F(a)ÙF(b)ÙF(c))®(G(a)ÚG(b)ÚG(c)).⑺$x"yH(x,y)=(H(a,a)ÙH(a,b)ÙH(a,c))Ú(H(b,a)ÙH(b,b)ÙH(b,c))Ú(H(c,a)Ù(H(c,b)ÙH(c,c)).com4.指出下列命题的真值:⑴$x(P(x)®Q(x))其中,P(x):xf3H(x):x=4定义域:D={2};⑵"x(P(x)ÚQ(x)),其中,P(x):x=1Q(x):x=2定义域:D={1,2};⑶"x(P®Q(x))ÚR(e))其中,P:3f2Q(x):x≤3R(x):xf5e:5定义域:D={-2,3,6}.

36资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。解⑴$x(P(x)®Q(x))=(P(2)®Q(2))=(0®0)=1。⑵"x(P(x)ÚQ(x))=(P(1)ÚQ(1))Ù(P(2)ÚQ(2))=(1Ú0)Ù(0Ú1)=1Ù1⑶"x(P®Q(x))ÚR(e))=(P®Q(-2))Ù(P®Q(3))Ù(P®Q(6))ÚR(5)。因为在上式中,P真,Q(-2)真,Q(3)真,Q(6)假,R(5)假,因此,原式=(1®1)Ù(1®1)Ù(1®0)Ú0=0Ú0。说明当定义域为有限集时,如D={a1,L,an},由量词的定义能够看出,对任意的谓词G(x),都有:⑴"xG(x)=G(a1)ÙLÙG(an);⑵$xG(x)=G(a1)ÚLÚG(an).这实际上是将一阶逻辑中的命题公式转化为等价的命题落雷中的命题公式。若在表示式中有多个量词,则能够按其层次,逐层将量词消除。例如D={a,b},"x$yP(x,y)="x(P(x,,a)ÚP(x,,b))=(P(a,a))ÚP(a,b))Ù(P(b,a)ÚP(b,b))5．将下列表示式中的变量适当改名,是的约束变量不是自由的,自由变量不是约束的⑴$xF(x)ÙG(x,y);⑵"x(P(x)®R(x,y))ÙQ(x,y);⑶"x$y(P(x,z)®Q(y))«S(x,y);⑷"x(P(x)®(R(x)ÚQ(x)Ù$xR(x))®$zS(x,z);⑸ØR(x,y,z)Ù$xQ(x,y)®$yQ(x,y)).课后答案网解(1)的改名为:$zF(z)ÙG(x,y);⑵的改名为:$z(P(z)®R(z,y)ÙQ(x,y);⑶的改名为:"u$v(P(u,z)®Q(v)«S(x,y);⑷的改名为:"u(P(u)®R(u)ÚQ(u))Ù$vR(v))®$zS(x,z);⑸的改名为:ØR(x,y,z)Ù$tQ(t,y)®"u(R(u,y,z)®$vQ(u,v))。说明在符号"xG(x)或$xG(x)中的G(x)是量词"x或$x的作用范围,称谓辖域。当量词后面有括号时,则括号内的公式为此量词的辖域,此时在辖域内出现的个体变量x.com是约束的,或者说x的出现是约束的;当辖域内不含有"y和$y时,在辖域内出现的个体变量是自由的,或者说y是自由的(可视为参数)。如("xP(x,y)®$yQ(x,y,z)))ÙS(x,z),其中,$y的辖域是Q(x,y,z),"x的辖域是P(x,y)®$yQ(x,y,z).

37资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。从左向右算起,变量x的第一、第二次出现是约束的,第三次的出现是自由的;变量y的第一次出现是自由的,第二次出现是约束的;变量z在全式中的出现都是自由的。为避免出现这样一个变量在同一个公式中具有的双重身份,在一阶逻辑中,合理的引出了约束变量的改名规则。从而能够做到,在一阶逻辑中的表示式里,每个变量都能够只以一种面目出现,即约束都不是自由的;由变量也都不是约束的。6．设I是如下一个解释:D:实数集Raf(x,y)x-yF(x,y)2xpy试确定下列公式在I下的真值⑴"xF((a,x),a);⑵"x"y(ØF(f(x,y)x));(3)"x"y"z(F(x,y)®F(f(x,z),f(y,z)));课后答案网(4)"x$yF(x,f(f(x,y),y)).解(1)因为在I下,对任意的xÎR及aÎR,有f(a,x)=a-x,F(f(a,x):a-xpa,将2代入,得2-xp2,即-xp0,显然为假,因此"xF((a,x),a)="x(-xp0),真值为0。(2)因为在I下,对任意的x,yÎR,F(f(x,y),x):x-ypx,ØF(f(x,y),x):x-y³x,为假,因此,"x"y(ØF(f(x,y),x)="x"y(x-y³x)真值为0。(3)因为在I下,F(x,y):xpy,f(x,z):x-z,f(y,z):y-z,F(f(x,z),f(y,z):x-zpy-z,即xpy.显然,对任意的x,y,zÎR,(x-y)®(x-zpy-z)为真。所以,.com"x"y"z(F(x,y)®F(f(x,z),f(y,z)))="x"y"z(xpy)®(x-zpy-z))真值为1。(4)因为在I下,f(x,y)=x-y,f(f(x,y),y)=(x-y)-y=x-2y,F(x,f(f(x,y),y)):xpx-2y.对任意的xÎR,令y=-1,均有xpx-2y。所以

38资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。"x$yF(x,f(f(x,y),y))="x$y(xpx-2y)真值为1。7．设I是如下一个解释:D:自然数集Naf(x,y)x+yg(x,y)F(x,y)x=y3x•y试确定下列公式在I下的真值。(1)"xF(g(x,a),x);(2)"x"y(F(f(x,a),y®F(f(y,a),x));(3)"x"y$zF(f(x,y),z;(4)"x"yF(f(x,y),g(x,y)).课后答案网解(1)因为在I下,对任意的xÎN及aÎN,有g(x,a)=x•a,F(g(x,a),x):x•a=x,将a代入,x•3=x,显然为假。因此"xF(g(x,a),x)="x(x•3=x)真值为0。(2)因为在I下,对任意的x,yÎN,及aÎN,f(x,a)=x+a,f(y,a)=y+a,F(f(x,a),y):x+a=y,F(f(y,a),x):y+a=x,将a=3代入,F(f(x,a),y®(F(y,a),x):x+3=y®y+3=x为假。所以,"x"y(F(f(x,a),y®F(f(y,a),x))="x"y(x+3=y®y+3=x)真值为0。(3)公式可化为:"x"y$z(x+y=z),真值为1。.com8．设I是如下一个解释:(4)公式可转化为:"x"y(x+y=x·y),真值为0。D:{3,2}abf(3)f(2)P(3,3)P(3,2)p(2,3)P(2,2)

39资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。32231100试求出下列公式在I下的真值。(1)p(a,f(a))Ùp(b,f(b));(2)"x$P(y,x);(3)"x"y(p(x,y)®p(f(x),f(y)).解(1)p(a,f(a))Ùp(b,f(b))=p(3,f(3))Ùp(2,f(2))=p(3,2)Ùp(2,3)=1Ù0(2)"x$P(y,x)="xP(3,x)ÚP(2,x)=(P(3,3)ÚP(2,3))ÙP(3,2)ÚP(2,2))=(1Ú0)Ù(1Ú0)=1Ù1=1.(3)"x"y(p(x,y)®p(f(x),f(y))="x(P(x,3)®P(f(x),f(3)))Ù(P(x,2))®P(f(x),f(2))))=P(f(2),f(3)))Ù(P(2,2)课后®P(3,2))Ù(P(2,2)P(3,3)®P(f(3),f(3)))Ù(P(3,2)®P(f(3),f(2)))P(2,3)®P(2,2)Ù(P(3,2)®P(2,3))ÙP(2,3)Ù®®P(f(2),f(2)))=®答案P(3,3)网®®®1)Ù(0®1)=0Ù0Ù1Ù1=0.0)Ù(10)Ù(09．设G=$xP(x)®"xP(x)P(3,3))=(1(1)若解释I的非空区域D包含仅仅一个元素,G在I下取1值;(2)设D={a,b},试找出一个D上的解释I,使G在I取0值。解(1)因为在解释I下,D={a},因此$xP(x)=P(a),P(x)=P(a),故G=$xP(x)®"xP(x)=P(a)®P(a),取1值。(2)设D={a,b},于是在解释I下,$xP(x)=P(a)ÚP(b),"xP(x)=.com®P(a)ÙP(b).故G=$xP(x)®"xP(x)=(P(a)ÚP(b))(P(a)ÙP(b))。于是,当解释I是如下一个解释:D={a,b}P(a)p(b)

40资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。10时,G=$xP(x)®"xP(x)取0值。说明由递规定义给出的公式是抽象的符号串,没有什么意义。可是,当我们对这个符号串中的符号做出具体的解释,即给出一个集合D,将公式中的常量符号赋以D中某个元素,变量符号的变化范围指定为D,函数符号赋以D上的一个具体函数,为此符号赋以D上一个具体谓词时,公式就有了确定的真值。我们已经知道,命题逻辑的公式恒真性是可解的,然而一阶逻辑的公式恒真性却是不可解的。这是因为,在一阶逻辑中,为判定公式是否恒真,需要考虑公式的所有解释,可是,这是人类所无法实现的,也就是说采用判定命题逻辑的公式恒真性的真值表,对一阶逻辑的公式是不存在的。当然,对某些特殊的公式还是能够判定的。®10．设G1="x(P(x)Q(x)),G2=ØQ(a).证明:ØP(a)是G1和G2的逻辑结果。分析欲证ØP(a)是G1和G2的逻辑结果,当且仅当(G1ÙG2)ÞØP(a)。证设I是G1,G2的任一个解释,而且I满足G1ÙG2,即I满足"x(P(x)®Q(x))ÙØQ(a),以下证明I满足ØP(a)。否则,令ØPa)为真,于是,因为ØQ(a)为真,因此,(a)在I下为假,即答案P(课后网I下(P(a)®Q(a))为假。故"x(P(x)®Q(x))在I下为假,矛盾。故ØP(a)在I下亦为真,由蕴涵定义知(G1ÙG2)ÞØP(a),即ØP(a)是G1和G2的逻辑结果。证毕。11．证明一阶逻辑蕴涵公式:(1)$x(A(x)ÙB(x))Þ$xA(x)Ù$xB(x);(2)"x(A(x)®B(x))Þ"xA(x)®"xB(x);(3)$xP(x)Ù"xQ(x)Þ$x(P(x)ÙQ(x));www.(4)$xA(x)"xB(x)Þ"x(A(x)®khd®aw.comB(x)).证(1)设I是A(x),B(x)的任一解释,而且I满足$x(A(x)ÙB(x))。于是,在解释I下所指定的区域D中,存在x取1值,B(x)取1值。因此在解释I下,$xB(x)取1值。故解释I使$xA(x)Ù$xB(x)使(ÎD,Ax)ÙB(x)取值,从而A(x)010000取1值。故$x(A(x)ÙB(x))Þ$xA(x)Ù$xB(x)。

41资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(2)设I是A(x),B(x)的任一解释,而且I满足"x(A(x)®B(x))Ù"xA(x)。于是I满足"x(A(x)®B(x)),并同时满足"xA(x),即对所有xÎD,A(x)®B(x)取1值,同时A(x)取1值,,即I满足"xB(x)。因为I的任意性,因此,"x(A(x)®Ù"xA(x)Þ"xB(x),亦即"x(A(x)®B(x))Þ"xA(x)®"xB(x)。B(x))(3)设I是P(x),Q(x)的任一解释,而且I满足$xP(x)Ù"xQ(x)。于是I满足$xP(x),并同时满足"xQ(x),亦即在解释I下所指定的区域D中,存在x0ÎD,使P(x0)取1值,并同时使Q(x0)取1值。因此,在I下,P(x0)ÙQ(x0)取1值,亦即在I下,使$x(P(x)ÙQ(x))取1值。故"x(A(x)®B(x))Þ"xA(x)®"xB(x)。(4)设I是P(x),Q(x)的任一解释,而且I满足"xA(x)®"xB(x)。而在I下,$xA(x)®"xB(x)=Ø$xA(x)Ú"xB(x)="x(ØA(x))Ú"xB(x)。由基本蕴涵式,有"x(ØA(x))Ú"xB(x)Þ"x(ØA(x)Ú"xB(x)),在I下,"x(ØA(x))Ú"xB(x)="x(A(x)®B(x))。于是,由蕴涵关系的传递性,对任意解释I,有$xA(x)®"xB(x)Þ"x(A(x)®B(x))。12证明(1)$x(A(x)®B(x))="x(A(x)®$xB(x);(2)$xA(x)®B="x(A(x)®B);课后答案网(3)"x"y(P(x)®Q(y))=$xP(x)®"yQ(y).证(1)$x(A(x)®B(x))=$x(ØA(x)ÚB(x))=$x(ØA(x))Ú$xB(x)=Ø"x(A(x)Ú$xB(x)="x(A(x)®$xB(x);(2)$xA(x)®B=Ø$xA(x)ÚB="xØA(x)ÚB="x(ØA(x)ÚB)="x(A(x)®B);(3)"x"y(P(x)®Q(y))="x"y(ØP(x)ÚQ(y))="xØP(x)Ú"yQ(y)=Ø$xP(x)"yQ(y)=$xP(x)®"yQ(y)。.com说明在一阶逻辑中,要证明来年感个公式的等价或蕴涵,是一件十分复杂的事情。可是,对于比较简单公式等价、蕴涵的证明,采用教材中关于三段论的证明方法,即用解释的方法进行证明,和是应该掌握的。当然,也能够引用命题逻辑和一阶逻辑中的有关基本等价式和蕴涵式。另外,也还要注意准确划定量词的辖域以及逻辑联结词的等价转换。13将下面命题符号化:

42资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(1)”尽管有人聪明,但未必一切人都聪明”;(2)”每个人都有一些缺点”;(3)”如果每一个在银行存钱的人都能得到利息,则如果没有利息,就没有人在银行存钱”;(4)设f1(x),L,fn(x),L是函数序列,f(x)是一个函数,”对任何ef0x0Î(a,b),都存在N,使当nfN,有|f(x0)–fn(x)|pe,则称函数序列{fn(x)},在(a,b)区间内敛于f(x)”.解(1)令F(x):x聪明M(x):x是人于是,命题可表示为:$x(M(x)ÙF(x))ÙØ("xM(x)®F(x)).(2)令R(x,y):x都有y于是,命题可表示为:P(x):x是人Q(y):y是缺点"x$y(P(x)®Q(y)ÙR(x,y))课后答案网(3)令S(x,y):x存在yM(y):y是钱H(x):x是人R(x,z):x得到zP(z):z是利息于是,命题可表示为:"x(H(x)®$y(S(x,y)ÙM(y))®$z(R(x,z)ÙP(z)))(3)的结论可表示为:Ø$zP(z)®$x$y(H(x)ÙS(x,y)ÙM(y)).(4)令G(x,y):x大于yB(x):x属于(a,b)区间.comS(x,n):f1(x)与fn(x)之差的绝对值于是,命题可表示为:®®G(e,S(x,n)))."x"e(G(x,0)ÙB(x)$N"n(G(n,N)14试将下列公式化成等价的前束范式:(1)"xF(x)®$xG(x);

43资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(2)"x(P(x)®$yQ(x,y));(3)$x(Ø$yP(x,y)®($zQ(z)®R(x)));(4)"x"y(($zP(x,y,z)Ù$uQ(x,u))®$vQ(y,v)).解(1)"xF(x)®$xG(x)=Ø"xF(x)Ú$xG(x)=$xØF(x)Ú$xG(x)=$x(ØF(x)ÚG(x))(2)"x((P(x)®$yQ(x,y))="x(ØP(x)Ú$yQ(x,y))="x$y(ØP(x)ÚQ(x,y))。(3)$x(Ø$yP(x,y)®($zQ(z)®R(x)))=$x($yP(x,y)Ú($zQ(z)®R(x)))=$x($yP(x,y)Ú(Ø$zQ(z)ÚR(x)))=$x($yP(x,y)Ú("z(ØQ(z))ÚR(x)=$x$y"z(P(x,y)ÚØQ(z))ÚR(x))。))(4)"x"y(($zP(x,y,z)Ù$uQ(x,u))®$vQ(y,v))课后答案网="x"y(Ø($zP(x,y,z)Ù$uQ(x,u))Ú$vQ(y,v))"ØP(x,y,z)Ú"uØQ(x,u))Ú$vQ(y,v))="x"y(z="x"y"z"u$v(ØP(x,y,z)ÚØQ(x,u)ÚQ(y,v))说明在一阶逻辑中,对任意公式G中,都存在一个与其等价的前束范式,一般情况下,其前束范式是不唯一的。这是由于在将G化成等价的前束范式的过程中,量词提到公式最左边的顺序不同造成的。但它们彼此是等价的。如$x$y(F(x)®G(y));$y$x(F(x)®G(y))等也是本例(1)的前束范式。在前束范式的首标中,全称量词的存在量词的排列没有一定的规则,这是前束范式的不足之处。.com

44资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第五章群与环1.计算轮换的乘积(123)(234)(14)(23)解设1=(123),s2=(234),s3=(14),s4=(23),则我们要计算置换的乘积t=1s2s3s4我们先计算t(1),因为s4=(23)不含1,因此s4不变1,即s4(1)=1,s3s4(1)=s3(s4(1))=s3(1)=4.s2s3s4(1)=s2(s3s4(1))=s2(4)=2.s1s2s3s4(1)=s1(s2s3s4(1))=1(2)=3.即t(1)=3.接下去我们计算t(3).有s4(3)=2,s3s4(3)=2,s2s3s4(3)=3,s1s2s3s4(3)=1.即t(3)=1依照上面过程,可计算出t(2)=4,t(4)=2.æ1234ö于是t=(13)(24).写成置换的形式是çç÷÷3412èøé12345ù2.计算置换的幂6úûê34521ëé12345ù解设s=.úûê34521ë先把s写成轮换的乘积课后答案网s=(135)(24).因为不相杂轮换的乘法满足交换律,因此有s6=[(135)(24)]=(135)(24)[(24)666=[(135)=I*I3]2]23=I.3.设s=(132),t=(13)(24),计算sts解s=(231)-1-1设置换r=sts.我们先计算r(1).因为s(1)=2,ts(1)=t(2)-1-1-1=4,sts(1)=s(4)=4,因此r(1)=4.2)=3,r(3)因此r=(14)(32).写成置换的形式是-1w.khdaw.com同理可计算出=2.wwr(é12334ùêú4321ëû4.判断下列置换的奇偶性并写成对换的乘积é1234567ùé12345678ù4375162úê51876243úûëû.êë

45资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。解设前一置换为s,后一置换为t,先把s和t写成轮换乘积(乘积中应包括长度为1的轮换)s=(145)(237)(6)t=(1562)(38)(47)对于s来说,因为7-3是偶数,因此s是偶置换;对于t来说,因为8-3是奇数,因此是奇置换。把s和t写成对换乘积的形式的写法不是唯一的。其中一种写法是s=(15)(14)(27)(23)t=(12)(16)(15)(38)(47)5.把置换s写成不相杂轮换的乘积=1s2Lsk证明n=nn2Lskn,其中n是自然数.1证对k使用数学归纳法.当k=1时,s是一轮换,命题显然成立。假设当命题＜k时成立。则当s写成k个轮换,即=1s2Lsk时n=(1s2Lsk)n=((1Lsk-1)k)n因为1,s2,L,sk是不相杂轮换,因此1,s2,L,sk-1的乘积L1s2sk-1)与k也不相杂。仿照定理1的证明,容易证出如果置换L((1s2sk-1)与轮换k不相杂,也适合交换律。因此有Lsk-1)n[(根据归纳假设1s2Lsk-1)k]n=(kn.1n=(1s2Lsk)n1Lk)n=((课=(sk-1)L2k-1n案网kns)答n1n后nLs=.证毕.1k6.设,t是两个置换,把t表为不相杂的轮换的乘积,求证,计算sts-1只要用变换t中的文字.证设t表成不相杂轮换乘积为t=L(a1a2Lar)L.(x)=(ai).因此ts又设(ai)=x,则s-1-1-1(x)=t(s(x))=t(ai)=ai+1,sts(x)=(ts(ai))=(ai+1)(当I=r时,(ai+1)为(a1))-1-1设用变换t中的文字所得置换为t1,则t1=L(s(a1)(a2)Ls(ar))L于是t1(x)=t1(s(ai))=(ai+1).com(当I=r时,(a)为(a))i+11因此sts-1(x)=t(x)1设s,t是集合M上的置换,因为对M中的任意x都有上述证明过程,因此sts-1=t证毕.1。7.设M={1,2,L,n},证明M的所有偶置换在置换的乘法下做成一个群.证设M的所有偶置换做成的集合为S,因为偶置换的乘积仍是偶置换,因此S

46资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。在置换的乘法下封闭,即置换的乘法构成S中的运算.因为置换的乘法满足结合律,因此S中的置换运算满足结合律.因为单位置换I是偶置换,因此I在S中,由单位置换的性质知I是S中的单位元素.设s是S中的一个偶置换,则有置换s-1,使ss=ss=I.因只有偶置换的乘积才是偶置换,因此s满足ss=ss=I.综上所述,可知S是群.-1-1-1是偶置换,即S中有s-1-1-18.设S为非负整数做成的集合,在S中定义运算”*”如下:对任意a,b∈S,a*b=max(a,b)判断(S,*)是否是群.解不是,因为不是对任意元素都有逆元素.9.设R是实数集合,S={(a,b)︱a≠0,a,b∈R},利用一般的加法和乘法在S定义”*”如下:对S中的任意元素(a,b),(c,d)(a,b)*(c,d)=(ac,ad+b)证明S对”*”运算做成群.证因为对S中任意(a,b),(c,d),ac和ad+b都是实数,因此(a,b)*(c,d)∈S,即S对*运算封闭.设(a,b),(c,d),(e,f)是S中任意3个元素,则((a,b)*(c,d))*(e,f)=(ac,ad+b)*(e,f)=(ace,acf+ad+b)(a,b)*((c,d)*(e,f))=(a,b)*(ce,cf+d)=(ace,a(cf+d)+b)=(ace,acf+ad+b)因此((a,b)*(c,d))*(e,f)=(a,b)*((c,d)*(e,f))”*”运算在S中满足结合律.因为(1,0)∈S,对S中任意元素(a,b)课后答案网(1,0)*(a,b)=(a,b)*(1,0)=(a,b)因此(1,0)是S在”*”运算之下的单位元素.对S中的任意元素(a,b),有(,-b)ÎS,使得1aa(a,b)(,-b)=(,-b)(a,b)=(1,0)11aaaa因此(,-b)是(a,b)的逆元素.1aa综上所述,S对于”*”运算做成群.证毕.10.举例说明不要求可除条件而要求消去条件,即要求由ax=ay,可推出x=y,由xa=ya可推出x=y,则G不一定是个群.若G有限则结果怎样?解举例,全体自然数在乘法下适合消去律但不成群.若G有限,则消去条件保证G是一个群..com设G={a,a},a是G中任一元素.用a右乘G中各元素得到,L,a12naa,aa,L,aa12n这些元素必然互不相同.因若不然,由aa=aa和消去律知a=a,当i≠j时导ijij致矛盾.因此对任意b∈G,必有a满足aa=b,因之方程xa=b有解,同理可知iiay=b有解.即可除条件成立.由§5.3节定理3可知G是群.11.如果对群G中任意两个元素a,b都有(ab)=ab,试证G是交换群.222

47资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。证由(ab)2=a2b2知(ab)(ab)=(aa)(bb)因为G是群,因此任意元素a,b有逆.,右乘b,再利用群中乘法运算的结合-1在等式(ab)(ab)=(aa)(bb)的两端左乘a-1律及单位元的性质知ba=ab,因此G是交换群.12.设G是由3个元素构成的群,证明G是交换群.证设a,b是G中任意两个元素,若a,b中有一个是单位元素,比喻说是a,则ab=b,ba=b,因此ab=ba.若a,b都不是单位元素,由ab不可能是a(否则会得出b是单位元素),ab不可能是b(否则会得出a是单位元素),因此ab必是单位元素,同理ba也必是单位元素.因此ab=ba,G是交换群.13.设(G,*)是一个群.(H1,*)和(H2,*)是(G,*)的两个子群,证明(H1∩H2,*)也是(G,*)的子群.证因为H1和H2是G的两个子群,因此它们都包含G的单位元素e,因此e∈H1∩H2,因此H1∩H2非空.设a∈H1∩H2,b∈H1∩H2,因为a∈H1,b∈H1,又H1是子群,对乘法运算封闭,因此ab∈H1.同时ab∈H2,因此ab∈H1∩H2.因为a∈H1,H1是子群,因此a∈H1;同样地,因为a∈H2,H2是子群,因此-1∈H2,因此a∈H1∩H2.根据§5.4节定理2,H1∩H2是子群.a-1-114.讨论下面的问题,(H1,*)和(H2,*)是(G,*)的两个子群,问H1∪H2是否是(G,*)的子群.解不一定例如,设集合M={1,2,3}.G是M上的所有置换做成的群.则H1={I,(12)},H2={I,(13)}是G的两个子群.但H1∪H2={I,(12),(13)}不是G的子群.其原因是课后答案网乘法运算在H1∪H2中并不封闭,例如(12)(13)=(132)不在H1∪H2中.15.设(G,*)是一个群.C={a︱a∈G,对任意的x∈G有ax=xa},证明(C,*)是(G,*)的一个子群.证因为群中单位元素e满足ex=xe=x因此e∈C,C非空.设a∈C,b∈C,则对任意x∈G有ax=xa,bx=xb.于是,根据乘法结合律(ab)x=a(bx)=a(xb)=(ax)b=(xa)b=x(ab)因此ab∈C.设a∈C,则对任意x∈G,有ax=xa在上式两端左乘a-1,右乘a-1得a-1(ax)a-1=a-1(xa)a-1根据乘法结合律,群中逆元素与单位元素性质xa=ax-1-1因此a∈C.-1.com根据§5.4节定理2,C是子群.16.设M={1,2,3,4,5},s为M的一个置换é12345ùs=êú23154ëû写出s的循环群.解先把s写成不相杂轮换的乘积

48资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。s=(123)(45)由此可计算出s2=(132),s3=(45),s456=(123),s=(132)(45),s=I.因此由s生成的循环群(s)={I,s,s23,s,s4,s5}.(s)的所有子群是H1={I,(123),(132)}H2={I,(45)}(123)和(132)是H1的生成元素.(45)是H2的生成元素.17.设(G,*)=(a)是n元循环群,b=a,证明k(1)元素b是群G的生成元素,当且仅当n和k互质;(2)元素b的周期为n/d,其中d是n和k的最高公因.kk证(1)若b=a是群G的生成元素,则a必可用a的幂的形式表出,即a=(a)kq,根据§5.4节定理5知n|(1-kq),设pn=1-kq于是有pn+kq=1.若n与k不互质,则设n与k的最大公约数为r＞1,由pn+kq=1推出r整除1,矛盾.反之,若n与k互质,知有整数p与q,使得pn+qk=1,于是(pn+qk)pnqkkq·aa=a=a=(a)由此可知a为生成元素.k(2)若b是群G的生成元素,由(1),命题(2)显然成立.以下设b不是群G的生成元素.因为nb(n/d)=(ak)()课后答案网=a(k/d)·nn(k/d)=(a)=ed因此b的(n/d)次幂是e.若有m＜(n/d),使a=e,则a=emkm因此n整除km,设qn=km,于是q(n)=m(k).因为n与k互质,因此dddd(n)整除m,矛盾.d证毕.18.设M={1,2,3},写出M的置换群的所有子群.解M的置换群有6个元素,它们是I,(12),(13),(23),(123),(132).M的置换群的所有子群是{I},{I,(12)},{I,(13)},{I,(23)},{I,(123),(132)},置换群本身.19.求证若群(G,*)的元数是一个质数,则(G,*)必是循环群..com证设(G,*)的元数是一个质数p,因p是质数,因此G中至少有两个元素,设a是G中的一个非单位元的元素,其周期是n＞1.a,a,L,a,an=e(1)2n-1显然,序列(1)中的元素是彼此不等的.如果G中的元素全在序列(1)中,则G显然是循环群.以下我们证明若G有元素b不在(1)中,则会导致矛盾.此时考虑序列

49资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。ba,ba2,Lban-1,ban(2)容易说明序列(1),(2)中的元素彼此不同,若G中的元素全在(1),(2)中,则2n=p,n整除p,与p是质数矛盾.若G中元素不全在(1),(2)中,则仿上考虑序列(3):ca,ca2,L,can-1,can(3)其中c是G是元素,既不在序列(1)中,又不在序列(2)中.然后由3n=p推出矛盾.仿照上述过程,因G有限,必有q使qn=p从而q整除p,推出矛盾.证毕.20.设A={1,2,3,4},s是A的一个置换é1234ùs=êúû4312ë求由s生成的循环群(s),写出(s)的所有右陪集,判断(s)是否为正规子群.解先把s写成轮换的乘积s=(1423)然后计算s的各次幂s2=(12)(34)因此由s生成的循环群是s3(1324)s2=I(s)={(1423),(12)(34),(1324),I}(s)本身是(s)的一个右陪集,(s)的其余的右陪集是:(12)(s)={(14)(23),(34),(13)(24),(12)}课后答案网(13)(s)={(142),(1234),(243),(13)}(14)(s)={(234),(1243),(132),(14)}(23)(s)={(143),(1342),(124),(23)}(24)(s)={(123),(1432),(134),(24)}因为(s)关于(13)的左陪集是:(s)(13)={(234),(1432),(124),(13)}因为(s)(13)不等于它的右陪集,因此(s)不是正规子群.21.设(H,*)是(G,*)的子群,若(H,*)在(G,*)中的右陪集的个数有限,求证左陪集的个数也有限而且和右陪集的个数相等.证设H在G中的所有右陪集是g1H,g2H,L,gnH(1)我们考虑下面这些陪集.comHg-1,Hg-1,L,Hgn-1(2)12首先,我们说明这些陪集并在一起刚好等于G.对于任意g∈G,g∈G,因为序-1列(1)是H在G中的所有右陪集,因此g必在某一陪集中,设g∈gH,于是有h-1-1i∈H,使得gg,因此g∈Hg.-1=gH从而g=h-1-1-1iii其次,我们说明序列(2)重点所有陪集是彼此不等的.如果有i≠j,但=Hgj,则有h1,h2,使得h1gi=h2gj,从而h2h1=gjgi,gi=gj(h2h1),-1Hgi-1-1-1-1-1-1

50资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。因此gi∈gjH,此与gi与gj在不同的陪集矛盾.22.设(G,*)是一个群.证毕.C={a︱a∈G,对任意的x∈G有ax=xa},证明(C,*)是(G,*)的一个正规子群.证根据例5.15知C是G的子群.因为C中的元素与G中的任意元素相乘都是可交换的,因此对G中任意元素a,都有aC=Ca.因此C是G的正规子群.证毕.23.求证(G,*)的任意多个子群的交集仍是(G,*)的子群.(G,*)的任意多个正规子群的交集也是(G,*)的正规子群.证设H1,H2,L,Hn是(G,*)的子群.因为这些子群都有单位元素e,因此e∈H1∩H2∩LIHn,因此H1∩H2∩LIHn非空.设a∈H1∩H2∩LIHn,b∈H1∩H2∩LIHn,则a∈Hi,b∈Hi(i=1,2,L,n),因为Hi是子群,因此ab-1∈Hi,因此ab-1∈H1∩H2∩LIHn.根据§5.4节定理3.H1∩H2∩LIHn是子群.设H1,H2,L,Hn是(G,*)的正规子群,则由上面的证明首先知道H1∩H2∩LIHn是子群.任取h∈H1∩H2∩LIHn,则h∈Hi(i=1,2,L,n),因为Hi是正规子群,因此gHig-1ÍH,于是ghg-1∈Hi(i=1,2,L,n),ghg-1∈H1∩H2∩课后答案网ILIHn.由h的任意性知,g(H1∩H2∩LIHn)g-1ÍH1∩H2∩LIHn.根据§5.4节定理2知H1∩H2∩LIHn是正规子群.证毕.24.设(G,*)事实群,(H,*)是(G,*)的子群,证明若(H,*)在(G,*)中的右陪集只有两个,则(H,*)是正规子群.证设a是群G中的任意元素,我们证明aH=Ha.若a是H中元素,则显然aH=Ha=H.若a不是H中元素,则因为a的右陪集只有两个.aH必是另外一个右陪集.对任意h∈H,ha必然不在H中,因假如设ha在H中,比喻说ha=h1,h1∈H,则a=h-1h1∈H,矛盾.既然ha不在H中,ha必在另一个右陪集aH中,因此HaÍaH.因为a是aH中任意元素,因此把上式中的a换成a仍会有同样的结果,即-1.comHa-1Ía-1H,即aHÍHa.因此有aH=Ha.证毕.25.设(H,*)是(G,*)的子群,(N,*)是(G,*)的正规子群.令HN={hn|h∈H,n∈N},即HN为H的元素乘N的元素所得的所有元素的集合,求证HN是G的子群.证因为H和G都是子群,都包含元素e,因此e∈HN,因为HN非空.任取a=h1n1∈HN,b=h2n2∈HN,

51资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。则ab-1-1=(h1n1)(h2n2)∈N,设n1n2=n,则h1n∈h1N.因为N是正规子群,因此h1N=Nh1因此h1n=h1(n1n2)h2).因为H是群,h1∈H,h2∈H,所=h1n1n2h2=h1(n1n2)h2.因为N是子群,因此-1-1-1-1-1n1n2-1∈Nh1.于是知道有n3,使h1n=n3h1,从而ab=h1nh2=(h1n)h2=(n3h1)h2=n3(h1h2∈H.设h1h2=h3,则ab-1-1-1-1-1-1-1以h1h2群.-1-1-1=n3h3∈NH,根据§5.4节定理3,NH是子证毕.26.设(H,*)是群(G,*)的子群.证明(H,*)是(G,*)的正规子群的充要条件是H的任意两个左陪集的乘积还是H的一个左陪集.证设H是正规子群.Ha,Hb是H的任意两个左陪集.任取hia∈Ha,h2b∈Hb,则(hia)(h2b)=hi(ah2)b因为H是正规子群,aH=Ha,因此ah2∈aH,ah2∈Ha,因此有h3∈H,使ah2=h3a,于是(hia)(h2b)=hi(ah2)b=hih3(ab)∈H(ab)因此(Ha)(Hb)ÍH(ab)任取hab∈Hab,则因hab=(ha)b,ha∈Ha,b=e·b∈Hb,因此hab∈(Ha)(Hb),即H(ab)Í(Ha)(Hb)因此(Ha)(Hb)=H(ab).设H的任意两个左陪集的乘积还是H的一个左陪集.则设Ha,Hb是两个左陪集,则(Ha)(Hb)还是一个左陪集.因为ea∈Ha,eb∈Hb,因此(ea)(eb)∈(Ha)(Hb).因为(ea)(eb)=ab∈H(ab),课后答案网因此(Ha)(Hb)=H(ab).因为上式对任意的a,b都成立,故可取b=a,从而-1-1-1得到(Ha)(Ha)=H(aa)=H因此对任意的hi,h2,有(hia)(h2a)∈H,设(hia)(h2a-1)=h3,则有ah2a-1=h1-1h3∈H,由h2的任意性知aHa-1ÍH.由此知H是正规子群.证毕.27.设A={1,2,3,4},G是A上所有置换做成的集合.设H={I,(12)(34),(13)(24),(14)(23)},证明H是G的正规子群.证首先,H非空.其次我们证明对任意a∈H,b∈H,ab-1∈H.若a=I,则因对任意b∈H,b=b,因此ab=Ib=b=b∈H,若b=I,则ab=a∈H.以下假设a-1-1-1-1-1≠I,b≠I.若a,b相同,则因对任意a∈H,a2=I,a=a.知ab=I∈H.若a,b不同,则容-1-1=ab等于H的另外一个元素c,因此H是G的子群.根据例6的结果,能够验证对任意g∈G,均有gHg易验证ab-1-1∈H,因此H是G的正规子群.证毕..com根据§5.3节例13知G是交换群,矛盾.28.设(G,*)是非交换群,其元数是6,证明(G,*)必有一个元数为3的子群.证因为G有6个元素,因此G有非单位元素.若G的所有非单位元素的周期都是2,则对G中任意元素x都有x=e,或者说G中每个元素的逆元素就是其自身.2既然G中有非单位元素a的周期不是2,则设a的周期是n,n＞2,根据§5.6节定理2,n整除6,因此n或者为3,或者为6.若n=3,则{e,a,a}是3个元素的2

52资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。子群.若n=6,则{e,a2,a4}是3个元素的子群.证毕.29.设(G,*)是一个群,其元数为p必有一个元数为p的子群.证因为pm,其中p是质数,m≥1,证明(G,*)m≥2,因此G中必有不是单位元素的元素.任取其中一个非单位元素的元素a,设其周期为n,则n整除p.因为p只能被p,整除(s≤m),或者被2mms整除,而n＞1.因此必然是n=p,于是{e,asp,ap2p的子群.,ap3,L,ap(s-1)}就是一个元数为课后答案网.com

53资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第六章格与布尔代数1．判定图6-1所示半序集中哪些是格,哪些不是格课后答案网.com

54资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。图6-1解(a),(c),(e)是格,(b),(d),(f)不是格。(b)不是格是因为A,B两元素无最小上界。(d)不是格是因为C,D两元素无最大下界。(f)不是格是因为E,F两元素无最大下界。2．设(L,´,Å)是一个格,a,b是格中两元素,证明a´b=b当且仅当aÅb=a。证设a´b=b,则aÅb=aÅ(a´b)=a(吸收律)设aÅb=a,则a´b=(aÅb)´b=b´(bÅa)(交换律)=b(吸收律)证毕。3．设(L,´,Å)是一个格,a,b,c是格中任意3个元素,a£b,证明aÅ(b´c)£b´(aÅc)证因为a£b,b´c£b,因此b是a和b´c的一个上界,而aÅ(b´c)是a和课后答案网(b´c)的最小上界,因此有aÅ(b´c)£b。因为a£(aÅc),b´c£b(aÅc),因此(aÅc)是a和b´c的一个上界,而aÅ(b´c)是a和(b´c)的最小上界,因此有aÅ(b´c)£(aÅc)。因为aÅ(b´c)£b,aÅ(b´c)£(aÅc),因此aÅ(b´c)是b和(aÅc)的一个下界,因为b´£(aÅc)是b和(aÅc)的最大下界,因此aÅ(b´c)£b´(aÅc)4．证明在格(L,£)中,若a,b,cÎL,且a³b,a³c,则有a´(bÅc)=(a´b)Å(a´c)。证毕证因为a´b£a,a´c£a,因此a是a´b与a´c的一个上界,而(a´b)Å(a´c).com因为(a´b)£b£bÅc,(a´c)£c£bÅc,因此bÅc是(a´b)与(a´c)的一个上界,而(a´b)Å(a´c)是(a´b)与(a´c)的最小上界,因此是(a´b)与(a´c)的最小上界,因此(a´b)Å(a´c)£a(a´b)Å(a´c)£(bÅc)

55资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。因为(a´b)Å(a´c)£a,(a´b)Å(a´c)£(bÅc),因此(a´b)Å(a´c)是a与(bÅc)的一个下界,而a´(bÅc)是a与(bÅc)的最大下界,因此有a´(bÅc)=(a´b)Å(a´c)(1)因为a³b,因此a´b=b,因为a³c,因此a´c=c,因此(a´b)Å(a´c)=(bÅc),因为a´(bÅc)£(bÅc)因此a´(bÅc)£(a´b)Å(a´c)。由(1),(2)能够推出a´(bÅc)=(a´b)Å(a´c)(2)证毕。5设(L,´,Å)是一个格,a,bÎL。令S={x|xÎL,且a£x£b}其中L是格中的半序关系。证明(S,´,Å)是L的子格。证由定义,我们只要证明S在´,Å运算下封闭即可。设x1,x2是S中任意两个元素,则有课后答案网a£x£b2a£x1£b,因而a是x1和x2的一个下界,b是x1和x2的一个上界。因为x1´x2和x1Åx2分别是x1和x2的最大下界和最小上界,因此a£x1´x2£b,a£x1Åx2£b此说明S在´,Å两运算下封闭。证毕6证明在格中,若a£b且c£d,则有a´c£b´d,aÅc£bÅd.证(a´c)´(b´d).com=a´b´c´d=(a´b)´(c´d)=a´c(交换律)(结合律)(定律1,因为a£b,c£d)因此,根据定理1,有a´c£b´d。

56资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(aÅc)Å(bÅd)=(aÅb)Å(cÅd)=bÅd.(交换律,结合律)因为(定律1,因为a£b,c£d)因此,根据定理1,有aÅc£bÅd.7证明在格中,对任意元素a,b,c,d有(a´b)Å(c´d)£(aÅc)´(bÅd)证毕´(a´b)Å(b´c)Å(c´a)£(aÅb)´(bÅc)(cÅa)。证因为a´b£a£aÅc,c´d£c£aÅc,因此(aÅc)是a´b与c´d的一个上界,而(a´b)Å(c´d)是(a´b)与(c´d)的最小上界,因此有(a´b)Å(c´d)£aÅc。因为a´b£b£bÅd,c´d£d£bÅd因此(bÅd)是(a´b)与(c´d)的一个上界,而(a´b)Å(c´d)是(a´b)与(c´d)的最小上界,因此有课后答案网(a´b)Å(c´d)£(bÅd)因为(a´b)Å(c´d)£aÅc,(a´b)Å(c´d)£(bÅd),因此(a´b)Å(c´d)是aÅc和(bÅd)的一个下界,而(aÅc)(´bÅd)是aÅc和(bÅd)的最大下界,因此有(a´b)Å(c´d)£(aÅc)´(bÅd)因为(a´b)£a£(aÅb),(b´c)£b£(aÅb),(c´a)£a£(aÅb),因此(aÅb)是(a´b),(b´c),(c´a)的一个上界,而(a´b)Å(b´c)Å(c´a)表示(a´b),(b´c),(c´a)的最小上界,因此有(a´b)Å(b´c)Å(c´a)£(aÅb)同理(a´b)Å(b´c)Å(c´a)£(bÅc).com(a´b)Å(b´c)Å(c´a)£(cÅa)因此(a´b)Å(b´c)Å(c´a)是(aÅb),(bÅc),(cÅa)的一个下界,而´(aÅb)´(bÅc)(cÅa)是它们的最大下界,因此´(a´b)Å(b´c)Å(c´a)£(aÅb)´(bÅc)(cÅa)证毕

57资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。8证明在有余分配格(L,´,Å)中,对任意a,bÎL,有①②③a£bÛa´b¢=0;aÅb=1;a´b¢=b¢£a¢Û¢0a£bÛb¢´a¢=b¢.证①若a£b,则a´b=a,于是(a´b¢=a´b´b¢=a´b´b¢)=a´0=0如果a´b¢=0,则因bÅb¢=1,于是由分配律´1a=a´=a(bÅb’)=(a´b)Å(a´b’)=(a´b)Å0课后答案网=(a´b)因此a£b。b¢£a¢,则b¢Åa¢=a¢,于是②如果a¢Åb=b¢Åa¢Åb=a¢Å(b¢Åb)=a¢Å1=1。如果a¢Åb=1,则b¢=b¢´1=b¢´(a¢Åb).com=(ba)(b´b)¢´¢Å¢(分配律)¢´¢=(ba)Å0=a¢´b¢

58资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。因此b¢£a¢。③如果a£b,则a´b=a,于是,由摩跟根定律=(a´b)¢=a¢Åb¢,即b¢£a¢。a¢a,则有a¢=a¢Åb¢反之,若b¢£¢b=a´b,即a£b。由此推出a=(a¢)¢=(a¢Å¢)¢证毕9证明一个格是分配格的充要条件是对格中任意元素x,y,z,均有(x´y)Å(y´z)Å(z´x)=(xÅy)´(yÅz)´(zÅx).证设(L,´,Å)是分配格,x,y,zÎL,则(x´y)Å(y´z)Å(z´x)=[(x´y)Å(y´z)]Å(z´x)=[(xÅy)´(yÅy)´(xÅz)´(yÅz)]Å(z´x)=[(xÅy)´y´(xÅz)´(yÅz)]Å(z´x)(等幂律)(1)课后答案网=[(xÅy)´(xÅz)´(yÅz)]Å(z´x)因为(z´x)£x£(xÅy),(z´x)£x£(xÅz),(z´x)£x£(yÅz)因此(z´x)是(xÅy),(xÅz),(yÅz)的一个下界,而(xÅy)´(xÅz)´(yÅz)是(xÅy),(xÅz),(yÅz)的最大下界,因此(z´x)£(xÅy)´(xÅz)´(yÅz)因此[(xÅy)´(xÅz)´(yÅz)]Å(z´x)=(xÅy)´(xÅz)´(yÅz)(2)结合(1)式和(2)式,可知(x´y)Å(y´z)Å(z´x)=(xÅy)´(yÅz)´(zÅx)。.com设对格中任意元素x,y,z,均有(x´y)Å(y´z)Å(z´x)=(xÅy)´(yÅz)´(zÅx)。则设x=a,y=b´c,z=(aÅb)´(aÅc),其中,a,b,c是格中任意元素。于是(x´y)Å(y´z)Å(z´x)=(a´(b´c))Å[(b´c)´(aÅb)´(aÅc)]Å[(aÅb)´(aÅc)´a](3)

59资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。根据吸收律[a´(b´c)]Å[(aÅb)´(aÅc)´a]=[a´(b´c)]Åa=a因为(b´c)£b£(aÅb),(b´c)£c£(aÅc)因此(b´c)是(aÅb)和(aÅc)的一个下界,而(aÅb)´(aÅc)是(aÅb),(aÅc)的最大下界,因此(b´c)£(aÅb)´(aÅc)因此(b´c)´[(aÅb)´(aÅc)]=(aÅb)´(aÅc)(4)(5)因为a£(aÅb)´(aÅc),因此有aÅ[(aÅb)´(aÅc)]=(aÅb)´(aÅc)结合(3),(4),(5)可知课后答案网(x´y)Å(y´z)Å(z´x)=(aÅb)´(aÅc)(x´y)Å(y´z)Å(z´x)=[aÅ(b´c)]´{(b´c)Å[(aÅb)´(aÅc)]}´{(aÅb)´(aÅc)}Åa}=[aÅ(b´c)]´[(aÅb)´(aÅc)]=[aÅ(b´c)]=aÅ(b´c)因此(aÅb)´(aÅc)=aÅ(b´c)即格L是分配格。.com证毕。10证明下列布尔恒等式(1)a+(a•b)+(a•b)=a+b;(2)a•[a+b+(a•b)]=a•b.

60资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。证(1)a+(a•b)+(a•b)=a+[(a•b)+(a•b)](结合律)=a+1•b(分配律)=a+b(2)a•[a+b+(a•b)]=a•a+(a•b)+(a•a•b)(分配律)=0+(a•b)+(a•b)=0+(a•b)(等幂律)(等幂律)=a•b证毕。11设(B,•,+,-,0,1)是布尔代数,a,b,cÎB,证明(1)(a+b)•(b+c)•(c+a)=(a+b)•(b+c)•(c+a);课后答案网(2)(a+b)•(a+c)=(a•c)+(a+b);(3)a£bÞa+(b•c)=b•(a+c).证(1)(a+b)•(b+c)•(c+a)=[(a•b)+(b•b)+(a•c)+(b•c)](c+a)=[(a•b)+(a•c)+(b•c)](c+a).com(分配律)=(a•b•c)+(a•c•c)+(b•c•c)+(a•b•a)+(a•c•a)+(b•c•a)(分配律)=(a•b•c)+(a•b•c)

61资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。同样能够证明(a+b)•(b+c)•(c+a)=(a•b•c)+(a•b•c)因此(a+b)•(b+c)•(c+a)=(a+b)•(b+c)•(c+a)。(1)(a+b)•(a+c)=(a•a)+(a•b)+(a•c)+(b•c)=(a•b)+(a•c)+(b•c)(分配律)=(a•b)+(a•c)+(b•c•1)=(a•b)+(a•c)+[b•c(a+a)]课后答案网=(a•b)+(a•b•c)+(a•c)+(a•b•c)(分配律)=(a•b)•(1+c)+(a•c)•(1+b)=(a•b)•1+(a•c)•1=(a+b)+(a•c)(3)因为a£b,因此a+b=b,于是.comb•(a+c)=(a+b)•(a+c)=(a•a)+(a•b)+(a•c)+(b•c)(分配律)=a+(b•c)(吸收律)

62资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。证毕。12.化简下述布尔表示式(1)(a·b)+(a·b·c)+(b·c);(2)(a·b)+(a·b·c)+(b+c);(3)(a·b)+(a·b·c)+(b·c).解(1)(a·b)+(a·b·c)+(b·c)=(a·b)+(a·b·c)+(a·b·c)+(b·c)(等幂律)=[(a·b)+(a·b·c)]+[(a·b·c)+(b·c)](结合律)=(a·b)(1+c)+(b·c)(a+1)(分配律)=a·b·1+b·c·1=a·b+b·c=b·(a+c)(分配律)(2)(a·b)+(a·b·c)+b+c=[(a·b)+b]+[(a·b·c)+c(交换律,结合律)=b(a+1)+c(1+ab)=b+c(4)(a·b)+(a·b·c)+(bc)=(a·b)(c+c)+(a·b·c)+(a+a)b·c课后答案网=(a·b·c)+(a·b·c)+(a·b·c)+(a·b·c)+(a·b·c)=(a·b·c)+(a·b·c)+(a·b·c)+(a·b·c)(等幂律)=[(a·b·c)+(a·b·c)]+[(a·b·c)+(a·b·c))(交换律,结合律)=b·c(a+a)+bc(a+a)=b·c+bc.com=b(c+c)=b13.设(B,*,Å)是一个环,有壹(用1表示),且对*运算满足等幂律,即对任意x∈B,有x*x=x在B中定义·,+,—运算如下:对任意a,b∈Ba·b=a*ba+b=aÅbÅ(a*b)

63资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。a=a+1证明(B,·,+,—,0,1)是一个布尔代数.证根据§6.3定理,我们只需证明运算·,+,—满足如下条件:H:a·b=b·a,a+b=b+a;1H2:a·(b+c)=(a·b)+(a·c);a+(b·c)=(a+b)(a+c);H3:a·1=a,a+0=a;H4:对任意a∈B,有a∈B,使得a·a=0,以下我们分别证明H1～H4首先证明H1.a+a=1.设a是B中任意一个元素,则由对*运算等幂律知(aÅa)*(a.Åa)=(aÅa)把上式左端分配律乘开,得到(a*a)Å(a*a)Å(a*a)Å(a*a)=aÅa使用对*运算的等幂律得到aÅaÅaÅa=aÅa因此,对B中任意元素a有aÅa=0由对*运算的等幂律知(aÅb)*(aÅb)=(aÅb)课后答案网(a*a)Å(b*a)Å(a*b)Å(b*b)=aÅbaÅ(b*a)Å(a*b)Åb=aÅb(b*a)Å(a*b)=0在上式两端同时加上(a*b),利用(a*b)Å(a*b)=0,得到(b*a)=(a*b)这说明环(B,Å,*)的运算适合交换律,即(B,Å,*)是交换环.因为*运算适合交换律,又因为a·b=a*ba+b=aÅbÅ(a*b)因此a·b=b·a,a+b=b+a,即H1成立.接着我们证H2:由环的分配律知a·(b+c)=(a·b)+(a·c).com能够计算出a+(b·c)=[a+(b*c)]=aÅ(b*c)Å(a*b*c)(a+b)(a+c)=[aÅbÅ(a*b)][aÅcÅ(a*c)]=aÅ(b*c)Å(a*b*c)因此a+(b·c)=(a+b)(a+c),即H2成立.

64资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。由环中1和0的性质知H3.成立.对任意a∈B,设a=1+a,则a·a=a·(1+a)=a+a2=a+a=0a+a=a+1+a=a+a+1=0+1=1因此H4成立.现在既然已经证明H1～H4成立,可知(B,·,+,—,0,1)是一个布尔代数.证毕.课后答案网.com

65资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。第七章图论1设P={u,v,w,x,y},画出图G={P,L},其中(1)L={uv,ux,uw,vy,xy};(2)L={uv,vw,wx,wy,xy},并指出各个点的度。解对应于(1)的图如图7—1所示。其中各点的度为:dG(u)=3,dG(x)=2,dG(y)=2,dG(v)=2,dG(w)=1.对应于(2)的图如7—2所示。各点的度为:dG(u)=1,dG(x)=2,dG(y)=2,dG(v)=2,dG(w)=3。UVUV课后答案网YXYXW图7—12设图G有5个点,4条边,在同构的意义下,画出图G的所有可能形式。解图7—3是图G的所有可能形式。.com1

66资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(a)(b)(c)(d)(g)(e)(f)图7—2图7--33图G=(P,L)如图7—4所示,试画出G的三个不同支撑子图。课后答案网图7--4解图7—5(a),(b),(c)就是图G的三个支撑子图。.com(a)(b)(c)图7--54是否能够画一个图,使各点的度与下面给出的序列一致,如可能,画出一个符合条件的2

67资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。图,如不可能,说明原因。(1)3,3,3,3,3,3;(2)3,4,7,7,7,7;(3)1,2,3,4,5,5;解(1)能够,如图7—6所示:图7—6(2)不可能。在六个顶点中,奇数度点为5个,与定理2相矛盾。(3)不可能。考虑两个度为5的顶点,设其为u和v,因为只有6个顶点,因此u和v除自身之外的个顶点皆相连。而除u,v之外的4个顶点中的每一个都至少是两条边的端点,即这4个顶点的度都至少是非,这与其中某一个顶点的度为1矛盾。5设G是有限图,M,A分别是G的关联矩阵和相邻矩阵,证明:M*M/和A2的对角线上的元素恰好是G中所有点的度。证设L(G),P(G)的元素分别为n,m.令B=M*M/,由矩阵的乘法定义知课后答案网nåbii=aij*a/jii=1,2,3---------mj=1因为M/是M的转置矩阵,因此aij=a/ji,,又因为aij非0即1,因此aij2=aij故得nnnåååbii=aij*a/ji=aij2=aijj=1j=1j=1即bii等于M的第I行中所有1的个数,也就是bii等于M的第I行所对应的点的度。故M*M/的对角线上的元素是G中所有点的度。må令C=A2则Cii=aji·ajiI=1,2,------,mj=1.commmmåååaij·aji=2a=ijaij.因为A是对称矩阵,因此a=a,aij2=a,因此cii=ijjiijj=1j=1j=1即cii等于第I行所有1的个数,即第I行所对应点的度,(I=1,2,-------M)。故A2的对角线上的元素是G中所有点的度。6设G是有限图,P(G),L(G)的元素分别为m,n,＆△分别是G中点的最小度现最3

68资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。大度。证明:＆≤2n／m≤△证因为＆△分别是G中点的最小度和最大度,因此有m*＆≤≤m*△又因为=2n,因此m*＆≤2n≤m*△即＆≤2n／m≤△7证明连通图中两条最长年简单路必有公共点。证毕证用反证法。若不然,设两条最长路为l1=(u,-----u/),l2=(v----v/).因为图是连通的,故从u到v/有路,设此路最后一次离开l1的点是w,第一次进入l2的点是w/,由题设可知,w≠w/,见图7—7:L1N’W图7—7取max{(u,------,w),(w,-----,u)}∪{(w,----,w/)}∪max{(v,-----,w/),(w/,-----,v/)便得到一条更长的简单路,与l1,l2是两条最长的简单路矛盾。因此,连通图中任意两条最长的简单路必有公共点。课/后答案网8一公司在六个城市C1,C2,----,C6中每一个都有分公司,从CI到CJ的班机旅费由下列矩阵中第I行第J列的元素给出(∞表示没有直接班机)。00500∞1504025102550∞4020∞152010020∞1020∞1002525∞1025551025550公司所关心的是计算两城市间的费用最低的路线,对上述六城市中任意一对城市,计算两城市间费用最低的路线。解首先,求C1到C2,----,C6的最短路线。.com(1)从C2,---,C6,中找出与C1距离最近的一个,为C6,于是l(C6)=10,最短路线C1→C6。(2)从d(C1,Ci),l(C6)+d(C6,Ci)中选取最小者,其中i2,3,4,5,可得dC1,C5),于是lC5)=25,最短路线C1→C5。(3)类似于步骤(2),依次可得:l(C4)=15,最短路线C1→C6→C4;l(C2)=35,最短路线C1→C6→C2;l(C3)=45,最短路线C1→C5→C34

69资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。对于城市C2,----,C6,能够用类似于C1的方法得到最短路线。9设G是图,＆是G中最小度,K是一个正整数,若k≤＆,试证明G中有一条长为k的简单路。证明不妨设＆≥0,当＆=0时,命题显然成立。以下设＆≠0,任取一点v0,显然d(v0)≥＆,故可找到一相邻点v1。设已找到vi,i＜＆.由d(vi)≥＆,看vi的相邻点,至少有一个不同于v0,v1,---,是vi–1取这样一个点设为vi+1;如此下去可一直找到v﹠,而(v0,v1,---,v﹠)正是一条长为﹠的简单路。因此,若k≤＆,则必有一条长为k的简单路。10设G为图(可能无限),无回路,但若外加任意一边于G后就形成一回路,试7证明G必为树。证按树的定义可知,只需证G为连通即可。任取不相领两点v,v1,由已知,加上边vv1后就形成一回路。于是去掉边vv1,从v到v1仍有路v,…,v1,即v,v1相连。由v,v1的任意性可知G是连通的。因此,G必为树。证毕。11在具有n个顶点的完全图kn中需删去多少条边才能得到树?解n个点的完全图kn中共有Cn2条边,而n个点中的树中共有n-1条边。因此需要删除cn2-(n-1)=.(n-1)(n-2)/2条边后方可得到树。12分别用三种不同的遍历方式写出图7-8中二叉树点的访问次序。ABCGDJE课后答案网FHIKL图7-8解先根次序:ABDEHKLCFGIJ;中根次序:DBEKHLAFCIGJ;后根次序:DKLHEBFIJGCA..com13分别写出下列表示式的后缀表示:(1)(a+b)*c;(2)l(a+b)-c+e*f.n解(1)首先将表示式化成二叉树如图7-9(a),由此可知表示式的后缀表示为:ab+c*.5

70资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。CCEF1NAB图7-9(2)首先将表示式化为二叉树,如图7-9(b),从而表示式的后缀表示为:ab+㏑c-ef*+.14设有5个城市v1,…,v5,任意两城市之间铁路造价如下(以百万元为单位):W(v1,v2)=4,W(v1,v3)=7,W(v1,v4)=16,W(v1,v5)=10,W(v2,v3)=13,W(v2,v4)=8,W(v2,v5)=17,W(v3,v4)=3,W(v3,v5)=10,课后答案网W(v4,v5)=12.试求出连接5个城市而且造价最低的铁路网。解首先将本题用一权图来描述,于是求解此题便成为求权图中的最优支撑树问题。按克鲁斯卡尔算法,图7-10中(b)～(e)就是求解最优支撑树的过程。V174V31613V2V3310810173V4.comV412V5(a)(b)6

71资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。V1V1V1774V3V2V2V1V2V333310(c)(d)(e)15试用克鲁斯卡尔算法求图7-11所示权图中的最优支撑树。17354295678课后答案网3图7-11解图7-12(a)～(e)表示图7-11的最优支撑树。212(a)(b)(c).com1133235237

72资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(d)(e)16举出满足下列要求的具有5个点的有向图:(1)G有根,可是不是强连通的;(2)G存在一棵有向支撑子树,并标出这棵有向树;(3)G是强连通的(将G漠视为于是强连通的),但G无根。解(1)如图7-13(a),A是根,可是不存在从B到D的有向路。(2)如图7-13(b),图7-13(c)是7-13(b)的一棵有向支撑树。(3)如图7-13(d)。(a)(b)(c)(d)17设G(P,A)是有向图,G中任意两个不同点之间至多有一条弧,G中没有指向自身的弧,若不考虑G中弧的方向,把弧看成边,则G是连通的。问G是否有根?若能肯定G有根,试给出证明,否则举出反例。课后答案网解回答是否定的。举例如图7-13(d),将此有向图漠视为图以后,它是连通的,但它却无根。18设G=(P,A)为有向图,若G与根r,且无有向回路,问G是否是有向树?解回答是否定的,举反例如图7-13中(a)。19证明:若r是有向图G的根,则G必含有一个以r为根的有向支撑树。.com图7-14GG21证用如下方法来构造的支撑树:令G0={r},设已得GK是有向树,做GK+1如下:选取P(G)中的某顶点v,使得v∈P(Gk)。设从v到r的有向路进入Gk后第一个顶点v’,进入Gk前的最后一个顶点是v”,再在GK中加入弧v”v’,及顶点v”。8

73资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。又归纳法可证,GK是有向树。按如上做法便可得到G中以r为根的支撑树。20能否对图7-14的边指定方向,使其成为欧拉图?解G能够,如图7-15(a)所示,由于G1中的每一个点都是平衡点。G2不能够,图7-15(b)中所有点的度都是3,因此不论怎样指定边的方向,G2中的每个点都不是平衡点。因此不可能适当地指定G2中各边的方向,使其成欧拉图。(a)(b)图7-1521下列图形是否能够一笔画出?如能够的话画出欧拉图,否则说明原因。课后答案网G1G2图7-16解不能够。因为中有8个度为奇数的顶点。能够。按照边上的标号依次读下来,便能够一笔画出。见图7-17.com9

74资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。156147161124121381093图7-1721举出满足下列要求的具有5个点的图。(1)没有哈密顿回路,也不能适当指定各边的方向使其具有欧拉路;(2)有哈密顿回路,可是不能适当指定各边的方向使其具有欧拉路;(3)没有哈密顿回路,可是能适当指定各边的方向使其具有欧拉路;(4)有哈密顿回路,也能适当指定各边的方向使其具有欧拉路。解见图7-18(a)～(d),它们分别满足条件(1)～(4)课后答案网(a)(b).com(c)(d)图7-823使用平面图定义及Jordan曲线性质证明K3..3是非平面图。证用反证法。K3..3如图7-19(a)所示,假设能够把K3..3画成一个平面图。10

75资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。回路v1v6v3v4v1构成一个Jorand曲线,设其为C,如图7-19(b),顶点v2或在ext(C)中,不妨假定v2∈int(C),于是边v2v4,v2v6将int(C)分成两个区域。设C1=v1v4v2v6v1,G2=v4v2v6v3v4,v5必然位于ext(C),int(C1),int(C2)三个区域之一。(1)若v5∈int(C),则v2v5与C相交,与K3..3是平面图矛盾。(2)若v5∈int(C1),则v3v5与C1相交,也矛盾。(3)若v5∈int(C2),则v1v5与C2相交,同样产生矛盾。同理可证,当v2∈ext(C)时,也产生矛盾。故假设不成立,即K3..3不是平面图。V1V2V1V6Int(C1)Ext(C)V4V3V5V6V4(课后答案网a)图7-19(b)24设G是连通平面图,最短回路长度是k(k≥3),边数为u,顶点数为v,证明u≤k(v-2)/(k-2)证因为最短回路长度是,而平面图的每一个面是由一个回路所围起来的,因此对于任一个面都有,于是有∑f∈F(G)dG(f)≥k＆其中＆是图G的面数。再由∑f∈F(G)dG(f)=2u可知2u≥k＆,即2u/k≥＆,根据欧拉公式可得v-u+2u/k≥2由此能够推出u≤k(v-2)/(k-2).25利用上题结果说明下面各图不是平面图。.com11

76资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。(a)(b)图7-20解图7-20()中:边数u=9,顶点数v=6,最短路长k=4,因为u=9≮k(v-2)/(k-2)=8于是,由上题结果可知7-20(a)不是平面图。图7-20()中:边数u=15,顶点数v=10,最短路长k=5,因为课后答案网u=15≮k(v-2)/(k-2)=40/3因此7-20(b)不是平面图。26若是平面图,而且的所有面全由长度为3的回路围成,证明:u=3v-6。证因为中所有面由长度为3的回路围成,因此对任意f∈F(G),都有dG(f)=3,从而∑f∈F(G)dG(f)=3﹠。其中﹠为G的面数。再由∑f∈F(G)dG(f)=2u,其中u为G的边数,可得3﹠=2u,代入欧拉公式,得v-u+2u/3=2即u=3v-6证毕。.com12