數(shù)學(xué)02-謂詞邏輯-16-17

30六月2023第六節(jié)謂詞公式范式 第六節(jié)謂詞公式范式一、前束范式定義：一個(gè)公式A如果有如下形式

(Q1x1)(Q2x2)…(QKxK)B

其中，Qi是或，B為不含量詞的公式

稱它為A的為前束范式，(Q1x1)(Q2x2)…(QKxK)稱作首標(biāo)特點(diǎn)： 所有量詞均非否認(rèn)地出現(xiàn)在公式最前面，

且轄域一直延伸到公式末尾30六月2023前束范式前束范式存在定理：

Lp中任意公式A都有與之等價(jià)的前束范式證明：〔略〕

P4330六月2023前束范式例2.11：

將公式((x)P(x)

∨(y)Q(y))(x)R(x)化為前束范式解：公式 ((x)P(x)

∨(y)Q(y))

(z)R(z)

(x)

(P(x)

∨(y)Q(y))

(z)R(z)

(x)(y)(P(x)

∨

Q(y))

(z)R(z) (x)(y)

((P(x)∨Q(y))

(z)R(z))

(x)(y)(z)((P(x)

∨

Q(y))

R(z))解：〔公式(x)(y)(z)((P(x)∨Q(y))R(z))〕公式 ((x)P(x)∨(y)Q(y))(z)R(z) (y)((x)P(x)∨Q(y))(z)R(z) (y)(x)(P(x)∨Q(y))(z)R(z) (y)(x)(z)((P(x)∨Q(y))R(z))假設(shè)公式中有約束變?cè)貜?fù)出現(xiàn)，或者與公式中的自由變?cè)孛?，那么將公式中的約束變?cè)拿笆妒讲皇俏ㄒ坏?0六月2023斯柯倫范式二、斯柯倫范式前束范式的缺點(diǎn)是：

量詞的排列無(wú)一定規(guī)那么，會(huì)形成很多形式的前束范式斯柯倫范式規(guī)定：

將前束范式的首標(biāo)中的量詞進(jìn)行排列，

每個(gè)存在量詞均放到全稱量詞的前面30六月2023斯柯林范式例2.12將公式(x)((P(x)∨(y)Q(y,z))(z)R(y,z))化為斯柯林范式解：公式(x)((P(x)∨(u)Q(u,z))

(v)R(y,v))

(x)((P(x)∨(u)Q(u,z))∨(v)R(y,v))

(x)((P(x)∧(u)

Q(u,z))∨(v)

R(y,v))

(u)(v)(x)(P(x)∧

Q(u,z)∨

R(y,v))30六月2023自由變?cè)胍?guī)那么自由變?cè)胍?guī)那么：對(duì)公式中的某個(gè)自由出現(xiàn)的個(gè)體變?cè)?，可以用個(gè)體常元或與整個(gè)公式中所有約束變?cè)煌膫€(gè)體變?cè)ゴ?，而且是處處代入。A(x)可以用項(xiàng)t代入，條件是x不出現(xiàn)在項(xiàng)t所含的任意個(gè)體變?cè)獃的量詞(y)或(y)的轄域內(nèi)，稱項(xiàng)t對(duì)x是自由的。例如：A(x)=(y)(P(y)∧Q(x,y))

