离散数学作业分析

离散数学作业分析上海交通大学离散数学作业分析/52上海交通大学可信任数字计算实验室第1章命题逻辑第1章命题逻辑上海交通大学离散数学作业分析/521.

⋀

≦

→2.

↔3.

≦

≦

∨

→4.↔

≦

≦

∨1.1命题与联结词【习题5

】设

：“我吃饭前完成作业”，

：“今天下雨”，:“我去看球赛”，试写出下面符号表达式对应的自然语言：上海交通大学离散数学作业分析/52解：如果我吃饭前完成作业并且今天不下雨，那么我就去看球赛。我吃饭前完成作业当且仅当我去看球赛。

如果我吃饭前没完成作业或今天下雨两件事都没发生，那么我就去看球赛。

我去看球赛当且仅当我吃饭前没完成作业并且今天下雨这两件事没有同时发生。分析：在这种类型的题目中，要特别注意等价联结词的表述。1.1命题与联结词上海交通大学离散数学作业分析/521.2.≦→=

0,

求

≦ ∨

≦

→→=

0,

求

≦

∨3.≦↔↔⋀=1,求⋀≦⋀→→⋀⋀⋀1.2命题公式上海交通大学离散数学作业分析/52【习题3】求给定条件的命题公式的真值。≦

→=0，可得=

0，=

0，2.由已知，则

≦

∨⋀·3.由已知，

≦=1，↔

=

1↔

=1，可得=

0，

=

1→⋀⋀

⋀≦⋀·=0，=

1，→⋀⋀

⋀≦⋀→

⋀0=

1=→

⋀

=上海0交通大学离散数学作业分析/521.2命题公式解：1.由已知，→则

≦ ∨

≦

→=

0=0，可得=

0，=

1，分析：在这种类型的题目中，要利用好形如

→=0这样的条件。同时注意在遇到如第3小题这样的情况时，要进行分类讨论。1.2命题公式上海交通大学离散数学作业分析/522.

≦(

↔

)

∨

⋀≦

⋀4.≦10→→

≦→→.

⋀

⋀

→

⋀

→∨∨⋀↔

→1.3等值演算上海交通大学离散数学作业分析/52【习题1】证明下列等值式：证明：2.

≦(

↔

)≦≦ ∨

≦≦

⋀⋀↔⋀

∨∨∨⋀≦

⋀4.→→⋀

→≦0

→

≦≦ ∨

≦

∨≦→

∨→

≦∨

≦

≦1⋀

→

≦1.3等值演算1上海交通大学离散数学作业分析/5210.∨∨

∨⋀

⋀

→

⋀

→≦∨

⋀

⋀

∨

⋀

≦

∨≦

∨ ∨

≦ ∨

≦

⋀

∨

∨

∨≦⋀∨

⋀↔

→≦∨

≦

⋀

∨≦≦⋀

↔∨

≦∨↔∨≦

∨

∨

↔

≦≦

∨

∨

≦ ∨

≦

⋀

∨分析：大家要牢记28个基本等值式，做到融会贯通，熟练应用。这种题型在考试中属于基础得分题，不能轻易放弃。1.3等值演算上海交通大学离散数学作业分析/521.4命题公式的范式【习题5】两位同学同住一间宿舍。宿舍照明电路按下述要求设计：宿舍门口装一个开关

，两位同学的床头各自装一个开关

,

。当夜晚回宿舍时，拉一下开关

，室内灯点亮；上床后拉一下开关

或

，室内灯熄灭；这样以后，拉一下

,

,

三个开关中的任何一个，室内灯亮。如果室内灯

亮和灭分别用1

和O表示，试求出

用

,

,

表示的主析取范式和主合取范式。上海交通大学离散数学作业分析/52解：首先构造真值表如下：1.4命题公式的范式上海交通大学离散数学作业分析/5200000011010101101001101011001111·

主析取范式：001

∨

010

∨

100

∨

111∨

≦

⋀

⋀≦

∨∨

⋀

⋀≦

⋀≦

⋀⋀≦

⋀≦·

主合取范式：

000

⋀

011

⋀

101

