第五章：等值演算与推理课件

第五章:等值演算与推理

第一节：等值式与置换规则第二节：前束范式

第三节：推理理论第五章:等值演算与推理主要内容一阶逻辑等值式与基本的等值式置换规则、换名规则、代替规则前束范式自然推理系统NL及其推理规则第五章:等值演算与推理

第一节：等值式与置换规则第二节：前束范式

第三节：推理理论等值式：公式A，B的等价式A↔B为永真式符号：A

B，也称A逻辑恒等于B等价定义：对任意解释II²

A

当且仅当I²

B5.1等值式与置换规则第一类等值式：命题逻辑的重言式的代换实例理由：重言式的代换实例都是永真式例

xF(x)

xF(x)F(x)G(x)F(x)G(x)¬¬A

AA

B

¬A

B5.1等值式与置换规则第二类等值式：消去量词等值式给定有限个体域D={a1,a2,…,an}2.量词否定等值式

x在公式A(x)中自由出现

x

A(x)

A(a1)A(a2)…A(an)

xA(x)

A(a1)

A(a2)

…A(an)

x

A(x)

x

A(x)

xA(x)

x

A(x)5.1等值式与置换规则例：设个体域为D＝{a,b,c}，将下面公式的量词消去

xF(x)yG(y)

(xF(x)yG(y))(F(a)F(b)F(c))(G(a)G(b)G(c))

xF(x)yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))5.1等值式与置换规则第二类等值式：量词辖域收缩与扩张等值式x在公式A(x)中自由出现，但不在B中自由出现(1a)

x(A(x)

B)

x

A(x)

B

(1b)

x(A(x)

B)

x

A(x)

B

(1c)

x(A(x)

B)

x

A(x)

B

(1d)

x(B

A(x))

B

x

A(x)(2a)

x(A(x)

B)

x

A(x)

B

(2b)

x(A(x)

B)

x

A(x)

B

(2c)

x(A(x)

B)

x

A(x)

B

(2d)

x(B

A(x))

B

x

A(x)5.1等值式与置换规则第二类等值式：4.量词分配等值式x在公式A(x)和B(x)中自由出现(2)

x(A(x)

B(x))

x

A(x)

x

B(x)

(1)

x(A(x)

B(x))

x

A(x)

x

B(x)

(3)x(A(x)

B(x))xA(x)

xB(x)5.1等值式与置换规则下列等值式不成立！x在公式A(x)和B(x)中自由出现(2)

x(A(x)

B(x))

x

A(x)

x

B(x)

(1)

x(A(x)

B(x))

x

A(x)

x

B(x)

提示：任意实数或者是有理数或者是无理数或者任意实数是有理数或者任意实数是无理数提示：存在实数既是有理数又是无理数存在实数是有理数或者存在实数是无理数5.1等值式与置换规则置换规则：给定φ(A)A

B，则φ(A)

φ(B)

换名规则：

x

A(x)

x’A(x’)，x’不在A中出现xA(x)

x’A(x’)，x’不在A中出现代替规则A(x)

A(x’)，x’不在A中出现5.1等值式与置换规则实例例1

将下面命题用两种形式符号化,并证明两者等值(1)没有不犯错误的人解令F(x)：x是人，G(x)：x犯错误.

x(F(x)

G(x))或

x(F(x)

G(x))

x(F(x)

G(x))

x

(F(x)

G(x))量词否定等值式

x(

F(x)

G(x))置换

x(F(x)

G(x))置换实例(2)不是所有的人都爱看电影解令F(x)：x是人，G(x)：爱看电影.

x(F(x)

G(x))

或

x(F(x)

G(x))

x(F(x)

G(x))

x

(F(x)

G(x))量词否定等值式

x

(

F(x)

G(x))置换

x(F(x)

G(x))置换例：消除既是约束出现又是自由出现的变项

xF(x,y,z)yG(x,y,z)

x(F(x,y)yG(x,y,z))

tF(t,y,z)yG(x,y,z)

tF(t,y,z)wG(x,w,z)

x(F(x,t)yG(x,y,z))

xF(x,y)tG(x,t,z)例证明:¬x

y(F(x)

G(y)H(x,y))

x

y(F(x)

G(y)¬H(x,y))

证明：

¬x

y(F(x)

G(y)H(x,y))

x

¬

y(¬(F(x)

G(y))H(x,y))

x

y((F(x)

G(y))¬H(x,y))5.1等值式与置换规则给定D={a,b,c},消去下列公式的量词

x(F(x)

yG(y))

xF(x)

yG(y)(F(a)F(b)F(c))(G(a)G(b)G(c))

x

yF(x,y)

y

(F(a,y)F(b,y)F(c,y))(F(a,a)F(b,a)F(c,a))(F(a,b)F(b,b)F(c,b))(F(a,c)F(b,c)F(c,c))5.1等值式与置换规则给定解释I如下：D={2,3}a*=2f*(2)=3,f*(3)=2F*(2)=F,F*(3)=TG*(2,2)=G*(2,3)=G*(3,2)=T,G*(3,3)=FL*(2,2)=L*(3,3)=T,L*(2,3)=L*(3,2)=F5.1等值式与置换规则求下列各式在I下的真值：

