《离散数学-2-4变元的约束.ppt》由会员分享，可在线阅读，更多相关《离散数学-2-4变元的约束.ppt（22页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章谓词逻辑2-4 变元的约束授课人：李朔1一、基本概念在给定的一个合式公式x(A)或x(A)中n称x为指导变元或作用变元指导变元或作用变元。n称A为相应量词的辖域或作用域为相应量词的辖域或作用域，在辖域辖域中中x的所有出现称为约束的的所有出现称为约束的。nA中不是约束出现的变元称自由变元自由变元。n自由变元有时也在量词的作用域中出现，但它不受相应量词中指导变元的约束，故可把自由可把自由变元看成公式中的参数变元看成公式中的参数。2一、基本概念例：指出下列各公式中指导变元、量词辖域、自由变元和约束变元。1）x(F(x)yH（x,y）)；2）x F(x)G（x,y）；3）x y（R(x,y)L(
2、y,z)）x H(x,y)。3一、基本概念例：指出下列各公式中指导变元、量词辖域、自由变元和约束变元。1）x(F(x)yH（x,y）)；2）x F(x)G（x,y）；3）x y（R(x,y)L(y,z)）x H(x,y)。解：（1）yH（x,y）中，y为约束变元，辖域为H(x,y)，其中y为约 束出现，x是自由出现。在整个公式中，x为指导变元，x的辖域为（F(x)y H（x,y），x,y都是约束出现。（2）在x F(x)中，x辖域为F(x)，x为约束出现 G（x,y）中，x,y都是自由出现。在整个公式中，x约束出现一次，自由出现一次，y自由出现。（3）可以类似分析，x为约束出现，y既约束出现，
3、又自由出现。z是自由出现。4一、基本概念从约束变元的概念可见，若P（x1,xn）是有n个独立自由变元的n元谓词，若对其中k个变元进行约束，则变为n-k元谓词。例如：nx P（x,y,z）是二元谓词。nyx P（x,y,z）是一元谓词。为了避免由于变元的约束与自由同时出现，引起概念上的混乱，可对约束变元进行换名，使得一个变元在一个公式中仅以一种形式出现。为避免混乱，采用下面二条规则。5二、换名规则换名规则 一个公式中的约束变元所使用的名称符号是无关紧要的。x P(x)与y P(y)具有相同的意义。换名规则换名规则：将量词辖域中出现的某个约束出现的个体变元及其指导变元，改换成另一个辖域中未曾出现过
4、的个体符号，公式中其余部分符号不变。6二、换名规则换名规则例2：对 x P(（x）R（x,y）Q（x,y）换名。可换为：z（P(z)R(z,y)）Q(x,y)。注：n（1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。n（2）换名时一定要为作用域中没有出现过的变元名称。*最好是公式中没有的变元名。7三、代入规则三、代入规则对公式中的自由变元也允许更改，这种更改叫做代入。代入规则代入规则：对于某自由出现的个体变元用与原公式中所有个体变元符号不同的变元符号去代替，且处处代替。例3：对x(P（y）R（x,y）)进行代替。解：对y
5、施行代替后公式为：x(P（z）R（x,z）)8三、代入规则三、代入规则注：注：n（1）对于自由变元可以代入，代入时需对公式中出现该自由变元的每一处进行代入。n（2）用以代入的变元与原公式中的所有变元的名称不能相同。9四、练习1.说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)10四、练习1.说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)的辖域为的辖域为P(x)，x是约束变元，是约束变元，y是自由变
6、是自由变元元 (x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)11四、练习1.说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)的辖域为的辖域为P(x)(y)Q(x,y)，(y)的辖域为的辖域为Q(x,y)，x和和y都是约束变元，无自由变元。都是约束变元，无自由变元。(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)12四、练习1.说明下列各式量词的辖域，找出约束变元和自由
7、变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)的的辖辖域域为为P(x)，(y)的的辖辖域域为为Q(x,y)，P(x)中中的的x和和Q(x,y)中中的的y是是约约束束变变元元，Q(x,y)中中的的x是是自自由变元。由变元。(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)13四、练习1.说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)的的辖辖域域为为(y)(P(x
8、,y)Q(y,z)，(y)的的辖辖域域为为P(x,y)Q(y,z)，(x)的的辖辖域域为为R(x,y)，x是是约约束束变变元元，z是是自自由由变变元元，(P(x,y)Q(y,z)中中的的y是是约约束束变变元，元，R(x,y)中的中的y是自由变元。是自由变元。(x)P(x)R(x,y)14四、练习1.说明下列各式量词的辖域，找出约束变元和自由变元。(x)P(x)Q(y)(x)(P(x)(y)Q(x,y)(x)P(x)(y)Q(x,y)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)(x)P(x)R(x,y)(x)的的辖辖域域为为P(x)，y是是自自由由变变元元，P(x)中中x是是约约束束
9、变元，变元，R(x,y)中中x是自由变元。是自由变元。15四、练习由1.可知在一个公式中，同一个变元既可以是约束的，又可以是自由的，容易混淆。因为(x)P(x)与(y)P(y)，(x)P(x)与(y)P(y)都具有相同意义，所以约束变元与表示该变元的符号无关。根据这个特点，可以对约束变元换名。n可应用换名规则使换名后的公式中出现的变元要么是约束的，要么是自由的n也可应用代入规则,对自由变量换名。16四、练习2.对下面公式中的约束变元y换名。(x)(y)(P(x,y)Q(y,z)(x)R(x,y)17四、练习2.对下面公式中的约束变元y换名。(x)(y)(P(x,y)Q(y,z)(x)R(x,y
10、)解：用u置换约束变元y。换名后为：(x)(u)(P(x,u)Q(u,z)(x)R(x,y)注：不能换成：(x)(u)(P(x,u)Q(y,z)(x)R(x,y)(部分替换)也不能换成：(x)(z)(P(x,z)Q(z,z)(x)R(x,y)(与自由变元同名)18四、练习3.对以下公式中的自由变元y进行代入。(x)(P(y)R(x,y)(y)Q(y)19四、练习3.对以下公式中的自由变元y进行代入。(x)(P(y)R(x,y)(y)Q(y)解：用z代换y，代入后为：(x)(P(z)R(x,z)(y)Q(y)注：不能换成:(x)(P(x)R(x,x)(y)Q(y)(与约束变元x同名)或 (x)(P(z)R(x,y)(y)Q(y)(部分替换)需要指出：P6520本课小结基本概念:指导变元或作用变元、辖域或作用域约束变元、自由变元。21作业P65（3）22