2007-2008离散数学测验.doc

广东商学院期中考试2007-2008学年第一学期课程：离散数学 代码：110094 考试班级：2006计机1、2班、软件1班一、判断题（共16分，每小题2分）1、（ F ）已知两个集合A=，B=，则AB=。2、（ F ）已知集合A有10个元素，则在集合A上可定义210个互不相同的二元关系。3、（ F ）设集合A=a，b，c，B=x，y，z，e，R是A到B的二元关系，若R=（a，x），（b，y），（c，z），则R的逆关系是B到A的函数。4、（ T ）若R1和R2都是集合A的相容关系，则R1R2也是A上的相容关系。5、（ F ）R是集合A上的反自反二元关系，则R的传递闭包也是反自反关系。？6、（ T ）若R是A上的二元关系，IA是A上的恒等关系，则当且仅当IAR时，R是A上的自反关系。7、（ F ）设I是整数集合，N是自然数集合，f是I到N的函数，且对任意的整数xI都有f（x）=x3，则f是I到N的双射函数。8、（ F ）如果一个命题公式可以等价地表示为A1A2A3、An。其中A1、A2、A3、An都是由命题变元（或其否定）所组成的析取式，则称这种表示形式为析取范式。二、选择题（共14分，每小题2分）1、（ A ）设A，B是集合，如果A=F，B=F，a，F，则： A、AB且AB B、AB但AB C、AB但AB D、AB且AB2、（ F ）设集合A=a，b，c，R是A上的二元关系，R=（a，a），（a，b），（a，c），（c，a），那么R是： A、自反的； C、反自反的； E、反对称的； B、对称的； D、可传递的； F、不可传递的。3、（ D）若集合A=2，3，4，5，6，8，10，12，24，R是A上的整除关系，那么子集3，4，6的上确界是： A、6； B、8； C、10； D、12； E、244、（ D ）下面哪个叙述是错误的：A、若R、S均是非空集合A上的自反关系，则RS也是A上的自反关系。B、若R、S均是非空集合A上的反自反关系，则RS也是A上的反自反关系。C、若R、S均是非空集合A上的对称关系，则R-S也是A上的对称关系。D、若R、S均是非空集合A上的反对称关系，则RS也是A上的反对称关系。5、（ C ）下列二元关系中，哪个能构成函数？ A、集合A=1，2，3，B=4，5，6，当aA，bB，且ab时，(a,b) f。 B、设N是自然数集，f是N到N的二元关系，若a，bN，当a+b=10时，（a，b）f。 C、集合A=2，3，5，B=0，1，对于aA，当a为素数时，（a,0）f。 D、设集合A=x，y，z，B=1，2，3，f是A到B的二元关系，并且f=（x，3），（y，2），（z，3），（y，3）。6、（ C）设P：我很累，Q：我去打篮球，R：我去看电影。则“如果我不累，我就去打篮球；但我很累，所以我去看电影。”可符号化为： A、（PQ）（PR）； C、（PQ）（PR）； B、（PQ）（PR）； D、（PQ）（PR）；7、（ B ）设A（x）：x是大学生，B（x）：x学习勤奋。那么“有些大学生学习不勤奋”可符号化为： A、（x）（A（x）B（x）； C、（彐x）（A（x）B（x）； B、（彐x）（A（x）B（x）； C、（彐x）（A（x）B（x）。三、证明题（共40分，每小题10分）1、 对于任意集合A、B，求证P(A)P(B)=P(AB) 证明：（1）先证： P(A)P(B) P(AB)任取x P(A)P(B)，则x P(A)且xP(B)，即xA且xB 所以xAB。因此 x P(A)P(B)。由子集合的定义知：P(A)P(B) P(AB)（2）再证：P(AB) P(A)P(B)任取x P(AB)，则x AB，即xA且xB 所以x P(A)且xP(B)。因此 x P(A)P(B)。由子集合的定义知：P(AB) P(A)P(B) 综合上面（1）、（2）知：求证P(A)P(B)=P(AB)。证毕。2、若R是有限集合A上的反自反关系和可传递关系，求证R是集合A上的反对称关系。证明：（反证法）假设R不是集合A上的反对称关系。则必存在a、bA，使得（a，b）R且（b，a）R。因R是集合A上的可传递关系，所以有：（a，a）R。而这与已知R是A上的反自反关系矛盾。这说明假设错误，则原命题成立。?3、试用PT规则证明 (PQ) (PR) (QS) RS。?4、证明（彐x）(A（x）B（x）) （x）A（x）（彐x）B（x）四、综合题（共30分，每小题10分）1、 70名学生参加体育比赛，短跑得奖者36人，跳高得奖者29人，投掷得奖者36人，三项都得奖者6人，仅得2项奖者有24人，问一项奖都没有得到的人数有几人？2、设R1、R2是集合A上的两个二元关系，判断下列命题是否正确。若正确，请给出证明；若不正确，请给出例子。 （1）若R1和R2是自反的，则R1R2也是自反的； （2）若R1和R2是对称的，则R1R2也是对称的； （3）若R1和R2是反对称的，则R1R2也是反对称的；解：（1）正确，证明略。（2）正确，证明略。 （3）不正确。如：R1=（a，b），（c，b），R2=（b，c），（b，a）。 但是：R1R2=（a，c），（a，a），（c，c），（c，a）是对称的。3、求 (PQ)（PR）的主析取范式和主合取范式。(课本例题)广东商学院期中考试 参考答案2007-2008学年第一学期课程：离散数学 代码：110094 考试班级：2006计机1、2班、软件1班一、判断答案：4、6对，其他错。二、选择答案：1-A，2-F，3-D，4-D，5-C，6-C，7-B三、证明1、对于任意集合A、B，求证P(A)P(B)=P(AB) 证明：（1）先证： P(A)P(B) P(AB)任取x P(A)P(B)，则x P(A)且xP(B)，即xA且xB 所以xAB。因此 x P(A)P(B)。由子集合的定义知：P(A)P(B) P(AB)（2）再证：P(AB) P(A)P(B)任取x P(AB)，则x AB，即xA且xB 所以x P(A)且xP(B)。因此 x P(A)P(B)。由子集合的定义知：P(AB) P(A)P(B) 综合上面（1）、（2）知：求证P(A)P(B)=P(AB)。证毕。2、若R是有限集合A上的反自反关系和可传递关系，求证R是集合A上的反对称关系。证明：（反证法）假设R不是集合A上的反对称关系。则必存在a、bA，使得（a，b）R且（b，a）R。因R是集合A上的可传递关系，所以有：（a，a）R。而这与已知R是A上的反自反关系矛盾。这说明假设错误，则原命题成立。3、试用PT规则证明(PQ) (PR) (QS)永真蕴含RS。（课本例题）4、证明（彐x）(A（x）B（x）) （V x）A（x）（彐x）B（x）（课本例题）四、综合1、70名学生参加体育比赛，短跑得奖者36人，跳高得奖者29人，投掷得奖者36人，三项都得奖者6人，仅得2项奖者有24人，问一项奖都没有得到的人数有几人？解：（）设是短跑得奖者集合，是跳高得奖者集合，是投掷得奖者集合。 由题意得：|A|=36, |B|=29, |C|=36, | ABC|=6, | AB|+| AC|+| BC|-3| ABC|=24. 因此| AB|+| AC|+| BC|(2) 由包含排斥原理得：|BC|=(|A|+|B|+|C|)(|AB|+|AC|+|BC|)+|ABC|=36+29+36-42+665(3) 因此一项奖都没有得到的人数为70-65=5人2、设R1、R2是集合A上的两个二元关系，判断下列命题是否正确。若正确，请给出证明；若不正确，请给出例子。 （1）若R1和R2是自反的，则R1R2也是自反的； （2）若R1和R2是对称的，则R1R2也是对称的； （3）若R1和R2是反对称的，则R1R2也是反对称的；解：（1）正确，证明略。（2）正确，证明略。 （3）不正确。如：R1=（a，b），（c，b），R2=（b，c），（b，a）。 但是：R1R2=（a，c），（a，a），（c，c），（c，a）是对称的。3、求 (PQ)（PR）的主析取范式和主合取范式。解：（真值表法）先写出真值表（略），易得：主析取范式为：（PQR）（PQR）（PQR）（PQR）主合取范式为：（PQR）（PQR）（PQR）（PQR）广 东 商 学 院 试 题 纸2007-2008学年第一学期期终试题课程：离散数学（A卷） 班级 2006计机、软件、信科（6个班） 共3页【答题说明】：“全部答案”均应写在“答题纸”上，写在试卷上无效。一、判断题（共10分，每小题1分）（正确的打“”，错误的打“”）1、已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。2、已知集合A有4个元素，所以在集合A上一共可定义24个互不相同的二元关系。3、设集合A=a，b，c，B=x，y，z，w，R是A到B的二元关系，若R=（a，x），（b，y），（c，z），则R的逆关系是B到A的函数。4、（G，*）是代数系统，运算*对G是封闭和可结合的，且G中存在幺元，称（G，*）为群。5、若（G，*）是10阶群，则（G，*）必有2阶子群。6、一个无向连通图是半欧拉图的充要条件是图中至少有两个奇度点。7、已知图G是一个由n个顶点、m条边构成的无向连通平面图，则3n-6m。8、若无向简单图G（V1，V2）是完全二部图，则它不一定是无向简单完全图。9、设S是一命题公式，若S可以逻辑等价地写成A1A2An,其中Ai均为由命题公式S的命题变元或其否定构成的析取式，则称A1A2An为S的析取范式。10、在谓词逻辑中，一般地，全称量词的特性谓词常作蕴含的前件；存在量词的特性谓词常作合取项。二、填空题（共10分，每小题2分）1、设A为有限集合，则A=（ ）。2、群（N5-0，*）中，若*为模5乘法运算，则元素2的阶数是（ ）。3、设图G是完全二元树，且有t片叶子，那么它有（ ）条边。4、树T有2个2度点，3个3度点，4个4度点，无大于4度的点。则这棵树有（ ）个1度点。5、设P表示“天下雪”；Q表示“我去看电影”；R表示“我在家复习功课”。则“如果天不下雪，那么我去看电影，否则我在家复习功课”可符号化为：（ ）。三、选择题（共20分，每小题2分）。1、（ ）设A，B是集合，如果A=F，B=F，a，F，则： A、AB且AB； B、AB但AB； C、AB但AB； D、AB且AB2、（ ）设A=a，b，c，A上的二元关系R=（a，a），（a，b），（a，c），则R是： A、自反的； B、反自反的； C、对称的； D、反对称的。3、（ ）集合A=3，4，5，6，8，10，12，24，R是A上的整除关系，则子集3，4，6的上确界是： A、6； B、8； C、10； D、12。4、（ ）下列二元关系中，哪个能构成函数？ A、集合A=1，2，3，B=4，5，6，当aA，bB，且ab时，(a,b) f。 B、设N是自然数集，f是N到N的二元关系，若a，bN，当a+b=10时，（a,b）f。 C、集合A=2，3，5，B=0，1，对于aA，当a为素数时，（a,0）f。 D、设A=x，y，z，B=1，2，A到B的二元关系f=（x，1），（x，2），（z，2）。5、（ ）完全二元树中的内点数比叶子数： A、相等； B、多1； C、少1； D、不确定6、（ ）设P：我很累，Q：我去打篮球，R：我去看电影。则“如果我不累，我就去打篮球；但我很累，所以我去看电影。”可符号化为： A、（PQ）（PR）； C、（PQ）（PR）；B、（PQ）（PR）； D、（PQ）（PR）7、（ ）设A（x）：x是大学生，B（x）：x学习勤奋。“有些大学生学习不勤奋”符号化为： A、（x）（A（x）B（x）； C、（彐x）（A（x）B（x）； B、（彐x）（A（x）B（x）； D、（彐x）（A（x）B（x）。8、（ ）（A，*）是有限半群，则（A，*）必有：A、等幂元；B、幺元；C、零元；D、逆元9、（ ）（A，*）是代数系统，A是非空集合，如果（A，*）为半群，则运算*对A满足： A、封闭、可结合； B、封闭、可交换； C、封闭、可交换； D、封闭、可结合、可交换10、（ ）群（N11-0，11）中元素3的阶为： A、11； B、3； C、5； D、10。四、证明题（共30分，每小题6分）1、已知R是集合A上的偏序关系，B是A的子集合，试证明R（BB）是B上的偏序关系。2、证明群（G，*）中不存在零元，其中|G|2。3、证明：n（n为奇数）阶图G中奇次度顶点的个数与其补图中奇次度顶点的个数相等。4、设G 是具有6个顶点、13条边的简单无向连通图，证明G是哈密顿图但不是平面图。5、试用PT规则证明(PQ) (PR) (QS)永真蕴含RS。五、综合题（共30分，每小题6分）1、70名学生参加体育比赛，100米得奖者36人，跳高得奖者29人，掷铅球得奖者36人，三项都得奖者6人，仅得2项奖者有24人，问一项奖都没有得到的学生有几人？2、求群（N12，12）的所有子群。（其中12为“模12加法运算”）3、某城市拟在六个区之间架设有线电视网，其网点间距离如下面有权图矩阵给出（如a32=4，表示a3到a2有一条长为4的电视线）。试给出架设线路的最优方案，请画出图，并计算出线路的长度。 4、问有6个顶点的不同构的无向树有几种？试画出这些无向树。5、设A、B、C为任意命题公式，试判断以下说法是否正确。若不正确，请给出反例；若正确，请说明理由。 （1）若AC逻辑等价于BC，则A与B逻辑等价。 （2）若AC逻辑等价于BC，则A与B逻辑等价。广 东 商 学 院 试 题 纸2007-2008学年第一学期期终试题课程：离散数学（B卷） 班级 2006计机、软件、信科（6个班） 共3页【答题说明】：“全部答案”均应写在“答题纸”上，写在试卷上无效。一、判断题（共10分，每小题1分）（正确的打“”，错误的打“”）1、已知两个集合A=，B=，则AB=。2、若R1和R2都是集合A上的相容关系，则R1R2也是A上的相容关系。3、设I是整数集合，N是自然数集合，f是I到N的函数，且对任意的整数xI都有f（x）=x3，则f是I到N的双射函数。4、含有幺元的半群叫独异点，每个元素都有逆元的独异点称为群。5、若（G，*）为群，则在其运算表中每一行（列）元素都互不相同。6、在有向树T中，如果某内点有n个儿子，则称T为完全n元树。7、在一棵无向树中任意增加一个2度点，则叶子数也相应地增加2个。8、设T是具有n片叶子的完全二元树，则树T共有2n+1个顶点。9、已知命题公式A在其变元的各种可能的指派下共有5种情况取F值、3种情况取T值，则A的主析取范式中必有5个合取项，主合取范式中必有3个析取项。10、设P（X）：X是素数，Q（X）：X是偶数。“有些素数是偶数”符号化为：（彐X）（P（X）Q（X）二、填空题（共10分，每小题2分）1、设集合A=1，2，3，4，那么在集合A上一共可定义（ ）种互不相同的对称关系。2、当（A，*）为（ ）（注：可填“半群、独异点、群、子群”其中之一）时，若a、bA，有a*b=a（或b*a=a），则（A，*）的幺元是a。3、具有n个顶点的无向树，各顶点的度数和为（ ）。4、一棵具有n个顶点的二元树，它的最大高度是（ ）。5、用谓词合式表示命题：如果两数的乘积为零，则其中至少有一个数为零。其中：P（x，y）表示“x与y的乘积为零”，A（x）表示“x为零”，B（y）表示“y为零”，则符号化的谓词合式为（ ）。三、选择题（共20分，每小题2分）1、设A，B是集合，如果A=F，B=F，a，F，则： A、AB且AB B、AB但AB C、AB但AB D、AB且AB2、设R是A=a，b，c上的二元关系，R=（a, a）,（a, b）,（a, c）,（c, a），则R是： A、可传递的；B、反对称的；C、对称的；D、自反的；E、反自反的。3、若A=2，3，4，5，6，8，10，12，24，R是A上的整除关系，则R是集合A上的： A、相容关系； B、等价关系； C、偏序关系； D、不确定。4、下列二元关系中，哪个能构成函数？ A、集合A=1，2，3，B=4，5，6，当aA，bB，且ab时，(a,b) f。 B、N是自然数集，f是N到N的二元关系，若a，bN，当a+b=10时，（a，b）f。 C、集合A=2，3，5，B=0，1，对于aA，当a为素数时，（a，0）f。 D、设A=x，y，B=1，2，f是A到B的二元关系，并且f=（x，1），（x，2）。5、完全二元树的顶点有： A、偶数个； B、奇数个； C、2个； D、不确定。6、若T是一棵有10个顶点的无向树，由这棵无向树可以生成多少个不同的有向图？ A、20； B、29； C、210； D、215。7、设P：我很累，Q：我去打篮球，R：我去看电影。则“如果我不累，我就去打篮球；但我很累，所以我去看电影。”可符号