上海交通大学：《离散数学》课程教学资源（PPT课件）第5章 谓词逻辑的等值和推理演算

第5章 谓词逻辑的等值和推理演 算 谓词逻辑研究的对象是重要的逻辑规律，普遍 有效式是最重要的逻辑规律，而等值式、推理 式都是普遍有效的谓词公式，因此等值和推理 演算就成了谓词逻辑的基本内容，同命题逻辑 相比，由于量词谓词的引入，使谓词演算有着 广泛的应用.特别是计算机科学、人工智能等 领域，是把谓词逻辑当作表示知识、实现推理 的有力工具来看待的. 这章的讨论，主要是以语义的观点进行的非形 式的描述，而严格的形式化的讨论见第6章所 建立的公理系统

第5章 谓词逻辑的等值和推理演 算 n 谓词逻辑研究的对象是重要的逻辑规律，普遍 有效式是最重要的逻辑规律，而等值式、推理 式都是普遍有效的谓词公式，因此等值和推理 演算就成了谓词逻辑的基本内容，同命题逻辑 相比，由于量词谓词的引入，使谓词演算有着 广泛的应用．特别是计算机科学、人工智能等 领域，是把谓词逻辑当作表示知识、实现推理 的有力工具来看待的． n 这章的讨论，主要是以语义的观点进行的非形 式的描述，而严格的形式化的讨论见第6章所 建立的公理系统．

5.1否定型等值式 若给定了两个谓词公式A,B,说A和B是 等值的，如果在公式A,B的任一解释下， A和B都有相同的真值 等价的说法是A,B等值当且仅当A→B是 普遍有效的公式，A和B等值.就记作A=B 或A一B

5．1 否定型等值式 n 若给定了两个谓词公式A，B，说A和B是 等值的，如果在公式A，B的任一解释下， A和B都有相同的真值． n 等价的说法是A，B等值当且仅当A↔B是 普遍有效的公式,A和B等值．就记作A＝B 或AB

5.1.1 由命题公式移植来的等值式 若将命题公式的等值式，直接以谓词公式代入命题变项便可 得谓词等值式.由 -p=pP→q=pVq,(p∧q)Vr=(pVr)∧(qVr) 可得 一-P(X)=P(X) 一(X)P(X)=(X)P(X) P(x)-Q(x)=-P(x)VQ(x) (Vx)P(x)x)Q(x)=-(Vx)P(x)Vx)Q(x) (P(x)AQ(x))VR(x)=(P(x)VR(x))A(Q(x)VR(x)) ((Vx)P(x)AQ(y))V(z)R(z)=((Vx)P(x)V(z)R(z))A(Q(y)V (3z)R(Z)

5．1．1 由命题公式移植来的等值式 n 若将命题公式的等值式，直接以谓词公式代入命题变项便可 得谓词等值式．由 ﹁﹁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否定型等值式 一(X)P(X)=(3x)P(X) 一(3x)P(X)=(x)一P(x) ■形式上看这对公式，是说否定词”一”可越过 量词深入到量词的辖域内，但要把所越过的量 词V转换为]，彐转换为V

5．1．2 否定型等值式 ﹁(x)P(x)=(x)﹁P(x) ﹁(x)P(x)=(x)﹁P(x) n 形式上看这对公式，是说否定词” ﹁ ”可越过 量词深入到量词的辖域内，但要把所越过的量 词转换为，转换为

(1)从语义上说明 一(x)P(X)语义上表示的是，并非所有的x都具有性质 P.这相当于，有一个不具有性质P,这正是 (臼x)一P(X)的含义.从而由语义分析知一(X)P(X) 与（妇x)一P(X)表示的是同一命题，自然有 一(X)P(X)=(3x)-P(X) (x)P(x)=一(3x)-P(X) 类似的有一(3x)P(X)=(x)一P(X) (3xX)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)

而一(X)P(X)与(X)一P(X)不等值，如P(X)表 示X是有理数，前者的语义是并非所有的x都是 有理数.而后者的语义是说所有的x都不是有 理数.这两句话是不同的。 ■同样，一(3x)P(x)与(3x)一P()也不等值

n 而﹁(x)P(x)与(x)﹁P(x)不等值，如P(x)表 示x是有理数，前者的语义是并非所有的x都是 有理数．而后者的语义是说所有的x都不是有 理数．这两句话是不同的。 n 同样，﹁(x)P(x)与(x)﹁P(x)也不等值．

(2)在I,2}域上分析 (X)P(X)=(P(1)NP(2)=-P(1)N一 P(2)=(3x)一P(X) -(3x)P(X)=-(P(1)P(2)=一P(1)^一 P(2)=(X)-P(X) ■这样看来，否定词越过量词的内移规律，就是 摩根律的推广

(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) n 这样看来，否定词越过量词的内移规律，就是 摩根律的推广．

(3)语义上的证明 依等值式定义，A=B如果在任一解释I下A真B就真，而 且B真A就真. 若证明一(X)P(X)=(3x)一P(X) 设任一解释I下有一(x)P(x)=T 从而(X)P(X)=F,即有一个x∈D,使P(X)=F 于是P(X)=T 故在I下(3x)一P(X)=T 反过来，设任一解释I下有(x)一P(X)=T 即有一个X∈D,使P(X)=T 从而P(X)=F 于是(X)P(X)=F 即一(X)P(X)=T

(3)语义上的证明 n 依等值式定义，A=B如果在任一解释I下A真B就真，而 且B真A就真． 若证明﹁(x)P(x)=(x)﹁P(x) 设任—解释I下有﹁(x)P(x)=T 从而(x)P(x)=F，即有一个xoD,使P(Xo)=F 于是﹁P(xo)=T 故在I下(x)﹁P(x)=T 反过来，设任—解释I下有 (x) ﹁P(x)=T 即有一个xoD,使﹁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)) (Hx)(A(x)→B(x)) =(3x)(A(x)*B(x)) =(3x)(A(x)VB(x)) =(3x)(A(x)∧-B(x)) 而（臼x)(A(x)A”B(x))的含义是有一个动物不是猫，显然这句话与原语句等同

(4)举例 例1 “并非所有的动物都是猫”的表示 设 A(x)：x是动物 B(x)：x是描 原语句可表示成﹁(x)(A(x)B(x)) 依否定型公式得

例2“天下乌鸦一般黑”的表示 设 F(X):x是乌鸦 G(x,y):x与y是一般黑 原语句可表示成 (Vx)(Vy)(F(x)F(y)G(x,y)) 不难知道与之等值的公式是 x)y(F(x)F(y)-G(x,y)) 即不存在x,y是乌鸦但不一般黑.这两句话含义是相同 的.经计算有

例2 “天下乌鸦—般黑”的表示 设 F(x)：x是乌鸦 G(x，y)：x与y是一般黑 原语句可表示成 (x)(y)(F(x)^F(y) →G(x,y)) 不难知道与之等值的公式是 ﹁(x)(y)(F(x)^F(y)^﹁G(x,y)) 即不存在x,y是乌鸦但不一般黑．这两句话含义是相同 的．经计算有