离散数学同步练习.doc

《离散数学同步练习.doc》由会员分享，可在线阅读，更多相关《离散数学同步练习.doc（27页珍藏版）》请在三一文库上搜索。

1、华南理工大学网络教育学院离散数学练习题第一章命题逻辑一填空题（1）设：p：派小王去开会。q：派小李去开会。则命题：“派小王或小李中的一人去开会” 可符号化为： 。（2）设A，B都是命题公式，AB，则AB的真值是 。（3）设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：“刘平不但不聪明，而且不用功” 可符号化为： 。（4）设A , B 代表任意的命题公式，则等价式A B 。（5）设，p：径一事；q：长一智。在命题逻辑中，命题：“不径一事，不长一智。” 可符号化为： 。（6）设A , B 代表任意的命题公式，则德 摩根律为（A B） 。（7）设，p：选小王当班长；q：选小李当班长。则命题：“选

2、小王或小李中的一人当班长。” 可符号化为： 。（8）设，P：他聪明；Q：他用功。在命题逻辑中，命题：“他既聪明又用功。” 可符号化为： 。（9）对于命题公式A，B，当且仅当 是重言式时，称“A蕴含B”，并记为AB。（10）设：P：我们划船。Q：我们跑步。在命题逻辑中，命题：“我们不能既划船又跑步。” 可符号化为： 。（11）设P , Q 是命题公式，德摩根律为：（P Q） 。（12）设 P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。” 可符号化为： 。（13）设 p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑

3、冠军。” 可符号化为： 。（4）设A，C为两个命题公式，当且仅当 为一重言式时，称C可由A逻辑地推出。二判断题1. 设A，B是命题公式，则等价式ABAB。 （ ）2. 命题公式pqr是析取范式。 （ ）3. 陈述句“x + y 5” 是命题。 （ ）4. 110 (p=1,q=1, r=0)是命题公式 (pq)r)q 的成真赋值。 （ ）5. 命题公式 p(pq) 是重言式。 （ ）6. 设A，B都是合式公式，则ABB也是合式公式。 （ ）7. A(BC)( AB)(AC)。 （ ）8. 陈述句“我学英语，或者我学法语” 是命题。 （ ）9. 命题“如果雪是黑的，那么太阳从西方出”是假命题。

4、（ ）10. “请不要随地吐痰！” 是命题。 （ ）11. P Q P Q 。 （ ）12. 陈述句“如果天下雨，那么我在家看电视” 是命题。 （ ）13. 命题公式（PQ）（RT）是析取范式。 （ ）14. 命题公式 (PQ) R (PQ) 是析取范式。 （ ）三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。1 设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。”可符号化为 。 （1）PQ （2）Q P （3） Q P （4）Q P2 (1 ) 明年国庆节是晴天。(2 ) 在实数范围内，x+y3。 (3 ) 请回答这个问题！(4 ) 明天

5、下午有课吗？在上面句子中，是命题的只有 。3 命题公式A与B是等值的，是指 。（1） A与B有相同的命题变元（2） AB是可满足式（3） AB为重言式（4） AB为重言式4 (1 ) 雪是黑色的。(2 ) 这朵花多好看呀！。 (3 ) 请回答这个问题！(4 ) 明天下午有会吗？在上面句子中，是命题的是 。5 设：P：天下大雨。Q：他乘公共汽车上班。则命题“只要天下大雨，他就乘公共汽车上班。”可符号化为 。 （1）QP （2）P Q （3） Q P （4）Q P6 设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。”在命题逻辑中可符号化为 。 （1）QP （2）P Q （3） P Q

6、 （4）Q P7 (1 ) 现在开会吗？(2 ) 在实数范围内，x+y 5。 (3 ) 这朵花多好看呀！(4 ) 离散数学是计算机科学专业的一门必修课。在上面语句中，是命题的只有 。8 设：P：天气好。Q：他去郊游。则命题“如果天气好，他就去郊游。”可符号化为 （1）PQ （2）Q P （3） Q P （4）Q P9 下列式子是合式公式的是 。（1）（P Q） （2） （P （Q R）（3）（P Q） （4） Q R10 （1）1101110 （2） 中国人民是伟大的。 （3） 全体起立！ （4） 计算机机房有空位吗？在上面句子中，是命题的是 。11 设：P：他聪明；Q：他用功。则命题“他虽聪

