数学02-谓词逻辑-16-17

30六月2023第六节谓词公式范式 第六节谓词公式范式一、前束范式定义：一个公式A如果有如下形式

(Q1x1)(Q2x2)…(QKxK)B

其中，Qi是或，B为不含量词的公式

称它为A的为前束范式，(Q1x1)(Q2x2)…(QKxK)称作首标特点： 所有量词均非否认地出现在公式最前面，

且辖域一直延伸到公式末尾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))假设公式中有约束变元重复出现，或者与公式中的自由变元重名，那么将公式中的约束变元改名前束范式不是唯一的30六月2023斯柯伦范式二、斯柯伦范式前束范式的缺点是：

量词的排列无一定规那么，会形成很多形式的前束范式斯柯伦范式规定：

将前束范式的首标中的量词进行排列，

每个存在量词均放到全称量词的前面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自由变元代入规那么自由变元代入规那么：对公式中的某个自由出现的个体变元，可以用个体常元或与整个公式中所有约束变元不同的个体变元去代入，而且是处处代入。A(x)可以用项t代入，条件是x不出现在项t所含的任意个体变元y的量词(y)或(y)的辖域内，称项t对x是自由的。例如：A(x)=(y)(P(y)∧Q(x,y))

项f(y,z)对x不是自由的，而项f(x,z)对x是自由的。t要代替x出现，如果t中有一个个体变元y，它是受量词约束的，那么原本自由的x，被t代替后，却不完全自由了Q(f(y,z),y))Q(f(x,z),y))虽然f〔x，z〕出现在了(y)的辖域内，但是f〔x，z〕并不包含个体变元y，所以不受影响。30六月2023第七节谓词逻辑的推理理论引言Lp是Ls的深化开展，因此Ls的推理理论在Lp中几乎可完全照搬。在Lp中，某些前提和结论可能受到量词的约束，为确立前提和结论之间的内部联系，有必要削去量词和添加量词，因此正确理解和运用有关量词规那么是关键所在。必要准备：A(x)对y是自由的。目的是：允许用y代入x后得到A(y)，它不改变原来公式A(x)的约束关系(x)A(x)A(y)30六月2023第七节谓词逻辑的推理理论 第七节谓词逻辑的推理理论一、A(x)对y是自由的定义：在谓词公式A(x)中，假设x不自由出现在量词(y)或(y)的辖域内，那么称A(x)对于y是自由的。假设y在A(x)中不是约束出现，那么A(x)对于y一定是自由的。考察目的：使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？代入规那么针对自由变元30六月2023谓词逻辑的推理理论二、谓词逻辑的推理理论全称量词的消去规那么UI/US存在量词的消去规那么EI/ES存在量词的产生规那么EG全称量词的产生规那么UG30六月2023全称量词的消去规那么UI/US全称量词的消去规那么UI/US也叫作全称指定规那么(UniversalSpecification)规那么内容：

(x)A(x)A(c) 其中c为任意个体常元

(x)A(x)A(y) y为任意变元，

且A(x)对y是自由的该规那么用于删除全称量词30六月2023全称量词的消去规那么UI/US例2.14考察下面公式(x)A(x)，能推导出怎样的A(y)来？(x)A(x)=(x)((y)P(y)∧Q(x,y))

由于x没有出现在(y)的辖域内，所以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全称量词的消去规那么UI/US(x)A(x)=(x)((y)P(x,y)∧Q(x,y))

由于x出现在(y)的辖域内，因此需要对约束变元y改名 (x)A(x)经过改名得到：(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)全称量词的消去规那么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全称量词的消去规那么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)全称量词的消去规那么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结论是：张平和李明不是同事全称量词的消去规那么UI/USP(x,y)：x和y是同事，Q(x,y)：x和y是有工作矛盾的

a：张平，b：李明消去时通常要先消去最外面的量词，消去后要以一个常元代替原式中的变元30六月2023存在量词的消去规那么EI/ES存在量词的消去规那么EI/ES也叫作存在指定规那么(ExistentialSpecification)规那么内容：

(x)A(x)A(c) 其中c为某指定个体常元

(x)A(x)A(y) A(x)对y是自由的规那么成立条件：

c不能在前提或居先推导中、或(x)A(x)中出现

y不能是前提或居先推导中、或(x)A(x)中的自由变元注意：y只是一个暂时、说明上的自由变元容易出错！重点掌握A(y)只是新引入的暂时假设，它不是对y的一切值都成立的。30六月2023存在量词的消去规那么EI/ES例2.15考察下面推论是否符合规那么？个体域DI是自然数，O(x)：x是奇数，E(x)：x是偶数前提：(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)中出现

y不能是前提或居先推导中、或(x)A(x)中的自由变元消去存在量词所新引入的变元，在之前不能出现过。30六月2023存在量词的消去规那么EI/ES个体域DI是全体实数，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)中出现

y不能是前提或居先推导中、或(x)A(x)中的自由变元30六月2023存在量词的产生规那么EG存在量词的产生规那么EG也叫作存在推广规那么(ExistentialGeneralization)规那么内容：

A(c)(y)A(y) 其中c为某指定个体常元

A(x)(y)A(y) A(x)对y是自由的规那么成立条件：

y不在A(c)或A(x)中出现

假设A(x)为推导行的公式，x是由EI引入的，那么不能用x以外的个体变元作为约束变元30六月2023存在量词的产生规那么EG例2.16考察下面推论是否符合规那么？个体域DI是全体实数，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)中出现(3) G(z,u) EI(2)(4) (z)G(z,z) EG(3’)z在(3)中出现30六月2023全称量词的产生规那么UG全称量词的产生规那么UG也叫作全称推广规那么(UniversalGeneralization)规那么内容：

A(x)(y)A(y) A(x)对y是自由的规那么成立条件：

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

x不是由EI引入

由EI引入的其他变元，不能出现在A(x)中30六月2023全称量词的产生规那么UG例2.17考察下面推论是否符合规那么？个体域DI是全体实数，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而产生的自由变元不能保存在结论中，因为它只是暂时的假设，在推导结束之前，必须使用EG规那么使之成为约束变元谓词逻辑的推理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)谓词逻辑的推理仅由谓词与个体变元还不能构成命题，所以需要产生量词。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为整数，P(x)：x=2，Q(x)：x是偶数，

R(x)：x是合数，那么前件为真，而后件为假。故可证得：该推论无效。谓词逻辑的推理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)符号化以下各命题，并给出构造推理证明。每一个自然数不是奇数就是偶数

自然数是偶数当且仅当它能被2整除

并不是所有自然数都能被2整除所以：有的自然数是奇数设： N(x)：x是自然数，O(x)：x是奇数， E(x)：x是偶数，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(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)符号化以下各命题，并给出构造推理证明。每个科学工作者都是刻苦钻研的每个刻