离散数学练习题(含答案)[谷风书屋]

1、离散数学试题第一部分 选择题 一、单项选择题1下列是两个命题变元p，q的小项是（ C ）AppqBpqCpqDppq2令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）ApqBpqCpqDpq3下列语句中是命题的只有（ A ）A1+1=10Bx+y=10Csinx+siny0Dx 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

2、,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=,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

3、在自然数集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上的二元关系,且RRR,可以肯定R应是( D )A对称关系; B全序关系; C自反关系; D传递关系第二部分 非选择题二、填空题1设论域是a,b,c，则(x)S(x)等价于命题公式 S(a)S(b)S(c) ；()S(x)等价于命题公式 S(a

4、)S(b) S(c) 。2设R为A上的关系，则R的自反闭包r(R)= _R_ ，对称闭包s(R)= _R 。3某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 _ ，其关系矩阵是 只有主对角线上元素为1 。三、计算题1（4分）如果论域是集合a,b,c，试消去给定公式中的量词：。2用等值演算求下面公式的主析取范式。3用等值演算法求公式的主合取范式。4（6分）在偏序集中，其中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,试求

5、：1) 写出划分诱导的等价关系R；2) 写出关系矩阵；3) 画出关系图。6. 设Aa，b，c，d，R是A上的二元关系，且R，求r(R)、s(R)和t(R)。解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，四、证明题1设R和S是二元关系，证明2设A=a,b,c,R=(a,a),(a,b),(b,c),验证rs(R)=sr(R)。3设R是A上的二元关系，试证：R是传递的当且仅当，其中表示。4证明下列结论：（1） （2）解：（1）1PQP附加前提2PT，1，I23PQT，2，I14PQRP5RT，3，4，I36PQRCP（2）1DP假设前提2DAP3AT，1，2，I54(AB)

6、(AC)P5ABT，4，I2 6 BT，3，5，I3 7 ACT，4，I2 8CT，3，7，I3 9BCT，6，8 ，合取式10（BC）P11（BC）（BC）T，9，10，合取式，矛盾5. 已知R和S是非空集合A上的等价关系，试证：1）RS是A上的等价关系；2）对aA，aRS=aRaS。解：xA，因为R和S是自反关系，所以R、S，因而RS，故RS是自反的。x、yA，若RS，则R、S，因为R和S是对称关系，所以因R、S，因而RS，故RS是对称的。x、y、zA，若RS且RS，则R、S且R、S，因为R和S是传递的，所以因R、S，因而RS，故RS是传递的。总之RS是等价关系。2）因为xaRSRSRS xaRxaS xaR