項(xiàng)f(y,z)對(duì)x不是自由的，而項(xiàng)f(x,z)對(duì)x是自由的。t要代替x出現(xiàn)，如果t中有一個(gè)個(gè)體變?cè)獃，它是受量詞約束的，那么原本自由的x，被t代替后，卻不完全自由了Q(f(y,z),y))Q(f(x,z),y))雖然f〔x，z〕出現(xiàn)在了(y)的轄域內(nèi)，但是f〔x，z〕并不包含個(gè)體變?cè)獃，所以不受影響。30六月2023第七節(jié)謂詞邏輯的推理理論引言Lp是Ls的深化開(kāi)展，因此Ls的推理理論在Lp中幾乎可完全照搬。在Lp中，某些前提和結(jié)論可能受到量詞的約束，為確立前提和結(jié)論之間的內(nèi)部聯(lián)系，有必要削去量詞和添加量詞，因此正確理解和運(yùn)用有關(guān)量詞規(guī)那么是關(guān)鍵所在。必要準(zhǔn)備：A(x)對(duì)y是自由的。目的是：允許用y代入x后得到A(y)，它不改變?cè)瓉?lái)公式A(x)的約束關(guān)系(x)A(x)A(y)30六月2023第七節(jié)謂詞邏輯的推理理論 第七節(jié)謂詞邏輯的推理理論一、A(x)對(duì)y是自由的定義：在謂詞公式A(x)中，假設(shè)x不自由出現(xiàn)在量詞(y)或(y)的轄域內(nèi)，那么稱A(x)對(duì)于y是自由的。假設(shè)y在A(x)中不是約束出現(xiàn)，那么A(x)對(duì)于y一定是自由的。考察目的：使y代入到A(x)中得到A(y)，不會(huì)改變?cè)紸(x)的約束關(guān)系。30六月2023A(x)對(duì)y是自由的例2.13A(x)是以下公式，考察A(x)對(duì)y是否自由，并求A(y)A(x)=(y)P(y)∧Q(x) A(x)對(duì)y是自由的。A(y)=(y)P(y)∧Q(y)A(x)=(y)P(y)∧Q(x,y) A(x)對(duì)y是自由的。A(y)=(y)P(y)∧Q(y,y)30六月2023A(x)對(duì)y是自由的A(x)=(x)P(x)∧Q(x,y) A(x)對(duì)y是自由的。A(y)=(x)P(x)∧Q(y,y)A(x)=(y)(P(y)∧Q(x,y)) A(x)對(duì)y不是自由的。 此時(shí)可以將A(x)中的約束變?cè)獃進(jìn)行改名：

A(x)=(z)(P(z)∧Q(x,z))， 此時(shí)A(x)對(duì)y是自由的A(y)=(z)(P(z)∧Q(y,z))為什么不把(x)P(x)也都換y？代入規(guī)那么針對(duì)自由變?cè)?0六月2023謂詞邏輯的推理理論二、謂詞邏輯的推理理論全稱量詞的消去規(guī)那么UI/US存在量詞的消去規(guī)那么EI/ES存在量詞的產(chǎn)生規(guī)那么EG全稱量詞的產(chǎn)生規(guī)那么UG30六月2023全稱量詞的消去規(guī)那么UI/US全稱量詞的消去規(guī)那么UI/US也叫作全稱指定規(guī)那么(UniversalSpecification)規(guī)那么內(nèi)容：

(x)A(x)A(c) 其中c為任意個(gè)體常元

(x)A(x)A(y) y為任意變?cè)?/p>

且A(x)對(duì)y是自由的該規(guī)那么用于刪除全稱量詞30六月2023全稱量詞的消去規(guī)那么UI/US例2.14考察下面公式(x)A(x)，能推導(dǎo)出怎樣的A(y)來(lái)？(x)A(x)=(x)((y)P(y)∧Q(x,y))

由于x沒(méi)有出現(xiàn)在(y)的轄域內(nèi)，所以A(x)對(duì)y是自由的

A(y)=(y)P(y)∧Q(y,y)

即(x)((y)P(y)∧Q(x,y))

(y)P(y)∧Q(y,y)(x)A(x)A(y)；消去了量詞(x)30六月2023全稱量詞的消去規(guī)那么UI/US(x)A(x)=(x)((y)P(x,y)∧Q(x,y))

由于x出現(xiàn)在(y)的轄域內(nèi)，因此需要對(duì)約束變?cè)獃改名 (x)A(x)經(jīng)過(guò)改名得到：(x)((z)P(x,z)∧Q(x,y))

A(y)=(z)P(y,z)∧Q(y,y)

即(x)((y)P(y,z)∧Q(x,y))(z)P(y,z)∧Q(y,y)30六月2023例2.18證明以下論證：所有人都是要死的蘇格拉底是人所以蘇格拉底是要死的解：令P(x)：x是人，D(x)：x是要死的，a：蘇格拉底題目符號(hào)化為：(x)(P(x)D(x)),P(a)

D(a)全稱量詞的消去規(guī)那么UI/US30六月2023(x)(P(x)D(x)),P(a)

