离散07—08期末考试题(B卷)

注：试题字迹务必清晰，书写工整。本题6页，本页为第1页教务处试题编号：四川大学期末考试试题（闭卷B）（2007-2008学年第1学期）1．下列命题公式是永真式的是（）A．（P∧～P）↔QB．（～（P→Q）∧Q）→QC．（P→Q）∨QD．（P∨P）∧（P→～P）2．命题公式A不存在主合取范式，则A是（）A．矛盾式B．可满足式C．永真式D．都不对3．谓词公式（x）P（X）→（x）P（X）是（）A．可满足式B．矛盾式C．无法判别D．永真式4．公式（x）（y）（P（x,y）∧Q（z））→R（x）中的x（）A．仅是约束变元B．仅是自由变元C．既是约束变元又是自由变元D．既不是约束变元也不是自由变元5．设S={I，Q，R}，下列命题哪个正确（）A．IQ，QR则IRB．-1∈I，I∈S则-1∈SC．D．都不正确6．下面的表达哪个不正确（）A．{a}{{a}}B．{a}∈{{a}}C．{a}{a，{a}}D．{a}∈{a，{a}}7．若集合A中共有n个元素，那么A上不同二元关系的个数为（）A．n2B．2n2C．2n2-1D．都不对8．下列判断正确的是（）A．若R，S是自反的，则R-S是自反的B．若R，S是对称的，则R○S是对称的C．若R，S是传递的，则R∩S是传递的D．若R，S是传递的，则R∪S是传递的9．设R，S是非空集合上的等价关系，则R∪S是（）A．一定具有自反性，但不一定保持对称性B．一定具有对称性，但不一定保持自反性C．一定具有自反性和对称性D．是等价关系10．在5个元素的集合上可以定义的单射数目为（）A．5B．10C．60D．12011．设函数f：X→Y；X，Y是有限集合，f是单射，那么下列关系一定不成立的是（）A．|X|=|Y|B．|X|﹥|Y|C．|X|﹤|Y|D．X∈Y12．平面非连通图G，n-m+f的值为（）A．2B．ω（G）C．ω（G）+1D．313．若一棵树G（n，n-1）只有两个叶节点，则（）不正确A．不包含点度大于等于3的枝点B．节点总度数大于等于4C．最少包含2个节点D．节点总度数=2+2（n-2）课程名称：任课教师：学号：姓名：本题6页，本页为第2页教务处试题编号：14．设10阶简单连通图有32条边，则最少要去掉（）条边才能使其成为平面图A．10B．12C．32D．815．下列代数系统，（）是群A．〈S1={1，1/2，2，1/3，1/4，4}，*：为普通乘法〉B．〈S2={ai|ai∈R，i=1，2，3…n}，o：ai，aj∈S2→aioaj=ai〉C．〈S3={0，1}，*：为普通乘法〉D．〈S4={-1，1}，+：为普通加法〉二、多项选择题（本大题共5小题，每小题2分，共10分）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。1.设A＝{1,2,3}，则右图所示A上的关系具有（）。1).自反性2).反自反性3).对称性4).反对称性5).传递性2.设A＝{a}，B＝{a，{a}}1).A∈B2).AB3).{A}∈B4).{A}B5).{A}{B}3.下列命题公式中，（）在解释{～P，Q，～R}下为真。1).(P∧Q)→R2).(P∨Q)→R3).(RQ)→P4).P→(Q→R)5).～(P∧Q)→R4.树是（）。1).欧拉图2).哈密顿图3).二部图4).平面图5).连通图5.在一个环（R，+，.）中，以下命题不一定成立的有1)a.0=02)a.(-b)=-(a.b)3)-a.(-b)=a.b4)a.b=0，则a=0或b=05)a.b=a.c，则b=c三、简答题（本大题共4小题，每小题2.5分，共10分）1、试述谓词逻辑中自由变元和约束变元的定义。2、试述关系中二元关系的定义3、试述无向图中度数的定义4、试述代数格的定义四、演算题（本大题共5小题，每小题7分，共35分）。1．写出（P∧～R）∨（S∧P）的主析取范式。2．把下面的命题符号化成逻辑公式：312课程名称：任课教师：学号：姓名：本题6页，本页为第3页教务处试题编号：每个旅客要么坐硬座要么坐软座，每个旅客当且仅当富裕时坐软座，并非每个旅客都富裕。因此，有些旅客坐硬座。3．利用矩阵方法求下图的所有强分图：4．将┌123456┐下式表示成循环之积，并求其逆置换└516324┘5．无向图G有21条边，12个3度顶点，其余顶点的度数均为2，求G的阶数n（写出求解过程）五、推理与证明题（本大题共4小题，共30分）。1．（7分）证明〈{a+b√2|a，b∈I}，+，x〉为环（+，x为普通加法和乘法）。2．（7分）证明：简单连通无向图的任何一条边，都是G的某一棵生成树的边。3．（7分）证明P→（Q→S）是{P→（Q→R），R→（Q→S）}的逻辑结果。4．（9分）设R是A上的自反和传递关系，S也是A上的关系，且满足〈x，y〉∈S〈=〉（〈x,y〉∈R）∧（〈y,x〉∈R），证明S是一个等价关系。A卷答案1、④2、③3、③4、②5、②6、④7、③8、③9、②10、④11、③12、③13、②14、②15、③1、1）4）5）2、2）4）5）3、1）2）3）5）4、1）2）3）4）5、3）4）三1、具有确切真值的陈述句称为命题2、设f是从X到Y的函数，若f满足：对任意x1,x2∈X，若x1≠x2，则f(x1)≠f(x2)，则称f为从X到Y的单射或1-1映射；V1V2V3V4课程名称：任课教师：学号：姓名：本题6页，本页为第4页教务处试题编号：3、设G＝V,E是一个简单有向图，V＝{v1,v2,…,vn}，则n阶方阵A＝(aij)nn称为G的邻接矩阵。其中：4、设〈X，*〉与〈Y,о〉是两个代数系统，如在集合X与Y之间存在一个双射f：XY，使得对a，bX，有：f(a*b)=f(a)оf(b)则称f是从〈X，*〉到〈Y,о〉的同构，记为X≌Y。四1、)()()()()()()()())(())(()()()()())(()())((RQPRQPRPQRPQRQPRQPRPQRPQRRQPRRPQQPPQQPPQPRPPQPRP2、},,,,,,,,,,,,,,,,{)()t()(},,,,,,,,,,,{},,,,,,,,,,,,,{},,,,,,,{11111112121ccbbbccbabaccabaaaRsRRRRrccbcacbbabaaRccbbcbabcabaaaRRccbbbaaaRR3、设G的结点个数为n，由握手定理3×4＋3×（n-3）=21×23×（n-3）=30n-3=10即n=134、Z6={[0]，[1]，[2]，[3]，[4]，[5]}H={[0]，[2]，[4]，}主合取范式主析取范式E,)v,(v0,E,)v,(v,1jijiija课程名称：任课教师：学号：姓名：本题6页，本页为第5页教务处试题编号：[0]H=[2]H=[4]H={[0]，[2]，[4]}=H[0]=H[2]=H[4][1]H=[3]H=[5]H={[1]，[3]，[5]}=H[1]=H[3]=H[5]5、权值=17此题略五1、设N（x）：x是自然数，P（x）：x是奇数，Q（x）：x是偶数F(x):x能被2整除则上述语句可符号化为：)8()8()8()),()(()()(()),()(()()((PFNxQxFxNxxQxPxNx证明：T(7)(10)I)8()11T(2)(9)I)8()8()10US(8)))8()8(()8()9P)))()(()()(()8T(5)(6)I)8()7T(1)I)8()6T(2)(4)I)8()8()5US(3)))8()8(()8()4P))()(()()(()3T(1)I)8()2P)8()8()1PQPQPNxQxPxNxQFQFQFNxQxFxNxNFN2、1）自反性：∵对Ayx),(，x-y=x-y,∴(x,y)R(x,y)2)对称性：设(x1,y1)R(x2,y2)，则x1-y1=x2-y2有x2-y2=x1-y1即(x2,y2)R(x1,y1)3）传递性：设(x1,y1)R(x2,y2)，(x2,y2)R(x3,y3)，则x1-y1=x2-y2=x3-y3，∴(x1,y1)R(x3,y3)故R是等价关系3、证明：1）证,*I是交换群IbaIbababa*,,,1*，I是封闭的课程名称：任课教师：学号：姓名：本题6页，本页为第6页教务处试题编号：∵(a*b)*c=a+b-1+c-1=a+b+c-2a*(b*c)=a+b+c-1-1=a+b+c-2∴*是可结合的∵a*1=a+1-1=a∴1是I,*的幺元,Ia令112*,211aaaaaa，∴a的逆元存在∵a*b=a+b-1=b*a∴,*I是交换群2)证,I是含幺交换半群,,,,IbaIbabababa∴I关于是封闭的cbacbcabacbacbcbacbcbacbacbacbcabacbacbabacbabacba)()()()(∴是可结合的∵令aaaab00,0，∴0是,I的幺元∵abbababa，∴,I是含幺交换半群3）∵)1(1)1()*(cbacbacbacba)(*)()(*)(cacababacaba)1(1cbacba∴)*(cba)(*)(caba同理)(*)()*(acabacb故,*,I是具有幺元的可交换环