《期末练习题12年1学期.doc》由会员分享，可在线阅读，更多相关《期末练习题12年1学期.doc（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date期末练习题12年1学期期末练习题12年1学期习题一. 多重选择填空题(本题包括16个空格，每个空格3分，共48分。每道小题都可能有一个以上的正确选项，须选出所有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)1 命题公式(P(PQ)Q是_式。(1) 重言 (2) 矛盾 (3) 可满足 (4) 非永真的可满足2给定解释I=(D,)=(整数集，f(x,y):f(
2、x,y)=x-y；g(x,y):g(x,y)=x+y；P(x,y):xy)，下列公式中_在解释I下为真。(1) P(f(x,y),g(x,y) (2) xy P(f(x,y),g(x,y) (3) xy(P(x,y) P(f(x,y),x) (4) xy P(f(x,y),g(x,y)3 是集合， =10，则=_。(1) 100 (2) 99 (3) 2048 (4) 1024 (5) 5124 集合=x|x是整数，30，=x|x是质数，x20，C=1,3,5，则=_;=_;=_;=_。(1) 1,2,3,5 (2) (3) 0(4) 1,3,5,7,11,13,17,19 (5) 1,3,5
3、,7 (6) 7,11,13,17,195设A、B、C是集合，下列四个命题中，_在任何情况下都是正确的。(1) 若AB且BC，则AC (2) 若AB且BC，则AC(3) 若AB且BC，则AC (4) 若AB且BC，则AC5127S=1,2,3,4,5,6,7,8,9,10,11,12，是S上的整除关系。S的子集2,4,6，则在(S，)中，的最大元是_；的最小元是_；的上确界是_；的下确界是_。(1) 不存在的 (2) 36 (3) 24 (4) 12 (5) 6 (6) 1 (7) 28设有有限布尔代数(B,+,*,0,1)，则=_能成立。(1) 1 (2) 2 (3) 3 (4) 4 (5)
4、 5 (6) 8 (7) 99 n个结点、m条边的无向连通图是树当且仅当m=_。(1) n+1 (2) n (3) n-1 (4)2n-1 二. 请给出命题公式的主析取范式。(10分)三. 假设下列陈述都是正确的：(1)学生会的每个成员都是学生并且是班干部；(2)有些成员是女生。问是否有成员是女班干部？请将上述陈述和你的结论符号化，并给出你的结论的形式证明。(10分)四. 设R和S是集合上的等价关系,则SR必是等价关系。(10分)六。假设在图G(有向图或无向图)中，有10条边，4个3度的结点，其余结点的度数不大于2。问G中至少有几个结点？(10分)一、选择题1令P：今天下雪了，Q：路滑，则命题
5、“虽然今天下雪了，但是路不滑”可符号化为（）APQBPQCPQDPQ2下列命题公式为重言式的是（）AQ（PQ）BP（PQ）C（PQ）PD（PQ）Q4谓词公式x(P(x)yR(y)Q(x)中量词的辖域是（）ABP（x）C(P(x)yR(y)DP(x), Q(x)5设个体域A=a,b，公式xP(x)xS(x)在A中消去量词后应为（）AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)6下列选项中错误的是（）ABCD7设A=a,b,c,d，A上的等价关系R=, , , IA，则对应于R的A的划分是（）Aa,b, c,dBa, b,c, dCa,b
6、,c,dDa, b, c,d8设R为实数集，函数f：RR，f(x)=2x，则f是（）A满射函数B入射函数C双射函数D非入射非满射10下列运算中关于整数集不能构成半群的是（）Aab=maxa, bBab=bCab=2abDab=|a-b|12设A=a, b, c，R是A上的二元关系，R=, , , ，那么R是（）A反自反的B反对称的C可传递的D不可传递的13设D=为有向图，V=a, b, c, d, e, f, E=, , , , 是（）A强连通图B单向连通图C弱连通图D不连通图14在有n个结点的连通图中，其边数（）A最多有n-1条B至少有n-1条C最多有n条D至少有n条15连通图G是一棵树，当
7、且仅当G中（）A有些边不是割边B每条边都是割边C无割边集D每条边都不是割边16下列命题公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)17下列语句中为命题的是（）A这朵花是谁的？B这朵花真美丽啊！C这朵花是你的吗？D这朵花是他的。18设个体域是整数集，则下列命题的真值为真的是（）Ayx(xy=1)Bxy (xy0)Cxy (xy=y2)Dyx(xy=x2)19关于谓词公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中错误的是（）A（x）的辖域是（y）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元C（x）的辖域是P（x,y）D
8、x是该谓词公式的约束变元20设论域D=a,b，与公式xA（x）等价的命题公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）21集合A=1，2，3上的下列关系矩阵中符合等价关系条件的是（）ABCD22设A=，B=P（P（A），以下不正确的式子是（）A ， ， ， 包含于BB 包含于BC ， 包括于BD ， ， 包含于B23设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f（）A仅是满射B仅是入射C是双射D无逆函数24设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
9、4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，426在实数集合R上，下列定义的运算中不可结合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+abDa*b=a-b27下列集合关于所给定的运算成为群的是（）A已给实数a的正整数次幂的全体，且a0，1，-1，关于数的乘法B所有非负整数的集合，关于数的加法C所有正有理数的集合，关于数的乘法D实数集，关于数的除法28设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A3B4C5D629下列各图中既是欧拉图，又是汉密尔顿图的是（）A B C D30设无向图G
10、的边数为m，结点数为n，则G是树等价于（）AG连通且m=n+1BG连通且n=m+1CG连通且m=2nD每对结点之间至少有一条通路31下列为两个命题变元P，Q的小项是（）APQ PB PQC PQD PPQ32下列语句中是真命题的是（）A我正在说谎B严禁吸烟C如果1+2=3，那么雪是黑的D如果1+2=5，那么雪是黑的33设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A P QB P QC（PQ）D（ P Q）34命题公式（P（PQ）Q是（）A矛盾式B蕴含式C重言式D等价式35命题公式（PQ）R的成真指派是（）A000，001，110，B001，011，101，110，11
11、1C全体指派D无36在公式（）F（x，y）（ y）G（x，y）中变元x是（）A自由变元B约束变元C既是自由变元，又是约束变元D既不是自由变元，又不是约束变元37集合A=1，2，10上的关系R=|x+y=10，xA，yA，则R的性质是（）A自反的B对称的C传递的、对称的D反自反的、传递的38若R和S是集合A上的两个关系，则下述结论正确的是（）A若R和S是自反的，则RS是自反的B若R和S是对称的，则RS是对称的C若R和S是反对称的，则RS是反对称的D若R和S是传递的，则RS是传递的39R=，则下列不是t（R）中元素的是（）ABCD40设A=1，2，3，4，5，6，7，8，下列选项正确的是（）A1A
12、B1，2，3AC4，5ADA41在自然数集N上，下列运算是可结合的是（）Aab=a-2bBab=mina，bCab=-a-bDab=|a-b|45具有4个结点的非同构的无向树的数目是（）A2B3C4D547设A-B=，则有（）AB=BBCABDAB48A，B是集合，P（A），P（B）为其幂集，且AB=，则P(A)P(B)为（）ABCD，49设集合A=1，2，3，10，下列定义的运算关于集合A是不封闭的是（）Ax*y=maxx,yBx*y=minx,yCx*y=GCDx,y,即x,y的最大公约数Dx*y=LCMx,y,即x,y的最小公倍数51设A=1，2，3，4，5，B=6，7，8，9，10，以
13、下关系是从A到B的入射函数的是（）Af =,Bf =,Cf =,Df =,52设简单图G所有结点的度数之和为12，则G一定有（）A3条边B4条边C5条边D6条边53下列不一定是树的是（）A无回路的连通图B有n个结点，n-1条边的连通图C每对结点之间都有通路的图D连通但删去一条边则不连通的图54下面关于关系R的传递闭包t(R)的描述最确切的是（）At(R)是包含R的二元关系Bt(R)是包含R的最小传递关系Ct(R)是包含R的一个传递关系Dt(R)是任何包含R的传递关系55欧拉回路是（）A路径B迹C既是初级回路也是迹D既非初级回路也非迹56.在公式中变元y是（ ）A自由变元B约束变元C既是自由变元
14、，又是约束变元D既不是自由变元，又不是约束变元57设A=1，2，3，A上二元关系S=，则S是（ ）A自反关系B反自反关系C对称关系D传递关系59设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (2，3，4，62，3，4，6)=（ ）A O/BC，D，61结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ）A欧拉图B汉密尔顿图C非平面图D不存在的62无向图G是欧拉图当且仅当G是连通的且（ ）AG中各顶点的度数均相等BG中各顶点的度数之和为偶数CG中各顶点的度数均为偶数DG中各顶点的度数均为奇数63平面图(如下)的三个面的次数分别是（）A11，3，4B11，3，5C12，3，6D
15、10，4，65.设A=a,b,c,则AA中的元素有( )。 A.3个 B.6个 C.8个 D.9个66.设(G,+,*)是一个除环,则它不满足的运算律是( )。 A.加法交换律 B.乘法交换律 C.乘法消去律 D.加法消去律67.对于一个代数系统,以下命题成立的是( )。 A.每个元素必有左逆元 B.一个元素有左逆元,则它也是右逆元 C.一个元素的左右逆元不一定相等 D.一个元素的左逆元存在时必唯一68.若一个代数系统(A,*)满足运算封闭性及结合律,且有幺元,则它是( )。 A.独异点 B.群 C.格 D.布尔代数69.在有3个结点的图中,奇结点的个数为( )。 A.0 B.1 C.1或3
16、D.0或2 71.若图G有一条路经过图中每个结点恰好一次,则G( )。 A.有一条欧拉路 B.是欧拉图 C.有一条汉密尔顿路 D.是汉密尔顿图二、填空题（本大题共10小题，每小题2分，共20分）1任意两个不同的小项的合取为_式，全体小项的析取式必为_式。2公式x(P(x)Q(x,y)zR(y, z)S(x)中的自由变元为_，约束变元为_。3设集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，则 MN=_，MN=_。4设X=1，2，3，f：XX，g：XX，f=,g=,，则fg=_，gf=_。5设A=a,b,c，R是A上的二元关系，且给定R=,，则R的自反闭包r(R)=
17、_，对称闭包s(R)= _。6设*是集合S上的二元运算，若运算*满足_且存在_，则称为独异点。7如下无向图割点是_，割边是_。8无向图G具有生成树，当且仅当_。G的所有生成树中_的生成树称为最小生成树。9、命题公式P7P有_组为T的真值指派，_为F的真值指派。10.一棵有6个叶结点的完全二叉树，有_个内点；而若一棵树有2个结点度数为2，一个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_个叶结点。11.在一棵根树中，有且只有一个结点的入度为_，其余所有结点的入度均为_。12.当f:XY是_函数时，f有逆函数，且f -1。f=_。13.设E=1,2,3,4,5,6,A=1,4,B=1,2
18、,3,C=2,4,则(AB)C=_,幂集P(AB)C)=_。14.由命题变元及其否定所组成的有限个析取式的合取式称为_，由命题变元及其否定所组成的有限个合取式的析取式称为_。15（x）（y）（P（x，y）Q（y，z）xP（x，y）中x的辖域为_，x的辖域为_。16两个重言式的析取是_式，一个重言式与一个矛盾式的析取是_式。17设N是自然数集合，f和g是N到N的函数，且f（n）=2n+1，g（n）=n2，那么复合函数（ff）（n）=_（gf）（n）=_。18、设是群，则满足结合律和_；20设A=1，2，B=2，3，则A-A=_，A-B=_。21设S是非空有限集，代数系统中，其中P（S）为集合S的
19、幂集，则P（S）对运算的单位元是_，零元是_。24在下图中，结点v2的度数是_。25设图D=，V=v1，v2，v3，v4，若D的邻接矩阵A=，则deg-（v1）=_，从v2到v4长度为2的路有_条。26不能再分解的命题称为_，至少包含一个联结词的命题称为_。27在命题演算中，五个联结词的含义是由其_表唯一确定的。28使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的条件是_不含有y，_不含有x。29设A为任意集合，请填入适当的运算符，使式子A_A=；A_A=成立。30设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则domR=_，ranR=_。31
20、称集合S是给定非空集合A的覆盖：若S=S1，S2，Sn，其中SiA，Si，i=1，2，n，且_；进一步若_，则S是集合A的划分。32对实数的普通加法和乘法，_是加法的幂等元，_是乘法的零元。33若一条路中，所有边均不相同，则此路称作_；若一条路中所有的结点均不相同，则称此路为_。35设A=0，1，2，3，R=x,y|x,yA(y=x+1y=)，S=x,y|x,yA（x=y+2）。试求RSR。36在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_。37、AB的对偶式为_。39(1)画出一个有欧拉回路的图; (2)画出一个有哈密尔顿回路的图; (3)画出一个有欧拉回路和哈密
21、尔顿回路的图.38设A=1，2，B=2，3，则AA=_，AB=_。39设A=1，2，3，4上关系R=,，则R的自反闭包r(R)= _，对称闭包S（R）=_。40命题公式（PQ） P的成真指派为_，成假指派为_。41公式（）（F（x）G(y)）()(H(x)中的自由变元为_，约束变元为_。42设f :RR,f (x)=x2-2,g :RR,g(x)=x-1,那么复合函数=_，=_。46在根树中，若每一个结点的出度_m,则称这棵树为m叉树。如果每一个结点的出度_m或0，则称这棵树为完全m叉树。47是一个群，其中Zn=0,1,2,n-1,xy=(x+y)mod n，则在中，1的阶是_，4的阶是_。4
22、8、对代数系统，其中*是S上的二元运算，若a，bS，且对任意的xS，都有a*x=x*a=x，b*x=x*b=b，则称a为运算“*”的_，称b为运算“*”的_。49一个_且_的无向图称为树。50在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_，如果V有n个结点，那么它还是_度正则图。.公式A(x)B(x)的前束范式为_。51.设论域为集合a,b,c，则(x)P(x)(x)Q(x)_。52.集合A上的关系“”称为偏序关系，如果满足_。53.设A=a,b,c，B=a,b,c,d,则AB=_。54.集合A=a,b,c上的关系R=,的对称闭包为_。55.设A=1,2，A上的二元
23、运算定义为x*y=minx,y，则*的运算表为_。56.设A=2,3,6,12，A上的序关系“”定义为：xy当且仅当x整除y.令B=2,3,6，则B的最小上界是_，B的极小元是_。60.的单位元是_。61.设图G的邻接矩阵为，则从结点v1到v3的长度为2的路径数为_，v2的数_的度数为_。62. 一颗完全二叉树的高为3，则它至少有_片树叶.三、计算题：1集合A=a, b, c, d, e上的二元关系R为R=, , , , , , , , , , , , ,（1）写出R的关系矩阵,关系图；（2）判断R是否是等价关系,求出所有元素的等价类； （3）求出R所对应的划分（4）任意给划分a,c,b,de
24、,求出对应的等价关系。2、求出下图的最小生成树3已知A=，1，B=，1，1，计算AB，AB，A的幂集P（A）。4构造命题公式（PQ）P）R的真值表。5下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，A4及可达矩阵P。6求下列公式的主合取范式和主析取范式：P（ P（Q（ QR）7设A=1，2，3，4，6，8，12，24，R为A上的整除关系，试画的哈斯图，并求A中的最大元、最小元、极大元、极小元。9设A为54的因子构成的集合，R1AA，x,yA, xRyx整除y，R2是定义在A上的小于等于关系。画出偏序集，的哈斯图，并分别求A中关于R1和R2的最大元，最小元，极大元，极小元。
25、12（1）试构造一棵带权为15，28，2， 36，41，45的最优树； （2）求出该树的WPL；（3）再写出权为3的树叶所对前缀码。13.设A=1,2,3，给定A上二元关系R=,，求r(R),s(R)和t(R)。14.求公式的前束范式。15. 符号化下列语句并构造下面推理的证明。前提：如果他喜欢美术，他必去买颜料。如果他不喜欢文学，那么他必定喜欢美术。他没买颜料。结论：他喜欢文学。16：符号化下列语句并构造下面推理的证明。前提：如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或小张去看电影。小王去看电影。结论：当小赵去看电影时，小李也去。17、设X=1，3，4，R是X上的二元关系，R=,。（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明R是否具有自反、反自反、对称、传递性质。18构造下面推理的证明。前提：只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。结论： A犯了谋杀罪。19在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。-