⋀

110∨

∨

⋀∨

≦ ∨

≦⋀

≦ ∨

≦

∨⋀

≦

∨ ∨

≦分析：此题属于范式部分的应用题型，既要求大家熟悉范式的定义，也要能够熟练应用。构造真值表是解题的关键。1.4命题公式的范式上海交通大学离散数学作业分析/52=

1, =

1,=0时，↑↑

↑↑

=

1=

0分析：大家要注意题目的要求，不要忘记举例说明。1.5联结词的功能完全集上海交通大学离散数学作业分析/52【习题6

】证明：

↑↑

，即↑的交换律成立，但↑的结合律不成立，试举例说明。解：↑

≦

⋀

≦

⋀↑

满足交换律。但是结合律不成立。如当【习题1】利用归结法证明：3.

(∨)

∧(→)∧

(→)

⇒∨5.

≦(→→↔)

→≦(∨),

(→)

∨≦,1.8命题逻辑归结推理法上海交通大学离散数学作业分析/52证明：3.

(

∨ )

∧

(

→

)

∧

(

→

)⇒化为合取∨范式：(

∨)

∧(≦∨)∧(≦∨)∧

≦∧≦子句集：=*∨∨,

≦

∨,

≦ ,

≦

+,≦1.8命题逻辑归结推理法上海交通大学离散数学作业分析/52(1)

≦

∨2

≦3

≦(4)

∨5(6)

≦

∨78

≦(9)

01和(2)的归结3和(4)的归结5和(6)的归结7和(8)的归结1.8命题逻辑归结推理法上海交通大学离散数学作业分析/52证明：5.

≦(→ )

→

≦(∨),

(→ )

∨

≦化为⇒合取范↔式：⇔((≦∨∨≦)

∨∨(≦

∧≦

)∧≦))∧(∧

(∨

)∧

(≦∨

≦

)⇔

(≦∨∨

≦∨)

∧≦

)

∧

