離散數(shù)學高等教育出版社屈婉玲課件

離散數(shù)學高等教育出版社屈婉玲離散數(shù)學高等教育出版社屈婉玲5.1一階邏輯等值式與置換規(guī)則定義5.1設A,B是兩個謂詞公式,如果A

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

B,并稱A

B是等值式基本等值式第一組命題邏輯中16組基本等值式的代換實例

例如，

xF(x)xF(x),

xF(x)

yG(y)

xF(x)

yG(y)等第二組(1)消去量詞等值式

設D={a1,a2,…,an}①

xA(x)

A(a1)

A(a2)

…

A(an)②

xA(x)

A(a1)

A(a2)

…

A(an)25.1一階邏輯等值式與置換規(guī)則定義5.1設A,B是兩離散數(shù)學高等教育出版社屈婉玲課件離散數(shù)學高等教育出版社屈婉玲課件置換規(guī)則、換名規(guī)則、代替規(guī)則1.置換規(guī)則設

(A)是含A的公式,那么,若A

B,則

(A)

(B).2.換名規(guī)則設A為一公式，將A中某量詞轄域中個體變項的所有約束出現(xiàn)及相應的指導變元換成該量詞轄域中未曾出現(xiàn)過的個體變項符號，其余部分不變，設所得公式為A

，則A

A.3.代替規(guī)則設A為一公式，將A中某個個體變項的所有自由出現(xiàn)用A中未曾出現(xiàn)過的個體變項符號代替，其余部分不變，設所得公式為A

，則A

A.5置換規(guī)則、換名規(guī)則、代替規(guī)則1.置換規(guī)則5實例例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))置換6實例例1將下面命題用兩種形式符號化,并證明兩者等值:解實例(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實例(2)不是所有的人都愛看電影解令F(x)：x是人，G實例例2將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)的個體變項:

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ī)則

x

t(F(x,y,z)

G(x,t,z))

轄域擴張等值式或者

x(F(x,y,z)

yG(x,y,z))

x(F(x,u,z)

yG(x,y,z))

代替規(guī)則

x

y(F(x,u,z)

G(x,y,z))

轄域擴張等值式8實例例2將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)解實例例3設個體域D={a,b,c},消去下述公式中的量詞:(1)

x

y(F(x)G(y))解x

