资源描述
. . 题型一、填空题1、设集合A有n个元素,那么A的幂集P(A)的元素个数为_。2、谓词公式$xF(x)Q(x,y)中的前束式为_。3、设集合Aa,b,a,b,Ba,b,则B-A=_。4、设集合A0,1,B1,2,则AB=_。5已知图G中有1个1度结点,2个2度结点,3个3度结点,则G的边数是。二、单项选择题1、以下各命题中真值为真的命题有( )。A. 2+2=4当且仅当3是奇数 B. 2+2=4当且仅当3不是奇数C. 2+24当且仅当3是奇数 D. 2+2=4仅当3不是奇数2、设个体域D=a,b,与公式等价的公式是( )。A. B. C. D. 3、令F(x):x是人,G(x):x是犯错误,则命题“没有不犯错误的人”可符号化为( )。A. B.C. D.4、以下命题公式不是永真式的是( )。A. B . C. D. 5、设X=1,2,3,Y=a,b,c,f=,则以下命题正确的是( )。Af是从X到Y的二元关系,但不是从X到Y的函数Bf是从X到Y的函数,但不是满射的,也不是单射的Cf是从X到Y的满射,但不是单射 Df是从X到Y的双射6、设集合A=a, b, c,A上的二元关系R=, , ,则R是( )。A.自反的 B.对称的 C. 传递的 D.反对称的7、设集合A=1,2,3,4,A上的等价关系R= , IA,则对应于R的划分是( )。A. 1,2,3,4 B. 1,3,2,4 C. 1,3,2,4 D. 1,2,3,4图1 G1dcab8、图G1如图1所示,以下说确的是( )。A. a是割点 B. b,c是点割集 C. b,d是点割集 D. c是割点9、设集合S=1,-1,下面定义的哪种运算关于集合S是封闭的( )。A. 普通的减法运算 B. 普通的加法运算 图2 G2243612623C. 普通的乘法运算 D. 以上均不是10、 集合A=2,3,6,12,24,36上的偏序关系R的哈斯图G2如图2所示,则集合B=2,3,6的最小元为( )。A. 2 B. 3 C. 2和3 D. 不存在三、 推理与证明题1、已知A,B,C是三个集合,证明:A-(BC)=(A-B)-C.2、构造下面推理的证明。 前提:A,AB,AC,B(DC) 结论:D四、 综合应用题1、 利用等值演算法求命题公式(PQ)R的主合取式并给出其成真赋值和成假赋值。2、设集合=a,b,c上的二元关系R=a,b,b,a,b,c,求R的自反闭包r(R),对称闭包s(R)与传递闭包t(R)。3、设有向图D如图G3所示,回答以下问题:(1)求图D的邻接矩阵;(2)求图D中长度为2的通路数;(3)求图D中长度为2的回路数;(4)求图D的可达矩阵。4、如图4-1和图4-2所示的两个图G4,G5:(1)试判断它们是否为欧拉图?并说明理由;(2)若是欧拉图,请写出一条欧拉回路;dbecfajihg(3)若不是欧拉图,请问至少添加几条边,能够使其成为欧拉图。cedba 图4-1 G4图4-2 G55、设R为实数集合,在R上定义二元运算*,有(1)验证二元运算*是否满足结合律;(2)求二元运算*的单位元;(3)对实数x,求其逆元。离散数学期末考试复习题一、填空题1、谓词公式中的辖域是。2、将以下命题进行命题符号化为_。(1) 平不但聪明又用功。 (2) 平虽然聪明,但不用功。 (3) 平不但聪明,而且用功。 (4) 平不是不聪明,而是不用功。 3、将以下命题进行命题符号化为_。(1) 人不犯我,我不犯人;人若犯我,我必犯人。 (2) 不经一事,不长一智。4、 命题公式的成真赋值为_。5、命题公式的成真赋值为 _。6、将命题“没有一个运动员不是强壮的”谓词符号化为_。7、给定简单命题函数:A(x):x身体好, B(x):x学习好, C(x):x工作好,复合命题函数 A(x)(B(x)C(x)表示的含义是:_。8、将以下命题符号化:_。(1)偶数均能被2整除. (2)存在着偶素数. (3)没有不吃饭的人.(4)素数不全是奇数. 9、公式的前束式为_。10、谓词公式(xF(x,y)$yG(x,y)的前束式为。11、在1和1000之间(包括1和1000在)不能被4和5整除的数有个。12、若集合Aa,b,B0,1,2,则AB为_;BA为_。13、设集合A = 1, 2,则P(A)为_; P(A)A为_。14、设集合A=0, 1, B=1, 2, C=0, 1, 2 ,则A, B和C的笛卡尔积ABC为:_。15、请用谓词表达式(或枚举方式)描述实数集上子集A上的小于等于关系_;正整数集合的子集B上的整除关系_;集合C的幂集上的包含关系_;集合D=1,2,3,4,5,6,7上的模3同余关系_。16设是定义在集合上的二元关系,则的对称闭包_。17、命题“所有的人都是要死的”的否定的含义是_。18、设集合A中有m个元素,集合B中有n个元素,则集合A和集合B的笛卡尔积AB中含有_个元素,定义在集合A和集合B上不同的二元关系有_个,从集合A到集合B不同的函数有_个。19无向连通图是欧拉图的充分必要条件是_。20已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是21设给定图G(如以下图所示),则图G的点割集是ooooocabedof22设无向图G是哈密尔顿图,则V的任意非空子集V1,都有23设有向图D为欧拉图,则图D中每个结点的入度24设完全图Kn有n个结点(n2),m条边,当时,Kn中存在欧拉回路25集合A=a , b , c 上总共可定义的二元运算的个数为_。26设,则关于普通加法、减法、乘法中_ _运算是封闭的。27设,在代数系统中,分别表示模n的加法和乘法,则对运算的单位元是_,对的单位元是_。28设G=1 , 2 , 3 , 4 , 5, 6,G关于模7乘法构成代数系统,群G的幺元是_,元素3与_互为逆元。二、单项选择题1、以下句子中有( )个是命题。 (1) 我是老师。(2) 禁止吸烟! (3) 蚊子是鸟类动物。(4) 月亮比地球大。A. 1 B . 2 C. 3 D. 42、以下公式中,哪个是永真式( )A. B. C. D. 3、 设: 是有理数,:能表示成分数。在一阶逻辑中,命题“没有不能表示成分数的有理数”可符号化为( )。A. B. C. D. 4、 设个体域是整数集,则以下命题的真值为真的是( )。A BC D5、以下命题中为假命题的是( )(其中P(A)为A的幂集)A B. C. D.6、 集合上的关系,则的性质为( )。A、自反的 B、传递的、对称的C、对称的 D、反自反的、传递的7、设分别表示实数、整数和自然数集,设函数,(除以3所得的余数),则上述函数中满射的个数为( )。A1 B. 2 C. 3 D. 4 8、设R和S定义在P上,P是所有人的集合。, ,则对于表示( )A.x是y的丈夫 B.x是y的妻子 C. x是y的子 D.x是y的祖母9、设集合A =1 , 2, 3上的函数分别为:f = ,g = ,h = ,则h =( ) A. fg B. gf C. ff D. gg10设图G的邻接矩阵为则G的边数为( )A5 B6 C3 D411图G如右图所示,以下说确的是 ( ) A(a, d)是割边B(a, d)是边割集C(d, e)是边割集D(a, d) ,(a, c)是边割集12无向图G存在欧拉通路,当且仅当( )AG中所有结点的度数全为偶数 BG中仅有有两个奇数度结点CG连通且所有结点的度数全为偶数DG连通且仅有两个奇数度结点13设S=a,b,则S上总共可定义的二元运算的个数是( ) A.4B.8C.16D.3214设集合,下面定义的哪种运算关于集合是不封闭的( )。 A BC 即的最大公约数D 即的最小公倍数15在自然数集N上,以下哪种运算是可结合的?( )A.a*b=a-bB.a*b=maxa,bC.a*b=a+2bD.a*b=|a-b|16设是正整数集上的二元运算,其中(即取与中的最大者),那么在中( )A不适合交换律;B不适合结合律;C存在单位元;D每个元都有逆元。三、计算题1、 求命题公式的主析取式,主合取式与其成真成假赋值。2、 求命题公式的主析取式,主合取式与其成真成假赋值。3、 求命题公式主析取式,主合取式与其成真成假赋值。4、 求命题公式p (q r)主析取式,主合取式与其成真成假赋值。5、给定集合A=a,b,c,d,给出A上的所有等价关系。6、给定集合A=a,b,c,给出A上的所有等价关系。7、设A=a,b,c,d。以下哪个是A的划分,请说明原因?若是划分,则求其诱导的等价关系?(1)B=a,b,c,d;(2)C=a,b,c,a,d;(3)D=a,b,c8、设为偏序集,其中,是上的整除关系。(1)画出的哈斯图;(2)求中的极大元最大元、最小元、极大元、极小元。9、设集合,R为A上的整除关系,则R为偏序关系。1) 求该关系的哈斯图;2) 令,求B的最大元、最小元、极大元、极小元、上界,上确界,下界和下确界。10、 设集合,R为A上的二元关系,且,1) 求R的关系矩阵;2) 求R的性质;3) 求R的自反闭包,对称闭包以与传递闭包t(R);11、 给定解释I如下:(1) D1=2,3; (2) D1中特定元素a=2;(3) 函数f(x)为f(2)=3,f(3)=2;(4)谓词F(x)为F(2)=0;F(3)=1;G(x,y)为G(i,j)=1,i,j=2,3;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;在解释I下,求以下各式的真值。1)2)3)12、求出以下公式的前束式1) 2)3)4)5)13、求1到1000之间不能被5、6、8整除的数的个数。14、设Aa,b,c,d,R,试给出R和r(R),s(R),t(R)的关系图。15、设图G=,其中V=a1,a2,a3,a4,a5,E=,(1)试给出G的图形表示;(2)求G的邻接矩阵,关联矩阵;v2v1(3)判断图G是强连通图、单侧连通图还是弱连通图?16、设有向图D如右图所示,求图D中长度为3的通路数,并指出其中的回路数v4v317、在实数集合R上定义二元运算(1) 验证*是否满足交换律和结合律。(2) 求*的单位元。(3) 对任何实数X,求其逆元。18、设代数系统,其中,*运算定义如下表,请指出*运算是否是可交换的;是否有单位元;如果有单位元,指出哪些元素是可逆的,并给出它们的逆元。19、设V=为代数系统,其中A=0,1,2,3,4,。(1) 列出*的运算表(2) *是否有零元和幺元?若有幺元,请求出所有可逆元素的逆元。20、设Z为整数集合,在Z上定义二元运算*,有,(1) 二元运算*满足结合律吗?(2)二元运算*是否有零元和幺元?若有幺元,请求出所有可逆元素的逆元。(3)Z与二元运算*是否构成群,为什么。22、学生会下设6个委员会, 第一委员会=, , 王, 第二委员会=, , , 第三委员会=, , 王, 第四委员会=, , , 第五委员会=, 王, 第六委员会=, , 王. 每个月每个委员会都要开一次会, 为了确保每个人都能参加他所在的委员会会议, 这6个会议至少要安排在几个不同时间段?23、某课题组要从a, b, c, d, e 5人中派3人分别到、去开会,每个地方只能去一人. 已知a只想去,b只想去,c, d, e都表示想去或. 问该课题组在满足个人要求的条件下,给出一种派遣方案?24、有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语. 问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈?25、画出下面平面图的对偶图四、推理与证明。 1、如果我上街,我一定去新华书店.我没上街,所以我没去新华书店.2、若小喜欢数学,则小或小也喜欢数学。若小喜欢数学,则他也喜欢物理。小确实喜欢数学,可小不喜欢物理。所以,小喜欢数学。3、如果今天是星期一,则要进行英语或离散数学的考试.如果英语老师有会,则不考英语.今天是星期一,英语老师有会,所以进行离散数学的考试.4、构造下面推理的证明前提:qp,q s,s t, tr结论:pqsr 5、判断以下推理是否正确。先将命题符号化,再写出前提和结论,然后进行判断。a) 如果今天是1号,则明天是5号,今天是1号,所以明天是5号。 b) 如果今天是1号,则明天是5号,明天是5号,所以今天是1号。 c) 如果今天是1号,则明天是5号,今天不是1号,所以明天不是5号。 d) 如果今天是1号,则明天是5号,明天不是5号,所以今天不是1号。 6、构造下面推理的证明 前提:PQ,(QR) 结论:P7、构造下面推理的证明 前提:(PQ)R,RS,S,P 结论:Q8、构造下面推理的证明 前提:ABC, BD , (EP)D, BAE 结论:BE9、给定集合A,证明P(A)上的包含关系为偏序关系。10、给定有限集合A,证明A上的小于等于关系为偏序关系。11、设为偏序集,其中,是上的整除关系,试证明R为偏序关系。12、令I是整数集合,I上关系R定义为:R=|x-y可被m整除,求证R是自反、对称和传递的。13、已知A、B、C是三个集合,证明以下集合恒等式。 A(BC)=(AB)(AC) A(BC)=(AB)(AC) A-(BC)=(A-B)(A-C) A-(BC)=(A-B)(A-C)14、若无向图G中只有两个奇数度结点,则这两个结点一定是连通的15、设G是一个n阶无向简单图,n是大于等于2的奇数证明图G与它的补图中的奇数度顶点个数相等16、设连通图G有k个奇数度的结点,证明在图G中至少要添加条边才能使其成为欧拉图17、设G为n阶无向连通简单图, 若G中有割点或桥, 则G不是哈密顿图.18、证明K5 和 K3,3不是平面图.五、判断题1、以下命题公式的类型,若为可满足式,给出成真赋值1) 2) 3) 4) 5) 6) 7)8) 9) 10) 11) 2、如何判断一个二元关系是否具有自反性、反自反性、对称性、反对称性以与传递性(给出一种方法即可)。3、设集合A=1,2,3,A上关系R1,R2,R3,R4,.判断其各有哪些性质(用二进制码依次对是否具有自反、反自反、对称、反对称、传递性质进行标示):R1=, , ;R2=, , ;R3=, ;R4=, , , , , ;R5=, , ;R6=, , , , ;.4、判断以下f、g、h是否为从A到B的函数,若是,再判断是否是单射、满射或双射;若不是,请说明理由。1) A=1,2,3,4,5,B=6,7,8,9,10,f=, , , , 。2) A=1,2,3,4,5,B=6,7,8,9,10,g=, , , 。3) A=1,2,3,4,5,B=6,7,8,9,10,h=, , , , , 。4) A=B=R(实数集), f(x)=x2-x。5) A=B=R(实数集), f(x)=x3。6) A=B=R(实数集), f(x)=。5给定两个图G1,G2(如以下图所示):(1)试判断它们是否为欧拉图、汉密尔顿图?并说明理由(2)若是欧拉图,请写出一条欧拉回路11 / 11
展开阅读全文