离散数学(1.7对偶与范式)

对偶公式离散数学对偶公式是离散数学中的一种重要概念，它与图形的对称性有关，可以帮助我们更好地理解图形的结构特征和性质。

在本文中，我将讨论对偶公式的定义、证明、应用等方面，以帮助读者更好地理解这一概念。

对偶公式的定义对偶公式是指将一个平面图形的所有面和所有点互换得到的另一个平面图形，两个图形互为对偶关系。

具体来说，对于一个给定的平面图形G=(V，E)，我们可以定义它的对偶图G某=(V某，E某)，使得G和G某满足以下两个条件：1.G和G某的所有面和所有点一一对应。

2.对于G中的任意两个面，它们相邻当且仅当它们对应的点在G某中相邻；对于G某中的任意两个面，它们相邻当且仅当它们对应的点在G中相邻。

对偶公式的证明对于平面图形G=(V，E)，我们可以通过以下步骤来证明它的对偶图G 某=(V某，E某)存在：1.根据欧拉公式，我们有：，V，-，E，+，F，=2，其中，V，E，F，分别表示G中的点数、边数和面数。

2.我们将G中的每一个面向外“翻面”，得到一个新图形G'，它的每个面都是由原来的面与周围的边所围成的一块区域。

3.我们将G'中的每个交点都插入一个新的点，得到一个新图形H。

4.我们将H中每个面都向外“翻面”，得到一个新图形H'，它的每个面都是由原来的面与周围的点所围成的一块区域。

5.我们可以发现，H'中的每个面都对应着G中的一个点，且H'中的每个点都对应着G中的一个面。

因此，我们可以定义G某=(V某，E某)，其中V某为H'中的点集，E某为H'中的边集，且G某为G的对偶图。

通过上述证明，我们可以看出，对偶公式的存在并不依赖于G是否为平面图形，而只与G中的面、点、边之间的关系有关。

对偶公式的应用对偶公式在离散数学中有着广泛的应用，包括图论、拓扑学、计算几何等领域。

以下是一些典型的应用场景：1. 图论中常常使用对偶公式来证明定理或推导算法。

例如，通过对偶公式可以证明Planar Graph的最大独立集大小小于等于4/3 某最小顶点覆盖大小。

对偶式离散数学
对偶式离散数学是一种研究离散结构的数学分支，它主要关注离散结构中的对偶性和对称性。

对偶性是指将一个数学结构中的某些概念和操作进行转换，得到另一个相对应的数学结构，两个结构之间存在一种相似性或者映射关系。

对偶性的概念在离散数学中具有广泛的应用，可以用来研究图论、集合论、代数结构等多个领域。

对偶式离散数学的一个重要方面是对偶图（dual graph）。

在图论中，对偶图是指将原始图中的节点和边进行转换，得到一个新的图。

对偶图与原始图具有一一对应的关系，并且它们在某些性质上是相同的。

通过对偶图的研究，可以更好地理解原始图的特征和结构。

另一个重要的概念是对偶算子（dual operator）。

对偶算子是指将一个向量空间中的线性算子转化为另一个向量空间中的线性算子。

对偶算子可以用来描述向量空间中的对称性和共轭性质。

在代数结构中，对偶算子的概念也得到广泛的应用，特别是在线性代数和泛函分析中。

对偶式离散数学还包括对偶关系的研究。

对偶关系是指两个数学结构之间的一种对应关系，通过这种对应关系可以建立两个结构之间的联系。

对偶关系可以用来研究不同领域中的相似性和等价性，进而推导出一些结构和性质之间的等价关系。

总之，对偶式离散数学是一门研究离散结构中对偶性和对称性的数学学科。

它通过对偶图、对偶算子和对偶关系的研究，揭示了离散结构中的一些隐藏规律和性质，为离散数学的发展提供了新的视角和方法。

对偶公式离散数学对偶公式是离散数学中的一个重要概念，它在逻辑推理、集合论、图论以及计算机科学等领域都有广泛的应用。

本文将详细介绍对偶公式的概念、性质和应用。

一、对偶公式的概念对偶公式是基于集合论中关于集合运算的补运算的一个重要概念。

在集合论中，对于一个给定的全集U，定义任意一个子集A的补集为全集U 中不属于A的元素所构成的集合，记作A'。

根据这个定义，对于两个子集A和B，它们的交集的补集和并集的补集都具有一定的关系，这种关系可以用对偶公式来表达。

