离散数学填空题包括答案.docx

编

题目答案号

1

谓词公式x(P(x) yR(y))Q(x) 中量词x 的辖域是（）。答： P(x)yR(y)

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

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

4

一个图的欧拉回路是一条通过图中()的回路。答：所有边一次且恰好一次

5

有 n 个结点的树，其结点度数之和是()。答：2n-2

6

设 T 是一棵树，则T 是一个连通且()图。答：简单无回路

7

任一有向图中，度数为奇数的结点有() 个。答：偶数

8

{ x | ( x N )且 ( x 5)}, B { x | x E 且 x 答： {0 ，1， 2， 3，4， 6}

设 A7} （N：自然数集，E+

正偶数）则 A B（）。

9

设 P， Q 的真值为0， R， S 的真值为1，则答：1题分

大纲

难型值度填 2 3.13空

题

填 2 3.13空

题

填 27.13空

题

填 2 6.43空

题

填 2 6.43空

题

填 2 6.23空

题

填 2 6.13空

题

填 212空

题

填 2 2.13空

( P (Q ( R P)))(R S) 的真值=（）。

题

10

公式 (P R)(S R)P 的主合取范式为（）。答： ( P S R) ( PS R)填 2 2.34

空

题

11设 A={1， 2 ，3， 4} ， A上关系为｛ <1,2>,<2,1>,<2,3>,<3,4> ｝则 R2 =答： {<1,1>, <1,3>, <2,2>, <2,4> }填 2 4.1；4.23

空()。题

12

设 A={a ， b， c，d} ，其上偏序关系R 的哈斯图为答： {,,,,}I A填 2 4.44

空

题则 R= （）。

13树是不包含树是不包含（）的（）图的。答：环 ;无向填 28.13

空

题

14设 A={1 ，2，3} ，则 A 上既不是对称的又不是反对称的关系R= ()。答： R={<1,2>,<1,3>,<2,1>}填 2 4.33

空

题

15

设 f ，g 是自然数集N 上的函数x N , f (x) x 1 , g (x)2x

答： 2(x+1)填 2 5.23，则

空

f g( x) （）。

题

16设 A={a ， b， c} ， A 上二元关系 R={< a, a > , < a, b >,< a, c >, < c, c>},答：填 2 4.45

则 s（R）= （

{ a , a , a ,b , a , c , c , c , b , a , c, a }空）。题

17

P，Q 真值为 0；R，S 真值为 1。则wff( P (R S)) (( P Q) (R S))答： 1填 2 2.23

空

的真值为（）。题

