离散测试卷

第1页共8页一、判断题(每小题1分，共15分)1、若图G是自对偶的，则e=2v-2（）2、“离散数学是很有趣的一门课程”，这句话是命题。（）3、函数的复合既能交换也能结合。（）4、如果A∨CB∨C，则AB（）5、设G=V,E为连通图，且eE,则当e是G的割边时，e才在G的每棵生成树中。（）6、)()(RQPQ是合式公式。（）7、任何阶数为4的群都是阿贝尔群。（）8、设G是简单连通图，且有v个结点，e条边，若G是平面图，则e3v-6。（）9、一个循环群的生成元是唯一的。（）10、有任意集合A、B，则f(A∩B)f(A)∩f(B)且f(A)∩f(B)f(A∩B)。（）11、)()()()())()()((xBxxAxxBxAx（）12、对任意集合A，B，C，如果A∈B以及BC，则AC。（）13、整数集上的同余类是对整数集的一个划分。（）14、有限半群中存在等幂元。（）15、设A,*是一个代数系统，且|A|1，若该代数系统中存在幺元和零元，则幺元与零元相等。（）二、选择题(每小题2分，共22分)1、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，则该树有（）片树叶。A.6B.7C.8D.92、图1中v1到v4长度为2的路有（）条A.1B.2C.3D.4v2v4v3v1v2v4v3v1图13、设A={1，2，3，4}，B={a，b，c，d}，f定义为：{1,a,2,b,3,c,4,d}，则f（）。A.不是函数B.仅为入射函数C.仅为满射函数D.是双射函数4、设F(x)：x是乌鸦；G(x,y)：x与y一般黑，则“天下乌鸦一般黑”可以符号化为：()A.)),()()()()((yxGyFxFyxB.)),()()()()((yxGyFxFyx第2页共8页C.)),()()()()((yxGyFxFyxD.)),()()()()((yxGyFxFyx5、给定下列谓词公式，则是矛盾式的公式为（）A.))()()((xPxPxB.)()()()(xPxxPxC.)()())()(()()((yQyyQyxPxD.),())((),())((yxPyxyxPyx6、设有下列四个集合，偏序关系为整除，则是全序关系的为（）A.{3,5,15}B.{1,2,3,6,12}C.{3,4,12}D.{3,9,27,54}7、设集合P={x1，x2，x3，x4，x5}上的偏序关系如图2所示，则下列说法中正确的是（）A、P的最大元素为x1，无最小元素，极小元素为x4，x5，极大元为素x1B、P无最大元素，也无最小元素，极小元素为x4，x5，极大元为素x1C、P的最大元素为x1，无最小元素，也无极小元素，极大元为素x1D、P的最大元素为x1，最小元素为x4，x5，极小元素为x4，x5，极大元为素x1x1x4x5x3x2图28、集合A={a，b，c}，A上的关系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c）}，则R具有关系的（）性质。A、自反性B、对称性C、反对称性D、传递性9、下面给出的一阶逻辑等价式中，（）是错的。)).(()(.));(()(.);()())()((.);()())()((.xBAxxxBADxAxxxACxxBxxAxBxAxBxxBxxAxBxAxA10、一个公式在等价意义下，下面哪个写法是唯一的（）。第3页共8页A．析取范式B．合取范式C．主析取范式D．以上答案都不对11、已知图G的相邻矩阵为A(G)则G有（）。A.5点，8边B.6点，7边C.5点，7边D.6点，8边A(G)=三、填空题(每空2分，共30分)1、n为时，无向完全图Kn是欧拉图。n为时，无向完全图Kn仅存在欧拉通路而不存在欧拉回路。2、如图2，则k(G)=λ(G)=δ(G)=图23、假设X和Y是有穷集合，则从X到Y存在入射的必要条件是4、设P表示命题“8是偶数”，Q表示命题“糖果是甜的”，则命题P→Q的反换式所表示的含义是5、（P∨Q）∧R的对偶式为6、设P(x)表示x是聪明的，M(x)表示x是人，则命题“尽管有人聪明，但未必一切人都聪明”可以符号化为：7、集合{a,{a}}的幂集为：8、令R={1,2,3,4,2,2}和S={4,2,2,5,3,1,1,3}，则SR9、设A={a,b,c}，R是A上的二元关系，且给定R={a,b,b,c,c,a}，则r(R)=10、设I是整数集合，R是同余模3的关系，则I/R=11、设谓词的定义域为},,{cba，将表达式))()((xQxPx中的量词消除，写成与之等价的命题公式是12、设P(x)：x是素数；E(x)：x是偶数；O(x)：x是奇数；N(x，y)：x可以整除y。则))),()()(()()((xyNyOyxPx可以译成自然语言为：四、证明题(第1，2题各5分，第3题8分，共18分)1、证明：若X×Y=X×Z，且X不为空集，则Y=Z。第4页共8页2、如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。符号化该命题，并用推理理论证明之。3、设A,*是半群，e是左幺元且对每一个x∈A，存在x’∈A，使得x’*x=e。a)证明：对于任意的a,b,c∈A，如果a*b=a*c，则b=c。b)通过证明e是A中的幺元，证明A,*是群。五、应用题(第1题5分，第2题10分，共15分)1、双射函数是密码学中的重要工具，因为在密码体制中大都会同时涉及加密和解密，假设f是由表1定义的，即f(A)=D,f(B)=E,F(C)=S,…等，试找出给定密文“ARDJYLRXBMB”对应的明文。表1ABCDEFGHIJKLMDESTINYABCFGH续表1NOPQRSTUVWXYZJKLMOPQRUVWXZ2、设有a,b,c,d,e,f,g七个人，他们分别会讲如下各种语言：a会讲英语；b会讲汉语与英语；c会讲英语、西班牙语和俄语；d会讲日语和汉语；e会讲德语和西班牙语；f会讲法语、日语和俄语；g会讲法语和德语。能否将这七个人的座位安排在圆桌旁，使得每个人均能与他身边的人交谈？第5页共8页一、计算题(每小题8分，共24分)1、实数集合R上定义运算：x*y=xy-2x-2y+6。完成下列小题：（1）求*运算的幺元和零元；（2’）（2）对任何实数x求其逆元。(2’)（3）证明*满足交换性和结合性(4’)2、设集合}24,12,8,6,3,2,1{A上的整除关系R，画出哈斯图(4’)，并求A的极大元,极小元,最大元,最小元(4’)。3、设R，S是A={1,2,3,4}上的等价关系，其关系矩阵分别为1100110000100001RM，1000011001100001SM。求包含R与S的最小等价关系。二、选择题(每小题1.5分，共15分)1、下面语句是真命题的为（）。A、我正在说谎。B、如果1＋1＝2，则太阳从东边升起来。C、如果1＋1＝2，则太阳从西边升起来。D、吃饭了吗？2、一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，则该树有（）片树叶。A、6B、7C、8D、93、关于阿贝尔群，下列说法不正确的是（）。A、任何阶为4的群都是阿贝尔群。B、群中每个元素都是自身为逆元，则该群是阿贝尔群。C、任何循环群必定是阿贝尔群。D、任何阶为6的群都是阿贝尔群。4、设6{0,1,,5}N，6为模6加法，则下列元素是66,N的生成元的是（）A、1B、2C、3D、45、图1中从v1到v3长度为3的通路有（）条。图1第6页共8页A、0B、1C、2D、36、下列函数是双射的为（）A、f:IE,f(x)=2xB、f:NNN,f(n)=n,n+1C、f:RI,f(x)=[x]D、f:IN,f(x)=|x|（注：I—整数集，E—偶数集，N—自然数集，R—实数集）7、下图中既不是Eular图，也不是Hamilton图的图是（）8、设A={1，2，3，4}，则A上的二元关系有（）个。A、24B、42C、24X4D、42X29、下面给出的一阶逻辑等价式中，（）是错的。)).(()(.));(()(.);()())()((.);()())()((.xBAxxxBADxAxxxACxxBxxAxBxAxBxxBxxAxBxAxA10、设S={a,b,c}，在S上的一个二元运算△定义如表1所示。则下列说法正确的是（）。表1△abcabcabcabcabcA、△运算封闭，等幂，可交换B、△运算封闭，不等幂，不可交换C、△运算不封闭，等幂，可交换D、△运算封闭，等幂，可结合三、填空题(每空2分，共20分)1、无向图G如右图所示，则图G的阅卷人得分adcbee2e1e3e4e5第7页共8页割点为_______________。2、（P∨Q）∧R的对偶式为。3、一个具有n个结点的简单连通无向图的边数至少为条。4、给定集合S={a,b,c,d,e}，在S上的一个划分{{a,b}，{c}，{d,e}}所对应的等价关系为。5、设解释I如下，个体域D={1,2}，F(1,1)=F(2,2)=0，F(1,2)=F(2,1)=1，在解释I下，∃xF(x,2)的真值为。6、设D：全总个体域，F(x)：x是花，M(x)：x是人，H(x,y)：x喜欢y，则命题“每个人都喜欢某种花”的逻辑符号化为__。7、令R={1,2,3,4,2,2}和S={4,2,2,5,3,1,1,3}，则SR。8、设谓词的定义域为},,{cba，将表达式))()((xQxPx中的量词消除，写成与之等价的命题公式是。9、合式公式))),()()(()()((xyNyOyxPx的前束范式为：。10、一组学生，用二二扳腕子比赛法来测定臂力的大小，则零元是。四、证明题(10分)1、设G，*是群，对任一a∈G，令},|{GyyaayyH，试证明H,*是G,*的子群。五、改错题(6分)1、给定推理①))()((xGxFxP②)()(yGyFUS①③)(xxFP④)(yFES③⑤)(yGT②④I⑥)(xxGUG⑤)()()()())()()((xGxxFxxGxFx指出以上出错的步骤，并在旁边改正。第8页共8页六、应用题(第1题5分，第2，3题10分，共25分)1、如下图所示的赋权图表示某七个城市721,,,vvv及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。2、公安人员审查一件盗窃案。已知的事实如下：（1）甲或乙盗窃了名画；（2）若是甲盗窃了名画，则作案时间不可能在午夜前；（3）若乙的证词正确，则午夜时屋里灯光未灭；（4）若乙的证词不正确，则作案时间在午夜前；（5）午夜时屋里灯光灭了。将各命题符号化，推断是谁盗窃了名画，并用形式方法证明推理的有效性。3、某年级共有9门选修课程，期末考试前必须提前将这9门课程考完，每人每天只在下午考一门课，若以课程表示结点，有一人同时选两门课程，则这两点间有边（其图如下），问至少需几天？