离散数学 课件 2.4 变元的约束

CHAPTER02谓词逻辑2.4变元的约束目录CONTENTS01核心概念指导变元、作用域、约束变元、自由变元02案例分析例题解析，识别辖域与变元类型。03规则详解约束变元的换名规则与自由变元的代入规则。04深化与总结闭式的定义、有限论域下的量词展开及总结。定义2.8：指导变元与作用域给定G为一个谓词公式，其中有一部分公式形式为`(∀x)P(x)`或`(∃x)F(x)`。这里，“∀”、“∃”后面所跟的x叫做量词的指导变元或作用变元，`P(x)`叫做相应量词的作用域或辖域，即量词起作用的范围。指导变元(LeadingVariable)紧跟在量词`∀`(全称量词)或`∃`(存在量词)后面的变量，指明了被量化的对象是什么。作用域/辖域(Scope)量词的“影响力”所能达到的公式范围。只有在这个范围内，指导变元才是受约束的。定义2.9：约束出现与约束变元定义内容给定一个合式公式G,若变元x出现在使用变元的量词的辖域之内,也就是在作用域中x的一切出现,则称变元x的出现为约束出现，x亦称为被相应量词中的指导变元所约束，此时的变元x称为约束变元。约束出现变元的出现位置满足“在某个量词的辖域内”这一前提条件。这是一个关于位置关系的定义约束变元指被量词“绑定”或“管辖”的变元本身。它的取值范围受到对应量词的限制，而非自由取值。定义2.10：自由出现与自由变元📖定义核心内容若x的出现不是约束出现，则称它为自由出现，此时的变元x称为自由变元。自由变元是“不受约束”的变元。虽然它有时也在量词的作用域中出现，但它并不受相应量词中指导变元的约束。因此，在逻辑公式中，我们可以把自由变元看作是公式中的一个独立参数。🔑什么是“自由出现”？指变元的出现位置，要么完全不在任何量词的辖域之内，要么虽在辖域内，但不受该量词的直接约束。⚙️如何理解“自由变元”？它是公式中的一个“独立参数”。它的值不依赖于公式中的量词，可以根据具体的论域任意指定。在某种程度上，它相当于函数中的“自变量”。如何确定量词的辖域？方法一：量词后有括号规则：若量词后紧跟左括号，则括号内的完整子公式就是该量词的辖域。这是最清晰、最不容易产生歧义的写法。标准形式：(∀x)(...)或(∃x)(...)示例：在公式(∀x)(P(x)∨Q(y))中，(∀x)的辖域是整个括号内的(P(x)∨Q(y))。方法二：量词后无括号规则：若量词后无括号，则辖域范围“最小化”，即仅包含与量词邻接的第一个原子公式（原子谓词公式）。标准形式：(∀x)F(x)∧G(y)或(∃y)R(x,y)→S(y)示例：在公式(∃y)R(x,y)∧P(x)中，(∃y)的辖域仅为R(x,y)，不包含P(x)。例题2.12(1)：分析辖域与变元类型(∀x)(P(x)→(∃y)R(x,y))辖域范围界定●(∀x)的辖域：(P(x)→(∃y)R(x,y))●(∃y)的辖域：R(x,y)注：辖域指量词约束的最小完整逻辑公式。变元约束状态判定1.P(x)中的x：约束变元(受外层全称量词∀x约束)2.R(x,y)中的x：约束变元

(仍受∀x约束，非自由变元)3.R(x,y)中的y：约束变元(受存在量词∃y约束)例题2.12(2)：分析辖域与变元类型公式：(∃x)P(x)∧Q(x,y)辖域判定全称量词(∃x)的作用范围：在公式(∃x)P(x)∧Q(x,y)中，(∃x)仅对紧随其后的P(x)产生约束作用，并不跨越逻辑连接符∧覆盖到Q(x,y)。结论：(∃x)的辖域是P(x)。变元类型辨析•P(x)中的x：约束变元(受左侧存在量词∃x直接约束)。•Q(x,y)中的x：自由变元(与左边的x重名，但不在(∃x)的辖域内)。•Q(x,y)中的y：自由变元(公式中没有任何量词对其进行约束)。例题2.12(3)：分析辖域与变元类型(∀x)(∃y)(P(y,z)∨Q(x,y))∧(∃x)R(x,y)辖域范围界定•(∀x)的辖域：(∃y)(P(y,z)∨Q(x,y))•(∃y)的辖域：(P(y,z)∨Q(x,y))•(∃x)的辖域：R(x,y)变元类型判定•P(y,z)和Q(x,y)中的x,y：约束变元•P(y,z)中的z：自由变元•R(x,y)中的x：约束变元（受第二个∃x约束）•R(x,y)中的y：自由变元例题2.12(4)：分析辖域与变元类型(∀x)(P(x)→R(x))∧(∃y)Q(x,y)辖域分析•全称量词(∀x)的辖域：公式右侧紧随其后的子公式(P(x)→R(x))•存在量词(∃y)的辖域：公式右侧紧随其后的原子公式Q(x,y)变元类型判定•P(x)、R(x)中的x：受(∀x)约束➜约束变元•Q(x,y)中的x：未被任何量词约束➜自由变元•Q(x,y)中的y：受(∃y)约束➜约束变元💡逻辑辨析提示同一个符号（如本式中的x）在同一公式中完全可以同时作为“约束变元”和“自由变元”出现。虽然书写符号相同，但它们在逻辑上属于完全独立、互不影响的变元。例题2.12(5)：分析辖域与变元类型(∀x)(P(x)∧(∃x)Q(x,z)→(∃y)R(x,y))∨Q(x,y)辖域分析ScopeAnalysis•(∀x)的辖域：(P(x)∧(∃x)Q(x,z)→(∃y)R(x,y))•(∃x)的辖域：Q(x,z)•(∃y)的辖域：R(x,y)变元类型判定VariableTypesP(x)中的x：约束变元(受最外层∀x约束)Q(x,z)中的x：约束变元(受内部∃x屏蔽式约束)Q(x,z)中的z：自由变元(FreeVariable)R(x,y)中的x,y：均为约束变元Q(x,y)(最右侧)：x,y均为自由变元从n元谓词到命题的演变核心观点•表达式P(x₁,x₂,...,xₙ)代表一个n元谓词，其中包含n个相互独立的自由变元。•若对其中k个自由变元进行全称或存在量化约束，则该表达式演变为一个(n-k)元谓词。•结论：当一个谓词公式中不再含有任何自由变元时，它不再是谓词，而是一个具有确定真假值的命题。逻辑示例(∀x)P(x,y,z)→二元谓词(剩余自由变元：y,z)(∃y)(∀x)P(x,y,z)→一元谓词(剩余自由变元：z)(∃z)(∃y)(∀x)P(x,y,z)→命题(无自由变元，具有确定真值)规则1：约束变元的换名规则换名范围对于约束变元可以换名，更改的范围是量词中的指导变元，以及该量词作用域中所出现的该变元。公式的其余部分保持不变。新名选择换名时必须遵循一个核心原则：一定要将变元更改为在当前作用域中没有出现过的变元名称，避免与已有自由变元或其他约束变元混淆。核心思想：符号无关紧要，意义保持一致