18wff(( P Q) R)R 的主合取范式为（）。答：Q R)(P Q R)( P Q填2 2.34

( P R)

空

题

19

设 P（ x）： x是素数，E(x) ： x 是偶数， O(x)： x 是奇数N (x,y) ：x 可以整答：( P Q R)(P Q R)( P Q

填2 3.13 R)

空

数 y 。则谓词wff x( P(x)y(O ( y)N ( y, x)))的自然语言是题（）。

20

谓词

答：填 2 3.24 wff x y( z(P(x, z) P( y, z))uQ( x, y,u)) 的前束范式为

空

x y z u( P(x, z)P( y, z) Q (x, y,u))

题

（）。

21

若 P， Q，为二命题，P Q 真值为0当且仅当（）。答： P 真值为 1， Q 的真值为 0填 2 2.13

空

题

22将量词辖域中出现的（）和指导变元交换为另一变元符号，公式其余答：约束变元填 2 3.13

空的部分不变，这种方法称为换名规则。题

23

设 G 为 9 阶无向图，每个结点度数不是 5 就是 6，则 G 中至少有（）

答：6填2 6.13

个 5 度结点。空题

24答： 2

有向图中从 v1到 v2长度为 2的通路有

（）条。

25

设 [ L, ,] 是代数系统，则 [ L, ,] 满足幂等律，即对 a L 有答： a a a 且 a a a （）。

26

任何 (n,m)图 G = (V,E) ,边与顶点数的关系是（）。答： d(v) 2m

v V

27

当 n 为（）时,非平凡无向完全图K n是欧拉图。答：奇数

28 已知一棵无向树

T 有三个 3 顶点 , 一个 2 度顶点 , 其余的都是 1 度顶点 , 则 T 中答： 5

有（）个 1 度顶点。

29

集合 A={,{}} 的幂集 P(A) =（）。答：{,{}, {{}}, {,{}}}

30

设|A|=3 ，则 A 上有（）个二元关系。答：29填 2 6.33空

题

填 2 8.24空

题

填 2 6.43空

题

填 2 6.23空

题

填 27.13空

题

填 213空

题

填 2 4.13空

题

31 32 33 34 35 36 37 38 39Q：我将去上海，R：我有时间，公式(Q R) ( R Q ) 的自然语言为

答：我将去上海当且仅当我有空填 2

空

（）。题

公式 (QP) (P Q ) 的主合取范式是（）。

答：填 2

空

( P Q ) (P Q ) ( P Q) ( P Q )

题

若 S { S1 , S2 ,, S m } 是集合A的一个分划，则它应满足（）。m

填 2

答： (1)S i S j(i j ) (2) S i A空

i 1题

代数系统 中，|A|>1，如果e和分别为 的幺元和零元，则e和的答：

e填 2

空

关系为（）。题

设 A { x | x 2n, n N } ，定义A上的二元运算为普通乘法、除法和加法，

答：乘法填 2

空

则代数系统 中运算 * 关于（）运算具有封闭性。题

设 是由元素a G生成的循环群，且 |G|=n，则 G = ()。答： G { a, a2 , a n 1， a n e}

填 2

空

题

一个图是平面图的充要条件是() 。答：它不包含与 K 3, 3或 K 5在 2 度结点内同构的子图填 2

空

题

某人有三个儿子，组成集合 A={S 1,S2,S3} ，在 A上的兄弟关系具有答：反自反性、对称性、传递性填 2

空

（）性质。题

若 f : A B 是函数，则当 f 是A B 的（）， f c: BA 是f

答：双射填 2

空

的逆函数。题

2.13

2.33

4.43

8.13

8.13

8.34

6.43

4.13

5.23

40设 P：它占据空间， Q：它有质量， R：它不断运动， S：它叫做物质。命题“占答：据空间的，有质量的而且不断运动的叫做物质”的符号化为（）。

41设 A ， B 是两命题公式，A B 当且仅当（）。

答：

42

对谓词公式yP (x, y) zQ(x, z)xR(x, y) 的自由变元代入得答：

()。S P Q填2 2.13 R

空

题

A B T填 2 2.1；2.23

空

题

yP (u, y)

填2 3.1；3.23 zQ(u, z)xR(x, w)

空

题

43对集合 X 和 Y ，设 |X|=m， |Y|=n，则从 X 到 Y 的函数有 ()个。答： n m

填 2 5.13

空

题

44若关系 R 是等价关系 ,则 R 满足 ()性质。答：自反性、对称性、传递性填 2 4.43

空

题

45关系 R 的传递闭包 t (R) = () 。

答：R i R 填 2 4.34空

i1题

46

代数系统 A ,是群，则它满足 ()。答：①运算 * 在 A上封闭，② * 在 A 上可结合，③ *填 28.2；8.33在 A 上存在幺元，④ A 中每个元素都有逆元；空

题

47

设 A, ,?和 B , ,是两代数系统， f 是 A , ,?到 B ,

答：填 28.2；8.33 ,

A , f (a b) f (a) f (b) , f (a b) f (a) f (b)空

a,b

的同态映射，则 f 具有 ()性质。题

48

若连通平面图 G V , E共有 r 个面，其中V v , E

答： v e r 2填 2 6.43 e，则它满足的空

Euler 公式为 ()。

题

49树 T 的边数 e 与点数 v 有关系 ()。答： e v1填 27.1；7.23

空

题

50

n 个命题变元有 ()个互不等价的极小项。答： 2n 填 2 2.2；2.33空

题

51n(n)填 2 2.2；2.33

答：A i

按 De-Morgan 定理，A1A2A n A i=(空

)。i 1

i1题

52

公式 P( Q R) 的主析取范式为(

答：填 2 2.34 ) 。

( P Q R) ( P Q R) ( P QR) ( P Q R)空

(P Q R) ( P Q R ) (P Q R)

0,1, 2, 3, 4,5, 7

题

53

设 P(x)：x 是大象， Q(x) ：x 是老鼠， R(x,y) ：x 比 y 重，则命题“大象比老鼠

重”的符号化为 ()。

54101设 X{ a, b, c} ，X上的关系R的关系矩阵是 M R 110，则

111

M R R()。

55

在具有n个结点的有向图中，任何基本通路的长度都不超过() 。答：x y( P( x) Q( y)R(x, y))

1 11

答： 1 11

1 11

答： n-1

填 2 3.13

空

题

填 2 6.34

空

题

填 2 6.13

空

题

56

任何图的点连通度(G ) ，边连通度(G ) ，最小点度(G ) 的关系为答： (G )(G)(G ) ()。填 2 6.1；6.2 3空

题

57结点数n（n 3 ）的简单连通平面图的边数为m，则 m与 n 的关系为答： m3n6

()。

58

群 G的非空子集 H 是 G 的子群当且仅当若x , y H 则 ()。答： x y 1H

59

代数系统A,,?是环，若对运算“·”还满足 ()则

答：含幺元，可交换，无零因子A,,?是整环。

60

给定命题公式 A 、B ，若（），则称 A 和 B 是逻辑相等的。答：对于 A ，B 中原子变元P1, P2,, P n任意一组

真值指派， A 和 B 的真值相同。

61

设 A { a, b, c}考虑下列子集S1{{ a, b}, { b, c}}，答： S1 , S2 , S3 , S4 , S5； S3， S4， S5 S2{{ a}, { a, b}, { a,c}} ， S3{{ a}, {b, c}} ， S4{{ a, b, c}}

S5{{ a}, {b}, { c}}， S6 {{a}, { a, c}}

则 A的覆盖有（）， A 的划分有（）。

62

若 G V, E为哈密顿图，则对于结点集V 的每个非空子集S，均有

答：≤

P(G-S)（） S 成立，

63 某班有学生 50 人 , 有 26 人在第一次考试中得优, 有 21人在第二次考试中得优,答：14

有17 人两次考试都没有得优 , 那么两次考试都得优的学生人数是

（）。填 2 6.44空

题

填 2 8.34空

题

填 2 8.2；8.3 5空

题

填 2 2.13空

题

填 2 4.44空

题

填 2 6.44空

题

填 213空

题

64 给命题变元p、 s 和 r 指派真值1,q 指派真值0, 公式 p→ ( ┐ (s ∧ r) →┐ q) ∧ s)

