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

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

(Q1x1)(Q2x2)…(QKxK)B

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

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

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

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

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))假設公式中有約束變元重復出現(xiàn)，或者與公式中的自由變元重名，那么將公式中的約束變元改名前束范式不是唯一的30六月2023斯柯倫范式二、斯柯倫范式前束范式的缺點是：

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

將前束范式的首標中的量詞進行排列，

每個存在量詞均放到全稱量詞的前面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自由變元代入規(guī)那么自由變元代入規(guī)那么：對公式中的某個自由出現(xiàn)的個體變元，可以用個體常元或與整個公式中所有約束變元不同的個體變元去代入，而且是處處代入。A(x)可以用項t代入，條件是x不出現(xiàn)在項t所含的任意個體變元y的量詞(y)或(y)的轄域內(nèi)，稱項t對x是自由的。例如：A(x)=(y)(P(y)∧Q(x,y))

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

A(x)=(z)(P(z)∧Q(x,z))， 此時A(x)對y是自由的A(y)=(z)(P(z)∧Q(y,z))為什么不把(x)P(x)也都換y？代入規(guī)那么針對自由變元30六月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為任意個體常元

(x)A(x)A(y) y為任意變元，

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

由于x沒有出現(xiàn)在(y)的轄域內(nèi)，所以A(x)對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)，因此需要對約束變元y改名 (x)A(x)經(jīng)過改名得到：(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：蘇格拉底題目符號化為：(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有下面前提：同事之間總是有工作矛盾的張平和李明沒有工作矛盾問：能得到什么結論？解：令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結論是：張平和李明不是同事全稱量詞的消去規(guī)那么UI/USP(x,y)：x和y是同事，Q(x,y)：x和y是有工作矛盾的

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

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

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

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

y不能是前提或居先推導中、或(x)A(x)中的自由變元注意：y只是一個暫時、說明上的自由變元容易出錯！重點掌握A(y)只是新引入的暫時假設，它不是對y的一切值都成立的。30六月2023存在量詞的消去規(guī)那么EI/ES例2.15考察下面推論是否符合規(guī)那么？個體域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不能在前提或居先推導中、或(x)A(x)中出現(xiàn)

y不能是前提或居先推導中、或(x)A(x)中的自由變元消去存在量詞所新引入的變元，在之前不能出現(xiàn)過。30六月2023存在量詞的消去規(guī)那么EI/ES個體域DI是全體實數(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)只是臨時引入的一個假設前提，

不能作為結論z是(2)中的自由變元c不能在前提或居先推導中、或(x)A(x)中出現(xiàn)

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

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

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

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

假設A(x)為推導行的公式，x是由EI引入的，那么不能用x以外的個體變元作為約束變元30六月2023存在量詞的產(chǎn)生規(guī)那么EG例2.16考察下面推論是否符合規(guī)那么？個體域DI是全體實數(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)對y是自由的規(guī)那么成立條件：

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

x不是由EI引入

由EI引入的其他變元，不能出現(xiàn)在A(x)中30六月2023全稱量詞的產(chǎn)生規(guī)那么UG例2.17考察下面推論是否符合規(guī)那么？個體域DI是全體實數(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主要用于推導過程中刪除量詞UG和EG主要用于使結論呈量化形式注意：使用EI而產(chǎn)生的自由變元不能保存在結論中，因為它只是暫時的假設，在推導結束之前，必須使用EG規(guī)那么使之成為約束變元謂詞邏輯的推理30六月2023例2.20證明(x)Q(x)是(x)(P(x)Q(x))和(x)P(x)的有效結論(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)謂詞邏輯的推理僅由謂詞與個體變元還不能構成命題，所以需要產(chǎn)生量詞。30六月2023例2.20證明(x)Q(x)是(x)(P(x)Q(x))和(x)P(x)的有效結論 注意：下面推理是否有效？(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)中的自由變元30六月2023例2.21證明或否認下面推理：每棵松樹都是針葉松每一冬季落葉的樹都是非針葉松所以，每一冬季落葉的樹都不是松樹解：令P(x)：x是松樹，Q(x)：x是針葉松，

R(x)：x是冬季落葉的樹題目：(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是松樹，Q(x)：x是針葉松，

R(x)：x是冬季落葉的樹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〔假設前提〕(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)推出矛盾，因此假設不成立。證畢。謂詞邏輯的推理(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)中的自由變元消去時先消去存在量詞，再消去全稱量詞30六月2023例2.23證明或否認下面推理：每個大學教師都是知識分子有些知識分子有怪脾氣所以，有些大學老師有怪脾氣解：令P(x)：x是大學教師，Q(x)：x是知識分子

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))我們知道該論證應當是無效的，要證明論證無效，只要給出一個解釋證明蘊涵式不是永真式即可取論域DI為整數(shù)，P(x)：x=2，Q(x)：x是偶數(shù)，

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

R(x)：x有怪脾氣30六月2023習題19構造證明以下各式(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習題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習題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習題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習題22(1)符號化以下各命題，并給出構造推理證明。每一個自然數(shù)不是奇數(shù)就是偶數(shù)

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

并不是所有自然數(shù)都能被2整除所以：有的自然數(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習題22(1)前提：(x)(N(x)O(x)E(x)),(x)(N(x)(E(x)

T(x))), (x)(N(x)T(x)) 結論：(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習題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習題22(2)符號化以下各命題，并給出構造推理證明。如果一個人怕困難，那么他就不會獲得成功

每個人或者獲得成功，或者失敗過

有些人未曾失敗過所以：有些人不怕困難設： 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習題22(2)前提：(x)(P(x)∧D(x)

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

(x)(P(x)∧

F(x)) 結論：(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習題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習題22(3)符號化以下各命題，并給出構造推理證明。每個科學工作者都是刻苦鉆研的每個刻