离散数学部分概念和公式总结(考试专用)

╰半夏微凉° 2024-03-24 14:08 80阅读 0赞

**命题**：称能判断真假的陈述句为命题。

**命题公式**：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。

**命题的赋值**：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个**赋值**或**解释**。若指定的一组值使A的值为真，则称**成真赋值**。

**真值表**：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。

**命题公式的类型**：（1）若A在它的各种赋值下均取值为真，则称A为重**言式**或**永真式**。

（2）若A在它的赋值下取值均为假，则称A为矛盾式或**永假式**。

（3）若A至少存在一组赋值是成真赋值，则A是**可满足式**。

**主析取范式**：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。

**主合取范式**：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。

**命题的等值式**：设A、B为两命题公式，若等价式A↔B是重言式，则称A与B是**等值的**，记作A<=>B。

**约束变元和自由变元**：在合式公式"*x* A和 $*x* A中，称x为**指导变项**，称A为相应量词的**辖域**，x称为**约束变元**，x的出现称为**约束出现**，A中其他出现称为**自由出现**（**自由变元**）。

**一阶逻辑等值式**：设A，B是一阶逻辑中任意的两公式，若A↔B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。

**前束范式**：设A为一谓词公式，若A具有如下形式Q*1*x*1*Q*2*x*2*Q*k…*x*k*B，称A为前束范式。

**集合的基本运算**：并、 交、差、相对补和对称差运算。

**笛卡尔积**：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。

**二元关系**：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。

**特殊关系**：（1）**、空关系**：*Φ* （2）**全域关系**：EA=\{<x, y> | x∈A ∧ y∈A \}= A×A

（3）**恒等关系**：IA=\{<x, x> | x∈A\}

（4）**小于等于关系**：LA=\{<x, y>| x, y∈A∧x≤y∈A \},A Í R

（5）**整除关系**： RÍ =\{<x, y>| x，y∈ψ ∧ x Í y\} ,ψ是集合族

**二元关系的运算**：**设*****R*****是二元关系**，

（1）*R*中所有有序对的第一元素构成的集合称为*R*的**定义域dom*****R*** = \{ x |$y（<*x , y>*∈*R*）\}

（2）*R*中所有有序对的第二元素构成的集合称为*R*的**值域ranR** = \{ *y* |$*x*（<*x* , *y>*∈*R*）\}

（3）*R*的定义域和值域的并集称为*R*的**域fld*****R***= dom*R* ∪ran*R*

**二元关系的性质**：自反性，反自反性，对称性，反对称性，传递性。

**等价关系**：如果集合*A*上的二元关系*R*是自反的，对称的和传递的，那么称*R*是**等价关**系。设*R*是*A*上的等价关系，*x , y*是*A*的任意元素，记作*x*～*y*。

**等价类**：设*R*是*A*上的等价关系，对任意的"*x*∈*A*，令\[*x*\]R=\{ *y* | *y*∈*A* ∧ *x R y* \}，称\[*x*\]R为***x*****关于*****R*****的等价类**。

**偏序关系**：设*R*是集合*A*上的二元关系，如果*R*是自反的，反对称的和传递的，那么称*R*为*A*上的**偏序**，记作≤；称序偶< *A ,R* >为**偏序集合**。

**函数的性质**：**设*****f*****:** ***A*****®*****B*****，**

（1）若ran*f* = B，则称*f* 是**满射**（**到上**）的。

（2）若 "*y*Î ran*f* 都存在唯一的*x* Î*A* 使得f(*x*)=*y*,则称*f* 是**单射**（— —）的。

（3）若*f* 既是满射又是单射的，则称*f* 是**双射**（**— —到上**）的。

**无向图**：是一个有序的二元组<*V*, *E*>，记作*G*，其中：

(1) *V*¹*Ф*称为顶点集，其元素称为**顶点**或**结点**。

(2) *E*为边集，它是无序积*V*&*V*的多重子集，其元素称为**无向边**，简称**边**。

**有向图：**是一个有序的二元组<*V*,*E*>,记作*D*,其中

(1) *V*同无向图。 (2) *E*为边集，它是笛卡尔积*V*´*V*的多重子集，其元素称为**有向边**。

**设G=<V,E>是一个无向图或有向图。**

**有限图**：若*V*, *E*是有限集，则称*G*为有限图。