的真值为（）。

65

设 p：我生病， q：我去上课，命题“我虽然生病但我还是去上课”符号化为：

（）。

66 公式xA(x) →xB(x) 的前束范式为（）。

67 若{1,2,3,4}上的二元关系R={<1,1>,<1,2>,<2,4>},则R的自反闭包r(R )=

（）。

68有向图 D 如下，则 D 的邻接矩阵A(D) = （）。

695阶的群有（）个不同的子群。

70

一棵高度为 5 的二元树结点数最多为（）。答： 1

答： p q

答：x( A( x)B( x))或x( A( x)B( x))

答： r(R)= ｛ <1,1>,<1,2>,<2,4>,<2,2><3,3>,<4,4> ｝

0 1 01

0 0 11

答：

0 0 01

0 1 00

答： 2

答： 63

填 2 2.1；2.2 3

空

题

填 2 2.1；2.2 3

空

题

填 2 3.24

空

题

填 2 4.1；4.2 4

空

题

填 2 6.33

空

题

填 2 8.34

空

题

填 2 7.1；7.2 3

空

题

71 一个连通平面图 G 有 10 条边， G 中度为 1 的顶点有 2 个，其余是度为

6 的顶

答： 5， 7

填 2 6.1；6.2 3

点，则 G 中共有（

