离散数学考试答案

2007-2008学年第2学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学2003-2004学年第2学期离散数学期末考试题&参考答案第1页共4页离散数学基础期中考试题（参考答案）学期：2007－2008学年第2学期学生班级：信科0601-04考试时间：2008.4.2110:10-12:00am学号：姓名：班级：□必修□选修一、填空题（共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）不正确。2007-2008学年第2学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学2003-2004学年第2学期离散数学期末考试题&参考答案第2页共4页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．a{{a}}；B．{a}{{a}}；C．{a}{{a}}；D．{{a}}。6.下列命题中正确的是（B）。A．∪{}=；B．{,{}}-{{}}={}；C．{,{}}-{}={，{}}；D．{,{}}-={{}}；7.由集合运算定义，下列各式正确的有（A）。A．XXYB.XXYC.XXYD.YXY8.设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。9.设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．以上都不是10.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（C）。A．2，1B．2，2C．3，1D．3，2三、计算题（共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））；解：（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m72007-2008学年第2学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学2003-2004学年第2学期离散数学期末考试题&参考答案第3页共4页（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.将公式x((yP(x，y))(zQ(z)R(x)))化成等价的前束范式：解：x((yP(x，y))(zQ(z)R(x)))=x((yP(x，y))((zQ(z))R(x)))=x((yP(x，y))((zQ(z))R(x)))=x((yP(x，y))(z(Q(z))R(x)))=xy(P(x，y)(z(Q(z))R(x)))=xyz(P(x，y)Q(z)R(x))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)2007-2008学年第2学期离散数学基础期中考试题北京交通大学理学院黄晓鸣北京交通大学2003-2004学年第2学期离散数学期末考试题&参考答案第4页共4页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.将集合M中元素映射到自身的变换称为同一变换，记为I。设，是集合M上的两个变换。证明，如果•=•=I，则，是1–1变换，并且=-1。4.（选做）考虑整数集合Z。对于某个正整数r，定义Z上的一个关系R：aRb当且仅当b=ar。证明R是Z上的一个偏序。