D(a)(1) (x)(P(x)D(x)) P(2) P(a)D(a) UI(1)(3) P(a) P(4) D(a) T(2)(3)I8全稱量詞的消去規(guī)那么UI/USP(x)：x是人，D(x)：x是要死的，a：蘇格拉底30六月2023例2.19有下面前提：同事之間總是有工作矛盾的張平和李明沒(méi)有工作矛盾問(wèn)：能得到什么結(jié)論？解：令P(x,y)：x和y是同事，Q(x,y)：x和y是有工作矛盾的

a：張平，b：李明前提：(x)(y)(P(x,y)Q(x,y)),Q(a,b)全稱量詞的消去規(guī)那么UI/US30六月2023(x)(y)(P(x,y)Q(x,y)),Q(a,b)(1) (x)(y)(P(x,y)Q(x,y)) P(2) (y)(P(a,y)Q(a,y)) UI(1)(3) P(a,b)Q(a,b) UI(2)(4) Q(a,b) P(5) P(a,b) T(3)(4)I9結(jié)論是：張平和李明不是同事全稱量詞的消去規(guī)那么UI/USP(x,y)：x和y是同事，Q(x,y)：x和y是有工作矛盾的

a：張平，b：李明消去時(shí)通常要先消去最外面的量詞，消去后要以一個(gè)常元代替原式中的變?cè)?0六月2023存在量詞的消去規(guī)那么EI/ES存在量詞的消去規(guī)那么EI/ES也叫作存在指定規(guī)那么(ExistentialSpecification)規(guī)那么內(nèi)容：

(x)A(x)A(c) 其中c為某指定個(gè)體常元

(x)A(x)A(y) A(x)對(duì)y是自由的規(guī)那么成立條件：

c不能在前提或居先推導(dǎo)中、或(x)A(x)中出現(xiàn)

y不能是前提或居先推導(dǎo)中、或(x)A(x)中的自由變?cè)⒁猓簓只是一個(gè)暫時(shí)、說(shuō)明上的自由變?cè)菀壮鲥e(cuò)！重點(diǎn)掌握A(y)只是新引入的暫時(shí)假設(shè)，它不是對(duì)y的一切值都成立的。30六月2023存在量詞的消去規(guī)那么EI/ES例2.15考察下面推論是否符合規(guī)那么？個(gè)體域DI是自然數(shù)，O(x)：x是奇數(shù)，E(x)：x是偶數(shù)前提：(x)O(x)，(x)E(x)(1) (x)O(x) P(2) O(y) EI(1)(3) (x)E(x) P(4) E(y) EI(3)(5) O(y)∧E(y) T(2)(4)y是(2)中的自由變?cè)猚不能在前提或居先推導(dǎo)中、或(x)A(x)中出現(xiàn)

y不能是前提或居先推導(dǎo)中、或(x)A(x)中的自由變?cè)ゴ嬖诹吭~所新引入的變?cè)?，在之前不能出現(xiàn)過(guò)。30六月2023存在量詞的消去規(guī)那么EI/ES個(gè)體域DI是全體實(shí)數(shù)，G(x,y)：x>y前提：(x)(y)G(x,y)(1) (x)(y)G(x,y) P(2) (y)G(z,y) UI(1)(3) G(z,z) EI(2)(3) G(z,c) EI(2)(4) (x)G(z,x)

A(c)或A(y)只是臨時(shí)引入的一個(gè)假設(shè)前提，

不能作為結(jié)論z是(2)中的自由變?cè)猚不能在前提或居先推導(dǎo)中、或(x)A(x)中出現(xiàn)

y不能是前提或居先推導(dǎo)中、或(x)A(x)中的自由變?cè)?0六月2023存在量詞的產(chǎn)生規(guī)那么EG存在量詞的產(chǎn)生規(guī)那么EG也叫作存在推廣規(guī)那么(ExistentialGeneralization)規(guī)那么內(nèi)容：

A(c)(y)A(y) 其中c為某指定個(gè)體常元

A(x)(y)A(y) A(x)對(duì)y是自由的規(guī)那么成立條件：

y不在A(c)或A(x)中出現(xiàn)

