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

離散數(shù)學(xué)一階邏輯等值演算與推理1第1頁，共37頁，2023年，2月20日，星期一5.1

一階邏輯等值式與置換規(guī)則定義5.1

設(shè)A,B是兩個(gè)謂詞公式,如果AB是永真式,

則稱A與B等值,記作AB,并稱AB是等值式?；镜戎凳?第一組命題邏輯中16組基本等值式的代換實(shí)例

例如，xF(x)xF(x),xF(x)yG(y)

xF(x)yG(y)等第二組

(1)消去量詞等值式

設(shè)D={a1,a2,…,an}①xA(x)A(a1)A(a2)…A(an)②xA(x)A(a1)A(a2)…A(an)2第2頁，共37頁，2023年，2月20日，星期一基本等值式(2)量詞否定等值式①xA(x)xA(x)②xA(x)xA(x)(3)量詞轄域收縮與擴(kuò)張等值式

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(BA(x))

BxA(x)3第3頁，共37頁，2023年，2月20日，星期一基本等值式關(guān)于存在量詞的：①x(A(x)B)

xA(x)B②x(A(x)B)

xA(x)B③x(A(x)B)

xA(x)B④x(BA(x))

BxA(x)(4)量詞分配等值式①x(A(x)B(x))

xA(x)xB(x)②x(A(x)B(x))

xA(x)xB(x)注意：對(duì)，對(duì)無分配律4第4頁，共37頁，2023年，2月20日，星期一置換規(guī)則、換名規(guī)則、代替規(guī)則1.置換規(guī)則設(shè)(A)是含A的公式,那么,若AB,則(A)(B).2.換名規(guī)則設(shè)A為一公式，將A中某量詞轄域中個(gè)體變項(xiàng)的所有約束出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)獡Q成該量詞轄域中未曾出現(xiàn)過的個(gè)體變項(xiàng)符號(hào)，其余部分不變，設(shè)所得公式為A，則AA.3.代替規(guī)則設(shè)A為一公式，將A中某個(gè)個(gè)體變項(xiàng)的所有自由出現(xiàn)用A中未曾出現(xiàn)過的個(gè)體變項(xiàng)符號(hào)代替，其余部分不變，設(shè)所得公式為A，則AA.5第5頁，共37頁，2023年，2月20日，星期一實(shí)例例1

將下面命題用兩種形式符號(hào)化,并證明兩者等值:(1)沒有不犯錯(cuò)誤的人解令F(x)：x是人，G(x)：x犯錯(cuò)誤.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))置換6第6頁，共37頁，2023年，2月20日，星期一實(shí)例(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))置換7第7頁，共37頁，2023年，2月20日，星期一實(shí)例例2

將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)的個(gè)體變項(xiàng):x(F(x,y,z)yG(x,y,z))解x(F(x,y,z)yG(x,y,z))x(F(x,y,z)tG(x,t,z))

換名規(guī)則xt(F(x,y,z)G(x,t,z))

轄域擴(kuò)張等值式或者x(F(x,y,z)yG(x,y,z))x(F(x,u,z)yG(x,y,z))

代替規(guī)則xy(F(x,u,z)G(x,y,z))

轄域擴(kuò)張等值式8第8頁，共37頁，2023年，2月20日，星期一實(shí)例例3

設(shè)個(gè)體域D={a,b,c},消去下述公式中的量詞:(1)xy(F(x)G(y))解xy(F(x)G(y))y(F(a)G(y)))(y(F(b)G(y)))(y(F(c)G(y)))((F(a)G(a))(F(a)G(b))(F(a)G(c)))((F(b)G(a))(F(b)G(b))(F(b)G(c)))

((F(c)G(a))(F(c)G(b))(F(c)G(c)))

9第9頁，共37頁，2023年，2月20日，星期一實(shí)例解法二xy(F(x)G(y))x(F(x)yG(y))轄域縮小等值式x(F(x)G(a)G(b)G(c))(F(a)G(a)G(b)G(c))

(F(b)G(a)G(b)G(c))(F(c)G(a)G(b)G(c))10第10頁，共37頁，2023年，2月20日，星期一實(shí)例(2)xyF(x,y)

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))11第11頁，共37頁，2023年，2月20日，星期一5.2

一階邏輯前束范式定義5.2

