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

离散数学同步练习册 学号姓名专业教学中心华南理工大学二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；构造一颗最优二叉树。