1、易自考02324# 离散数学试题 第 1 页 共 4 页离散数学试题第一部分 选择题 一、单项选择题1下列是两个命题变元 p，q 的小项是（ C ）Appq BpqCpq Dppq2令 p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）Apq BpqCpq Dpq3下列语句中是命题的只有（ A ）A1+1=10 Bx+y=10Csinx+siny,I A，则对应于 R 的 A 的划分是（ D ）Aa,b,c,d Ba,b,c,dCa,b,c,d Da,b,c,d7设 A=，B=P(P(A)，以下正确的式子是（ A ）A, B B,BC,B D,B8设 X，Y，Z
2、 是集合，一是集合相对补运算，下列等式不正确的是（ 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+b易自考02324# 离散数学试题 第 2 页 共 4 页Ca*b=GCD(a,b)(a,b 的最大公约数)Da*b=a(mod b)10.设 R 和 S 是集合 A 上的关系,RS 必为反对称关系的是 ( )A当 R 是偏序关系,S 是等价关系; B 当 R 和 S
3、都是自反关系;C当 R 和 S 都是等价关系; D 当 R 和 S 都是传递关系11.设 R 是 A 上的二元关系,且 RRR,可以肯定 R 应是( D )A对称关系; B全序关系 ; C自反关系; D传递关系12设 R 为实数集，函数 f：RR ，f(x)=2 x，则 f 是（ ）A满射函数 B单射函数C双射函数 D非单射非满射CDACCDAADADB第二部分 非选择题二、填空题1设论域是a,b,c，则( x)S(x)等价于命题公式 S(a)S(b)S(c) ；( )S(x)等价于x命题公式 S(a)S(b) S(c) 。2设 R 为 A 上的关系，则 R 的自反闭包 r(R)= _R _
4、，对称闭包 s(R)= _R AI R。3某集合 A 上的二元关系 R 具有对称性，反对称性，自反性和传递性，此关系 R 是 _ ，其关系矩阵是 只有主对角线上元素为 1 。I三、计算题1 （4 分）如果论域是集合a,b,c，试消去给定公式中的量词： 。)0yx)(2用等值演算求下面公式的主析取范式。 )()(PQP易自考02324# 离散数学试题 第 3 页 共 4 页3用等值演算法求公式 的主合取范式。)()(QP4 （6 分）在偏序集中，其中 Z=1,2,3,4,6,8,12,14，是 Z 中的整除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元，最小上界和最大下界。易自考
5、02324# 离散数学试题 第 4 页 共 4 页5设集合 A=1,2,3,4,5,A 上的划分为 1,2,3,4,5,试求：1) 写出划分 诱导的等价关系 R；2) 写出关系矩阵 ；RM3) 画出关系图。6. 设 Aa，b，c ，d，R 是 A 上的二元关系，且 R，求 r(R)、s(R)和 t(R)。解 r(R)R IA， ，s(R)RR -1，易自考02324# 离散数学试题 第 5 页 共 4 页R2，R3，R4，R 2t(R) ，i17已知集合 A 和 B 且|A|=n，|B|=m，求 A 到 B 的二元关系数是多少？A 到 B 的函数数是多少？ 解：因为|P(AB)|=2|AB|=
6、2|A|B|=2mn，所以 A 到 B 的二元关系有 2mn 个。因为|BA|=|B|A|=mn，所以 A 到 B 的函数 mn 个。四、证明题1设 R 和 S 是二元关系，证明11)(SR2设 A=a,b,c,R=(a,a),(a,b),(b,c),验证 rs(R)=sr(R)。3设 R 是 A 上的二元关系，试证：R 是传递的当且仅当 ，其中 表示 。R22R易自考02324# 离散数学试题 第 6 页 共 4 页4证明下列结论：（1） RQP（2） DACBAB),(),()(解：（1）1 PQ P 附加前提2 P T，1，I 23 PQ T，2，I 14 PQR P5 R T，3，4，
7、I 36 PQR CP（2）1 D P 假设前提2 DA P3 A T，1，2，I 54 (AB)(AC) P5 AB T，4，I 2 6 B T，3，5，I 3 7 AC T，4，I 2 8 C T，3，7，I 3 9 BC T，6，8 ，合取式10 （BC） P11 （BC） （BC） T，9，10，合取式，矛盾易自考02324# 离散数学试题 第 7 页 共 4 页5. 已知 R 和 S 是非空集合 A 上的等价关系，试证：1）RS 是 A 上的等价关系；2）对aA，a RS =aRa S。解：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）因为 xa RS RS RS xa Rxa S xa Ra S所以a RS =aRa S。五、应用题1所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。 （论述域：所有人的集合）
