2离散数学

1

离散数学 三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．

12．将语句“今天没有下雨．”翻译成命题公式．

四、判断说明题（每小题7分，本题共14分）

判断下列各题正误，并说明理由．

13．下面的推理是否正确，试予以说明．

(1) （x）F（x）→G（x）前提引入

(2) F（y）→G（y）US（1）．

14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．

图二

五．计算题（每小题12分，本题共36分）

15．求（P∨Q）→（R∨Q）的合取范式．

16．设A={0，1，2，3，4}，R={|xA，yA且x+y<0}，S={|xA，yA且x+y3}，试求R，S，RS，R-1，S-1，r(R)．

17．画一棵带权为1, 2, 2, 3, 4的最优二叉树,计算它们的权．

六、证明题（本题共8分）

18．设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G是G的补图)．

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：他接受了这个任务，Q：他完成好了这个任务，（2分）

PQ．（6分）

12．设P：今天下雨，（2分）

P．（6分）

四、判断说明题（每小题7分，本题共14分）

13．错误．（3分）

（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．（7分）

14．错误．（3分）

集合A的最大元不存在，a是极大元．（7分）

五．计算题（每小题12分，本题共36分）

15．（P∨Q）→（R∨Q）

（P∨Q）∨（R∨Q）（4分） 2

离散数学 (P∧Q)∨（R∨Q）

(P∨R∨Q)∧(Q∨R∨Q)

(P∨R∨Q) ∧R 合取范式（12分）

16．R=, （2分）

S={<0,0>,<0,1>,<0,2>,<0,3>,<1,0>,<1,1>,<1,2>,<2,0>,<2,1>,<3,0>} （4分）

RS=，（6分）

R-1=，（8分）

S-1= S，（10分）

r(R)=IA．（12分）

17．

（10分）

权为13+23+22+32+42=27 （12分）

六、证明题（本题共8分）

18．证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数，（3分）

因此，若G中顶点v的度数为奇数，则在G中v的度数一定也是奇数，（6分）

所以G与G中的奇数度顶点个数相等．（8分）

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天考试，明天放假．”翻译成命题公式．

12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．

四、判断说明题（每小题7分，本题共14分）

判断下列各题正误，并说明理由．

13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图．

14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元是f．

图二

五．计算题（每小题12分，本题共36分）

