离散数学课试卷B

第1页共2页课程名称：离散数学(B卷闭卷)适用专业年级：通信工程专业05级考试时间:100分钟题号一二三四五六总分统分人签名题分15122038510100得分考生注意事项：1、本试卷共2页，试卷如有缺页或破损，请立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。(答案请写在密封线内和纸卷正面，否则不记分)一、填空题(每空1.5分，共15分)1、（）是用数学方法研究逻辑学中（）的一种分支学科。2、设A为一个命题公式，若A在它的各种赋值下取值均为假，则称A为（）。3、表示抽象的性质、关系的谓词或泛指的谓词称为（）。4、设集合A={3,5,7,4}，集合B={7,3,9,2}，则A⊕B的结果为（）。5、设关系F={1,4,2,7,3,4,2,1}，关系G={4,2,4,6,7,1,2,2}，则GºF的结果为（）。6、设A={a,b,c}，A上的关系R={a,b,b,a,b,c}，则R的自反闭包r(R)=（）,R的对称闭包s(R)=（）。7、设无向完全图G=V,E有10个顶点，则图G共有（）条边。8、在有向图G中，设所有顶点的入度和为m，出度和为n，则m与n应该是（）的。二、单项选择题(每空一选每选2分共12分)1、在下面四项陈述中，可称为命题的是（）。A．天气多好啊！B．x=4。C．南昌起义那天下雪了。D．我只给不给自己理发的人理发。2、若P：他聪明；Q：他用功；则“他虽然聪明，但不用功。”可符号化为（）。A．P∨QB．P∧¬QC．P→¬QD．P∨¬Q3、已知谓词公式为xF(x)→xG(x),则以下哪一项不是该谓词公式的前束范式（）。A．x(¬F(x)∨G(x))B．xy(G(y)→F(x))C．xy(¬F(x)∨G(y))D．yx(F(x)→G(y))4、以下命题为假的是（）。A．空集包含空集B．空集被任一集合包含C．空集是唯一的D．空集属于任一集合5、设Ｓ＝｛１,２,３,４｝，R为S上的关系；其关系矩阵是如下图所示，则RºR中有（）个有序对。A．7B．6C．8D．56、在一个有向简单图中，已知该图有8个顶点，则该图不可能具有的边数为（）。A．1B．55C．34D．57三、判断题：(正确的打√，错误的打╳，每题一分，共20分)()1、“外太空存在生物。”是假命题。()2、在命题变元确定的情况下，按照命题公式的定义可以形成无限的不同的命题公式。()3、在谓词公式中，可以用公式中未出现的变项符号代替某自由出现的个体变项，但必须处处代替。()4、命题公式中的重言式的代换实例在谓词公式中不一定是重言式。()5、在使用量词辖域收缩与扩张等值式时，公式A（x）中可以有x的约束出现。()6、集合A={1,2,5,2,1}，集合B={5,2,1}，则集合A与B是相等的。()7、在一个∣R∣≥2的二元关系R中，有序对之间的顺序是不可交换的。()8、设F[A]为集合A在二元关系F下的像，则F[A]一定不是二元关系。()9、在一个二元关系R中不可能同时具备自反性与反自反性。()10、设R与S为集合A上的对称关系，则R∪S也是集合A上的对称关系。()11、在集合A中任取两个元素x和y，则等价类[x]与[y]的交集可以是[x]的真子集。()12、所有的二元关系都可以称为函数。()13、设集合A={1,2,3,4}，则A上的关系R={1,12,23,32,33,2}具有对称性与传递性。()14、设*为S上的二元运算，如果S上关于运算*存在左幺元el与右幺元er，则el=er。()15、逆元是针对二元运算而言的。()16、在一个有向图G=V,E中，如果所有顶点度的和为180，则该图共有90条有向边。()17、对于一个命题公式A，其析取范式可有多种表达形式，但其主析取范式是唯一的。()18、在一阶逻辑中存在量词分配等值式：x（A(x)∧B(X)）=(xA(x)∧xB(x))。()19、等价类是一个集合。()20、在有向图中，如果某顶点的入度是3，出度是4，则该顶点的度是1。湖南工业大学考试试卷纸系(院)课程名称班级姓名学号密封线四、综合题：(共38分)1、用等值演算法证明等值式（（p→q）∧（p→r））=（p→（q∧r））。（5分）2、求命题公式（p∨（q∧r））→(p∧q∧r)的主析取范式。（8分）3、在一阶逻辑中将命题“任何金属都可以溶解在某种液体中。”符号化。（3分）4、已知集合A={a,b,c,d,e},B={f,e,g,c,d}。试求：A∪B、A∩B、A-B、A⊕B。（8分）5、已知集合A={a，b，c，d}。R，S为集合A上的关系。R={a,a,a,b,b,d},S={a,d,b,c,b,d,c,d}。试求：RºS、SºR、R2、S3。（6分）6、已知集合A={a,b,c,d,e},A上的关系R={a,b,b,c,c,d,d,c,b,e,e,e}。试求:（1）画出R的关系矩阵。（2）R的自反闭包。（3）R的对称闭包。（4）R的传递闭包。（8分）五、推理题：（共5分）1、构造下面推理的证明。（5分）前提：（r→¬q），r∨s，s→¬q，p→q结论：¬p六、证明题（共10分）1、证明：(FºG)-1=G-1ºF-1。（6分）2、证明：任何命题公式的主析取范式如果存在则是唯一的。（4分）湖南工业大学考试试卷纸系(院)课程名称班级姓名学号湖南工业大学考试答卷纸系(院)课程名称班级姓名学号密封线第2页共2页