哈尔滨理工大学
2004－2005学年第 一 学期考试答案 A 卷
考试科目： 离散数学 考试时间：120分钟 试卷总分100分
一、填空（本大题共5个空，每空2分，总计10分） 1、*2,,!,!m n
m m
n n C m m * 2、是
二、计算（本大题共2小题，每小题10分，总计20分）
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 P Q R P Q R ?∨∨∧∨?∨∧?∨?∨
()()()()()()
P Q R P Q R P Q R P Q R P Q R ?∧∧∨∧?∧∨∧?∧?∨?∧∧∨?∧?∧2、自反闭包(){1,2,2,2,2,4,3,4,1,1,3,3,4,4}r R =<><><><><><><>
对称闭包(){1,2,2,2,2,4,3,4,2,1,4,2,4,3}s R =<><><><><><><> 传递闭包(){1,2,2,2,2,4,3,4,1,4}r R =<><><><><>
三、证明（本大题共2小题，第1小题5分，第2小题10分，总计15分） 1、()()()()A B C A B C A C B A C B ?-=??=??=-?:: 2、()(()())()(()())()()()()x A x B x x A x B x x A x x B x ?→???∨???∨?
()()()()()()()(
)x A x x B x x A x x B x ???∨???→?
四、（本大题共15分）
P ：张三的彩票中奖了。Q ：李四的彩票中奖了。 R ：你知道张三的彩票中奖。S ：王五的彩票中奖了。
,,,P Q P R Q S R Q S ∨→→??∧
证明：(1)R
P ? (2)P R P → (3)(1)(2)P T I ? (4)P Q P ∨ (5)(3)(4)Q T I (6)Q S P → (7)(5)(6)S T I (8)(5)(7)Q S
T I ∧
五、（本大题共10分）
证明：对于,,a bi c di e fi C ?+++∈，有,,0a c e ≠ 因为0aa >，所以,a bi a bi R <++>∈，故R 是自反的。
若,a bi c di R <++>∈，则00,0,0ac ce ac ce ae >>>>g 且即得，所以,c di a bi R <++>∈，故R 是对称的。
若,a bi c di R <++>∈，,c di e fi R <++>∈则0,0ac ca >>即，所以
,a bi e fi R <++>∈，故R 是传递的。
综上：R 为等价关系。 六、（本大题10分）
证明：因为A B C D ::和，所以可作双射:,:f A B g C D →→。
定义:h A B C D ?→?，对于,,(),(),,a b A B f a d g b c d C D ?<>∈?=<>∈?有c= 对1,1,2,2,1,12,2a b a b A B a b a b ?<><>∈?<>≠<>， 设(1),2(2),1(1),2(2)f a c f a d g b d g b ===c1=，
当12a a ≠时，由于:f A B →是双射，所以1(1)(2)2c f a f a c =≠=，得
1,12,2c d c d <>≠<>；当12b b ≠时，由于:g C D →是双射，所以
1(1)(2)2d g c g c d =≠=，得1,12,2c d c d <>≠<>。故:h A B C D ?→?是入射。
对,c d C D ?<>∈?，因为:,:f A B g C D →→均为双射，所以,a A b B ?∈∈使得
(),()c f a d g b ==，,a b A B <>∈?。故:h A B C D ?→?是满射。
综上，故:h A B C D ?→?是双射。有A B C D ??:。
七、（本大题10分）对,,G b a ∈?设112223,23m n m n a b ==
G b a n n m m n m n m ∈=?=?++21212211323232，所以×封闭。
对,,,a b c G ?∈设112233
23,23,23m n m n m n a b c ===
112233112233()(2323)2323(2323)()m n m n m n m n m n m n a b c a b c ??=??=??=??，所以*
可结合。
a a a G a n m n m n m =?====?∈?++++001010110101003232323232,，所以0032为幺元。 11111100111111,2323232323m n m m n n m m n n m n a G a a -----+-+--?∈?====?，所以
11123m n a ---=。
综上：>*<,G 是群。
八、（本大题10分）因为对于,x y R ?∈有()()()x y
x y f x y e e e f x f y ++==?=?，所
以,,f R R <+>是从到的同态。
对于,,x y R x y ?∈≠有()()x y
f x e e f y =≠=，所以f R R 是从到的入射。
故,,f R R <+>是从到的单一同态。