离散复习附部分答案.doc

1、一、范式 1、 RRQP )( 的 主合取范式为 )()()( RQPRQPRQP 。 2、 利用主析取范式，求公式 RQQP )( 的类型。 解、 FRQQPRQQPRQQPRQQP )()( )()()( 它无成真赋值，所以为矛盾式。 3、 求命题公式 (P Q)(PR)的主合取范式。 解： (P Q)(PR)（ (P Q)(PR)）（ (PR)(P Q)） （ (P Q) (P R)）（ (P R) (P Q)） (P Q) (P R) (P R)（ Q P）（ Q R） (P Q R) (P Q R)（ P Q R）（ P Q R） M1 M3 M4 M5 4、 设命题公式 G = (

2、P Q) (Q (P R), 求 G 的主析取范式。 G = (P Q) (Q (P R) = (P Q) (Q (P R) = (P Q) (Q (P R) = (P Q) (Q P) (Q R) = (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) = (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) = m3 m4 m5 m6 m7 = (3, 4, 5, 6, 7). 5、 通过求主析取范式判断下列命题公式是否等价： (1) G = (P Q) (P Q R) (2) H = (P (Q R) (Q (P R)

3、 G (P Q) (P Q R) (P Q R) (P Q R) (P Q R) m6 m7 m3 (3, 6, 7) H = (P (Q R) (Q (P R) (P Q) (Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) (P Q R) m6 m3 m7 (3, 6, 7) G,H 的主析取范式相同，所以 G = H. 6、用等值演算法和真值表法判断公式 )()()( QPPQQPA 的类型。 （ 1） 等值演算法 TQPQPQPPQQPA )()()()()( （ 2） 真值表法 P Q QP PQ

4、 )()( PQQP QP A 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 所以 A 为重言式 。 7、设命题 A1， A2 的真值为 1， A3， A4 真值为 0，求命题 )() ) )( 421321 AAAAAA 的真值。（ 5 分） 1111)01( 1)01(1()11()001(1( 8、公式 )()( QPPQ 的主合取范式是 二、推理证明 1、叙述并证明苏格拉底三段论 解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化： F（ x）： x 是一个人。 G（ x）： x 要死的。 A：苏格拉底。

5、 命题符号化为 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),I 2、设论域 D=a , b , c，求证： )()()()( xBxAxxxBxxA 。 )()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(xBxAxcBcAbBbAaBaAcBcAbBcAaBcAcBbAbBbAaBbAcBaAbBaAaBaAcBbBaBcAbAaAxxBxxA3、用反

6、证法证明 RSSQRPQP )()()( 。 4、用 CP 规则证明 )()(),( SQPSQRRQP 。 5、演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，虚数既不是有理数，也不是无理数。 6、利用形式演绎法证明： A B, C B, C D蕴涵 A D。 (1) A D(附加 ) (2) A B 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) A D D(1)(8) 所以 A B, C B, C D蕴涵 A D. 7、 FAFEDDCBA , A

7、P（附加前提） BA T I DCBA P DC T I D T I ED T I FED P F T I FA CP 8、 )()()()( xxQxxPxQxPx )(xxP P（附加前提） )(cP US )()( xQxPx P )()( cQcP US )(cQ T I )(xxQ UG )()( xxQxxP CP 9、所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生 很有风度。 证明：设 P(x)： x 是个舞蹈者； Q(x) ： x 很有风度； S(x)： x 是个学生； a：王华 上述句子符号化为： 前提： )()( xQxPx 、 )()( aPaS 结论：

8、)()( xQxSx 3 分 )()( aPaS P )()( xQxPx P )()( aQaP US )(aP T I ).(aQ T I )(aS T I )()( aQaS T I )()( xQxSx EG 10、符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。 解 ： yxyxHxxGxxFxxM 喜欢是杂草是花是人 :),(;:)(;:)(;:)( ),()()( yxHyFyxMx ),()()( yxHyGyxMx )()( xGxFx 证明： ),()()( yxHyFyxMx P ),()()( yaHyFyaM ES )(aM T

9、I ),()( yaHyFy T I ),()()( yxHyGyxMx P ),()()( yaHyGyaM US ),()( yaHyGy T I )(),( yGyaHy T E ),()( zaHzF US )(),( zGzaH US )()( zGzF T I )()( xGxFx UG 11、符号化语句：“有些病人相信所有的医生，但是病人都不相信骗子，所以医生都不是骗子”。并推证其结论 解： F(x)： x 是病人， G(x)： x 是医生， H(x)： x 是骗子， L(x,y)： x 相信 y 符号化：前提： ),()()( yxLyGyxFx ) ) ),()()( yxL

10、yHyxFx 结论： )()( xHxGx ),()()( yxLyGyxFx P ),()()( yaLyGyaF ES )(aF T I ),()( yaLyGy T I ) ) ),()()( yxLyHyxFx P ),()()( yaLyHyaF US ),()( yaLyHy T I )(),( yHyaLy T E ),()( zaLzG US )(),( zHzaL US )()( zHzG T I )()( xHxGx UG 三、 集合 1、已知 A、 B、 C 是三个集合，证明 A (B C)=(A B) (A C) 证明： x A（ B C） x A x（ B C） x

11、A（ xB xC） （ x A xB）（ x A xC） x（ A B） x A C x（ A B）（ A C） A（ B C） =（ A B）（ A C） 2、 1设 7|) ,5()(| xExxBxNxxA 且且（ N：自然数集， E+ 正偶数） 则 BA 0， 1， 2， 3， 4， 6； 。 3、 A， B， C 表 示三个集合，文图中阴影部分的集合表达式为 ACB )( 。 4、 ）（ = 。 5、 集合 2,2,A 的幂集 )(A = 2,2, ,2 ,2, 。 并搜集为 2, ，交搜集为 6、 BAcbaBA ,2,1 四、 二元关系 1、 设 A=2， 3， 4， 5， 6上

12、的二元关系 |, 是质数xyxyxR ，则 R= , （列举法）。 R 的关系矩阵 MR= 0000011111110001111111111。 2、设集合 A= a ,b , c , d 上关系 R= , , , A B C 要求 1、写出 R 的关系矩阵和关系图。（ 4 分） 2、用矩阵运算求出 R 的传递闭包。（ 6 分） 0000100001010010RM； 关系图 2、 00000000101001012 RRR MMM 000000000101101023 RRR MMM 2340000000010100101RRRR MMMM , 4635 RRRR MMMM 00001000

13、11111111432)( RRRRRt MMMMM t (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, R S, R 1, S 1R 1. 解、 (1)0000100001000101RM 1000000011000010SM (2)RS (a, b),(c, d), R S (a, a),(a, b),(a, c),(b, c),(b, d

14、),(c, d),(d, d), R 1 (a, a),(c, a),(c, b),(d, c), S 1R 1 (b, a),(d, c). 4、 设 A a， b， c， d， R 是 A 上的二元关系，且 R ， ， ， ，求 r(R)、 s(R)和 t(R)。 解 r(R) R IA ， ， ， ， ， ， ， s(R) R R-1 ， ， ， ， ， R2 ， ， ， R3 ， ， ， R4 ， ， ， R2 t(R) ii R1 ， ， ， ， ， ， ， ， 5、设 R 是集 合 A = a, b, c, d. R 是 A 上的二元关系 , R = (a,b), (b,a), (

15、b,c), (c,d), (1) 求出 r(R), s(R), t(R)； (2) 画出 r(R), s(R), t(R)的关系图 . (1) 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,b) (c,d), (d,c), t(R) R R2 R3 R4 (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=,

16、，求 r(R)、 s(R)和 t(R)。 解： r(R)=, s(R)=, t(R)=, 7、集合 4,3,2,1A 上的关系 bacdr (R )bacds( R )bacdt( R )4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1 R，写出关系矩阵 RM ，画出关系图并讨论 R 的性质。 解： 1100110100100101RMR 的关系图为 R 是自反、对称的。 8、设 A= ， 1， 1， 3， 1， 2， 3则 A 上包含关系“ ”的哈斯图为 9、设 S=1 , 2 , 3 , 4, 6 , 8 , 12 , 24，“ ”为 S 上整除关系，问：（ 1）偏序集 ,S

17、 的Hass 图如何？（ 2） 若 6,4,3,2B ，求 B 的极小元、最小元、极大元、最大元，上界，上确界，下界，下确界 =, ，,covS=, , 10、设 A=1， 2， 3， 4， 5， A 上的偏序关系为 求 A 的子集 3， 4， 5和 1， 2， 3，的上界，下界， 上确界和下确界，极大、极小元，最大最小元。 11、集合 36,24,12,6,3,2A 上的偏序关系 为整除关系。设 12,6B ，6,3,2C ，试画出 的哈斯图，并求 A， B， C 的最大元素、极大元素、下界、上确界。 解： 的哈斯图为 集合 最大元 极大元 下界 上确界 A 无 24， 36 无 无 B 1

18、2 12 6， 2， 3 12 C 6 6 无 6 12、设集合 A 1, 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、设集合 A 1, 2, 3, 4, 6, 8, 9, 12， R 为整除关系。 （ 1）画出半序集 (A,R)的哈斯图； （ 2）写出 A 的子集 B = 3,6,9,12的上界，下界，最小上界，最大下界； （ 3）写出 A 的最大元，最小元，极大元，极小元。 (1) (2) B 无上界，也无最小上界。下界 1, 3; 最大下界是 3. (3) A 无最大元，最小元是 1，极大元 8, 12, 90+; 极小元是 1. 14、设 A=a,b,c,d， A 上的二元关系 R=,，求 R 所诱导的等价关系，并求出等价关系中各元 素的等价类。 15、设 X=1,2,3,4,5， X 上的关系 R= , , , , ，求 R24168 12124836129