離散數(shù)學(xué)3階邏輯3 2

13.2一階邏輯等值演算3.2.1一階邏輯等值式與置換規(guī)則基本等值式置換規(guī)則、換名規(guī)則、代替規(guī)則3.2.2一階邏輯前束范式2等值式定義3.10若A

B是永真式,則稱A與B是等值的,記作A

B,并稱A

B為等值式基本等值式命題邏輯中基本等值式的代換實(shí)例如，

xF(x)

yG(y)

xF(x)

yG(y)

(

xF(x)

yG(y))

xF(x)

yG(y)等消去量詞等值式設(shè)D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)3基本等值式(續(xù))量詞轄域收縮與擴(kuò)張等值式

設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn)關(guān)于全稱量詞的：

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)關(guān)于存在量詞的:

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)4基本等值式(續(xù))量詞否定等值式設(shè)A(x)是含x自由出現(xiàn)的公式

xA(x)

x

A(x)

xA(x)

x

A(x)量詞分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)注意：

對(duì)

無分配律，

對(duì)

無分配律5置換規(guī)則、換名規(guī)則、代替規(guī)則置換規(guī)則設(shè)Φ(A)是含公式A的公式,Φ(B)是用公式B取代Φ(A)中的所有A得到的公式,則Φ(A)

Φ(B)換名規(guī)則將公式A中某量詞的指導(dǎo)變?cè)捌湓谳犛騼?nèi)的所有約束出現(xiàn)改成該量詞轄域內(nèi)未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng),其余部分不變,記所得公式為A

,則A

A

代替規(guī)則將公式A中某個(gè)自由出現(xiàn)的個(gè)體變項(xiàng)的所有自由出現(xiàn)改成A中未曾出現(xiàn)的某個(gè)個(gè)體變項(xiàng),其余部分不變,記所得公式為A

,則A

A6實(shí)例例1消去公式中既約束出現(xiàn)、又自由出現(xiàn)的個(gè)體變項(xiàng)(1)

xF(x,y,z)

yG(x,y,z)

uF(u,y,z)

yG(x,y,z)換名規(guī)則

uF(u,y,z)

vG(x,v,z)換名規(guī)則或者

xF(x,u,z)

yG(x,y,z)代替規(guī)則

xF(x,u,z)

yG(v,y,z)代替規(guī)則(2)

x(F(x,y)

yG(x,y,z))

x(F(x,y)

tG(x,t,z))換名規(guī)則或者x(F(x,t)

yG(x,y,z))代替規(guī)則7實(shí)例例2設(shè)個(gè)體域D={a,b,c},消去下面公式中的量詞:(1)

x(F(x)

G(x))

(F(a)

G(a))

(F(b)

G(b))

(F(c)

G(c))(2)

x(F(x)

yG(y))

xF(x)

yG(y)量詞轄域收縮(F(a)

F(b)

F(c))(G(a)

G(b)

G(c))

x(F(x,a)

F(x,b)

F(x,c))(3)

x

yF(x,y)

(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))8實(shí)例解(F(f(2))

G(2,f(2)))

(F(f(3))

G(3,f(3)))例3給定解釋I:(a)D={2,3},(b)(c):x是奇數(shù),:x=2

y=2,:x=y.在I下求下列各式的真值:(1)

x(F(f(x))

G(x,f(x)))

(2)

x

yL(x,y)

(11)

(01)

1解yL(2,y)

yL(3,y)(L(2,2)

L(2,3))(L(3,2)

L(3,3))(10)(01)09實(shí)例例4證明下列各等值式:

x(M(x)

F(x))

x(M(x)

F(x))證左邊

x

(M(x)

F(x))量詞否定等值式

x(

M(x)

F(x))

x(M(x)

F(x))10前束范式定義3.11設(shè)A為一個(gè)一階邏輯公式,若A具有如下形式Q1x1Q2x2…QkxkB則稱A為前束范式,其中Qi

為

或,1

i

k,B為不含量詞的公式.例如

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

G(x))是前束范式

x(F(x)

y(G(y)

H(x,y)))

x(F(x)

G(x))不是前束范式11公式的前束范式定理3.3(前束范式存在定理)一階邏輯中的任何公式都存在與之等值的前束范式例5求公式的前束范式(1)

xF(x)

xG(x)解

xF(x)

x

G(x)量詞否定等值式

x(F(x)

G(x))量詞分配等值式解2

xF(x)

yG(y)換名規(guī)則

xF(x)

y

G(y)量詞否定等值式

x(F(x)

y

G(y))量詞轄域擴(kuò)張

x

y(F(x)

G(y))量詞轄域擴(kuò)張12實(shí)例(續(xù))(2)

xF(x)

xG(x)解

xF(x)

x

G(x)量詞否定規(guī)則

xF(x)

y

G(y)換名規(guī)則

x(F(x)

y

G(y))量詞轄域擴(kuò)張

