离散数学 课件 2.6 前束范式

CHAPTER02谓词逻辑2.6前束范式目录CONTENTS01基本概念了解前束范式的定义，掌握其核心特征与标准逻辑形式。02化归方法掌握将任意谓词公式化为前束范式的四个关键步骤与操作要点。03例题解析通过典型的公式转换例题，巩固并熟练应用化归方法。04进一步规范探索更严格的范式：前束合取范式与前束析取范式。定义2.13：前束范式(PrenexNormalForm)定义内容设G为一个谓词公式，如果量词均在全式的开头（不含否定词¬），它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。简单来说，就是将公式中所有的量词都“提到”最前面，并且这些量词后面的部分不再含有任何量词。这是谓词逻辑中的一种规范化表达形式，便于进行公式的简化和推理。标准形式(□v₁)(□v₂)⋯(□vn)A▪□：代表量词符号，可表示全称量词∀或存在量词∃。▪vi：代表客体变元（个体变元），其中i=1,2,3,⋯,n▪A：是不含有任何量词的谓词公式，被称为公式的“母式”(Matrix)。前束范式示例解析是前束范式(Valid)∀x∃y(F(x)→(G(y)∧H(x,y)))解析：全称量词∀x与存在量词∃y均位于公式最左端，且量词的作用域延伸并覆盖了整个公式。∀x¬(F(x)∧G(x))解析：全称量词∀x位于公式最前端，否定连接词¬处于量词作用域的内部，符合前束范式的定义。不是前束范式(Invalid)∀x(F(x)→∃y(G(y)∧H(x,y)))解析：存在量词∃y被包含在蕴含式的后件中，没有移至公式的最左端，不符合“前缀”的要求。¬∃x(F(x)∧G(x))解析：否定连接词¬出现在唯一的量词∃x之前，构成了“否定量词”的形式，不满足前束范式定义。定理2.1：前束范式存在定理定理内容：任何一个一阶逻辑中的谓词公式，都存在与之等价的前束范式。01.否定深入利用量词转化等值式（¬∀xA(x)⇔∃x¬A(x)和¬∃xA(x)⇔∀x¬A(x)），将否定联结词¬逐步向内“深入”，直至移到命题变元和谓词填式的前面。02.量词前移利用量词辖域扩张等值式，将公式中所有的量词依次“前移”，直至全部移到整个公式的最前端，形成前束范式的形式。化前束范式的详细步骤01换名（必要时）目的：确保不同量词的指导变元使用不同的符号，避免混淆。依据：(∃x)A(x)⇔(∃y)A(y)02转换联结词目的：消去蕴含(→)和双条件(↔)，统一使用否定(¬)、合取(∧)和析取(∨)。依据：P→Q⇔¬P∨Q03否定内移目的：将否定联结词(¬)移到紧靠谓词的位置，即仅作用于原子公式。依据：量词否定等值式、德摩根定律04量词前移目的：将所有的量词（全称或存在）都移到整个公式的最前端，形成前束部分。依据：量词辖域扩张/收缩等值式步骤一：换名(Rename)核心目的确保不同量词的指导变元（约束变元）使用不同的符号，避免因变量同名而产生逻辑混淆。特别注意：在进行“量词前移”操作前，必须先完成换名，以防止变量名冲突导致的推导错误。经典示例原公式中，两个量词作用域内的变量均为x，但它们是独立的：∀xF(x)∨∀xG(x)若需将第二个全称量词前移，必须先换名（如换成y），避免变量冲突：∀xF(x)∨∀yG(y)逻辑依据换名规则基于“约束变元易字规则”，在不改变公式逻辑含义的前提下，约束变元可以替换为公式中未出现的任意变元符号：1.(∃x)A(x)⇔(∃y)A(y)2.(∀x)A(x)⇔(∀y)A(y)注：y必须是在公式A(x)中未出现的符号。步骤二：转换联结词01/转换目的消去公式中可能存在的条件联结词(→)和双条件联结词(↔)。将公式统一转化为仅使用否定(¬)、合取(∧)、析取(∨)三种基本联结词来表达，为后续步骤打好基础。02/转换依据•蕴含消去律：

