当前位置：文档之家› 《离散数学》练习题

《离散数学》练习题

第二部分:.集合

1.若集合A 上的关系R 是对称的，则1R -也是对称的。( )

2.数集合上的不等关系()≠可确定A 的一个划分。( )

3.设A ，B ，C 为任意集合，若A B A C ?=?，则 B C =。( )

4.函数的复合运算“。”满足结合律。 ( )

5.A ，B ，C 为任意集合，若 A B A C ?=? 则B C =。( )

6.设R 是实数集，R 上的关系R (){},2,,x y x y x y R =-<∈，则R 是相容关系。(

) 7.设,A ≤是偏序集，B A ?，则B 的极大元b B ∈且唯一。( )

8.设{}1,2A =，{}B a =，则()222A B A B ??=。（注其中 2A 为()A ?） ( )

9.设 {}0,1A =，{}1,2B =，则{}20,1,1,0,1,2,1,0,1,1,0,2A B ?=。( )

10.集合A 上的恒等关系是一个双射函数。( )

11.设A ，B 为任意集合，不能A B ? 且A B ∈。 ( )

12.设R 是集合A 上的关系，若12,R R 是对称的，则 12R R 也是对称的。( )

1. 设A ＝{}?，B ＝(())P P A ，下列各式中哪个是错的 ( )

A. B ??

B. {}B ??

C. {{}}B ?∈

D. {,{}}()P A ???

2. 设Z 为整数集，下面哪个序偶不构成偏序集 ( )

A. Z,

B. Z,?≤? (≤：小于等于)

C. Z,=?? (＝：等于关系)

D. Z,|?? (|：整除关系)

3. 设集合{}4,3,2,1=A ，A 上的二元关系{},4,3,4,2,3,2,1,1=R

则R 具有 ( )

A.自反性

B.对称性

C.传递性

D. 以上答案都不对

4. 设{}d c b a A ,,,=，下面哪一个是A 的划分（）

A.{}{}{}d c b a ,,,,Φ

B. {}{}d c b a ,,,

C. {}{}{}{}d a c b a ,,,,

D. {}{}{}c b a ,,

5. 设A ＝?，B={?,{?}}，则B A -是 ( )

A. {{?}}

B. {?}

C. {?,{?}}

D. ?

6. 下图描述的偏序集中，子集{b,e,f}的上界为 ( )

A. b,c

B. a,b

C. b

D. a,b,c

7. 设集合{}{}ΦΦ=,A , 则A 的幂集为： ( )

A. {}{

}ΦΦ, B. {}{}{}{}{}{}ΦΦΦΦΦ,,,, C. {}{}{}{

}ΦΦΦ,, D. {}{}{}{}{}{}{}ΦΦΦΦΦ,,,, 8. 若Q P Q P ?=?, 则P, Q 要满足的条件为（）

A. Q P ?

B. P Q ?

C. Q 为空集

D. P=Q

``````````````````````````````

9. 在０ ?之间应填入的符号为 ( )

A. ＝

B. ?

C. ∈

D. ?

10. 设,A ?≤?是偏序集，B A ?，下面结论正确的是 ( )

A. B 的极大元b B ∈且唯一

B. B 的极大元b A ∈且不唯一

C. B 的上界b B ∈且不唯一

D. B 的上确界b A ∈且唯一