x

y(F(x)

G(y))量詞轄域擴(kuò)張(3)

xF(x)

xG(x)解xF(x)

yG(y)換名規(guī)則

x

y(F(x)

G(y))量詞轄域擴(kuò)張13實(shí)例(續(xù))(4)

xF(x,y)

yG(x,y)解

sF(s,y)

tG(x,t)換名規(guī)則

s

t(F(s,y)

G(x,t))量詞轄域擴(kuò)張解2

xF(x,u)

yG(v,y)代替規(guī)則

x

y(F(x,u)

G(v,y))量詞轄域擴(kuò)張143.3一階邏輯推理理論3.3.1一階邏輯中推理的形式結(jié)構(gòu)重要推理定律3.3.2量詞消去與引入規(guī)則UI規(guī)則、UG規(guī)則、EG規(guī)則、EI規(guī)則3.3.3自然推理系統(tǒng)F15一階邏輯中推理的形式結(jié)構(gòu)推理的形式結(jié)構(gòu)形式1

A1

A2

…

Ak

B(*)形式2

前提：A1,A2,…,Ak

結(jié)論：B其中A1,A2,…,Ak,B為一階邏輯公式.若(*)為永真式,則稱推理正確,記作A1

A2

…

Ak

B16推理定律重要推理定律第一組命題邏輯推理定律的代換實(shí)例例如

xF(x)

yG(y)

xF(x)化簡(jiǎn)律的代換實(shí)例第二組每個(gè)一階邏輯基本等值式生成2個(gè)推理定律例如

xF(x)

x(

F(x)),

x(

F(x))

xF(x)第三組

xA(x)

xB(x)

x(A(x)

B(x))

x(A(x)

B(x))

xA(x)

xB(x)推理定律:一階邏輯中永真的蘊(yùn)涵式17量詞消去與引入規(guī)則全稱量詞消去規(guī)則(UI)兩式成立的條件是:在第一式中,取代x的y應(yīng)為任意的不在A(x)中約束出現(xiàn)的個(gè)體變項(xiàng).在第二式中,c為任意個(gè)體常項(xiàng).用y或c去取代A(x)中的自由出現(xiàn)的x時(shí),一定要在x自由出現(xiàn)的一切地方進(jìn)行取代.18量詞消去與引入規(guī)則(續(xù))該式成立的條件是無論A(y)中自由出現(xiàn)的個(gè)體變項(xiàng)y取何值,A(y)應(yīng)該均為真.取代自由出現(xiàn)的y的x,也不能在A(y)中約束出現(xiàn).全稱量詞引入規(guī)則(UG)19量詞消去與引入規(guī)則(續(xù))該式成立的條件是：c是使A為真的特定個(gè)體常項(xiàng).取代c的x不能在A(c)中出現(xiàn)過.存在量詞引入規(guī)則(EG)20量詞消去與引入規(guī)則(續(xù))該式成立的條件是：c是使A為真的特定的個(gè)體常項(xiàng).c不在A(x)中出現(xiàn).x在A(x)中自由出現(xiàn),除x之外沒有其他自由出現(xiàn)的個(gè)體變項(xiàng)存在量詞消去規(guī)則(EI)21自然推理系統(tǒng)F自然推理系統(tǒng)F包括下述組成部分:1.字母表,同一階語言?的字母表2.合式公式,同?的合式公式3.推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則22自然推理系統(tǒng)F(續(xù))(6)化簡(jiǎn)規(guī)則(7)拒取式規(guī)則(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)UI規(guī)則(13)UG規(guī)則(14)EG規(guī)則(15)EI規(guī)則23實(shí)例例1證明蘇格拉底三段論:“人都是要死的,蘇格拉底是人，所以蘇格拉底是要死的.”解令F(x):x是人,G(x):x是要死的,a:

蘇格拉底前提：

x(F(x)

G(x))，F(xiàn)(a)結(jié)論：G(a)證明：①F(a)前提引入②

x(F(x)

G(x))前提引入③F(a)

G(a)②UI④G(a)①③假言推理24實(shí)例例2構(gòu)造下述推理證明前提：

x(F(x)

G(x))，

xF(x)結(jié)論：

xG(x)證明：①

xF(x)前提引入②

x(F(x)

G(x))前提引入③F(c)①EI④F(c)

G(c)②UI⑤G(c)③④假言推理⑥

xG(x)⑤EG注意：必須先消存在量詞25實(shí)例例3設(shè)個(gè)體域:R,F(x,y):x>y.指出下述推理證明中的錯(cuò)誤前提:

x

yF(x,y)真命題結(jié)論:

xF(x,c)假命題證明:①

x

yF(x,y)前提引入②

yF(t,y)①UI規(guī)則③F(t,c)②EI規(guī)則④

xF(x,c)③UG規(guī)則③,在F(t,y)中,除y外,