离散数学(一)

离散数学（一）知识梳理•逻辑和证明部分o命题逻辑题型▪命题符号化问题将自然语言转为符号化逻辑命题▪用命题变量来表示原子命题▪用命题联结词来表示连词▪命题公式的类型判断判断命题公式是否是永真式、矛盾式、可能式▪利用真值表判断▪利用已知的公式进行推理判断▪利用主析取和合取范式判断▪定理：A为含有n个命题变元的命题公式，若A的主析取范式含有2^n个极小项，则A为重言式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为矛盾式；若A的主合取范式含有2^n个极大项，则A为矛盾式，若极小项在0到2^n之间，则为可满足式，若含有0个极小项，则A为重言式▪翻译：一个命题公式化成主范式后，若所有项都分布在主析取范式中（主合取范式为1）则为重言式；若所有项都分布在主合取范式中（主析取范式为0）则为矛盾式；若均有分布，则为可满足式。

【思想来源：真值表法求主范式】▪一个质析取式是重言式的充要条件是其同时含有某个命题变元及其否定式；一个质合取式是矛盾式的充要条件是其同时含有某个命题变元及其否定式▪一个析取范式是矛盾式当且仅当它的每项都是矛盾式；一个合取范式是重言式当且仅当它的每项都是重言式▪求（主）析取或合取范式▪等值演算法▪ 1. 利用条件恒等式消除条件（蕴含和双条件）联结词，化简得到一个范式▪ 2. 在缺项的质项中不改变真值地添加所缺项，化简得到一个主范式▪ 3. 找出包含所有命题变元排列中剩余项，凑出另一个主范式（思想上类似于真值表法）▪真值表法▪ 1. 画出命题公式真值表▪ 2. 根据真值表结果求出主范式▪主析取范式：真值为1的所有项，每一项按对应01构成极小项▪主合取范式：真值为0的所有项，每一项按对应01构成极大项▪形式证明与命题推理利用推理规则构造一个命题公式的序列，证明结论▪形式证明：命题逻辑的论证是一个命题公式的序列，其中每个公式或者是前提，或者是由它之前的公式作为前提推得的结论，序列的最后一个是待证的结论，这样的论证也称为形式证明。

自学考试：离散数学复习(一)自学考试是一种能够让没有条件参加全日制学习的人继续学习的方式。

与传统的大学学习相比，它更为灵活和自由。

在自学考试中，离散数学是一门必修的科目，也是考试难点之一。

本文将从离散数学的定义、内容、复习方法以及注意事项等方面进行讲解。

一、离散数学的定义离散数学是研究数量的离散性质的数学分支学科，主要研究对象是离散的集合、函数、算法、逻辑、图论等。

它的研究对象并不是连续的，而是由一些个别的、离散的数量组成的。

二、离散数学的内容离散数学主要包括以下几个方面：1. 逻辑与集合论：又称数理逻辑，是离散数学的重要组成部分。

它主要涉及命题逻辑、谓词逻辑、逻辑推理等内容。

2. 离散数学的代数结构：主要包括半群、群、环、域等内容。

3. 布尔代数与逻辑设计：主要涉及布尔运算、代数基本定理、逻辑电路设计等方面。

4. 图论：涉及图的定义、图的类型、基本概念和定理、图的遍历等方面。

5. 计算机科学中的重要应用：涉及图论和逻辑设计等方面。

三、离散数学的复习方法1. 系统地复习课本，强调对每个概念和定理的理解和记忆。

2. 刻意练习，做大量的练习题，以此巩固知识点。

3. 找到与离散数学相关的书籍，进行阅读和学习，补充知识点。

4. 制定学习计划并严格执行，不断检查自己的学习进度。

四、注意事项1. 离散数学比较抽象，需要认真思考并理解其概念和定理。

2. 多做题，不要死记硬背，应该结合题目进行思考，理解知识点。

3. 有时间限制的考试需要注重时间管理，做题的时候应该合理分配时间。

4. 总结每次考试的弱点，找到自己的不足之处，并及时进行复习和巩固。

总之，离散数学是一门重要的学科，它具有广泛的应用领域，并且在计算机科学领域中具有重要地位。

对于自学考试的学生而言，掌握好离散数学的知识点是非常重要的。

希望本文对自学考试的离散数学复习有所帮助。

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

离散数学（1）复习笔记Ch1 命题逻辑的基本概念1.1 命题命题：能判断真假且⾮真即假的陈述句。

命题的真值，真命题，假命题。

* 真值待定 *简单命题 | 原⼦命题，复合命题。

1.2 常⽤的5个命题联结词否定，合取，析取，蕴涵，双蕴涵。

* 异或 | 排斥或 | 不可兼或 * 注意语义判断。

