第五章 一阶逻辑等值演算与推理.ppt

《第五章 一阶逻辑等值演算与推理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、复习变元的约束(Boundofvariable)在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))注意：(1)n元谓词公式A(x1，x2...xn)中有n个自由变元,若对其中的k(k≤n)个进行约束,则构成了n-k元谓词;如果一个公式中没有自由变元出现,则该公式就变成了一个命题(2)一个公式的约束变元

2、所使用的名称符号是无关紧要的,如(x)M(x)与(y)M(y)意义相同.约束变元的换名与自由变元的代入规则换名规则:(对约束变元而言）对约束变元进行换名,使得一个变元在一个公式中只呈一种形式出现.(1)约束变元可以换名,其更改的变元名称范围是量词中的指导变元以及该量词作用域中所出现的该变元,公式的其余部分不变.(2)换名时一定要更改为作用域中没有出现的变元名称.例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

3、(x,y,z)))换名为x(H(x,y)s(W(s)∧L(x,s,z)))代入规则（对自由变元而言）对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入,代入时需要对公式中出现该自由变元的每一处进行;(2)用以代入的变元与原公式中所有变元的名称不能相同.例如对例1中的公式x(P(x)R(x,y))∧L(x,y)自由变元y用z来代入,得x(P(x)R(x,z))∧L(x,z)习题1、在一阶逻辑中将下列命题符号化。（1）大熊猫都可爱。（2）有人爱发脾气。（3）说所有人都爱吃

4、面包是不对的。（4）没有不爱吃糖的人。（5） 一切人都不一样高。（6）并不是所有的汽车都比火车快。解：由于没指出个体域，故用全总个体域（1）大熊猫都可爱。设F(x):x为大熊猫，G(x):x可爱，命题符号化为x(F(x)G(x))（2）有人爱发脾气。设F(x):x是人，G(x):x爱发脾气，命题符号化为x(F(x)G(x))（3）说所有人都爱吃面包是不对的。设F(x):x是人，G(x):x爱吃面包，命题符号化为x(F(x)G(x))或x(F(x)G(x))（4）没有不爱吃糖的人。设

5、F(x):x是人，G(x):x爱吃糖，命题符号化为x(F(x)G(x))或x(F(x)G(x))（5）一切人都不一样高。设F(x):x是人,H(x,y)：x与y相同,L(x,y):x与y一样高，命题符号化为xy(F(x)F(y)H(x,y)L(x,y))或x(F(x)y(F(y)H(x,y)L(x,y)))（6）并不是所有的汽车都比火车快。设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快，命题符号化为xy(F(x)G(y)H(x,y))

6、或xy(F(x)G(y)H(x,y))2、在一阶逻辑中将下列命题符号化。（1）没有一个自然数大于等于任何自然数。（2）有唯一的偶素数。解：（1）N(x):x是自然数，G(x,y):xyx(N(x)y(N(y)G(x,y)))（2）Q(x):x是偶数，P(x):x是素数，E(x,y):x＝yx(Q(x)P(x)y(Q(y)P(y)E(x,y)))3、判断公式是否为永真公式。(xA(x)xB(x))x(A(x)B(x))解：不是永真公式。设个体域为{a,b

7、}，令A(a)=1,B(a)=0,A(b)=0,B(b)=1。小节结束第5章一阶逻辑等值演算与推理离散数学山东师范大学本科生课程信息科学与工程学院2008专升本本章说明本章的主要内容一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则前束范式一阶逻辑推理理论本章与其他各章的关系本章先行基础是前四章本章是集合论各章的先行基础本章主要内容5.1一阶逻辑等值式与置换规则5.2一阶逻辑前束范式5.3一阶逻辑的推理理论主要内容作业5.1一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的符号化形式。例如

8、：没有不犯错误的人令M(x):x是人。F(x):x犯错误。则将上述命题的符号化有以下两种正确形式：(1)┐x(M(x)∧┐F(x))(2)x(M(x)→F(x))我们称(1)和(2)是等值的。说明等值式的定义定义5.1设A，B是一阶逻辑中任意两个公式，若AB是永真式，则称A与B是等值的。记做AB，称AB是等值式。例如：判断公式A与B是否等值，等价于判断公式AB是否为永真式。谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。说明一阶逻辑