离散数学练习题含答案.doc
. .离散数学试题第一局部 选择题 一、单项选择题1以下是两个命题变元p，q的小项是 C AppqBpqCpqDppq2令p：今天下雪了，q：路滑，那么命题“虽然今天下雪了，但是路不滑可符号化为 D ApqBpqCpqDpq3以下语句中是命题的只有 A A1+1=10Bx+y=10Csinx+siny<0Dx mod 3=24以下等值式不正确的选项是 C A(x)A(x)AB(x)(BA(x)B(x)A(x)C(x)(A(x)B(x)(x)A(x)(x)B(x)D(x)(y)(A(x)B(y)(x)A(x)(y)B(y)5谓词公式(x)P(x,y)(x)(Q(x,z)(x)(y)R(x,y,z)中量词x的辖域是 C A(x)Q(x,z)(x)(y)R(x,y,z)BQ(x,z)(y)R(x,y,z)CQ(x,z)(x)(y)R(x,y,z)DQ(x,z)6设A=a,b,c,d，A上的等价关系R=<a,b>,<b,a>,<c,d>,<d,c>IA，那么对应于R的A的划分是 D Aa,b,c,dBa,b,c,dCa,b,c,dDa,b,c,d7设A=Ø，B=P(P(A)，以下正确的式子是 A AØ,ØBBØ,ØBCØ,ØBDØ,ØB8设X，Y，Z是集合，一是集合相对补运算，以下等式不正确的选项是 A A(X-Y)-Z=X-(YZ)B(X-Y)-Z=(X-Z)-YC(X-Y)-Z=(X-Z)-(Y-Z)D(X-Y)-Z=X-(YZ)9在自然数集N上，以下定义的运算中不可结合的只有 D Aa*b=min(a,b)Ba*b=a+bCa*b=GCD(a,b)(a,b的最大公约数)Da*b=a(mod b)10.设R和S是集合A上的关系,RS必为反对称关系的是( A )A当R是偏序关系,S是等价关系; B当R和S都是自反关系;C当R和S都是等价关系; D当R和S都是传递关系11.设R是A上的二元关系,且R·RÍR,可以肯定R应是( D )A对称关系; B全序关系; C自反关系; D传递关系第二局部 非选择题二、填空题1设论域是a,b,c，那么(x)S(x)等价于命题公式S(a)S(b)S(c)；()S(x)等价于命题公式S(a)S(b) S(c)。2设R为A上的关系，那么R的自反闭包r(R)=_R_，对称闭包s(R)=_R。3某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是_，其关系矩阵是只有主对角线上元素为1 。三、计算题14分如果论域是集合a,b,c，试消去给定公式中的量词：。2用等值演算求下面公式的主析取X式。3用等值演算法求公式的主合取X式。46分在偏序集<Z,>中，其中Z=1,2,3,4,6,8,12,14，是Z中的整除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元，最小上界和最大下界。5设集合A=1,2,3,4,5,A上的划分为1,2,3,4,5,试求：1) 写出划分诱导的等价关系R；2) 写出关系矩阵；3) 画出关系图。6. 设Aa，b，c，d，R是A上的二元关系，且R<a，b>，<b，a>，<b，c>，<c，d>，求r(R)、s(R)和t(R)。解 r(R)RIA<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>s(R)RR-1<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>R2<a，a>，<a，c>，<b，b>，<b，d>R3<a，b>，<a，d>，<b，a>，<b，c>R4<a，a>，<a，c>，<b，b>，<b，d>R2t(R)<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>四、证明题1设R和S是二元关系，证明2设A=a,b,c,R=(a,a),(a,b),(b,c),验证rs(R)=sr(R)。3设R是A上的二元关系，试证：R是传递的当且仅当，其中表示。4证明以下结论：12解：11PQP附加前提2PT，1，I23PQT，2，I14PQRP5RT，3，4，I36PQRCP21DP假设前提2DAP3AT，1，2，I54(AB)(AC)P5ABT，4，I2 6 BT，3，5，I37 ACT，4，I28CT，3，7，I39BCT，6，8 ，合取式10BCP11BCBCT，9，10，合取式，矛盾5. R和S是非空集合A上的等价关系，试证：1RS是A上的等价关系；2对aA，aRS=aRaS。解："xA，因为R和S是自反关系，所以<x,x>R、<x,x>S，因而<x,x>RS，故RS是自反的。"x、yA，假设<x,y>RS，那么<x,y>R、<x,y>S，因为R和S是对称关系，所以因<y,x>R、<y,x>S，因而<y,x>RS，故RS是对称的。"x、y、zA，假设<x,y>RS且<y,z>RS，那么<x,y>R、<x,y>S且<y,z>R、<y,z>S，因为R和S是传递的，所以因<x,z>R、<x,z>S，因而<x,z>RS，故RS是传递的。总之RS是等价关系。2因为xaRSÛ<x,a>RSÛ<x,a>R<x,a>SÛxaRxaSÛxaRaS所以aRS=aRaS。五、应用题1所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。论述域：所有人的集合. .word.