二、对偶公式的性质1.补运算的自反性：对于任意一个子集A，有(A')'=A。

这个性质表明，一个子集的补集的补集还是它本身。

2.补运算的交换率：对于任意两个子集A和B，有(A∩B)'=A'∪B'。

这个性质表明，两个子集的交集的补集等于它们的补集的并集。

3.补运算的结合率：对于任意三个子集A、B和C，有(A∪B)∩C=A∩C∪B∩C。

这个性质表明，三个子集的并集的补集等于它们的补集的交集。

三、对偶公式的应用1.逻辑推理：对偶公式常常在逻辑推理中用于判定两个逻辑命题的等效性。

根据对偶公式，可以将一些命题的补命题转化为原命题的补命题，从而在推理过程中利用已知条件推导出新的结论。

2.集合论：对偶公式在集合论的证明中也有重要应用。

例如，在证明集合之间的关系时，可以通过对偶公式将一个集合之间的包含关系转化为另一个集合之间的补包含关系，从而简化证明过程。

3.图论：对偶公式在图论中也有广泛的应用。

例如，在图的割边和割点的计算中，对偶公式可以帮助我们快速得到割边和割点的补集。

4.计算机科学：对偶公式在计算机科学中也有很多应用。

例如，在编译原理中，对偶公式可以用于将一个复杂的语法规则转化为一个简化的等价规则，从而简化编译器的设计和实现过程。

总之，对偶公式是离散数学中一个基础而重要的概念。

它在逻辑推理、集合论、图论以及计算机科学等领域都有广泛的应用。

1.5 对偶与范式任一命题公式都存在着与之逻辑等价的主析取和主合取范式，并且是唯一的。

1.5.1对偶定义1.15在给定的仅使用联结词﹁, ∧, ∨的命题公式A中，若把∧和∨互换，0和1互换而得到一个命题公式A*，则称A*是A的对偶式。

显然，A也是A*的对偶式。

可见，A*和A互为对偶式且(A*)*=A。

定理1.3设A*和A互为对偶式，P1, P2, …, P n是出现在A和A*中的命题变元，则1）﹁A (P1, P2, …, P n) ⇔A*(﹁P1,﹁P2, …, ﹁P n)2）A(﹁P1,﹁P2, …, ﹁P n) ⇔﹁A* (P1, P2, …, P n)定理1.4设A和B是两个命题公式，若A⇔B，则A*⇔B*。

说明：1）对于含有﹁,∧,∨之外联结词的公式，必须利用逻辑等价演算将其他联结词消去后，才能求其对偶式。

2）一般情况下，公式与其对偶式不是逻辑等价的。

1.5.2 范式定义11.6命题变元和命题变元的否定称为文字。

仅由有限个文字构成的析取式称作简单析取式。

仅由有限个文字构成的合定义11.7取式称作简单合取式。

一个文字既是简单析取式，又是简单合取式。

例1.37判断以下公式是否为简单析（合）取式。

1) ﹁P2) ﹁﹁P3) P ∧ ﹁Q4) ﹁(P ∧ ﹁Q)解：1) 是简单析取式，也是简单合取式；2) 不是；3) 是简单合取式；4) 不是。

1.5.2 范式定理1.51）由有限个简单合取式构成的析取式称为析取范式。

2）由有限个简单析取式构成的合取式称为合取范式。

3）析取范式与合取范式统称为范式。

定义11.8无论是简单析取式或是简单合取式，都既是析取范式又是合取范式。

1）一个简单析取式是重言式当且仅当它同时含某个命题变元及它的否定式。

2）一个简单合取式是矛盾式当且仅当它同时含某个命题变元及它的否定式。

1.5.2 范式定理1.61）一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。

2）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式。

教学设计课程名称《离散数学》教师姓名授课题目小项、大项授课章节§1.7对偶与范式授课对象数学与应用数学专业教学目标掌握小项（大项）的写法及性质教学方式启发式教学内容小项（大项）的概念及性质，会使用真值表法求命题公式的小项（大项）教学重点小项（大项）的写法及性质、求解教学难点小项的性质教学方法和策略采用多媒体课件辅助，分析小项的概念和真值情况、性质，分析利用真值表写出小项（大项）的方法；注意师生互动，以学生为教学主体，共同完成教学目标。

学情分析学生已经掌握了析取范式、合取范式的求解，思考如何寻找范式的“标准”形式。

教学评价师生互动，启发式教学引导学生思考并进而解决问题；深入分析，用例题加深学生对知识点的理解。

课程资源参考书目，网上教学视频，网络微课。

JINING UNIVERSITY教学过程：一、小项1、定义1-7.4 ｎ个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。

例如，两个命题变元P,Q的小项为：P∧Q,P∧¬Q,¬P∧Q, ¬P∧¬Q;注：1)有n个变元，则有2n个小项。

2)每一组指派有且只有一个小项为T。

没有两个小项是等价的。

2、小项的编码m00=m0=⌝P∧⌝Q，m01=m1= ⌝P∧Q，m10=m2= P∧⌝Q，m11=m3=P∧Q 为了记忆方便，可将各组指派对应的为T的小项分别记作m0, m1, m2,…, m2n-1三个命题变元P,Q,R的小项为：P∧Q∧R，P∧Q∧¬R,P∧¬Q∧R, P∧¬Q∧¬R, ¬P∧Q∧R, ¬P∧Q∧¬R, ¬P∧¬Q∧R,¬P∧¬Q∧¬R.m000= m0= ⌝P∧⌝Q∧⌝R , m001= m1= ⌝P∧⌝Q ∧Rm010= m2= ⌝P∧Q ∧⌝R, m011`= m3= ⌝P∧Q ∧Rm100= m4= P∧⌝Q ∧⌝R , m101= m5= P∧⌝Q ∧Rm110= m6= P∧Q ∧⌝R , m111= m7= P∧Q ∧R3、小项的性质性质1 ：每个小项当其真值指派与编码相同的时，其真值为T，在其余2n -1种指派情况下均为F。

第一章命题逻辑1.1 命题及其表示方法1.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。