离散数学高概率考试题

(2)（高概）证明若S为集合X上的二元关系：a)S是传递的，当且仅当(S∘S)⊆S证明：必要性任取序偶a,b∈S∘S,则存在c∈X,使得a,c∈S∧c,b∈S,因为S传递，故a,b∈S,即S∘S⊆S.充分性对任意序偶a,b∈S∧b,c∈S,有a,c∈S∘S,因为S∘S⊆S,故有a,c∈S,S传递.(3)（中难）设S为X上的关系，证明若S是自反的和传递的，则S∘S=S。证明:S传递S∘S⊆S;以下只需证明S⊆S∘S.x,yS,因为S自反，有x,xS,由关系合成运算的定义，有x,yS∘S，即S⊆S∘S。本命题的逆不真，举反例如下：空关系满足∘=,但仅传递而不自反。(6)（中概低难）设R为集合X上的二元关系，R在X上反传递⇔∀x∀y∀z(x∈X∧y∈X∧z∈X∧xRy∧yRz→xRz)当且仅当(R∘R)∩R=φ。证明：必要性任取序偶a,b∈R∘R,则存在c∈X,使得a,c∈R∧c,b∈R,因为R反传递，故a,b∉R,即R∘R中任何序偶都不属于R，因此(R∘R)∩R=φ.充分性对R中任意序偶aRc∧cRb,有a,b∈R∘R,因为(R∘R)∩R=φ,故a,b∉R，因此，R反传递.(8)(中概中上难度)设R,S,T为集合X上的关系，证明R∘(S∪T)=R∘S∪R∘T证明：a)任取序偶a,b∈R∘(S∪T),则存在c∈X,使得a,c∈R且c,b∈S∪T,若c,b∈S,则a,b∈R∘S,若c,b∈T,则a,b∈R∘T,故a,b∈R∘S∪R∘T,即R∘(S∪T)⊆R∘S∪R∘T.b)任取序偶a,b∈R∘S∪R∘T,则有a,b∈R∘S或a,b∈R∘T,若a,b∈R∘S,则存在c∈X,使得a,c∈R且c,b∈S,若a,b∈R∘T,则存在d∈X,使得a,d∈R且d,b∈T,总之，存在y∈X,使得y,b∈S∪T且a,y∈R,故a,b∈R∘(S∪T),即R∘(S∪T)⊇R∘S∪R∘T.综合a)和b)，有R∘(S∪T)=R∘S∪R∘T.3-8（2）算闭包。高概3-10(4)（高概）设R是一个二元关系，设S={a,b|对于某一c，有a,cR且c,bR}。证明若R是一个等价关系，则S也是一个等价关系。证明：显然，S=R∘R。为方便讨论，设R为X上二元关系。自反性xX,R自反,有x,xR，于是x,xR∘R,即R∘R自反;对称性若a,bR∘R,则存在xR，使aRx且xRb。由R对称，知bRx且xRa，故b,aR∘R，R∘R是对称的;传递性若a,bR∘R且b,cR∘R，则存在x1,x2X,使aRx1且x1RbbRx2且x2Rc,R传递，知aRb且bRc，于是a,cR∘R，即R∘R传递。综上所述,R∘R为X上等价关系。(5)（超高概率）设正整数的序偶集合A，在A上定义的二元关系R如下：x,y,u,vR当且仅当xv=yu,证明R是一个等价关系。证明：由已知x,yRu,vxv=yux/y=u/v自反性a,bA,因为a/b=a/b,故a,bRa,b,即R自反；对称性若a,bRc,d,则a/b=c/d,即c/d=a/b，故c,dRa,b，即R对称；传递性若a,bRc,d且c,dRe,f，则a/b=c/d且c/d=e/f，显然有a/b=e/f，故a,bRe,f，即R传递。综上所述，R是A上的等价关系。(6)（低概率较易）设R是集合A上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在一个b，使a,b在R之中，则R是一个等价关系。证明：只需证明R是自反的。aA,则bA,使aRb，由R对称，知bRa，由R传递，知aRa，故R自反。(8)（主流考试题，超高概率）设C*是实数部分非零的全体复数集合，C*上关系R定义为：(a+bi)R(c+di)⇔ac0，证明R是等价关系，并给出关系R的等类几何说明。证明：a×a0⇔(a+bi)R(a+bi),R自反;(a+bi)R(c+di)⇔ac0(c+di)R(e+fi)⇔ce0,显然有ae0,故(a+bi)R(e+fi)，R传递;(a+bi)R(c+di)⇔ac0⇔ca0⇔(c+di)R(a+bi),故R对称。综上所述，R是C*上的等价关系。关系R将C*划分为两种等价类，[正实数+bi]R与[负实数+bi]R,在复平面上，以垂直的虚数坐标轴为分界线，将复数分为左右两部分。习题3-12(1)（高概低难）答案:P的最大元：x1最小元：没有极大元：x1极小元：x4,x5{x2,x3,x4}{x3,x4,x5}{x1,x2,x3}上界：x1x1,x3x1下界：x4无x4上确界：x1x3x1下确界：x4无x4(2)（超高概率）答案：线(全)序；良序231423143412341234123412（2）（低概）设f:AB,这里CA,证明f(A)-f(C)f(A-C)证明：bf(A)-f(C),则bf(A)且bf(C),因于是存在aA,使f(a)=b。因为f(a)f(C)，必须aC,又因为CA,于是aA-C，即f(a)=bf(A-C)。综上所述，f(A)-f(C)f(A-C)(3)（高概）假设f和g是函数，且有fg和domgdomf，证明f=g。证明：只需证明gf。任意x,yg,则xdomg。因为domgdomf，知xdomf。设f(x)=y1,由fg得x,y1g，g是函数，必须y1=y。于是，x,yf，即gf。（8）（中上难高概）假设f:A→B并定义一个函数G：B→ℐ(A),对于b∈B,G(b)={x∈A|f(x)=b}证明,如果f是A到B的满映射，则G是入射的;其逆成立吗？证明：B中任取元素b1,b2,且b1≠b2,因为f是A到B的满射函数，故A中存在元素a1,a2,使得f(a1)=b1,f(a2)=b2,显然a1≠a2,否则同一个自变量同时对应两个不相等的函数值b1,b2。设G(b1)=M1,G(b2)=M2,根据函数G的定义，有a1∈M1,a2∈M2,由于a1≠a2,故必有M1≠M2。所以，G为入射。以下考察逆命题，即G入射是否能推出f满射：B中任取元素b1,设G(b1)=M1,因为函数G为入射，故不存元素b2∈B且b2≠b1,使得G(b2)=M1。显然，当M1为空集时，b1在函数f中找不到原象，故函数f不定是满射。(3)（高概）设f◦g是复合函数，如果f◦g是满射的，那么f是满射的。如果f◦g是入射的，那么g是入射的。如果f◦g是双射的，那么f是满射而g是入射的。证明：设f：B→C，g:A→B，C中任取元素c,因为f◦g为满射,故存在a∈A,使得f◦g(a)=c,故存在b∈B,使a,b∈g,b,c∈f,即对任意c∈C,存在b∈B，使得f(b)=c,所以，函数f为满射。任取a1,a2∈A且a1≠a2,设g(a1)=b1,g(a2)=b2,f(b1)=c1,f(b2)=c2,即f◦g(a1)=c1,f◦g(a2)=c2,由于f◦g为入射函数且a1≠a2,故c1≠c2,g为函数，故必须b1≠b2,所以，函数g为入射。由a)和b)的结论，显然可证得该命题。(4)(难题，一般不考)试证若f:A→B,g:B→A,且g◦f=Ia,f◦g=Ib,则g=f－1且f=g－1。证明：首先证明函数f为双射。A中任取a1,a2且a1≠a2,设f(a1)=b1,f(a2)=b2,因为g◦f=IA，有g◦f(a1)=g(b1)=a1,g◦f(a2)=g(b2)=a2,因为g是函数且a1≠a2,故必须b1≠b2,所以f为入射。B中任取b,设g(b)=a,因为f◦g=IB,有f◦g(b)=f(a)=b,故f为满射。综上所述f为双射，其逆函数成立。同理可证明函数g也为双射，其逆函数成立。任取序偶b,a∈g，即g(b)=a,因为f◦g=IB,有f◦g(b)=f(a)=b,所以a,b∈f,＜b,a∈f－1，g◦f－1。任取序偶b,a∈f－1，即f－1(b)=a，f(a)=b因为g◦f=IA,有g◦f(a)=g(b)=a,故b,a∈g，f－1◦g。所以g=f－1。同理可证f=g－1。(5)（高概中难）设A,*是一个半群，而且对于A中的元素a和b,如果a≠b必有a*b≠b*a,试证明对于A中每个元素a,有a*a=a对于A中任何元素a和b，有a*b*a=a对于A中任何元素a,b和c,有a*b*c=a*c证明：方法一A中任取元素a,设a*a=b且b≠a,则有(a*a)*a=b*a,而(a*a)*a=a*(a*a)=a*b即有a*b=b*a,与已知矛盾,故必须b=a,即a*a=a。A中任取元素a,b，设a*b*a=c，设c≠a,有a*c=a*(a*b*a)=(a*a)*(b*a)=a*b*a=c,c*a=(a*b*a)*a)=(a*b)*(a*a)=a*b*a=c即a*c=c*a=c，这与已知不符，故必有a=cA中任取元素a,b,c,设a*b*c=x，且x≠a*c,则有(a*c)*x=(a*c)*(a*b*c)=a*b*cx*(a*c)=(a*b*c)*(a*c)=a*b*c,故(a*c)*x=x*(a*c)=a*b*c,与已知不符，必须a*c=x。证明：方法二aba*bb*aa*b=b*aa=b(逆反式)由结合律知(a*a)*a=a*(a*a)，必有a*a=a。(a*b*a)*a=a*b*(a*a)=a*b*a=a*(a*b*a)故,(a*b*a)=a。(a*b*c)*(a*c)=a*b*(c*a*c)=a*b*c=(a*c*a)*b*c=(a*c)*(a*b*c)，故(a*b*c)=a*c。(2)（高概中难）设A,*是半群，e是左幺元且对每一个xA,存在ˆxA,使得ˆx*x=e。证明:对于任意的a,b,cA,如果a*b=a*c，则b=c。通过证明e是A中幺元，证明A,*是群。证明：对任意的a,b,cA，若a*b=a*c，则存在ˆaA,使得ˆa*a=e，于是a*b=a*cˆa*(a*b)=ˆa*(a*c)(ˆa*a)*b=(ˆa*a)*c(半群结合律)e*b=e*cb=c(e是左单位元)对任意aA,则存在ˆaA，使得ˆa*a=e。于是,ˆa*(a*e)=(ˆa*a)*e=e*e=e=ˆa*a，由a)所证得的消去律，有a*e=a，即e为右单位元，因此e为单位元。以下只需证明ˆa为a的逆元，则A,*必为群。显然，ˆa*a=e，即ˆa为a的左逆；又因为ˆa*(a*ˆa)=(ˆa*a)*ˆa=e*ˆa=ˆa*e，由消去律，有a*ˆa=e，即ˆa也是a的右逆。即，A中每一个元素a都有逆元。5-4的（3）题是超高概中难5-5的四题超高概简单：答案：是循环群，生成元是【3】和【5】。1、（超高概率）（1）设G＝｛f|f:x→ax+b,其中a,b∈R且a≠0,x∈R｝二元运算◦是映射的复合。证明G,◦是一个群.（2）若S和T分别是由G中a=1和b=0的所有映射构成的集合，证明S,◦和T,◦都是子群。（3）写出S和T在G中的所有左陪集.证明：任取G中任取f1,f2且f1≠f2,设f1(x)=a1x+b1,a1≠0,f2(x)=a2x+b2,a2≠0,则f1◦f2(x)=f1(a2x+b2)=a1(a2x+b2)+b1=a1a2x+a1b2+b1，显然a1a2≠0且f1◦f2∈G,◦运算封闭。设f3∈G,f3≠f1≠f2,f3(x)=a3x+b3,a3≠0,f1◦(f2◦f3)(x)=f1(a2a3x+a2b3+b2)=a1a2a3x+a1a2b3+a1b2+b1(f1◦f2)◦f3(x)=(f1◦f2)(a3x+b3)=a1a2(a3x+b3)+a1b2+b1=a1a2a3x+a1a2b3+a1b2+