假設(shè)A(x)為推導(dǎo)行的公式，x是由EI引入的，那么不能用x以外的個(gè)體變?cè)鳛榧s束變?cè)?0六月2023存在量詞的產(chǎn)生規(guī)那么EG例2.16考察下面推論是否符合規(guī)那么？個(gè)體域DI是全體實(shí)數(shù)，G(x,y)：x>y前提：(x)(y)G(x,y)(1) (x)(y)G(x,y) P(2) (y)G(z,y) UI(1)(3) (y)(y)G(y,y) EG(2)y在(2)中出現(xiàn)(3) G(z,u) EI(2)(4) (z)G(z,z) EG(3’)z在(3)中出現(xiàn)30六月2023全稱量詞的產(chǎn)生規(guī)那么UG全稱量詞的產(chǎn)生規(guī)那么UG也叫作全稱推廣規(guī)那么(UniversalGeneralization)規(guī)那么內(nèi)容：

A(x)(y)A(y) A(x)對(duì)y是自由的規(guī)那么成立條件：

前提A(x)對(duì)于x的任意取值都成立

x不是由EI引入

由EI引入的其他變?cè)?，不能出現(xiàn)在A(x)中30六月2023全稱量詞的產(chǎn)生規(guī)那么UG例2.17考察下面推論是否符合規(guī)那么？個(gè)體域DI是全體實(shí)數(shù)，G(x,y)：x>y前提：(x)(y)G(x,y)(1) (x)(y)G(x,y) P(2) (y)G(z,y) UI(1)(3) G(z,a) EI(2)(4) (x)G(x,a) UG(3)(5) (y)(x)G(x,y) EG(4)公式中含有由EI引入的a30六月2023謂詞邏輯的推理：UI和EI主要用于推導(dǎo)過(guò)程中刪除量詞UG和EG主要用于使結(jié)論呈量化形式注意：使用EI而產(chǎn)生的自由變?cè)荒鼙４嬖诮Y(jié)論中，因?yàn)樗皇菚簳r(shí)的假設(shè)，在推導(dǎo)結(jié)束之前，必須使用EG規(guī)那么使之成為約束變?cè)^詞邏輯的推理30六月2023例2.20證明(x)Q(x)是(x)(P(x)Q(x))和(x)P(x)的有效結(jié)論(1) (x)P(x) P(2) P(y) EI(1)

(3) (x)(P(x)Q(x)) P(4) P(y)Q(y) UI(3)(5) Q(y) T(2)(4)I8(6) (x)Q(x) EG(5)謂詞邏輯的推理僅由謂詞與個(gè)體變?cè)€不能構(gòu)成命題，所以需要產(chǎn)生量詞。30六月2023例2.20證明(x)Q(x)是(x)(P(x)Q(x))和(x)P(x)的有效結(jié)論 注意：下面推理是否有效？(1) (x)(P(x)Q(x))

P(2) P(y)Q(y) UI(1)

(3) (x)P(x) P(4) P(y) EI(3)(5) Q(y) T(2)(4)I8(6) (x)Q(x) EG(5)謂詞邏輯的推理y是(2)中的自由變?cè)?0六月2023例2.21證明或否認(rèn)下面推理：每棵松樹(shù)都是針葉松每一冬季落葉的樹(shù)都是非針葉松所以，每一冬季落葉的樹(shù)都不是松樹(shù)解：令P(x)：x是松樹(shù)，Q(x)：x是針葉松，

R(x)：x是冬季落葉的樹(shù)題目：(x)(P(x)Q(x)),(x)(R(x)Q(x))

(x)(R(x)P(x))謂詞邏輯的推理30六月2023(x)(P(x)Q(x)),(x)(R(x)Q(x))

(x)(R(x)P(x))(1) (x)(P(x)Q(x))

P(2) P(y)Q(y) UI(1)(3) Q(y)P(y) T(2)E11(4) (x)(R(x)Q(x))

P(5) R(y)Q(y) UI(4)(6) R(y)P(y) T(3)(5)I11(7) (x)(R(x)P(x)) UG(6)謂詞邏輯的推理P(x)：x是松樹(shù)，Q(x)：x是針葉松，

R(x)：x是冬季落葉的樹(shù)30六月2023例2.22證明(x)(P(x)∨Q(x))

(x)P(x)∨(x)Q(x)證明：(1) (x)(P(x)∨Q(x))

