上海交大离散数学作业

上海交大离散数学作业篇一

上海交大10年离散数学试题

上 海 交 通 大 学 试 卷（ A 卷）

（ 2009 至 2010 学年 第1学期 ）

班级号_______________________ 学号______________ 姓名 课程名称 离散数学 成绩

一、

选择题（40’， 每题2’，每题只有一个选项正确，请将答案写在题号前的括号里）

A．火星上有生命存在 B．雪是白的 C．我正在说谎 D．10 + 11= 101

（ ）2. 所有使命题公式P(QR)的真值为T的解释是（P,Q,R）=___

A．(F, F, F), (F, F, T), (T, F, F); B．(F, T, T), (F, T, F), (F, F, F); C．(T, F, F), (T, F, T), (T, T, F); D．(T, T, F), (T, F, T), (T, T, T). （ ）3. 下面关于命题公式的叙述不正确的是___

A．不是可满足的公式必永假

B．如果P是重言式，对其使用代入规则得到的公式Q不一定是重言式 C．如果PQ是重言式，那么P=Q D．如果P→Q是重言式，那么Q→P是重言式 （ ）4. 下面的联结词集合不是完备集的是______

A．{} （表示与非） B．{, →} C．{, } D．{, }

（ ）5. 下面不正确的是______

A．Q(PQ)P B．PPQ

C．PQQP D．(PQ)QP

（ ）1. 下面不是命题的是___

我承诺，我将严 格遵守考试纪律。

承诺人：

（ ）6. 下列公式中______是重言式

A．P→(PQ) B．(Q(P→Q))→P C．Q →(P →Q)

D．(P →Q)→((P→R) →(Q→R))

（ ）7. 设A(x)：x是成功人士，B(x)：x出身名门，命题“成功人士未必都出身名门”

符号化为______ A．(x)(A(x)B(x)) B．(x)(A(x)B(x)) C．(∀x)(A(x)∧B(x)) D．(∀x)(A(x)B(x))

（ ）8. 设个体域为{-1,1}，并对P(x,y)设定为P(-1,-1)=T, P(-1,1)=F, P(1,-1)=T,

P(1,1)=F,其真值为T的公式为______ A．(∀x)(y)P(x,y) B．(x)(∀y)P(x,y) C．(∀x)(∀y)P(x,y) D．(∀y)(x)P(x,y)

（ ）9. (x)(P(a,x) (∀y)Q(x,b,y))的前束范式为______

A. (x)(∀y)(P(a,x)∨Q(x,b,y)) B. (∀x)(y)(P(a,x)∧Q(x,b,y))

C. (x) (∀y)( P(a,x)∧Q(x,b,y)) D. (x) (P(a,x)∨(∀y)Q(x,b,y)) （ ）10.下列公式普遍有效的是______

