离散数学(对偶和范式)

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

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

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

具体来说，对于一个给定的平面图形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 某最小顶点覆盖大小。

离散数学对偶式离散数学对偶式：1. 什么是离散数学对偶式离散数学对偶式（简称DMS）是一种简单的数学表达方式，它用于表示由不同对象和对应关系建立而成的模型。

它包含一系列有限变量，以及这些变量之间存在的条件，所以它也可以被用来描述许多具体的数学概念，并被用于求解复杂的问题。

DMS在数学学的一般习语中通常称为“对偶”形式。

2. 离散数学对偶式的历史DMS出现于20世纪60年代，最初由英国数学家Bertrand Russell和Alfred North Whitehead发明，他们用离散数学对象进行离散数学运算，从而把无限数量的离散数学表达式转换成有限数量的表达式。

此外，一些科学家和数学家宣称，这种方法比以前的方法更有效率。

随着DMS被人们接受，它被用于许多不同的领域，例如计算机科学和统计学，以及流体力学和运筹学的研究领域。

3. 离散数学对偶式的优势DMS有许多优势，比如它能够避免无限数量的表达式，而像数学学家Bertrand Russell等人所做的只能处理有限数量的表达式。

此外，它也能够抽象地表达复杂的问题，因此可以更有效地解决实际问题。

此外，它还可以被用于求解许多有趣的数学和逻辑问题，它还可以被用来计算机程序，用来完成复杂的计算。

4. 离散数学对偶式的应用DMS可以用于许多领域。

它可以用于计算机科学，运筹学，统计学，流体力学，数学建模以及许多其他领域。

DMS也可以用于解决许多复杂的问题，包括逻辑问题，数学问题，科学问题和工程研究问题等。

此外，由于它的简单性，可以被用于计算机程序，用来完成复杂的计算。

5. 结论DMS是一种由变量和条件组成的简单数学表示方式，它可以用于求解复杂问题，以及用于计算机程序的复杂计算。

其优势在于可以避免无限数量的表达式，并且能把复杂的问题抽象表达出来，使问题变得更加容易被解决。

它也可以被广泛应用于不同的领域，包括计算机科学，数量分析，统计学，流体力学，运筹学等。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基本等值式1.双重否定律 A ⇔┐┐A2.幂等律 A ⇔ A∨A, A ⇔ A∧A3.交换律A∨B ⇔ B∨A，A∧B ⇔ B∧A4.结合律(A∨B)∨C ⇔ A∨(B∨C) (A∧B)∧C ⇔ A∧(B∧C)5.分配律A∨(B∧C) ⇔ (A∨B)∧(A∨C) （∨对∧的分配律）A∧(B∨C) ⇔ (A∧B)∨(A∧C) （∧对∨的分配律）6.德·摩根律┐(A∨B) ⇔┐A∧┐B ┐(A∧B) ⇔┐A∨┐B7.吸收律 A∨(A∧B) ⇔ A，A∧(A∨B) ⇔ A8.零律A∨1 ⇔ 1,A∧0 ⇔ 09.同一律A∨0 ⇔ A，A∧1 ⇔ A10.排中律A∨┐A ⇔ 111.矛盾律A∧┐A ⇔ 012.蕴涵等值式A→B ⇔┐A∨B13.等价等值式A↔B ⇔ (A→B)∧(B→A)14.假言易位A→B ⇔┐B→┐A15.等价否定等值式 A↔B ⇔┐A↔┐B16.归谬论(A→B)∧(A→┐B) ⇔┐A求给定公式范式的步骤(1)消去联结词→、↔(若存在)。