y(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實例例3設個體域D={a,b,c},消去下述公式中的量詞實例解法二

x

y(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實例(2)

x

yF(x,y)

x

yF(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實例(2)xyF(x,y)xyF(5.2一階邏輯前束范式定義5.2設A為一個一階邏輯公式，若A具有如下形式Q1x1Q2x2…QkxkB則稱A為前束范式，其中Qi(1

i

k)為

或

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

x

(F(x)

G(x))

x

y(F(x)

(G(y)

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

x(F(x)

G(x))

x(F(x)

y(G(y)

H(x,y)))不是前束范式，125.2一階邏輯前束范式定義5.2設A為一個一階邏輯公式前束范式存在定理定理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前束范式存在定理定理5.1（前束范式存在定理）例4求下列求前束范式的實例(2)

xF(x)

xG(x)解

xF(x)

xG(x)

xF(x)

x

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

x(F(x)

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

xF(x)

xG(x)

xF(x)

x

G(x)量詞否定等值式

xF(x)

y

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

x

y(F(x)

G(y))轄域收縮擴張規(guī)則14求前束范式的實例(2)xF(x)xG(x)解求前束范式的實例(3)

xF(x)

y(G(x,y)

H(y))或

xF(x)

y(G(z,y)

H(y))代替規(guī)則

x

y(F(x)

(G(z,y)

H(y)))解

xF(x)

y(G(x,y)

H(y))

zF(z)

y(G(x,y)

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

z

y(F(z)

(G(x,y)

H(y)))轄域收縮擴張規(guī)則15求前束范式的實例(3)xF(x)y(G(x,y)5.3一階邏輯的推論理論推理的形式結(jié)構(gòu)1.A1

A2

Ak

B若次式是永真式,則稱推理正確,記作A1

A2

Ak

B2.前提:A1,A2,,Ak

結(jié)論:B推理定理:永真式的蘊涵式165.3一階邏輯的推論理論推理的形式結(jié)構(gòu)16推理定理第一組命題邏輯推理定理的代換實例如,

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)17推理定理第一組命題邏輯推理定理的代換實例17量詞消去引入規(guī)則1.全稱量詞消去規(guī)則(-)

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

其中x是個體變項符號,且不在前提的任何公式中自由出現(xiàn)

xA(x)

A(y)

xA(x)

A(c)A(x)

xA(x)18量詞消去引入規(guī)則1.全稱量詞消去規(guī)則(-)xA(x)量詞消去引入規(guī)則3.存在量詞消去規(guī)則(-)

其中x是個體變項符號,且不在前提的任何公式和B中自由出現(xiàn)A(x)B

xA(x)B19量詞消去引入規(guī)則3.存在量詞消去規(guī)則(-)A量詞消去引入規(guī)則4.存在量詞引入消去規(guī)則(+)

或或其中x,y是個體變項符號,c是個體常項符號,且在A中y和c不在

x和x的轄域內(nèi)自由出現(xiàn).B

A(y)

B

xA(x)B

A(c)

B

xA(x)A(y)

xA(x)A(c)

xA(x)20量詞消去引入規(guī)則4.存在量詞引入消去規(guī)則(+)自然推理系統(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自然推理系統(tǒng)NL定義5.3自然推理系統(tǒng)NL定義如下:自然推理系統(tǒng)NL(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)-規(guī)則(13)+規(guī)則(14)-規(guī)則(15)+規(guī)則推理的證明22自然推理系統(tǒng)NL(8)假言三段論規(guī)則22構(gòu)造推理證明的實例例5在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明,取個體域R:任何自然數(shù)都是整數(shù).存在自然數(shù).所以,存在整數(shù).解設F(x):x是自然數(shù),G(x):x是整數(shù).前提:

x(F(x)G(x)),xF(x)結(jié)論:xG(x)證明:①

x(F(x)G(x))前提引入②F(x)G(x)①-③F(x)xG(x)②+④

xF(x)xG(x)③-⑤

xF(x)前提引入⑥

xG(x)④⑤假言推理

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

x(F(x)H(x)),

x(G(x)H(x))結(jié)論:x(G(x)F(x))證明:①

x(F(x)H(x))前提引入②

x(F(x)H(x))①置換③

x(F(x)H(x))②置換④F(x)H(x)③-24構(gòu)造推理證明的實例例6在自然推理系統(tǒng)NL中構(gòu)造下面推理構(gòu)造推理證明的實例⑤

x(G(x)H(x))

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

⑦H(x)F(x)④置換⑧G(x)F(x)⑥⑦假言三段論⑨

x(G(x)F(x))⑧+25構(gòu)造推理證明的實例⑤x(G(x)H(x))重要提示要特別注意使用-、+、-、+規(guī)則的條件.反例1.對A=x

yF(x,y)使用-規(guī)則,推得B=yF(y,y).取解釋I:個體域為R,在I下A被解釋為

x

y(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:個體域為Z,在I下前提為真,結(jié)論為假,從而推理不正確26重要提示要特別注意使用-、+、-、+規(guī)則的條件.反例反例2(續(xù))“證明”:①P(x)

Q(x)前提引入②P(x)前提引入③Q(x)①②假言推理④

xQ(x)③+錯誤原因:在④使用+規(guī)則,而x在前提的公式中自由出現(xiàn).27反例2(續(xù))“證明”:27第五章習題課主要內(nèi)容一階邏輯等值式基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式推理的形式結(jié)構(gòu)自然推理系統(tǒng)NL推理定律、推理規(guī)則28第五章習題課主要內(nèi)容28基本要求深刻理解并牢記一階邏輯中的重要等值式,并能準確而熟練地應用它們．熟練正確地使用置換規(guī)則、換名規(guī)則、代替規(guī)則．熟練地求出給定公式的前束范式．深刻理解自然推理系統(tǒng)NL的定義，牢記NL中的各條推理規(guī)則，特別是注意使用

、

+、

+、

4條推理規(guī)則的條件．能正確地給出有效推理的證明．29基本要求深刻理解并牢記一階邏輯中的重要等值式,并能準確而熟練習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)030練習11.給定解釋I如下:解xF(f(x))y練習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))

z

y(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))

x

y(F(x)

(G(z,y)

H(z,y)))31練習22.求下述公式的前束范式:解使用換名規(guī)則,練習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)⑥置換32練習33.構(gòu)造下面推理的證明:證明：32練習3(續(xù))(2)前提：

x(F(x)

G(x)),

xG(x)結(jié)論：

xF(x)證明：用歸謬法①

xF(x)結(jié)論否定引入②

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)⑦⑨合取引入33練習3(續(xù))(2)前提：x(F(x)G(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