A．((x)P(x)  (x)(Q(x))  (x)(P(x)  Q(x)) B．((x)P(x)  (x)(Q(x))  (x)(P(x)  Q(x)) C．(x)(P(x)  Q(x))  (x)(P(x)  Q(x)) D．(x)(P(x)  Q(x))  ((x)P(x)  (x)Q(x))

班级 学号 姓名

（ ）11. 下列公式与(x)((y)P(y)Q(x))等值的是______

A．(x)(y)(P(y)  Q(x)) B．(x)(y)(P(y)  Q(x)) C．(x)(Q(x)  (y)P(y)) D．(y)P(y)  (x)Q(x)

（ ）12. 根据归结推理规则，子句P(x)  Q(a,x)与P(y)  Q(y,b)的归结式是______

A．P(a) B．P(b)

C．P(a)  P(b) D．P(a)  P(b)

（ ）13. 下列说法错误的是______

A．给定G1的某个子图H，如果在G2中找不到与H同构的子图，则G1和G2一定不同构 B．任一非空无向图中的道路有无穷条

C．任何非平面图中一定存在一个子图是K 型图或者K 型图 (K 型图指K5的同胚，K 型图指K3，3的同胚)

D．给定赋权的叶子结点集合，则相应的Huffman树是唯一的 （ ）14. 下图中______不存在欧拉回路

(1)

(2)

(1)

(2)

（ ）15. 下面说法错误的是______

A．若简单图每个结点的度大于等于B．Kn的H回路含有

n

，则G有H回路 2

1

n(n1)条边 2

C．如果一个图G的子图是非平面图，则G一定是非平面图

D．简单图G的任意结点vi，vj之间恒有d(vi)d(vj)n，则G存在H回路{上海交大离散数学作业}.

（ ）16. 一个无向图有五个结点，其中4个的度数是1, 2, 3, 4，则第5个结点的度数

不可能是______ A．0 B．2 C．4 D．5

（ ）17. 在平面图G的某个域内增加一个结点及连接该结点与该域的边界上某结点的一条

边，得到一个新图G，那么以下正确的是______ A．GG （G为G的对偶图） B．GG C．G=G D．以上都不对

（ ）18. 下列说法错误的是______

A．K3,3是边数最少的非平面图 B．K5是结点数最少的非平面图 C．K6中不存在K型子图

D．K3,3去掉任意一条边所形成的图是可平面图 （ ）19. 下图中存在Ｈ回路的图有______个

(1)

*

**

*

*

*

*

A．0 B．1 C．2 D．3

（ ）20. 下列图中，和M图同构的图（不计M图本身）有______个

A．1 B．2 C．3 D．4

班级 学号 姓名

二、

填空题（20’，每空2’）

1． 设P:天下大雨，Q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”

的符号化形式为____________________________________________________________。 2． 命题公式P→Q的主析取范式为_______________________________________________。 3． PQ可以用（表示或非）表示为

__________________________________________________________________________。 4． 设个体域是人类，谓词F(x,y)表示“x的父亲是y”，则公式

(x)(y)(F(x,y) z(z  y  F(x,z))

的自然语言含义是_______________________________________________________。

5． 公式(x)(y)(z)(w)P(x,y,z,w)的Skolem标准型(仅保留全称量词的前束形)是

__________________________________________________________________________。 6． 在论域{1,2}上公式(∀y) (x)P(x,y)可写成命题逻辑公式

__________________________________________________________________________。 7． 已知一棵树T中有9个结点，度为4、3的结点各一个，度为2的结点有两个，其余为

树叶结点，T的树叶结点数为_________________________________________________。 8． 一个林中有n个结点，k个连通支，则边数m=__________________________________。 9． 下图中最短树的权值总和是__________________________________________________。

10． 平面图G有n个结点，m条边，d个域，k个连通支，则G的对偶图G*的连通支的个数为{上海交大离散数学作业}.{上海交大离散数学作业}.

_________________________________________________________________________。

上海交大离散数学作业篇二

离散数学第一次作业——参考答案

4.用等值演算法证明下面等值式：

(2)(p→q)∧(p→r)(p→(q∧r))

(4)(p∧q)∨(p∧q)(p∨q) ∧(p∧q)

证明（2）(p→q)∧(p→r)

 (p∨q)∧(p∨r)

p∨(q∧r))

p→(q∧r)

（4）(p∧q)∨(p∧q)(p∨(p∧q)) ∧(q∨(p∧q))

(p∨p)∧(p∨q)∧(q∨p) ∧(q∨q)

1∧(p∨q)∧(p∧q)∧1

(p∨q)∧(p∧q)

14. 在自然推理系统P中构造下面推理的证明：

(4)前提：qp,qs,st,tr

结论：pq

证明：

② tr

②t

③qs

④st 前提引入 ①化简律 前提引入 前提引入

③④等价三段论 ⑤qt

⑥（qt）(tq) ⑤ 置换

⑦（tq）

⑧q

⑨qp

⑩p ⑥化简 ②⑥ 假言推理 前提引入 ⑧⑨假言推理

⑧⑩合取 11pq ○

P59. 18. 在自然推理系统P中构造下面推理证明

（1） 如果今天是星期六，我们就要到颐和园或圆明园去玩，如果颐和园游人太多，

我们就不去颐和园玩，今天是周末颐和园游人太多，所以我们去圆明园玩。 证明： 设p：今天是星期六，q：我们到颐和园玩，r:我们到圆明园玩，s:颐和园游人太多

前提：p  (q∨r), s q ,p ,s

结论：r

推理：① s q

P86. 22. 在自然推理系统N£中，构造下列推理的证明。 ② s ③ q ④ p 前提引入 前提引入 ①②假言推理 前提引入 前提引入 ④⑤假言推理 ③⑥析取三段论 ⑤ p  (q∨r) ⑥ q∨r ⑦ r

（1） 偶数都能被2整除。6是偶数。所以6能被2整除。

设：F（x）:x为偶数，G（x）:x能被2整除，a：6

前提：x(F(x) →G(x)), F(a)

结论：G（a）

证明：

①任意x（F（x）—>G（x）） 前提引入

②F（a）—>G（a） ①全称量词消去规则

③F（a） 前提引入

④G（a） 假言推理

上海交大离散数学作业篇三

离散数学作业题

华南理工大学网络教育学院 2013–2014学年度第一学期 《 离散数学 》作业

1．设命题公式为  Q （P  Q）  P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。–

2．用直接证法证明

前提：P  Q，P  R，Q  S 结论：S  R{上海交大离散数学作业}.

3．在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x

喜欢骑自行车。

4．用直接证法证明：

前提：（x）（C（x）→ W（x）∧R（x）），（x）（C（x）∧Q（x）） 结论：（x）（Q（x）∧R（x））。

5．设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。

(1) 给出关系R； （2） 给出COV A

（3） 画出关系R的哈斯图；

（4） 给出关系R的极大、极小元、最大、最小元。

6．求带权图G的最小生成树，并计算它的权值。

7．给定权为1，9，4，7，3；构造一颗最优二叉树。

8．给定权为2，6，3，9，4；构造一颗最优二叉树。

9、给定权为2，6，5，9，4，1；构造一颗最优二叉树。

10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，

d:10%,e:10%,f:5%。试给出传输这6个字母的最佳前缀码？问传输1000个字

符需要多少位二进制位？

上海交大离散数学作业篇四

2011—2012上海交大离散数学期末考试

上海交大离散数学作业篇五

离散数学大作业答案

一、简要回答下列问题：（每小题3分，共30分）

1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)x∈(AUB)UC，即 x∈AUB 或 x∈C即 x∈A 或 x∈B 或 x∈C即 x∈A 或 x∈B∪C即 x∈AU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)

