华南理工网络教育离散数学同步练习册.doc

上传人:wux****ua 文档编号:8888912 上传时间:2020-04-01 格式:DOC 页数:30 大小:190.50KB
返回 下载 相关 举报
华南理工网络教育离散数学同步练习册.doc_第1页
第1页 / 共30页
华南理工网络教育离散数学同步练习册.doc_第2页
第2页 / 共30页
华南理工网络教育离散数学同步练习册.doc_第3页
第3页 / 共30页
点击查看更多>>
资源描述
离散数学同步练习册 学号姓名专业教学中心华南理工大学二O一O年九月第一章命题逻辑一填空题(1)设:p:派小王去开会。q:派小李去开会。则命题:“派小王或小李中的一人去开会” 可符号化为: pq 。(2)设A,B都是命题公式,AB,则AB的真值是 T 。(3)设:p:刘平聪明。q:刘平用功。在命题逻辑中,命题:“刘平不但不聪明,而且不用功” 可符号化为: pq 。(4)设A , B 代表任意的命题公式,则蕴涵等值式为A B PQ 。(5)设,p:径一事;q:长一智。在命题逻辑中,命题:“不径一事,不长一智。” 可符号化为: pq 。(6)设A , B 代表任意的命题公式,则德 摩根律为(A B) AB 。(7)设,p:选小王当班长;q:选小李当班长。则命题:“选小王或小李中的一人当班长。” 可符号化为: (AB) (AB) 。(8)设,P:他聪明;Q:他用功。在命题逻辑中,命题:“他既聪明又用功。” 可符号化为: PQ 。(9)对于命题公式A,B,当且仅当 AB 是重言式时,称“A蕴含B”,并记为AB。(10)设:P:我们划船。Q:我们跑步。在命题逻辑中,命题:“我们不能既划船又跑步。” 可符号化为: (PQ) 。(11)设P , Q 是命题公式,德摩根律为:(P Q) PQ 。(12)设 P:你努力。Q:你失败。在命题逻辑中,命题:“除非你努力,否则你将失败。” 可符号化为: PQ 。(13)设 p:小王是100米赛跑冠军。q:小王是400米赛跑冠军。在命题逻辑中,命题:“小王是100米或400米赛跑冠军。” 可符号化为: pq 。(4)设A,C为两个命题公式,当且仅当 A C 为一重言式时,称C可由A逻辑地推出。二判断题1. 设A,B是命题公式,则蕴涵等值式为ABAB。 ( F )2. 命题公式pqr是析取范式。 ( T )3. 陈述句“x + y 5” 是命题。 ( T )4. 110 (p=1,q=1, r=0)是命题公式 (pq)r)q 的成真赋值。 ( T )5. 命题公式 p(pq) 是重言式。 ( F )6. 设A,B都是合式公式,则ABB也是合式公式。 ( F )7. A(BC)( AB)(AC)。 ( F )8. 陈述句“我学英语,或者我学法语” 是命题。 ( T )9. 命题“如果雪是黑的,那么太阳从西方出”是假命题。 ( T )10. “请不要随地吐痰!” 是命题。 ( F )11. P Q P Q 。 ( F )12. 陈述句“如果天下雨,那么我在家看电视” 是命题。 ( T )13. 命题公式(PQ)(RT)是析取范式。 ( T )14. 命题公式 (PQ) R (PQ) 是析取范式。 ( T )三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的 内。1 设:P:天下雪。Q:他走路上班。则命题“只有天下雪,他才走路上班。”可符号化为 (1) 。 (1)PQ (2)Q P (3) Q P (4)Q P2 (1 ) 明年国庆节是晴天。(2 ) 在实数范围内,x+y3。 (3 ) 请回答这个问题!(4 ) 明天下午有课吗?在上面句子中,是命题的只有 (2 ) 。3 命题公式A与B是等值的,是指 (4 ) 。(1) A与B有相同的命题变元(2) AB是可满足式(3) AB为重言式(4) AB为重言式4 (1 ) 雪是黑色的。(2 ) 这朵花多好看呀!。 (3 ) 请回答这个问题!(4 ) 明天下午有会吗?在上面句子中,是命题的是 (1 ) 。5 设:P:天下大雨。Q:他乘公共汽车上班。则命题“只要天下大雨,他就乘公共汽车上班。”可符号化为 (2) 。 (1)QP (2)P Q (3) Q P (4)Q P6 设:P:你努力;Q:你失败。则命题“除非你努力,否则你将失败。”在命题逻辑中可符号化为 (3) 。 (1)QP (2)P Q (3) P Q (4)Q P7 (1 ) 现在开会吗?(2 ) 在实数范围内,x+y 5。 (3 ) 这朵花多好看呀!(4 ) 离散数学是计算机科学专业的一门必修课。在上面语句中,是命题的只有 (2 ) 。8 设:P:天气好。Q:他去郊游。则命题“如果天气好,他就去郊游。”可符号化为 (1) (1)PQ (2)Q P (3) Q P (4)Q P9 下列式子是合式公式的是 (4) 。(1)(P Q) (2) (P (Q R)(3)(P Q) (4) Q R10 (1)1101110 (2) 中国人民是伟大的。 (3) 全体起立! (4) 计算机机房有空位吗?在上面句子中,是命题的是 (1) 。11 设:P:他聪明;Q:他用功。则命题“他虽聪明但不用功。”在命题逻辑中可符号化为 (4) 。 (1)P Q (2)P Q (3)P Q (4)P Q12 (1 ) 如果天气好,那么我去散步。 (2 ) 天气多好呀! (3 ) x=3。 (4 ) 明天下午有会吗?在上面句子中 (1 ) 是命题。13 设:P:王强身体很好;Q:王强成绩很好。命题“王强身体很好,成绩也很好。”在命题逻辑中可符号化为 (4) 。 (1)P Q (2)P Q (3)P Q (4)P Q四、解答题1设命题公式为(pq)(qp)。 (1)求此命题公式的真值表;(2)给出它的析取范式;(3)判断该公式的类型。(1)Pqpqpqqp(pq)(qp)TTFFTFFTFFTTTTFTTFTTTFFTTFTT(2)(p q)p q(3)可满足式2设命题公式为(p q)(p r)。 (1)求此命题公式的真值表;(2)给出它的析取范式;(3)判断该公式的类型。(1)pqrpqp r(p q)(p r)TTTTTTTTFTTTTFTFTFTFFFTFFTTTTTFTFTTTFFTTTTFFFTFF(2)(pq) ( p r) (pr)(3) 可满足式3设命题公式为 Q (P Q) P。 (1)求此命题公式的真值表;(2)求此命题公式的析取范式;(3)判断该命题公式的类型。(1)PQ P QP Q(P Q) P Q (P Q) PTTFFTTFTFFTFTTFTTFTTFFFTTTFF(2) P(P Q)(3) 可满足式4完成下列问题 (1)求此命题公式 Q (P Q) P 的真值表;(2)求命题公式(P(QR)S的析取范式。(1)同上表(2) P(Q R) S5设命题公式为(P (P Q) Q。(1)求此命题公式的真值表;(2)判断该公式的类型。(1)PQP QP (P Q)(P (P Q) QTTTTTTFFFTFTTFFFFTFF(2) 可满足式6设命题公式为(P Q)P) Q。 (1)求此命题公式的真值表;(2)给出它的析取范式;(3)判断该公式的类型。(1)PQPP Q(P Q)P(P Q)P) QTTFTFTTFFTFTFTTTTTFFTFFT(2) P Q(P Q)(3)重言式7用直接证法证明 前提:P Q,P R,Q S结论:S R证明:8用直接证法证明 前提:P (Q R),S Q,P,S。结论:R证明:S Q,S推出 Q(假言推论)P (Q R),P推出Q R (假言推论) Q,Q R推出R(析取三段论)第二章谓词逻辑一填空题(1)若个体域是含三个元素的有限域a,b,c,则A(x) A(a)A(b)A(c) (2)取全总个体域,令F(x):x为人,G(x):x爱看电影。则命题“没有不爱看电影的人。”可符号化为_($x_(F(x)_ G(x)_。(3)若个体域是含三个元素的有限域a,b,c,则xA(x) A(a) A(b) A(c) 。(4)取全总个体域,令M(x):x是人,G(y):y是花, H(x,y):x喜欢y。则命题“有些人喜欢所有的花。”可符号化为_$x$y (_M(x) H(x,y) G(y)_。(5)取个体域为全体人的集合。令F(x):x在广州工作,G(x):x是广州人。在一阶逻辑中,命题“在广州工作的人未必都是广州人。”可符号化为_$x (F(x) G(x)_。(6)P(x):x是学生,Q(x):x要参加考试。在谓词逻辑中,命题:“每个学生都要参加考试” 可符号化为:x(P(x) Q(x) ) 。(7)M(x):x是人,B(x):x勇敢。则命题“有人勇敢,但不是所有的人都勇敢”谓词符号化为 _$x (M(x) B(x) (x(M(x) B(x)_。(8)P(x):x是人,M(x):x聪明。则命题“尽管有人聪明,但不是一切人都聪明”谓词符号化为 _$x (P(x) M(x) (x(P(x) M(x)_。(9)I(x):x是实数,R(x):x是正数,N(x):x是负数。在谓词逻辑中,命题:“任何实数或是正的或是负的” 可符号化为:x(I(x) R(x) R(x) 。(10)P(x):x是学生,Q(x):x要参加考试。在谓词逻辑中,命题:“每个学生都要参加考试” 可符号化为:x(P(x) Q(x) ) 。(11)令M(x):x是大学生,P(y):y是运动员, H(x, y):x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为 _$xy(M(x) P(y) H(x, y) _ _。二判断题1. 设A,B都是谓词公式,则x AB也是谓词公式。 ( T )2. 设c是个体域中某个元素,A是谓词公式,则A(c) xA(x)。 ( F )3. xyA(x,y) yxA(x,y) 。 ( T )4. x$yA(x,y) $yxA(x,y) 。 ( F )5. 取个体域为整数集,则谓词公式xy(x y = y ) 是假命题。 (T )6. (x)(P(x)Q(x)) (x)(P(x) Q(x))。 (T )7. 命题公式 (PQ R) (PQ) 是析取范式。 ( F )8. 谓词公式(x)(A (x) B(x, y) R(x) 的自由变元为x, y。 ( F )9. (x)A(x) B)($x)(A(x) B)。 (F )10. R(x):“x是大学生。” 是命题。 (T )三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的 内。1设F(x):x是火车,G(x):x是汽车,H(x,y):x比y快。命题“某些汽车比所有火车慢”的符号化公式是 (2) 。(1) $y(G(y)x(F(x)H(x,y)(2) $y(G(y)x(F(x)H(x,y)(3) x $y(G(y)(F(x)H(x,y)(4) $y(G(y)x(F(x)H(x,y)2设个体域为整数集,下列真值为真的公式是 (3) 。(1)$yx (x y =2)(2)xy(x y =2)(3)x$y(x y =2)(4)$xy(x y =2)3设F(x):x是人,G(x):x早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是 (4) 。(1) (x)(F(x) G(x)(2) (x)(F(x) G(x)(3) ($x)(F(x) G(x)(4) ($ x)(F(x) G(x)5下列式子中正确的是 (4) 。(1)(x)P(x)($x)P(x) (2)(x)P(x)(x) P(x)(3)($x)P(x)($x) P(x) (4)($x)P(x)(x) P(x)6下面谓词公式是永真式的是(d) 。a) P(x) Q(x)b) (x)P(x)($x)P(x)c) P(a)(x)P(x)d) P(a)($x)P(x)5 设S(x):x是运动员,J(y):y是教练员,L(x,y):x钦佩y。命题“所有运动员都钦佩一些教练员”的符号化公式是 (c) 。a) x(S(x) y(J(y) L(x,y)b) x $y(S(x)(J(y) L(x,y)c) x(S(x) $y(J(y) L(x,y)d) $yx(S(x)(J(y) L(x,y)6 下列式子是合式公式的是 (2) 。(1)(P Q) (2) (P (Q R)(3)(P Q) (4) Q R7 下列式子中正确的是 (4) 。(1)(x)P(x)($x)P(x) (2)(x)P(x)(x) P(x)(3)($x)P(x)($x) P(x) (4)($x)P(x)(x) P(x)四、解答题1构造下面推理的证明:前提:$ x F(x)y(F(y) G(y) R(y),$ x F(x)。结论:$ x R(x)。2在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。令F(x):x喜欢步行。G(x):x喜欢坐汽车。H(x):x喜欢骑自行车。x( F(x) G(x), x(G(x) H(x), $ x H(x) $ x F(x)3在命题逻辑中构造下面推理的证明: 如果他是理科学生,他必须学好数学。如果他不是文科学生,他必是理科学生。他没学好数学,所以他是文科学生。4用直接证法证明:前提:(x)(C(x) W(x)R(x),($x)(C(x)Q(x)结论:($x)(Q(x)R(x)。第三章集合与关系一填空题(1)如果|A|n,那么|AA|n*n。A上的二元关系有_2_个。(2)集合A上关系R的自反闭包r(R)=_。(3)设集合A上的关系R和S,R=(1,2),(1,3),(3,2),S=(1, 3),(2,1),(3,2),则SR= (2,2),(1,2) 。(4)如果|A|n,那么|P(A)|。(5)设集合A上的关系R和S,R=,S=,则RS= , 。(6)设集合E=a, b, c,E的幂集P(E) ,a,b,c,a,b,a,c,b,c,a,b,c_。(7)设R是定义在集合X上的二元关系,如果对于每个x, yX, _ _ _ ,则称集合X上的关系R是对称的。(8)设关系R和S为,R=,S=,则RS =_ _ _ _。(9)设R是定义在集合X上的二元关系,如果对于每个x, yX, _ _ _ ,则称集合X上的关系R是自反的。二判断题1设A、B、C为任意的三个集合,则A(BC)=A(BC)。 ( )2设S,T是任意集合,如果S -T = ,则S = T。 ( )3集合A=1,2,3,4上的关系,是一个函数。 ( )4集合A=1,2,3,4上的整除关系是等价关系。 ( )5集合A 的幂集P(A)上的包含关系是偏序关系。 ( )6设A=a, b, c, R AA且R=, 则R是传递的。 ( )6设A,B是任意集合,如果B ,则A B A。 ( )7集合A=1,2,3上的关系,是传递的。 ( )8集合A=1,2,3,4上的小于关系是等价关系。 ( )9关系x1, x2N, x1+x26能构成一个函数。 ( )10集合A 上的恒等关系是偏序关系。 ( )11集合A=1,2,3上的关系S=,是自反的。 ( )12设X=1, 2, 3, Y=a, b, c。函数F=,是双射。 ( )13集合A上的关系R的自反闭包r(R)=RIA。 ( )14集合A上的偏序关系R是自反的、对称的、传递的。 ( )15. 设A,B是任意集合,则A B (A-B) (B-A)。 ( )三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的 内。1 设A=a,b,c,B=a,b,则下列命题不正确的是 。a) AB=a,bb) AB= a,b c) AB=cd) BA2 设 A = a, b, c, d, A 上的关系R = , , , ,则它的对称闭包为。a) R = , , , , , , ,b) R = , , , , ,c) R = , , , , , ,d) R = , , , , , ,3 对于集合1, 2, 3, 4上的关系是偏序关系的是 。a) R=, ,b) R=, ,c) R=, ,d) R=, ,4 设A=1,2,3,4,5,B=6,7,8,9,10,以下哪个关系是从A到B的单射函数 。a) f =,b) f =,c) f =,d) f =,5设 A = a, b, c,要使关系, , , R 具有对称性,则 。a) R = , b) R = , c) R = , d) R = , 6设S=F,1,1,2,则S的幂集P(S)有 个元素 (1)3 (2)6 (3)7 (4)87设R为定义在集合A上的一个关系,若R是 ,则R为等价关系 。(1)反自反的,对称的和传递的 (2)自反的,对称的和传递的(3) 自反的,反对称的和传递的 (4)对称的,反对称的和传递的8设S,T,M为任意集合,下列命题正确的是 。a) 如果ST = SM,则T = Mb) 如果S-T = F,则S = Tc) S-T Sd) S S = S9 设 A = a, b, c,要使关系, , , R 具有对 性,则 。(1)R = , (2)R = , (3) R = , (4)R = , 10设A=1,2,3,4,5,B=a,b,c,d,e,以下哪个函数是从A到B的入射函数 。a) F =,b) F=,c) F =,d) F=,四、解答题1已知偏序集(A,),其中A=a,b,c,d,e,“”为(a,b),(a,c),(a,d),(c,e),(b,e),(d,e),(a,e)IA。(1)画出偏序集(A,)的哈斯图。(2)求集合A的极大元,极小元,最大元,最小元。2设R是集合A = 1, 2, 3, 4, 5, 6, 7, 8, 9上的整除关系。 (1) 给出关系R;(2)画出关系R的哈斯图;(3)指出关系R的最大、最小元,极大、极小元。 3设R是集合A = 1, 2, 3, 4, 6, 12上的整除关系。(2) 给出关系R;(2) 给出COV A(3) 画出关系R的哈斯图;(4) 给出关系R的极大、极小元、最大、最小元。 第五章代数结构一填空题(1)集合S的幂集P(S)关于集合的并运算“”的零元为 _。(2)集合S的幂集P(S)关于集合的并运算“”的零元为 _。(3)集合S的幂集P(S)关于集合的并运算“”的么元为 _。(4)一个代数系统S, * ,其中S是非空集合。*是S上的一个二元运算,如果 ,则称代数系统S, * 为广群。二判断题1含有零元的半群称为独异点。 ( )2运算“”是整数集I上的普通加法,则群的么元是1。 ( )三、填空题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的 内。1 下列群一定为循环群的是。e) (运算“”是整数集I上的普通加法)f) (R是实数集,“”是普通乘法)g) (运算“”是有理数集Q上的普通加法)h) (P(S)是集合S的幂集,“”为对称差)2运算“”是整数集I上的普通减法,则代数系统 满足下列 性质 。(1)结合律 (2)交换律 (3)有零元 (4) 封闭性3设I是整数集,N是自然数集,P(S)是S的幂集,“,”是普通的乘法,加法和集合的交运算。下面代数系统中 是群。 (1) (2) (3) (4)4下列代数系统不是群的是。(5) (运算“”是整数集I上的普通加法)(6) (P(S)是集合S的幂集,“”为交运算)(7) (运算“”是有理数集Q上的普通加法) (P(S)是集合S的幂集,“”为对称差)第七章图论一填空题(1)一个无向图G=(V,E)是二部图当且仅当G中无 长度的回路。(2)任何图(无向的或有向的)中,度为奇数的顶点个数为。(3)设D是一个有向图,若D中任意一对顶点都是相互可达的,则称D是_。(4)既不含平行边,也不含环的图称为 。(5)经过图中 一次且仅一次并且行遍图中每个顶点的回路,称为欧拉回路。(6)一棵有n个顶点的树含有_边。(7)设G =(V,E),G =(V,E)是两个图,若 且 ,称G是G的生成子图。 (8)经过图中 一次且仅一次的回路,称为哈密尔顿回路。二判断题15个顶点的有向完全图有20条边。 ( )2连通无向图的欧拉回路经过图中的每个顶点一次且仅一次。 ( )3 图中的初级通路都是简单通路。 ( )4 已知n (n2)阶无向简单图G有n 1条边,则G一定为树。 ( )5 n阶无向完全图Kn的每个顶点的度都是n。 ( )6一个无向图是二部图当且仅当它没有奇数度的顶点。 ( )7任何图都有一棵生成树。 ( )8连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。 ( )9图中的初级回路都是简单回路。 ( )10任一图G=(V,E)的顶点的最大度数必小于G的顶点数。 ( )11欧拉图一定是汉密尔顿图。 ( )12无向连通图G的任意两结点之间都存在一条路。 ( )13根树中除一个结点外,其余结点的入度为1。 ( )三、选择题:在每小题的备选答案中只有一个正确答案,将正确答案序号填入下列叙述中的 内。1 下列为欧拉图的是 。2 下列各图为简单图的是 。(4)(3)(2)(1) 3 设无向图G有12条边,已知G中3度顶点有6个,其余顶点的度数都小于3,则该图至少有 个顶点。 (1)6 (2)8 (3)9 (4) 124下列四个有6个结点的图 是连通图。(2)(1)(3)(4)5称图G=为图G = 的生成子图是指_.(1)V V (2)V V且E E(3)V= V且E E (4)V V且E E6有向图中结点之间的可达关系是_。(1) 自反的,对称的 (2) 自反的,传递的(3) 自反的,反对称的 (4) 反自反的,对称的7在下列关于图论的命题中,为真的命题是 。a) 完全二部图Kn, m (n 1, m 1)是欧拉图b) 欧拉图一定是哈密尔顿图c) 无向完全图Kn(n3)都是欧拉图d) 无向完全图Kn(n3)都是哈密尔顿图8下列各图为平面图的是。(4)(2)(3)(1) 9 设G为任意的连通的平面图,且G有n个顶点,m条边,r个面,则平面图的欧拉公式为 。(1)n m + r = 2(2)m n + r = 2(3)n + m r =2(4)r + n + m = 210 下列四个图中与其余三个图不同构的图是 。 (1) (2) (3) (4)四、解答题1给定边集:(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(8) 画出相应的无向图G(设G无孤立点);(9) 画出顶点子集V1 = 2, 3, 4, 5导出的导出子图;(10) 画出图G的一棵生成树。2如图所示带权图,用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。 3如图所示带权图,用避圈法(Kruskal算法)求一棵最小生成树并计算它的权值。 4求带权图G的最小生成树,并计算它的权值。 5给定权为2,6,3,9,4;构造一颗最优二叉树。6给定权为1,9,4,7,3;构造一颗最优二叉树。 7给定权为2,6,5,9,4,1;构造一颗最优二叉树。
展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 图纸专区 > 考试试卷


copyright@ 2023-2025  zhuangpeitu.com 装配图网版权所有   联系电话:18123376007

备案号:ICP2024067431-1 川公网安备51140202000466号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!