P→Q⇔¬P∨Q•等价消去律：

P↔Q⇔(¬P∨Q)∧(¬Q∨P)03/转换示例•示例一：

F(x)→G(x)⇒¬F(x)∨G(x)•示例二：

F(x)↔G(x)⇒(¬F(x)∨G(x))∧(¬G(x)∨F(x))步骤三：否定内移核心目的将公式中所有的否定联结词¬，一层一层向内“推进”，直到紧靠谓词的位置，即最终位于原子公式或其否定之前。这是化归过程中最容易出错的关键步骤。量词否定等值式¬(∀x)A(x)⇔(∃x)¬A(x)¬(∃x)A(x)⇔(∀x)¬A(x)德摩根定律¬(P∨Q)⇔¬P∧¬Q¬(P∧Q)⇔¬P∨¬Q双重否定¬¬P⇔P步骤四：量词前移▍核心目的将公式中所有的量词按顺序移到整个公式的最前端，并保证其辖域能延伸至公式的末尾，最终形成前束范式的结构。量词分配等值式∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)量词辖域扩张等值式（当B中不含x时）∀x(A(x)∨B)⇔∀xA(x)∨B∃x(A(x)∧B)⇔∃xA(x)∧B例题2.19：详细步骤解析【题目】求谓词逻辑公式：¬((∀x)(∃y)P(a,x,y)→(∃x)(¬(∀y)Q(y,b)→R(x)))的前束范式。01消去蕴含符号(→)¬(¬(∀x)(∃y)P(a,x,y)∨(∃x)((∀y)Q(y,b)∨R(x)))02否定联结词(¬)内移(∀x)(∃y)P(a,x,y)∧(∀x)((∃y)¬Q(y,b)∧¬R(x))03量词前移并合并(∀x)[(∃y)P(a,x,y)∧(∃y)¬Q(y,b)∧¬R(x)]04换名规则(避免变元冲突)将第二个(∃y)中的约束变元y替换为z，避免与前一个y混淆：

(∀x)[(∃y)P(a,x,y)∧(∃z)¬Q(z,b)∧¬R(x)]05最终前移：得到前束范式(∀x)(∃y)(∃z)(P(a,x,y)∧¬Q(z,b)∧¬R(x))结论：此公式即为原公式的一个前束范式。例题2.20(1)：¬∃x(M(x)∧F(x))解法一⇔∀x(¬M(x)∨¬F(x))(量词否定等值式)解法二⇔∀x(M(x)→¬F(x))(再转换为条件式)CONCLUSION

