离散数学期中考试题-0X-0X-2-A-答案

200X-200X学年第X学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学200X-200X学年第X学期离散数学期中考试题&参考答案第1页共5页离散数学基础期中考试题（参考答案）学期：200X－200X学年第X学期学生班级：XX专业0X01-0X04班考试时间：200X.XX.XXXX:XX-XX:XXam学号：姓名：班级：□必修□选修一、填空题（共10分，每空1分）1.我们称能够表达判断，并且具有确定真值的陈述句为命题。2.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。3.把命题公式在其所有解释下所取真值列成一个表，称为G的真值表。4.命题公式G=（PQ）R，则G共有8个不同的解释；解释（F，T，F）使G的真值为T。5.在推理理论中，前提在推导过程中的任何时候都可以引入使用，这一推理规则叫做（P规则）。6.设集合}}{,{A，A的幂集(),{},{{}},{,{}}A。7.设R是集合A上的二元关系，如果R是自反的，则它的关系矩阵的主对角线元素（全是1）。8.设R是集合A上的二元关系，R-1是R的逆关系，则R的关系矩阵与R-1的关系矩阵具有的关系是（互为转置矩阵）。9.设R是集合A上的二元关系，如果关系R同时具有自反性、反对称性和传递性，则称R是A上的一个偏序关系。二、选择一个正确答案的代号，填入括号中。（共20分，每小题2分）1.下列语句中不能成为命题的是（D）。A．地球外的星球上也有人；B．小王是我的同学，也是我的好朋友；C．11+1=100；D．我正在说慌。2.下列谓词公式中（C）不是命题。A．(x)P(x)；B．(x)P(x)；C．(x)(P(x)P(y))；D．(x)(y)(P(x)R(y))3.个体域为整数集合，下列公式中（C）不是命题。A．(x)(y)(x*y=y)；B．(x)(y)(x*y=1)；C．(x)(x*y=x)；D．(x)(y)(x*y=2)4.下列谓词公式中（A）不正确。200X-200X学年第X学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学200X-200X学年第X学期离散数学期中考试题&参考答案第2页共5页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；5.下列命题中正确的是（B）。A．∪{}=；B．{,{}}-{{}}={}；C．{,{}}-{}={，{}}；D．{,{}}-={{}}；6.由集合运算定义，下列各式正确的有（A）。A．XXYB.XXYC.XXYD.YXY7.设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。8.设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．以上都不是9.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（C）。A．2，1B．2，2C．3，1D．3，210.设有函数2,3:,()2,3xxfRRfxx,:,()2gRRgxx，则()():fgxRR是。(A)单射非满射;(B)满射非单射;(C)不是单射也非满射;(D)双射.三、计算题（共40分，每小题10分）1.求命题公式S=(P(QR))((PQ)(PR))的真值表。解：PQRQRP(QR)PQPR(PQ)(PR)STTTTTFTFTTFFFTTFTFFFTFFFTFTTTFTTTFTTTTTTTTFFTTTTTFTFTTTTTFTTTTTTTTTTTTTT2.通过求主析取范式判断下列命题公式是否等值。（1）（PQ）（PQR）；（2）（P（QR））（Q（PR））；200X-200X学年第X学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学200X-200X学年第X学期离散数学期中考试题&参考答案第3页共5页解：（PQ）（PQR）（PQ（RR））（PQR）（PQR）（PQR）（PQR）m6m7m3m3m6m7（P（QR））（Q（PR））（PQ）（QR）（PPR）（PQR）（分配律）（PQ（RR））（（PP）QR）（PQR）（PQR）（PQR）（PQR）（PQR）（PQR）m6m7m3m7m3m3m6m7由此可见（PQ）（PQR）（P（QR））（Q（PR））3.某学校有597名学生，有299人选修数学，259人选修计算机，227人选修英语；其中99人同时选修数学与计算机，68人同时选修数学与英语，33人同时选修计算机与英语。画出文氏图，问该统计数字是否可能，并说明理由。若总人数是581呢？4.设已知集合A={1,2,3,4,5,6}上的等价关系R={(1,1),(1,5),(2,2),(2,3),(2,6),(3,2),(3,3),(3,6),(4,4),(5,1),(5,5),(6,2),(6,3)(6,6)}求A的由R诱导出的划分。解：[1]={1,5}[2]={2,3,6}[4]={4}A/R={[1],[2],[4]}={{1,5},{2,3,6},{4}}四、证明题（共30分）1.用归纳法证明(A1B)(A2B)„(AnB)(A1A2„An)B是一个正确的推理形式。证明：往证(A1B)(A2B)„(AnB)(A1A2„An)B是一个永真式。用归纳法。当n=1时，(A1B)A1B(A1B)A1B((A1B)A1)B((A1A1)(BA1)B(BA1BBA1BT设当n=k-1时推理表达式为真，即设(A1B)(A2B)„(Ak-1B)(A1A2„Ak-1)B是一个永真式。令C(A1A2„A可－1)200X-200X学年第X学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学200X-200X学年第X学期离散数学期中考试题&参考答案第4页共5页D(A1B)(A2B)„(Ak-1B)即设CDB为T。当n=k时，(A1B)(A2B)„(Ak-1B)(AkB)(A1A2„Ak-1Ak)B(D(AkB)(CAk))B(D(AkB)(CAk))B((D(AkB)C)((D(AkB)Ak)))B„„(CDB)AkTAkT所以原式是一个正确的推理形式。2.设R是集合A上的二元关系，证明（1）R是反自反的IA∩R=；（2）R是反对称的R∩R-1IA证明：（1）R是反自反的(a)(aA(a,a)A)，但(a)(a,a)IA(a)((a,a)A)(a,a)IA)IA∩R=。（2）设R是反对称的，任取aA，bA，如果(a,b)R∩R-1，则有(a,b)R且(a,b)R-1，也即(a,b)R且(b,a)R，由R的反对称性，a=b，所以(a,b)=(a,a)IA，从而得，R∩R-1IA。反之，若R∩R-1IA，设(a,b)R，(b,a)R，则有，(a,b)R且(a,b)R-1，也即(a,b)R∩R-1，再由R∩R-1IA，得到(a,b)IA，从而a=b。3.求欧拉函数的值。设n是正整数，欧拉函数()n表示0,1,...,n-1中与n互素的数的个数。证明欧拉函数可写成12111()(1)(1)...(1)knnppp其中12,,...,kppp是n的素数因子。最后再计算(60)的值。【证明】利用包含排斥原理证明。给定正整数n，1212kknppp为n的素数因子分解式，令|01,|iiAxxnpx则有200X-200X学年第X学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学200X-200X学年第X学期离散数学期中考试题&参考答案第5页共5页12()knAAA我们有||,1,2,,iinAikp||,1ijijnAAijkpp根据包含排斥原理，有1212123411212()()()(1)111(1)(1)...(1)kkkkkkknAAAnnnnnnnpppppppppnpppnppp最后，111124(60)60(1)(1)(1)6016125235与60互素的正整数个数有16个，它们分别是1，7，11，13，17，19，23，29，31，37，41，43，47，49，53，59。