空

）个顶点，（ ）个面。

题

72 集 合

X={0,1,2,3}

，

R

是X

上 的

二

元

关 系 ，

0 1 1 0 填 2 6.2；6.3 3

0 1 0 1

空

R={<0,1>,<0,2>,<1,1>,<1,3>,<2,0>,<2,3>,<3,1,>} ，则

R 的关系矩阵 M R 是

答：

0 0 1 题

（

）。

1

0 1

0 0

73 无向图 G 中有 n 个结点 m 条边，且 G 中每个结点的度数不是

k 就是 k+1,则 G 答： (k+1)n-2m

填 2 6.1；6.2 3

空

中度数为 k 的结点的个数是（

）。

题

74 设 Z +

={x │ x ∈ Z ∧ x>0} ，* 表示求两个数的最小公倍数的运算，则

* 运算的幺

答： 1

填 2 8.1；8.2 3

空

元是（

）。

题

75 群总共有（

）个不同的子群。

答： 2

填 2 8.1；8.2 4

空

题

76 在个体域 D={a,b} 中，与公式

xA(x) 等价又不含量词的公式是（

）。 答： A(a) ∧ A(b)

填 2 3.1；3.2 3

空

题

77 具有 4 个结点的有向完全图的边数为（

）条。

答： 24

填 2 6.1

3

空

题

78 若 p ：他聪明； q ：他用功； 则 “他虽聪明， 但不用功 ”，可符号化为 （

）。 答： p ∧┐ q

填 2 2.1

3

空

题

79 若集合 A={1, 2, 3} 上的二元关系 R 1 和 R 2 的关系图如下所示，

答： r(R)= ｛ <1,1>,<1,2>,<2,4>,<2,2><3,3>,<4,4> ｝

填 2 4.1；4.2 3

空

题

则 R 1oR 2 =（ ）。

80树是平面图，它有（）个面。答： 1填 2 6.1；7.13

空

题

81哈密尔顿回路要求经过图中（）一次且仅一次。答：每个顶点填 2 6.43

空

题

82有向图 D 如下：D 的邻接矩阵 A=(aij)3 × 3,则 a11=（）,a32=（）。答： 1， 0填 2 6.33

空

题

83在一棵根树中，仅有一个结点的入度为（），称为树根，其余结点的答： 0， 1填 27.23入度均为（）。空

题

84合式公式 Q→(P ∨ (P∧ Q)) 与 Q→P的关系是 _______的。（等价或蕴含选一）答：等价填 2 2.2；2.33

空

题

85设 R 为非空集合 A 上的二元关系，如果R 满足（），则称 R 为 A答：自反、反对称、传递填 2 4.33上的一个偏序关系。空

题

86设 R 为 A 上的关系，则 R 的自反闭包 r(R)= （），对称闭包 s(R)=答： R I x , R R c填 2 4.34

空（）。题

87一棵高度为 3 的二叉树结点数最多为（）。答： 7填 27.1；7.23

空

题

88设 Z 是整数集，在 Z 上定义二元运算 * 为 a*b=a+b+a ?b，其中 +和 ?是数的加法答： a , 0填 28.1；8.23

和乘法，则代数系统 的幺元是（），零元是（）。

89

设 T 是有 n 个结点的完全二叉树，则T 叶子数为（）。答：(n+1)/2