* p→q = ﹁ p∨q ** 必要条件 * 只有……才……；仅当……，……；……，仅当……。

注意命题符号化的蕴涵⽅向。

* domain * A horse is white. （×）联结词集，⼀元联结词，⼆元联结词。

* 优先顺序 * （），﹁，∧，∨，→，↔1.3 合式公式及其赋值命题常项 | 命题常元（值是确定的），命题变项 | 命题变元（真值可以变化的陈述句）。

合式公式 | 命题公式 | 命题形式 | 公式（wff）（well formed formulas），原⼦命题公式（单个命题变项），⼦公式。

* 单个命题变项是合式公式，没说命题常项。

*赋值 | 解释，成真赋值，成假赋值。

真值表。

* 真值表要点：赋值从00…0开始，按照⼆进制加法，直到11…1为⽌；按照运算的优先次序写出各⼦公式。

*命题公式的分类：重⾔式 | 永真式，⽭盾式 | 永假式，可满⾜式。

1.4 重⾔式与代⼊规则代⼊规则。

* 1. 公式中被代换的只能是命题变项（原⼦命题），⽽不能是复合命题。

2.对公式中某命题变项施以代⼊，必须对该公式中出现的所有同⼀命题变项施以相同的代换。

* 1.5 命题形式化命题形式化 | 符号化。

* 注意充分条件和必要条件的区别 ** 注意语义是否考虑完整 *1.6 波兰表达式中置式 | 中缀式，前置式 | 前缀式 | 波兰式，后置式 | 后缀式 | 逆波兰式。

Ch2 命题逻辑的等值和推理演算2.1 等值定理等值 | 等价，等值定理：设A，B为两个命题公式，A = B的充分必要条件是 A↔B为⼀个重⾔式。

1 / 6离散数学（1）复习题一、填空题1、集合S={n 100 | n ∈N}的基数为（ 0ℵ ）。

2、设R 是集合A 上的二元关系，则R 是对称的，当且仅当其关系矩阵（ 为对称矩阵 ）。

3、集合P={Ф，{a}}的幂集ρ(P)=（ {Ф,{Ф},{a}, {Ф，{a}} } ）。

4、设A={1,2,7,8}，B={i │i ∈N 且i 2<50}，则A —B=（ {8} ）。

5、设(A ，≤)是一个有界格，只要满足（ 每个元素均有补元 ），它也是有补格。

6、设S 为非空有限集，代数系统（ρ(S)，Y ，I ）中，ρ(S)对Y 的零元为（ S ），ρ(S)对I 的单位元为（ Ф ）。

7、重言式的否定式是（ 矛盾 ）。

8、设A=φ，B={φ，{φ}}，则B －A=（ {}{}φφ， ）。

9、集合A={1，2，…，10}上的关系R={（x ，y ）│x+y=10且x 、y ∈A}，则R 的性质为（ 对称的 ）。

10、有界格（P ，∧，∨）对于“∧”运算的零元为（ 0 ）。

11、设P ：张三可以做这件事，Q ：李四可以做这件事。

则命题“张三或李四可以做这件事”符号化为（ P Q ∨ ）。

12、设M={x| f 1（x ）=0}，N={x| f 2（x ）=0}，则方程f 1（x ）·f 2（x ）=0的答案为（ M N U ）。

13、设 |A|=m ，|B|=n ，则 |ρ(A ×B) | 等于（ 2m n ⨯ ）。

二、计算与证明题1、设A={0，1}，B={a ，b}，求：（1）A ×B ；（2）B ×A答：（1）()()()(){}0,,0,,1,,1,A B a b a b ⨯=（2）()()()(){},0,,0,,1,,1B A a b a b ⨯=2、（1）叙述幂集的定义；（2）求集合P={Ф，{a}}的幂集ρ(P)．。

《离散数学(1)》15春在线作业3
一、判断题（共8 道试题，共40 分。

）
1. 命题“存在一些人是大学生”的否定是所有的人都不是大学生。

A. 错误
B. 正确
正确答案：B
2. 如果太阳从东边出来，那么地球自转停止。

A. 错误
B. 正确
正确答案：A
3. 凡陈述句都是命题。

A. 错误
B. 正确
正确答案：A
4. 任一命题公式的主析取范式和它的主和取范式互为对偶式。

A. 错误
B. 正确
正确答案：A
5. “王兰和王英是姐妹”是复合命题，因为该命题中出现了联结词“和”。

A. 错误
B. 正确
正确答案：A
6. “蓝色和黄色可以调成绿色”是一个复合命题。

A. 错误
B. 正确
正确答案：A
7. 同一谓词公式，指定不同的论域，其真值不一定相同。

A. 错误
B. 正确
正确答案：A
8. “喜马拉雅山比华山高”是一个命题。

