《离散数学》遗忘要点

╰+攻爆jí腚メ 2021-12-11 22:37 1086阅读 0赞

**第1章 命题逻辑**

**1.1命题符号化及联结词**

1.能判断真假的陈述句（"！"、"？"祈使句等都不是）为**命题。**

**判断条件一：是不是陈述句；条件二：真值是否唯一。**

a）“x+y>5”不是命题。既可以为真，也可以为假，没有真值

b）“存在地球外的星球上也有生命”是命题。他的真值是唯一的，知识人们还不知道而已，但其真值终将知道

2.不能分解成更简单的句子的命题为**简单命题**或**原子命题，**用小写的英文字母p,q,r...表示。

a）简单命题的真值的确定的，因而又称为**命题常项**或**命题常元。**

b）x+y>5不是命题，但当给定x与y的值后，它的真值也就确定下来了，这种真值可以变化的简单陈述句称为**命题变项**或**命题变元。命题变项不是命题。**

3.简单命题由**联结词(也称真值联结词，逻辑联结词)**联结而成的命题，称为**复合命题**。

a）5种常用联结词的符号表示**¬、Λ、V、→、↔ **

b）Λ在自然语言中表达为：“既...又...”，“不仅...而且...”，“虽然...但是...”，“不是...而是...”。V在自然语言中的表达为“或”。

c）设p：“派小王去开会"，q： “派小李去开会”，那么“派小王或小李去开会”为(pΛ¬q)V(¬pΛq)，或(pVq)Λ¬(pΛq)

d）→在自然语言中的表达为：“只要...就...”/“除非...否则...”**（充分条件）**，“p仅当q”，“只有...才”/“如果...就...”**（必要条件）**

e）**↔** 在自然语言中的表达为：“当且仅当”

4.命题符号化

a）“小王现在在宿舍或在图书馆里”，在宿舍和在图书馆里不可能同时发生，故pVq

b）“选小王或小李中的一人当班长”，选小王和选小李可能同时发生，故(pΛ¬q)V(¬pΛq)

5.优先级顺序：**¬、Λ、V、→、↔ **

**1.2命题公式及分类**

1.**命题公式**是由命题常项、命题变项、联结词、括号等组成的符号串。简称公式

a）1可以看成某个恒取1的公式(pV¬p)的缩写，0可以看成某个恒取0(pΛ¬p)的公式的缩写

b）A称为0层公式，若A=右式(**¬、Λ、V、→、↔ **)，A比右式B、C中的最大层高一层

2.永真式（重言式）、永假式（矛盾式）、可满足式

3.n个命题变项，共有2n个可能的赋值，可以形成22^n个不同的真值函数

**1.3等值演算**

1.判断A与B是否等值等价于判断A、B的真值表是否相同

2.重要的等值式：

![1671281-20190630111409266-516130076.jpg][]

3.通过等值演算判断公式类型

**1.4范式**

1.仅由有限个**命题变项或其否定**构成的析取式称为简单析取式；

仅由有限个**简单合取式**构成的析取式称为析取范式；

2.通过等值演算求析取范式的步骤：

![1671281-20190630113728838-1939656146.jpg][]

3.在简单合取式中每个命题变项与其否定有且仅有一个出现一次，这样的简单合取式称为**极小项**。

<table style="width:531px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:left;">主析取范式</td> 
   <td>极小项(简单合取式)</td> 
   <td>二进制数(成真赋值)</td> 
   <td>记作</td> 
   <td>编码形式</td> 
  </tr> 
  <tr> 
   <td>(¬pΛ¬qΛ¬r)V(¬pΛ¬qΛ¬r)V(¬pΛ¬qΛ¬r)</td> 
   <td>¬pΛ¬qΛ¬r</td> 
   <td>000</td> 
   <td>m0</td> 
   <td>Σ(0,1,2)</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>¬pΛ¬qΛr</td> 
   <td>001</td> 
   <td>m1</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>¬pΛqΛ¬r</td> 
   <td>010</td> 
   <td>m2</td> 
   <td>&nbsp;</td> 
  </tr> 
  <tr> 
   <td>主合取范式</td> 
   <td>极大项(简单析取式)</td> 
   <td>二进制数(成假赋值)</td> 
   <td>记作</td> 
   <td>编码形式</td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>&nbsp;</td> 
   <td>M</td> 
   <td>Π(3,4,5,6,7)</td> 
  </tr> 
 </tbody> 
</table>

