北京大学现代远程教育2008年秋季学期期末考试试卷A1.T为无向连通图G(m,n)的一棵生成树，则对应T的基本回路数为（m-n+1）[是]2、每条边都是桥的无向连通图必是树。[是]3、非平凡无向树T至少1片树叶[非]4、11阶无向连通图G中有17条边，其任一棵生成树T中必有6条树枝[非]5、无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有8个顶点.[是]6、二元正则树有奇数个顶点。[对]7、n（n≥1）阶有向完全图都是有向欧拉图。[对]8、无向连通图G（m,n）的每一条边都可以成为他的某一生成树的树枝。[x]9、边数m等于n-1的n阶无向图都是树。[x]10、10阶无向连通图G有m条边，则生成树T对应的基本割集数目为9［］11．树Ｔ有ｍ条边，ｎ个顶点，则有ｎ＝ｍ＋１［是］12．（１，２，３，４，５，６）可以是一个图的顶点度数列［非］13．作为有向图中有向边始点的次数叫出度。[是]14．10阶无向简单图G中有6个奇数度顶点，其补图中必有４个奇数度顶点[是]15．10、11阶无向简单连通图G中，顶点间的最大距离是11[x]11、11条边的图G中，所有顶点的度数之和为22[]12、11阶无向简单图G中有6个奇数度顶点，其补图中必有5个奇数度顶点[x]13、图Ｇ中２个３度顶点，３个４度顶点，４个５度顶点，则Ｇ中有１８条边．[]14、10阶无向连通图G有m条边，则生成树T对应的基本割集数目为9。［］15.边数m等于n-1的n阶无向图都是树。[X]16.无向树的任何边都是桥。[]17.无向连通图G（n，m）的每一棵生成树都有n-1条树枝。[]18、无向连通图G（n，m）的每一条边都可以成为他的某一生成树的树枝。[X]19、一棵树中有i个顶点的度数为i（i=2，…k），其余顶点都是树叶。当k=4时，问树叶多少片？（10分）三、填空题.(每题2分，共16分）1、个体域是人类，则命题”人固有一死”应符号化为(xF（x）)。2、命题应为能判断对错的(陈述)句。3、令p：天下雨；q：乘汽车。命题’’如果天下雨，则乘汽车’’符号化为(ｐ→ｑ)4、任一个命题公式至少(1)个主析取范式.5、命题”明天不下雨，也没有太阳，将是阴天。”应符号化为(┐p∧┐q∧r).6、命题公式p的主合取范式为(∏(0))7、命题公式p∧┐q∧r的主析取范式为(∑(5))8、个体域为自然数集合,则x+y=y+x(是)命题。１３．令F（x）：x是兔子；G（y）：y是乌龟；H（x，y）：x比y跑得快。将命题“所有兔子不比某些乌龟跑得快”符号化为：（x（F（x）→﹃彐y（G（y）∧H（x，y））））14、设个体域是自然数集合，p代表xy彐zF（x－y=z），则p(是假)命题。15、令p代表一阶逻辑公式G（x）与G（y）等值，则p（是假）命题。1６．命题公式（﹁ｐ∧ｐ）→ｑ的类型是（永真式）．17．任何图中，度数为奇数的顶点个数为（偶数）18．在命题逻辑中，任何命题公式都(有唯一的一个)主合取范式.19．设域为正整数集合，命题x彐y（x＞y）的真值为（０）20令p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p21.p：天气好；q：我们去游玩．将命题＂除非天气好，否则我们不去游玩＂符号化为［Ｂ］A．p→q；B．q→p；C．p∧q；D．﹁q→﹁p22.命题公式ｐ→(ｐ∧ｑ)为假的赋值是ｐ,ｑ分别为（（１，０））23、明天不下雨，也没有太阳，将是阴天。┐p∧┐q∧r。24、人固有一死。x（F（x）→G（x））。25、有的汽车不见得比所有的火车跑得慢。﹁L（x,y）））。26、x+3y=3y+x。符号化为：P或。27、即使张三和李四考分相等，也只有一人被我校录取。P∧（（q∧┐r）∨（┐q∧r））。28.任何命题公式都有唯一的主析取范式和唯一的主合取范式[是]29.任何命题公式都有唯一的与其等值的析取范式和唯一的与其等值的合取范式[非]30.任何命题公式都有唯一的与其等值的析取范式和唯一的与其等值的合取范式[非]31.任何命题公式都有唯一的与其等值的析取范式[非]32.任何命题公式都有唯一的与其等值的合取范式[非]33.公式A有n个命题变元,其主析取范式中有k个极小项,m个极大项,则m+k=2n[是]34.有n个命题变元的永真式,其主析取范式中有k=2n极小项,则极大项数m=0[是]35.有n个命题变元的永假式,其主析取范式中有k=0个极小项,则极大项数m=2n[是]36.有n个命题变元的可满足式,其主析取...
