离散数学练习题(含答案)

易自考02324#离散数学试题第1页共4页离散数学试题第一部分选择题一、单项选择题1．下列是两个命题变元p，q的小项是（C）A．p∧┐p∧qB．┐p∨qC．┐p∧qD．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（D）A．p→┐qB．p∨┐qC．p∧qD．p∧┐q3．下列语句中是命题的只有（A）A．1+1=10B．x+y=10C．sinx+siny0D．xmod3=24．下列等值式不正确的是（C）A．┐(x)A(x)┐AB．(x)(B→A(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))B．Q(x,z)→(y)R(x,y,z)C．Q(x,z)→(x)(y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={a,b,b,a,c,d,d,c}∪IA，则对应于R的A的划分是（D）A．{{a},{b,c},{d}}B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}}D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（A）A．{Ø,{Ø}}∈BB．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈BD．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（A）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（D）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)易自考02324#离散数学试题第2页共4页D．a*b=a(modb)10.设R和S是集合A上的关系,R∩S必为反对称关系的是(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)；(x)S(x)等价于命题公式S(a)∨S(b)∨S(c)。2．设R为A上的关系，则R的自反闭包r(R)=_R∪AI_，对称闭包s(R)=_R∪R~。3．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是AI_，其关系矩阵是只有主对角线上元素为1。三、计算题1．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：)0yx)(x)(y(。2．用等值演算求下面公式的主析取范式。)()(PQQP易自考02324#离散数学试题第3页共4页3．用等值演算法求公式)()(QPQP的主合取范式。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}},试求：1)写出划分诱导的等价关系R；2)写出关系矩阵RM；3)画出关系图。易自考02324#离散数学试题第4页共4页6.设A＝{a，b，c，d}，R是A上的二元关系，且R＝{a，b，b，a，b，c，c，d}，求r(R)、s(R)和t(R)。解r(R)＝R∪IA＝{a，b，b，a，b，c，c，d，a，a，b，b，c，c，d，d}s(R)＝R∪R-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)＝iiR1＝{a，b，b，a，b，c，c，d，a，a，a，c，b，b，b，d，a，d}四、证明题1．设R和S是二元关系，证明111)(SRSR易自考02324#离散数学试题第5页共4页2．设A={a,b,c},R={(a,a),(a,b),(b,c)},验证rs(R)=sr(R)。3．设R是A上的二元关系，试证：R是传递的当且仅当RR2，其中2R表示RR。4．证明下列结论：（1）RQPRQP（2）DADCBCABA),(),()(解：（1）1P∧QP附加前提2PT，1，I23P∨QT，2，I1易自考02324#离散数学试题第6页共4页4P∨Q→RP5RT，3，4，I36P∧Q→RCP（2）1DP假设前提2D∨AP3AT，1，2，I54(A→B)∧(A→C)P5A→BT，4，I26BT，3，5，I37A→CT，4，I28CT，3，7，I39B∧CT，6，8，合取式10（B∧C）P11（B∧C）∧（B∧C）T，9，10，合取式，矛盾5.已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R∩S=[a]R∩[a]S。解：x∈A，因为R和S是自反关系，所以x,x∈R、x,x∈S，因而x,x∈R∩S，故R∩S是自反的。x、y∈A，若x,y∈R∩S，则x,y∈R、x,y∈S，因为R和S是对称关系，所以因y,x∈R、y,x∈S，因而y,x∈R∩S，故R∩S是对称的。x、y、z∈A，若x,y∈R∩S且y,z∈R∩S，则x,y∈R、x,y∈S且y,z∈R、y,z∈S，因为R和S是传递的，所以因x,z∈R、x,z∈S，因而x,z∈R∩S，故R∩S是传递的。总之R∩S是等价关系。2）因为x∈[a]R∩Sx,a∈R∩Sx,a∈R∧x,a∈Sx∈[a]R∧x∈[a]Sx∈[a]R∩[a]S所以[a]R∩S=[a]R∩[a]S。五、应用题易自考02324#离散数学试题第7页共4页1．所有的主持人都很有风度。李明是个学生并且是个节目主持人。因此有些学生很有风度。请用谓词逻辑中的推理理论证明上述推理。（论述域：所有人的集合）