当前位置：文档之家› 《离散数学》题库及答案

《离散数学》题库及答案

《离散数学》题库答案

一、选择或填空

（数理逻辑部分）

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），（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、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。

答：所有人都不是大学生，有些人不会死

7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。

(1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校

(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P

?（4）Q

P→

→（3）Q

Q→

?（2）Q

8、设个体域为整数集，则下列公式的意义是( )。

(1) ?x?y(x+y=0) (2) ?y?x(x+y=0)

答：（1）对任一整数x存在整数y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值：

(1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( )

(3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )

答：（1）F （2）F （3）F （4）T

10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( )

(1) 自然数(2) 实数(3) 复数(4) (1)--(3)均成立

答：（1）

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

14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。

答：P(x)∨?yR(y)

15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。

答：??x(R(x)→Q(x))

（集合论部分）

16、设A={a,{a}}，下列命题错误的是（）。

(1) {a}∈P(A) (2) {a}?P(A) (3) {{a}}∈P(A) (4) {{a}}?P(A)

答：(2)

17、在0（）Φ之间写上正确的符号。

(1) = (2) ?(3) ∈(4) ?

答：(4)

18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（）。

答：32

19、设P={x|(x+1)2≤4且x∈R},Q={x|5≤x2+16且x∈R},则下列命题哪个正确（）

(1) Q?P (2) Q?P (3) P?Q (4) P=Q

答：（3）

20、下列各集合中，哪几个分别相等( )。

(1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c}

(5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0}

答：A1=A2=A3=A6，A4=A5

21、若A-B=Ф，则下列哪个结论不可能正确？( )

(1) A=Ф(2) B=Ф(3) A?B (4) B?A

答：（4）

22、判断下列命题哪个为真?( )

(1) A-B=B-A => A=B (2) 空集是任何集合的真子集

(3) 空集只是非空集合的子集(4) 若A的一个元素属于B，则A=B

答：（1）

23、判断下列命题哪几个为正确？( )

(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}} (3) Ф∈{{Ф}}

(4) Ф?{Ф} (5) {a,b}∈{a,b,{a},{b}}

答：（2），（4）

24、判断下列命题哪几个正确？( )

(1) 所有空集都不相等(2) {Ф}≠Ф(4) 若A为非空集，则A?A成立。答：（2）

25、设A∩B=A∩C，A∩B=A∩C，则B( )C。

答：=（等于）

26、判断下列命题哪几个正确？( )

(1) 若A∪B＝A∪C，则B＝C (2) {a,b}={b,a}

(3) P(A∩B)≠P(A)∩P(B) （P(S)表示S的幂集）

(4) 若A为非空集，则A≠A∪A成立。

答：（2）

27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：

(1) A?B，B?C=> A?C (2) A?B，B?C=> A∈B (3) A∈B，B∈C=> A∈C 答：（1）

（二元关系部分）

28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，

求(1)R (2) R-1 。

答：（1）R={<1,1>,<4,2>} (2) R1-={<1,1>,<2,4>}

29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系

30、集合A上的等价关系的三个性质是什么？( )

答：自反性、对称性和传递性

31、集合A上的偏序关系的三个性质是什么？( )

答：自反性、反对称性和传递性

32、设S={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝求(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={<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>,<1,2>,<1,3>,<1,4>,

<1,5>,<1,6>,<2,4>,<2,6>,<3,6>}

34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R-1 。

答：（1）R={<1,1>,<4,2>,<6,3>} (2) R1-={<1,1>,<2,4>,(36>}

35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，

求R和R-1的关系矩阵。

答：R 的关系矩阵=????

?????

????0000000010000000

01 R 1-的关系矩阵=????

??????000000010000000001 36、集合A={1,2,…,10}上的关系R={|x+y=10,x,y ∈A}，则R 的性质为（）。

(1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的

答：（2）

（代数结构部分）

37、设A={2,4,6}，A 上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是( )，零元是( )。

答：2，6

38、设A={3,6,9}，A 上的二元运算*定义为：a*b=min{a,b}，则在独异点中，单位元是( )，零元是( )；

答：9，3

（半群与群部分）

39、设〈G,*〉是一个群，则

(1) 若a,b,x ∈G ，a *x=b ，则x=( )；

(2) 若a,b,x∈G，a*x=a*b，则x=( )。

-1 b （2）b

答：（1）a*

40、设a是12阶群的生成元，则a2是( )阶元素，a3是( )阶元素。答：6,4

41、代数系统是一个群，则G的等幂元是( )。

答：单位元

42、设a是10阶群的生成元，则a4是( )阶元素，a3是( )阶元素。答：5，10

43、群的等幂元是( )，有( )个。

答：单位元，1

44、素数阶群一定是( )群, 它的生成元是( )。

答：循环群，任一非单位元

45、设〈G,*〉是一个群，a,b,c∈G，则

(1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。

*a(2) b

答：（1）b1-

46、是的子群的充分必要条件是( )。

答：是群或? a，b ∈G，a*b∈H，a-1∈H 或? a,b ∈G，a*b-1∈H

47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。答：1，单位元，0

48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。

答：k

49、在自然数集N上，下列哪种运算是可结合的？（）(1) a*b=a-b (2) a*b=max{a,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)

（格与布尔代数部分）

52、下列哪个偏序集构成有界格（）

(1) （N,≤）(2) （Z,≥）

(3) （{2,3,4,6,12},|（整除关系））(4) (P(A),?)

答：(4)

53、有限布尔代数的元素的个数一定等于（）。

(1) 偶数(2) 奇数(3) 4的倍数(4) 2的正整数次幂答：(4)

（图论部分）

54、设G是一个哈密尔顿图，则G一定是( )。

(1) 欧拉图(2) 树(3) 平面图(4) 连通图

答：(4)

55、下面给出的集合中，哪一个是前缀码？( )

(1) {0，10，110，101111} (2) {01，001，000，1}

(3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011}

答：（2）

56、一个图的哈密尔顿路是一条通过图中( )的路。

答：所有结点一次且恰好一次

57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。答：以v为起点的边的条数，以v为终点的边的条数

58、设G是一棵树，则G 的生成树有( )棵。

(1) 0 (2) 1 (3) 2 (4) 不能确定

答：1

59、n阶无向完全图K n 的边数是( )，每个结点的度数是( )。

答：

2)1

(

, n-1

60、一棵无向树的顶点数n与边数m关系是( )。答：m=n-1

61、一个图的欧拉回路是一条通过图中( )的回路。

答：所有边一次且恰好一次

62、有n个结点的树，其结点度数之和是( )。

答：2n-2

63、下面给出的集合中，哪一个不是前缀码( )。

(1) {a，ab，110，a1b11} (2) {01，001，000，1}

(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}

答：(1)

64、n个结点的有向完全图边数是( )，每个结点的度数是( )。答：n(n-1),2n-2

65、一个无向图有生成树的充分必要条件是( )。

答：它是连通图

66、设G是一棵树，n,m分别表示顶点数和边数，则

(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。

答：（3）

67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。答：2

68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。

答：1，树

69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于:

(1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。

答：（1）

70、设T是一棵树，则T是一个连通且( )图。

答：无简单回路

71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 16

答：（4）

72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。

(1) 10 (2) 4 (3) 8 (4) 12

答：(4)

73、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？

答：有向图

74、任一有向图中，度数为奇数的结点有( )个。

答：偶数

75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？

(1) 2 (2) 4 (3) 3 (4) 5

答：（3）

76、在有n个顶点的连通图中，其边数（）。

(1) 最多有n-1条(2) 至少有n-1 条

(3) 最多有n条(4) 至少有n 条

答：（2）

77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（）。

(1) 5 (2) 7 (3) 8 (4) 9

答：（4）

78、若一棵完全二元（叉）树有2n-1个顶点，则它（）片树叶。

(1) n (2) 2n (3) n-1 (4) 2

答：（1）

79、下列哪一种图不一定是树（）。

(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图

(3) 每对顶点间都有通路的图(4) 连通但删去一条边便不连通的图答：（3）

80、连通图G是一棵树当且仅当G中（）。

(1) 有些边是割边(2) 每条边都是割边

(3) 所有边都不是割边(4) 图中存在一条欧拉路径

答：（2）

（数理逻辑部分）

二、求下列各公式的主析取范式和主合取范式：

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)?(?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)∨( ?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∨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)∨(?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)∨(?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∧?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)∨(?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∨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?

∨Q)∧R)

∨R))∨((P?

∨P)∧(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

??(?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)∨?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)

?(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)(主合取范式)

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

离散数学考试（试题及答案）一、（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>}。

2016离散数学练习题 (答案修改)

2016注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的总结把重点内容再做复习。另外，把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题 1．令p : 今天下雪了，q :路滑，r :他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（ A ）。 A. p q r ∧→ B. p q r ∨→ C. p q r ∧∧ D. p q r ∨? 2.设()P x :x 是整数，()f x :x 的绝对值，(,)L x y ：x 大于等于y ；命题“所有整数的绝对值大于等于0”可符号化为（ B ）。 A. (()((),0))x P x L f x ?∧ B. (()((),0))x P x L f x ?→ C. ()((),0)xP x L f x ?∧ D. ()((),0)xP x L f x ?→ 3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。 A ．(()())x F x G x ?∧ B ． (()())x F x G x ??→? C ．(()())x F x G x ??∧ D ． (()())x F x G x ??∧? *4.下列命题公式不是永真式的是（ A ）。 A . ()p q p →→ B . ()p q p →→ C . ()p q p ?∨→ D . ()p q p →∨ 5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。 A. p q ∧ B. ()p q ?∧ C. p q ?∧? D. p q ?∧ 6．设()R x :x 为有理数；()Q x :x 为实数。命题“任何有理数都是实数”的符号化为（ A ） A ．()(()())?→x R x Q x B ．()(()())?∧x R x Q x C ．()(()())x R x Q x ?∧ D ．(()())x R x Q x ?→ 7. 设个体域{,}D a b =，与公式()xA x ?等价的命题公式是( C ) A ．()()A a A b ∧ B ．()()A a A b → C ．()()A a A b ∨ D ．()()A b A a → 8．无向图G 有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G 一共有（ C ）个顶点。

离散数学模拟试题讲解

1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f

2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >=

离散数学模拟题(开卷)

《离散数学》模拟题（补）一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) (

7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件下X 与（）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合，，则表示关系（）。 A 、； B 、； C 、； D 、。 10.下面函数（）是单射而非满射。 A 、； B 、； C 、； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f

《离散数学》及答案

《离散数学》+答案一、选择或填空: 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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44

离散数学复习题及答案

离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]

1. 写出命题公式﹁（P →（P ∨ Q ））的真值表。答案： 2.证明答案： 3. 证明以下蕴涵关系成立：答案： 4. 写出下列式子的主析取范式：答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化：所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?

答案：令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化：存在着不是有理数的实数。答案：令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化：尽管有人聪明，但并非一切人都聪明。答案：令M(x)：x 是人 C(x)：x 是聪明的则上述命题符号化为 10. 请将下列命题符号化：对于所有的正实数x,y，都有x+y≥x。答案：令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化：每个人都要参加一些课外活动。答案：令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化：某些人对某些药物过敏。答案：

令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式：答案： 15. 证明：答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明：前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?

离散数学模拟试卷和答案

北京语言大学网络教育学院《离散数学》模拟试卷一注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（）。 [A]3个 [B]6个 [C]8个 [D]9个

离散数学(上)模拟题

离散数学（上）模拟题 1、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化 a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 b) 对于所有非零实数x，总存在y使得xy=1。 c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得 f(a)=b. 2、简答题（共6道题，共32分） 1. 求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) xy(x+y=4) b) yx (x+y=4) 3. 求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （AB）－C=(A-B) (A-C) b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. 设A是有穷集，|A|=5，问（每小题2分，共4分） a) A上有多少种不同的等价关系？ b) 从A到A的不同双射函数有多少个？ 6. 设有偏序集，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分) f g d e b c a 图1 7. 已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求

