離散數(shù)學(xué)：第五章 一階邏輯等值演算與推理

第五章:一階邏輯等值演算與推理

第一節(jié)：等值式與置換規(guī)則第二節(jié)：前束范式

第三節(jié)：推理理論1計(jì)算機(jī)科學(xué)與工程學(xué)院第五章:一階邏輯等值演算與推理主要內(nèi)容一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式自然推理系統(tǒng)NL及其推理規(guī)則2計(jì)算機(jī)科學(xué)與工程學(xué)院第五章:一階邏輯等值演算與推理

第一節(jié)：等值式與置換規(guī)則

第二節(jié)：前束范式

第三節(jié)：推理理論計(jì)算機(jī)科學(xué)與工程學(xué)院3等值式：公式A，B的等價(jià)式A?B為永真式符號(hào)：AB，也稱A邏輯恒等于B等價(jià)定義：對(duì)任意解釋II(A)當(dāng)且僅當(dāng)I(B)5.1等值式與置換規(guī)則4計(jì)算機(jī)科學(xué)與工程學(xué)院第一類等值式：命題邏輯的重言式的代換實(shí)例理由：重言式的代換實(shí)例都是永真式例xF(x)xF(x)F(x)G(x)F(x)G(x)??AAAB

?A

B5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院5第二類等值式：1.消去量詞等值式

給定有限個(gè)體域D={a1,a2,…,an}2.量詞否定等值式

x在公式A(x)中自由出現(xiàn)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等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院6例：設(shè)個(gè)體域?yàn)镈＝{a,b,c}，將下面公式的量詞消去1.xF(x)yG(y)2.(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等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院7第二類等值式：3.量詞轄域收縮與擴(kuò)張等值式x在公式A(x)中自由出現(xiàn)，但不在B中自由出現(xiàn)(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))Bx

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))Bx

A(x)5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院8第二類等值式：4.量詞分配等值式x在公式A(x)和B(x)中自由出現(xiàn)(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等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院9

下列等值式不成立！x在公式A(x)和B(x)中自由出現(xiàn)(2)x(A(x)B(x))x

A(x)x

B(x)

(1)x(A(x)B(x))x

A(x)x

B(x)

提示：任意實(shí)數(shù)或者是有理數(shù)或者是無(wú)理數(shù)或者任意實(shí)數(shù)是有理數(shù)或者任意實(shí)數(shù)是無(wú)理數(shù)提示：存在實(shí)數(shù)既是有理數(shù)又是無(wú)理數(shù)存在實(shí)數(shù)是有理數(shù)或者存在實(shí)數(shù)是無(wú)理數(shù)5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院10置換規(guī)則：給定φ(A)AB，則φ(A)

φ(B)

換名規(guī)則：x

A(x)x’A(x’)，x’不在A中出現(xiàn)xA(x)x’A(x’)，x’不在A中出現(xiàn)代替規(guī)則A(x)A(x’)，x’不在A中出現(xiàn)5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院11例：消除既是約束出現(xiàn)又是自由出現(xiàn)的變項(xiàng)1.xF(x,y,z)yG(x,y,z)2.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)5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院12證明:?x

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

xy(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等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院13給定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))xyF(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))xyF(x,y)x(F(x,a)F(x,b)F(x,c))(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c))(F(c,a)F(c,b)F(c,c))5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院14給定解釋I如下：D={2,3}f*(2)=3,f*(3)=2F*(2)=F,F*(3)=TG*(2,2)=G*(2,3)=G*(3,2)=T,G*(3,3)=F求下式在I下的真值：x(F(f(x))G(x,f(x)))5.1等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院15求下式在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等值式與置換規(guī)則計(jì)算機(jī)科學(xué)與工程學(xué)院16第五章:一階邏輯等值演算與推理

第一節(jié)：等值式與置換規(guī)則第二節(jié)：前束范式

第三節(jié)：推理理論計(jì)算機(jī)科學(xué)與工程學(xué)院17前束范式：一階邏輯公式滿足量詞都出現(xiàn)在公式最前面量詞的轄域一直延伸到公式末形如Q1x1Q2x2…Qkxk

BQ為或，B不含量詞例：下列為前束范式xy(F(x)G(y)?H(x,y))5.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院185.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院19前束范式存在定理：一階邏輯任何公式都存在等值的前束范式將公式中的聯(lián)接詞、換為、、利用量詞否定等值式把深入到原子公式前利用約束變?cè)膿Q名規(guī)則利用量詞轄域的擴(kuò)張收縮律把量詞移到全式的最前面5.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院20例：求下面公式的前束范式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))直觀上為什么等價(jià)？5.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院21例：求下面公式的前束范式xF(x)xG(x)xF(x)xG(x)xF(x)yG(y)x

