离散数学结构试题集1-4

第1章

一.填空题 1.

2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。 3. 4. 5. 6.

7. 全体小项的析取式必为____________________式。

8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。

9. P,Q为两个命题，则吸收律可表示为____________________ 。

10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13. 14.

15. 设P、Q为两个命题，交换律可表示为____________________。 16.

17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________ 。

18. 19. 20.

21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为_______________ _____。 22. 23.

24. 一个重言式和一个矛盾式的合取是____________________。

25. 全体小项的析取式为____________________ 。

26. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________。

27.

28. 设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为____________________。 29. 30.

二.选择题 1. 2.

3. 在除﹁之外的四大联结词中，满足结合律的有几个( )。 A. 2 B.3 C. 4 D. 1

4. 判断下列语句哪个是命题( )。

A.你喜欢唱歌吗？ B.若7+8＞18，则三角形有4条边。 C.前进！ D. 给我一杯水吧！

5. 6. 7.

8. 永真式的否定是（ ） A. 永真式 B. 永假式 C. 可满足式 D. A--D均有可能

9. 下面哪一个是假命题（ ）。 A.如果2是偶数，那么一个公式的析取范式唯一。

B.如果2是偶数，那么一个公式的析取范式不唯一。 C. 如果2是奇数，那么一个公式的析取范式唯一。

D. 如果2是奇数，那么一个公式的析取范式不唯一。

10. 设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班 ”的符号化形式为( )。

A. p→q B. q→p C. p→┐q D. ┐p→q

11. 设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好 成绩”的符号化形式为( )。 A.p→q B.q→p C.┐q→p D.┐p→q

12. 下面4个推理定律中，不正确的为( )。

A.A=>(A∨B) (附加律) B.(A∨B)∧┐A=>B (析取三段论) C.(A→B)∧A=>B (假言推理) D.(A→B)∧┐B=>A (拒取式)

13. 使命题公式p→(p∧q)为假的赋值是 ( )。

A.10 B.01 C. 00 D.11

14. 令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ）。 A. p∧┐q B．p∨┐q C.p∧q D．p→┐q

15. 一个公式在等价意义下，下面哪个写法是唯一的（ ）。 Ａ．析取范式 B．合取范式 Ｃ．主析取范式 D．以上答案都不对

16. 令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符化 为（ ）。 A．p→┐q B．p∨┐q C．p∧q D．p∧┐q

17. 下列各组公式中哪组互为对偶（ ）。(P为原子命题，A为复合命题) A. P,P B. P, ┐P C. A, (A*)* D. A,A

18. 19. 20. 21. 22. 23. 24.

25. 下列语句哪个是命题（ ）。 A.9+5?12 B. x+3=5 C.我用的计算机CPU主频是1G吗？ D 我正在说谎。

26.

27.

28. n个命题变元可产生（ ）个互不等价的大项。

A. n B. n

2

C. 2n D. 2

n

29. 下列各命题中真值为真的命题有（ ）。

A.2+2=4当且仅当3是奇数 B.2+2=4当且仅当3不是奇数 C.2+2≠4当且仅当3是奇数 D.2+2≠5当且仅当3不是奇数

30. 下列语句哪个不是命题（ ）。

A.雪是黑的。 B. 天气多好啊！

C.今天下雨。 D 我学英语，或者我学日语。

三.判断题

1. “我正在说谎。”是一个命题。 （ ）

2. 一个命题标识符如表示确定的命题，就称为命题常量。（ ）

3. “她昨天做了一顿或两顿饭。”是个原子命题。（ ）

4. 命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一 个命题。（ ）

5. 如果A和B是合式公式，那么(A→ B)是合式公式。（ ）

6. 原子谓词公式是合式公式。（ ）

7. 一般来说，n个命题变元组成的命题公式共有2n中真值情况。（ ）

8. 任何两个重言式的合取或析取，仍然是一个重言式。（ ）

9. 重言式和矛盾式的析取是重言式。（ ）

10. 在真值表中，一个公式的真值为F的指派所对应的大项的析取，即为此公式的主析取范式。（ ）

11. 从假的命题出发，能证明任何命题。（ ）

12. 全体小项的析取式永为假 。（ ）

13. 连接词↑和↓是可交换的，也是可结合的。（ ）

14. P→Q =〉P→P∧Q。（ ）

15. 由n个命题变元组成不等值的命题公式的个数为2n。（ ）

四.计算题 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.

15.

五.证明题 1. 2. 3.

第2章

一.填空题 1. 2. 3. 4. 5. 6.

7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17 18. 19. 20. 21. 22.

23. 24. 25.

二.选择题 1. 2. 3. 4.

