离散数学试题一（A 卷答案）一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。
二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。
关于谁参加竞赛，下列4种判断都是正确的： (1)甲和乙只有一人参加；(2)丙参加，丁必参加；(3)乙或丁至多参加一人；(4)丁不参加，甲也不会参加。
请推出哪两个人参加了围棋比赛。
三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。
(1)x (P (x )Q (x )) P (2)P (y )Q (y ) T (1)，US(3)xP (x ) P(4)P (y ) T (3)，ES(5)Q (y ) T (2)(4)，I(6)xQ (x ) T (5)，EG四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、五、（15分）设函数g ：A →B ，f ：B →C ，(1)若f o g 是满射，则f 是满射。
(2)若f o g 是单射，则g 是单射。
六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得<a ，b >T <a ，b >R 且<b ，a >R ，证明T 是一个等价关系。
七、（15分）若<G ，*>是群，H 是G 的非空子集，则<H ，*>是<G ，*>的子群对任意的a 、b ∈H 有a *b －1∈H 。
八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。
(2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗离散数学试题一（B 卷答案）一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。
设F 表示灯亮。
u vw(1)写出F在全功能联结词组{}中的命题公式。
(2)写出F的主析取范式与主合取范式。
二、（10分）判断下列公式是否是永真式(1)(xA(x)xB(x))x(A(x)B(x))。
(2)(xA(x)xB(x))x(A(x)B(x)))。
三、（15分）设X为集合，A＝P(X)－{}－{X}且A≠，若|X|＝n，问(1)偏序集<A，>是否有最大元(2)偏序集<A，>是否有最小元(3)偏序集<A，>中极大元和极小元的一般形式是什么并说明理由。
四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明设<G，*>是一个有幺元且满足消去律的有限半群，要证<G，*>是群，只需证明G的任一元素a可逆。
考虑a，a2，…，a k，…。
因为G只有有限个元素，所以存在k＞l，使得a k＝a l。
令m＝k－l，有a l*e ＝a l*a m，其中e是幺元。
由消去率得a m＝e。
于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*a m-1＝a m-1*a＝e。
从而a是可逆的，其逆元是a m-1。
总之，a是可逆的。
七、（20分）有向图G如图所示，试求：(1)求G的邻接矩阵A。
(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少(3)求出A T A和AA T，说明A T A和AA T中的第(2，2)元素和第(2，3)元素的意义。
(4)求出可达矩阵P。
(5)求出强分图。
离散数学试题二（A卷答案）一、（10分）判断下列公式的类型（永真式、永假式、可满足式）1)((P Q)∧Q)((Q∨R)∧Q) 2)((Q P)∨P)∧(P∨R)3)((P∨Q)R)((P∧Q)∨R)二、（8分）个体域为{1，2}，求x y（x+y=4）的真值。
三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少A到B的函数数是多少四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。
若每样乘坐一次的费用是元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C B×D且<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。
证明h是双射。
八、（12分）<G,*>是个群，u∈G，定义G中的运算“”为a b=a*u-1*b，对任意a,b∈G，求证：<G, >也是个群。
九、（10分）已知：D=<V,E>，V={1,2,3,4,5}，E={<1,2>,<1,4>,<2,3>,<3,4>,<3,5>,<5,1>}，求D的邻接距阵A和可达距阵P。
离散数学试题二（B卷答案）一、（10分）求命题公式(P∧Q)(P R)的主合取范式。
解：(P∧Q)(P R)（(P∧Q)(P R)）∧（(P R)(P∧Q)）（(P∧Q)∨(P∧R)）∧（(P∨R)∨(P∨Q)）(P∧Q)∨(P∧R)(P∨R)∧（Q∨P）∧（Q∨R）(P∨Q∨R)∧(P∨Q∨R)∧（P∨Q∨R）∧（P∨Q∨R）M1∧M3∧M4∧M5二、（8分）叙述并证明苏格拉底三段论三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。
五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{<a，b>，<b，a>，<b，c>，<c，d>}，求r(R)、s(R)和t(R)。
六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C B×D且<a,c>∈A×C，h(<a,c>)＝<f(a),g(c)>。
证明h是双射。
七、(12分)设<G，*>是群，H是G的非空子集，证明<H，*>是<G，*>的子群的充要条件是若a，b H，则有a*b-1H。
八、（10分）设G=<V，E>是简单的无向平面图，证明G至少有一个结点的度数小于等于5。
九.G=<A,*>,A={a,b,c},*的运算表为：(写过程，7分)（1）G是否为阿贝尔群（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元离散数学试题三(A卷答案）一、证明题（10分）1) (P∧Q∧A C)∧(A P∨Q∨C) (A∧(P Q))C。
2) (P Q)P Q。
二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。
三、推理证明题（10分）1）P∨Q，Q∨R，R S P S。
2) x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))四、某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习COBOL语言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两门语言的学生数是多少(10分)五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）六、已知R、S是N上的关系，其定义如下：R={<x,y>| x,y N∧y=x2}，S={<x,y>| x,y N∧y=x+1}。
求R-1、R*S、S*R、R{1,2}、S[{1,2}]（10分）七、证明：R是传递的R*R R（10分）。
八、证明整数集I上的模m同余关系R={<x,y>|x y(mod m)}是等价关系。
其中，x y(mod m)的含义是x-y可以被m整除（15分）。
九、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。
离散数学试题三(B卷答案）一、证明题（10分）1)((P∨Q)∧(P∧(Q∨R)))∨(P∧Q)∨(P∧R)T2) x y(P(x)Q(y))(xP(x)yQ(y))三、推理证明题（10分）1)(P(Q S))∧(R∨P)∧Q R S2) x(A(x)yB(y))，x(B(x)yC(y))xA(x)yC(y)。
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。
所以，如果考试准时进行，那么天气就好（15分）。
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）六、A={ x1,x2,x3 }，B={ y1,y2}，R={<x1, y1>,<x2, y2>,<x3, y2>}，求其关系矩阵及关系图（10分）。
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。
八、设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠。
关系R满足：<<x1，y1>，<x2，y2>>∈R<x1，x2>∈R1且<y1，y2>∈R2，证明R是A×B上的等价关系（10分）。
九、设f：A B，g：B C，h：C A，证明：如果h o g o f＝I A，f o h o g＝I B，g o f o h＝I C，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。
离散数学试题四（A卷答案）一、（10分）求(P Q)(P∧(Q∨R))的主析取范式二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。