11. 集合{}4,3,2,1=I , I 上的关系 R={4,43,44,1,3,3,3,2,23,1,1,1，则R 是（）

A. 反对称的

B. 传递的

C.反自反的

D. 自反的

12. 设S A B ??，下列各式中哪个是正确的 ( )

A. domS B ?

B. domS A ?

C. ranS A ?

D. domS ranS S ?=

13. 设A ＝｛1,2,3,4,5｝，下面哪个集合等于A ( )

A. ｛1,2,3,4,5,6｝

B. {x |x 是整数且225x ≤}

C. {x |x 是正整数且5x ≤}

D. {x |x 是正有理数且5x ≤}

14. 设A ＝｛｛1,2,3｝,{4,5},{6,7,8}｝，下列各式中哪个是错的 ( )

A. A ??

B. {6,7,8}A ∈

C. {{4,5}}A ?

D. {1,2,3}A ?

15. 设集合X ≠?，则空关系X ?不具备的性质是 ( )

A. 自反性

B. 反自反性

C. 对称性

D. 传递性

``````````````````````````````````````````````

16. 集合A 的一个划分，确定A 的元素间的关系为 ( )

A. 全序关系

B. 等价关系

C. 偏序关系

D. 拟序关系

17. 设{}d c b a A ,,,=，下面哪一个是A 的划分 ( )

(A) {}{}{}d c b a ,,,,Φ (B)

{}{}d c b a ,,, (C) {}{}{}{}d a c b a ,,,, (D) {}{}{}c b a ,,

18. 设集合A ＝{0, b }, B ={1, b , 3}, 则A ?B 上的恒等关系是 ( )

(A) {<0, 0>, <1, 1>, <3, 3>} (B){<0, 0>, <1, 1>, ,<3, 3>}

19. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ?C )= ( )

(A) {<1,c >,<2,c >} (B) {,<2,c >}

(C) {,} (D) {<1,c >,}

20. 设A , B , C 都是集合，如果A ?C ＝B ?C ，则有 ( )

(A) A ＝B (B) A ≠B

(C) 当A －C ＝B －C 时,有A =B (D) 当C =E 时, 有A ≠B

21. 设集合A ＝{?，a }，则幂集P (A )＝ ( )

(A){,{},{,}}a a ?? (B){{},{},{,}}a a ??

(C){,{},{},{,{}}},}a a A ??? (D){,{},{},{,}}a a ???

22. 集合A 上的等价关系R ，决定了A 的一个划分，该划分就是 ( )

A. 并集A R

B. 交集A R

C. 差集A R -

D. 商集/A R

23. 设1R 和2R 是集合A 上的任意关系，则下列命题为真的是 ( )

A. 若1R 和2R 是自反的，则12R R 也是自反的

B. 若1R 和2R 是反自反的，则12R R 也是反自反的

C. 若1R 和2R 是对称的，则12R R 也是对称的

D. 若1R 和2R 是传递的，则12R R 真也是传递的

24. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ?C )= ( )

(A) {<1,c >,<2,c >} (B) {,<2,c >}

(C) {,} (D) {<1,c >,}

25. 设A , B , C 都是集合，如果A ?C ＝B ?C ，则有 ( )

(A) A ＝B (B) A ≠B

(C) 当A －C ＝B －C 时,有A =B (D) 当C =E 时, 有A ≠B

26. 设集合A ＝{?，a }，则幂集P (A )＝ ( )

(A){,{},{,}}a a ?? (B){{},{},{,}}a a ??

(C){,{},{},{,{}}},}a a A ??? (D){,{},{},{,}}a a ???

27. 集合A 上的关系R 是相容关系的必要条件是 ( )

A. 自反的，反对称的

B. 反自反的，对称的

C. 传递的，自反的

D. 自反的，对称的

28. 集合{1,2,,10}A = 上的关系R={x,y |x+y=10 x,y }A ∈且

则R 的性质为 ( )

A. 自反的

B. 对称的

C. 传递的，对称的

D. 反自反的，传递的

29. 下面关于集合的表示中，正确的是 ( )

A. 0φ=

B. {}φφ∈

C. φφ∈

D. {,}a b φ∈

30. 设{}c b a A ,,=，{}2,1=B ，则从A 到B 的所有函数集合中有个函数。

（）

(A) 62 (B) 3

(C) 26 (D) 23

1. 由4个元素组成的有限集上有个等价关系

2. {0,1,2,3,4}A =±±±±，{,|,,12}R x y x y A y x y =??∈-<<+为A 上的关系，

令{}()|R x y xRy =，则(0)R =

3.设Q 为有理数集，笛卡尔积S Q Q =?；*是S 上的二元运算.(,),(,)a b x y S ?∈

有,,,a b x y ax y b *=+，则*运算的幺元是 .

4. 设偏序集,|A ??，其中A ＝{2，3，4，…，1000}，｜表示整除关系，那么该偏