A. 错误
B. 正确
正确答案：B。

离散数学知识点整理（⼀）离散数学数学语⾔与证明⽅法集合幂集运算交集并集相对补集绝对补集对称差集运算律交换律结合律分配律德摩根律恒等式证明⽅法直接证明归谬法分情况证明构造性证明数学归纳法命题逻辑命题简单命题p,q,r复合命题基本复合命题五种复杂复合命题真值真命题假命题命题符号化联结词否定联结词¬否定式合取联结词∧合取式析取联结词∨析取式相容或p∨q排斥或(¬p∧q)∨(p∧¬q)蕴含联结词蕴含式p->q真值p真q假，p->q为真其他全为真前件p后件q等价联结词等价式p<->q真值p,q真值相同，p<->q为真不同为假‘当且仅当’公式命题常项p,q,r为定值变项p,q,r为变量合式公式/命题公式A，B，C，D永真式重⾔式永假式⽭盾式可满⾜式赋值/解释成真赋值成假赋值等值演算A<->B，则A<=>B等价式为重⾔式常⽤等值公式蕴含等值式A→B⇔¬A∨B德摩根律 ¬(A∨B)⇔¬A∧¬B联结词集优先顺序扩展与⾮联结词p↑q⇔¬(p∧q)或⾮联结词p↓q⇔¬(p∨q)联结词完备集(1)S={¬,∧,∨}(2)S={↑}(3)S={↓}范式分类析取范式主析取范式极⼤项合取范式主合取范式极⼩项计算推理概念蕴含式为重⾔式⇒形式结构(A1∧A2∧...∧A k)⇒B前提结论证明推理规则前提引⼊结论引⼊置换规则等值置换A⇔B:A⇒B;B⇒A推理定律特殊证明⽅法附加前提证明法(A1∧A2∧...∧A k)⇒A→B(A1∧A2∧...∧A k∧A)⇒B归结证明法归结规则(L∨C1)∧(¬L∨C2)⇒C1∨C2基本思想归谬法证明步骤结论的否定引⼊前提把所有前提化成合取范式，并将简单析取式作为单个前提归结规则进⾏推理推出0则推理正确⼀阶逻辑表达个体与总体之间的内在联系与数量关系概念个体词个体常项a,b,c....个体变项个体域x,y,z....谓词谓词常项表⽰具体性质或关系⼦主题 2谓词变项表⽰抽象性质或关系F，G....0元谓词不带个体变项的谓词当谓词为谓词常项时为命题量词全称量词存在量词符号化不同个体域形式可能不同引⼊特性谓词公式分类原⼦公式合式公式/谓词公式闭式A中不含⾃由出现的个体变项概念x:指导变元A:辖域x在A中约束出现A中出现的除x所有其他个体变项都为⾃由出现解释/赋值定义封闭的公式在任何解释下都变成命题分类永真式/逻辑有效式A在任何解释和任何赋值下均为真永假式/⽭盾式A在任何解释和任何赋值下均为假可满⾜式⾄少存在⼀个解释和⼀个赋值使A为真代换实例重⾔式的代换实例都是重⾔式⽭盾式的代换实例都是⽭盾式等值演算命题逻辑的代换实例等值式消去量词等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式规则置换规则换名规则前束范式存在但不唯⼀利⽤等值演算求前束范式Processing math: 100%。

《离散数学》在线作业（一）
A:错误
B:正确
参考选项：B
任意平面图至少是四色的。

A:错误
B:正确
参考选项：A
A:错误
B:正确
参考选项：A
任意函数一定有逆函数。

A:错误
B:正确
参考选项：A
模格一定是分配格。

A:错误
B:正确
参考选项：A
图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。

A:错误
B:正确
参考选项：B
质数阶群必是循环群。

A:错误
B:正确
参考选项：A
A:错误
B:正确
参考选项：A
任意一棵无向树至少有两片树叶（退化树除外）。

A:错误
B:正确
参考选项：B
A:错误
B:正确
参考选项：A
任何循环群必是阿贝尔群。

A:错误
B:正确
参考选项：B
若连通图所有结点度数均为奇数，则该图为欧拉图。

A:错误
B:正确
参考选项：A
任意一个谓词公式均和一个前束范式等价。

A:错误
B:正确
参考选项：B
R是A上的二元关系，R是自反的，当且仅当r(R)=R。

A:错误
B:正确
参考选项：B
若函数f，g为入射则其复合函数也为入射。

A:错误
B:正确
参考选项：B
A:错误
B:正确
参考选项：A
集合A上的等价关系确定了A的一个划分。

A:错误
B:正确
参考选项：B
在任何图中，度数为偶数的结点必定是偶数个。

A:错误。