离散数学第二章谓词逻辑-4-6节

《离散数学第二章谓词逻辑-4-6节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2-4变元的约束一、指导变元、辖域、约束出现、自由出现辖域：紧接在量词后面的谓词公式，即量词的作用范围称之为量词的作用域或辖域。指出下列公式中各量词的辖域(x)(y)(z)(A(x,y)→B(x,y,z))∧C(t)(x)的辖域(z)的辖域(y)的辖域量词辖域的确定方法：（1）若量词后有括号，则括号内的公式为该量词的辖域；（2）若量词后无括号，则与量词邻接的公式为该量词的辖域。如：(x)P(x,y)。（3）若多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。约束变元/指导变元/作用变元：在量词的辖域内，且在量词

2、后面出现的变元。约束出现：在(x)和(x)的辖域中，x的所有出现。自由变元：不受量词约束的变元。自由出现：A中不是约束出现的其他变元。量词约束变元辖域约束变元自由变元(x)P(x,y)例确定以下公式各量词的辖域以及各客体变量为自由变元还是约束变元。（1）(x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)P(x,y)、Q(y,z)中的x,y为约束变元，z为自由变元，R(x,y)中的x为约束变元，但y为自由变元。指导变元(y)的辖域(x)的辖域指导变元(x)的辖域约束变元约束变元自由变元约束变元自由变元对约束

3、变元和自由变元的说明(1)对约束变元用什么符号表示无关紧要。就是说(x)A(x)与yA(y)是一样的。这类似于计算积分与积分变元无关，即积分∫f(x)dx与∫f(y)dy相同。(2)一个谓词公式如果无自由变元，它就表示一个命题。例如：A(x)表示x是个大学生。(x)A(x)或者(y)A(x)就是命题，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。谓词公式中有自由变元，则为命题函数。对约束变元和自由变元的说明（续）3、P(x1,x2,…,xn)是n元谓词,有n个独立的自由变元。若对其中k个变元进行约束，则成为n-

4、k元谓词。若对n个变元进行约束即没有自由变量出现则成为0元谓词，即成为命题。例：(x)P(x,y,z)是二元谓词(y)(x)P(x,y,z)是一元谓词P(x,y,z)是三元谓词(y)(z)(x)P(x,y,z)是命题变元混淆指导变元(y)的辖域(x)的辖域指导变元(x)的辖域约束变元约束变元自由变元约束变元自由变元（1）(x)(y)(P(x,y)∨Q(y,z))∧(x)R(x,y)在一个公式中，某一个变元的出现即可以是自由的，又可以是约束的。为了使得我们的研究更方便，而不致引起混淆，同时为了使其式子给大家以一目

5、了然的结果，采用对客体变元更改名称，使得变元只以一种形式出现。约束变元自由变元二、约束变元换名和自由变元代入1、约束变元的换名规则：含义：对约束变元更改名称。改名的范围是：该变元在量词及该量词的辖域中的所有出现必须一起更改。改名的规则：改名时用的客体变元名称不能与该量词辖域内的其它变元名称相同。例如(x)(P(x)→Q(x,y))∨(R(x)∧A(x))x以两种形式出现。可以对约束变元x改名。(z)(P(z)→Q(z,y))∨(R(x)∧A(x))2、对自由变元的代入规则：含义：对自由变元更换名称。改名的范围是：对整个公式中出现该

6、自由变元的每一处进行更改。改名的规则：对该自由变元可用客体常量或用与原公式中所有客体变元不同的客体变元去更改。上例(x)(P(x)→Q(x,y))∨(R(x)∧A(x))对自由变元x作代入，改成(x)(P(x)→Q(x,y))∨(R(z)∧A(z))改名规则和代入规则的关系相同点：不改变约束关系。不同点：(1)实施对象不同换名规则是对约束变元实施的，代入规则是对自由变元实施的。(2)实施范围不同换名规则可对公式中一个量词及其作用域内实施，即只对公式的一个子公式实施；代入规则是整个公式的同一自由变元都实施。(3)实施后结果不同换名后

7、，公式含义不变，因为约束变元只改名为另一个客体变元，约束关系不改变，约束变元不能改名为客体常量；代入后，不仅可用另一个客体变元进行代入，并且也可用客体常量去代入，从而使公式由具有普遍意义变为仅对该客体常量有意义，即公式的含义改变了。例对以下公式分别利用换名和代入规则改写例(x)(A(x)∨B(x,y))∨C(x)∨D(x,w)换名：(x)(A(x)∨B(x，y))∨C(y)∨D(y,w)错(x)(A(x)∨B(x，y))∨C(w)∨D(w,w)错(x)(A(x)∨B(x，y))∨C(u)∨D(x,w)对代入：(y)(A(y)

8、∨B(y,y))∨C(x)∨D(x,w)(z)(A(z)∨B(z,y))∨C(x)∨D(x,w)(w)(A(w)∨B(w，y))∨C(x)∨D(x,w)错对对(x)(A(x)∨B(x，y))∨C(u)∨D(u,w)