离散数学期末考试题答案

北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第1页共7页北京交通大学2007-2008学年第二学期《离散数学基础（信科专业）》期末考试卷（A）学院：_____________专业：___________________班级____________姓名：学号：□选修□必修题号总分得分阅卷人一、填空题（共10分，每空1分）1.在推理理论中，推导过程中如果一个或多个公式重言蕴涵某个公式，则这个公式就可以引入推导过程中，这一推理规则叫做（T规则）。2.设A={a，{b}}，则A的幂集是P(A)={Φ,a，{b},{a，{b}}；3.设R是集合A上的二元关系，如果关系R同时具有自反性、反对称性和传递性，则称R是A上的一个偏序关系。4.既是满射，又是单射的映射称为1-1映射（双射）。5.设S为非空有限集,代数系统P(S),∪的单位元和零元分别为S和φ。6.具有n个顶点的无向完全图共有n(n-1)/2条边。7.简单图是指无环、无重边的图。8.k-正则图是指所有顶点的度数均为k的的图。9.Hamilton通路是指通过图中所有顶点一次且仅一次的通路。10.设G=（E，V）是图，如果G是连通的，则P（G）=1。11.命题公式(PQ)(PR)的主析取范式中包含极小项（A）A．PQR；B．PQR；北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第2页共7页C．PQR；D．PQR12.下列谓词公式中（A）不正确。A．(x)(A(x)B)(x)A(x)B；B．(x)(BA(x))B(x)A(x)；C．(x)(BA(x))B(x)A(x)；D．(x)(A(x)B)(x)A(x)B；13.设S={2，a，{3}，4}，R={{a}，3，4，1}，指出下面的写法中正确的是（D）（A）R=S；（B）{a,3}S；（C）{a}R；（D）R；14.下列命题公式不是重言式的是C。A.Q→(P∨Q)；B.(P∧Q)→P；C.（P∧Q）；D.（P∧0）。15.下列谓词公式中（）不正确。(A)(x)(A(x)B)(x)A(x)B；(B)(x)(BA(x))B(x)A(x)；(C)(x)(BA(x))B(x)A(x)；(D)(x)(A(x)B)(x)A(x)B；16.下列命题中正确的是（B）。(A)∪{}=；(B){,{}}-{{}}={}；(C){,{}}-{}={，{}}；(D){,{}}-={{}}；17.设A,B,C为任意三个集合，下列各命题中正确的是（A）。(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。18.3,23,)(,:2xxxxfRRf设,则,2)(,:xxgRRg))((xgfA。（A）121)2(2xxx;（B）323)2(xxx;（C）121)2(2xxx;（D）303)2(2xxx.19.设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b），（b，c），（c，b），（d，d）}，则R2是R1的（B）闭包。(A)自反(B)对称(C)传递(D)以上都不是北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第3页共7页20.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（C）。(A)2，1(B)2，2(C)3，1(D)3，2二、计算题（共40分，每小题10分）1.求命题公式（PQ）（PR）的主合取范式。2.在一个班级的50个学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A。假如有17人两次考试都没有得到A，问有多少学生两次考试中都得到了A？3.设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。（1）画出的哈斯图；（2）求R关于A的极大元；（3）求B={4,6,9}的最小上界和最大下界。4.用逻辑推理方法证明：{PQ，RS，PR}蕴涵QS。5.将公式P((PQ)(QP))化为主析取范式和主合取范式：解：P((PQ)(QP))P((PQ)QP)P(QP)(P(QQ))(QP)(PQ)(PQ)(QP)（主析取范式）P((PQ)(QP))P((PQ)QP)P(QP)(PQ)(PP)PQ（主合取范式）6.化简（ABC）（（AB）C）（ABC）（ABC）解：（ABC）（（AB）C）（ABC）（ABC）=（A~B~C）（A~BC）（AB~C）（ABC）=（（A~B）（~CC））（（AB）（~CC））=（（A~B）E）（（AB）E）E为全集=（A~B）（AB）=A（~BB）=AE=A7.写出下面有向图（关系图）所表示的关系R的关系矩阵，并求出R的自反闭包和对称闭包。北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第4页共7页解：1{,,,,,,,}110001010(){,,,,,,,,,,,}(){,,,,,,,,,}RARaaabbccbMrRRIaabbccabbccbsRRRaaabbabccb8.设图G中各点的度都是3，且点数n与边数m满足2n-3=m。问：G中点数n和边数m各为多少？解：由图G中各点的度都是3知，)()(vGPvGd=3n，而)()(vGPvGd=2m，故，3n=2m。再由已知2n-3=m，解得n=6，m=9。9.张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。问张三、李四、王五三人到底谁说真话，谁说假话？解：10.对102名学生调查表明,有35人学日语,20人学法语,45人学英语,15人既学日语又学英语,8人既学日语又学法语,10人既学法语又学英语,28人不学这三门中的任何一门。cba北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第5页共7页(1)求三门语言都学的人数；(2)求至少两门语言的人数；(3)求只学英语,只学法语,只学日语的人数。解：REFx15-x10-x8-x2+x12+x20+xREFx15-x10-x8-x2+x12+x20+x(1)45+20+2+x+18=102,1).x=7(2)至少学两门的人数为15+4=19,(3)只学英语27人,只学法语9人,只学日语19人,11.设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。（1）画出的哈斯图；（2）求R关于A的极大元；（3）求B={4,6,9}的最小上界和最大下界。12.设A={0,1}，B={1,2}，试确定下列集合：(1)A×{1}×B；(2)A2×B；(3)(B×A)2。解：13.画出K4的所有非同构的生成子图，其中有几个是连通图？北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第6页共7页非同构的生成子图有11个,其中六个连通图.三、证明题（共28分）1.用逻辑推理方法证明：{PQ，RS，PR}蕴涵QS。证明：（1）PR规则P（2）RP规则Q，根据（1）（3）PQ规则P（4）RQ规则Q，根据（2）（3）（5）QR规则Q，根据（4）（6）RS规则P（7）QS规则Q，根据（5）（6）（8）QS规则Q，根据（7）2.证明集合等式（A-B）∪（B-A）=（A∪B）-（A∩B）.3.设R是一个关系，用R-1表示R的逆关系，s(R)表示S的对称闭包，证明s(R)=R∪R-1。证明：①任取(x,y)R∪R-1，则(x,y)R或(x,y)R-1，若(x,y)R，则有(y,x)R-1，所以(y,x)R∪R-1；若(x,y)R-1，则有(y,x)R，所以(y,x)R∪R-1，R∪R-1具有对称性；②显然，RR∪R-1③对A上任意关系R，若RR，且R是对称的，往证R∪R-1R。任取(x,y)R∪R-1，则(x,y)R或(x,y)R-1，若(x,y)R，因为RR，则(x,y)R；若(x,y)R-1，则有(y,x)R，则(y,x)R，因为R是对称的，所以(x,y)R，因此，R∪R-1R。4.设R是一个二元关系，证明：(1)若R是自反的，则s(R)和t(R)是自反的；(2)若R是对称的，则r(R)和t(R)是对称的；北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案第7页共7页5.在半群G,*中，若对a,bG，方程a*x=b和y*a=b都有惟一解，则关于运算*存在单位元。证明：任意取定aG，记方程a*x=a的惟一解为eR。即a*eR=a。下证eR为关于运算*的右单位元。对bG，记方程y*a=b的惟一解为y。因为G,*是半群，所以运算*满足结合律。从而b*eR=(y*a)*eR=y*(a*eR)=y*a=b。故eR为关于运算*的右单位元。类似地，记方程y*a=a的唯一解为eL。即eL*a=a。下证eL为关于运算*的左单位元。对bG，记方程a*x=b的惟一解为x。则eL*b=eL*(a*x)=(eL*a)*x=a*x=b。故eL为关于运算*的左单位元。从而在半群G,*中，在半群G,*中，关于运算*存在单位元，记为e。6.证明：如果图G=(V,E)是Hamilton图，则对顶点集的任一非空子集X，都有p(G-X)|X|，其中p(G-X)表示图G-X的连通分支数。证明：设C是G中的Hamilton回路，因为在回路中，依次删去一点及与此点相邻的两条边每次最多只增加一个分支，所以W(C-X)=1|X|。因为C是G的支撑子图，所以C-X是G-X的支撑子图。故p(G-X)W(C-X)，故p(G-X)|X|。7.设G(V,E)是一个无向带权图，且各边的权不相等。{V1,V2}是V的一个划分，即V1Φ，V2Φ，V1V2=V，V1V2=Φ，证明：V1和V2之间的最短边一定在G的最小生成树上。证明：设e是V1和V2之间的最短边，G的最小生成树为T。若e不在T上，则T{e}有唯一的圈c。因为T是G的最小生成树，所以c上除e之外还有另一条V1和V2之间的边e1。而W(e1)W(e)，T{e}-{e1}是连通图，并且与T的边数相同，所以T{e}-{e1}也是G的生成树。而W(T{e}-{e1})=W(T)+W(e)-W(e1)W(T)，所以T不是G的最小生成树，于是得到矛盾！故命题得证。