(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。

(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。

推理定律--重言蕴含式(1) A ⇒ (A∨B) 附加律(2) (A∧B) ⇒ A 化简律(3) (A→B)∧A ⇒ B 假言推理(4) (A→B)∧┐B ⇒┐A 拒取式(5) (A∨B)∧┐B ⇒ A 析取三段论(6) (A→B) ∧(B→C) ⇒ (A→C) 假言三段论(7) (A↔B) ∧(B↔C) ⇒ (A ↔ C) 等价三段论(8) (A→B)∧(C→D)∧(A∨C) ⇒(B∨D) 构造性二难(A→B)∧(┐A→B)∧(A∨┐A) ⇒ B 构造性二难(特殊形式)(9)(A→B)∧(C→D)∧(┐B∨┐D) ⇒(┐A∨┐C)破坏性二难设个体域为有限集D={a1,a2,…,an},则有 （1）∀xA(x) ⇔ A(a1)∧A(a2)∧…∧A(an) （2）∃xA(x) ⇔ A(a1)∨A(a2)∨…∨A(an)设A(x)是任意的含自由出现个体变项x 的公式，则 （1）┐∀xA(x) ⇔ ∃x ┐A(x) （2）┐∃xA(x) ⇔ ∀x ┐A(x)设A(x)是任意的含自由出现个体变项x 的公式，B 中不含x 的出现，则 （1） ∀x(A(x)∨B) ⇔ ∀xA(x)∨B ∀x(A(x)∧B) ⇔ ∀xA(x)∧B ∀x(A(x)→B) ⇔ ∃xA(x)→B ∀x(B →A(x)) ⇔ B →∀xA(x) （2） ∃x(A(x)∨B) ⇔ ∃xA(x)∨B∃x(A(x)∧B) ⇔ ∃xA(x)∧B ∃x(A(x)→B) ⇔ ∀xA(x)→B∃x(B →A(x)) ⇔ B →∃xA(x)设A(x)，B(x)是任意的含自由出现个体变项x 的公式，则 （1）∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x) （2）∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨ ∃xB(x)全称量词“∀”对“∨”无分配律。

第一章命题逻辑一、等价公式(真值表)1)常用联结词：┐否定∨析取∧合取→：条件∆：双条件当且仅当Q 取值为F 时P →Q 为F ，否则为T ★等价公式表(等值公式表)常用的其它真值表┐┐P<=>P 双重否定P ∨P<=>P P ∧P<=>P幂等律(P ∧Q)∧R<=>P ∧(Q ∧R)(P ∨Q)∨R<=>P ∨(Q ∨R)结合律P ∧Q<=>Q ∧P P ∨Q<=>Q ∨P交换律P ∧(Q ∨R)<=>(P ∧Q)∨(P ∧R)P ∨(Q ∧R)<=>(P ∨Q)∧(P ∨R)分配律P ∨(P ∧Q)<=>P P ∧(P ∨Q)<=>P 吸收┐(P ∧Q)<=>┐P ∨┐Q ┐(P ∨Q)<=>┐P ∧┐Q 德摩根P ∨F<=>P P ∧T<=>P 同一律P ∨T<=>T P ∧F<=>F 零律P ∨┐P<=>T P ∧┐P<=>F否定律常用的其它真值表P ┐P T F FTP Q P ∨Q T T T T F T F T T FFFP Q P ∧Q T T T T F F F T F F FFP Q P →Q (┐P ∨Q)T T T T F F F T T FFTP→Q<=>┐P ∨Q P ∆Q<=>(P→Q)∧(Q→P)P ∆Q<=>Q ∆PP ∆Q<=>(P ∧Q)∨(┐P ∧┐Q)┐(P ∆Q)<=>P ∆┐Q R ∨(P ∨┐P)<=>T R ∧(P ∧┐P)<=>F P→Q<=>┐Q→┐P ┐(P→Q)<=>P ∧┐Q (P→Q)∧(P→┐Q)<=>┐P P→(Q→R)<=>(P ∧Q)→R (P ∆Q)∆R<=>P ∆(Q ∆R)命题公式的类型：(1)若A在它的各种赋值下均取值为真，则称A为重言式或永真式。

《离散数学》课程教学大纲课程编号：课程中文名称：离散数学课程英文名称：Discrete mathematics课程类型：考查课课程性质：专业技术基础课总学时： 54学时理论授课学时： 46学时实验（实践）学时：8学时学分：3分适用对象：信息管理与信息系统、信息工程本科先修课程：高等数学线性代数一、编写说明（一）制定大纲的依据依据我系信息管理与信息系统、信息工程专业学科体系和特色化人才培养目标的要求，制定编写了该教学大纲，在内容上突出了《离散数学》课程的基本理论、基本知识和基本技能，反映现代科学技术的发展趋势，体现了我系的特色化人才培养模式。

（二）课程简介离散数学，是现代数学的一个重要分支，是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素。

《离散数学》内容主要包括: 数理逻辑中命题演算、谓词演算等形式逻辑的推理规律；集合的概念、运算及应用，集合内元素间的关系以及集合之间的关系,无限集的特性；抽象代数的基本理论和应用,格与布尔代数图论学科的基本概念、欧拉图、哈密尔顿图、最小路径算法、中国邮路问题、树及平面图的基本理论；通过该课程可以培养学生的抽象思维和慎密的概括能力，该课程主要适用于自动控制、电子工程、管理科学等有关专业，是计算机专业的必修课。

（三）课程性质、目的和任务《离散数学》课程是为计算机科学与技术专业的学生开设的一门专业基础课程。

随着计算机科学的发展和计算机应用领域的日益广泛，迫切需要适当的数学工具来解决计算机科学各个领域中提出的有关离散量的理论问题，离散数学就是适应这种需要而建立的，它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述，从而为研究计算机科学及相关学科提供了有利的理论基础和工具。