15．设谓词公式)),,()(),()((zxyBzyxAx，试 

 

   

  1 2 2 3 3

4 7 5 12 3

离散数学 （1）写出量词的辖域；（2）指出该公式的自由变元和约束变元．

16．设集合A={{1},1,2}，B={1,{1,2}}，试计算

（1）（AB）；（2）（A∩B）；（3）A×B．

17．设G=，V={ v1，v2，v3，v4 }，E={ (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) }，试

（1）给出G的图形表示；（2）写出其邻接矩阵；

（3）求出每个结点的度数；（4）画出其补图的图形．

六、证明题（本题共8分）

18．设A，B是任意集合，试证明：若AA=BB，则A=B．

三、逻辑公式翻译（每小题4分，本题共12分）

11．设P：今天考试，Q：明天放假．（2分）

则命题公式为：P∧Q．（6分）

12．设P：我去旅游，Q：我有时间，（2分）

则命题公式为：PQ．（6分）

四、判断说明题（每小题7分，本题共14分）

13．错误．（3分）

当图G不连通时图G不为欧拉图．（7分）

14．错误．（3分）

集合A的最大元与最小元不存在，

a是极大元，f是极小元，．（7分）

五．计算题（每小题12分，本题共36分）

15．（1）x量词的辖域为)),,()(),((zxyBzyxA，（3分）

z量词的辖域为),,(zxyB, （6分）

（2）自由变元为)),,()(),((zxyBzyxA中的y，（9分）

约束变元为x与z．（12分）

16．（1）AB ={{1},2} （4分）

（2）A∩B ={1} （8分）

（3）A×B={<{1},1>，<{1},{1,2}>，<1,1>，<1, {1,2}>，<2,1>，<2, {1,2}>} （12分）

17．（1）G的图形表示为(如图三)：

（3分）

图三

（2）邻接矩阵： 4

离散数学 0110101111000100（6分）

（3）v1，v2，v3，v4结点的度数依次为1，2，3，2 （9分）

（4）补图如图四所示：

（12分）

图四

六、证明题（本题共8分）

18．证明：设xA，则AA，（1分）

因为AA=BB，故BB，则有xB，（3分）

所以AB．（5分）

设xB，则BB，（6分）

因为AA=BB，故AA，则有xA，所以BA．（7分）

故得A=B．（8分） 5

离散数学 6

离散数学 7

离散数学 8

离散数学

试卷代号：1009

国家开放大学（中央广播电视大学）2014年春季学期“开放本科”期末考试

离散数学（本） 试题（半开卷）

一、单项选择题（每小题3分，本题共15分） 9

离散数学 10

离散数学 11

离散数学 12

离散数学 13

离散数学 14

离散数学

一、单选题：在下列各题的备选答案中选择一个正确的。（每题3分，共18分）

1、若集合Ａ＝{a，b，c}，Ф为空集合，则下列表示正确的是（ ）

;AＡ、｛a}A; B、{a}　　Ｃ、aA; D、Ａ。

2、 Ｐ：我将去市里，Ｑ：我有时间，例题“我将去市里，仅当我有时间时”符号化为（ ）

Ａ．Ｐ→Ｑ Ｂ．Ｑ→Ｐ Ｃ． Ｐ Ｑ Ｄ．┐Ｇ∨┐Ｐ

3、 题 y P(y)取真值为1的充分必要条件 是( )

A 、对任意y, P(y)都取真值1 ； B、存再一个y, 使P(y)取真值1 ； 15

离散数学 C、存在某些y, 使P(y)取真值1 ； D、以上(A),(B),(C)都不对 。

4、设图Ｇ的相邻矩阵为

则Ｇ的顶点数为（ ）

Ａ．３ Ｂ．４ Ｃ．５ Ｄ．６

5．H是有5个顶点的完全图 ,则从H中删去 ( )条边可以得到树.

A 。4 ； B 。5 ； C 。6 ； D 10 。

6． 设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>,}

二、填空题：（每空3分，共２4分）

7. 设集合Ａ＝｛ａ，ｂ，ｃ，ｄ｝，Ａ上的二元关系Ｒ＝｛（ａ，ｂ），（ａ，ｄ），（ｂ，ａ），（ｂ，ｃ），（ｃ，ｃ），（ｄ，ａ），（ｄ，ｄ）｝，则逆关系Ｒ-1的关系矩阵ＭR-1 ＝。

8. 命题公式┐（Ｐ→Ｑ）的主析取范式为

9. 有限图Ｇ是树是两个等价命题是

10. 设集合A ,B,其中A={a ,b ,c }, B ={1 ,2 },则

A×B =_________________________, B×A=___________________________.

11．设P，Q是两个命题，当且仅当_______________时，PQ的真值为1. 得 分 评卷人

16

离散数学 12、设数在集合A={a,b,c,d}上的二元关系R={(a,a),(a,b),(c,d)},则

R2=_______,R-1=_________.

三、计算解答题：（每题12分，共48分）

１3．化简下式：（Ｂ－（Ａ∩Ｃ）） ∪（Ａ∩Ｂ∩Ｃ）

１4．将下列命题符号化：

（1） Ｇ（ｘ）：ｘ是金子，Ｆ（ｘ）：ｘ是闪光的，命题“金子是闪光的，闪光的不一定是金子”

（2） 个体域为实数集，命题“任意实数总能比较大小”

１5．求命题公式)()(QPQP的真值表.

１6．是求命题公式Ｇ＝Ｒ（（ＲＳ）（ＳＲ）的主析取范式.

得 分 评卷人