7、明但不用功。”在命题逻辑中可符号化为 。 （1）P Q （2）P Q （3）P Q （4）P Q12 (1 ) 如果天气好，那么我去散步。 (2 ) 天气多好呀！ (3 ) x=3。 (4 ) 明天下午有会吗？在上面句子中 是命题。13 设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为 。 （1）P Q （2）P Q （3）P Q （4）P Q四、解答题1设命题公式为（pq）（qp）。 （1）求此命题公式的真值表；（2）给出它的析取范式；2设命题公式为（p q）（p r）。 （1）求此命题公式的真值表；（2）给出它的析取范式；3设命题公式为 Q

8、（P Q） P。 （1）求此命题公式的真值表；（2）求此命题公式的析取范式；4完成下列问题 （1）求此命题公式 Q （P Q） P 的真值表；（2）求命题公式（P（QR）S的析取范式。5设命题公式为（P （P Q） Q。（1）求此命题公式的真值表；（2）判断该公式的类型。6设命题公式为（P Q）P） Q。 （1）求此命题公式的真值表；（2）给出它的析取范式；7用直接证法证明 前提：P Q，P R，Q S结论：S R8用直接证法证明 前提：P (Q R)，S Q，P，S。结论：R第二章谓词逻辑一填空题（1）若个体域是含三个元素的有限域a，b，c，则$xA(x) （2）取全总个体域，令F(x)：x

9、为人,G(x)：x爱看电影。则命题“没有不爱看电影的人。”可符号化为_。（3）若个体域是含三个元素的有限域a，b，c，则xA(x) 。（4）取全总个体域，令M(x)：x是人,G(y)：y是花, H(x,y)：x喜欢y。则命题“有些人喜欢所有的花。”可符号化为_。（5）取个体域为全体人的集合。令F(x)：x在广州工作,G(x)：x是广州人。在谓词逻辑中，命题“在广州工作的人未必都是广州人。”可符号化为_。（6）P(x)：x是学生，Q(x)：x要参加考试。在谓词逻辑中，命题：“每个学生都要参加考试” 可符号化为： 。（7）M(x)：x是人，B(x)：x勇敢。则命题“有人勇敢，但不是所有的人都勇敢”

10、谓词符号化为 _。（8）P(x)：x是人，M(x)：x聪明。则命题“尽管有人聪明，但不是一切人都聪明”谓词符号化为 _。（9）I(x)：x是实数，R(x)：x是正数，N(x)：x是负数。在谓词逻辑中，命题：“任何实数或是正的或是负的” 可符号化为： 。（10）令M(x)：x是大学生,P(y)：y是运动员, H(x, y)：x钦佩y。则命题“有些大学生不钦佩所有运动员。”可符号化为_ _。二判断题1. 设A，B都是谓词公式，则x AB也是谓词公式。 （ ）2. 设c是个体域中某个元素，A是谓词公式，则A(c) xA(x)。 （ ）3. xyA(x,y) yxA(x,y) 。 （ ）4. x$yA

11、(x,y) $yxA(x,y) 。 （ ）5. 取个体域为整数集，则谓词公式xy(x y = y ) 是假命题。 （ ）6. (x)（P(x)Q(x)） (x)（P(x) Q(x)）。 （ ）7. 命题公式 (PQ R) (PQ) 是析取范式。 （ ）8. 谓词公式(x)(A (x) B(x, y) R(x) 的自由变元为x, y。 （ ）9. （x）A（x） B）（$x）（A（x） B）。 （ ）10. R(x)：“x是大学生。” 是命题。 （ ）三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。1设F（x）：x是火车，G（x）：x是汽车，H（x，y）：x

12、比y快。命题“某些汽车比所有火车慢”的符号化公式是 。（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设个体域为整数集，下列真值为真的公式是 。（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早晨吃面包。命题“有些人早晨吃面包”在谓词逻辑中的符号化公式是 。（1） （x）（F（x） G（x）（2） （x）（F（x） G（x）（3） （$x）（F（x） G（x）

13、（4） （$ x）（F（x） G（x）5下列式子中正确的是 。（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下面谓词公式是永真式的是。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。命题“所有运动员都钦佩一些教练员”的符号化公式是 。a) x（S（x） y（J（y） L（x，y）b) x $y（S（x）（J（y） L（x，y）c) x（S（x）

14、 $y（J（y） L（x，y）d) $yx（S（x）（J（y） L（x，y）6 下列式子是合式公式的是 。（1）（P Q） （2） （P （Q R）（3）（P Q） （4） Q R7 下列式子中正确的是 。（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在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人