設(shè)A為一個(gè)一階邏輯公式，若A具有如下形式

Q1x1Q2x2…QkxkB則稱A為前束范式，其中Qi(1

i

k)為或，B為不含量詞的公式。例如，x(F(x)G(x))

xy(F(x)(G(y)H(x,y)))是前束范式而x(F(x)G(x))

x(F(x)y(G(y)H(x,y)))不是前束范式.12第12頁，共37頁，2023年，2月20日，星期一前束范式存在定理定理5.1（前束范式存在定理）一階邏輯中的任何公式都存在與之等值的前束范式。例4

求下列公式的前束范式

(1)x(M(x)F(x))解x(M(x)F(x))

x(M(x)F(x))（量詞否定等值式）

x(M(x)F(x))

后兩步結(jié)果都是前束范式，說明公式的前束范式不惟一.13第13頁，共37頁，2023年，2月20日，星期一求前束范式的實(shí)例

(2)xF(x)xG(x)解xF(x)xG(x)

xF(x)xG(x)（量詞否定等值式）

x(F(x)G(x))（量詞分配等值式）或

xF(x)xG(x)

xF(x)xG(x)量詞否定等值式

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

xy(F(x)G(y))轄域收縮擴(kuò)張規(guī)則14第14頁，共37頁，2023年，2月20日，星期一求前束范式的實(shí)例(3)xF(x)y(G(x,y)H(y))或

xF(x)y(G(z,y)H(y))代替規(guī)則

xy(F(x)(G(z,y)H(y)))解xF(x)y(G(x,y)H(y))

zF(z)y(G(x,y)H(y))換名規(guī)則

zy(F(z)(G(x,y)H(y)))轄域收縮擴(kuò)張規(guī)則15第15頁，共37頁，2023年，2月20日，星期一5.3

一階邏輯的推論理論推理的形式結(jié)構(gòu)：1.A1A2AkB

若次式是永真式,則稱推理正確,記作A1A2AkB2.前提:A1,A2,,Ak

結(jié)論:B推理定理:永真式的蘊(yùn)涵式16第16頁，共37頁，2023年，2月20日，星期一推理定理第一組命題邏輯推理定理的代換實(shí)例如,xF(x)yG(y)xF(x)第二組基本等值式生成的推理定理如,xF(x)xF(x),xF(x)xF(x)xF(x)xF(x),xF(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)17第17頁，共37頁，2023年，2月20日，星期一量詞消去引入規(guī)則1.全稱量詞消去規(guī)則(-)

或其中x,y是個(gè)體變項(xiàng)符號(hào),c是個(gè)體常項(xiàng)符號(hào),且在A中x不在y和y的轄域內(nèi)自由出現(xiàn).2.全稱量詞引入規(guī)則(+)

其中x是個(gè)體變項(xiàng)符號(hào),且不在前提的任何公式中自由出現(xiàn).xA(x)A(y)xA(x)A(c)

A(x)xA(x)18第18頁，共37頁，2023年，2月20日，星期一量詞消去引入規(guī)則3.存在量詞消去規(guī)則(-)

其中x是個(gè)體變項(xiàng)符號(hào),且不在前提的任何公式和B中自由出現(xiàn).19第19頁，共37頁，2023年，2月20日，星期一量詞消去引入規(guī)則4.存在量詞引入消去規(guī)則(+)

其中x,y是個(gè)體變項(xiàng)符號(hào),c是個(gè)體常項(xiàng)符號(hào)，且在A中y和c不在x和x的轄域內(nèi)自由出現(xiàn).

A(y)xA(x)

A(c)xA(x)20第20頁，共37頁，2023年，2月20日，星期一自然推理系統(tǒng)NL定義5.3