P(2) (x)(P(x)

Q(x)) T(1)E11

(3) (x)P(x)

(x)Q(x) T(2)Q(4)

(x)P(x)

(x)Q(x) T(3)Q(5) (x)P(x)∨(x)Q(x)

T(4)E11謂詞邏輯的推理(x)(A(x)

B(x))(x)

A(x)

(x)

B(x)(p43)30六月2023例2.22證明(x)(P(x)∨Q(x))(x)P(x)∨(x)Q(x)證明：用反證法：(1) ((x)P(x)∨(x)Q(x)) P〔假設(shè)前提〕(2) (x)P(x)∧(x)Q(x) T(1)E5 (3) (x)P(x) T(2)I1(4) (x)P(x) T(3)Q(5) (x)Q(x) T(2)I2(6) (x)Q(x) T(5)Q謂詞邏輯的推理30六月2023(7)

P(y) EI(4)(8)

Q(y) UI(6)

(9)

P(y)∧

Q(y) T(7)(8)(10) (P(y)∨Q(y)) T(9)E5(11) (x)(P(x)∨Q(x))

P(12) P(y)∨Q(y) UI(11)(13) (P(y)∨Q(y))∧(P(y)∨Q(y)) T(10)(12)推出矛盾，因此假設(shè)不成立。證畢。謂詞邏輯的推理(4) (x)

P(x) T(3)Q

(6) (x)

Q(x) T(5)Q(7)

Q(y) UI(6)(8)

P(y) EI(4)y是(7)中的自由變?cè)r(shí)先消去存在量詞，再消去全稱量詞30六月2023例2.23證明或否認(rèn)下面推理：每個(gè)大學(xué)教師都是知識(shí)分子有些知識(shí)分子有怪脾氣所以，有些大學(xué)老師有怪脾氣解：令P(x)：x是大學(xué)教師，Q(x)：x是知識(shí)分子

R(x)：x有怪脾氣題目：(x)(P(x)Q(x)),(x)(Q(x)∧R(x))

(x)(P(x)∧R(x))謂詞邏輯的推理30六月2023(x)(P(x)Q(x)),(x)(Q(x)∧R(x))(x)(P(x)∧R(x))我們知道該論證應(yīng)當(dāng)是無(wú)效的，要證明論證無(wú)效，只要給出一個(gè)解釋證明蘊(yùn)涵式不是永真式即可取論域DI為整數(shù)，P(x)：x=2，Q(x)：x是偶數(shù)，

R(x)：x是合數(shù)，那么前件為真，而后件為假。故可證得：該推論無(wú)效。謂詞邏輯的推理P(x)：x是大學(xué)教師，Q(x)：x是知識(shí)分子

R(x)：x有怪脾氣30六月2023習(xí)題19構(gòu)造證明以下各式(x)(P(x)Q(x)),(x)(Q(x)R(x))

(x)(P(x)R(x))(x)(H(x)M(x)),(x)H(x)

(x)M(x)(x)(P(x)∧Q(x))

(x)P(x)∧(x)Q(x)30六月2023習(xí)題19證明：(1)

(x)(P(x)Q(x))

P

(2)

P(y)Q(y) UI(1)

(3)

(x)(Q(x)R(x))

P

(4)

Q(y)R(y) UI(3)

(5)

P(y)R(y) T(2)(4)I11 (6)

(x)(P(x)R(x))

UG(5)1) (x)(P(x)Q(x)),(x)(Q(x)R(x))

(x)(P(x)R(x))30六月2023習(xí)題19證明：(1)

(x)H(x)

P

(2)

H(y) EI(1)

(3)

(x)(H(x)M(x))

P

(4)

H(y)M(y) UI(3)

(5)

M(y) T(2)(4)I8 (6)

(x)M(x)

EG(5)2) (x)(H(x)M(x)),(x)H(x)(x)M(x)30六月2023習(xí)題19證明：(1)

(x)(P(x)∧Q(x))

P

(2)

P(y)∧Q(y)

EI(1)

(3)

P(y)

T(2)I1

(4)

(x)P(x)

EG(3)

(5)

Q(y) T(2)I2 (6)

(x)Q(x)

EG(5) (7)

(x)P(x)∧(x)Q(x)