90

设 A={a,b,c}, 则 A × A 中的元素有 ()。答：9

91图 G 与其对偶图 G* 的结点数目（）相等。答：不一定

92

设S { 1, 2, 3 } ，定义S S上的等价关系

答： 4 R{a,b ,c, d|a,b S S, c, dS S, a d b c}则

由R 产生的S S 上一个划分共有（）个分块。

93设〈 G，〉是一个群，则对任意的a, b ∈G均有 (a b) 1= （）。答： b 1 * a 1 940101答： 2， 2

设图 D=，V={ v1234

A=101

1 ，则

，v ，v ，v } ，若 D 的邻接矩阵1100

1001

deg-（ v1） =（），从 v2到 v4长度为 2 的路有（）条。

95设 A={1， 2} ， B={2 ， 3} ，则 A-A= （）， A-B= （）。答：，{1}空

题

填 2 7.1；7.2 3空

题

填 2 1； 4.1 3空

题

填 2 6.44空

题

填 2 4.3；4.4 3空

题

填 28.35空

题

填 2 6.34空

题

填 2 13空

题

96两个重言式的析取是（）式，一个重言式与一个矛盾式的析取是答：重言式，重言式（）式。

97一个无向树中有 6 条边，则它有（）个结点。答： 5

98 谓词公式 ( x)(y)（ P(x,y) ∨R(y)) → Q(y) ，则其约束变元是（），答：（ P(x,y) ∨ R(y)) 中的 x,y; Q(y) 中的 y

自由变元是（）。

99 一个结点为

n 的无向完全图，其边的数目为（） , 并且它是答： n(n-1)/2,n （）度正则图。

100

设 R 为非空集合 A 上的等价关系，其等价类记为〔 x〕R。 x,y∈ A ，若〈 x,y 〉答：［x］

R

=［y］

R

,

∈R，则〔 x〕R与〔 y〕R的关系是（），而若〈 x,y 〉R，则〔 x〕

R ∩〔 y〕 =（）。

R

填 2 2.1；2.2 3

空

题

填 2 7.13

空

题

填 2 2.1；2.2 3

空

题

填 2 6.1；7.1 3

空

题

填 2 4.44

空

题

100道离散数学填空题分解

离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为

则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统的 ，元的元素 为，它们的逆元分别为。 16. P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 17. 论域D={1，2}，指定谓词P

离散数学作业答案

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，

山东大学离散数学题库及答案

《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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 Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 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)均有可能

(完整版)离散数学作业答案一

离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式

《离散数学》题库及答案