结论一个公式的前束范式不是唯一的（Non-unique）例题2.20(2)：∀xF(x)∧¬∃xG(x)解法一：量词分配律⇔∀xF(x)∧∀x¬G(x)(量词否定等值式)⇔∀x(F(x)∧¬G(x))(全称量词对合取的分配律)解法二：换名规则+量词扩张⇔∀xF(x)∧∀y¬G(y)(换名规则)⇔∀x∀y(F(x)∧¬G(y))(量词辖域收缩与扩张律)结论：前束范式的不唯一性同一个谓词公式，可以通过不同的等值演算路径，得到多个形式不同但逻辑等价的前束范式。上述两种方法得到的结果均正确。例题2.20(3)：∃xF(x)∨¬∀xG(x)STEP01·量词否定等值式∃xF(x)∨∃x¬G(x)对公式¬∀xG(x)应用量词否定规则，转化为存在量词STEP02·量词分配律∃x(F(x)∨¬G(x))提取公共的存在量词，完成前束范式的转换💡核心结论：存在量词对析取可以直接分配一般形式：∃xA(x)∨∃xB(x)⇔∃x(A(x)∨B(x))，注意全称量词对析取不满足分配律。例题2.20(4)：∀xF(x)→∃y(G(x,y)∧¬H(y))Step1.约束变元换名⇔∀zF(z)→∃y(G(x,y)∧¬H(y))说明：前提中的约束变元x与结论中的自由变元x同名，为避免混淆，将约束变元x替换为z。Step2.量词前移(Prenexing)⇔∃z∃y(F(z)→(G(x,y)∧¬H(y)))说明：完成换名后，已消除变元冲突，可将全称量词∀z转换为存在量词∃z并移至公式最前端。💡核心易错点：变元冲突在此例中，若不先对约束变元x进行换名，直接进行量词前移操作，会导致原自由变元x被错误地量化约束，从而改变原命题的语义。因此，“换名”是保证逻辑等价性的前提条件。例题2.20(5)：∀x(F(x,y)→∃y(G(x,y)∧H(x,z)))推导过程Step1:⇔∀x(F(x,y)→∃u(G(x,u)∧H(x,z)))——换名规则：将内层约束变元y替换为u，避免与外层自由变元y重名混淆Step2:⇔∀x∃u(F(x,y)→(G(x,u)∧H(x,z)))——量词前移：根据逻辑等值式，将存在量词移至蕴含式之前，与全称量词结合重要逻辑原则：量词顺序不可随意颠倒在最终的前束范式中，∀x和∃u的顺序不能交换。因为∃u处于∀x的辖域之内，其变量的取值依赖于外层∀x的取值。如果颠倒顺序，公式表达的逻辑语义将发生根本性改变。例题2.20(6)：∃xF(x)→∀xG(x)Step1：消去蕴含词(→)⇔¬∃xF(x)∨∀xG(x)Step2：量词否定转换⇔∀x¬F(x)∨∀xG(x)Step3：变元换名(关键操作)⇔∀x¬F(x)∨∀yG(y)Step4：量词前移(扩张)⇔∀x∀y(¬F(x)∨G(y))核心易错点提示全称量词对析取不能直接分配，切勿写成∀x(¬F(x)∨G(x))。正确逻辑：必须先对变元进行换名，再统一进行量词前移扩张。定义2.14：前束合取范式一个谓词公式A，如果具有如下形式，则称为前束合取范式：(□v1)(□v2)…(□vn)[(A11∨A12∨…∨A1k)∧(A21∨A22∨…∨A1t)∧…∧(Am1∨Am2∨…∨Aml)]结构要求它是在前束范式的基础上，进一步要求其母式部分必须是一个合取范式。原子构成公式中的Aij

必须是原子公式或其否定式，不可再分解为更简单的逻辑式。定理2.2存在性逻辑系统完备性的重要体现：每一个谓词公式都可以转化为与其逻辑等价的前束合取范式。定义2.15：前束析取范式▍定义描述一个谓词公式A，如果具有如下形式，则称为前束析取范式：(□v₁)(□v₂)⋯(□vn)[(A₁₁∧A₁₂∧⋯∧A₁k)∨(A₂₁∧A₂₂∧⋯∧A₂t)∨⋯∨(Am₁∧Am₂∧⋯∧Aml)]结构基础：前束范式+析取母式它是在前束范式的基础上，进一步严格要求其母式A必须是一个标准的析取范式。元素构成：原子公式或其否定公式中的所有Aij均限定为原子公式，或者是原子公式的否定形式，不可再拆分。定理2.3（存在性定理）在谓词逻辑系统中，每一个谓词公式都可以通过有限次的等价变形规则，转化为与其逻辑等价的前束析取范式。本节核心要点回顾前束范式定义谓词逻辑中一种标准形式，要求公式中的所有量词都集中出现在整个公式的最前端，且量词的作用域延伸到公式的末端。核心化归四步法1.换名规则→2.转换联结词(消去→与↔)

3.否定内移→4.量词前移(利用分配/扩张律)易错与关键技