序集的所有极大元构成的集合是

{}|,5011000x x A x ∈≤≤, 5. 设有向图D ＝的邻接矩阵为A (D )=0110001000010

011????????????

，那么 ∣E ∣＝

6.设Q 为有理数集，笛卡尔积S Q Q =?；*是S 上的二元运算.(,),(,)a b x y S ?∈

有,,,a b x y ax y b *=+，则,ab S ?∈；0a ≠，则,a b 的逆元是 . 7. 设A={1,2,10} ，那么A 上的自反、对称关系有个

8. 集合中的包含关系?具有

自反性，反对称性，传递性

9．设{}4321,,,x x x x X =，{}321,,y y y Y =，{111322,,,,,,R x y x y x y =

23314142,,,,,,,x y x y x y x y ，则关系矩阵=R M

10. 设A ＝{1,2,3}，R 是P(A)上的关系，且R ＝{a,b |a b }φ???≠．在自反、反自反、

对称、反对称、传递五种性质中，R 满足性质．

11. 设集合A ={?,{a }}，则A 的幂集P (A )=

12. 设21,R R 为{}4,3,2,1,0=A 上的关系，?

?????

=∨+==21,1i j i j j R ， {}2,2+==j i j R ，则=21R R

13. 设E 为全集，称为A 的绝对补，记作A ，且()A

＝．

14. 设A ＝｛a,b,c ｝，考虑下列子集

1{{,},{,}}S a b b c =，2{{},{,},{,}}S a a b a c =，3{{},{,}}S a b c =，

4{{,,}}S a b c =，5{{},{},{}}S a b c =，6{{},{,}}S a a c =

A 的覆盖有．

15. 集合{}{

}1,1,Φ的幂集为 16. 设A ＝｛2,a,{3},4｝，B ＝{{a},3,4,1}，请在下列每对集合中间填入适当的符号：

,∈?． (1)｛a ｝ B, (2) {a,4,{3}} A ．

17．全集E={1，2，3，4，5}，A={1，5}， B={2，5}，则ρ（A ）?ρ（B ）= ，（其中ρ（A ）为A 的幂集）

18. 设A ＝｛a,b,c ｝，考虑下列子集

1{{,},{,}}S a b b c =，2{{},{,},{,}}S a a b a c =，3{{},{,}}S a b c =，

4{{,,}}S a b c =，5{{},{},{}}S a b c =，6{{},{,}}S a a c =

A 的划分有．

19. 在自然数集中，偶数集为1N ，奇数集为2N ，则12N N ?=

20. 设X={1,2,3,4}，R={<1,2>,<2,4>,<3,3>}，则 s(R)＝

21. 设R 为集合A 的等价关系，对a A ?∈，集合[]R a ＝，称为元素a

形成的R 等价类，[]R a ≠?，因为

22. 设M={|112x x ≤≤，x 被2整除，x Z ∈}， N ＝{|112x x ≤≤，x 被3整

除，x Z ∈}，则 M N -＝．

23. 在一个有n 个元素的集合上，可以有种不同的关系．

24. 若关系R 是反对称的，当且仅当关系矩阵中，

以主对角线为对称的元素不能同时为1;

1. 集合A ＝{1,2,3,4}上的关系

R ＝{<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>}，写出关系矩阵R M ，画出

关系图并讨论R 的性质．

2. 给定集合{}e d c b a S ,,,,=，找出S 上的等价关系R ，此关系R 能够产生划分

{}{}{}{}e d c b a ,,,,，并画出关系图．

3. 设A ＝｛a,b,c ｝，A 上关系ρ＝{ a,a ,a,b ,b,c ,c,b

，求出 r(ρ)，s(ρ)和t(ρ)．

4. 如果集合A 上的关系R 和S 是自反的、对称的和传递的．证明：R S ?是A 上的等价

关系．

5.设A ＝{2,3,4,9}，B ＝{2,4,7,10,12}，从A 到B 的关系R ＝{,a A ∈,b B ∈且

a 整除b}，试给出R 的关系图和关系矩阵，并说明此关系是否为函数？为什么？

6. 集合A ＝{2,3,6,12,24,36} 上的偏序关系为整除关系．设B ＝｛6,12｝，

C ＝{2,3,6}，试画出的哈斯图，并求A ，B ，C 的最大元素、极大元素、下

界、上确界．

7. 设1R 和2R 是A 上的任意二元关系，如果1R 和2R 是自反的，12R R 是否也是自反的，

为什么？若1R 和2R 是对称的，12R R 是对称的吗?

8. 设A={1,2,3,,9} ，在A x A 上定义关系R ：,,,a b c d R ??????∈当且

仅当a+d=b+c ，证明R 是A A ?上的等价关系，并求出{2,5}R ??．

9. A={a,b,c}，构造A 上的二元运算*使得a b c *=，c b b *=，且*运算是幂等

的、可交换的，给出关于*运算的一个运算表，说明它是否可结合，为什么？

10. 设集合{}e d c b a A ,,,,=上二元关系为{

,,,,,,c a b a a a R =

,,,e a d a }

e e d d d e c c c e b c b b ,,,,,,,,,,,,，

验证,A R 为偏序集，画出哈斯图．

11. 设R 的关系图如图所示．

(1) 说明R 具有什么性质(指自反性、反自反性、对称性、反对称性、传递性)；

(2) 求2R 的集合表达式；

(3) 求r(R) 、s(R) 、t(R)的关系矩阵．

12. 画出下面偏序集（A ，≤）的哈斯图，并指出集合A 的最小元、最大元、极大元和极小

元．其中A={a ，b ，c ，d ，e}，≤={（a ，b ），（a ，c ），（a ，d ），（a ，e ），（b ，e ），（c ，e ），（d ，e ）}?I A ．

13. 证明若R 是A 上的自反关系．则1R R - 是A 上的自反、对称关系．

14. 设A ＝{1,2,3}，R 为A A ?上的等价关系，且,,,a b c d R ??????∈当且仅当ab=cd ，

(1) 设I 为A A ?的恒等关系，求R-I ；

(2) 求R 对应的A A ?的划分∏．

15. 试画出集合A ＝{1，2，3，4，5，6}在偏序关系“整除”下的哈斯图，并分别求出：

(1)集合A 的最大元、最小元、极大元和极小元；

(2)集合B ＝{2，3，6}的上界、下界、最小上界、最大下界．

第三部分：代数系统

1.在代数系统,S *中，若一个元素的逆元是唯一的，其运算*必定可结合。( )

2.每一个有限整环一定是域，反之也对。( )

3.任何循环群必定是阿贝尔群，反之亦真。( )

4.设(),A ∧∨是布尔代数，则(),A ∧∨一定为有补分配格。( )

5.设Q 为有理数集，Q 上运算*定义为max(,)a b a b *=，则 ,Q * 是半群。( )

6.阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。( )

7.群中可以有零元（对阶数大于一的群）。( )

8.循环群一定是阿贝尔群。( )

9.每一个链都是分配格。( )

1. 对自然数集合N ，哪种运算不是可结合的，运算定义为任,a b N ∈

( )

A. min(,)a b a b *=

B. 2a b a b *=+

C. 3a b a b *=+-

D. a b a b *=+ (mod3)

2. 任意具有多个等幂元的半群，它 ( )

A. 不能构成群

B. 不一定能构成群

C. 不能构成交换群

D. 能构成交换群

3. 循环群33,Z +的生成元为[][]1,2，它们的周期为 ( )

A. 5

B. 6

C. 3

D. 9

4. 设是环，则下列正确的是 ( )

A. 是交换群

B. 是加法群

C. 对*是可分配的

D. *对是可分配的

5. 下面集合哪个关于减法运算是封闭的 ( )

A. N

B. {2|}x x I ∈

C. {21|}x x I +∈

D. {x |x 是质数}

6. 具有如下定义的代数系统,G ?*?，哪个不构成群 ( )

A. G={1,10}，*是模11乘

B. G={1,3,4,5,9}，*是模11乘

C. G ＝Q(有理数集)，*是普通加法

D. G ＝Q(有理数集)，*是普通乘法

7. 设G ＝{23|,m n m n I *∈}，*为普通乘法．则代数系统,G ?*?的么元为 ( )

A.不存在

B. e ＝0023?

C. e ＝2×3

D. e ＝11

23--?

8. 任意具有多个等幂元的半群，它( A )

A. 不能构成群

B. 不一定能构成群

C. 必能构成群

D. 能构成交换群

9. 在自然数集N 上，下面哪个运算是可结合的，对任意a,b N ∈ ( )

A. a b a b *=-

B. max(,)a b a b *=

C. 5a b a b *=+

D. ||a b a b *=-

10. Q 为有理数集，Q 上定义运算*为a b a b ab *=+-，则,Q ?*?的幺元为

( )

A. a

B. b

C. 1

D. 0

11. 下面哪一种运算不是实数集R 上的二元运算？（）

A.数的加

B.数的减

C. 数的乘 (D) 数的除

12. ,G ?*?是群，则对* ( )

A. 满足结合律、交换律

B. 有单位元，可结合

C. 有单位元，可交换

D. 每元有逆元，有零元

13. 实数集R 的下列运算，哪个满足结合律？ ( ) A. n m n m -= B. ()n m n m +=2

1 C. n m n m 2+= D. 22n m n m +=

14. 下面哪一种运算不是实数集R 上的二元运算？ ( )

(A) 数的加 (B) 数的减

(C) 数的乘 (D) 数的除

15. 在代数系统中，整环和域的关系为 ( )

A. 整环一定是域

B. 域下一定是整环

C. 域一定是整环

D. 域一定不是整环

16. 具有如下定义的代数系统,G *，哪个不构成群 ( )

A. {1,10}G =，*是模11乘

B. {1,3,4,5,9}G =， *同(1)

C. G Q = (有理数集)，*是普通加法

D. G Q =，*是普通乘法

17. Q 为有理数集，,Q ? (其中?为普通乘法)不能构成 ( )

A. 群

B. 独异点

C. 半群

D. 交换半群

18.下述*运算为实数集上的运算，其中可交换且可结合的运算是 ( )

（A ）a*b=a+2b （B ）a*b=a+b-ab

（C ）a*b=a （D ）a*b=|a+b|

19. 设I 是整数集，+，分别是普通加法和乘法，则,,I + 是 ( )

A. 域

B. 整环和域

C. 整环

D. 含零因子环

20. R 为实数集，运算*定义为：,a b R ∈，||a b a b *= ，则代数系统,R *是 ( )

A. 半群

B. 独异点

C. 群

D. 阿贝尔群

21. 对自然数集合N ，哪种运算不是可结合的 ( )

A. min(,)a b a b *=

B. 3a b a b *=++

C. 2a b a b *=+

D. a b a b *=

(mod3) 22.为有理数集，Q 上定义运算*为：a b a b ab *=+-，则,Q *的么元是

( )

A. a

B. b

C. 1

D. 0

23. 设,H ，,K 是群,G 的子群，下面哪个代数系统仍是,G 的子群

( )

A. ,HK

B. ,H K

C. ,H K -

D. ,K H -

24. 群,R +与{0},R -? ( )

A. 同态

B. 同构

C. 后者是的前者的子群

D. (2)与(3)都正确

25. 在自然数集N 上，下面哪种运算是可结合的 ( )

A. a b a b *=-

B. max(,)a b a b *=

C. 2a b a b *=+

D. ||a b a b *=-

26. 循环群,I +的所有生成元为 ( )

A. 1,0

B. -1,2

C. 1，2

D. 1，-1

27. 任何一个有限群在同构的意义下可以看作是 ( )

A. 循环群

B. 置换群

C. 变换群

D. 阿贝尔群

28. 下列集合关于指定的运算哪一个可以构成群？（）

(A) 给定a >0且1≠a ，集合{}

Z n a G n ∈=关于数的乘法。 (B) 非负整数集N ，关于数的加法。

(C) 整数集Z ，关于数的减法。

(D) 一元实系数多项式集合，关于多项式乘法。

1. 在环中进行计算，则（a+b ）（a-b ）＝

2. S 是一非空集合, P(S)是S 的幂集, 代数系统(),P S 中的幺元为

3. 设群G ＝a ??是15阶循环群，则子群H ＝3a ??的元素是

4. 在A={1,2,...,10}与运算×11( 模11乘)构成的群中，元素5的阶是

5. 在代数系统,N +中， (其中N 为自然数集，+为普通加法)，仅有有逆元．

6. 给定环}5|,,x x I ∈+ ，其中I 是整数集，+和是普通的加法和乘法，

它整环．因为．

7. 设代数系统6,V Z =???，其中?为模6乘法，那么V 中的幂等元是 8. ,S *是独异点．对,a b S ∈，且,a b 均有逆元，则11

()a --= ，

9. 设S 是非空有限集，()P S 为S 的幂集，代数系统(),,P S ?? 中，()P S 对的么元为，零元为．

10. ,G *是群，B G ?且B 是有限集，,B *是,G *的子群当且仅当 ·

11. 设S 为非空有限集，代数系统2,S U ??中么元为，零元为

12.在A={1,2,...,10}与运算×11( 模11乘)构成的群中，元素5的阶是

13. 设S 是非空有限集，()P S 为S 的幂集，代数系统(),,P S ?? 中， ()P S 对的么元为，零元为．

14. 三阶群有个(不同构)，其运算表为

15.半群(),A ρ 是独异点，因为

有幺元A

1. 设 ||2G >，且a G ?∈，2

a =e ，证明G 必含4阶子群．

2. 己知G ＝｛1,2,3,4,5,6｝，7?为模7乘法．试说明7,G ???是否构成群?

是否为循环群？若是，生成元是什么？

3. 在乘法模7运算7*下，考虑群7,*G ，其中{}6,5,4,3,2,1=G ,

（1）求出7*的乘法表，（2）求1116,3,2---，

（3）7,*G 是循环群吗？

4. 试证明若,G ?*?是群，H G ?，且任意的a H ∈，对每一个x G ∈，有 a x x a *=*，则,H ?*?是,G ?*?的子群．

5. 设S=R-{-1} (R 为实数集)，a b a b ab *=++．

(1)说明,S ?*?是否构成群；

(2)在S 中解方程237x **=．

6. 若G 中只有一个2阶元，则这个2阶元一定与G 中所有元素可交换．

7. 设代数系统V=A, 的运算表如表所列，

表

a b c d a a b c d

b b

c b d

c c a b c

d d a c c

(1) 说明运算是否满足交换律、结合律、幂等律;

(2) 求出运算的单位元和零元(如果存在)；

(3) 求出所有可逆元素的逆元．

8．设G={

Q x x ∈且}1≠x ，定义xy y x y x -+= ，G y x ∈?, 证明： ,G 是一个群。

9. 设,H ?? 和,K ?? 都是群,G ?? 子群，问,H K ??? 和,H K ??? 是否是,G ?? 的子群，并说明理由．

10. 设2,G Z =?⊕?是模2加群

(1) 给出直积G G ?运算表；

(2) 说明G G ?与哪个4阶群同构．

11. 试画出集合A ＝{1，2，3，4，5，6}在偏序关系“整除”下的哈斯图，并分别求出：

(1)集合A 的最大元、最小元、极大元和极小元；

(2)集合B ＝{2，3，6}的上界、下界、最小上界、最大下界．

离散数学考试题详细答案

离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。（5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为（PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）

离散数学模拟题一套及答案

离散数学考试（试题及答案）一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())

下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。

(完整版)离散数学试卷及答案

离散数学试题（A卷答案）一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：甲说：王教授不是苏州人，是上海人。乙说：王教授不是上海人，是苏州人。丙说：王教授既不是上海人，也不是杭州人。王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有：甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。证明设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，，，，，，}， (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系，为什么？解 (1) R 的关系矩阵为： ??? ??? ? ? ? ?=100001100010100 10110 11111 )(R M (2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；ij r ＋ji r ≤1，故R 是反对称的；可计算对应的关系矩阵为：