**n阶图**：若| *V* |=*n*，称G为n阶图。

**零图**：若| *E* |=0，称*G*为零图,当| *V* |=1时，称G为平凡图。

**基图**：将有向图变为无向图得到的新图，称为有向图的基图。

**图的同构：**在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。

**带权图**：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。

**连通图**：若无向图是平凡图，或图中任意两个顶点都是连通的，则称*G*是**连通图**。否则称为**非连通图**。设*D*是一个有向图，如果*D*的基图是连通图，则称*D*是**弱连通图**，若*D*中任意两个顶点至少一个可达另一个，则称*D*是**单向连通图**。若*D*中任意两个顶点是相互可达的，则称*D*是**强连通图**。

**欧拉图**：通过图中所有边一次且仅一次并且通过所有定点的通路（回路），称为**欧拉通路**（**回路**）。存在欧拉回路的图称为欧拉图。

**哈密顿图**：经过图中每个顶点一次且仅一次的通路（回路），称为哈密顿通路（回路），存在哈密顿回路的图称为哈密顿图。

**平面图**：一个图G如果能以这样的方式画在平面上：出定点处外没有变交叉出现，则称G为平面图。画出的没有边交叉出现的图称为G的一个**平面嵌入**。

**二部图**：若无向图*G*=〈*V*, *E*〉的顶点集合*V*可以划分成两个子集*V*1和*V* 2（*V*1∩*V*2 =*f* ），使*G*中的任何一条边的两个端点分别属于*V*1和*V*2，则称*G*为二部图（**偶图**）。二部图可记为*G* = < *V*1, *V* 2 , *E* >, *V*1和*V* 2称为互补顶点子集。

**树的定义**：连通无回路的无向图称为无向树，简称**树**，常用T表示树。平凡图称为**平凡树**。若无向图G至少有两个连通分支，每个连通都是树，则称G为**森林**。在无向图中，悬挂顶点称为**树叶**，度数大于或等于2的顶点称为**分支点**。

**树的性质**：**性质1、**设G=<V,E>是n阶m条边的无向图，则下面各命题是等价的：

**（1）**G是树 **（2）**G中任意两个顶点之间存在唯一的路径 **（3）**G中无回路且m=n-1.

**（4）**G是连通的且m=n-1. **（5）**G是连通的且G中任何边均为桥。 **（6）**G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。

**性质2、**设T是n阶非平凡的无向树，则T中至少有两片树叶。

证：设T有x片树叶，由握手定理及性质1可知，2(n-1)=∑d(vi)≥x+2(n-x)由上式解出x≥2.

**最小生成树**：设*T*是无向图*G*的子图并且为树，则称*T*为*G*的树。若*T*是*G*的树且为生成子图，则称*T*是G的生成树。设*T*是*G*的生成树。e∈*E*(*G*)，若e∈*E*(T)，则称e为T的树枝，否则称e为*T*的弦。并称导出子图*G*\[*E*(*G*)-*E*(*T*)\]为T的余树，记作*T*。

**最优二元树**：设2叉树T有t片树叶v1,v2,…,vt，权分别为w1,w2,…,wt，称W(t)=wil(vi)为T的权，其中l(vi)是vi的层数。在所有有t片树叶，带权w1,w2,…,wt的2叉树中，权最小的2叉树称为**最优2叉树**。

**最佳前缀码**：利用Huffman算法求最优2叉树，由最优2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。

**蕴含式推理**

**等值公式表**

