离散数学试卷

1、.大学20132014学年度第二学期期末考试失散数学试卷A第一局部选择题共20分一、单项选择题本大题共10小题，每题只有一个正确答案，答对一题得2分共20分1A、B、和C，以下论断中正确的选项是：【】、对随意集合A.假定AB，BC，那么ACB.假定AB，BC，那么ACC.假定AB，BC，那么ACD.假定AB，BC，那么AC2、设A=a,a,以下式子中正确的有：【】A.a(A)B.a(A)C.a(A)D.以上都不是3、P：我将去镇上。Q：我有时间。命题“我将去镇上，当且仅当我有时间符号化为：【】A.PQB.QPC.PQD.Q?P4【】、命题公式：PPQQ是A矛盾式B.可知足式C.重言式D.不能够

2、确定、谓词公式x(P(x)yR(y)Q(x)中，量词x的辖域是：【】5xPxyRyA.)B.P(x)(C.P(x),Q(x)D.P(x)yR(y)6【】、在以下各图中，哪一个是欧拉图？7、设|V|1，G=【】是强连通图，当且仅当：AG中最罕有一条通路BG中最罕有一条回路CG中有经过每个结点最少一次的通路DG中有经过每个结点最少一次的回路8、设S,1,1,2，那么(S)有多少个元素？【】A3；B6；C7；D8；9、集合A=1，2，3，4，5，6，7，8，9，10上的关系R=|x+y=10，那么R的性质为：【】A自反的；B对称的；C传达的、对称的；D反自反的、传达的10R，其等价类集合aR|aA称

3、为：【】、集合A上的等价关系AA与R的并集，记作ARBA与R的交集，记作ARCA与R的商集，记作A/RDA与R的差集，记作A-R1/11二、填空题(本大题共10小题，每题2分,共20分)11、集合A=,，那么A的幂集为。12、序偶=，那么x=;y=。13、P、Q为两个命题，当且仅当时，PQ的真值为014、?PQ?P?Q可化简为：。15、设Mx1x12,x被2整除，xZ，Nx1x12,x被3整除，xZ那么MN=，MN=16、个体域为自然数集，Px：x为奇数，Qx：x为偶数，那么命题“不存在既是奇数又是偶数的自然数形式化为：。17、设R为非空集合A上的等价关系，其等价类记为xR。x,yA，假定x,

4、yR，那么xR与y的关系是_，而假定x,yR，那么xy=_。RRRn18K为汉米顿图，当且仅当。19，|B|=m，那么A到B的二元关系共有个，A上的二元关系共有个。设A、B为集合，|A|=n202，一个结点度数为3，三个结点度数为4，它有一棵树有两个结点度数为个度数为1的结点？三、计算题本大题共6小题，其中21、22、23三题每题5分，24、25、26三题每题7分，共36分21、某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有14人在两次考试都得优，那么两次考试中都没得优的学生有多少人？22、可否能够分别画出无向简单图，使各点的度与下面给出的序列一致。如可能，画出切

5、合条件的无向图，如不能能，说明原因。11，1，2，2，321，1，2，2，2.23xPx的真值。、给定个体域D=3，5，7，Px讲解为“x是素数，求公式()24、设集合A=1,2,3，A上关系R=|xAyAx+3y8,关系S=,。求DomR，RanR，RS，R，rR及sR求公式qp?q的析取式、合取式、主析取式，并依照主析取式直接确定公式的弄真指派和弄假指派。26、，3，6，12集合上的整除关系画出哈斯图，并对子集2，3，6找出最大元素，最小元素，对2极大元素，极小元素。四、证明题(3小题，每题5分，共15分。)27、证明：A(BC)=(AB)(AC)28、证明逻辑等价式xy(P(x)Q(y)

6、?xP(x)yQ(y)。方法不限五、应用题本大题共1小题，9分30、有七位客人列席，A只会讲英语；B会讲汉语；C会讲英语、意大利语及俄语；D会讲汉语及日语；3/11E会讲意大利语及德语；F会讲法语，日语及俄语；G会讲德语和法语。问主人可否把七位客人安排在一圆桌上，使每一位客人与左右邻不用翻译即可发言。假定能安排，请给出一个方案。大学2013至2014学年第第二学期期末考试失散数学试题A标第一局部选择题共20分一、单项选择题每题只有一个正确答案，答对一题得2分，共20分1、C2、A3、C4、B5、6、B7、D8、D9、B10、C第二局部非选择题共80分二、填空题(本大题共10小题，每题11、P(

7、A)=,1,1，2,12分，共,1，220分。)12、R13、P与Q的真值同样时14、合取或，出现一个15、M=，6，9，12，15，18，N=4，8，12，16，MN12,3N3，6，9，15，1816、x(P(x)Q(X)17、相等、18、n=3,且每一对极点度之和=n19、16、220、9三、简答题本大题共6小题，每题6分，共36分。21、真值表以下：pqrqrp(qr)?(p(qpr)p00001110010111010011101111111000001101000111000011111100.22、(1)不切合握手定理，因此不能够画出图2切合条件的无向图为：23、主析取式：(?P

8、?QR)(?PQR)(PQ?R)(PQR)或许主析取式=m1m3m6m7成真赋值为：001，011，110，111成假赋值为：000，010，100，10124、domR=A，Ran(R)=1,2,RS=，R-1=，r(R)=，sR=，25、不会打这三种球的人数为：X=10A、B、C为会打篮球、排球、网球的人的集合，那么有：|S|=30|A|=16,|B|=14,|C|=11,|AB|=10,|AC|=8,|BC|=8,|ABC|=5X=|S|-(|A|+|B|+|C|)+(|AB|+|AC|+|BC|)-|ABC|=1026、R=,依照R中元素，可知R是偏序关系，其哈斯图为：最大元：45，最

9、小元：1，极大元：45，极小元：1四、证明题(2小题，每题5分，共10分。)27、28、证明：x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)5/11五、综合应用题本题共2小题，每题7分，共14分29、解能安排，其方案为：H=A，C，B，E，D，G，F，A将每一个人作为一个项点，若是两个人会讲同一种语言，就在代表他们的二个项点间连一条边，边上注明二人公用的语言，这样即可得一简单无向图G。所求问题转变为图G中有无Hamilton回路问题。而上边指出的回路H正好是图G的一条Hamilton回路，因此问题获得解决。30、令p：他是计算机系本科生q：

10、他是计算机系研究生r：他学过DELPHI语言他学过C+语言他会编程序前提：(pq)(rs),(rs)t结论：pt证pP(附加前提)pqT附加规那么(pq)(rs)(前提引入)rsT假言推理规那么rT花间规那么rsT附加规那么(rs)t(前提引入)tT假言推理规那么.大学20132014学年度第二学期期末考试失散数学试卷A一、单项选择题本大题共10小题，每题只有一个正确答案，答对一题得2分共20分1、设P=x|(x+1)2Q=x|x2，那么以下各式中建立的是：【】4,+165xA.QPB.QPC.PQD.PQ2S,1,1,2,以下式子中正确的有：【】、A.1(S)B.1(S)C.1(S)D.以上

11、都不是3【】、P：你努力，Q：你失败。“诚然你努力了，但仍是失败了符号化为：A.PQB.QPC.PQD.P?Q4E=a,b，且P(a,a)=T，P(a,b)=F，P(b,a)=T，P(b,b)=F；那么在以下公式中真、设论域值为T的是：【】A$xyP(x,y)BxyP(x,y)CxP(x,x)Dx$yP(x,y)、谓词公式x(P(x)yR(y)Q(x)中，变元x是：【】5A自由出现B拘束出现C既是拘束出现，又是自由出现D以上都不是6G，若是它的所有结点的度数都是偶数，那么它拥有一条：【】、.一个连通的无向图A汉密尔顿回路B欧拉回路C汉密尔顿通路D初级回路7、设|V|1，G=【】是强连通图，当且

12、仅当：AG中最罕有一条通路BG中最罕有一条回路CG中有经过每个结点最少一次的通路DG中有经过每个结点最少一次的回路8、由5个结点组成的根树中，其边数m最多为：【】A2；B3；C5；D4；9、设A=1，2，3，A上二元关系S=，那么S拥有的性质是：【】A自反关系B传达关系C对称关系D反自反关系【】10A的一个差别，该差别就是：、集合A上的等价关系R，决定了AA与R的并集ARBA与R的交集，记作ARCA与R的商集，记作A/RDA与R的差集，记作A-R二、填空题(本大题共10小题，每题2分,共20分)11、集合A=1，1，2，那么A的幂集为。12、设P是所有人的集合，在P上定义关系R、S为R=|a，

13、bPa是b的父亲，S=|a，bPa是b的母亲，那么关系|a，bxa是b的祖母的表达式为.。7/1113?、P、Q为两个命题，当且仅当时，PQ的真值为114、n个命题变元的_称为极小项，其中每个变元与它的否定不能够同时出现，但两者必定_。15、设Mx1x18,x被3整除，xZ，Nx1x18,x被4整除，xZ那么M=，N=，MN=，MN=。16、个体域为自然数集，Px：x为奇数，Qx：x为素数，那么命题“存在既是奇数又是素数的自然数形式化为：。17、设R为非空集合A上的等价关系，其等价类记为xR。x,yA，假定x,yR，那么xR与y的关系是_，而假定x,yR，那么xy=_。RRR18Kn是个结点的

14、完好图，那么K5有_条边，每个结点的度数为_。19设S=1，2，那么S上能够定义个不同样的二元关系，其中有个是等价关系。20片树叶，3个3度极点，其余都是4度极点，那么该树有个4度极点。在一棵树中有7三、简答题本大题共6小题，每题6分，共36分四、21、结构命题公式(p(qr)p的真值表。22、可否能够分别画出无向简单图，使各点的度与下面给出的序列一致。如可能，画出切合条件的无向图，如不能能，说明原因。11，1，2，2，321，2，2，2，123、求公式PQ?PR的主析取式，并依照主析取式直接确定公式的成真赋值和成假赋值。24、设集合A=1,2,3，A上关系R=|xAyAx+3y8,关系S=,

15、。求.DomR，RanR，R。S，R-1，rR及sR25.某班有学生30人，其中16人会打篮球，14人会打排球，10人会打篮球和排球，8人会打篮球和网球，还有5人会打这三种球，而11个会打网球的人都会打两外一种球指篮球或排球，求不会打这三种球的人数。26、设A1，3，5，9，15，45，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。四、证明题(2小题，每题5分，共10分。)27、设A,B,C是随意四个集合，证明:ABC=(AB)(AC)28、证明：x(A(x)B(x)xA(x)xB(x)五、综合应用题本题共2小题，每题7分，共14分29b会讲英语和语；c会讲英语、今

16、有a，b，c，d，e，f，g共7人，以下事实：a会讲汉语和英语；和意大利语；d会讲法语、俄语和意大利语；e会讲俄语和语；f会讲汉语；g会讲法语和汉语。试问这7个人应怎样排座位圆桌，才能使每一个人和他身边的人发言?。30、若是他是计算机系本科生或许是计算机系研究生，那么他必然学过DELPHI语言而且学过C+语言。只需他学过DELPHI语言或许C+语言，那么他就会编程序。因此若是他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，结构该推理的证明。大学2013至2014学年第一学期期末考试失散数学试题A标准答案及评分标准9/11第一局部选择题共20分一、单项选择题每题只有一个正确答案，答对

17、一题得2分，共20分1、A2、A3、C4、C5、D6、B7、D8、D9、B10、C第二局部非选择题共80分二、填空题(本大题共10小题，每题2分，共20分。)11、P(A)=,12、x=11,y=413、P为真，Q为假p=1，q=014、?P15、MN6,12,MN2,4,8,1016、?x(P(x)Q(X)17、相等等价、18、n=3,且每一对极点度之和=n19、2nmn2、220、9三、简答题本大题有4个小题,每题5分，共20分。21、|s|-|AB|=50-(26+21-14)=17人22、(1)不切合握手定理，因此不能够画出图2切合条件的无向图为：23、xP(x)=P3P5P7=111

18、=1为真24、domR=A，RS=，R=，r(R)=，sR=，25、析取式：pq，合取式：qp?q；主析取式：pq弄真指派：1,1，弄假指派：0,0，0,1，1,026、哈斯图为：12最大元：6极大元：66最小元：没有极小元：2，323.四、证明题(3小题，每题5分，共15分。)27、对任一x，xA(BUC)xAx(BUC)xA(xBUC)xA(xBxC)xA(xBxC)xA(xBxC)(xAxB)(xAxC)xABxACx(AB)I(AC)因此：A-(BC)=(A-B)(A-C)28、xy(P(x)Q(y)?xP(x)yQ(y)因为Px中不含y，因此y能够移入Q前?xP(x)yQ(y)因为Qy中不含