离散数学 课件 1.7 对偶与范式

01命题逻辑1.7对偶与范式：探索命题逻辑的标准化之路MATHEMATICALLOGIC&FOUNDATIONS逻辑公式的变形与标准化01/对偶：逻辑世界的对称之美•对偶式的定义与求解方法•对偶定理与对偶原理的核心思想02/范式：逻辑公式的标准化•合取范式(CNF)与析取范式(DNF)的定义•范式的一般求解方法与基础应用场景03/主范式：唯一的标准形式•极小项与极大项：主范式的基本构成单元•主析取/合取范式的求解与相互转化•主范式在逻辑电路与证明中的应用1.7.1对偶：逻辑世界的对称之美对偶的引入：等价式的成对出现在我们之前学习的命题定律中，许多常用的等价式是“成对”出现的。例如，交换律、结合律、分配律等，只要将其中的逻辑“与”符号（合取“∧”）和逻辑“或”符号（析取“∨”）相互交换，往往就能从一个定律直接推导出另一个。析取结合律(Disjunction)(P∨Q)∨R⇔P∨(Q∨R)运算符号：逻辑“或”(∨)合取结合律(Conjunction)(P∧Q)∧R⇔P∧(Q∧R)运算符号：逻辑“与”(∧)这种成对出现的等价式，深刻地反映了逻辑运算系统内部的一种对称与平衡——即“对偶性”。定义1.24：对偶式的定义在仅含有联结词¬，∧，∨的命题公式A中，将∧换成∨，∨换成∧，若存在常元T和F，亦相互取代，所得公式A*称为A的对偶式。▌核心操作步骤交换联结词：将公式A中的析取符号(∨)替换为合取符号(∧)，反之亦然。交换常元：将公式A中的T(真)与F(假)互相替换否定词不变：所有否定联结词¬保持原样，不进行任何改变。•互为对偶：如果A*是A的对偶式，那么A也是A*的对偶式，即(A*)*⇔A。•等价性传递：若A⇔B，则A*⇔B*。例题1.54：写出下列表达式的对偶式A:¬(P∧Q)∨(P∧(¬Q∨¬S)∨T)解:A*:¬(P∨Q)∧(P∨(¬Q∧¬S)∧F)B:(P∧Q)∧T解:B*:(P∨Q)∨FC:P↑Q(与非)解:P↑Q⇔¬(P∧Q)，其对偶式为¬(P∨Q)⇔P↓Q(或非)D:P↓Q(或非)解:P↓Q⇔¬(P∨Q)，其对偶式为¬(P∧Q)⇔P↑Q(与非)对偶式概念的推广：在仅含联结词¬,∧,∨,↑,↓的公式中，将联结词∨与∧、常元T与F、以及联结词↑与↓分别互换，即可得到其对偶式。定理1.5：对偶定理定理内容设A和A*互为对偶式，P₁,P₂,...,Pₙ是出现在A和A*中的所有原子命题变元，则：(1)¬A(P₁,P₂,...,Pₙ)⇔A*(¬P₁,¬P₂,...,¬Pₙ)(2)A(¬P₁,¬P₂,...,¬Pₙ)⇔¬A*(P₁,P₂,...,Pₙ)定理解读◆式(1)意义：

一个公式的否定，等价于将其所有命题变元取否定后的对偶式。这提供了一种将否定词深入到公式内部的方法。◆式(2)意义：