2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？ 答：不同的对称关系有：8种 R = Φ R = {<1,1>} R = {<2,2>}

R = {<1,1>,<2,2>} R = {<1,2>,<2,1>}

R = {<1,1>,<1,2>,<2,1>} R = {<1,2>,<2,1>,<2,2>}

R = {<1,1>,<1,2>,<2,1>,<2,2>}

4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。 答：m0= ┐p∧┐q∧┐r m4 = p∧┐q∧┐r

6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。 如〈I，+〉是交换群。

8．什么是群中右模H合同关系？

答：设G是群，H是G的子群，a,b∈G，若有h∈H， 使得a =bh，则称a合同于b（右模H），记为a≡b（右mod H）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

显然，对任一x ∈ A，有 e ☆ x = x ☆ e = x 环

设<A ,△,☆>是具有两个二元运算△ 和*的代数系统，如果适合: ① <A ,△>是交换群(阿贝尔群)； ② <A,☆> 是半群；

③运算☆对运算△是可分配的，即：

a ☆ (b △ c) = (a ☆ b) △ (a ☆ c) (b △ c) ☆ a = (b ☆ a) △ (c ☆ a) 则称<A,△,☆>是环。

含幺环：

如果<A,☆>是独异点(或含幺半群)，则称<A,△,☆>是含幺环。

设 V=<A,☆>是半群，如果V中有幺元存在，则称V为含幺半群，也称为独异点。

设V=<A,☆>是代数系统，☆是非空集合A上的二元运算，如果☆是可结合的，即对任意的x,y,z∈A,有

(x☆y)☆z = x☆(y☆z) 则称V为半群。

10．什么是极大理想？请举一例。 答：一个环R的一个不等于的理想I叫做一个最大理想，假如除了R同I自己外没有包含A的理想。

二、（12分）R，S是集合A上的两个关系。试证明下列等式：

（1）(R•S)-1= S-1•R-1

-1-1-1-1

证明：先证(R•S) S•R，对任意(x，y) (R•S)，则(y，x) (R•S)，则存在aA，满足

-1-1-1-1-1-1

(y，a) R且(a，x) S，那么(x，a) S且(a，y) R，所以(x，y)  S•R，因此(R•S) S-1-1-1-1-1-1-1

•R；再证S•R (R•S)，对任意(x，y)  S•R，则存在aA，满足(x，a) S且(a，y) -1-1-1-1R，所以(y，a) R且(a，x) S，所以(y，x) (R•S)，所以(x，y) (R•S)，因此S•R (R-1

•S)。

（2）(R-1)-1= R

-1-1-1-1-1-1-1

证明：先证(R) R，对任意(x，y) (R)，则(y，x)  R，则(x，y)  R，所以(R) R；

-1-1-1-1-1-1-1-1-1

再证R (R)，对任意(x，y)  R，则(y，x)  R，则(x，y) (R)，所以R (R)。故(R)= R得证。

三、（20分）指出下列公式哪些是恒真的哪些是恒假的：

解：(1)P（P Q）Q是恒真的Q）， (2)（P Q）（P是恒真的，

(3)（P Q） （QR）（P R ）是恒真的， (4)（P Q）（P QP Q）是可满足的。{上海交大离散数学作业}.

四、（18分）指出下列表达式中的自由变量和约束变量，并指明量词的作用域：

（1）(xP(x)xQ(x))(xP(x)Q(y)) （2）xy((P(x)Q(y))zR(z)) （3）A(z)(xyB(x，y，a)) （4）x A(x)yB(x，y)

（5）(xF(x)yG(x，y，z))zH(x，y，z)

答：（1）(∀xP(x)∧∃xQ(x))∨(∀xP(x)→Q(y))3个x都是约束变量，y为自由变量第一个∀x的作用域是第一个P(x)第2个∀x的作用域是第2个P(x)∃x的作用域是Q(x) （2）x,y,z都是约束变量

