下载文档原格式
《离散数学》题库与答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( A )(1)⌝Q=>Q→P (2)⌝Q=>P→Q (3)P=>P→Q (4)⌝P∧(P∨Q)=>⌝P答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别）2、下列公式中哪些是永真式？( )(1)(┐P∧Q)→(Q→⌝R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q)答：（2），（3），（4）可用蕴含等值式证明3、设有下列公式，请问哪几个是永真蕴涵式?( )(1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q(4)P∧(P→Q)=>Q (5) ⌝(P→Q)=>P (6) ⌝P∧(P∨Q)=>⌝P答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式4、公式∀x((A(x)→B(y，x))∧∃z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。
答：x,y, x,z（考察定义在公式∀x A和∃x A中，称x为指导变元，A为量词的辖域。
在∀x A和∃x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。
于是A(x)、B(y，x)和∃z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元）5、判断下列语句是不是命题。
若是，给出命题的真值。
( )(1)北京是中华人民共和国的首都。
(2) 陕西师大是一座工厂。
(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。
(5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。
）6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。
西南科技大学2007——2008学年第2学期《离散数学J 》参考答案及评分细则学院:_______________班级:_____________姓名:_______________学号:____________ 1．完成┐(R∨S)↔(R∧S)的真值表，并求出它的最简合取范式。
（20分）解：真值表（8分）求最简合取范式:（12分）设A = ┐(R∨S)↔(R∧S)，则┐A = ┐(┐(R∨S)↔(R∧S))= ┐(┐(R∨S)∧R∧S∨(R∨S) ∧(R∧S))= ┐((R∨S)∧┐(R∧S))= (┐R∧┐S)∨(R∧S)所以，A = (R∨S)∧(┐R∨┐S)2．“同班同学有同一个班主任，张三和李四的班主任不是同一个人，所以张三和李四不是同班同学。
”将上述命题谓词符号化，并证明。
(20分)其中P(x,y):x和y是同班同学，Q(x,y):x和y有同一个班主任，a:张三，b:李四。
解：符号化：（5分）前提：∀x∀y(P(x,y)→Q(x,y)), ┐Q(x,y)结论：┐P(a,b)推理证明：（15分）(1)∀x∀y(P(x,y)→Q(x,y)) P(2)∀y(P(a,y)→Q(a,y)) T,(1),US(3)P(a,b)→Q(a,b) T,(2),US(4)┐Q(a,b) P(5)┐P(a,b) T,(3,4),I43．写出集合{{φ,a},{a}}的全部子集合（8分）解：子集有：φ，{{φ,a}},{{φ}},{{φ,a},{a}}4．某班学生40人，会排球的有20人，会篮球的15人，以上两种运动都会的5人，问两种运动都不会的有几人？（12分）解：设会排球的是集合A，会篮球的是集合B。
则|A∪B|＝|A|＋|B|－|A∩B|＝20＋15－5＝30所以，两种运动都不会的有40-30＝10人。
5．设R是从集合A到集合B的关系，S,T是从集合B到集合C的关系，试证明R(S∩T)⊆(RS)∩(RT) （15分）证明：对任意<a,c>∈Rο(S∩T)，则由合成运算知，至少存在b∈B,使得：<a,b>∈R ,<b,c>∈(S∩T)，即：<b,c>∈S,且<b,c>∈T。
一、判断下列命题对错(每小题前标记/或X)(总20分)(V) 1.集合的交运算关于对称差运算满足分配律。
(X ) 2.对于集合A, A®A=Ao(X) 3.集合的差运算满足结合律。
(X) 4.集合A上的关系都是自反的。
(V) 5.若R,S都是A上的自反关系，则复合关系RoS也是自反关系。
(X) 6.若局,/?2都是A上的等价关系，则复合关系&。
尺2也是等价关系。
(X) 7.合取范式都不是析取范式。
(X)&命题的主析取范式不是唯一的。
(V) 9.无向图的总度数是偶数。
(V) 10.无回路的无向连通图称为树。
二、填空题题目(每空3分，总30分)1. 设集合A的阶数|A|=3,则幕集|P(A)I= 8 。
2. 设A是全集E的子集，则A€BE= A-E 。
3. 若集合A={1,2,3,4,5,6,7,8}, R是A上模为3的同余关系，则等价类[1]R= {1,4,7}, 商集A/R= {{1,4,7}, {2,5,8}, {3,6}}。
4. 偏序关系是指满足自反、反对称、传递的二元关系。
5. 命题P-Q的主合取范式是-.PV0 。
6. 有向连通图是欧拉图的充分必要条件是图中每个顶点的入度和出度相等o7. 设赋权图的顶点集是V={a,b,c,d,e,z},令T={ b,c,d,e,z },已知指标DT(b)=6, DT(c)=8,DT(d)=8, DT(e)=7, DT(z)=8,则 a 到 b 的最短路长是 6 。
& 命题逻辑中，吸收律是指如下两个等价式：PV(P/\Q)=P和PA(PVQ)=P 。
三、(10分)设集合A={1,2,3,4,6,8,12,16}, R是A上的整除关系，证明R是A上的偏序关系并画出R的哈斯图。
证明：R是A上的整除关系，即当a,b€A, a能整除b时，(a,b) €R。
易知a能整除a,得(a,a)GR,即R是自反的二元关系；易知(b,a)吃R,即R是反对称的二元关系；当ceA, c能整除a时,c也能整除b,即若(c,a) GR, (a,b) eR时，有(c,b) GR,即R是传递的二元关系。
一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 22n.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 .4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是(P∧⌝Q∧R)5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝{4} ; A⋃B＝{1,2,3,4};A－B＝{1,2} .7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0)9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则R1∙R2 ={(1,3),(2,2),(3,1)} , R2∙R1 = {(2,4),(3,3),(4,2)} _R12 ={(2,2),(3,3).10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = .11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} ,A∩B ={x | 0≤x≤1, x∈R} , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} .14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是∃x(⌝P(x)∨Q(x)) .15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。
《离散数学》考试试卷（试卷库20卷）及答案第 1 页/共 4 页《离散数学》考试试卷（试卷库20卷）试题总分： 100 分考试时限：120 分钟、选择题（每题2分，共20分）1. 设论域为全总个体域，M(x)：x 是人，Mortal(x)：x 是要死的，则“人总是要死的”谓词公式表示为( )（A ）)()(x Mortal x M → （B ）)()(x Mortal x M ∧（C ）))()((x Mortal x M x →?（D ）))()((x Mortal x M x ∧?2. 判断下列命题哪个正确？( )（A ）若A∪B＝A∪C，则B ＝C （B ）{a,b}={b,a}（C ）P(A∩B)≠P(A)∩P (B)（P(S)表示S 的幂集）（D ）若A 为非空集，则A ≠A∪A 成立3. 集合},2{N n x x A n∈==对( )运算封闭（A ）乘法（B ）减法（C ）加法（D ）y x -4. 设≤><,N 是偏序格，其中N 是自然数集合，“≤”是普通的数间“小于等于”关系，则N b a ∈?,有=∨b a ( )（A ）a（B ）b（C ）min(a ，b)（D ） max(a ，b)5. 有向图D=，则41v v 到长度为2的通路有( )条（A ）0 （B ）1 （C ）2 （D ）36. 设无向图G 有18条边且每个顶点的度数都是3，则图G 有( )个顶点（A ）10 （B ）4 （C ）8 （D ）127. 下面哪一种图不一定是树？（）（A ）无回路的连通图（B ）有n 个结点n-1条边的连通图（C ）每对结点间都有通路的图（D ）连通但删去一条边则不连通的图 8. 设P ：我将去镇上,Q ：我有时间。
命题“我将去镇上,仅当我有时间”符号化为（）（A ）P →Q （B ）Q →P （C ）P Q （D ）Q P ?∨? 9. 下列代数系统中,其中*是加法运算,（）不是群。
(完整)湖南大学离散数学考试试卷诚信应考，考试作弊将带来严重后果！湖南大学课程考试试卷课程名称： 离散数学 ；课程编码: 08038 试卷编号：A ;考试时间：120分钟题 号 一 二 三 四 五 六 七 八 九 十总分 应得分 10 1010151010151010100实得分 评卷人特别提示：答案请写答卷纸上，计算题与证明必须有步骤一、填空题（每小题1分, 共10分）1、树是连通的,且边的条数等于点数____，去掉任何一条边后树不_____。
2、树中度数为1的结点数的下限是_____。
3、一棵无向树的结点数是99个,则这树所有点的度数和___4、哈密顿回路是指________________________________________________。
.5、存在哈密顿回路的充分条件是___________________________________.6、欧拉回路是指________________________________________________。
7、存在欧拉路但不存在欧拉回路的充要条件________________________。
8、给出下图的关联矩阵-————-—-—--—————.9、根据关联矩阵依次算出上图中各点的入度、出度、度数，并验证是否满足握手定理。
____年___月___日考 试 用 专业班级：学号：姓名： 装订线（题目不得超过此线）湖南大学课程考试试卷湖南大学教务处考试中心(完整)湖南大学离散数学考试试卷10、关系R是集合A上的等价关系，那么关系R的_____是集合一个划分，给定义集合A的一个划分，如何构造出集合A上的等价关系__________。
二、（10分) 黄、李、肖预测德国A、乌拉圭B、西班牙C、荷兰D的名次，黄说“德国冠军,乌拉圭亚军”，李说“荷兰亚军,西班牙第4名”,肖说“德国亚军，乌拉圭第四名”，结果三人预测的结果都只对了一个,请问最后的名次是什么。
离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。
b)我今天进城，除非下雨。
c)仅当你走，我将留下。
2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。
c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。
（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。
（4分）4.判断下面命题的真假，并说明原因。
（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。
（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。
第 1 页/共 4 页《离散数学》考试试卷（试卷库14卷）试题总分： 100 分 考试时限：120 分钟一、选择题（每题2分，共20分）1. 下述命题公式中，是重言式的为( )（A ）)()(q p q p ∨→∧ （B ）q p ∨))()((p q q p →∨→⇔（C ）q q p ∧→⌝)(（D ）q q p →⌝∧)(2. 对任意集合A,B,C,下列结论正确的是（ ）（A ）若A ⊆B,B ∈C,则A ⊆C ； （B ）若A ∈B,B⊆C,则A ⊆C ； （C ）若A ⊆B,B ∈C,则A ∈C ； （D ）若A ∈B,B ⊆C,则A ∈C ； 3. 设} 3 ,2 ,1 {=S ，定义S S ⨯上的等价关系,,则由R 产生的S S ⨯上一个划分共有( )个分块。
（A ）4（B ）5（C ）6（D ）94. 下列偏序集( )能构成格5. 连通图G 是一棵树当且仅当G 中( )（A ）有些边是割边 （B ）每条边都是割边（C ）所有边都不是割边 （D ）图中存在一条欧拉路径6. 有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件( )（A ） 63-≤n m（B ）63-≤m n （C ）63-≥n m （D ） 63-≥m n7. 设P,Q 的真值为0,R,S 的真值为1,则下面命题公式中真值为1的是（ ）（A ）R →P （B ）Q ∧S （C ）P S （D ）Q ∨R 8. 在图G=<V,E>中,结点总度数与边数的关系是（ ）（A ）deg()2||i v E =（B ）deg()||i v E =（C ）deg()2||iv Vv E ∈=∑（D ）deg()||iv Vv E ∈=∑9. 设有33盏灯,拟公用一个电源,则至少需有五插头的接线板数（ ）（A ）７ （B ）８ （C ）９ （D ）１４ 10. 设集合A 上有四个元素,则A 上的不同的等价关系的个数为（ ）（A ）11 （B ）14 （C ）17（D ）15二、填空题（每题2分，共20分）1. 设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为则R= 。
参考答案及评分细则西南科技大学2007——2008学年第 2 学期《离散数学》期末考试试卷（A卷）一、(10分) 符号化下列命题：（1）R→S (2分)（2）┐(P∧Q)→R (2分)（3）┐(P∨Q) (2分)（4）┐∀x(L (x)→G(x)) (2分)（5）┐(∀x)（A（x）→B（x））或(∃x)（A(x)∧┐B(x)）(2分) 二、(7分)化简命题公式：┒(P→Q)∨(P→(P∧Q))解：┒(P→Q)∨(P→(P∧Q))⇔┒(┒P∨Q)∨(┒P∨(P∧Q)) (2分)⇔ (P∧┒Q)∨┒P∨(P∧Q) (2分)⇔ (P∧(Q∨┒Q)∨┒P (1分)⇔ (P∧T)∨┒P⇔ P∨┒P⇔T (2分)三、(10分)求命题公式：P↔(Q∧R) 的主析取范式和主合取范式。
解：（本题解法不唯一，只要能正确求出主析取范式和主合取范式均可。
）先求主合取范式(5分)：P↔(Q∧R)⇔(P→(Q∧R))∧((Q∧R)→P)⇔(┒P∨(Q∧R))∧(┒(Q∧R)∨P)⇔(┒P∨Q)∧(┒P∨R))∧(┒Q∨┒R∨P)⇔(┒P∨Q∨(┒R∧R))∧(┒P∨(┒Q∧Q)∨R))∧(┒Q∨┒R∨P)⇔(┒P∨Q∨┒R)∧(┒P∨Q∨R)∧(┒P∨┒Q∨R))∧(┒P∨Q∨R)∧(P∨┒Q∨┒R)⇔(┒P∨Q∨┒R)∧(┒P∨Q∨R)∧(┒P∨┒Q∨R)∧(P∨┒Q∨┒R) (2分)⇔π(3,4,5,6)根据命题公式主析取范式和主合取范式之间的对应关系可知，该命题的公式的主析取范式为：∑(0,1,2,7)。
(2分)即：(P∧Q∧R)∨(┒P∧Q∧┒R)∨(┒P∧┒Q∧R)∨(┒P∧┒Q∧┒R) (5分)四、(16分)用推理规则证明：（1）(8分)┐(P∧┐Q)，┐Q∨R，┐R＝＞┐P证明：①┐R P，前提引入②┐Q∨R P，前提引入③R∨┐Q T，②恒等变换④┐Q T，②析取三段论⑤┐(P∧┐Q) P，前提引入⑥┐P∨Q T，⑤恒等变换⑦Q∨┐P T，⑥恒等变换⑧┐P T，④⑦析取三段论故，原命题成立，证毕。
《离散数学》试卷(A)适用专业： 考试日期：试卷类型：闭卷 考试时间：120分钟 试卷总分：100分一、单项选择题(本大题共8小题，每小题3分，共24分)1、下述哪一个不是命题？（ ） A 、离散数学是计算机系的一门必修课 B 、不存在最大偶数。
C 、若我有空，我就看书。
D 、请勿随地叶痰！2、设A={a,b,c}，B={1,2,3}，以下哪一个关系是从A 到B 的双射函数？（ ） A 、f={<a,2>,<b,2>,<c,1>} B 、f={<a,3>,<b,1>,<c,2>} C 、f={<a,1>,<b,2>,<c,3>,<a,3>} D 、f={<a,1>,<b,2>,<a,3>}3.设<G, 。
>是群，且|G|>1,则下列命题不成立的是（ ）A.G 中有幺元B. G 中有零元C.G 中任一元素有逆元D. G 中除幺元外无其它幂等元 4、设A={}c b a ,,,则下列是集合A 的划分的是（ ） A.{}{}{}c c b ,, B. {}{}{}c a b a ,,, C.{}{}c b a ,, D.{}{}{}c b a ,, 5.设集合A={a,{b}}，下面四个命题为真的是A.a 包含于AB.φ∈AC.{b}包含于AD.φ包含于A 6、下列是命题公式p ∧(q ∨⌝r)的成真指派的是（ ） A.110,111,100 B.110,101,011 C 所有指派 D.无 7、与一阶公式P(x)→VxQ(x)等值的公式是A.P(y)→VyQ(y)B.P(y)→VxQ(y)C.P(x)→VyQ(y)D.P(z)→VyQ(y)8、设A 和B 都是命题，则A →B 的真值为假当且仅当（ ） A 、A 为0 ，B 为1 B 、A 为0 ，B 为0 C 、A 为1 ，B 为1 D 、A 为1 ，B 为0二、填空题（本大题共7小题，每空3分，共21分）１．.设A={a,b,c}，F 是A 上的二元关系，F={<a,c>,<b,a>,<c,b>}，则其自反闭包为r(F)= 。
