第10讲谓词逻辑等值式.ppt

《第10讲谓词逻辑等值式.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一阶逻辑的字母表个体常项:a,b,c,…,a1,b1,c1,…个体变项:x,y,z,…,x1,y1,z1,…函数符号:f,g,h,…,f1,g1,h1,…谓词符号:F,G,H,…,F1,G1,H1,…量词符号:,联结词符号:,,,,括号与逗号:(,),，2021/8/21一阶逻辑一阶(firstorder)逻辑的合式公式项原子公式合式公式2021/8/22一阶逻辑合式公式中的变项量词辖域:在xA,xA中,A是量词的辖域.例如:x(F(x)y(G(y)H(x,y)))指导变项:紧

2、跟在量词后面的个体变项.例如:x(F(x)y(G(y)H(x,y)))约束出现:在辖域中与指导变项同名的变项.例如:x(F(x)y(G(y)H(x,y)))自由出现:既非指导变项又非约束出现.例如:y(G(y)H(x,y))2021/8/23一阶逻辑解释(interpret)对一个合式公式的解释包括给出个体域谓词函数个体常项的具体含义2021/8/24一阶逻辑赋值(举例)F(f(a,a),b)赋值1：个体域是全体自然数;a:2;b:4;f(x,y)=x+y;F(x,y):x=y原公式

3、赋值成:“2+2=4”。赋值2：个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):x>y原公式赋值成:“3-3>5”。2021/8/25一阶逻辑一阶逻辑永真式(tautology)永真式:在各种解释下取值均为真(逻辑有效式)命题逻辑永真式:在各种解释下取值均为真(重言式)永假式:在各种解释下取值均为假(矛盾式)命题逻辑永假式:在各种解释下取值均为假(矛盾式)可满足式：非永假式2021/8/26一阶逻辑代换实例在含命题变项p1,p2,……,pn的命题公式中,每个命题变项代换成一阶逻辑公

4、式所得到的式子,称为原来公式的代换实例.例：F(x)→G(y)¬xF(x)∨G(y)2021/8/27一阶逻辑一阶逻辑公式分类例：xF(x)↔xF(x)xF(x)→(G(y)→xF(x))xF(x)→yG(y)(xF(x)→yG(y))yG(y)2021/8/28一阶逻辑命题符号化(举例)例:“不存在最大的自然数”。(论域取全体自然数)解:设:G(x,y):xy;原命题符号化成:xyG(y,x)或:xyG(y,x)2021/8/29一阶逻辑一阶逻辑等值式(定义)

5、等值：AB读作：A等值于B含义：A与B在各种赋值下取值均相等AB当且仅当A↔B是永真式例如：xF(x)xF(x)FF2021/8/210一阶逻辑一阶逻辑等值式(来源)命题逻辑等值式的代换实例与量词有关的有限个体域量词消去量词否定量词辖域收缩与扩张量词分配相同量词的交换与变项命名有关的换名规则代替规则2021/8/211一阶逻辑代换实例在命题逻辑等值式中,代入一阶逻辑公式所得到的式子,称为原来公式的代换实例.例1：AA,令A=xF(x),得到xF(x)xF(x)例2：A→

6、B¬A∨B,令A=F(x),B=G(y),得到F(x)→G(y)¬F(x)∨G(y)2021/8/212一阶逻辑有限个体域上消去量词设个体域为有限集D={a1,a2,…,an},则xA(x)A(a1)∧A(a2)∧…∧A(an)xA(x)A(a1)∨A(a2)∨…∨A(an)例:个体域D={a,b,c},则xyF(x,y)x(F(x,a)∧F(x,b)∧F(x,c))(F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c))∨(F(c,a)∧F(c,

7、b)∧F(c,c))2021/8/213一阶逻辑量词否定等值式xA(x)xA(x)xA(x)xA(x)AA2021/8/214一阶逻辑量词否定等值式(举例)Nn(n>N→

8、an-a

9、<)a1,a2,a3,…,aN,aN+1,aN+2,…,an,…?a2021/8/215一阶逻辑量词否定等值式(举例、续)Nn(n>N→

10、an-a

11、<)Nn(n>N→

12、an-a

13、<)Nn(n>N→

14、an-a

15、<)Nn(n>N→

16、

17、an-a

18、<)Nn(n>N∨

19、an-a

20、<)Nn(n>N∧

21、an-a

22、<)Nn(n>N∧

23、an-a

24、)2021/8/216一阶逻辑量词辖域收缩与扩张()x(A(x)∨B)xA(x)∨Bx(A(x)∧B)xA(x)∧B说明:B中不含x的出现例1:x(F(x)∨G(y))xF(x)∨G(y)例2:xy(F(x)∧G(y))x(F(x)∧yG(y))xF(x)∧yG