《离散数学》课程PPT教学课件（讲稿）第5章 谓词逻辑的等值和推理演算

第5章谓词逻辑的等值和推理演算 ●谓词逻辑研究的对象是重要的逻辑规律, 普遍有效式是最重要的逻辑规律,而等值 式、推理式都是普遍有效的谓词公式,因 此等值和推理演算就成了谓词逻辑的基本 内容 ●这章的讨论,主要是以语义的观点进行的 非形式的描述,而严格的形式化的讨论见 第6章所建立的公理系统

第5章 谓词逻辑的等值和推理演算 ⚫谓词逻辑研究的对象是重要的逻辑规律， 普遍有效式是最重要的逻辑规律，而等值 式、推理式都是普遍有效的谓词公式，因 此等值和推理演算就成了谓词逻辑的基本 内容． ⚫这章的讨论，主要是以语义的观点进行的 非形式的描述，而严格的形式化的讨论见 第6章所建立的公理系统．

5.1否定型等值式 ●等值:若给定了两个谓词公式A,B,说A 和B是等值的,如果在公式A,B的任一解 释(注意在谓词逻辑中,解释的范围还包含 论域以外的其他要素,见P65)下,A和B都 有相同的真值. ●其他说法:A,B等值当且仅当A→B是普遍 有效的公式(注意这里不再说重言式了).记 作A=B或AB

5．1 否定型等值式 ⚫等值：若给定了两个谓词公式A，B，说A 和B是等值的，如果在公式A，B的任一解 释(注意在谓词逻辑中，解释的范围还包含 论域以外的其他要素，见P65)下，A和B都 有相同的真值． ⚫其他说法：A，B等值当且仅当A↔B是普遍 有效的公式(注意这里不再说重言式了)．记 作A＝B或AB

5.1.1由命题公式移植来的等值式 ●若将命题公式的等值式,直接以谓词公式代入命题 变项便可得谓词等值式.由 --p=p,p >q=-pvq, (pnq)vr=(pvr)^(qvr) 可得(以下每两个为一对:无量词、有量词) p(x)=p(x) ()P(x)=(V)P(x) P(x)→Q(x)=P(x)vQ(x) ()p(x)→(3x)Q(x)=-(Vx)p(x)v(3x)Q(x) (P(x) Q(x)VR() =(P(x) VR(x)) ^((x) VR(x)) (()P(x)(y)v(3z)R() =(()p(x)v(3z)r(z)(Q(y)v(3z)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否定型等值式 (摩根律的推广) (V)P(x)=(3x)P(x) (3x)P(x)=(Vx)→P(x) ●形式上看这对公式,是说否定词”一”可越过量词 深入到量词的辖域内,但要把所越过的量词V转 换为3,3转换为V

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

(1)从语义上说明 (2)例:在{,2}域上分析 ()p(x)=-(p(1)p(2))=p(1)vP(2) =(3x)P(x) (3)P(x)=-(P(1)vP(2))=P(1)aP(2) =(Vx)P(x)

(1)从语义上说明 (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如果在任一解释I下 A真B就真,而且B真A就真 若证明一(V)P(x)=(3x)P(x) 1.设某一解释I下若一(x)P(x)=T 从而(Vx)P(x)=F,即有一个X∈D使P(X)=F 于是一P(x)=T 故在I下(3x)P(x)=T 2.反过来,设某一解释I下若(3x)-P(x)=T 即有一个xD使一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) 1. 设某一解释I下若﹁(x)P(x)=T 从而(x)P(x)=F，即有一个xoD,使P(Xo )=F 于是﹁P(xo )=T 故在I下(x)﹁P(x)=T 2. 反过来，设某一解释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)) 依否定型公式得 (Vx)(A(x)→B(x)) =(3x)-(A(x)→B(x)) =(3x)-(A(x)VB(x)) =(3x)(A(x)-B(x)) 而(3x)(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)) 不难知道与之等值的公式是 (3x)(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是乌鸦但不一般黑．这两句话含义是相同 的．经计算有

●●● (3x)(3y)(F(x)F(y)-G(x,y)) =(x)-((3y)(F()F(y)a-(x,y))) =()()-(F(:)AF(y)(x+y)) =(x)(y)(-(F(x)∧F(y))G(x,y)) =(x:)()(F(x)AF(y)+G(,y))

5.2量词分配等值式 一、含单独的命题变项,与无关 5.2.1量词对√、人的分配律 (3x)(P(x)Aq)=(3x)P(x)∧q ●这是一组量词对v、的分配律,其中q是命题变 项,与个体变元无关,这是很重要的条件 ●我们仅对第一个等式给出证明,其余三个同样可 证

5．2 量词分配等值式 一、含单独的命题变项，与x无关 5．2．1 量词对、的分配律 ⚫ 这是一组量词对、的分配律，其中q是命题变 项，与个体变元x无关，这是很重要的条件． ⚫ 我们仅对第一个等式给出证明，其余三个同样可 证．