自然推理系統(tǒng)NL定義如下:1.字母表.同一階語言L的字母表2.合式公式.同L的合式公式3.推理規(guī)則:(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡規(guī)則(7)拒取式規(guī)則21第21頁，共37頁，2023年，2月20日，星期一自然推理系統(tǒng)NL(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)-規(guī)則(13)+規(guī)則(14)-規(guī)則(15)+規(guī)則推理的證明22第22頁，共37頁，2023年，2月20日，星期一構(gòu)造推理證明的實(shí)例例5

在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明,取個(gè)體域R:任何自然數(shù)都是整數(shù).存在自然數(shù).所以,存在整數(shù).解設(shè)F(x):x是自然數(shù),G(x):x是整數(shù).前提:x(F(x)G(x)),xF(x)結(jié)論:xG(x)23第23頁，共37頁，2023年，2月20日，星期一構(gòu)造推理證明的實(shí)例證明:①x(F(x)G(x))前提引入②F(x)G(x)①-③F(x)xG(x)②+④xF(x)xG(x)③-⑤xF(x)前提引入⑥xG(x)④⑤假言推理

24第24頁，共37頁，2023年，2月20日，星期一構(gòu)造推理證明的實(shí)例例6

在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明,取個(gè)體域R:不存在能表示成分?jǐn)?shù)的無理數(shù).有理數(shù)都能表示成分?jǐn)?shù).所以,有理數(shù)都不是無理數(shù).解設(shè)F(x):x是無理數(shù),G(x):x是有理數(shù),H(x):x能表示成分?jǐn)?shù).前提:x(F(x)H(x)),

x(G(x)H(x))結(jié)論:x(G(x)F(x))25第25頁，共37頁，2023年，2月20日，星期一構(gòu)造推理證明的實(shí)例⑤x(G(x)H(x))

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

⑦H(x)F(x)④置換⑧G(x)F(x)⑥⑦假言三段論⑨x(G(x)F(x))⑧+證明:①x(F(x)H(x))前提引入②x(F(x)H(x))①置換③x(F(x)H(x))②置換④F(x)H(x)③-26第26頁，共37頁，2023年，2月20日，星期一重要提示要特別注意使用-、+、-、+規(guī)則的條件.反例1.對(duì)A=xyF(x,y)使用-規(guī)則,推得B=yF(y,y).取解釋I:個(gè)體域?yàn)镽,在I下A被解釋為xy(x>y),真;而B被解釋為y(y>y),假原因:在A中x自由出現(xiàn)在y的轄域F(x,y)內(nèi)反例2.前提:P(x)Q(x),P(x)

結(jié)論:xQ(x)取解釋I:個(gè)體域?yàn)閆,在I下前提為真,結(jié)論為假,從而推理不正確27第27頁，共37頁，2023年，2月20日，星期一反例2(續(xù))“證明”:①P(x)Q(x)前提引入②P(x)前提引入③Q(x)①②假言推理④xQ(x)③+錯(cuò)誤原因:在④使用+規(guī)則,而x在前提的公式中自由出現(xiàn).28第28頁，共37頁，2023年，2月20日，星期一練習(xí)11.給定解釋I如下:(1)個(gè)體域D={2,3}(2)(3)(4)求下述在I下的解釋及其真值:

xy(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)029第29頁，共37頁，2023年，2月20日，星期一練習(xí)22.求下述公式的前束范式:

xF(x)y(G(x,y)H(x,y))解使用換名規(guī)則,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))

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

使用代替規(guī)則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))

xy(F(x)(G(z,y)H(z,y)))30第30頁，共37頁，2023年，2月20日，星期一練習(xí)33.構(gòu)造下面推理的證明:(1)前提：x(F(x)G(x)),xF(x)結(jié)論：xG(x)證明：①x(F(x)G(x))前提引入②F(y)G(y)①③xF(x)前提引入④F(y)③⑤G(y)②④假言推理⑥yG(y)⑤+⑦xG(x)⑥置換31第31頁，共37頁，2023年，2月20日，星期一練習(xí)3(續(xù))(2)前提：x(F(x)G(x)),xG(x)結(jié)論：xF(x)證明：用歸謬法①xF(x)結(jié)論否定引入②xF(x)①置換③xG(x)前提引入④xG(x)③置換⑤x(F(x)G(x)),前提引入⑥F(c)②⑦G(c)④⑧F(c)G(c)⑤⑨G(c)⑥⑧析取三段論⑩G(c)G(c)⑦⑨合取引入32第32頁，共37頁，2023年，2月20日，星期一練習(xí)3(續(xù))(3)前提：x(F(x)G(x)),x(G(x)H(x))結(jié)論：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(x)④⑥假言三段論⑧H(x)②⑦假言推理⑨xH(x)⑧+33第33頁，共37頁，2023年，2月20日，星期一練習(xí)44.在自然推理系統(tǒng)NL中，構(gòu)造推理的證明．