天津理工大学：《离散数学》课程教学资源（PPT课件）第二章 谓词逻辑 Predicate Logic 2.4 变元的约束（Bound of variable）

第二章谓词逻辑（Predicate Logic)变元的约束（Boundofvariable)定义2.5:在谓词公式中,形如VxP(x)或日xP(x)中的x叫做量词的指导变项，P(x)称为相应量词的作用域或辖域。在Vx和x的辖域中，x的所有出现都称为约束出现，相应的x称为约束变元；P（x）中除约束变元以外出现的变元称为是自由变元例l: 1、Vx(H(x,y)→>3y(W(y) ^ L(x, y, z)))2、 Vx(H(x)→W(y))→y(F(x) ^L(x, y, z))2026/3/151计算机科学与工程系

2026/3/15 计算机科学与工程系 1 第二章 谓词逻辑（Predicate Logic） 变元的约束(Bound of variable) 定义2.5:在谓词公式中,形如xP(x)或xP(x)中 的x叫做量词的指导变项，P(x)称为相应量词的作用域 或辖域。 在x和x的辖域中，x的所有出现都称为约束出现，相 应的x称为约束变元; P(x)中除约束变元以外出现的变 元称为是自由变元。 例1： 1、x( H(x,y)→y(W(y) ∧ L(x,y,z))) 2、 x( H(x)→W(y))→ y( F(x) ∧L(x,y,z))

第二章谓词逻辑（PredicateLogic）■说明：(1)n元谓词公式A(X1.X2.Xn）中有n个自由变元若对其中的k(k≤n)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现，则该公式就变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关紧要的,如(Vx)M(x)与(Vy)M(y)意义相同2026/3/152计算机科学与工程系

2026/3/15 计算机科学与工程系 2 第二章 谓词逻辑（Predicate Logic） ◼ 说明: (1)n元谓词公式A(x1， x2 .xn ) 中有n个自由变元, 若对其中的k(k≤n)个进行约束,则构成了n-k元 谓词;如果一个公式中没有自由变元出现,则该公 式就变成了一个命题 (2)一个公式的约束变元所使用的名称符号是无关 紧要的,如(x)M(x)与(y)M(y)意义相同

定义设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的合式公式，简称闭式。2026/3/153计算机科学与工程系

2026/3/15 计算机科学与工程系 3 定义 设A为任一公式，若A中无 自由出现的个体变项，则称A是 封闭的合式公式，简称闭式

第二章谓词逻辑（PredicateLogic）变元的约束(Boundofvariable）约束变元的换名与自由变元的代入规则一个变元在同一个公式中既是自由出现是约束出现,这样在理解上容易发生混淆.为了避免这种混乱，可对约束变元进行换名换名规则日（对约束变元而言(1)将量词辖域中某个约束出现的个体变项及对应的指导变项，改成公式中未曾出现过的个体变项符号，公式中其余部分不变2026/3/154计算机科学与工程系

2026/3/15 计算机科学与工程系 4 第二章 谓词逻辑（Predicate Logic） 变元的约束(Bound of variable) ◼ 约束变元的换名与自由变元的代入规则 一个变元在同一个公式中既是自由出现又是约束 出现,这样在理解上容易发生混淆.为了避免这种 混乱,可对约束变元进行换名. 换名规则: (对约束变元而言） (1)将量词辖域中某个约束出现的个体变项及对应 的指导变项，改成公式中未曾出现过的个体变 项符号，公式中其余部分不变

第二章谓词逻辑（PredicateLogic）2.4变元的约束（Boundofvariable 例1: Vx(P(x)-→R(x, y)) ^L(x, y)换名为Vt(P(t)→R(t,y)) ^L(x,y) Vx(H(x, y)→3y(W(y) ^ L(x, y, z)))换名为Vx(H(x,y)→s(W(s) ^ L(x, S,z)))2026/3/155计算机科学与工程系

2026/3/15 计算机科学与工程系 5 第二章 谓词逻辑（Predicate Logic） 2.4变元的约束(Bound of variable) ◼ 例1: x( P(x)→R(x,y))∧L(x,y) 换名为t( P(t)→R(t,y))∧ L(x,y) ◼ x( H(x,y)→y(W(y) ∧ L(x,y,z))) 换名为x( H(x,y)→s(W(s) ∧ L(x,s,z)))

第二章谓词逻辑（PredicateLogic）谓词演算的等价式与蕴含式■代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行(2)用以代入的变元与原公式中所有变元的名称不能相同例如对例1中的公式Vx(P(x)→R(x,y)）^L(x,y)自由变元y用z来代入，得Vx(P(x)→R(x, z)) ^L(x,z)2026/3/156计算机科学与工程系

2026/3/15 计算机科学与工程系 6 第二章 谓词逻辑（Predicate Logic） 谓词演算的等价式与蕴含式 ◼ 代入规则（对自由变元而言） 对公式中自由变元的更改称为代入 (1)对于谓词公式中的自由变元可以作代入,代入 时需要对公式中出现该自由变元的每一处进行; (2)用以代入的变元与原公式中所有变元的名称不 能相同. 例如对例1中的公式x( P(x)→R(x,y))∧L(x,y) 自由变元y用z来代入,得 x( P(x)→R(x,z))∧L(x,z)