T(4)(6)3) (x)(P(x)∧Q(x))(x)P(x)∧(x)Q(x)30六月2023習(xí)題22(1)符號(hào)化以下各命題，并給出構(gòu)造推理證明。每一個(gè)自然數(shù)不是奇數(shù)就是偶數(shù)

自然數(shù)是偶數(shù)當(dāng)且僅當(dāng)它能被2整除

并不是所有自然數(shù)都能被2整除所以：有的自然數(shù)是奇數(shù)設(shè)： N(x)：x是自然數(shù)，O(x)：x是奇數(shù)， E(x)：x是偶數(shù)，T(x)：x能被2整除(x)(N(x)O(x)E(x))(x)(N(x)(E(x)

T(x)))(x)(N(x)T(x))(x)(N(x)∧O(x))30六月2023習(xí)題22(1)前提：(x)(N(x)O(x)E(x)),(x)(N(x)(E(x)

T(x))), (x)(N(x)T(x)) 結(jié)論：(x)(N(x)∧O(x))證明： (1)

(x)(N(x)T(x))

P

(2)

(x)(N(x)∨T(x)) T(1)E11

(3) (x)(N(x)∧T(x)) T(2)Q,E1,E5

(4)

N(y)∧T(y) EI(3)

(5)

N(y) T(4)I1 (6)

(x)(N(x)(E(x)

T(x)))

P (7)

N(y)(E(y)

T(y)) UI(6) (8)

E(y)

T(y) T(5)(7)I8 (9)

E(y)

T(y) T(8)I1830六月2023習(xí)題22(1)

(10)

T(y) T(4)I1

(11)

E(y) T(9)(10)I9

(12)

(x)(N(x)O(x)E(x))

P

(13)

N(y)O(y)E(y) UI(12)

(14)

O(y)E(y) T(5)(13)I8 (15)

(O(y)

E(y)) T(14) (16)

O(y)E(y) T(15)E12 (17)

O(y) T(11)(16)I8 (18)

N(y)∧

O(y) T(5)(17)

(19)

(x)(N(x)∧O(x))

EG(18)(4)

N(y)∧T(y) EI(3)(5)

N(y) T(4)E1(9)

E(y)

T(y) T(8)E1830六月2023習(xí)題22(2)符號(hào)化以下各命題，并給出構(gòu)造推理證明。如果一個(gè)人怕困難，那么他就不會(huì)獲得成功

每個(gè)人或者獲得成功，或者失敗過(guò)

有些人未曾失敗過(guò)所以：有些人不怕困難設(shè)： P(x)：x是人，D(x)：x怕困難， S(x)：x成功，F(xiàn)(x)：x失敗(x)(P(x)∧

D(x)

S(x))(x)(P(x)(S(x)∨

F(x)))(x)(P(x)∧

F(x))(x)(P(x)∧D(x))30六月2023習(xí)題22(2)前提：(x)(P(x)∧D(x)

S(x)),(x)(P(x)(S(x)∨F(x))),

(x)(P(x)∧

F(x)) 結(jié)論：(x)(P(x)∧D(x))證明： (1)

(x)(P(x)∧

F(x))

P

(2)

P(y)∧

F(y) EI(1)

(3)

P(y) T(2)I1

(4)

F(y) T(2)I1

(5)

(x)(P(x)(S(x)∨F(x)))

P (6)

P(y)(S(y)∨F(y)) UI(5) (7)

S(y)∨F(y) T(3)(6)I8 (8)

S(y) T(4)(7)I1030六月2023習(xí)題22(2)

(9)

(x)(P(x)∧D(x)

S(x))

P

(10)

P(y)∧D(y)

S(y) UI(1)

(11)

(P(y)∧D(y)) T(8)(10)I9

(12)

P(y)∨

D(y) T(11)E5

(13)

D(y) T(3)(12)I10 (14)

P(y)∧

D(y) T(3)(13) (15)

(x)(P(x)∧D(x))

EG(14)(3)

P(y) T(2)I1(8)

S(y) T(4)(7)I1030六月2023習(xí)題22(3)符號(hào)化以下各命題，并給出構(gòu)造推理證明。每個(gè)科學(xué)工作者都是刻苦鉆研的每個(gè)刻