(≦(

∨

≦∨∨

≦)∧

∧(

∨)

∧

(≦ ∨

≦)子句集：=*≦∨∨≦,

≦∨∨≦,∨≦∨≦,,∨,

≦∨≦

+1.8命题逻辑归结推理法上海交通大学离散数学作业分析/52(1)

≦(2)∨≦∨(3)

≦∨1和(2)的归结(4)∨(5)3和(4)的归结(6)≦∨≦∨(7)∨≦2和(6)的归结(8)≦∨

≦1.8命题逻辑归结推理法上海交通大学离散数学作业分析/52第2章谓词逻辑第2章谓词逻辑上海交通大学离散数学作业分析/522.1谓词逻辑的基本概念上海交通大学离散数学作业分析/52【习题2】将下列命题符号化：5.存在唯一的偶素数。7.每个人的外祖母都是他母亲的母亲。10.没有不犯错误的人。13.有些液体能溶解任何金属。2.1谓词逻辑的基本概念5.存在唯一的偶素数。解：设表示“

是素数”，

表示“是偶数”，示“,=表”，论域

为正整数集，则命题为：∃∧∧

∀∧→∧分·析：∃·

∃上海交通大学离散数学作业分析/52∧,，没有表示出唯一性；∧

∀

∧∧,

，“→”与“∧”不能等同2.1谓词逻辑的基本概念上海交通大学离散数学作业分析/527.每个人的外祖母都是他母亲的母亲。解：设

,

表示“

是的母亲”，

,的外祖表示“

是母”，论域

为所有人的集合，则命题为：∀

∀

,

→

∃

,

∧分析：设,表示“

的外祖母”，表示“

的母亲”，命题错误地使用了二阶谓词，表示为：∀

→2.1谓词逻辑的基本概念10.没有不犯错误的人。解：设

表示“

是人”，误”，上海交通大学离散数学作业分析/52表示“

犯错→论域

为所有事物的集合，则命题为：∀或者≦∃∧

≦2.1谓词逻辑的基本概念13.有些液体能溶解任何金属。解：设上海交通大学离散数学作业分析/52表示“ 是液体”， 表示“ 是金属”，,

表示“

能溶解

”，论域

为所有事物的集合，则命题为：∃

∧

∀

→

,分析：∃

∀∧∧,

是常见错误。2.1谓词逻辑的基本概念上海交通大学离散数学作业分析/52一阶谓词将命题符号化简要说明：设 为个体域：1.“

中所有都有性质 ”，符号化为∀有性质 ”，符号化为∃2.“ 中有的3.“对

中所有

而言，如果

有性质

，则就有性质

”，符号化为∀

→4.

“对

中有的（存在）

具有性质，又具有性质

”，符号化为∃∧2.1谓词逻辑的基本概念5.“对于则有与关系中所有

,

而言，若

有性质

，

有性质

，”,符号化为∀

∀∧上海交通大学离散数学作业分析/52→,6.“对于，使得中所有

而言，若

具有性质与

有关系

”，符号化为，就存在有性质∀→∃∧,7.“存在着中有性质，并且对中所有而言，如果有性质 ，则与就有关系”，符号化为∃

∧8

.

“

中存在着

与有关系

”，符号∃

∃∀

→

,，

有性质

，

有性质化为∧

∧

,，并且与2.1谓词逻辑的基本概念上海交通大学离散数学作业分析/52【习题6】设论域是整数集合，令：,,

表示“=”,表示“

=”,表示“

>”试符号化下列命题：如果<和<0,则>

z。解：,

∧,

,

∧0,,→,

,

∧分析：常见错误：→,∧,0,2.2谓词逻辑公式→

∀→【习题5】给定下列命题：∀→∀判断命题的真值是否是1？试证明之。证明：采用反证法。假设原命题真值为0，则必有∀上海交通大学离散数学作业分析/52∀→

∀真值为0。又因为∀→∀真值为0，故∀真值为1与

∀

真值为0

，

而这与

∀矛盾。故原命题真值为1。→真2.3谓词逻辑的等值演算与前束范式【习题3】求公式∃

→→

≦

∃→

∀的前束范式。→→

≦

∃→∀→

≦

∃上海交通大学离散数学作业分析/52→

∀解：∃∃→≦

∃∀

≦∀

∃

∨

≦∃≦ ∨

≦ ≦

∃∨

∨

∀∨

∃∧

∃≦≦∨

≦∧

≦∨2.4

Skolem标准型【习题2】求下列各式的无∃前束范式：∀∀解：∀

→

∃∀

≦∀∀,

∨

∀,

∨∀→

∃,

∨,

∨

∀∨

∃∃

∀

≦

∨≦

∨上海交通大学离散数学作业分析/52,∨2.6谓词逻辑的归结推理法【习题2

】设

1

=

∃∧→∀,,2

=

∀∀→→

≦,,=

≦

∃

∀,∧,∧

∀

∀

≦∨

≦,，用归结推理法证明∨

≦1

∧

2

⇒

。

解：令

=

1

∧∧≦

,

∨∧,

∨

≦

,∧

∀∃

∀

∧,∃∀

∀

∀∧≦≦

,

∨

≦∧∧

∃

∀上海交通大学离散数学作业分析/522.6谓词逻辑的归结推理法∧

≦

,

∨上海交通大学离散数学作业分析/52∀

∀

∀,∧≦∨

≦∨

≦,∧∀,∧∀

∀

∀∧

≦,∨,∧≦∨

≦∨

≦,∧,∧所以子句集为：=,≦,

,,,∨,,

≦∨

≦∨

≦归结推理过程如下：2.6谓词逻辑的归结推理法12

≦≦3

≦∨

≦∨,∨

≦,45

≦,6

≦,

∨7

≦,8,9

□,1 2归结上海交通大学离散数学作业分析/523 4归结5 6归结7 8归结第1章无向图第11章无向图上海交通大学离散数学作业分析/5211.1无向图的基本概念【习题14】假设某天晚上

先生和太太参加了一个桥牌聚会参加的人中还有另外三对夫妇，并且有几次握手。没有人和自己握手，没有夫妻之间握手，并且没有两个人握手超过一次。当其他人上海交通大学离散数学作业分析/52告诉先生，他或她握了几次手时，答案都不一样。问先生和太太分别握了几次手？解：由于当其他人告诉

先生，他或她握了几次手时，答案都不一样，所以其他7个人分别握手0、1、2、3、4、5、6次，下面我们来讨论每个人分别握手的次数。11.1无向图的基本概念这七个人中，有一个人比较特殊，即

太太，如果她握手次数为6次，那么说明她与其他6个人都握过手（因为她不能跟他丈夫握手），则这7个人每个人握手的次数均大于等于1次，这与题设“每个人握手次数不同”矛盾，故说明

太太握手次数不是6次。那么剩下的6个人中，有一个人握手次数为6，我们可以任意取这个人为

，那么他与除他太太的6个人分别握手1次，此时他的太太 握手次数为0，否则（用反证法）若 的握手次数不为0，

那么说明她至少握过一次手，而其他6个人又都与

握过手，那么就没有人握手0次，这与题设矛盾，故

握手次数为0。上海交通大学离散数学作业分析/5211.1无向图的基本概念下面去掉

、

及其所关联的边，所剩的子图为6个顶点，在这个子图中，除了

先生，其余5个人的握手次数为0、1、2、3、4

(但此时要记住，他们在原图中都与 握过一次手)这样利用上面的分析知在这个图中

太太不能握手4次，而其他4个人中任取一个人

握手4次（注意，这个人在原图中实际上海交通大学离散数学作业分析/52握过一次手），他的太太d握手就为上握了5次手，因为他还跟0次（同样在原图中为1次）。再去掉、下的2个人分别和a、及其所关联的边，剩下的子图中除

太太，剩、

分别握手2次和0次（在原图中为4次和2次，因为握过一次手），这样知，在原图中除了

太太，其余6个人分别握手0、1、2、4、5、6次，这样

太太就握手3次，根据上边的分析，知

先生实际上也握了3次手，分别与 、

、11.1无向图的基本概念上海交通大学离散数学作业分析/52分析：同学们在做这个题目的时候，很多人得到了正确的结果，但是没有分析的过程，或者是仅仅通过画出图形穷举来说明答案，但是有没有考虑所有情况。做这个题目需要将情况考虑全面，同时条理要清晰。11.1无向图的基本概念【习题15】证明：下面两个图是同构的。上海交通大学离散数学作业分析/5211.1无向图的基本概念上海交通大学离散数学作业分析/52证明：要证明

1

≅2,我们要给出顶点命名并给出一个双射，然后验证它保持联结关系：正如上面标记，将

、

、 、

、 、

分别映射到1、3、5、2、4、6，这是一个双射，即是从

1

到的一个同构。2类似我们可以证明下一个图的同构，但要注意映射的顺序，该图为

图的两种画法。11.1无向图的基本概念上海交通大学离散数学作业分析/52分析：有些同学虽然写出了映射，但是没有把映射的顺序写对，例如

上题，有些同学直接写

、

、

映射为1、2、3是显然不对的，一定要注意它们的联接关系。还有一些同学用书上给的必要条件来证明也是不对的，因为只是必要条件，不能说明两图一定同构，要说明同构，必须给出同构映射。11.2无向图的表示【习题2】求下图的关联矩阵。上海交通大学离散数学作业分析/5211.2无向图的表示11010011110000上海交通大学离散数学作业分析/52解：写出其关联矩阵为：0

0

1

1

1

0

00

0

0

0

1

1

1分析：这个题目有些同学把关联矩阵与邻接矩阵的概念的搞混了，建议把书上的概念好好看懂，另外一些同学直接写出关联矩阵而不做标号，建议把顶点与边的标号标好，结果才不至于混淆。11.3无向图的连通性【习题2】设为完全图，问：有多少圈？包含 中某边 的圈有多少？任意两点间有多少路？解：1.2.3.上海交通大学离散数学作业分析/52=3

2−2=1–2−2=0–211.3无向图的连通性上海交通大学离散数学作业分析/52【习题3】证明：若边中。证明：在

中的某一闭迹中，则在

的某一圈对于边

，设其两个顶点分别为由于 在