y(F(x)G(y))5.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院22前束合取范式：Q1x1Q2x2…Qkxk

((A1

A2

…An)(B1

B2

…Bn)…(C1

C2…Cn))定理：任何一個(gè)一階邏輯公式均可以轉(zhuǎn)化成與其等值的前束合取范式5.2前束范式計(jì)算機(jī)科學(xué)與工程學(xué)院23例：下列公式化為前束合取范式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)))第五章:一階邏輯等值演算與推理

第一節(jié)：等值式與置換規(guī)則第二節(jié)：前束范式

第三節(jié)：推理理論計(jì)算機(jī)科學(xué)與工程學(xué)院24邏輯(語(yǔ)義)蘊(yùn)涵：給定A1,…,Ak和B符號(hào)：{A1,…,Ak}?B對(duì)任意賦值v（解釋I）:如果v(Ai)=T,則v(B)=T或者存在Ai使得v(Ai)=F稱由前提A1,…,Ak推出結(jié)論B的推理是有效的B為有效結(jié)論定理：{A1,…,Ak}?B當(dāng)且僅當(dāng)A1…Ak

B為重言式計(jì)算機(jī)科學(xué)與工程學(xué)院255.3推理理論例：證明xA(x)

?xA(x)

證明（反證法）：設(shè)xA(x)

?xA(x)

存在個(gè)體域D的賦值I，

I(xA(x))=T，I(xA(x))=F

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

矛盾！計(jì)算機(jī)科學(xué)與工程學(xué)院265.3推理理論例：證明xA(x)xB(x)

?

x(A(x)B(x))

證明（構(gòu)造法）：構(gòu)造I如下D={a,b}F*(a)=T，F(xiàn)*(b)=FG*(a)=F，G*(b)=TI(xF(x))=F，I(xF(x)xG(x))=T

容易驗(yàn)證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))

計(jì)算機(jī)科學(xué)與工程學(xué)院275.3推理理論5.3推理理論自然推理系統(tǒng)N?字母表

合式公式空公理集合推理規(guī)則集關(guān)于量詞的規(guī)則集28計(jì)算機(jī)科學(xué)與工程學(xué)院全稱量詞消去規(guī)則(-)

x

A(x)x

A(x)結(jié)論：A(y)結(jié)論：A(c)條件x不在y和y的轄域內(nèi)自由出現(xiàn)A(y)指由A(x)把y代入x得到計(jì)算機(jī)科學(xué)與工程學(xué)院295.3推理理論全稱量詞引入規(guī)則(+)，給定前提Γ={A1,…,An}

A(x)結(jié)論：x

A(x)

條件：x不在Γ中任何公式自由出現(xiàn)思考：假設(shè)Γ={F(x),F(x)G(x)}Γ?G(x)是否有Γ?x

G(x)？計(jì)算機(jī)科學(xué)與工程學(xué)院305.3推理理論存在量詞消去規(guī)則(-)，給定前提

Γ={A1,…,An}

A(x)B

x

A(x)x

A(x)結(jié)論：x

A(x)B結(jié)論：A(y)A(c)條件：x不在Γ的任何公式和B中自由出現(xiàn)x不在y和y的轄域內(nèi)自由出現(xiàn)A(y)指由A(x)把y代入x得到例：要證明如果行列式有兩行或兩列成比例則行列式為零，只須取行列式的任意兩行或兩列，設(shè)它們成比例，證明行列式為零計(jì)算機(jī)科學(xué)與工程學(xué)院315.3推理理論

存在量詞引入規(guī)則(+)

A(y)A(c)結(jié)論：x

A(x)結(jié)論：x

A(x)條件：y和c分別不在x和x中轄域內(nèi)自由出現(xiàn)計(jì)算機(jī)科學(xué)與工程學(xué)院325.3推理理論5.3推理理論形式推演(語(yǔ)法蘊(yùn)涵)：給定A1,…,Ak和B符號(hào)：{A1,…,Ak}?B存在公式序列C1,C2,…,Cn，對(duì)每個(gè)i(i=1,…,n),Ci是某個(gè)Aj或者Ci是有序列中前面的公式應(yīng)用推理規(guī)則得到Cn=B稱C1,…,Cn是有A1,…,Ak推B的證明33計(jì)算機(jī)科學(xué)與工程學(xué)院5.3推理理論證明蘇格拉底論證前提：x(M(x)D(x)),M(s)

結(jié)論：D(s)M(x)：x是人,D(x)：x是要死的,s：蘇格拉底解：

M(s)

x(M(x)D(x))

M(s)D(s)