离散复习附部分答案

一、范式1、 的RQP)(主合取范式为 )()()( RQP 。2、利用主析取范式，求公式 QP的类型。解、FRRQP)()()()(它无成真赋值，所以为矛盾式。3、求命题公式(PQ)( PR)的主合取范式。解：(PQ)(PR) （(PQ)(PR)）（ (PR)(PQ)）（(PQ)(PR)） （(PR)(PQ)）(PQ)(PR)(PR)（ QP）（ QR）(PQ R)(P QR)（PQR）（PQ R）M1M 3M 4M 54、设命题公式 G = (PQ)(Q( PR), 求 G 的主析取范式。G = (P Q)(Q(PR)= (P Q)(Q(PR)= (PQ)(Q(PR)= (PQ)(QP)(QR)= (PQ R)(P Q R)(PQR)(PQR)(PQR)(PQR)= (PQ R)(P Q R)(PQR)(PQR)(PQR)= m3m 4m 5m 6m 7 = (3, 4, 5, 6, 7).5、通过求主析取范式判断下列命题公式是否等价：(1) G = (PQ)( PQR) (2) H = (P(QR)(Q (P R)G(PQ)(P QR)(PQR)(PQR)( PQR)m 6m 7m 3 (3, 6, 7)H = (P(QR)(Q( PR)(PQ)(Q R) (PQR)(PQR)(PQR)( PQR)(PQR)(PQR)(PQR)(PQR) (PQR)m 6m 3m 7 (3, 6, 7)G,H 的主析取范式相同，所以 G = H.6、用等值演算法和真值表法判断公式 )()()( QPPA的类型。（1）等值演算法 TQPQPA )()()()()(（2）真值表法P Q )()(PPQA1 1 1 1 1 1 11 0 0 1 0 0 10 1 1 0 0 0 10 0 1 1 1 1 1所以 A 为重言式。7、设命题 A1，A 2 的真值为 1，A 3，A 4 真值为 0，求命题)()( 423的真值。 （5 分）11)0( 18、公式 )(QP的主合取范式是 二、推理证明1、叙述并证明苏格拉底三段论解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。符号化：F（x）：x 是一个人。G（x）：x 要死的。A：苏格拉底。命题符号化为x（F（x）G（x） ） ，F（a）G（a）证明：（1）x(F(x) G(x) P（2）F(a)G(a) T(1),US（3）F(a) P（4）G(a) T(2)(3),I2、设论域 D=a , b , c，求证： )()()( xBAxBxA。)( )()()xBAx cBAbaccacbcbaxBxA3、用反证法证明 RSQRP( 。4、用 CP 规则证明 )()(),P。5、演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。6、利用形式演绎法证明：AB, CB, CD蕴涵 AD。(1) A D(附加)(2) AB P(3) B Q(1)(2)(4) C B P(5) B C Q(4)(6) C Q(3)(5)(7) C D P(8) D Q(6)(7)(9) AD D(1)(8)所以 AB, CB, CD蕴涵 AD.7、 FEB, P（附加前提） ATI DCP TI DTI ETI FP TI ACP8、 )()()( xQxPQxP P（附加前提） )(cUS )(xxP )(QPUS cTI )(xUG )(CP9、所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。证明：设 P(x)：x 是个舞蹈者； Q(x) ：x 很有风度； S(x)：x 是个学生； a：王华上述句子符号化为：前提： )(QP、 )(aPS 结论： )(QS 3 分 )aSP xxP (US )TI .aTI (STI )QTI (xxEG10、符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草” 。并推证其结论。解： yxHxGxFxM喜 欢是 杂 草是 花是 人 :),(;:)(;:)(;:)(,yHyxyM)()(GF证明： ),(yxFyx P ),()()(yaHFyaMES TI ),()( TI ),(yxyGxP )()(aHaUS ,y TI )(),(yHTE zazFUS )(),(GUS TI )()(xxUG11、符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子” 。并推证其结论解：F(x)：x 是病人，G(x)：x 是医生，H(x)：x 是骗子，L(x,y)：x 相信 y符号化：前提： ),()()(yLGyF ),()()(xLHF结论： HG ),()()(xyx P yaLaFES )( TI ),(yGTI ),()( yxLyHxP )(aaFUS ,(yTI )(),yLTE (zazGUS )(),HUS (TI )()xxUG3、集合1、已知 A、B、C 是三个集合，证明 A(BC)=(AB)(AC)证明：x A（BC） x Ax（BC） x A（x BxC）（ x Ax B）（x AxC） x（ AB） x AC x（ AB） （AC） A（BC）=（AB）（AC）2、1设 7|),5()(| xEBNxA且且 （N：自然数集，E + 正偶数） 则 B 0，1，2，3，4，6； 。3、A，B，C 表示三个集合，文图中阴影部分的集合表达式为 )( 。4、 = 。） ）（ 5、集合 2,A的幂集= 2, 。)(并搜集为 ，交搜集为 6、 BAcba,214、二元关系1、 设 A=2，3，4，5，6上的二元关系 |,是 质 数xyxR，则 R= , （列举法） 。R 的关系矩阵 MR=0011。2、设集合 A= a ,b , c , d 上关系 R= , , , 要求 1、写出 R 的关系矩阵和关系图。 （4 分）2、用矩阵运算求出 R 的传递闭包。 （6 分）A BC01RM； 关系图2、 02RR0123RRM234 01RRR M,4635 RRM01432)( RRRtMt (R)= , , , , , , , , 。3、设 R 和 S 是集合 A a, b, c, d上的关系，其中 R(a, a),( a, c),(b, c),(c, d), S(a, b),(b, c ),(b, d),(d, d).(1) 试写出 R 和 S 的关系矩阵；(2) 计算 RS, RS, R 1 , S1 R1 .解、 (1) =01RM=10SM(2)RS(a, b),(c, d),RS(a, a),(a, b),( a, c),(b, c),(b, d),(c, d),(d, d), R1 (a, a),(c, a),( c, b),(d, c),S1 R1 (b, a),(d, c ).4、设 Aa，b，c ，d，R 是 A 上的二元关系，且 R ，求 r(R)、s(R)和 t(R)。解 r(R)R IA， ，s(R)RR -1，R2，R3，R4，R 2t(R) ，i15、设 R 是集合 A = a, b, c, d. R 是 A 上的二元关系, R = (a,b), (b,a), (b,c), (c,d),(1) 求出 r(R), s(R), t(R)；(2) 画出 r(R), s(R), t(R)的关系图.(1) r(R)RI A(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,b) (c,d), (d,c),t(R)RR 2R 3R 4(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)；(2)关系图:6、已知 A=1,2,3,4,5和 R=,，求 r(R)、s(R)和 t(R)。解：r(R)=,s(R)=,t(R)=,7、集合 4,321A上的关系 4,3,4,1,3,2, Rbacdr(R) bacds(R) bacdt(R)，写出关系矩阵 RM，画出关系图并讨论 R 的性质。解： 10RR 的关系图为 R 是自反、对称的。8、设 A=，1，1，3， 1，2，3则 A 上包含关系 “”的哈斯图为9、设 S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24， “”为 S 上整除关系，问：（1）偏序集S 的 Hass 图如何？（2）若 ，求 的极小元、最小元、极大元、最6432BB大元，上界，上确界，下界，下确界=,，,covS=, ,10、设 A=1，2，3，4，5，A 上的偏序关系为求 A 的子集3，4，5和1，2，3，的上界，下界，上确界和下确界，极大、极小元，最大最小元。11、集合 36,241,3A上的偏序关系为整除关系。设 12,6B，6,2C，试画出 的哈斯图，并求 A，B，C 的最大元素、极大元素、下界、上确界。解：的哈斯图为集合 最大元 极大元 下界 上确界A 无 24，36 无 无B 12 12 6，2，3 12C 6 6 无 612、设集合 A1, 2, 4, 6, 8, 12，R 为 A 上整除关系。(1) 画出半序集(A,R)的哈斯图；(2) 写出 A 的最大元，最小元，极大元，极小元；(3) 写出 A 的子集 B = 4, 6, 8, 12的上界，下界，最小上界，最大下界.解 (1)(2) 无最大元，最小元 1，极大元 8, 12; 极小元是 1.(3) B 无上界，无最小上界。下界 1, 2; 最大下界 2.13、设集合 A1, 2, 3, 4, 6, 8, 9, 12，R 为整除关系。（1）画出半序集(A,R)的哈斯图；（2）写出 A 的子集 B = 3,6,9,12的上界，下界，最小上界，最大下界；（3）写出 A 的最大元，最小元