公式(∀x)P(x)与(∀y)P(y)在逻辑上完全等价。约束变元只是一个占位符，它的具体符号名称并不影响公式的本质含义。规则2：自由变元的代入规则01.全域代入对于谓词公式中的自由变元，可以作代入，代入时需要对公式中出现该自由变元的每一处进行。即不能只替换其中一部分，必须保持一致性。02.新名选择用以代入的变元，其符号名称必须是“全新”的，与原公式中所有变元的名称不能相同。目的是为了避免变元冲突，保证公式语义的准确性。💡核心思想总结自由变元的代入本质上是对公式中该变元所有“自由出现”位置的一次统一替换，且必须保证替换后的变元符号不与公式中任何其他符号冲突。定义2.11：闭式(ClosedFormula)💡核心定义设A是任一公式，若A中无自由出现的个体变元，则称A为封闭的合式公式，简称“闭式”。关键点解析✦本质特征

一个完全“自给自足”的谓词公式，公式中所有个体变元均被量词约束，不存在“自由变元”。✦逻辑性质

闭式的真值不再依赖于对自由变元的赋值。因此，闭式在任何解释下，都能确定唯一的真假值，即它本身就是一个命题。示例辨析✅闭式(Closed)•(∀x)(P(x)→R(x))

•(∃x)(∀y)(P(x)∧R(x,y))❌非闭式(Open)•(∀x)(P(x)→R(x,y))

[变量y未被任何量词约束]例题2.13：自由变元的代入实践原始公式：(∃x)(P(y)∧R(x,y))任务：对公式中的自由变元y施行代入操作正确代入示范将自由变元y统一替换为z(一个在原公式中未出现的新变元)，以避免与约束变元混淆。(∃x)(P(z)∧R(x,z))常见错误警示❌冲突代入：(∃x)(P(x)∧R(x,x))

错误原因：代入变元x与公式中已有的约束变元x同名，导致“混淆”。❌代入不彻底：(∃x)(P(z)∧R(x,y))

错误原因：没有对原公式中所有出现自由变元y的地方进行统一替换。有限论域中的量词等价式前提设定：设所讨论的论域（DomainofDiscourse）为有限集合：{a₁,a₂,...,aₙ}，即包含有限个元素的非空集合。全称量词展开(Universal)(∀x)A(x)⇔A(a₁)∧A(a₂)∧...∧A(aₙ)含义：对于论域中的所有个体x，谓词A(x)为真，当且仅当论域中每一个元素的性质A(aᵢ)同时成立。即：全称量词等价于对所有元素进行“逻辑与(AND)”操作。存在量词展开(Existential)(∃x)A(x)⇔A(a₁)∨A(a₂)∨...∨A(aₙ)含义：论域中存在至少一个个体x使得A(x)为真，当且仅当论域中至少有一个元素的性质A(aᵢ)成立。即：存在量词等价于对所有元素进行“逻辑或(OR)”操作。量词顺序的重要性核心观点：量词对变元的约束，往往与量词的出现顺序有关。量词次序不能随意颠倒，否则将与原题的逻辑意义完全不符。(∀y)(∃x)(x<(y-2))含义：对于任何实数y，都能找到一个对应的实数x，使得x小于y减2。✅在实数域上成立(∃x)(∀y)(x<(y-2))含义：存在一个固定的实数x，无论y取任何实数，x永远小于y减2。❌在实数域上不成立本节核心要点回顾核心概念·指导变元：量词后紧跟的变元。·辖域：量词作用的范围。·约束变元：在辖域内被量词约