下载文档原格式
杭州电子科技大学
硕士研究生复试同等学力加试科目考试大纲
学院：网络空间安全学院加试科目：离散数学
一、命题逻辑
1、命题及逻辑连接词的概念，自然语言的命题符号化。
2、真值表、命题公式与赋值、命题公式的类型。
3、命题的等价演算。
4、范式。
5、命题公式的推理演算。
二、谓词逻辑
1、个体词、谓词、量词及自然语言命题符号化。
2、谓词公式的解释。
3、谓词公式的等价演算。
4、谓词公式的推理规则及演绎推理。
三、集合和关系
1、集合的概念及集合之间的关系。
2、集合的运算。
3、集合的基本等价式。
4、序偶的概念及笛卡儿积。
5、关系的定义及运算。
6、关系的性质。
7、关系的闭包。
8、等价关系与划分。
9、函数的概念与类型。
10、复合函数和逆函数及相关结论。
四、代数结构
1、代数系统的概念。
2、半群、有幺半群、群的概念及性质。
3、循环群、交换群、子群、正规子群等重要概念以及这些代数结构的特性。
4、陪集及拉格朗日定理的应用。
五、图论
1、图、子图、顶点的度等图论基本概念。
2、路、回路的概念，图的连通性及割集的概念。
3、最短通路。
4、树与生成树。
5、欧拉图和哈密尔顿图。
6、有向图的概述。
7、根树与最优二叉树。
参考书目：《应用离散数学》，方景龙、周丽编著，人民邮电出版社，2014.09。
§1.2 命题公式与等价演算习题1.21. 设p 、q 和r 为如下简单命题：p ：532=+。
q ：大熊猫产在中国。
r ：复旦大学在广州。
求下列复合命题的真值。
（1）r q p →↔)(（2）p q p r ⌝↔∧→))((（3）)(r q p r ∨⌝∨⌝→⌝（4）))(()(r q p r q p →⌝∨⌝↔⌝∧∧解 因为p 、q 和r 分别取1，1，0。
所以（1）00)11()(=→↔=→↔r q p ；（2）01))11(0())((=⌝↔∧→=⌝↔∧→p q p r ； （3）0)011(0)(=∨⌝∨⌝→⌝=∨⌝∨⌝→⌝r q p r ；（4）1)0)11(()011())(()(=→⌝∨⌝↔⌝∧∧=→⌝∨⌝↔⌝∧∧r q p r q p 。
2. 构造下列复合命题的真值表，并由此判断它们是否永真式、永假式和可满足式。
（1）q p ⌝→（2）q p ↔⌝（3）)()(q p q p →⌝∨→ （4）)()(q p q p ⌝→⌝∧⌝→（5）)()(q p q p ↔⌝∧↔（6）)()(q p q p ⌝↔⌝∨⌝↔解 （1）是可满足式。
（2）是可满足式。
（3（4）是可满足式。
（5（6）是永真式。
3. 构造下列复合命题的真值表，并由此判断它们是否永真式、永假式和可满足式。
（1）r q p →↔)(（2）p q p r ⌝↔∧→))((（3）)(r q p r ∨⌝∨⌝→⌝（4）))(()(r q p r q p →⌝∨⌝↔⌝∧∧解 （1）是可满足式。
（2（3）是可满足式。
（4）是可满足式。
4. 用真值表证明下面的等价式 （1）B A B A ⌝∨⌝=∧⌝)( （2）A B A A =∨∧)(（3）B A B A ∨⌝=→（4）)()(A B B A B A →∧→=↔（5）)()()(C A B A C B A ∧∨∧=∨∧ 解 （1）（2）（3）（4）5. 只使用命题变元p和q能构造多少不同的命题公式真值表？解能构造出16（2的4次方）种不同的命题公式真值表。
习题1.3
1. 下列命题公式哪些是析取范式哪些是合取范式？ （1）)()(r q q p ∧∨⌝∧⌝ （2）)()(q p q p ∨⌝∧⌝∨ （3）q r p ∨⌝∧⌝)(
（4）q q p ⌝∧∨)( （5）q p ∨⌝ （6）r q p ⌝∧⌝∧⌝ （7）p ⌝ （8）q
（9）1
（10）0
解 是析取范式的有：(1)、(3)、（5）、（6）、(7)、 (8)、（9）、（10）；是合取范式有：（2）、（4）、（5）、（6）、(7)、 (8)、（9）、（10）。
2. 在下列由3个命题变元r q p 、、组成的命题公式中，指出哪些是标准析取范式哪些是标准合取范式？ （1）)()(r q p r q p ∧∧⌝∨∧⌝∧⌝ （2）)()(r q p r q p ∨∨⌝∧⌝∨⌝∨ （3）q r q p ∨⌝∧⌝∧⌝)( （4）)()()(r q r p q p ∨∧⌝∨⌝∧∨ （5）r q p ⌝∨∨⌝ （6）r q p ⌝∧⌝∧⌝
（7）1
（8）0
解 是标准析取范式的有：（1）、（6）、（8）；是标准合取范式的有：（2）、（5）、（7）。
3. 找出一个只含命题变元p 、q 和r 的命题公式，当p 和q 为真而r 为假时命题公式为真，否则为假。
解 r q p ⌝∧∧。
4. 找出一个只含命题变元p 、q 和r 的命题公式，在p 、q 和r 中恰有两个为假时命题公式为真，否则为假。
解 ))()()(r q p r q p r q p ∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧。
5. 利用等价演算法求下列命题公式的标准析取范式，并求其成真赋值。
（1）)()(p q q p ∨⌝→→⌝
（2）r q q p ∧∧→⌝)(
（3）)())((r q p r q p ∨∨→∧∨ 解（1） )()(p q q p ∨⌝→→⌝
)()(p q q p ∨⌝∨∨⌝=
p q q p ∨⌝∨⌝∧⌝=)(
)()()()()(q p q p q p q p q p ∧∨⌝∧∨⌝∧⌝∨⌝∧∨⌝∧⌝=
)()()(q p q p q p ∧∨⌝∧∨⌝∧⌝=
除0=p ，1=q 外，其余均为成真赋值。
(2) r q q p ∧∧→⌝)(r q q p ∧∧∨⌝⌝=)(r q q p ∧∧⌝∧=0= 这是永假式，不存在成真赋值。
(3) )())((r q p r q p ∨∨→∧∨
r q p r q p ∨∨∨∧∨⌝=))(( r q p r q p ∨∨∨⌝∨⌝∧⌝=))((
r q p r p q p ∨∨∨⌝∧⌝∨⌝∧⌝=)()(
)()()()(r q p r q p r q p r q p ⌝∧∧⌝∨⌝∧⌝∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝= )()()()(r q p r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨
)()()()(r q p r q p r q p r q p ∧∧∨⌝∧∧∨∧∧⌝∨⌝∧∧⌝∨ )()()()(r q p r q p r q p r q p ∧∧∨∧⌝∧∨∧∧⌝∨∧⌝∧⌝∨ )()()()(r q p r q p r q p r q p ∧∧⌝∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝=
)()()()(r q p r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨
这是永真式，所有赋值都是成真赋值。
6. 利用等价演算法求下列命题公式的标准合取范式，并求其成假赋值。
（1）p q p ⌝∧⌝→⌝)(
（2）)()(r p q p ∨⌝∨∧
（3）r q p p ∨∨→))((
解 （1）p q p ⌝∧⌝→⌝)(p q p ⌝∧⌝∨⌝⌝=)(p q p ⌝∧∧=)(0= 这是永假式，所有赋值都是成假赋值。
（2）)()(r p q p ∨⌝∨∧
)()()()(r q p q r p p p ∨∧⌝∨∧∨∧⌝∨=
)()()()()()(r q p r q p r q p r q p r q p r q p ∨∨⌝∧∨∨∧⌝∨∨⌝∧∨∨⌝∧∨⌝∨∧∨∨=)()()()(r q p r q p r q p r q p ⌝∨∨⌝∧∨∨⌝∧∨⌝∨∧∨∨=
成假赋值为：0,0,0===r q p ；0,1,0===r q p ；
0,0,1===r q p ；1,0,1===r q p
（3）r q p p ∨∨→))((r q p p ∨∨∨⌝=1=
这是永真式，不存在成假赋值。
7. 利用真值表法求下列命题公式的标准析取范式和标准合取范式。
（1）)(q p →⌝
（2）)()(q p q p ⌝↔→∨⌝ （3）r q p →→)(
（
4
）
))(())((r q p r q p ⌝∧⌝→⌝∧∧→
解 （1）
所以标准析取范式为
q p m ⌝∧=10
标准合取范式为
)()()(110100q p q p q p M M M ⌝∨⌝∧⌝∨∧∨=∧∧
（2）
所以标准析取范式为
)()(1001q p q p m m ⌝∧∨∧⌝=∨
标准合取范式为
)()(1100q p q p M M ⌝∨⌝∧∨=∨
（3）
所以标准析取范式为
111101100011001m m m m m ∨∨∨∨
)()()()()(r q p r q p r q p r q p r q p ∧∧∨∧⌝∧∨⌝∧⌝∧∨∧∧⌝∨∧⌝∧⌝=
标准合取范式为
)()()(110010000r q p r q p r q p M M M ∨⌝∨⌝∧∨⌝∨∧∨∨=∧∧
所以标准析取范式为
)()(111000r q p r q p m m ∧∧∨⌝∧⌝∧⌝=∨
标准合取范式为
110101100011010001M M M M M M ∧∧∧∧∧
)()()()()()(r q p r q p r q p r q p r q p r q p ∨⌝∨⌝∧⌝∨∨⌝∧∨∨⌝∧⌝∨⌝∨∧∨⌝∨∧⌝∨∨=
8. 假定用n 个命题变元给出一个真值表。
证明可依据此表构造一个命题公式，使其真值与此表一致。
证明 略
9. 设A 是含有n 命题变元的命题公式，证明
（1）A 是永真式当且仅当A 的标准析取范式含有全部n
2个最小项。
（2）A 是永假式当且仅当A 的标准析取范式不含任何最小项（即标准析取范式为0）。
（3）A 是可满足式当且仅当A 的标准析取范式至少含有一个最小项。
证明 略
10. 设A 是含有n 命题变元的命题公式，证明
（1）A 是永假式当且仅当A 的合取析取范式含有全部n 2个最大项。
（2）A 是永真式当且仅当A 的标准合取范式不含任何最大项（即标准合取范式为1）。
（3）A 是可满足式当且仅当A 的标准合取范式不包含所有最大项。
证明 略
11. 求下列命题公式的标准析取范式，再根据标准析取范式求标准合取范式。
（1）r q p ∨∧)(
（2）)()(r q q p →∧→ 解 （1）略
（2）)()(r q q p →∧→
)()(r q q p ∨⌝∧∨⌝=
)()()()(r q q q r p q p ∧∨⌝∧∨∧⌝∨⌝∧⌝=
)()()()(r q q q r p q p ∧∨⌝∧∨∧⌝∨⌝∧⌝=
)()()()(r q p r q p r q p r q p ∧∧∨∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝=
111011001000m m m m ∨∨∨=
所以标准合取范式为
110101100010M M M M ∧∧∧
)()()()(r q p r q p r q p r q p ∨⌝∨⌝∧⌝∨∨⌝∧∨∨⌝∧∨⌝∨=
12. 求下列命题公式的标准合取范式，再根据标准合取范式求标准析取范式。
（1）q q p →∧)( （2）r q p →↔)(
（3）q p p r ∧∧→⌝)( 解 （1）、（3）略 （2）r q p →↔)(
r p q q p ∨∨⌝∧∨⌝⌝=))()(( r p q q p ∨⌝∧∨⌝∧=)()( r p q q p ∨⌝∧∨⌝∧=)()(
r p q q q p p q p ∨⌝∨⌝∧∨⌝∧⌝∨∧∨=))()()()(( r p q q p ∨⌝∨⌝∧∨=))()(( )()(r q p r q p ∨⌝∨⌝∧∨∨=
110000m M ∧=
所以标准析取范式为
111101100011010001m m m m m m ∧∧∧∧∧ )()()(r q p r q p r q p ∨∨⌝∧⌝∨∨⌝∧∨⌝∨⌝= )()()(r q p r q p r q p ∨∨∧∨⌝∨∧⌝∨⌝∨∧
13. 三个人估计比赛结果，甲说：“A 第1，B 第2”，乙说：“C 第2，D 第4”，丙说：“A 第2，D 第4”。
结果三人估计的都不全对，但都对了一个。
试利用求范式的方法推算出D C B A 、、、分别是第几名？
解 略。