下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分) 3、证明题（共3小题，共计40分） 1. 使用构造性证明，证明下面推理的有效性。（每小题5分，共10 分） a) A→(B∧C),(E→F)→C, B→(A∧S)B→E b) x(P(x)→Q(x)), x(Q(x)∨R(x))，xR(x) xP(x) 2. 设R1是A上的等价关系，R2是B上的等价关系，A≠且B≠，关系R 满足：<,>∈R，当且仅当< x1, x2>∈R1且 ∈R2。试证明：R是A×B上的等价关系。（10分） 3. 用伯恩斯坦定理证明（0,1]和(a,b)等势。（10分） 4. 设R是集合A上的等价关系，A的元素个数为n，R作为集合有s个元素，若A关于R的商集A/R有r个元素，证明：rs≥n2。（10分） 4、应用题（10分）在一个道路上连接有8个城市，分别标记为a,b,c,d,e,f,g,h。城市之间的直接连接的道路是单向的，有a→b, a→c, b→g, g→b, c→f, f→e, b→d, d→f.对每一个城市求出从它出发所能够到达的所有其他城市。

离散数学作业答案

第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？能被5整除的有40个，能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试

3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同班同学，个体域是学校全体学生的集合。解：学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则第五章

离散数学考试题

离散数学测试题一．选择题（10*2） 1.设L (x )：x 是演员，J (y )：y 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( ) (A) ),()(y x A x xL →? (B) ))),()(()((y x A y J y x L x ∧?→? (C) )),()()((y x A y J x L y x ∧∧?? (D) )),()()((y x A y J x L y x →∧?? 2.令F(x):x 是有理数，G(x):x 是实数。将命题“所有的有理数都是实数，但有的有实数不是有理数”符号化为（） A.?x(F(x)∧G(x))∧?x(G(x)→?F(x)) B.?x(F(x)→G(x))∧?x(G(x)∧?F(x)) C.?x(F(x)∧G(x))∧?x(G(x)∧?F(x)) D.?x(F(x)→G(x))∧?x(G(x)→?F(x)) 3．设R 是集合A={a,b,c,d}上的二元关系， R={,,,,,,}，则R 具有关系的哪些性质（） A.自反性、反对称性 B.反自反性、传递性 C.自反性、对称性 D.反对称性、传递性 4．设A ＝{1，2}，B ＝{a,b,c}，C ＝{c,d}，则A ×（B ∩C ）为（） A ．{},1,2,c c <><> B ．{}1,,2,c c <><> C ．{},1,,2c c <><> D ．{}1,,,2c c <><> 5．设A={a,b,c,d}，A 上的等价关系R={,,,}∪I A ，则对应于R 的A 的划分是（） A ．{{a},{b,c},{d}} B ．{{a,b},{c},{d}} C ．{{a},{b},{c},{d}} D ．{{a,b},{c,d}} 6．设A ＝{a,b}，则A 的幂集P （A ）为（） A ．{a,b} B ．{Φ,{a},{b}} C ．{Φ,{a,}} D ．{Φ,{a},{b},{a,b}} 7、设A , B , C 都是集合，如果A ?C ＝B ?C ，则有( ) (A) A ＝B (B) A ≠B (C) 当A －C ＝B －C 时,有A =B (D) 当C =U 时, 有A ≠B 8．集合A ＝{1,2,3，4，5，6，7，8，9，10}，A 上的整除关系是一个偏序关系，则元素10是集合A 的（）． A ．最大元； B ．最小元； C ．极大元； D ．极小元 9．设R 为实数集，映射f ：R →R ，f （x ）＝-x 2+2x-1，则f 是（） A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不

离散数学模拟试题及答案

《离散数学》模拟试题一、填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化，其真值为。二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}，则R 不具备（）. 三、计算题（共50分） R Q P G →∧?=)(

离散数学模拟试卷和答案

离散数学课后答案

离散数学课后答案习题一 6.将下列命题符号化。（1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答：（1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q

离散数学期末练习题-(带答案)

离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。离散数学综合练习题一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）

离散数学考试试题(A、B卷及答案)

离散数学考试试题(A卷及答案）一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p）证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF

( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。证明：(P Q)((P∧Q))(P ∨Q))P Q。二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF

证明：公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF

所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF

离散数学复习题

一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B.

离散数学期末试卷A卷及答案

《离散数学》试卷（A 卷）一、选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.

2、公式)(Q P Q ?∨∧的主合取范式为。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。（ F ） 2、“张刚和小强是同桌。”是复合命题。（ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。（ T ） 4、)(T S R T R S R ??????。（ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。（ T ） 6、若f 、g 分别是单射,则g f ?是单射。（ T ） 7、若g f ?是满射，则g 是满射。（ F ） 8、若A B ?，则)()(A P B P ?。（ T ） 9、若R 具有自反性，则1-R 也具有自反性。（ T ） 10、B A ∈并且B A ?不可以同时成立。（F ）四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问（１）三门课程都不选的学生有多少？（２）只选修计算机课程的学生有多少？

离散数学答案

02任务_000 1 试卷总分：100 测试时间：0 单项选择题一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={|x=y且x, y A}，则R的性质为（）． A. 不是自反的 B. 不是对称的 C. 传递的 D. 反自反 3. 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A. {a，{a}}A B. {1，2}A C. {a}A D. A 4. 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2, 1>，<3, 1>}，则h =（）． A. f?g B. g?f C. f?f D. g?g

5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集上的元素5 是集合A的（）． A. 最大元 B. 最小元 C. 极大元 D. 极小元 8. 若集合A的元素个数为10，则其幂集的元素个数为（）． A. 1024 B. 10 C. 100 D. 1 9. 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A. 0 B. 2 C. 1