离散数学模拟试卷.doc

离散数学模拟题一、选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。1在命题演算中，语句为真为假的一种性质称为 （ ）A）真值 B）陈述句 C）命题 D）谓词2下列语句中不是命题的只有 （ ）A）这个语句是假的。 B）1+1=1.0C）飞碟来自地球外的星球。 D）凡石头都可练成金。3下列句子是命题的是 （ ）A）水开了吗? B）x1.5C）再过5000年，地球上就没水了。 D）我正在说谎4下列语句中为命题的是 （）A）这朵花是谁的？ B）这朵花真美丽啊！C）这朵花是你的吗？ D）这朵花是他的。5下列语句中不是命题的只有 （ ）A）鸡毛也能飞上天？ B）或重于泰山，或轻于鸿毛。C）不经一事，不长一智。 D）牙好，胃口就好。6下列语句不是命题的是 （ ）A）黄金是非金属。B）要是他不上场，我们就不会输。C）他跑100米只用了10秒钟，你说他是不是运动健将呢?D）他跑100米只用了10秒钟，他是一个真正的运动健将。7下列语句中是命题的只有 （ ）A）1+1=10 B）x+y=10C）sinx+siny0 D）x mod 3=28下列是两个命题变元p，q的小项是 （ ）A）ppqB）pq C）pq D）ppq9关于命题变元P和Q的大项M01表示 ( ) A）PQ B）PQ C）PQ D）PQ10设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为 ( )A） B） C） D） 11令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为 （ ）A）pqB）pq C）pq D）pq12设p：我很累，q：我去学习，命题：“除非我很累，否则我就去学习”的符号化正确的是 （ ）A）pq B）pq C）pq D）pq13若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（ ）A）PQ B）PQ C）PQ D）PQ14下列命题公式中不是重言式的是 （）A）p(qr) B）p(qp)C）p(pp) D）(p(qr)(q(pr)15下列命题公式为重言式的是 （ ）A）p (pq) B）(pp)q C）qq D）pq16以下命题公式中，为永假式的是 （ ）A）p(pqr) B）(pp)pC）(qq)p D）(qp)(pp)17下列是命题公式p(qr)的成真指派的是（ ）A）110，111，100 B）110，101，011 C）所有指派 D）无18设论域为整数集，下列谓词公式中真值为假的是 ( )A） B）C） D） 19设个体域是正整数集，则下列公式中真值为真的公式是 （ ）A）(x)(y)(xy=0) B）(x)(y)(xy=1)C）( x)(y)(xy=2) D）(x)(y)(z)(x-y=z)20设论域为整数集，下列真值为真的公式是 （ ）A） B）C） D）21设个体域是整数集，则下列命题的真值为真的是 （ ）A）yx(xy=1) B）xy (xy0)C）xy (xy=y2) D）yx(xy=x2)22设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于（ ）A）(x)A(x)B B）(x)A(x)BC）A(x)B D）(x)A(x)(x)B23下列等值式不正确的是 （ ）A）(x)A(x)AB）(x)(BA(x)B(x)A(x)C）(x)(A(x)B(x)(x)A(x)(x)B(x)D）(x)(y)(A(x)B(y)(x)A(x)(y)B(y)24下列等价式正确的是 （ ）A）A B）C）A D）25下列等价式不成立的是 ( )A）(x)A(x)(x)A(x)B）(x)A(x)(x)A(x)C）(x)(A(x)B(x)(x)A(x)(x)B(x)D）(x)(A(x)B(x)(x)A(x)(x)B(x)26公式(x)(y)(P(x,z)Q(y)S(x,y)中的(x)的辖域是 ( ) A）(y)(P(x,z)Q(y)B）P(x,z)Q(y)C）P(x,z)D）S(x,z)27谓词公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量词x的辖域是（ ）A）(x)Q(x,z)(x)(y)R(x,y,z) B）Q(x,z)(y)R(x,y,z)C）Q(x,z)(x)(y)R(x,y,z) D）Q(x,z)28公式(x)(y)(P(x,y)Q(z)R(x)中的x ( ) A）只是约束变元 B）只是自由变元C）既是约束变元又是自由变元 D）既非约束变元又非自由变元29在公式中变元y是（ ）A）自由变元 B）约束变元C）既是自由变元，又是约束变元 D）既不是自由变元，又不是约束变元30谓词公式(x)(P(x,y)(z)Q(x,z)(y)R(x,y)中变元x （ ）A）是自由变元但不是约束变元 B）既不是自由变元又不是约束变元C）既是自由变元又是约束变元 D）是约束变元但不是自由变元31令F(x):x是金属，G(y):y是液体，H(x,y):x可以溶解在y中，则命题“任何金属可以溶解在某种液体中”可符号化为 （ ）A）(x)(F(x)(y)(G(y)H(x,y) B）(x)(x)F(x)(G(y)H(x,y)C）(x)(F(x)(y)(G(y)H(x,y) D）(x)(F(x)(y)(G(y)H(x,y)32在个体域D=a,b中，与公式(x)A(x)等价又不含量词的公式是（ ）A）A(a)A(b) B）A(a)A(b) C）A(a)A(b) D）A(b)A(a)33关于谓词公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y)，下面的描述中错误的是 （ ）A）（x）的辖域是（y）（P（x,y）Q(y,z)） B）z是该谓词公式的约束变元C）（x）的辖域是P（x,y） D）x是该谓词公式的约束变元34设论域D=a,b，与公式xA（x）等价的命题公式是 （ ）A）A（a）A（b） B）A（a）A（b）C）A（a）A（b） D）A（b）A（a）35设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（）A） B）C） D）36下列公式是前束范式的是 （ ）A） B）C） D）37下列是谓词演算中的合式公式的是 （）A） B）C） D）38下列式子正确的是 （ ）A）（AB）-C=A-（BC） B）A（BC）=（AB）CC）（AB）=（BA） D）（AB）A39下列式子不正确的是（ ）A）(A-B)-C=(A-C)-B B）(A-B)-C=A-(BC)C）(A-B)-C=(A-C)-(B-C) D）A-(BC)=(A-B) C40下列式子正确的是（ ）A） B） C） D）41设A=，B=P(P(A)，以下正确的式子是 （ ）A）,BB）,B C）,BD）,B42下列命题正确的是（ ）A）l，21，2，l，2，3，1 B）1，21，l，2，l，2，3，2C）1，21，2，1，2 D）1，21，2，2，l，2，343下列命题中，不正确的是（ ）A）, B）,C）, D）, 44设A=a,a，则下列各式正确的是 ( ) A）ap(A)(A的幂集) B）ap(A)C）ap(A) D）a,ap(A)45设A=，B=P（P（A），以下不正确的式子是 （ ）A） ， ， ， 包含于B B） 包含于BC） ， 包括于B D） ， ， 包含于B46设为空集，P(x)是集合x的幂集，下列论断不正确的是 ( )A） P(), P() B）P（），P（）C） P（P（），P（P（） D）P（P（）,P（P（）47设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是 （ ）A）(X-Y)-Z=X-(YZ) B）(X-Y)-Z=(X-Z)-YC）(X-Y)-Z=(X-Z)-(Y-Z) D）(X-Y)-Z=X-(YZ)48集合的以下运算律不成立的是 ( ) A）AB=BA B）AB=BAC）AB=BA D）A-B=B-A49设A=a,b,c，则下列是集合A的划分的是（ ）A）b,c,c B）a,b,a,c C）a,b,c D）a,b,c50设A=a,b,c,d，A上的等价关系R=,IA，则对应于R的A的划分是 （ ）A）a,b,c,d B）a,b,c,dC）a,b,c,dD）a,b,c,d51设R为实数集，函数f：RR，f(x)=2x，则f是 （ ）A）满射函数 B）入射函数 C）双射函数 D）非入射非满射52设N为自然数集(含0)，函数F：NNN，F(n)=是（ ）A）满射，不是入射 B）入射，不是满射C）双射 D）不是入射，不是满射53设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f （ ）A）仅是满射 B）仅是入射 C）是双射 D）无逆函数54设N是自然数集，R是实数集，函数f：R，f(n)=lgn是 ( ) A）入射 B）满射 C）双射D）非以上三种的一般函数55设A=1，2，3，B=a,b，下列二元关系R为A到B的函数的是 ( )A）R=, B）R=,C）R=, D）R=,56设集合X为人的全体，在X上定义关系R、S为R=a，b|a，bXa是b的父亲，S=|a，bXa是b的母亲，那么关系|a，bx a是b的祖母的表达式为 （ ）A）RS B）R-1S C）SR D）RS-157设A=1，2，3，4，5，A上二元关系R=1，2，3，4，2，2，S=2，4，3，1，4，2，则S-1R-1的运算结果是 （ ）A）4，1，2，3，4，2 B）2，4，2，3，4，2C）4，1，2，3，2，4 D）2，2，3，1，4，458设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (2，3，4，62，3，4，6)= （ ）A） O/ B） C）， D），59设集合X=0,1,2,3，R是X上的二元关系，R=,，则R的关系矩阵MR是（ ）A）B） C） D） 60集合A=1，2，3上的下列关系矩阵中符合等价关系条件的是（ ）A） B） C） D）61设A=1，2，3，A上二元关系S=，则S是（ ）A）自反关系 B）反自反关系 C）对称关系 D）传递关系62设A=a,b,c，A上二元关系R=a,a，b,b,a,c，则关系R的对称闭包S(R)是（ ）A）RIA B）R C）Rc,a D）RIA63设X=a,b,c,Ix是X上恒等关系，要使Ixa,b，b,c，c,a，b,aR为X上的等价关系，R应取（ ）A）c,a，a,c B）c,b，b,aC）c,a，b,a D）a,c，c,b64非空集合A上的二元关系R若是自反和对称的，则R是 ( )A）偏序关系 B）等价关系 C）相容关系 D）拟序关系65设实数集R上的二元运算为：xy=x+y-2xy，则不满足 ( ) A）交换律 B）结合律 C）有幂等元D）有零元66设S是自然数集，则下列运算中不满足交换律的是 ( ) A）a*b=|a-b| B）a*b=abC）a*b=maxa,b D）a*b=mina,b67在实数集合R上，下列定义的运算中是可结合的只有 ( )A）a*b=a+2b B）a*b=a+b-2abC）a*b=a-b+2ab D）a*b=a-b-2ab68在实数集合R上，下列定义的运算中不可结合的是 （）A）a*b=a+b+2ab B）a*b=a+bC）a*b=a+b+ab D）a*b=a-b69在自然数集N上，下列定义的运算中不可结合的只有（ ）A）a*b=min(a,b) B）a*b=a+bC）a*b=GCD(a,b)(a,b的最大公约数) D）a*b=a(mod b)70设Z为整数集，A为集合，A的幂集为P(A)，+、-、/为数的加、减、除运算，为集合的交运算，下列系统中是代数系统的有（ ）A）Z，+，/ B）Z，/ C）Z，-，/ D）P(A)，71设Z是整数集合，则下面定义的二元运算不能使Z与构成代数系统的是（ ）A）i j=|i-j|,i,jZ B）i j=ij-j2，i,jZC）i j=i/j,i,jZ D）i j=i2+j2+1,i,jZ72在下列代数系统中，不是环的只有（ ）A）Z，+，*)，其中Z为整数集，+，*分别为整数加法和乘法。B）(Q，+，*)，其中Q为有理数集，+，*分别为有理数加法和乘法。C），其中R为实数集，+为实数加法，a*b=a+2b。D），其中Mn(R)为实数集nn阶矩阵结合，+，*是矩阵加法和乘法。73下列整数集对于整除关系都构成偏序集，而能构成格的是（ ）A）l，2，3，4，5 B）1，2，3，6，12C）2，3，7 D）l，2，3，774如右图所示的有界格中，元素b的补元是（ ）A）aB）0C）cD）d75若(A，*)是一个代数系统，且满足结合律，则(A，*)必为 ( ) A）半群 B）独异点 C）群D）可结合代数76设是有限循环群，则下列说法不正确的是 ( )A）的生成元是唯一的B）有限循环群中的运算*适合交换律C）G中存在一元素a，使G中任一元素都由a的幂组成D）设a是的生成元，则对任一正整数i，存在正整数j使a-i=aj77下列集合关于所给定的运算成为群的是 （ ）A）已给实数a的正整数次幂的全体，且a0，1，-1，关于数的乘法B）所有非负整数的集合，关于数的加法C）所有正有理数的集合，关于数的乘法D）实数集，关于数的除法78设群G=中，A的元素个数大于1，若元素aA的逆元素为bA，则a*b的运算结果是 ( )A）aB）b C）G中零元素D）G中幺元79设G,*是群，且|G|1，则下列命题不成立的是 （ ）A）G中有幺元 B）G中有零元C）G中任一元素有逆元 D）G中除了幺元外无其他幂等元80设有代数系统G=A，*，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是 （ ）A）矛盾式 B）重言式 C）可满足式 D）公式pq81设A是非空集合，P(A)是A的幂集，是集合交运算，则代数系统P(A),的幺元是 ( )A）P(A) B） C）A D）|82设*是集合A上的二元运算，称Z是A上关于运算*的零元，若（ ）A）有x*Z=Z*x=Z B）ZA，且有x*Z=Z*x=ZC）ZA，且有x*Z=Z*x=x D）ZA，且有x*Z=Z*x=Z83下列各代数系统中不含有零元素的是 （ ）A）Q，*Q是全体有理数集，*是数的乘法运算B）Mn(R),*,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算C）Z，Z是整数集，定义为xxy=xy,x,yZD）Z，+，Z是整数集，+是数的加法运算84下列集合对所给的运算是封闭的只有 （ ）A）非零整数集合Z*上的除法运算B）全体nn实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算C）全体nn实矩阵集合Mn（R）上的矩阵加法和乘法运算D）A=1，2，10，x*y=LCM（x，y），即x，y最小公倍数85设i是虚数，是复数乘法运算，则G=是群，下列是G的子群是 （ ）A） B）-1, C）i, D）-i,86设R为实数集，R+=x|xRx0，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是 （ ）A）R+中的有理数B）R+中的无理数C）R+中的自然数D）1，2，387设是环，则下列正确的是 （ ）A）是交换群B）是加法群C）对*是可分配的D）*对是可分配的88设是环，则下列说法不正确的是 （ ）A）是交换群 B）是半群C）*对是可分配的 D）对*是可分配的89在布尔代数L中，表达式(ab)(abc)(bc)的等价式是（ ）A）b(ac) B）(ab)(ab)C）(ab)(abc)(bc) D）(bc)(ac)90下列各图中既是欧拉图，又是汉密尔顿图的是（ ）A） B） C） D）91设G是连通平面图，G中有6个顶点8条边，则G的面的数目是 （ ）A）2个面 B）3个面 C）4个面 D）5个面92设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（ ）A）10 B）12 C） 14 D） 1693无向图G中有16条边，且每个结点的度数均为2，则结点数是（ ）A）8 B）16 C）4 D）3294设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是 （ ）A）3 B）4 C）5 D）695设无向图G的边数为m，结点数为n，则G是树等价于 （ ）A）G连通且m=n+1 B）G连通且n=m+1C）G连通且m=2n D）每对结点之间至少有一条通路96一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条（ ）A）汉密尔顿回路 B）欧拉回路C）汉密尔顿通路 D）初级回路97结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）A）欧拉图 B）汉密尔顿图 C）非平面图 D）不存在的98无向图G是欧拉图当且仅当G是连通的且（ ）A）G中各顶点的度数均相等 B）G中各顶点的度数之和为偶数C）G中各顶点的度数均为偶数 D）G中各顶点的度数均为奇数99设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大连通性是 ( ) A）不连通 B）弱连通 C）单侧连通D）强连通100一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点。 ( ) A）G没有奇数度结点B）G有1个奇数度结点C）G有2个奇数度结点D）G没有或有2个奇数度结点二、填空题1不能再分解的命题称为_，至少包含一个联结词的命题称为_。2在命题演算中，五个联结词的含义是由其_表唯一确定的，而不是由其类似的_语言的含义确定。3判断一个语句是否为命题，首先要看它是否为_，然后再看它是否具有唯一的_。4求一个公式的主析取或主合取范式的方法，有_法和_法。5一公式为_之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元及其否定；一公式为_之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定。6合取范式具有形式A1A2An(n1)，其中A1，A2，An是由_及其_所组成的析取式。7设命题P为“明天上午8点下雨”，Q为“明天上午8点下雪”，R为“我去学校”，则“如果明天上午8点不下雨且不下雪则我去学校”可表示为公式_；而“只有当明天上午8点不下雪并且不下雨时我才去学校”可表示为公式_。8若H1H2Hn是_，则称H1,H2,Hn是相容的，若H1H2Hn是_，则称H1,H2,Hn是不相容的。9前束范式具有形式(Q1V1)(Q2V2)(QnVn)A，其中Qi(1in)为_，A为_的谓词公式。10设论域是a,b,c，则(x)S(x)等价于命题公式_；()S(x)等价于命题公式_。11谓词公式(x)( y)（P(x,y)R(y)Q(y)，则其约束变元是_，自由变元是_。12使公式(x)( y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x。13设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)_,其中量词(x)的辖域是_。14给定谓词合式公式A，其中一部分公式形式为()B(x)或(x)B(x)，则量词，后面所跟的x称为_，而称B为相应量词的_。15使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的条件是_不含有y，_不含有x。16设A为任意集合，请填入适当的运算符，使式子A_A=；A_ _A=成立。17设A=,B=0,1,所有从A到B的双射函数是f1=_，f2=_。18设函数f:XY,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是_函数，如果ranf=Y，则称f是_函数。19设X，U，V，Y都是实数集，f1：XU，且fl(x)ex； f2：UV，且f2(u)u (1+u)；f3：VY，且f3(v)=cosv。那么f3f2f1的定义域是_，而复合函数(f3f2f1)(x)= _。20设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则domR=_，ranR=_。21称集合S是给定非空集合A的覆盖：若S=S1，S2，Sn，其中SiA，Si，i=1，2，n，且_；进一步若_，则S是集合A的划分。22设X=1,2,3上的关系R的关系图如下，从关系图可知R具有_，_和传递性等性质。23A=1,2,3,4上二元关系R=2，4，3，3，4，2，R的关系矩阵MR中m24=_,m34=_。24设R为A上的关系，则R的自反闭包r(R)= _，对称闭包s(R)= _。25设s,*是群，则那么s中除_外，不可能有别的幂等元；若s,*有零元，则|s|=_。26设Z是整数集，在Z上定义二元运算*为a*b=a+b+ab，其中+和是数的加法和乘法，则代数系统的幺元是_，零元是_。27设A为集合，P(A)为A的幂集，则P(A)，是格，若x,yP(A),则x,y最大下界是_，最小上界是_。28设是一个偏序集，如果S中的任意两个元素都有_和_，则称S关于构成一个格。29设A，是偏序集，若A中_都有最小上界和_ _则称A关于偏序构成格。30设A=2,3,6,12,是A上的整除关系，则偏序集A，的最大元是_，极小元是_。31设B,，0，1是布尔代数，对任意的aB,有aa=_,aa=_。32设G，*是群，若G中存在一个元素a，使得G中任意元素都可由a的幂生成，则称该群是_，元素a称为该群的_。33已知G=(其中i=，是数的乘法)是群，则-l的阶是_；i的阶是_。34对代数系统，其中*是S上的二元运算，若a，bS，且对任意的xS，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_，称b为运算“*”的_。35设是群，则满足结合律和_；若Sl，S中不可能有_。36对实数的普通加法和乘法，_是加法的幂等元，_是乘法的幂等元。37在代数系统A，*中，A=a，*是A上二元运算，则该代数系统的单位元是_ _，零元是_。38有向图D如下：D的邻接矩阵A=(aij)33,则a11=_,a32=_。39一个连通平面图G有10条边，G中度为1的顶点有2个，其余是度为6的顶点，则G中共有_个顶点，_个面。40在一棵根树中，仅有一个结点的入度为_，称为树根，其余结点的入度均为_。41一个_且_的无向图称为树。42在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_，如果V有n个结点，那么它还是_度正则图。43若一条路中，所有边均不相同，则此路称作_ _；若一条路中所有的结点均不相同，则称此路为_ _。44无向图G具有一条欧拉回路，当且仅当G是_，并且所有结点的度数都是_。45在下图中，结点v2的度数是_，结点v5的度数是_。三、计算题1作出命题公式(p(qr)q的真值表，并写出其主析取范式。2构造命题公式(p (q r)p的真值表。3求(PQ)(PQ)的主合取范式并给出所有使命题为真的赋值。4求下列公式的主析取范式和主合取范式：（PQ）（PR）5求公式(x)(F(x)(y)G(xy,z)(z)H(x,y,z)的前束范式。6求公式(x)F(x,y)(y)G(x,y)(x)H(x)的前束范式。7若集合A=a，b，c的幂集为P(A)，集合B= O/， O/ 的幂集为P(B)，求P(A)P(B)。 8设A2，3，4，6，8，12，24，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。9设A=1,2,3,4,5，A上偏序关系 R=1，2，3，2，4，1，4，2，4，3，3，5，4，5IA;(1)作出偏序关系R的哈斯图(2)令B=1,2,3,5，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。10设A=a,b,P(A)是A的幂集，是对称差运算，可以验证是群。设n是正整数，求(a-1ba)na-nbnan11设A=a,b,c,d,G=是交换群,a是G的单位元。G的运算表如下：*abcdaabcdbbax1x2ccx4ax3ddx5x6a求x1、x2、x3、x4、x5、x6并说明道理12设集合A=1,3,5,7,9,11,13,15，A上的一个划分S=1,15,3,9,11,13,5,7。试求由S导出的A上的等价关系R。13设A=a,b,c,d，R=,。试用关系图表示R及R的传递闭包。14设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。15设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。16一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。四、证明题（本大题共3小题，第31、32小题各6分，第33题8分，共20分）1在个体域D=a1,a2,，an中证明等价式： (x)(A(x)B(x)(x)A(x)(x)B(x)2证明A(BC),(CD)E, F(DE)|-A(BF)成立。3设f：XY，g：YX，gf为X上恒等函数，证明f是入射和g是满射。4设R是集合X上的二元关系，证明R是X上传递关系当且仅当RRR。5设R是集合A上对称和传递关系，且对于A中每个元素a，在A中同时也存在一个b，使在R之中，证明R是A上等价关系。6设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。 证明：F, 是群。7设M是偶数集，和是数的加、乘运算，证明是一个环。8设G是简单平面图，G有n个顶点m条边，且m30，证明G中存在一项点v，d（v）4。9设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k2),证明T中至少有2k-2片树叶。10证明：如果一个有向图G是弱连通图且是欧拉图，则G是强连通图。11设G,*是群，aG，N=ah-1a|hG,证明N，*是G,*的子群。五、应用题1对下面推理进行符号化，并作证明。会操作计算机的人都认识26个英文字母。文盲都不认识26个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。(个体域：所有人的集合)2对下面推理进行符号化，并作证明。任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车，或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。3如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C+语言。只要他学过DELPHI语言或者C+语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。4判断下面推理是否正确，并证明你的结论。如果小王今天家里有事，则他不会来开会。如果小张今天看到小王，则小王今天来开会了。小张今天看到小王。所以小王今天家里没事。5某发电厂a要向b,c,d,e四个地点送电，已知发电厂可以和b,c,d直接架接电线，地点e可以和b与d直接架设电线，其他由于地理原因无法直接架设电线，在a,b,c,d和e之间架设电线时不能有回路存在，否则会造成浪费。请找出所有电线架设方案，使从a可向b，c，d，e供电。6有6个村庄Vi，i=l，2，6欲修建道路使村村可通。现已有修建方案如下带权无