（3）x,y是约束变量，z为自由变量

（4）A(x)中的x是约束变量，B(x,y)中的x是自由变量，y是约束变量

（5）F(x)中的x是约束变量 G(x,y,z)中的y是约束变量，x,z是自由变量 H(x,y,z)中的z是约束变量，x,y是自由变量。

五、（20分）一公司在六个城市c1，c2，…，c6中的每一个都有分公司。从ci到cj的班机

旅费由下列矩阵中的第i行第j列元素给出(表示没有直接班机)：

0 50  40 25 10 50 0 15 20  25  15 0 10 20  40 20 10 0 10 25

25  20 10 0 55 10 25  25 55 0

公司所关心的是计算两城市间的最便宜路线的表格。请准备一张这样的表格。

上海交大离散数学作业篇六

离散数学 作业 3~4 答案

『离散数学』课程

作业3：

P64：3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。

解：直接使用容斥原理。我们做如下设定：

A：会打篮球的学生； B：会打排球的学生； C：会打网球的学生；

根据题意：|E|=25，|A|=14，|B|=12，|C|=6，

|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2 由容斥原理:

|A∪B∪C|＝|A|

＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6-6-5-4+2=19

——————————————————————————————————————

但相当一部分同学没有直接使用容斥原理，

而是画了文氏图。

使用文氏图的方法，会发现此题存在问题：

表示只会打网球的同学是-1人，

此种情况与实际不符。

这可能是作者的疏忽，该教材第一版中，

“已知6个会打网球的人中有4人会打排球。”

一句是写作

“已知6个会打网球的人都会打篮球或排球。”

则用容斥原理或文氏图，都可以得到5的结果。

A：会打篮球的学生； B：会打排球的学生； C：会打网球的学生；

根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2

因为“会打网球的人都会打篮球或排球。”

所以C =（A∩C）∪（B∩C）

由容斥原理:

|C|=|（A∩C）∪（B∩C）|

= |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）|

可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）|

= 6-5+2=3

|A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|

=14+12+6-6-5-3+2=20

作业4：

P70：2

当A=φ时， 若A×B⊆A×C，B⊆C不一定成立；

当A≠φ时，若A×B⊆A×C，则B⊆C一定成立，反证如下：

若B⊆C不成立，则存在y∈B∧y∉C；又因为φ≠A，所以存在x∈A；可知序偶<x,y>∈A×B∧ <x,y> ∉ A×C ，与A×B⊆A×C矛盾。

P76：5

自反闭包r(R)= R∪{<b,b>}

对称闭包s(R)= R∪{<b,a>,<c,b>}

传递闭包t(R)= R∪{<a,c>}

P80：2

A中各元素关于R的等价类：

[a]=[b]={a,b}

[c]=[d]={c,d}

相应的划分{{a,b}，{c,d}}

当堂测试：

1、判断下程序段基本语句执行次数的O(f(n))。

int n=10,x=n,y=0;

while(x>=(y+1)*(y+1))

y++;

解：

第(k+1)取临界值，我们认为x=n≈(y+1)*(y+1)=(k+1)2

k≈n1/2-1 时间复杂度T(n)= O(n1/2)

2、利用容斥原理作答：某班有50 位同学参加期末考试，结果英语不及格的有15 人，数学不及格的有19 人，英语和数学都及格的有21 人，求英语和数学都不及格的有多少人？ 解：A：英语及格的学生 B：数学及格的学生

|E|=50 |A|=50-15=35 |B|=50-19=31 |A∩B|=21

根据容斥原理：|A∪B|=|A|+|B|-|A∩B|=35+31-21=45

∪B|=50-45=5

3、 R和S都是A={1, 2, 3, 4}上的二元关系，R={<1, 1>, <1, 2>, <1, 3>, <2, 3>, <2, 4>, <4, 3>, <4,

4>}，S={<1, 2>, <1, 3>, <2, 3>, <2, 4>, <3, 1>, <4, 3>}，试用矩阵相乘的方法求RS。 解：本题是拷给大家的PPT课件原题。

RS={<1,1>，<1,2>，<1,3>，<1,4>，<2,1>，<2,3>，<4,1>，<4,3>}

4、 设Ａ={a,b,c}，R={<a,b>,<b,c>,<c,a>}，求r(R)，s(R)，t(R)。

5、判断给出的关系是否是{1,2,3,4,5}上的等价关系。如果是，列出等价类。

（1）{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,3>,<3,1>,<3,4>,<4,3>}

不是等价关系，不满足传递性 有<1,3>,<3,4>却无<1,4>

（2）{<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<1,5>,<5,1>,<3,5>,<5,3>,<1,3>,<3,1>} 是等价关系，等价类为：

[1]=[3]=[5]={1,3,5}

[2]={2} [4]={4}

对应的划分{{1,3,5}，{2}，{4}}