资源描述：
《离散数学题目大汇总.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、离散数学试题一（A卷答案）一、（10分）证明Ø(A∨B)®Ø(P∨Q)，P，(B®A)∨ØPA。二、（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)
2、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)若fog是满射，则f是满射。(2)若fog是单射，则g是单射。六、（15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得ÎTÛÎR且ÎR，证明T是一个等价关系。七、（15分）若是群，H是G的非空子集，则<
3、H，*>是的子群Û对任意的a、b∈H有a*b－1∈H。八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？离散数学试题一（B卷答案）一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。(1)写出F在全功能联结词组{}中的命题公式。(2)写出F的主析取范式与主合取范式。二、（10分）判断下列公式是否是永真式？(1)($
4、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≠Æ，若
5、X
6、＝n，问(1)偏序集是否有最大元？(2)偏序集是否有最小元？(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。四、（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(
7、R)和t(R)。六、（10分）有幺元且满足消去律的有限半群一定是群。证明设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。考虑a，a2，…，ak，…。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。七、（20分）有向图G如图所示，试求：(1)求G
8、的邻接矩阵A。(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？(3)求出ATA和AAT，说明ATA和AAT中的第(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分）已知
9、集合A和B且
10、A
11、=n，
12、B
13、=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人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。六、（12分）已知R和S是非
14、空集合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，h()＝。证明h是双射。八、（12分）是个群，u∈G，定义G中的运算“D”为aDb=a*u-1*b，对任意a,b∈G，求证：也是个群。九、（10分）已知：D=，V={1,2,3
