数理逻辑 课程
数理逻辑 课 程 V
第5章谓词逻辑的等值和推理演算 ■谓词逻辑研究的对象是重要的逻辑规律,普遍有效 式是最重要的逻辑规律,而等值式、推理式都是普 遍有效的谓词公式,因此等值和推理演算就成了谓 词逻辑的基本内容,同命题逻辑相比,由于量词谓 词的引入,使谓词演算有着广泛的应用.特别是计 算机科学、人工智能等领域,是把谓词逻辑当作表 示知识、实现推理的有力工具来看待的 这章的讨论,主要是以语义的观点进行的非形式的 描述,而严格的形式化的讨论见第6章所建立的公 理系统
第5章 谓词逻辑的等值和推理演算 谓词逻辑研究的对象是重要的逻辑规律，普遍有效 式是最重要的逻辑规律，而等值式、推理式都是普 遍有效的谓词公式，因此等值和推理演算就成了谓 词逻辑的基本内容，同命题逻辑相比，由于量词谓 词的引入，使谓词演算有着广泛的应用．特别是计 算机科学、人工智能等领域，是把谓词逻辑当作表 示知识、实现推理的有力工具来看待的． 这章的讨论，主要是以语义的观点进行的非形式的 描述，而严格的形式化的讨论见第6章所建立的公 理系统．
5.1否定型等值式 ■若给定了两个谓词公式A,B,说A和B是等值 的,如果在公式A,B的任一解释下,A和B都 有相同的真值 等价的说法是A,B等值当且仅当AB是普遍 有效的公式A和B等值.就记作A=B或AB
5．1 否定型等值式 若给定了两个谓词公式A，B，说A和B是等值 的，如果在公式A，B的任一解释下，A和B都 有相同的真值． 等价的说法是A，B等值当且仅当A↔B是普遍 有效的公式,A和B等值．就记作A＝B或AB
5.1.1由命题公式移植来的等值式 ■若将命题公式的等值式,直接以谓词公式代入命题变项便可 得谓词等值式.由 7-p=pp→q=-pVq,(p^q)Vr=(p∧(qvr) 可得 P()=P(X) (V×)P(x)=(V×)P(× P(×)→Q(×)=-P(×)vQ(×) (×)P(X)→→(×)Q(×)=-(V×)P(x)V(彐×)Q(×) (P(XAQ(X)VR(X=(P(XVR(X)A(Q(XVR(X)) Vx)P(x)AQ(y)v(2)R(z)=(×P(×)V(2)R(2)A(Q(y)V(日z) R(z)
5．1．1 由命题公式移植来的等值式 若将命题公式的等值式，直接以谓词公式代入命题变项便可 得谓词等值式．由 ﹁﹁p＝p,p→q=﹁p∨q, (p∧q)∨r=(p∨r)∧(q∨r) 可得 ﹁﹁P(x)＝P(x) ﹁﹁(x)P(x)＝(x)P(x) P(x)→Q(x)＝﹁P(x)∨Q(x) (x)P(x)→(x)Q(x)＝﹁ (x)P(x)∨(x)Q(x) (P(x)∧Q(x))∨R(x)=(P(x)∨R(x))∧(Q(x)∨R(x)) ((x)P(x)∧Q(y))∨(z)R(z)=((x)P(x)∨(z)R(z))∧(Q(y)∨(z) R(z))
5.1.2否定型等值式 (×)P()=(×)-P(×) (x)P(x)=(V×)-P(×) ■形式上看这对公式,是说否定词”-”可越过量词深 入到量词的辖域内,但要把所越过的量词∨转换为彐, 彐转换为∨
5．1．2 否定型等值式 ﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x) 形式上看这对公式，是说否定词”﹁ ”可越过量词深 入到量词的辖域内，但要把所越过的量词转换为， 转换为
(1)从语义上说明 (x)P(x)语义上表示的是,并非所有的x都具有性 质P.这相当于,有一个x不具有性质P,这正是 (x)-P(x)的含义.从而由语义分析知一(x)P(x) 与(彐x)→P(x)表示的是同一命题,自然有 (X)P(X)=(×)-P(× (X)P(×)=(×)-P(× 类似的有一(X)P(x)=(x)=P(x) (x)P(X)=-(X)-P(x)
(1)从语义上说明 ﹁(x)P(x)语义上表示的是，并非所有的x都具有性 质P．这相当于，有一个x不具有性质P，这正是 (x)﹁P(x)的含义．从而由语义分析知﹁(x)P(x) 与(x)﹁P(x)表示的是同一命题，自然有 ﹁(x)P(x)=(x)﹁P(x) (x)P(x)=﹁ (x)﹁P(x) 类似的有﹁(x)P(x)=(x)﹁P(x) (x)P(x)=﹁(x)﹁P(x)
而-(XP(x)与(x)P(x)不等值,如P(X)表示X是 有理数,前者的语义是并非所有的x都是有理 数.而后者的语义是说所有的x都不是有理数.这 两句话是不同的。 同样,一(x)P(X)与(彐x)-P(x)也不等值
而﹁(x)P(x)与(x)﹁P(x)不等值，如P(x)表示x是 有理数，前者的语义是并非所有的x都是有理 数．而后者的语义是说所有的x都不是有理数．这 两句话是不同的。 同样，﹁(x)P(x)与(x)﹁P(x)也不等值．
(2)在{,2}域上分析 (x)P(x)=-(P(1)4P(2)=-P(1)→P(2)=(X) P(X) (X)P(×)=-((1)vP(2)=P(1)^-P(2)=(y×) P(×) 这样看来,否定词越过量词的内移规律,就是摩根 律的推广
(2)在{l，2}域上分析 ﹁(x)P(x)=﹁(P(1)^P(2))=﹁P(1)v﹁P(2)=(x) ﹁ P(x) ﹁(x)P(x)=﹁(P(1)vP(2))=﹁P(1)^﹁P(2)=(x)﹁ P(x) 这样看来，否定词越过量词的内移规律，就是摩根 律的推广．
(3)语义上的证明 ■依等值式定义,A=B如果在任一解释丨下A真B就真,而且B 真A就真 若证明一(×)P(xX)=(×)-P(X 设任一解释|下有(Vx)P(×)=T 从而(x)P(X)=F,即有一个X∈D,使P(X)=F 于是一P(X)=T 故在下(彐x)P(x)=T 反过来,设任一解释下有(x)-P(x)=T 即有一个X∈D,使一P(X。)=T 从而P(X)=F 于是(vx)P(x)=F 即一(Vx)P(x)=T
(3)语义上的证明 依等值式定义，A=B如果在任一解释I下A真B就真，而且B 真A就真． 若证明﹁(x)P(x)=(x)﹁P(x) 设任—解释I下有﹁(x)P(x)=T 从而(x)P(x)=F，即有一个xoD,使P(Xo )=F 于是﹁P(xo )=T 故在I下(x)﹁P(x)=T 反过来，设任—解释I下有 (x) ﹁P(x)=T 即有一个xoD,使﹁P(Xo )=T 从而P(Xo )=F 于是(x) P(x)=F 即﹁ (x)P(x)=T
(4)举例 例1“并非所有的动物都是猫”的表示 设A(x):x是动物 B(x):X是描 原语句可表示成-(Vx)(A(x)→>B(x) 依否定型公式得 (Vx)(A(x)→B(x)) (彐x)-(A(x)→B(x)) =(x)(A(x)VB(x)) (彐x)(A(x)∧=B(x)) 而(x)(A(x)AB(x))的含义是有一个动物不是猫,显然这句话与原语句等同
(4)举例 例1 “并非所有的动物都是猫”的表示 设 A(x)：x是动物 B(x)：x是描 原语句可表示成﹁(x)(A(x)→B(x)) 依否定型公式得