5. 6. 7. 8. 9. 10. 11.

12. 13. 14. 15. 16. 17. 18.

19. 20. 21. 22. 23. 24. 25. 26.

27. 28. 29. 30.

三.判断题

1. “如果1+2=3，则4+5=9。”是真命题。（ ）

2. 约束变元换名时，一定要更改为作用域中没有出现的变元名称。（ ） 3.

4. 简单命题函数由一个谓词和一些客体变元组成。（ ）

5. 单独一个谓词，不是完整的命题。（ ）

6. 任意一个谓词公式均和一个前束范式等价。（ ） 7. 8. 9. 10.

11. 12. 13. 14. 15.

四.计算题 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

五.证明题 1. 2. 3. 4.

第3章

一.填空题

1. 设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A∪B=_________________。

2. A，B，C表示三个集合，图中阴影部分的集合表达式为____________________。

3. 设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},则A°B=_______________。

4. 设A={1，2，3，4}，A上二元关系R={<1，2>，<2，1>，<2，3>，<3，4>}画出R的关系图_

________________。

16. 设R，S是集合A上的关系，则下列（ ）断言是正确的。

17. 设X为集合，|X|=n，在X上有（ ）种不同的关系。 A、n2； B、2n； C、22^n； D、2n^2。

18. 下图描述的偏序集中，子集{b,e,f}的上界为 （ ）。

A、R,S自反的，则R°S是自反的；

B、若R,S对称的，则R°S是对称的； C、若R,S传递的，则R°S是传递的； D、若R,S反对称的，则R°S是反对称的

A、b,c ； B、a,b ； C、 b； D、a,b,c。

19. 设R，S是集合A上的关系，则下列说法正确的是（ ）。

A．若R，S 是自反的， 则R°S是自反的； B．若R，S 是反自反的， 则R°S是反自反的； C．若R，S 是对称的， 则R°S是对称的；

D．若R，S 是传递的， 则R°S是传递的。

20. 设R是集合A上的二元关系，IA是A上的恒等关系，IA?R下面四 个命题为真的是 ( )。 A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的

21. 已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ） A．10 B．5 C．20 D．13

22. 设X，Y，Z是集合，下列结论不正确的是（ ）。 A．若X?Y,则X∩Y=X B．(X-Y)-Z=X-(Y∩Z) C．X ⊕X=? D．X-Y=X∩(~Y)

23. 设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划 分是（ ）。

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

24. 设R是集合A上的二元关系，IA是A上的恒等关系，IA?R下面四个命题为真的是 ( ) A.R是自反的 B.R是传递的 C.R是对称的 D.R是反对称的

25. 集合A={1，2，3，4}，则对 A 的元素进行划分正确的是（ ）

A. {,{1,2},{3,4}} B. {{1,2,3},{3,4}} C. {{1},{3,4}} D. {{1,2,3,4}}

26. 设集合A={2,{a},3,4}，B = {{a},3,4,1}，E为全集，则下列命题正确的是( )。 (A){2}?A (B){a}?A (C)??{{a}}?B?E (D){{a},1,3,4}?B

27. 设集合A={1,2,3},A上的关系R＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则R不具备( ). (A)自反性 (B)传递性 (C)对称性 (D)反对称性

28. 设A, B为集合，当( )时A－B＝B. (A)A＝B (B)A?B (C)B?A (D)A＝B＝?.

29. 设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( )。

(A)自反性 (B)传递性 (C)对称性 (D)以上答案都不对

30. 下列关于集合的表示中正确的为( )。 (A){a}?{a,b,c} (B){a}?{a,b,c} (C)??{a,b,c} (D){a,b}?{a,b,c}

31. 设R和S是集合A上的关系，若R和S是传递的，则（ ） (A) R∩S是传递的； (B) R∪S是传递的；

(C) R°S是传递的； (D) 以上都不对。

