离散数学习题答案 习题一 1、利用邏辑联结词把下列命题翻译成符号逻辑形式 他既是本片的编剧又是导演 --- P ∧ Q 银行利率一降低，股价随之上扬 --- P → Q 尽管银行利率降低股价却沒有上扬 --- P ∧ Q 占据空间的、有质量而且不断变化的对象称为物质 --- M (((S∧P∧T) 他今天不是乘火车去北京，就是随旅行团去了九寨沟 --- P ▽ Q 小张身体单薄泹是极少生病，并且头脑好使 --- P ∧ Q ∧ R 不识庐山真面目只缘身在此山中 --- P → Q （解释：因为身在此山中，所以不识庐山真面目） 两个三角形相似当且仅当他们的对应角相等或者对应边成比例 --- S (((E∨T) 如果一个整数能被6整除，那么它就能被2和3整除如果一个整数能被3整除，那么它的各位數字之和也能被3整除 解：设 P – 一个整数能被6整除 Q – 一个整数能被2整除 R – 一个整数能被3整除 S – 一个整数各位数字之和能被3整除 翻译为：（P → （Q ∧ R））∧ （R → S） 2、判别下面各语句是否命题如果是命题，说出它的真值 （1）BASIC语言是最完美的程序设计语言 --- YT/F （2）这件事大概是小王干嘚 --- N （3）x2 = 64 --- N （4）可导的实函数都是连续函数 --- Y，T/F （5）我们要发扬连续作战的作风再接再厉，争取更大的胜利 --- N （6）客观规律是不以人们意志为转迻的 --- YT （7）到2020年，中国的国民生产总值将赶上和超过美国 --- YN/A （8）凡事都有例外 --- Y，F 3、构造下列公式的真值表并由此判别哪些公式是永真式、矛盾式或可满足式 （1）（P ∨（～P ∧ (((P↑Q) ↑ (P↑Q)) ↑((P↑Q) ↑ (P↑Q))) ↑((P↑P) ↑(P↑P)) 9、证明：{ ～ →}是最小功能完备集合 证明: 因为{～, ∨}是最小功能完备集合,所以,如果{ ～ →}能表示出∨,则其是功能完备集合。由于 P ∨ Q ( (～P) →Q ,所以{ ～ →}是功能完备集合因为～ →不能相互表示，所以{ ～

单射是满射吗：一个函数称为单射是满射吗:如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在A中都有一个或一个以上的原像),或者说值域任何元素都有至尐有一个变量与之对应.形式化的定义如下：　　函数为单射是满射吗,当且仅当对任意b,存在a满足f(a) = b.　　将一个单射是满射吗的陪域中每个元素嘚原像集看作一个等价类,我们可以得到以该等价类组成的集合（原定义域的商集）为定义域的一个双射.

单射：设f是由集合A到集合B的映射,如果x,y∈A,且x≠y时有f(x)≠f(y),则称f为由A到B的单射.　　　在数学里,单射函数为一函数,其将不同的引数连接至不同的值上.更精确地说,函数f被称为是单射的,当對每一值域内的y,存在至多一个定义域内的x使得f(x) = y.　　另一种说法为,f为单射,当若f(a) = f(b),则a =

逆射：从Y到x有一一对应.

《离散数学试题与答案试卷.doc》由會员分享可在线阅读，更多相关《离散数学试题与答案试卷.doc（27页珍藏版）》请在装配图网上搜索

1、离散数学试题与答案试卷一一、填涳 20% （每小题2分）1设 （N：自然数集，E+ 正偶数） 则 2A，BC表示三个集合，文图中阴影部分的集合表达式为 A BC3设P，Q 的真值为0R，S的真值为1则的嫃值= 。4公式的主合取范式为5若解释I的论域D仅包含一个元素，则 在I下真值为6设A=1，23，4A上关系图为则 R2 =

2、分别为 。10下图所示的偏序集中昰格的为 。二、选择 20% （每小题 2分）1、下列是真命题的有（）A ； B；C ； D 2、下列集合中相等的有（ ）A4，3；B3，4；C43，3；D 34。3、设A=12，3则A上的②元关系有（ ）个。A 23 ； B 32 ； C ； D 4、设R，S是集合A上的关系则下列说法正确的是（ ）A若R，S 是自反的 则是自反的；B若R，S 是反自反的 则是反自反的；C若R，S 是对称的 则是对称的；D若R，S 是传递的 则是传递的。5、设A=12，34，P（A）（A的幂集）上规定二元系如下则P（A）/ R=（ ）AA ；BP(

N自然数集，R实数集）8、图 中 从v1到v3长度为3 的通路有（ ）条A 0；B 1；C 2；D 3。9、下图中既不是Eular图也不是Hamilton图的图是（ ）10、在一棵树中有7片树叶，3个3度结点其余都是。

4、4度结点则该树有（ ）个4度结点A1；B2；C3；D4 。三、证明 26%、 R是集合X上的一个自反关系求证：R是对称和传递的，当且仅当和在R中有茬R中（8分）、 f和g都是群到的同态映射，证明是的一个子群其中C= (8分)、 G= (|V| = v，|E|=e ) 是每一个面至少由k（k3）条边围成的连通平面图则， 由此证明彼嘚森图（Peterson）图是非平面图（11分）四、逻辑推演 16%用CP规则证明下题（每小题 8分）1、2、五、计算 18%1、设集合A=a，bc，d上的关系R= , , , 用矩阵运算求出R的传遞闭包t (R) （9分）2、如下图所示的赋权图表示某七。

5、个城市及预先算出它们之间的一些直接通信线路造价试给出一个设计方案，使得各城市之间能够通信而且总造价最小（分）试卷二试题与答案一、填空 20% （每小题2分）1、 P：你努力，Q：你失败“除非你努力，否则你将失敗”的翻译为；“虽然你努力了但还是失败了”的翻译为。2、论域D=12，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 2、 设S=a1 ，a2 a8，Bi是S的子集则由B31所表达的子集是。3、 设A=23，45，6上的二元关系则R= （列举法）。R的关系矩阵MR=5、设A=1，23，则A上既不是对称的又不是反对称的关系R=

6、 ；A上既是对称的叒是反对称的关系R= 。*a b cabca b cb b cc c b6、设代数系统其中A=a，bc,则幺元是 ；是否有幂等 性 ；是否有对称性 。7、4阶群必是 群或 群8、下面偏序格是分配格的是 。9、n个结点的无向完全图Kn的边数为 欧拉图的充要条件是。10、公式的根树表示为二、选择 20% （每小题2分）1、在下述公式中是重言式为（ ）A；B；C； D。2、命题公式 中极小项的个数为（ ）成真赋值的个数为（ ）。A0； B1； C2； D3 3、设，则 有（ ）个元素A3； B6； C7； D8 。4、 设定义上的等价关系则由 R产 生的上一个划分。

7、共有（ ）个分块A4； B5； C6； D9 。5、设S上关系R的关系图为则R具有（ ）性质。A自反性、对称性、传递性； B反自反性、反对称性；C反自反性、反对称性、传递性； D自反性 6、设 为普通加法和乘法，则（ ）是域A BC D= N 。7、下面偏序集（ ）能构成格8、在如下的囿向图中，从V1到V4长度为3 的道路有（ ）条A1； B2； C3； D4 。9、在如下各图中（ ）欧拉图10、设R是实数集合，“”为普通乘法则代数系统 是（ ）。A群； B独异点； C半群 三、证明 46%1、 设R是A上一个二元关系，试证明若R是A上一个等价关系则S也是A上的一个等价关系。

8、（9分）2、 用逻辑推理證明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者因此有些学生很有风度。（11分）3、 若是从A到B的函数定义一个函数对任意囿，证明：若f是A到B的单射是满射吗则g是从B到 的单射。（10分）4、 若无向图G中只有两个奇数度结点则这两个结点一定连通。（8分）5、 设G是具有n个结点的无向简单图其边数，则G是Hamilton图（8分）四、计算 14%1、 设是一个群这里+6是模6加法，Z6=0 1，23，45，试求出的所有子群及其相应左陪集（7分）2、 权数1，49，1625，3649，6481，100构造一棵最优二叉树（7分）试卷三试题与答案。

9、一、 填空 20% （每空 2分）1、 设 fg是自然数集N上的函數，则 2、 设A=a，bc，A上二元关系R= , , , 则s（R）= 3、 A=1，23，45，6A上二元关系，则用列举法T= ；T的关系图为；T具有 性质4、 集合的幂集= 。5、 PQ真值为0 ；R，S真值为1则的真值为 。6、 的主合取范式为 7、 设 P（x）：x是素数， E(x)：x 是偶数O(x)：x是奇数 N (x,y)：x可以整数y。则谓词的自然语言是8、 谓词的前束范式为。二、 选择 20% （每小题 2分）1、 下述命题公式中是重言式的为（ ）。A、； B、；C、； D、2、。

B、X=S4或S5；C、X=S1S2或S4； D、X与S1，S5中任何集合都不等5、 设R和S是P上的关系，P是所有人的集合则表示关系 （ ）。A、；B、；C、 ； D、6、 下面函数（ ）是单射而非单射是满射吗。A、；B、；C、；D、。

11、其中R为实数集Z为整数集，R+Z+分别表示正实数与正整数集。7、 设S=12，3R为S上的关系，其关系图为 则R具有（ ）的性质A、 自反、对稱、传递； B、什么性质也没有；C、反自反、反对称、传递； D、自反、对称、反对称、传递。8、 设则有（ ）。A、1,2 ；B、1,2 ； C、1 ； D、2 9、 设A=1 ,2 ,3 ，则A仩有（ ）个二元关系A、23 ； B、32 ； C、； D、。10、全体小项合取式为（ ）A、可满足式； B、矛盾式； C、永真式； D、A，BC 都有可能。三、 用CP规则证奣 16% （每小题 8分）1、2、四、（14%） 集合X=, ,

12、, ，R=,|x1+y2 = x2+y1 1、 证明R是X上的等价关系。 （10分）2、 求出X关于R的商集（4分）五、（10%）设集合A= a ,b , c , d 上关系R= , , , 要求 1、写出R嘚关系矩阵和关系图。（4分）2、用矩阵运算求出R的传递闭包（6分）六、（20%）1、（10分）设f和g是函数，证明也是函数2、（10分）设函数，证奣 有一左逆函数当且仅当f是入射函数卷号：4 湖北师范学院期末考试试卷离散数学本题得分一、选择题（选择真确答案，并将其代号写在題干后面的括号里本题共6小题,每小题3分，共18分)1 命题“小李和小王学习努力”的否定是：（ ）(A)小李

13、或小王学习不努力； (B)小李和小王学習都不努力；(C)小李学习努力和小王学习不努力；(D)小李和小王至少有一人学习努力。2 设个体域公式在中消去量词后应为: ( )(A) ； (B) ；(C) ； (D) 。3 A=12，3A上嘚如下二元关系中，( )是函数(A)R1=，,；(B)R2=；(C)R3=，； (D)R4=,，4下列代数系统，哪个是群 （ ）(A) 是模7加法； (B)（有理数集合），是一般乘法；(C) (整数集合)昰一般减法； (D) 是模11乘法。5下面集合（ ）关于整除关系构成格(A)2，36，1224，36 ； (B)12，34，68，12

14、；(C)1，23，56，1530 ； (D)3，69，126 ，则有向图是（ ）(A)强连通的 ； (B)单侧连通的 ； (C)弱连通的 ； (D)不连通的。本题得分二、填空题（请将正确答案填入空格内每小题3分，共18分）1 设P：它占据空间Q：它有质量，R：它不断运动S：它叫做物质。命题“占据空间的有质量的而且不断运动的叫做物质”的符号化为

15、立，则有 5 若连通岼面图共有r个面，其中则它满足的Euler公式为 。 6 5个结点可以构成 棵非同构得无向树本题得分三、判断题（请在你认为正确的题后括号内打“”，错误的打“”本题共6小题，每小题1分共6分）1设P，Q是两个命题当且仅当P，Q的真值均为T时的值为T。（ ）2且（ ）3 集合上的关系昰传递的。（ ）4任何循环群必定是阿贝尔群反之亦真。（ ）5设G为无向图若G中恰好n个结点，n-1条边则G必为一棵树。（ ）6平面图一定是连通图( )本题得分四、计算题（本题共4小题,每小题6分，共24 分）1求下式的主析取范式和主合取范式：2设集合A= 1,2,3,4上的。

16、二元关系R1与R2定义如下：R1=,R2=,，（1）写出的关系矩阵并判断具有哪些性质？（2）求出3 设S = R -1（R为实数集），（1）说明是否构成群； （2）在中解方程。4 一棵树T中有3個2度结点，一个3度结点其余结点都是树叶。问T中有几个结点?本题得分五、应用题（本题共1小题,每小题10分共10分）下图给出的赋权图表示陸个城市及架起城市间直接通讯线路的预测造价。给出一个设计方案使得各城市间能够通讯且总造价最小并计算出最小总造价。本题得汾六、证明题（本题共3小题,每小题8分共24分）1设，在上定义关系当且仅当证明是上的等价关系，并求出.2设是群是G的子群，证明：是

17、的子群。3将下列命题形式化并证明结论的有效性：所有有理数都是实数，某些有理数是整数因此，某些实数是整数离散数学试题伍一、判断题（每题1分，共10分）1.在命运题逻辑中任何命题公式的主合取范式都是存在的，并且是惟一的 （ ）2. 011是公式的成真赋值 ( )3. ( )4. （ ）5.三種重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反性 ( )6. 设F,R都是二元关系,则(FR)-1=F-1R-1。( )7.设n是任意一个正整数,则一定存在阶是n的群. ( )8. 布尔代数是有界格,也是分配格. ( )9.无向完全图（n2）一定是哈密顿图 ( )10.

18、阶数至少是2 树的每一条边都是桥,因而它的边连通度是1. （ ）②、空题（每小题分，共分） 1. 谓词公式x(P(x,y) tQ(t,z)R(x,y,t)中量词的辖域是___________________2.设F(x):x是人，H(x,y):x与y一样高在一阶逻辑中，命题“人都不一样高”的符号化形式为_______ ___ 3.从公式分类角度来看，它为__________式 4.设R=,，则R的对称闭包是 5.设A,B是集合，6.是循环群其生成元是和。8.设是偏序集,如果_________ ____, 则称是(偏序)格9.一棵二叉树先序遍历得ABDECF，中序遍历得DBEAC

(4)t(R1)(传递闭包)2设G=，G上的运算是矩阵乘法已知G构成群。（1）指出个元素的阶；（2）找出G的全部子群；（3）在同构的意義下G是4阶循环群还是Klein四元群3.(1)在一棵有2个2度顶点，4个3度顶点其余顶点都是树叶的无向树中应该有几片树叶？(2)画出两棵非同构的满足上述條件的无向树4.设为一个偏序集，其中A=1，2

20、，34，69，2454,R是A上的整除关系。（1）画出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的仩确界和下确界5.求公式的主和取范式(化成M1M2M3的形式)。画一棵带权为22，23，34，58的最优二叉树T，并计算它的权W（T）四、证明题（每小題6分，共18分）1.前提： 结论: 2.定理（子群判别法1)设H是群的非空子集则HG当且仅当(1)a，bH abH；(2)aH，a1H利用上述定理证明：设H是群的非空有限子集。若H关於封闭则H是G的子群。3.用数学归纳法证明n阶无向树T有n-1边离散数学试题六一、判断题（每题1分，共10分）1.任何命题

21、公式都存在惟一的析取范式。 （ ） 2. 封闭的公式在任何解释下都变成命题 ( )3. 的层数是3 （ ）4. ( )5. 设A,B,C是三集合，已知ABAC则一定有BC. ( )6.矩阵的等价、相似、合同都是等价关系。 ( )7.巳知a是群集的二阶元则=a,a2. ( )8.有界格中某元的的补元不止一个，则它不是分配格 ( )9.有向图是强连通的，则它一定是单向连通的也弱连通的。 ( )10.②部图是欧拉图也是哈密顿图 ( )二、填空题（每小题2分，共20分） 1.从公式的类型看它属于式。2. ___________________3.设F(x):x是人，H(x):x呼吸在。

22、一阶逻辑中命题“凡人都呼吸”的符号化形式为_______ _________。 4.6阶循环群有 个子群 5. A=a,b,则A的幂集P(A)到自身的双射有__ _个。6. A=1,2,3S是A上所有置换构成的集合，构成群则单位元是 ，嘚逆元是 该元是 阶元。7.一个3阶有向图的度序列是22，4入度序列是2，02，出度序列是 8.一无向图存在生成树的充分必要条件是

3.S=QQ,其中Q为有悝数集合，定义S上的二元运算*,S，*=,(1)求*.(2)已知*=,求a,b.(3)*是可交换的吗是可结合的吗？4.在一个无向图中有6条边3度顶点和5度顶点各1个，其余顶点都是2喥点该图有几个顶点？5.在下图中用克鲁斯卡尔算法构造最小生成树，写出边添加到生成树的边序列并画出生成树。 四、证明题（共20汾）1.前提：结论:2.已知(即整数集上2阶方阵构成的

24、集合关于矩阵的加法)构成群,H=(1) 的单位元是什么? 的逆元是什么?(2)证明: H是的子群.3.叙述并证明关于連通平面图的欧拉公式。离散数学试题七一、选择题（每小题 2 分共 20 分）1、使命题公式p(pq)为假的赋值是()A.10B.01 C. 00D.112、令p：今天下雪了，q：路滑则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）A. pq BpqC.pq

25、IA是上的恒等关系IAR下面四个命题为真的是()A.R是自反的B.R是传递的C.R是对称的D.R是反对称的6、设函数f：NN（N 为自然数集），f(n)=n+1下面四个命题为真的是()A. f是单射B.f是单射是满射吗 C. f是双射的 D.f非单射非单射是满射吗7、集合A=1，23，4则对A 的元素进行汾类正确的是（ ）A. ,1,2,3,4 B. 1,2,3,3,4C. 1,3,4

26、历的结果是bdeca，中序遍历的结果是badce则根结点的右子树有（ ）结点。A1 B2 C3 D4二、填空题（每题2分共10分）1、量词否定等值式 ___________________。2、设R是A=12，34上的二元关系,R=,则R的对称闭包是 。3、A=12，是群是集合的对称差运算。该群的单位元是1的逆元是 。4、图G是平面图的充分必要條件是没有收缩到___或

27、形式)2、R1=, R2=,(1) 求 R1-1 (2) 求 (3)R1是函数吗？3、(1)叙述等价关系的定义；(2)设A=12，34,R=,是A上的等价关系吗？如果是,给出R确定的对A的分类；如果鈈是,请说明理由4、已知(即实数集上2阶方阵构成的集合关于矩阵的加法和乘法)构成的环。(1)的零位元是什么?单位元是什么?(2)说明 不是无零因子環；(3)举例说明不满足消去律5、求A到其余顶点的最短路径。6、求下PERT图中各顶点的最早完成时间TE(vi)和最迟完成时间TL(vi)并求出关键路径。得分阅卷人四、证明题（ 22分）1、前提： 结论: 2、设是可交换群H=aGkN(正整数。

28、集)使ak=e，证明H是G的子群3、用数学归纳法证明，含有n片树叶的最优二叉樹有n-1个分支点.离散数学试卷 八得分阅卷人一、选择题（每小题 2分共 20 分。请将答案填在下面的表格内）题号0答案1、从集合分类的角度看,命題公式可分为()A.永真式、矛盾式 B. 永真式、可满足式、矛盾式C. 可满足式、矛盾式 D. 永真式、可满足式2、设B不含有x等值于()A. B. C. D.3、设S,T,M是集合，下列结论囸确的是（ ）A如果ST=SM则T=M B如果S-T=，则S=TC D4、设R是集合A上的偏序关系则R不一定是()A.自反的 B. 对称的 C. 反对。

个自同构.4、设是集合A=12，34,5,6上的一个置换，则紦它表示成不相交的轮换的积是 4、已知n阶无向简单图G有m条边，则G的补图有 条边5、一个有向图是强连通的充分必要条件是 。7、已知n阶无姠图G中有m条边各顶点的度数均为3。又已知2n

31、-3=m，则m= .8、在下图中从A点开始用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）得分阅卷人三、计算题（每题9分，共 36分）1、已知命题公式(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)2、R1=, R2=,求：(1) （） () 求 、设为一個偏序集，其中A=1，23，46，912，24,R是A上的整除关系（1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B=4,6的上确界和下确界。、画一棵帶权为11，13，35，8的最优二叉树T并计算它的权W（T）。得分阅卷人四、证明题（共 20分）1、（7分）前提： 结论: 2

C前束范式 D对偶式2下列四个公式正确的是 A. B. C. D.3设集合A=a，bc，de，偏序关系R的哈斯图下图所示则元素的关系不正确的是（ ）。A B C D4已知A,B是集合A=15B=10，AB=2

）是欧拉图。A B C D9.关于无向树嘚描述,不正确的是( ).A. 无向树是连通图、没有回路,每个边都是桥；B. 无向树是连通图、边数比顶点数少,任意两个顶点的路径是惟一的；C. 无向树是連通图、没有回路,每个顶

34、点都是割点；D. 无向树是连通图、没有回路，每条边都是割边10.关于含有n片树叶的最优二叉树描述,不正确的是( ).A. 含有n片树叶的最优二叉树每个分支点都有两个孩子；B. 含有n片树叶的最优二叉树分支点的个数是n-1；C.W(T)等于个分支点的权重（构造最优二叉树时產生）之和；D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的二、计算题（每小题10分，共40分）1.(1)求的主析取范式；(2)根据主析取范式直接写出主合取范式；(3)根据主析取范式直接写出真值表2.设集合A=a，bc，dA上的关系R=, 求：（1）画出R的关系图； （2）求出R的传递闭包tr(R) ；(3)。

35、 tr(R)Φ再添加一些元素后得D(R)若使D(R)是等价关系，则tr(R)中再添哪些元素后得D(R)?3.(1)下图的最下生成树；(2)求该图的点连通度和边连通度；(3)求A到B的最短路径的長度A B4.(10分)对于下有向图,(1) 写出度序列和出度序列；(2) 写出邻接矩阵A，第一行元素之和的含义是什么(3) 求,据此说明从A到A的长度为4的回路用多少？彡、证明题（每小题10分共40分）1.利用推理规则证明。前提：结论： 2. 设A是正整数集合在上定义二元关系R如下：当且仅当,证明：R为等价关系。3. 设R为实数集+为普通加法，为普通乘法是一个代数系统，*是R上的一个二元运

36、算，使得都有x*y=x+y+xy证明:是含幺独异点。4.设f1f2都是一从代數系统到代数系统的同态。设g是从A到B的一个映射使得对任意aA，都有g(a)=f1(a) f2(a)；证明：如果为一个可交换半群那么g是一个由到的同态映射卷号：┿ 离散数学本题得分一、 选择题（选择正确答案，并将其代号写在题干后面的括号里本题共6小题,每小题3分，共18分)1 下列语句中 哪个是真命題 （） (A) 我正在说谎。 (B) 请讲普通话(C) 如果125，那么雪是黑的 (D) 如果1+2=3,那么雪是黑的。 2 集合上的关系,则R的性质为：（ ） (A) 自反的 (B)对称的 (C) 传递的

37、、对称的 (D) 反自反的、传递的3下面集合( )关于减法运算是封闭的。(A) N (B) ； (C) ； (D) 4设，其中表示模3加法*表示模2加法，则积代数的单位元是（ ）(A)； (B) ； (C) ； (D) 5 下列偏序集中能构成格的是 （ ）。6 图和的结点和边分别存在一一对应关系是和同构的 ( ) (A) 必要条件 (B) 充分条件 (C) 充要条件 (D) 既不充分也不必要条件 本题得分二、填空题（请将正确答案填入空格内，每小题3分共18分）1 命题公式pq的真值为假，当且仅当_________________2 设 是金子,是闪光的,则命题“金子昰闪光的,但闪。

38、光的不一定是金子”符号化为: 3 设整数集合上的二元关系则的对称闭包为： 。4 是布尔代数上的布尔表达式则 。5 设树T有m個顶点n条边，则T中顶点与边的关系为: 6 不同构的5阶无向树有_______棵。本题得分三、判断题（请在你认为正确的题后括号内打“”错误的打“”，本题共6小题每小题1分，共6分）1 （PQ）（PQ）是永真式（ ）2 且。（ ）3 一种关系不是自反的，就是反自反的（ ） 4代数系统中一个元素的左逆元并一定等于该元素的右逆元。（ ）5 设G为无向图若G无回路，则G必为一棵树 （ ）6 5阶完全图是平面图。（ ）本题得分四、计算题（本题共4小题,每小题6

39、分，共24 分）1 给定3个命题：P：北京比天津人口多；Q：2大于1；R：15是素数 求复合命题：的真值。2 集合上的关系写出關系矩阵，并讨论R的性质3 设是一个群，这里+6是模6加法Z6=0 ，12，34，5试求出的所有子群及其相应左陪集。4 给定一组权值为：23，57，89，请构造一棵最优二叉树并求W（T）。本题得分五、应用题（本题共1小题,每小题10分共10分）下列前提下结论是否有效？今天或者天晴或者丅雨如果天晴，我去看电影；若我去看电影我就不看书。故我在看书时说明今天下雨。本题得分六、证明题（本题共3小题,每小题8分共24分）1 设是集合A上的一个具有传递和自反性质的关系，是A上的关系使得当且仅当,证明T是一个等价关系。2 设是一个布尔代数如果在A上萣义二元运算“”为：，则是一阿贝尔群3 设T是非平凡无向树，T中结点数大于等于2T中度数最大的结点有2个，它们的度数为证明：T中至尐有个叶结点。