离散数学练习题

1、 离散数学题之相礼和创作第一部分 选择题一、单项择题1列是两个命题变元 ，q 的小项是（ C ）Appq CpqBpDppq2令 p：天下雪了， q：路滑，则命题“虽今天下雪 了，但是路不滑”可号化为（ D ）ApqCpq3列语句中是命题的只要（ A ） ABq DpqBC D mod 4列等值式不正确的是（ C ）A( x)A ( x)AB( x)(BA(x) B( x)A(x)C( B(x) ( x)A(x)( x)B(x)D( x)( B(y) ( x)A(x)( y)B(y)5谓词式 ( ( x)(Q(x,z) ( x)( 中量 A 词 x 的域是（ ）A( x)Q(x,z) x)(

2、B( y)R(x,y,z)C( x)( y)R(x,y,z) D6 设A=a,b,c,d ， A上 的 等 价 关 系 I ，则对应于 R 的 A 划 分是（ D ）Aa,b,c,dCa,b,c,dDa,b,c,dB a,b,c,d7 A=，B=P(P(A)，下正确的式子是（ A ）A,BB ,C,B , 8设 X，Y Z 是集合，一是集合绝对补算，下列等式 不正确的是（ A ）A Y)- Z=X- (YB(X- Y)- Z=(X- Z)- YC(X- Y)- Z)- (Y- Z)D(X- Y)- (Y9在自数集 ，下列定义的运算中不结合的只要 （ D ）Aa*b=min(a,b)BCa*b=

3、GCD(a,b)(a,b 最大公约数D b) R 和 是集合 A 上的关系R 必为反对称关系的是 ( A )A当 R 是偏序关系, 等价关系 B当 都自反 关;C当 都是价关系; D当 R 都是传递关系 11.设 A 上的二元关系 且 RR 可以一定 R 应是( D ) A对称关; B 全关系; 自反关系 D 传递关第二部分 非选择题二、填空1设论域 ，则( 等价于命题式 S(a) S(b) ；( 价于命公式 S(a)S(b) 2 A 上的关系，则 R 自反闭 I ，对A称闭包 s(R)=_R R .3集合 A 上的二元关系 R 具有对性，反对称性，自反 性和传递性，此关系 R 是 I ，其关

4、系矩阵是只要对A角线上元素为 .三、计算1 分假如论域是集合 a,b,c ，试消往给定公式中的量词：( y .2等值演算求上面公式的主析取范 ( Q ) ( )3等值演算法求公式 Q ) ( P )的主合取范式 .4 （ 6分 ） 在 偏 序 集 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,写出划 诱导的等价关系 R；写出关系矩阵MR；画出关系图 设 b c 是 上的二元系，且 R ，b，c，求 r)

5、、s)和 t(R).解 r R IA ， b ， c ， ，d，s) b d ， ，d，c2，a，b，d3，a，d，4，a，b，dR2t( R i ， b ， c ， d ， a i 1a，a，c，bb， a，d四、证明1 R 和 S 是二元关系，证明 )R 2 A=a,b,c,R=(a,a),(a,b),(b,c), 证 rs(R)=sr(R).3设 R 是 A 上的二元关系，试： R 是传递的当且仅当R R ，其中 R 2 暗示 .4明下列结论：（1）（2）P R R( B C ), B ), D D解：（1）1 附前提2 P T ， 1 ，I3 PQ T，2，I45QR P R ， 3

6、，4，I6（2）1QR CP D 假 设前提23DAA ， 1 ，2，I45(A(A AB ， 4 ，I6B ， 3 ，5，I7A ， 4 ，IR R 8 C ， ，7，I9 B ， ，8 合取式10（C）11（ B C ） （ B C ）T，910，合取式，矛盾已知 R 和 S 黑空集合 A 上的等价系，试证 1）S是 A 的价关系； ）对 aA，R=a a 解：xA，由于 R 和 是自反关系，以是x,x、，因 x,xR故 S 是自反的.x 、 A， 、 ， 由于 R 和 S 是对称关系，以是 y,x、，此 RS， RS 是对称的.x y 、 z ，若 R 且 S ， 、 且 、 S由于 R 和 S 是传递的，以是因 因此 R ，故 RS 是递的 .总之 是等价关系.R R R R