32. 设集合X为人的全体，在X上定义关系R、S为R={| a，b?X∧a是b的父亲}，S={|a，b?X∧a是b的母亲|，那么关系{| a，b?X∧a是b的祖母}的表达式为( )

(A) R°S (B)R-1 °S (C) S°R (D)R°S-1

33. 下列命题正确的是 ( )

(A){1,2}?{{1,2},{1,2,3},1} (B){1,2}?{1,{1,2},{1,2,3},2} (C){1,2}?{{1},{2},{1,2}} (D){1,2}?{1,2,{2},{1,2,3}}

34. 下列关系矩阵所对应的关系具有反自反性的是（ ）

35. 设R1和R2是集合A上的相容关系，下列关于R1 ⊕R2的说法正确的是（ ）

(A) 一定是相容关系； (B) 一定不是相容关系； (C) 可能是也可能不是相容关系； (D) 一定是等价关系。

三.判断题

1. 设集合A={ a,b,c,d,e,f}，那么S1= {?, {a,b},{c,d},{f}}是集合A的一个覆盖。( )

2. 恒等关系既是等价关系又是偏序关系。 ( )

3. 设F,R都是二元关系,则(F°R)-1=F-1 °R-1。 ( )

4. 设A,B,C是三集合，已知A∪B＝A∪C，则一定有B＝C。 ( )

5. 设集合A={ a,b,c,d,e,f}，那么S1= { {a,b},{c,d,e},{e,f } }是集合A的划分。( )

6. 集合A上的等价关系确定了A的一个划分。( )

7. 集合A上的偏序关系的三个性质是反自反性、对称性和传递性。 ( )

8. 三种重要的二元关系是等价关系、偏序关系和函数关系，它们的共同特点是都具有自反 性。 ( )

9. R的自反传递闭包也一定满足自反关系，传递关系。( )

10. 偏序集合中，链上的任何两个元素都是有关系的。( )

11. 设R是实数集，R上的关系f={||x-y|<2,x,y?R}，R是相容关系。( )

12. 空集是任何集合的真子集。( )

13. 设集合A、B、C为任意集合，若A×B = A×C，则B = C。 ( )

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

15. 空集是唯一的。 ( )

16. 全集不是唯一的。 ( )

17. 对于一个给定的集合，其划分是唯一的。 （ ）

18. 设R为X上的二元关系，则R是对称的<=>R=Rc。 （ ）

19. 设R为X上的二元关系，则R是反对称的<=>R∩Rc?IX。 （ ）

20. 设R为X上的二元关系，则R是传递的<=> (R°R) ?R。 （ ）

四.计算题

1. 设S={1,2,3,4,6,8,12,24}，“?”为S上整除关系，问： （1）偏序集的Hass图如何？ （2）偏序集的极小元、最小元、极大元、最大元是什么?

2. A={a，b，c，d}，R={,,},R是集合A上的二元关系。

3. 在实数平面上，画出关系R={|x-y+2>0∧x-y-2<0}，并判定关系的特殊性质。

4. R1={<1,2>,<1,3>,<2,3>,<3,3>}, R2={<2,2>,<2,3>,<3,4>}, (1) 求 R1-1 (2) 求R2 °R1

5. 设集合A＝{a,b,c,d}上的关系R＝{,,,}，写出它的关系矩阵和关 系图，并用矩阵运算方法求出R的传递闭包。

6. 设R是自然数集合N上的关系，且xRy<=>x+2y=10。 (1)求dom R；

(2)说明R具有的性质(自反、反自反、对称、反对称、传递)。 （1）画出的R的关系图；

（2）求R的自反闭包和对称闭包。

7. 设为一个偏序集，其中A={1，2，3，4，6，9，24，54},R是A上的整除关系。 （1）画出R的哈斯图； （2）求A的极大元和极小元； （3）求B={4,6}的上确界和下确界

8. 集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，{4，5 }}，并画出关系图。

9. 集合上的关系R={<1,1>,<1,3>,<2,2>,<3,3>,<3,1>,<3,4>,<4,3>,<4,4>},写出关系矩阵 ，画出关系图并讨论R的性质。

10. 下图是偏序集的哈斯图，

（1）写出集合A,R;

（2）求A的极大元和极小元； （3）求B={e,f}的上确界和下确界。

11. 设A={1,3,5,7}，定义A上的二元关系R:?R <=> a

12. A={a,b,c,}, R1={,,,},R2={,,}, 求：(1) R1-1 (2)R2 °R1

13. R1={<1,2>,<1,3>,<2,3>,<3,3>},R2={<2,2>,<2,3>,<3,4>} 求： (1) R1-1 (2) R1·R2 (3)R12

14. 设A是正整数m=20的因子的集合，并设?为整除关系。画出A上的偏序集合图(哈斯图)， 并指出A中的极大元和极小元，最大元和最小元。

五.证明题

1. 令I是整数集合，I上关系R定义为：R＝{|x-y可被3整除}，求证R是自反、对称和传递的。

2. 设A、B、C是任意集合，证明：A-(B∪C)=(A-B)∩(A-C)

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

4. 集合A的任一划分S诱导了A的一个等价关系R。

5. A, B为两个任意集合，求证：A－(A∩B) = (A∪B)－B .

6. 试证明实数集R上的小于等于关系“?” 是偏序关系。

7. 设R,S为二元关系, 试证明(R°S)c =S c °Rc.

本文来源：https://www.bwwdw.com/article/qh3g.html