谓词逻辑.docx
- 文档编号:12607032
- 上传时间:2023-06-06
- 格式:DOCX
- 页数:11
- 大小:443.90KB
谓词逻辑.docx
《谓词逻辑.docx》由会员分享,可在线阅读,更多相关《谓词逻辑.docx(11页珍藏版)》请在冰点文库上搜索。
谓词逻辑
定义3.2.1可以独立存在的物体称为个体。
∙定义3.2.2设D是非空个体名称集合,定义在Dn上取值于{1,0}上的n元函数,称为n元命题函数或n元谓词。
其中Dn表示集合D的n次笛卡尔乘积。
二元或多元谓词描述两个或多个个体间的关系。
∙例令G(x,y):
“x高于y”,
∙G(x,y)是一个二元谓词。
将x代以个体“张三”,y代以个体“李四”,则G(张三,李四)就是命题:
“张三高于李四”。
∙G(x,y)不是命题,而是一个命题函数即谓词。
随便将x,y代以确定的个体,由G(x,y)都能得到一个命题。
.D={2,3,4}
◆设P(x):
x大于3,则P(x)为一元谓词。
指定元素--命题:
P
(2)=0,P(3)=0,P(4)=1
◆设P(x,y):
x大于y,则P(x,y)为二元谓词。
指定元素--命题:
P(2,3)=0,P(4,2)=1
◆设P(x,y,z):
若x+y-1=z,则P(x,y,z)为1,否则为0。
则P(x,y,z)为三元谓词。
指定元素--命题:
P(2,3,4)=1,P(4,2,2)=0
语句“对任意x”称为全称量词,记以x;语句“存在一个x”称为存在量词,记以x
5)每个人都会犯错误,R(x):
x是人,P(x):
x会犯错误,x(R(x)→P(x))
语义上,当D={x0,x1,…}是可数集合时,
xG(x)等价于G(x0)G(x1)…
xG(x)等价于G(x0)G(x1)…
设个体域D={1,2,3},P(x):
x>2。
试判断下列公式的真值:
(1)xP(x)P
(2);
(2)P(3)xP(x).
解:
(1)xP(x)P
(2)
等价于(P
(1)P
(2)P(3))P
(2)
所以真值为(001)0
=10
=0
(2)P(3)xP(x)
等价于1(P
(1)P
(2)P(3))
所以真值为1(001)
=10
=0
x(P(x,y)Q(x,z))R(x)从左向右算起,变量x的第一,第二次出现是约束的,第三次出现是自由的;变量y,z的出现是自由的。
∙对于x(P(x,y)Q(x,z))R(x,v),
∙可改名为u(P(u,y)Q(u,z))R(x,v)。
∙但下面的改名都是不对的:
a.u(P(u,y)Q(x,z))R(x,v)
b.x(P(u,y)Q(u,z))R(x,v)
c.u(P(x,y)Q(x,z))R(x,v)
d.y(P(y,y)Q(y,z))R(x,v)
e.z(P(z,y)Q(z,z))R(x,v)
∙定义3.2.9谓词逻辑中公式G的一个解释I,是由非空区域D和对G中常量符号,函数符号,谓词符号以下列规则进行的一组指定组成:
1.对每个常量符号,指定D中一个元素;
2.对每个n元函数符号,指定一个函数,即指定Dn到D的一个映射;
3.对每个n元谓词符号,指定一个谓词,即指定Dn到{0,1}的一个映射。
TI(G)=TI((P(f
(2))Q(2,f
(2)))(P(f(3))Q(3,f
(2))))
=TI((P(3)Q(2,3))(P
(2)Q(3,3)))
=(11)(01)=1
TI(H)=TI(P
(2)Q(2,2)P(3)Q(3,2))=0
∙使用量词时应注意以下几个问题:
(1)量词的论域D,即D中都有哪些元素
(2)在多重量词时,应注意量词的顺序(重点)
⏹xyP(x,y)≠yxP(x,y)
例.I:
D={2,3,4},P(x,y):
x=y
TI(xyP(x,y))
=TI(x(yP(x,y)))
=TI(yP(2,y)yP(3,y)yP(4,y))
=TI((P(2,2)P(2,3)P(2,4))
(P(3,2)P(3,3)P(3,4))
(P(4,2)P(4,3)P(4,4)))
=111=1
TI(yxP(x,y))
=TI(y(xP(x,y)))
=TI(xP(x,2)xP(x,3)xP(x,4))
=TI((P(2,2)P(3,2)P(4,2))
(P(2,3)P(3,3)P(4,3))
(P(2,4)P(3,4)P(4,4)))
=000=0
∙例.设个体域D为实数集合,P(x,y)表示x xyP(x,y)表示对任意一个实数x,都存在实数y,使得x yxP(x,y)表示存在一个实数y,对任意实数x,都有x (3)注意量词的作用范围 例.设个体域为D,P(x)为D上任意一个谓词 (1)判断x(P(x)P(a))和xP(x)P(a)是否等价 (2)判断x(P(x)P(a))和xP(x)P(a)是否等价 解: (1)任取解释I, 若P(a)在I下为真,则xP(x)P(a)在I下为真; 若P(a)在I下为假,则xP(x)在I下为假,故xP(x)P(a)在I下为真. 因此,xP(x)→P(a)是恒真公式. (2)任取解释I,由P(a)P(a)为真,知,存在xD,使得P(x)P(a)为真,即 x(P(x)P(a))为真。 因此,x(P(x)P(a))为恒真公式。 而xP(x)P(a)不是恒真公式。 对于解释I, 若xP(x)在I下为0,则xP(x)P(a)在I下为1。 若xP(x)在I下为1,则如果P(a)在I下为1,则 xP(x)P(a)在I下为1,否则如果P(a)在I下为0, 则xP(x)P(a)在I下为0。 比如,对于 (1)中给出的解释I, TI(xP(x)P(a)) =TI((P (1)P (2))P (1)) =(01)0 =0 因此,x(P(x)P(a))和xP(x)P(a)不等价。 谓词公式的恒真,恒假,可满足 例.设G=xP(x)P(a),则G是恒假公式。 证明: 对G的任意解释I, Ø若TI(P(a))=1,则TI(P(a))=0,故 TI(xP(x)P(a))=0 Ø若TI(P(a))=0,则TI(xP(x))=0,故 TI(xP(x)P(a))=0 因此,G是恒假公式。 例.设G=xP(x)→xP(x),则G是恒真公式。 证明: 对G的任意解释I, Ø若TI(xP(x))=1,则至少有x0D,使得TI(P(x0))=1,故TI(xP(x))=1,因此,TI(xP(x)→xP(x))=1。 Ø若TI(xP(x))=0,则 TI(xP(x)→xP(x))=1 因此,G是恒真公式。 D集合包含两个为宜 ∙例.设G=x(A(x)B(x)), H=xA(x)xB(x) 证明: GH 证明: 设I是满足G的任意一个解释。 若TI(xA(x))=0,则TI(xA(x)xB(x))=1; 若TI(xA(x))=1,则在I下对任意xD,有 TI(A(x))=1, 又由TI(x(A(x)B(x)))=1知,对 任意xD,TI(A(x)B(x))=1,故 TI(B(x))=1,即,TI(x(B(x)))=1, 因此,TI(xA(x)xB(x))=1。 ∙例.令G1=x(H(x)M(x)),G2=H(a), H=M(a) 证明: H是G1G2的逻辑结果。 证明: 设I是G1,G2,H的一个解释,且I满足G1G2,即I满足 x(H(x)M(x))H(a) 则I应该满足M(a)。 否则,令M(a)在I下为假,而H(a)在I下为真,于是H(a)M(a)在I下为假,故x(H(x)M(x))在I下为假,矛盾。 故M(a)在I下为真命题。 谓词公式蕴涵的证明方法 方法一.证明AB是恒真公式。 方法二.由基本等价式和基本蕴涵式推导出AB。 常用的基本蕴涵式有: x(A(x)B(x))(xA(x)x(B(x))(a) (xA(x)xB(x))x(A(x)B(x))(b) x(A(x)B(x))xA(x)xB(x)(c) 方法三.任取解释I,若I满足A,往证I满足B。 方法四.证BA。 例.证明下列蕴涵式,其中A(x),B(x)表示含自由变量x的公式。 (1)xy(A(x)B(y))xA(x); (2)(xA(x)xB(x))x(A(x)B(x)); (3)x(A(x)B(x))xA(x)xB(x)。 证明: (1)使用方法一。 证明xy(A(x)B(x))xA(x)是恒真公式。 xy(A(x)B(y))xA(x) =xA(x)yB(y)xA(x)(引理3.2.1) =xA(x)yB(y)xA(x) =(xA(x)xA(x))yB(y) =1yB(y) =1 因此,xy(A(x)B(y))xA(x)。 引理3.2.1 (2)(xA(x)xB(x))x(A(x)B(x));使用方法二。 (xA(x)xB(x)) =xA(x)xB(x) =x(A(x))xB(x)(引理3.2.1) 由基本蕴涵式(b)知, x(A(x))xB(x)x(A(x)B(x)), 而x(A(x)B(x))=x(A(x)B(x))。 因此,(xA(x)xB(x))x(A(x)B(x)) 范式 ∙定义3.2.14谓词逻辑中公式G称为前束范式,如果G有如下形状: Q1x1…QnxnM 其中Qixi或者是xi,或者是xi,i=1,…,n,M是不含量词的公式,Q1x1…Qnxn称为首标,M称为母式。 例如,xyz(P(x,y)Q(x,z)),xyzP(x,y,z) ∙对任意谓词公式,量词是不能随便提前的。 如前面的例子: xP(x)P(a)≠x(P(x)P(a)) xP(x)P(a)≠x(P(x)P(a)) ∙设G是公式,其中自由变量有且仅有一个x, 记以G(x),H是不含变量x的公式,于是有: 3)(xG(x))=x(G(x)) 4)(xG(x))=x(G(x)) ∙公式的前束范式化: 引理3.2.2设G,H是两个公式,其中自由变量有且只有一个x,分别记以G(x), 3)xG(x)xH(x)=xy(G(x)H(y))4)xG(x)xH(x)=xy(G(x)H(y)) ∙? xG(x)xH(x)=x(G(x)H(x)) ∙? xG(x)xH(x)x(G(x)H(x)) √ ∙? x(G(x)H(x))xG(x)xH(x) × ∙? xG(x)xH(x)=x(G(x)H(x)) ∙? x(G(x)H(x))xG(x)xH(x) √ ∙? xG(x)xH(x)x(G(x)H(x)) × 使用基本等价式(KH)=(KH)(HK),(KH)=KH可将公式G中的和删除 xy(z(P(x,z)P(y,z))uQ(x,y,u)) =xy((z(P(x,z)P(y,z)))uQ(x,y,u)) =xy(z(P(x,z)P(y,z))uQ(x,y,u)) =xyz(P(x,z)P(y,z)uQ(x,y,u)) =xyzu(P(x,z)P(y,z)Q(x,y,u)) 由于不能放在全式的前面,故经常使用基本等价式(xG(x))=x(G(x))和(xG(x))=x(G(x))。 例.将公式xy(A(x)B(x,y))(yC(y)zD(z)) 化为前束范式。 解: (1)消去联结词。 xy(A(x)B(x,y))(yC(y)zD(z)) =xy(A(x)B(x,y))(yC(y)zD(z)) (2)将公式中所有否定号放在原子之前。 xy(A(x)B(x,y))(yC(y)zD(z)) =xy(A(x)B(x,y))(yC(y)zD(z)) (3)将约束变量改名。 xy(A(x)B(x,y))(yC(y)zD(z)) =xy(A(x)B(x,y))(tC(t)zD(z)) (4)将量词提到整个公式前。 xy(A(x)B(x,y))(tC(t)zD(z)) =xytz((A(x)B(x,y))C(t)D(z)) =xytz((A(x)C(t)D(z))(B(x,y)C(t)D(z))) 对首标中的所有存在量词做上述处理后,得到一个在首标中没有存在量词的前束范式,这个前束范式就称为公式G的Skolem范式。 ∙G=xyzuvwP(x,y,z,u,v,w) 用a代替x, 用f(y,z)代替u, 用g(y,z,v)代替w, 得公式G的Skolem范式: yzvP(a,y,z,f(y,z),v,g(y,z,v)) G与S的可满足性是等价的->当G是可满足的,S也是可满足的 两者并不等价。 例如,G=xP(x),S=P(a)。 令G和S的解释I如下: D={2,3}, AP (2)P(3) 201 则I满足G,但I弄假S。 现在I还不是S的解释,因为有函数符号f(x)没有指定,扩充I为I’,使其包括对f(x)的指定: 有多个扩充的选择,我们只选择扩充后使S为真的那个扩充。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 谓词 逻辑