<table> 
 <tbody> 
 <tr> 
 <td colspan="2"> P∧Q=&gt;P </td> 
 <td colspan="3"> 化简式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> P∧Q=&gt;Q </td> 
 <td colspan="3"> 化简式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> P=&gt;P∨Q </td> 
 <td colspan="3"> 附加式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> ┐P=&gt;P→Q </td> 
 <td colspan="3"> 变形附加式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> Q=&gt;P→Q </td> 
 <td colspan="3"> 变形附加式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> ┐(P→Q)=&gt;P </td> 
 <td colspan="3"> 变形简化式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> ┐(P→Q)=&gt;┐Q </td> 
 <td colspan="3"> 变形简化式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> p∧(P→Q)=&gt;Q </td> 
 <td colspan="3"> 假言推论 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> ┐Q∧(P→Q)=&gt;┐P </td> 
 <td colspan="3"> 拒取式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> ┐p∧(P∨Q)=&gt;Q </td> 
 <td colspan="3"> 析取三段式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> (P→Q) ∧(Q→R)=&gt;P→R </td> 
 <td colspan="3"> 条件三段式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> (PDQ) ∧(QDR)=&gt;PDR </td> 
 <td colspan="3"> 双条件三段式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> (P→Q)∧(R→S)∧(P∧R)=&gt;Q→S </td> 
 <td colspan="3"> 合取构造二难 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> (P→Q)∧(R→S)∧(P∨R)=&gt;Q∨S </td> 
 <td colspan="3"> 析取构造二难 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> P→Q=&gt;(P∨R) →(Q∨R) </td> 
 <td colspan="3"> 前后附加式 </td> 
 </tr> 
 <tr> 
 <td colspan="2"> P→Q=&gt;(P∧R) →(Q∧R) </td> 
 <td colspan="3"> 前后附加式 </td> 
 </tr> 
 <tr> 
 <td> E23 </td> 
 <td colspan="2"> ( x)((Ax)∨(Bx))&lt;=&gt;( x)(Ax)∨( x)(Bx) </td> 
 <td> E30 </td> 
 <td> ( x)(Ax) →B&lt;=&gt;( x) ((Ax)→B) </td> 
 </tr> 
 <tr> 
 <td> E24 </td> 
 <td colspan="2"> ( x)((Ax)∧(Bx))&lt;=&gt;( x)(Ax)∧( x)(Bx) </td> 
 <td> E31 </td> 
 <td> ( x)(Ax) →B&lt;=&gt;( x) ((Ax)→B) </td> 
 </tr> 
 <tr> 
 <td> E25 </td> 
 <td colspan="2"> ┐( x)(Ax)&lt;=&gt;( x)┐(Ax) </td> 
 <td> E32 </td> 
 <td> A→( x)(Bx) &lt;=&gt;( x) (A→(Bx)) </td> 
 </tr> 
 <tr> 
 <td> E26 </td> 
 <td colspan="2"> ┐( x)(Ax)&lt;=&gt;( x)┐(Ax) </td> 
 <td> E33 </td> 
 <td> A→( x)(Bx) &lt;=&gt;( x) (A→(Bx)) </td> 
 </tr> 
 <tr> 
 <td> E27 </td> 
 <td colspan="2"> ( x)(A∨(Bx))&lt;=&gt;A∨( x)(Bx) </td> 
 <td> I17 </td> 
 <td> ( x)(Ax)∨( x)(Bx) =&gt;( x)((Ax)∨(Bx)) </td> 
 </tr> 
 <tr> 
 <td> E28 </td> 
 <td colspan="2"> ( x)(A∧(Bx))&lt;=&gt;A∧( x)(Bx) </td> 
 <td> I18 </td> 
 <td> ( x)((Ax)∧(Bx)) =&gt;( x)(Ax)∧( x)(Bx) </td> 
 </tr> 
 <tr> 
 <td> E29 </td> 
 <td colspan="2"> ( x)((Ax)→(Bx))&lt;=&gt;( x)(Ax)→( x)(Bx) </td> 
 <td> I19 </td> 
 <td> ( x)(Ax)→( x)(Bx) =&gt;( x)((Ax)→(Bx)) </td> 
 </tr> 
 </tbody> 
</table>

**集合恒等式**：P61

幂等律：A∪A=A ；A∩A=A

结合律：(A∪B)∪C=A∪(B∪C) ；(A∩B)∩C=A∩(B∩C)

交换律：A∪B=B∪A ；A∩B=B∩A

分配律：A∪(B∩C)=(A∪B)∩(A∪C) ；A∩(B∪C)=(A∩B)∪(A∩C)

同一律：A∪*f* =A ；A∩E=A

零 律：A∪E =A ；A∩*f* = *f*

排中律：A∪~A=E

矛盾律：A∩~A =*f*f

吸收律：A∩(A∪B)=A；A∪ (A∩B)=A

德摩根定律：A-(B∪C)=(A-B)∩(A-C)；A-(B∩C)=(A-B)∪(A-C)

~(B∪C)= ~B∩~C；~(B∩C)= ~B∪~C；~*f*=E；~E=*f*