是学习后续专业课程不可缺少的数学工具，如：高级语言、数据结构、编译原理、操作系统、可计算性理论、人工智能、形式语言与自动机、信息管理与检索以及开关理论等，离散数学也是研究自动控制、管理科学、电子工程等的重要工具。

命题逻辑▪(论域)定义：论域是一个数学系统，记为D。

它由三部分组成：•(1)一个非空对象集合S，每个对象也称为个体；•(2) 一个关于D的函数集合F；•(3)一个关于D的关系集合R。

▪（逻辑连接词）定义•设n>0,称为{0,1}n到{0,1}的函数为n元函数，真值函数也称为联结词。

•若n =0，则称为0元函数。

▪（命题合式公式）定义：•(1).常元0和1是合式公式；•(2).命题变元是合式公式；•(3).若Q,R是合式公式，则(⌝Q)、(Q∧R) 、(Q∨R) 、(Q→R) 、(Q↔R) 、(Q⊕R)是合式公式；•(4).只有有限次应用(1)—(3)构成的公式是合式公式。

▪（生成公式）定义1.5 设S是联结词的集合。

由S生成的公式定义如下：•⑴若c是S中的0元联结词，则c是由S生成的公式。

•⑵原子公式是由S生成的公式。

•⑶若n≥1，F是S中的n元联结词，A1,…,A n是由S生成的公式，则FA1…A n 是由S生成的公式。

▪（复杂度）公式A的复杂度表示为FC(A)•常元复杂度为0。

•命题变元复杂度为0，如果P是命题变元，则FC (P)=0。

•如果公式A=⌝B，则FC (A)=FC(B)+1。

•如果公式A=B1∧ B2，或A=B1∨ B2，或A=B1→B2，或A=B1↔ B2，或A=B1⊕ B2，或则FC (A)=max{FC(B1), FC(B2)}+1。

▪命题合式公式语义•论域：研究对象的集合。

•解释：用论域的对象对应变元。

•结构：论域和解释称为结构。

•语义：符号指称的对象。

公式所指称对象。

合式公式的语义是其对应的逻辑真值。

▪（合式公式语义）设S是联结词的集合是{⌝，∧，∨，⊕，→，↔}。

由S生成的合式公式Q在真值赋值v下的真值指派v(Q)定义如下：•⑴v(0)=0, v(1)=1。

•⑵若Q是命题变元p，则v(A)= pv。

•⑶若Q1,Q2是合式公式▪若Q= ⌝Q1，则v(Q)= ⌝v(Q1)▪若Q=Q1 ∧ Q2，则v(Q)=v(Q1)∧ v(Q2)▪若Q=Q1∨Q2，则v(Q)=v(Q1)∨v(Q2)▪若Q=Q1→ Q2，则v(Q)=v(Q1)→ v(Q2)▪若Q=Q1 ↔ Q2，则v(Q)=v(Q1)↔ v(Q2)▪若Q=Q1⊕ Q2，则v(Q)=v(Q1)⊕ v(Q2)▪（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下：•⑴若Q是S中的0元联结词c，则v(Q)=c。

第一章命题逻辑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 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

第一章命题逻辑原子命题：不包含任何联结词的命题叫做原子命题。

复合命题：至少包含一个联结词的命题称作复合命题。

重言式：给定一个命题公式，若无论对分量作怎样的指派，其对应的真值用为T。

蕴含：当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作P⇒Q对偶：在给定的命题公式中，将联结词⋁换成⋀，将⋀换成⋁，若有特殊边缘F和T亦相互取代，所得公式A*称为A的对偶式。

主析取范式：对于给定的命题公式，如果有一个等价公式，它仅小项的析取所组成，则该等价式称作原式的主析取范式。

主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。

第二章谓词逻辑不可满足的：一个谓词公式wff A，如果在所有赋值下都为假，则称该wff A为不可满足的。

可满足的：一个谓词公式wff A，如果至少在一种赋值下为真，则称该wff A为可满足的。

前束范式：一个公式，如果两次均在全式的开头，它们的作用域，延伸到整个公式末尾，则该公式叫做前束范式。

第三章集合与关系包含：设A，B是任意两个集合，假如A的每一个元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。

记作A⊆B，或B⊇A。

真子集：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集，记作A⊂B。

幂集：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。

集合的交：设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作A⋂B。

集合的并：设任意两个集合A和B，所有属于A或属于B的元素组成的集合S，称为A和B的集合，记作A⋃B。

集合的绝对补：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作~A。

对称差：设A，B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于B，记作A⊕B。

序偶相等：两个序偶相等，<x，y>=<u，v>，iffx=u,y=v。