15、不喜欢骑自行车。因而有的人不喜欢步行。令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。3在命题逻辑中构造下面推理的证明： 如果他是理科学生，他必须学好数学。如果他不是文科学生，他必是理科学生。他没学好数学，所以他是文科学生。4用直接证法证明：前提：（x）（C（x） W（x）R（x），（$x）（C（x）Q（x）结论：（$x）（Q（x）R（x）。第三章集合与关系一填空题（1）如果|A|n，那么|AA|n2。A上的二元关系有_个。（2）集合A上关系R的自反闭包r（R）=_。（3）设集合A上的关系R和S，R=（1，2），（1，3），（3，2），S=（1, 3），（2，1），（

16、3，2），则SR= 。（4）如果|A|n，那么|P(A)|2n。（5）设集合A上的关系R和S，R=，S=，则RS= 。（6）设集合E=a, b, c，E的幂集P(E) _。（7）设R是定义在集合X上的二元关系，如果对于任意x, yX， _ _ _ ，则称集合X上的关系R是对称的。（8）设关系R和S为，R=，S=，则RS =_ _ _ _。（9）设R是定义在集合X上的二元关系，如果对于每个x X， _ _ _ ，则称集合X上的关系R是自反的。二判断题1设S，T是任意集合，如果S -T = ，则S = T。 （ ）2集合A=1,2,3,4上的关系,是一个函数。 （ ）3集合A=1，2，3，4上的整

17、除关系是等价关系。 （ ）4集合A 的幂集P(A)上的包含关系是偏序关系。 （ ）5设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集

18、合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上

19、的关系是偏序关系的是 。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）

20、 自反的，反对称的和传递的 （4）对称的，反对称的和传递的8设S，T，M为任意集合，下列命题正确的是 。a) 如果ST = SM，则T = Mb) 如果S-T = F，则S = Tc) S-T Sd) S S = S9设A=1，2，3，4，5，B=a，b，c，d，e，以下哪个函数是从A到B的入射函数 。e) F =，f) F=，g) F =，h) 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是

21、集合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是

22、非空集合。*是S上的一个二元运算，如果 ，则称代数系统S, * 为广群。二判断题1含有零元的半群称为独异点。 （ ）2运算“”是整数集I上的普通加法，则群的么元是1。 （ ）三、填空题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。1 下列群一定为循环群的是。i) （运算“”是整数集I上的普通加法）j) （R是实数集，“”是普通乘法）k) （运算“”是有理数集Q上的普通加法）l) （P（S）是集合S的幂集，“”为对称差）2运算“”是整数集I上的普通减法，则代数系统 满足下列 性质 。（1）结合律 （2）交换律 （3）有零元 （4） 封闭性3设I是整数集，N是自然数集

23、，P（S）是S的幂集，“，”是普通的乘法，加法和集合的交运算。下面代数系统中 是群。 （1） （2） （3） （4）4下列代数系统不是群的是。（5） （运算“”是整数集I上的普通加法）（6） （P（S）是集合S的幂集，“”为交运算）（7） （运算“”是有理数集Q上的普通加法） （P（S）是集合S的幂集，“”为对称差）第七章图论一填空题（1）任何图(无向)中，度为奇数的顶点个数为。（2）设D是一个有向图，若D中任意一对顶点都是相互可达的，则称D是_。（3）既不含平行边，也不含环的图称为 。（4）经过图中 一次且仅一次并且行遍图中每个顶点的回路，称为欧拉回路。（5）一棵有n个顶点的树含有_边。（6

24、）设G =（V，E），G =（V，E）是两个图，若 且 ，称G是G的生成子图。 （7）经过图中 一次且仅一次的回路，称为哈密尔顿回路。二判断题15个顶点的有向完全图有20条边。 （ ）2. 已知n (n2)阶无向简单图G有n 1条边，则G一定为树。 （ ）3. n阶无向完全图Kn的每个顶点的度都是n。 （ ）4任何图都有一棵生成树。 （ ）5连通无向图的哈密尔顿回路经过图中的每条边一次且仅一次。 （ ）6任一图G=（V，E）的顶点的最大度数必小于G的顶点数。 （ ）7欧拉图一定是汉密尔顿图。 （ ）8无向连通图G的任意两结点之间都存在一条路。 （ ）9根树中除一个结点外，其余结点的入度为1。

25、（ ）三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的 内。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）

26、 反自反的，对称的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），（

27、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；构造一颗最优二叉树，并求此最优二叉树的权。