将一个公式中所有命题变元取否定，等价于其对偶式的否定。这揭示了变元否定与对偶式之间的转换关系。证明思路该定理的证明主要基于逻辑代数中的基础法则：德摩根定律(DeMorgan'sLaws)通过反复应用德摩根定律，将公式最外层的否定符号逐步向内深入，直到深入到每一个原子命题变元之前。在此过程中，公式中的逻辑连接词（如∧与∨）也随之互换，这实际上就是构造原公式对偶式的过程。例题1.55：证明A*(¬S,¬W,¬R)⇔¬A(S,W,R)已知条件：逻辑表达式A*的定义为：A*(S,W,R)⇔¬S∧(¬W∨R)STEP01：计算A*(¬S,¬W,¬R)将变元S,W,R分别替换为¬S,¬W,¬R：

A*(¬S,¬W,¬R)⇔¬(¬S)∧(¬(¬W)∨¬R)

根据双重否定律化简得：

S∧(W∨¬R)STEP02：求原公式A(S,W,R)A是A*的对偶式。交换∧与∨，可得：

A(S,W,R)⇔¬S∨(¬W∧R)

这就是原公式A的逻辑表达式。STEP03：计算¬A(S,W,R)对原公式取否定并应用德摩根定律：

¬A⇔¬(¬S∨(¬W∧R))

⇔¬(¬S)∧¬(¬W∧R)

⇔S∧(W∨¬R)结论：对比步骤1和步骤3的最终化简结果，两者完全一致，均为S∧(W∨¬R)。

因此，我们证明了逻辑等价关系A*(¬S,¬W,¬R)⇔¬A(S,W,R)成立。证毕。定理1.6（对偶原理）定理内容：如果公式A与公式B逻辑等价（即A⇔B），那么A的对偶式A*与B的对偶式B*也逻辑等价（即A*⇔B*）。证明思路1.基础：若A⇔B，则双条件式A↔B是重言式。2.代入：将公式中所有变元Pi替换为¬Pi，得到A(¬P)↔B(¬P)，仍为重言式。3.替换：根据定理1.5，A(¬P)⇔¬A*，B(¬P)⇔¬B*，代入得¬A*↔¬B*。4.结论：对¬A*↔¬B*两边同时取否定，即可得证A*⇔B*。对偶原理的意义对偶原理是逻辑推理中的“倍增器”。它告诉我们：只要证明了一个逻辑等价式，就相当于自动证明了它的对偶式。这一性质极大地减少了需要记忆和证明的逻辑公式数量，从而显著提高了逻辑推导的效率。“事半功倍”的逻辑捷径1.7.2范式：逻辑公式的标准化范式的引入：为何需要标准化？命题公式的形式千变万化，这给判断两个公式是否等价、分析公式的真值情况带来了很大不便。真值表虽然直观，但当命题变元增多时，其规模会呈指数级增长，变得不切实际。为了解决这个问题，引入范式(NormalForm)的概念。范式是一种具有固定格式的命题公式，它能解决上述难题：简化分析将复杂的公式转化为范式，能够快速判断公式的真值情况：它是一个永真的重言式、永假的矛盾式，还是一个可满足式。统一比较为逻辑推理建立统一的标准语言。将两个看似不同的公式转化为标准形式后，就可以直观、方便地比较它们在逻辑上是否等值。范式的定义定义1.25：合取范式(CNF)一个命题公式称为合取范式，当且仅当它具有型式：A₁∧A₂∧...∧Aₙ，其中每个Aᵢ都是由命题变元或其否定所组成的析取式（简单析取式）。结构特征：合取范式本质上是简单析取式的合取（逻辑“与”）。示例：(P∨Q)∧(P∨¬Q∨¬S)定义1.26：析取范式(DNF)一个命题公式称为析取范式，当且仅当它具有型式：A₁∨A₂∨...∨Aₙ，其中每个Aᵢ都是由命题变元或其否定所组成的合取式（简单合取式）。结构特征：析取范式本质上是简单合取式的析取（逻辑“或”）。示例：(P∧Q)∨(P∧¬Q∧¬S)范式的性质析取范式的性质一个析取范式是矛盾式，当且仅当它的每一个简单合取式Ai都是矛盾式（即每个Ai都包含某个变元及其否定）。合取范式的性质一个合取范式是重言式，当且仅当它的每一个简单析取式Ai都是重言式（即每个Ai都包含某个变元及其否定）。范式存在定理任一命题公式都存在着与之等值的析取范式和合取范式。范式的求解方法STEP01·消去联结词利用逻辑等价式，将公式中所有的蕴涵词“→”和等价词“↔”消去，仅保留基本联结词¬、∧、∨。•蕴涵等值式：P→Q⇔¬P∨Q•等价等值式：P↔Q⇔(¬P∨Q)∧(¬Q∨P)STEP02·否定词内移反复运用德摩根定律和双重否定律，将否定联结词“¬”向内深入，直至直接作用于单个的命题变元。•德摩根定律：¬(P∨Q)⇔¬P∧¬Q¬(P∧Q)⇔¬P∨¬Q•双重否定律：¬¬P⇔PSTEP03·整理成范式根据目标范式类型，利用分配律进行结构调整。同时利用结合律和幂等律等简化公式。合取范式：用∨对∧的分配律

P∨(Q∧R)⇔(P∨Q)∧(P∨R)析取范式：用∧对∨的分配律

P∧(Q∨R)⇔(P∧Q)∨(P∧R)例题1.56：求(P∧(Q→R))→S的合取范式STEP01消去蕴含→利用逻辑等价式A→B⇔¬A∨B消去公式中的蕴含符号：(P∧(Q→R))→S⇔(P∧(¬Q∨R))→S⇔¬(P∧(¬Q∨R))∨SSTEP02否定词内移利用德·摩根定律，将否定联结词¬向内移动，直至紧贴命题变项：⇔¬P∨¬(¬Q∨R)∨S⇔¬P∨(Q∧¬R)∨S💡注：此式已是“析取范式”STEP03整理成合取范式使用“∨对∧的分配律”将公式展开：⇔((¬P∨S)∨Q)∧((¬P∨S)∨¬R)⇔(¬P∨S∨Q)∧(¬P∨S∨¬R)✅最终结果：合取范式例题1.57：求¬(P∨Q)↔(P∧Q)的析取范式01.消去等价符号(↔)(利用公式:A↔B⇔(A∧B)∨(¬A∧¬B))¬(P∨Q)↔(P∧Q)⇔(¬(P∨Q)∧(P∧Q))∨((P∨Q)∧¬(P∧Q))02.否定词内移(利用德·摩根定律¬(A∨B)⇔¬A∧¬B和¬(A∧B)⇔¬A∨¬B)⇔(¬P∧¬Q∧P∧Q)∨((P∨Q)∧(¬P∨¬Q))03.整理为析取范式(利用分配律展开，并消去矛盾式，即恒假式0)⇔(0)∨((P∧¬P)∨(¬P∧Q)∨(P∧¬Q)∨(Q∧¬Q))⇔(¬P∧Q)∨(P∧¬Q)—最终的主析取范式—1.7.3主范式：唯一的标准形式范式的“不唯一性”困境虽然范式为命题逻辑提供了规范化的表达工具，但它在形式上并不唯一。例如：同一个逻辑关系，可以被改写为不同的标准范式：•析取范式：P∨(Q∧R)•合取范式：(P∨Q)∧(P∨R)这给逻辑公式的等价性判断和标准化带来了不便。引入“主范式”的必要性为了解决形式不唯一的问题，引入了“主范式”这一概念。它的核心价值在于：➊唯一性：对于任意一个含n个命题变项的公式，其主范式的形式是唯一的。可以通过对比主范式直接判断公式的等价性。➋两种类型：包含主析取范式和主合取范式，分别对应公式的成真赋值与成假赋值分析。主范式的定义定义1.27：小项(极小项,Minterm)n个命题变元的合取式，每个变元与它的否定必须出现且仅出现一次。•示例(P,Q):P∧Q,P∧¬Q,¬P∧Q,¬P∧¬Q•编码:变元原形记为1，否定形式记为0。例:P∧¬Q→10(m₂)定义1.29：大项(极大项,Maxterm)n个命题变元的析取式，每个变元与它的否定必须出现且仅出现一次。•编码(与小项相反):变元原形记为0，否定形式记为1。

例:P∨¬Q→01(记为M₀₁或M₁)定义1.28：主析取范式由若干个小项的析取(∨)所组成的、与原公式等价的命题公式。它是一种标准形式，能直观地显示公式为真的赋值。定义1.30：主合取范式由若干个大项的合取(∧)所组成的、与原公式等价的命题公式。它也是一种标准形式，能直观地显示公式为假的赋值。主范式的求解方法：方法一真值表法定理1.7(主析取范式)在真值表中，一个公式的真值为T(真)的指派所对应的小项的析取(∨)，即为此公式的主析取范式。定理1.8(主合取范式)在真值表中，一个公式的真值为F(假)的指派所对应的大项的合取(∧)，即为此公式的主合取范式。01构建真值表列出所有命题变元的逻辑组合，逐一计算并填入公式的最终真值（T或F）02求主析取范式找出真值为T的所有行。将每行变元取值（T=1，F=0）转化为对应的极小项，最后对所有极小项进行析取(∨)运算。03求主合取范式找出真值为F的所有行。将每行变元取值（T=0，F=1）转化为对应的极大项，最后对所有极大项进行合取(∧)运算。例题1.59：求(P→Q)∧(Q→R)的主范式（真值表法）PQRP→QQ→R(P→Q)∧(Q→R)000111001111010100011111100010101010110100111111主析取范式(DisjunctiveNormalForm)成真赋值：000,001,011,111→极小项m₀,m₁,m₃,m₇A⇔m₀∨m₁∨m₃∨m₇⇔∑(0,1,3,7)主合取范式(ConjunctiveNormalForm)成假赋值：010,100,101,110→极大项M₂,M₄,M₅,M₆A⇔M₂∧M₄∧M₅∧M₆⇔∏(2,4,5,6)主范式的求解方法：方法二等值演算法求解步骤01.求范式首先，求出公式的析取范式（用于求主析取范式）或合取范式（用于求主合取范式），作为求解的基础。02.填补缺少的变元若简单式缺少变元P，利用互补律填补：

•主析取：Bi=Bi∧(¬P∨P)•主合取：Bi=Bi∨(¬P∧P)03.合并与排序：合并重复项，调整顺序以获得规范的主范式表达。例题1.59(续)：等值演算求主合取范式(P→Q)∧(Q→R)⇔(¬P∨Q)∧(¬Q∨R)(消去蕴含符号→)⇔((¬P∨Q)∨(¬R∧R))∧((¬Q∨R)∨(¬P∧P))(填补变元)⇔(¬P∨Q∨¬R)∧(¬P∨Q∨R)∧(¬Q∨R∨¬P)∧(¬Q∨R∨P)(分配律展开)⇔(P∨¬Q∨R)∧(¬P∨Q∨R)∧(¬P∨Q∨¬R)∧(¬P∨¬Q∨R)(整理)⇔∏(2,4,5,6)主范式的相互转化互补关系原理对于包含n个变元的命题公式，主析取范式中“未出现”的极小项下标，恰好是主合取范式中“出现”的极大项下标；反之亦然。二者的下标集合构成全集{0,1,...,2ⁿ-1}的一个划分。快速转化四步法1.求其一：先求出公式的其中一种主范式（如主析取范式）。

2.定全集：确定变元个数n，得出下标全集范围为0~2ⁿ-1。

3.找补集：找出第一步结果中“未使用”的下标。

4.写结论：直接用未使用的下标写出另一种主范式。例题1.63解析求以下公式的主范式：A=(P∧Q)∨(¬P∧R)∨(¬Q∧¬R)Step1:求主析取范式(m)A⇔∑(0,1,3,4,6,7)（共6个极小项）Step2:求主合取范式(M)补集下标{2,5}⇒A⇔M₂∧M₅主范式的应用判断公式等值两个命题公式逻辑等值，当且仅当它们的主析取范式（或主合取范式）完全相同。这是主范式最重要的理论应用之一，提供了一种将公式转化为规范形式后进行机械比对的方法。判断公式类型•重言式：主析取范式包含全部2ⁿ个极小项（小项）。•矛盾式：主析取范式为空，不包含任何极小项。•可满足式：主析取范式至少包含一个极小项。解决实际逻辑推理将复杂的实际问题转化为标准的逻辑公式，通过求其主析取范式，可以清晰、系统地列出所有满足条件的解（成真赋值）。这种方法在逻辑电路设计、人工智能规划和决策分析等领域有广泛应用。例题1.65：解决实际逻辑推理问题题目背景与约束条件某研究所要从A、B、C三名科研骨干中挑选1