x(F(f(x))G(x,f(x)))(F(f(2))G(2,f(2)))(F(f(3))G(3,f(3)))(F(3)G(2,3))(F(2)G(3,2))(TT)(FT)T5.1等值式与置换规则第五章:等值演算与推理

第一节：等值式与置换规则第二节：前束范式

第三节：推理理论前束范式：一阶逻辑公式满足量词都出现在公式最前面量词的辖域一直延伸到公式末形如Q1x1Q2x2…Qkxk

BQ为或，B不含量词例：下列为前束范式

x

y(F(x)

G(y)¬H(x,y))

5.2前束范式5.2前束范式前束范式存在定理：一阶逻辑任何公式都存在等值的前束范式将公式中的联接词、换为、、利用量词否定等值式把

深入到原子公式前利用约束变元的换名规则利用量词辖域的扩张收缩律把量词移到全式的最前面5.2前束范式例：求下面公式的前束范式

xF(x)

xG(x)

xF(x)

xG(x)

x(F(x)G(x))或者

xF(x)

yG(y)

xF(x)

yG(y)

x

y(F(x)G(y))直观上为什么等价？5.2前束范式例：求下面公式的前束范式

xF(x)

xG(x)

xF(x)

xG(x)

xF(x)

yG(y)

x

y(F(x)G(y))5.2前束范式例：求下面公式的前束范式

xF(x,y)

yG(x,y)P80,12(4)5.2前束范式前束合取范式：Q1x1Q2x2…Qkxk

((A1

A2…An)(B1

B2…Bn)…(C1

C2…Cn))定理：任何一个一阶逻辑公式均可以转化成与其等值的前束合取范式5.2前束范式例：下列公式化为前束合取范式

x(

yP(x)zQ(z,y)¬

yR(x,y))

x(P(x)zQ(z,y)¬yR(x,y))

x(¬(P(x)zQ(z,y))¬yR(x,y))

x(¬P(x)z¬Q(z,y)y¬R(x,y))

x(¬P(x)z¬Q(z,y)w¬R(x,w))

xzw(¬P(x)

¬Q(z,y)¬R(x,w))

xzw((¬P(x)¬R(x,w))

(¬Q(z,y)¬R(x,w)))第五章:等值演算与推理

第一节：等值式与置换规则第二节：前束范式

第三节：推理理论逻辑(语义)蕴涵：给定A1,…,Ak和B符号：{A1,…,Ak}⊨B对任意赋值v:如果v(Ai)=T,则v(B)=T或者存在Ai使得v(Ai)=F称由前提A1,…,Ak推出结论B的推理是有效的B为有效结论定理：{A1,…,Ak}⊨B当且仅当A1

…

Ak

B为重言式5.3推理理论例：证明

x

A(x)

⊨

xA(x)

证明（反证法）：设

x

A(x)

⊭

xA(x)

存在个体域D的赋值I，

I(

x

A(x))=T，I(

xA(x))=F

由于I(

x

A(x))=T，存在aD，

A(a)=T故存在aD，A(a)=F由于I(

xA(x))=F，I(

xA(x))=T矛盾！5.3推理理论例：证明

xA(x)

xB(x)

⊭

x(A(x)

B(x))

证明（构造法）：构造I如下D={a,b}F^*(a)=T，F^*(b)=FG^*(a)=F，G^*(b)=TI(

xF(x))=F，I(

xF(x)

xG(x))=T