《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）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 (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）

离散数学期末试卷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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？

吉林大学离散数学课后习题答案

第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每

一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故

G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G

大学本科高等数学《离散数学》试题及答案

本科高等数学离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

安徽大学期末试卷离散数学上卷及参考答案.doc

安徽大学20 09 — 20 10 学年第 1 学期 《离散数学（上）》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 题 号 一 二 三 四 五 总分 得 分 一、单选题（每小题2分，共20分） 1. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( ) A.R ∪I A B.R C.R ∪{〈c,a 〉} D.R ∩I A 2. 设X={a,b,c},I x 是X 上恒等关系，要使I x ∪{〈a,b 〉，〈b,c 〉，〈c,a 〉，〈b,a 〉}∪R 为X 上的等 价关系，R 应取( ) A. ｛〈c,a 〉，〈a,c 〉｝ B.{〈c,b 〉，〈b,a 〉} C. {〈c,a 〉，〈b,a 〉} D.{〈a,c 〉，〈c,b 〉} 3. 下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 4. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x

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

离散数学复习注意事项： 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为实数。命题“任何有理数都是实数”的符号化为（）

慕课 离散数学 电子科技大学 课后习题十 答案

作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G=，其中： V={a,b,c,d,e,f,g} E={(u,v)|u,v∈V,且u和v有共同语言} 从而图G如下图所示。 a b c d e f g 将这7个人围圆桌排位，使得每个人都能与他两边的人交谈，就是在图G 中找哈密顿回路，经观察上图可得到两条可能的哈密顿回路，即两种方案：abdfgeca和acbdfgea。 3.证明（法一）：根据已知条件，每个结点的度数均为n，则任何两个不相邻 的结点v i,v j的度数之和为2n，而图中总共有2n个结点，即deg(v i)+ deg(v j)?2n，满足哈密顿图的充分条件，从而图中存在一条哈密顿回路，当然，这就说明图G是连通图。 证明（法二）：用反证法，假设G不是连通图，设H是G的一个连通分支，由于图G是简单图且每个结点的度数为n，则子图H与G-H中均至少有n+1个结点。所以G的结点数大于等于2n+2，这与G中结点数为2n矛盾。所以假设不成立，从而G是连通图。 4.将n位男士和n位女士分别用结点表示，若某位男士认识某位女士，则在 代表他们的结点之间连一条线，得到一个偶图G，假设它的互补结点子集V1、V2分别表示n位男士和n位女士，由题意可知V1中的每个结点度 1

数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2

中国石油大学大学《离散数学》期末复习题及答案

《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群的元素，则-(a+b+c)= 。 10、一个图的哈密尔顿路是。 11、不能再分解的命题称为，至少包含一个联结词的命题称 为。 12、命题是。 13、如果p表示王强是一名大学生，则┐p表示。 14、与一个个体相关联的谓词叫做。 15、量词分两种：和。 16、设A、B为集合，如果集合A的元素都是集合B的元素，则称A是B 的。 17、集合上的三种特殊元是、 及。 18、设A={a, b}，则ρ(A) 的四个元素分别 是：，，，。

19、代数系统是指由及其上的或 组成的系统。 20、设是代数系统，其中是*1,*2二元运算符，如果*1,*2都满 足、，并且*1和*2满足，则称是格。 21、集合A={a,b,c,d}，B={b }，则A \ B= 。 22、设A={1, 2}, 则∣A∣= 。 23、在有向图中，结点v的出度deg+(v)表示，入度deg-(v)表示 以。 24、一个图的欧拉回路是。 25、不含回路的连通图是。 26、不与任何结点相邻接的结点称为。 27、推理理论中的四个推理规则 是、、、。 二、判断题（每题2分，共20分） 1、空集是唯一的。 2、对任意的集合A，A包含A。 3、恒等关系不是对称的，也不是反对称的。 4、集合{1,2,3,3}和{1,2,2,3}是同一集合。 5、图G中，与顶点v关联的边数称为点v的度数，记作deg(v)。 6、在实数集上，普通加法和普通乘法不是可结合运算。 7、对于任何一命题公式，都存在与其等价的析取范式和合取范式。 8、设（A,*）是代数系统，a∈A，如果a*a＝a，则称a为（A，*）的等幂元。 9、设f：A→B，g：B→C。若f，g都是双射，则gf不是双射。 10、无向图的邻接矩阵是对称阵。 11、一个集合不可以是另一个集合的元素。 12、映射也可以称为函数，是一种特殊的二元关系。 13、群中每个元素的逆元都不是惟一的。

离散数学 练习题七

9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={ | x,y ∈S ∧ x+y=10 }， 试列举出R 中的所有有序对，并分析说明R 具有哪些性质。(10分)

离散数学作业答案

第一章 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规则 第五章

山东大学离散数学题库及答案

《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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 Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 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

《离散数学》练习题和参考答案

《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (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 Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 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是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。

国开放大学离散数学本离散数学作业答案

国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021

离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题

1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，则R具有的性质是反自反性． 6．设集合A=｛a, b, c, d｝，A上的二元关系R={, , , }，若在R中再增加两个元素 , ，则新得到的关系就具有对称性． 7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2 个．