离散数学试卷及答案(12)

离散数学试卷（十二）76一、填空20%（每空2分）1、设集合A={1，2，3，4，5，6，7，8，9，10}，定义A上的二元关系“≤”为x≤y=x|y,则yx=。2、设},2|{NnxxAn，定义A上的二元运算为普通乘法、除法和加法，则代数系统A,*中运算*关于运算具有封闭性。3、设集合S={α，β，γ，δ，ζ}，S上的运算*定义为*αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ则代数系统S，*中幺元是，β左逆元是，无左逆元的元素是。4、在群坯、半群、独异点、群中满足消去律。5、设G,*是由元素Ga生成的循环群，且|G|=n，则G=。6、拉格朗日定理说明若H,*是群G,*的子群，则可建立G中的等价关系R=。若|G|=n,|H|=m则m和n关系为。7、设f是由群G,☆到群G,*的同态映射，e是G中的幺元，则f的同态核Ker(f)=。二、选择20%（每小题2分）1、设f是由群G,☆到群G,*的同态映射，则ker(f)是（）。A、G的子群；B、G的子群；C、包含G；D、包含G。离散数学试卷（十二）772、设A，+，·是环，Aba,，a·b的关于“+”的逆元是（）。A、(-a)·(-b)；B、(-a)·b；C、a·(-b)；D、a·b。3、设A，+，·是一代数系统且A，+是Abel群，如果还满足（）A，+，·是域。A、A，·是独异点且·对+可分配；B、A-{}，·是独异点，无零因子且·对+可分配；C、A-{}，·是Abel群且无零因子；D、A-{}，·是Abel且·对+可分配。4、设A，+，·是一代数系统，+、·为普通加法和乘法运算，当A为（）时，A，+，·是域。A、},,5|{均为有理数babaxx；B、},,5|{3均为有理数babaxx；C、},,,|{kbaIbabaxx且；D、}0|{I，xxx。5、设A,是一个格，由格诱导的代数系统为,,A，则（）成立。A、的分配律对满足,,A；B、bbabaAba,,；C、cbcabaAcba则若,,,；D、bbaabbaaAba)()(,,且有。6、设A,是偏序集，“”定义为：babaAba|,,，则当A=（）时，A,是格。A、{1,2,3,4,6,12}；B、{1,2,3,4,6,8,12,14}；C、{1,2,3,…，12}；D、{1,2,3,4}。7、设,,A是由格A,诱导的代数系统，若对Acba,,，当ab时，有（）A,是模格。A、)()(cabcba；B、)()(cbacac；C、)()(cabcba；D、)()(cabcac。8、在（）中，补元是唯一的。A、有界格；B、有补格；C、分配格；D、有补分配格。离散数学试卷（十二）789、在布尔代数,,,A中，0cb当且仅当（）。A、cb；B、bc；C、cb；D、bc。10、设,,,A是布尔代数，f是从An到A的函数，则（）。A、f是布尔代数；B、f能表示成析取范式，也能表示成合取范式；C、若A={0，1}，则f一定能表示成析取范式，也能表示成合取范式；D、若f是布尔函数，它一定能表示成析（合）取范式。三、8%设A={1，2}，A上所有函数的集合记为AA,是函数的复合运算，试给出AA上运算的运算表，并指出AA中是否有幺元，哪些元素有逆元。四、证明42%1、设R,*是一个代数系统，*是R上二元运算，bababaRba*,，则0是幺元且R,*是独异点。（8分）2、设G,*是n阶循环群，G=(a)，设b=ak，Ik则元素b的阶为dn，这里d=GCD(n,k)。（10分）3、证明如果f是由A,☆到B,*的同态映射，g是由B,*到C,△的同态映射，则fg是由A,☆到C,△的同态映射。（6分）4、设A，+，·是一个含幺环，且任意Aa都有a·a=a，若|A|≥3则A，+，·不可能是整环。（8分）5、K={1,2,5,10,11,22,55,110}是110的所有整因子的集合，证明：具有全上界110和全下界1的代数系统K,LCM,GCD,ˊ是一个布尔代数。（xxKx110,）。（10分）五、布尔表达式10%设)()()(),,(313221321xxxxxxxxxE是布尔代数,,},1,0{上的一个布尔表达式，试写出其析取范式和合取范式。（10分）离散数学试卷（十二）79一、填空20%（每空2分）1、LCM（x,y）；2、乘法；3、α、δ，γ、ζ；4、群；5、},,{12eaaaaGnn，；6、}*,,|,{1HbaGbGaba、nm/；7、})(|{exfGxx且二、选择20%（每小题2分）题目12345678910答案BB，CDABAADCC，D三、8%解：因为|A|=2，所以A上共有22=4个不同函数。令},,,{4321ffffAA，其中：1)2(,2)1(;2)2(,2)1(;1)2(,1)1(;2)2(,1)1(44332211ffffffff1f2f3f4f1f1f2f3f4f2f2f2f2f2f3f3f3f3f3f4f3f3f2f1f1f为AA中的幺元，1f和4f有逆元。四、证明42%1、（8分）证明：[幺]Ra，000*,00*0aaaaaaa即为幺元00**0aaa[乘]Rba,，由于+，·在R封闭。所以Rbababa*即*在R上封闭。[群]Rcba,,)*(**)*()*(*)(*)(*)*(cbacbacbacbcabacbacbacbacbcabacbacbabacbabacbabacba所以离散数学试卷（十二）80因此，〈R，*〉是独异点。2、（10分）证明：（1）11,),,(kdkndnknGCDd设11111nnkkndknbaaae（2）若b的阶不为n1，则b阶mn1，且有)1(1lmln，则有ebm，即eaeaenkdmk11,，即eaaekneknd111，1k有因子l，这与),(knGCDd矛盾。由（1）、（2）知，元素b的阶为dn3、（6分）)(△)())((△))(())(*)(())(()(,,bfgafgbfgafgbfafgbafgbafgAba☆☆所以fg是由A,☆到c,△的同态映射。4、（8分）证明：反证法：如果A，+，·是整环，且|A|≥3，则1,,aaAa且aaa即有1,aa且aaaaaaa)1(，这与整环中无零因子矛盾。所以A，+，·不可能是整环。5、（10分）（1）代数系统K,LCM,GCD,ˊ是由格K,|诱导的，其Hasst图为Hass图中不存在与五元素格和同构的子格。所以K,|格是分配格。（2）1),(,110),(:/100,xxGCDxxLCMxxKx使得1)5,22(,110)5,22(,52211022:GCDLCM如离散数学试卷（十二）81即任元素都有补元，所以K,|有补格。K,LCM,GCD,’是布尔代数。五、布尔表达式10%解：函数表为：1x2x3x),,(321xxxE00000011010101111001101111011110析取范式：)()()()()()(),,(321321321321321321321xxxxxxxxxxxxxxxxxxxxxE合取范式：)()(),,(321321321xxxxxxxxxE