容易验证I(

x(F(x)

G(x))=F

所以

xF(x)

xG(x)

⊭

x(F(x)

G(x))

所以

xA(x)

xB(x)

⊭

x(A(x)

B(x))

5.3推理理论自然推理系统Nℒ字母表

合式公式空公理集合推理规则集关于量词的规则集5.3推理理论推理定理第一组命题逻辑推理定理的代换实例如,

xF(x)yG(y)xF(x)第二组基本等值式生成的推理定理如,

xF(x)xF(x),xF(x)xF(x)

xF(x)x

F(x),x

F(x)xF(x)第三组其他常用推理定律

(1)

xA(x)xB(x)x(A(x)B(x))(2)

x(A(x)B(x))xA(x)xB(x)(3)

x(A(x)B(x))xA(x)xB(x)(4)

x(A(x)B(x))xA(x)xB(x)全称量词消去规则(UI)

x

A(x)x

A(x)结论：A(y)结论：A(c)条件x不在

y和

y的辖域内自由出现A(y)指由A(x)把y代入x得到5.3推理理论UI条件设真命题推导如下

使用UI规则该结论是错误的，原因在于x在

y和

y的辖域内自由出现存在量词消去规则(EI)，给定前提

Γ={A1,…,An}xA(x)结论：A(c)条件：c不在Γ的任何公式出现例：要证明如果行列式有两行或两列成比例则行列式为零，只须取行列式的任意两行或两列，设它们成比例，证明行列式为零5.3推理理论EI条件设真命题Q(x)为有理数推导如下

使用EI规则

使用EI规则

该结论是错误的，原因在于c不在Γ的任何公式出现全称量词引入规则(UG)，给定前提Γ={A1,…,An}

A(x)结论：

x

A(x)

条件：x不在Γ中任何公式自由出现思考：假设Γ={F(x),F(x)G(x)}Γ⊢G(x)是否有Γ⊢

x

G(x)？5.3推理理论UG条件设真命题推导如下

使用UI规则

使用EI规则

使用UG规则该结论是错误的，原因在于x在Γ中任何公式自由出现存在量词引入规则(+)

A(y)A(c)结论：

x

A(x)结论：

x

A(x)条件：y和c分别不在

x和

x中辖域内自由出现5.3推理理论形式推演(语法蕴涵)：给定A1,…,Ak和B符号：{A1,…,Ak}⊢B存在公式序列C1,C2,…,Cn，对每个i(i=1,…,n),Ci是某个Aj或者Ci是有序列中前面的公式应用推理规则得到Cn=B称C1,…,Cn是有A1,…,Ak推B的证明

5.3推理理论推理规则(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式规则(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则(12)-规则(13)+规则(14)-规则(15)+规则证明苏格拉底论证前提：

x(M(x)D(x)),M(s)结论：D(s)M(x)：x是人,D(x)：x是要死的,s：苏格拉底解：

M(s)

x(M(x)D(x))

M(s)D(s)D(s)前提引入前提引入

-假言推理5.3推理理论构造下面推理的证明前提：¬x(P(x)Q(x)),xP(x)

结论：¬xQ(x)

解：

¬¬xQ(x)

xQ(x)

Q(y)

xP(x)

P(y)

P(y)

Q(y)

x(P(x)Q(x)¬x(P(x)Q(x))前提引入双重否定律

-前提引入

-合取引入

+前提引入5.3推理理论构造下面推理的证明前提：

x(P(x)Q(x)),¬Q(a)结论：

x¬P(x)?解：

¬Q(a)

x(P(x)Q(x))

P(a)Q(a)¬P(a)

x¬P(x)?5.3推理理论讨论A(x)与

xA(x)的区别与联系

xA(x)到A(x)：全称量词消去规则A(x)到xA(x)：全称量词引入规则A(x)不是一个命题对x的不同取值对应不同的真值

xA(x)在一个赋值下有唯一真值5.3推理理论第五章习题课主要内容一阶逻辑等值式基本等值式，置换规则、换名规则、代替规则前束范式推理的形式结构自然推理系统NL

推理定律、推理规则基本要求深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们．熟练正确地使用置换规则、换名规则、代替规则．熟练地求出给定公式的前束范式．深刻理解自然推理系统NL

的定义，牢记NL

中的各条推理规则，特别是注意使用

、

+、

+、

4条推理规则的条件．能正确地给出有效推理的证明．练习11.给定解释I如下:(1)个体域D={2,3}(2)(3)(4)求下述在I下的解释及其真值:

x

y(F(f(x))G(y,f(a)))解

xF(f(x))yG(y,f(a))

F(f(2))F(f(3))(G(2,f(2))G(3,f(2)))10(10)0练习22.求下述公式的前束范式:

xF(x)

y(G(x,y)

H(x,y))解使用换名规则,

xF(x)

y(G(x,y)

H(x,y))

zF(z)

y(G(x,y)

H(x,y))

z(F(z)

y(G(x,y)

H(x,y))

z

y(F(z)

(G(x,y)

H(x,y)))使用代替规则

xF(x)

y(G(x,y)

H(x,y))

xF(x)

y(G(z,y)

H(z,y))

x(F(x)

y(G(z,y)

H(z,y))

x

y(F(x)

(G(z,y)

H(z,y)))练习33.构造下面推理的证明:(1)前提：

x(F(x)

G(x)),

xF(x)

结论：

xG(x)证明：①

x(F(x)

G(x))前提引入②F(y)

G(y)①

③

xF(x)前提引入④F(y)③

⑤G(y)②④假言推理⑥

yG(y)⑤

+⑦

xG(x)⑥置换练习3(续)(2)前提：

x(F(x)

G(x)),

xG(x)结论：

xF(x)证明：用归谬法①

xF(x)结论否定引入②

x

F(x)①置换③

xG(x)前提引入④

x

G(x)③置换⑤

x(F(x)

G(x)),前提引入⑥

F(c)②

⑦

G(c)④

⑧F(c)

G(c)⑤

⑨G(c)⑥⑧析取三段论⑩

G(c)

G(c)⑦⑨合取引入练习3(续)(3)前提：

x(F(x)

G(x)),

x(G(x)

H(x))结论：

xF(x)

xH(x)证明:用附加前提法①

xF(x)附加前提引入②F(x)①

③

x(F(x)

G(x))前提引入④F(x)

G(x)③

⑤

x(G(x)

H(x))前提引入⑥G(x)

H(x)⑤

⑦F(x)

H