p<=>(pΛ¬q)V(pΛq)

**1.5联结词全功能集**

1.p↑q<=>¬(pΛq)，p与q的否定，↑称作与非联结词

p↓q<=>¬(pVq)，p或q的否定，↓称作或非联结词

**1.6组合电路**

**1.7推理理论**

**![1671281-20190630122504482-1045655604.jpg][]**

1.等值演算法，真值表法，构造证明法

a）附加前提证明法

**第2章 一阶逻辑**

**2.1一阶逻辑基本概念**

1.个体变项x,y具有关系L，记作L(x,y)

2.通常来讲，谓词P（x1,x2,...,xn）不是命题，必须制定某一谓词常项代替P，同时用n个个体常项代替n个个体变项。

0元谓词常项都是命题

3.一阶逻辑转换为命题逻辑

**2.2一阶逻辑合式公式及解释**

1.**合式公式，**简称**公式**¬、Λ、V、→、↔ 和全称量词、特称量词的组合

2.换名规则：将一个**指导变项**及其**在辖域中所有约束出现**替换成公式中没有出现的个体变项符号

3.解释：给定个体域D、给个体常项一个D中的元素、给函数变项一个D上的函数、给谓词变项一个D上的谓词

4.逻辑有效式（永真式）、矛盾式（永假式）、可满足式

5.代换实例

6.若公式A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式

**2.3一阶逻辑等值式和前束范式**

1.量词否定的等值式

2.量词辖域收缩与扩张等值式

当A与闭式形成析取、合取关系时，量词辖域可以收缩或者扩张，当形成蕴含关系时，A(X)→B要改量词

3.量词分配等值式

任意对合取，存在对析取，存在分配等值式

4.证明等值式

a）消去量词，化成命题逻辑

b）等值演算

c）解释

5.求前束范式可能用到的定理

换名规则、辖域的收缩或扩张、否定后移改量词、分配等值式

**第3章 集合论**

**3.1集合的基本概念**

1.幂集：A的全体子集构成的集合

**3.2集合的基本运算**

1.交集、并集、相对补集、绝对补集~A（对全集的相对补集）、对称差

2.集合相等的证明

a）取任意x

b）等值演算A-B=A∩~B

**3.3集合中元素的计数**

1.基数：集合中所含元素的多少。card A、|A|

2.包含排斥原理

**第4章 二元关系**

**4.1集合的笛卡儿积与二元关系**

**4.2关系的运算**

**4.3关系的性质**

**4.4关系的闭包**

**4.5等价关系和偏序关系**

**4.6函数的定义和性质**

**4.7函数的复合和反函数**

**第5章 图的基本概念**

**5.1无向图及有向图**

1.无向图、有向图

2.n阶图：有n个顶点的图

零图：没有一条边的图

一阶零图：即只有一个顶点、没有边的图，称为平凡图

3.点与边之间的关系：关联。关联次数：1，2（环），0（不关联）

4.点与点之间的关系：相邻的（无向图），邻接到（有向图）

5.边与边之间的关系：相邻

6.在无向图中，顶点v作为**边的端点**的次数之和为v的度数，简称度。入度、出度（有向图）

称度数为1的顶点为悬挂顶点，它所关联的边为悬挂边

7.握手定理

推论：任何图中，度数为奇数的顶点个数是偶数

8.度数序列

9.重数：平行边的条数

10.简单图：既不含平行边也不含环

11.n阶无向完全图Kn：G为简单图，其中任何顶点都与其余n-1个顶点相邻。

**5.2通路、回路和图的连通性**

**5.3图的矩阵表示**

**5.4最短路径、关键路径和着色**

**第6章 特殊的图**

**6.1二部图**

**6.2欧拉图**

**6.3哈密顿图**

**6.4平面图**

**第7章 树**

**7.1无向树及生成树**

**7.2根树及其应用**

**第9章 代数系统简介**

**9.1二元运算及其性质**

**9.2代数系统**

**9.3几个典型的代数系统**　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　·　　　　　　　　　　·

转载于:https://www.cnblogs.com/wxt1997/p/11109563.html

[1671281-20190630111409266-516130076.jpg]: /images/20211211/d6d0d39b2c324b52b28b7420a8f4175e.png
[1671281-20190630113728838-1939656146.jpg]: /images/20211211/16fd6632205b4f0ea7da0a76c15f4e3e.png
[1671281-20190630122504482-1045655604.jpg]: /images/20211211/6e488911633648cd9b46b5ef4460d021.png