离散数学课后习题.doc

1、 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？ ( ) (1) Q=Q P (2) Q=P Q (3)P=P Q (4) P (P Q)= P 答：（ 1），（ 4） 2、下列公式中哪些是永真式？ ( ) (1)( P Q) (Q R) (2)P (Q Q) (3)(P Q) P (4)P (P Q) 答：（ 2），（ 3），（ 4） 3、设有下列公式，请问哪几个是永真蕴涵式 ?( ) (1)P=P Q (2) P Q=P (3) P Q=P Q (4)P (P Q)=Q (5) (P Q)=P (6) P (P Q)= P 答：（ 2），（ 3），（ 4），（ 5），（

2、6） 4、公式 x(A(x)B(y， x) z C(y， z)D(x)中，自由变元是 ( )，约束变元是 ( )。 答： x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。 ( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若 7+8 18，则三角形有 4 条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（ 1） 是， T （ 2） 是， F （ 3） 不是 （ 4） 是， T （ 5） 不是 （ 6） 不是 6、命题“存在一些人是大学生”的否定是 ( )，而命题“所有的人都是要死的”的否定是 ( )。 答：所有人

3、都不是大学生，有些人不会死 7、设 P：我生病， Q：我去学校，则下列命题可符号化为 ( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校 (4) 若我不生病，则我一定去学校 答：（ 1） PQ （ 2） QP （ 3） QP （ 4） QP 8、设个体域为整数集，则下列公式的意义是 ( )。 (1) xy(x+y=0) (2) yx(x+y=0) 答：（ 1）对任一整数 x 存在整数 y 满足 x+y=0（ 2）存在整数 y 对任一整数 x 满足 x+y=0 9、设全体域 D 是正整数集合，确定下列命题的真值： (1) xy (

4、xy=y) ( ) (2) xy(x+y=y) ( ) (3) xy(x+y=x) ( ) (4) xy(y=2x) ( ) 答：（ 1） F （ 2） F （ 3） F （ 4） T 11、命题“ 2 是偶数或 -3 是负数”的否定是（ ）。 答： 2 不是偶数且 -3 不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)-(3)均有可能 答：（ 2） 13、公式 ( P Q) ( P Q)化简为（ ），公式 Q (P (P Q)可化简为（ ）。 答： P ， Q P 15、令 R(x):x 是实数， Q(x):x 是有理数。则命题“并非每

5、个 实数都是有理数”的符号化表示为（ ）。 答： x(R(x) Q(x) （二元关系部分） 28、设 1,2,3,4,5,6， B=1,2,3，从到 B 的关系 x,y |x=y2，求 (1)R (2) R-1 。 答：（ 1） R=, (2) R1 =, 29、举出集合 A 上的既是等价关系又是偏序关系的一个例 子。 ( ) 答： A 上的恒等关系 30、集合 A 上的等价关系的三个性质是什么？ ( ) 答：自反性、对称性和传递性 31、集合 A 上的偏序关系的三个性质是什么？ ( ) 答：自反性、反对称性和传递性 32、设 S= , , , ，上的关系 1,2， 2,1， 2,3， 3,4

6、 求 (1)R R (2) R-1 。 答： R R = 1,1， 1,3， 2,2， 2,4 R-1 = 2,1， 1,2， 3,2， 4,3 33、设 1， 2， 3， 4， 5， 6，是 A 上的整除关系，求 R= ( )。 答： R=, , 34、设 1,2,3,4,5,6， B=1,2,3，从到 B 的关系 x,y |x=2y，求 (1)R (2) R-1 。 答：（ 1） R=, (2) R1 =,(3， 6 35、设 1,2,3,4,5,6， B=1,2,3，从到 B 的关系 x,y |x=y2，求 R 和 R-1的关系矩阵。 答： R 的关系矩阵 =00000000100000

7、0001R1 的关系矩阵 =000000010000000001 36、集合 A=1,2, ,10上的关系 R=|x+y=10,x,yA，则 R 的性质为（ ）。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 答：（ 2） （代数结构部分） 37、设 A=2,4,6， A 上的二元运算 *定义为： a*b=maxa,b，则在独异点 中，单位元是 ( )，零元是 ( )。 答： 2， 6 38、设 A=3,6,9， A 上的二元运算 *定义为： a*b=mina,b，则在独异点 中，单位元是 ( )，零元是 ( )； 答： 9， 3 （半 群与群部分） 39、设 G,*

8、是一个群，则 (1) 若 a,b,x G， a x=b，则 x=( )； (2) 若 a,b,x G， a x=a b，则 x=( )。 答： （ 1） a 1 b （ 2） b 40、设 a 是 12 阶群的生成元， 则 a2是 ( )阶元素， a3是 ( )阶元素。 答： 6,4 41、代数系统 是一个群，则 G 的等幂元是 ( )。 答：单位元 42、设 a 是 10 阶群的生成元， 则 a4是 ( )阶元素， a3是 ( )阶元素。 答： 5， 10 43、群 的等幂元是 ( )，有 ( )个。 答：单位元， 1 44、素数阶群一定是 ( )群 , 它的生成元是 ( )。 答：循环群，

9、任一非单位元 45、设 G,*是一个群， a,b,c G，则 (1) 若 c a=b，则 c=( )； (2) 若 c a=b a，则 c=( )。 答：（ 1） b 1a (2) b 46、 是 的子群的充分必要条件是 ( )。 答： 是群 或 a， b G， a bH， a-1H 或 a,b G， a b-1H 47、群 A,*的等幂元有 ( )个，是 ( )，零元有 ( )个。 答： 1，单位元， 0 48、在一个群 G,*中，若 G 中的元素 a 的阶是 k，则 a-1的阶是 ( )。 答： k 49、在自然数集 N 上，下列哪种 运算是可结合的？（ ） (1) a*b=a-b (2)

10、 a*b=maxa,b (3) a*b=a+2b (4) a*b=|a-b| 答： (2) 50、任意一个具有 2 个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群 答： (1) 51、 6 阶有限群的任何子群一定不是（ ）。 (1) 2 阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 答： (3) （数理逻辑部分） 二、求下列各公式的主析取范式和主合取范式： 1、 (P Q) R 解： (P Q) R ( P Q ) R ( P R) (Q R) （析取范式） ( P (Q Q) R) ( P P) Q R) ( P Q R) (

11、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)（原公式否定的主析取范式） (P Q) R (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)（主合取范式） 2、 (P R) (Q R) P 解： (P R) (Q R) P（析取范式） (P (Q Q) R) (P P) Q R) ( P (Q Q) (R R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)

12、 ( 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 R) (Q R) P） (P Q R) (P Q R）（原公式否定的主析取范式） (P R) (Q R) P ( P Q R) ( P Q R)（主合取范式） 3、 ( P Q) (R P) 解： ( P Q) (R P) (P Q) (R P)（合取范式） (P Q (R 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

13、R)（主合取范式） ( P Q) (R P) (P Q R) ( P Q R) ( P Q R) ( P Q R) ( P Q R)（原公式否定的主合取范式） (P Q) (R P) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R) （主析取范式） 4、 Q (P R) 解： Q (P R) Q P R（主合取范式） （ Q (P R)） ( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R）（原公式否定的主合取范式） Q (P R) (P Q R) (P Q R) (P Q R) (P Q R)

14、( P Q R) ( P Q R) ( P Q R）（主析取范式） 5、 P (P (Q P) 解： P (P (Q P) P (P ( Q P) P P T (主合取范式 ) ( P Q) ( P Q) (P Q) (P Q)（主析取范式） 6、 (P Q) (R P) 解： (P Q) (R P) ( P Q) (R P) (P Q) (R P)（析取范式） (P Q (R 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) (P Q R) ( P Q R)

15、 ( P Q R) ( P Q R) ( P Q R)（原公式否定的主析取范式） (P Q) (R P) ( P Q R) (P Q R) (P Q R) (P Q R) (P Q R)（主合取范式） 7、 P (P Q) 解： P (P Q) P ( P Q) (P P) Q T(主合取范式 ) ( P Q) ( P Q) (P Q) (P Q)（主析取范式） 8、 (R Q) P 解： (R Q) P ( R Q ) P ( R P) (Q P) （析取范式） ( R (Q Q) P) ( R R) Q P) ( R Q P) ( R Q P) ( R Q P) (R Q P) (P Q

16、R) (P Q R) (P Q R)（主析取范式） (R Q) P) ( P Q R) ( P Q R） (P Q R) ( P Q R) ( P Q R)（原公式否定的主析取范式） (R Q) P (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R)（主合取范式） 9、 P Q 解： P Q P Q（主合取范式） ( P (Q Q) ( P P) Q) ( P Q) ( P Q) ( P Q) (P Q) ( P Q) ( P Q) (P Q)（主析取范式） 10、 P Q 解： P Q （主合取范式） (P ( Q Q) ( P P) Q） (P Q) (P Q

17、) ( P Q) (P Q） (P Q) (P Q) ( P Q)（主析取范式） 11、 P Q 解： P Q（主析取范式） (P (Q Q) (P P) Q) (P Q) (P Q) (P Q) ( P Q) (P Q) (P Q) ( P Q)（主合取范式） 12、（ P R） Q 解：（ P R） Q (P R) Q ( P R) Q ( P Q) ( R Q)（合取范式） ( P Q (R R) ( P 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

18、 R) (P Q R)（主合取范式） （ P R） Q ( P Q R) ( P Q R) (P Q R) (P Q R) (P Q R) （原公式否定的主析取范式） （ P R） Q (P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)（主析取范式） 13、（ P Q） R 解：（ P Q） R ( P Q) R (P Q) R(析取范式 ) (P Q (R R) (P 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) ( P Q R) (

19、 P Q R)(主析取范式） （ P Q） R ( P Q) R (P Q) R(析取范式 ) (P R) ( Q R)(合取范式 ) (P (Q Q) R) (P P) Q R) (P Q R) (P Q R) (P Q R) ( P Q R) (P Q R) (P Q R) ( P Q R)(主合取范式 ) 14、 (P (Q R) ( P ( Q R) 解： (P (Q R) ( P ( Q R) ( P (Q R) (P ( Q R) ( P Q) ( P R) (P Q) (P R)（合取范式） ( P Q (R R) ( P (Q Q) R) (P Q (R R) (P (Q Q)

20、 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) (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)(主析取范式 ) 15、 P ( P (Q ( Q R) 解： P ( P (Q ( Q R) P (P (Q (Q R) P Q R(主合取范式 ) (P Q R

21、) (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) (P Q R) (P Q R) (P Q R)(主析取范式 ) 16、 (P Q) (P R) 解、 (P Q) (P R) ( P Q) ( P R) (合取范式 ) ( P Q (R 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)(主合取范式

22、) (P Q) (P R) ( P Q) ( P R) P (Q R)(合取范式 ) ( P (Q Q) (R R) ( P 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) (主析取范式 ) 三、 证明： 1、 P Q， Q R， R， S P= S 证明： (1) R 前提 (2) Q R 前提 (3) Q （ 1），（ 2） (4) P Q 前提 (5) P （ 3），（ 4） (6) S P 前提 (7) S （ 5），（ 6） 2、 A (B C)， C ( D E)， F (D E),A=B F 证明： (1) A 前提 (2) A (B C) 前提 (3) B C （ 1），（ 2）