吉林大学2005软件学院离散数学I试题(A).doc

《吉林大学2005软件学院离散数学I试题(A).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、吉林大学软件学院2005级本科《离散数学I》试题（A）一、简答题（本大题共20小题，每小题2分，共40分）1、设集合A={Æ}，则幂集合r(r(A))的基数是多少？2、设命题公式的集合S={P，Q，PÙQ，PÚQ}，Þ是S上的公式蕴涵关系，则部分序集(S,Þ)中的最大元和最小元是什么？3、设集合A={a,b}，请给出集合A上所有的等价关系。4、设R是集合A={1,2,3}上的二元关系，R={(1,1),(2,3),(3,1)}，问R满足反自反性吗？R满足反对称性吗？5、是否存在集合A，使得A与r(A)等势？若存在，请举例说明

2、。6、命题公式(PÙ(ØP®Q))®Q是恒真公式吗？若不是，请给出一个弄假G的解释。7、写出关于3个原子P、Q、R的极小项m3。8、若短语恒假，则该短语中一定包含互补对吗？若子句中包含互补对，则该子句一定恒真吗？9、对于包含4个不同原子的恒假公式，其主析取范式共包含多少个极小项？10、蕴含式"xP(x)Þ$xP(x)一定成立吗？11、设G＝"xP(x)Ú"xQ(x)，H＝"x(P(x)ÚQ(x))，个体域D={a，b}，请给弄假公式G，但满足H的一个解释。12、有向树中所有点都只发出一条弧吗？有向树一定强连通吗？13、没有孤

3、立点的Euler图一定是强连通的吗？其中的Euler路一定经过图中每个点吗？14、若有限树T中共有m(m³2)个度为1的点，则树T中任意点的度一定£m，对吗？15、给出mod9的一个完全剩余系和一个简化剩余系。16、任意整数都能写成质数乘积吗？若不能，请举例。17、若a

4、b且b

5、a，则a=b，对吗？18、对任意正整数m、n，都有nmºn(modm)成立吗？若不成立，请举反例。19、对任意两个整数a、b的最高公因数d，都有d=sa+tb，s、t为整数，请问s和t的最高公因数是多少？20、画出右图的闭合图，在该图的闭合图中共有多

6、少条不同的Hamilton回路？（注：若两条Hamilton回路包含的边完全相同(可能顺序不同)，则这两条Hamilton回路相同；两条不同的Hamilton回路中至少存在一条不同的边，）。二、解答题（本大题共6小题，共60分）1、【10分】求命题公式P®Q的主析取范式。2、【10分】求谓词公式$xG(x,y)®"yH(y)的Skolem范式。3、【10分】用形式演绎法证明{ØS,PÚQ,ØQÚS,P®R}ÞR。4、【10分】设集合A={1,2,3,4,…,99,100}上的关系R={(x,y)

7、x+y为偶数，xÎA，yÎA

8、}，证明：R是A上的等价关系，并求出商集A/R。5、【10分】解同余式组（要求写出求解步骤）xº2（mod5）xº5（mod6）xº4（mod7）6、【10分】下图是一个有6个点的权图，请解答如下问题：（1）求出图中A点到其它各点的最短路及长度；（2）画出图中的一棵最优树。（不必写算法步骤，只写结果即可）ADEFCB9885518232415321282251115