数学谓词逻辑学习教案.pptx

数学数学(shxu)谓词逻辑谓词逻辑第一页，共49页。07 07 二月二月 2023 2023前束范式(fn sh)前束范式前束范式(fn sh)(fn sh)存在定理：存在定理：LpLp中任意公式中任意公式A A都有与之等价的前束范式都有与之等价的前束范式(fn sh)(fn sh)证明：证明：（略）（略）P43P43第1页/共49页第二页，共49页。07 07 二月二月 2023 2023前束范式(fn sh)例例2.112.11：将公式将公式(gngsh)(gngsh)(x)P(x)x)P(x)(y)Q(y)y)Q(y)(x)R(x)x)R(x)化化为前束范式为前束范式解：解：公式公式 (x)P(x)(y)Q(y)(z z)R(z z)(x)x)(P(x)P(x)(y)Q(y)y)Q(y)(z)R(z)(x)x)(y)y)(P(x)P(x)Q(y)Q(y)(z)R(z)(x)x)(y)y)(P(x)(P(x)Q(y)Q(y)(z)R(z)(x)x)(y)y)(z)z)(P(x)P(x)Q(y)Q(y)R(z)R(z)解：解：（公式（公式(x)x)(y)y)(z)z)(P(x)P(x)Q(y)Q(y)R(z)R(z)）公式公式 (x)P(x)(y)Q(y)(z z)R(z z)(y)y)(x)P(x)x)P(x)Q(y)Q(y)(z)R(z)(y)y)(x)x)(P(x)P(x)Q(y)Q(y)(z)R(z)(y)y)(x)x)(z)z)(P(x)P(x)Q(y)Q(y)R(z)R(z)若公式中有约束变元重复出现，或者与公式中的自由变元重名，则将公式中的约束变元改名若公式中有约束变元重复出现，或者与公式中的自由变元重名，则将公式中的约束变元改名若公式中有约束变元重复出现，或者与公式中的自由变元重名，则将公式中的约束变元改名若公式中有约束变元重复出现，或者与公式中的自由变元重名，则将公式中的约束变元改名前束范式不是唯一的前束范式不是唯一的前束范式不是唯一的前束范式不是唯一的第2页/共49页第三页，共49页。07 07 二月二月 2023 2023斯柯伦范式(fn sh)二、斯柯伦范式二、斯柯伦范式前束范式的缺点是：前束范式的缺点是：量词的排列无一定规则，会形成很多形式量词的排列无一定规则，会形成很多形式(xngsh)(xngsh)的前束范式的前束范式斯柯伦范式规定：斯柯伦范式规定：将前束范式的首标中的量词进行排列，将前束范式的首标中的量词进行排列，每个存在量词均放到全称量词的前面每个存在量词均放到全称量词的前面第3页/共49页第四页，共49页。07 07 二月二月 2023 2023斯柯林范式(fn sh)例例2.12 2.12 将公式将公式(gngsh)(gngsh)(x)(x)(P(x)P(x)(y)Q(y,z)y)Q(y,z)(z)R(y,z)z)R(y,z)化为斯化为斯柯林范式柯林范式解：公式解：公式(x)(P(x)(u u)Q(u u,z)(v v)R(y,v v)(x)(P(x)P(x)(u)Q(u,z)u)Q(u,z)(v)R(y,v)(x)(P(x)P(x)(u)u)Q(u,z)Q(u,z)(v)v)R(y,v)R(y,v)(u)u)(v)v)(x)x)(P(x)P(x)Q(u,z)Q(u,z)R(y,v)R(y,v)第4页/共49页第五页，共49页。07 07 二月二月 2023 2023自由(zyu)变元代入规则自由变元代入规则：对公式中的某个自由出现的个体变元，可以用个体常元或与整个公式自由变元代入规则：对公式中的某个自由出现的个体变元，可以用个体常元或与整个公式中所有约束变元不同的个体变元去代入，而且是处处代入。中所有约束变元不同的个体变元去代入，而且是处处代入。A(x)A(x)可以用项可以用项(yngxing)t(yngxing)t代入，条件是代入，条件是x x不出现在项不出现在项t t所含的任意个体变元所含的任意个体变元y y的量词的量词(y)y)或或(y)y)的辖域内，称项的辖域内，称项t t对对x x是自由的。是自由的。例如：例如：A(x)=(A(x)=(y)(P(y)y)(P(y)Q(x,y)Q(x,y)项项f(y,z)f(y,z)对对x x不是自由的，而项不是自由的，而项 f(x,z)f(x,z)对对x x是自由的。是自由的。t t要代替要代替要代替要代替x x出现，出现，出现，出现，如果如果如果如果t t中有一个中有一个中有一个中有一个个体变元个体变元个体变元个体变元y y，它是，它是，它是，它是受量词约束的，受量词约束的，受量词约束的，受量词约束的，那么原本自由的那么原本自由的那么原本自由的那么原本自由的x x，被，被，被，被t t代替后，代替后，代替后，代替后，却不完全自由了却不完全自由了却不完全自由了却不完全自由了Q(Q(f(y,z),y),y)Q(Q(f(x,z),y),y)虽然虽然虽然虽然f f（x x，z z）出现在了）出现在了）出现在了）出现在了(y)y)的辖域内，的辖域内，的辖域内，的辖域内，但是但是但是但是f f（x x，z z）并不包含个体变元）并不包含个体变元）并不包含个体变元）并不包含个体变元y y，所，所，所，所以不受影响。以不受影响。以不受影响。以不受影响。第5页/共49页第六页，共49页。07 07 二月二月 2023 2023第七节 谓词(wi c)逻辑的推理理论引引 言言LpLp是是LsLs的深化发展，因此的深化发展，因此LsLs的推理理论在的推理理论在LpLp中几乎可完全照搬。中几乎可完全照搬。在在LpLp中，某些前提和结论中，某些前提和结论(jiln)(jiln)可能受到量词的约束，为确立前提可能受到量词的约束，为确立前提和结论和结论(jiln)(jiln)之间的内部联系，有必要削去量词和添加量词，之间的内部联系，有必要削去量词和添加量词，因此正确理解和运用有关量词规则是关键所在。因此正确理解和运用有关量词规则是关键所在。必要准备：必要准备：A(x)A(x)对对y y是自由的。目的是：允许用是自由的。目的是：允许用y y代入代入x x后得到后得到A(y)A(y)，它，它不改变原来公式不改变原来公式A(x)A(x)的约束关系的约束关系(x)A(x)A(y)第6页/共49页第七页，共49页。07 07 二月二月 2023 2023第七节 谓词逻辑(lu j)的推理理论第七节第七节 谓词逻辑的推理理论谓词逻辑的推理理论一、一、A(x)A(x)对对y y是自由的是自由的定义定义(dngy)(dngy)：在谓词公式：在谓词公式A(x)A(x)中，若中，若x x不自由出现在量词不自由出现在量词(y)y)或或(y)y)的辖域的辖域内，则称内，则称A(x)A(x)对于对于y y是自由的。是自由的。若若y y在在A(x)A(x)中不是约束出现，则中不是约束出现，则A(x)A(x)对于对于y y一定是自由的。一定是自由的。考察目的：使考察目的：使y y代入到代入到A(x)A(x)中得到中得到A(y)A(y)，不会改变原公式，不会改变原公式A(x)A(x)的约束关系。的约束关系。第7页/共49页第八页，共49页。07 07 二月二月 2023 2023A(x)对y是自由(zyu)的例例2.13 A(x)2.13 A(x)是下列是下列(xili)(xili)公式，考察公式，考察A(x)A(x)对对y y是否自由，并求是否自由，并求A(y)A(y)A(x)=(A(x)=(y)P(y)y)P(y)Q(x)Q(x)A(x)A(x)对对y y是自由的。是自由的。A(y)=(A(y)=(y)P(y)y)P(y)Q(y)Q(y)A(x)=(A(x)=(y)P(y)y)P(y)Q(x,y)Q(x,y)A(x)A(x)对对y y是自由的。是自由的。A(y)=(A(y)=(y)P(y)y)P(y)Q(y,y)Q(y,y)第8页/共49页第九页，共49页。07 07 二月二月 2023 2023A(x)对y是自由(zyu)的l lA(x)=(A(x)=(x)P(x)x)P(x)Q(x,y)Q(x,y)l l A(x)A(x)对对y y是自由的。是自由的。A(y)=(A(y)=(x)P(x)x)P(x)Q(y,y)Q(y,y)l lA(x)=(A(x)=(y)(P(y)y)(P(y)Q(x,y)Q(x,y)l l A(x)A(x)对对y y不是自由的。不是自由的。l l此时可以将此时可以将A(x)A(x)中的约束中的约束(yush)(yush)变元变元y y进行改名：进行改名：A(x)=(A(x)=(z)(P(z)z)(P(z)Q(x,z)Q(x,z)，l l此时此时A(x)A(x)对对y y是自由的是自由的 A(y)=(A(y)=(z)(P(z)z)(P(z)Q(y,z)Q(y,z)为什么不把为什么不把为什么不把为什么不把(x)P(x)x)P(x)也都换也都换也都换也都换y y？代入规则针对自由变元代入规则针对自由变元代入规则针对自由变元代入规则针对自由变元 第9页/共49页第十页，共49页。07 07 二月二月 2023 2023谓词(wi c)逻辑的推理理论二、谓词逻辑二、谓词逻辑(lu j)(lu j)的推理理论的推理理论全称量词的消去规则全称量词的消去规则 UI/US UI/US存在量词的消去规则存在量词的消去规则 EI/ES EI/ES存在量词的产生规则存在量词的产生规则 EG EG全称量词的产生规则全称量词的产生规则 UG UG第10页/共49页第十一页，共49页。07 07 二月二月 2023 2023全称量词(lingc)的消去规则 UI/US全称量词的消去规则全称量词的消去规则 UI/US UI/US也叫作全称指定规则也叫作全称指定规则(Universal Specification)(Universal Specification)规则内容：规则内容：(x)A(x)x)A(x)A(c)A(c)其中其中(qzhng)c(qzhng)c为任意个体常元为任意个体常元(x)A(x)x)A(x)A(y)A(y)y y为任意变元，为任意变元，且且A(x)A(x)对对y y是自由的是自由的该规则用于删除全称量词该规则用于删除全称量词第11页/共49页第十二页，共49页。07 07 二月二月 2023 2023全称量词(lingc)的消去规则 UI/US例例2.14 2.14 考察下面公式考察下面公式(x)A(x)x)A(x)，能推导出怎样的，能推导出怎样的A(y)A(y)来？来？(x)A(x)=(x)A(x)=(x)(x)(y)P(y)y)P(y)Q(x,y)Q(x,y)由于由于x x没有没有(mi yu)(mi yu)出现在出现在(y)y)的辖域内，所以的辖域内，所以A(x)A(x)对对y y是自由的是自由的A(y)=(A(y)=(y)P(y)y)P(y)Q(y,y)Q(y,y)即即(x)(x)(y)P(y)y)P(y)Q(x,y)Q(x,y)(y)P(y)y)P(y)Q(y,y)Q(y,y)(x)A(x)A(y)；消去了量词消去了量词消去了量词消去了量词(x)x)第12页/共49页第十三页，共49页。07 07 二月二月 2023 2023全称量词(lingc)的消去规则 UI/USl l(x)A(x)=(x)A(x)=(x)(x)(y)P(x,y)y)P(x,y)Q(x,y)Q(x,y)l l由于由于(yuy)x(yuy)x出现在出现在(y)y)的辖域内，因此需要对约束变元的辖域内，因此需要对约束变元y y改名改名l l(x)A(x)x)A(x)经过改名得到：经过改名得到：(x)(x)(z)P(x,z)z)P(x,z)Q(x,y)Q(x,y)l lA(y)=(A(y)=(z)P(y,z)z)P(y,z)Q(y,y)Q(y,y)l l即即(x)(x)(y)P(y,z)y)P(y,z)Q(x,y)Q(x,y)(z)P(y,z)z)P(y,z)Q(y,y)Q(y,y)第13页/共49页第十四页，共49页。07 07 二月二月 2023 2023例例2.18 2.18 证明证明(zhngmng)(zhngmng)以下论证：以下论证：所有人都是要死的所有人都是要死的苏格拉底是人苏格拉底是人所以苏格拉底是要死的所以苏格拉底是要死的解：令解：令P(x)P(x)：x x是人，是人，D(x)D(x)：x x是要死的，是要死的，a a：苏格拉底：苏格拉底题目符号化为：题目符号化为：(x)(P(x)x)(P(x)D(x),P(a)D(x),P(a)D(a)D(a)全称量词(lingc)的消去规则 UI/US第14页/共49页第十五页，共49页。07 07 二月二月 2023 2023(x)(P(x)x)(P(x)D(x),P(a)D(x),P(a)D(a)D(a)(1)(1)(x)(P(x)x)(P(x)D(x)D(x)P P(2)(2)P(a)P(a)D(a)D(a)UI (1)UI (1)(3)(3)P(a)P(a)P P(4)(4)D(a)D(a)T (2)(3)T (2)(3)I I8 8全称量词(lingc)的消去规则 UI/USP(x)：x是人，是人，D(x)：x是要死的，是要死的，a：苏格拉底苏格拉底第15页/共49页第十六页，共49页。07 07 二月二月 2023 2023例例2.19 2.19 已知有下面前提：已知有下面前提：同事同事(tng sh)(tng sh)之间总是有工作矛盾的之间总是有工作矛盾的张平和李明没有工作矛盾张平和李明没有工作矛盾问：能得到什么结论？问：能得到什么结论？解：令解：令P(x,y)P(x,y)：x x和和y y是同事是同事(tng sh)(tng sh)，Q(x,y)Q(x,y)：x x和和y y是有工作矛盾的是有工作矛盾的a a：张平，：张平，b b：李明：李明前提：前提：(x)(x)(y)(P(x,y)y)(P(x,y)Q(x,y),Q(x,y),Q(a,b)Q(a,b)全称(qun chn)量词的消去规则 UI/US第16页/共49页第十七页，共49页。07 07 二月二月 2023 2023(x)(x)(y)(P(x,y)y)(P(x,y)Q(x,y),Q(x,y),Q(a,b)Q(a,b)(1)(1)(x)(x)(y)(P(x,y)y)(P(x,y)Q(x,y)Q(x,y)P P(2)(2)(y)(P(a,y)y)(P(a,y)Q(a,y)Q(a,y)UI (1)UI (1)(3)(3)P(a,b)P(a,b)Q(a,b)Q(a,b)UI (2)UI (2)(4)(4)Q(a,b)Q(a,b)P P(5)(5)P(a,b)P(a,b)T (3)(4)I9T (3)(4)I9结论是：张平和李明不是结论是：张平和李明不是(b shi)(b shi)同事同事全称量词的消去(xio q)规则 UI/USP(x,y)：x和和y是同事，是同事，Q(x,y)：x和和y是有工作矛盾的是有工作矛盾的a：张平，张平，b：李明李明消去时通常要先消去时通常要先消去时通常要先消去时通常要先消去最外面的量消去最外面的量消去最外面的量消去最外面的量词，消去后要以词，消去后要以词，消去后要以词，消去后要以一个常元代替原一个常元代替原一个常元代替原一个常元代替原式中的变元式中的变元式中的变元式中的变元第17页/共49页第十八页，共49页。07 07 二月二月 2023 2023存在量词(lingc)的消去规则 EI/ES存在量词的消去规则存在量词的消去规则 EI/ES EI/ES也叫作存在指定规则也叫作存在指定规则(Existential Specification)(Existential Specification)规则内容：规则内容：(x)A(x)x)A(x)A(c)A(c)其中其中c c为某指定个体常元为某指定个体常元(x)A(x)x)A(x)A(y)A(y)A(x)A(x)对对y y是自由的是自由的规则成立条件：规则成立条件：c c不能在前提或居先推导中、或不能在前提或居先推导中、或(x)A(x)x)A(x)中出现中出现y y不能是前提或居先推导中、或不能是前提或居先推导中、或(x)A(x)x)A(x)中的自由变元中的自由变元注意：注意：y y只是一个只是一个(y)(y)暂时、表明上的自由变元暂时、表明上的自由变元容易出错！重点掌握容易出错！重点掌握容易出错！重点掌握容易出错！重点掌握A(y)A(y)只是新引入的暂时假设，它不是对只是新引入的暂时假设，它不是对只是新引入的暂时假设，它不是对只是新引入的暂时假设，它不是对 y y的一切值都成立的。的一切值都成立的。的一切值都成立的。的一切值都成立的。第18页/共49页第十九页，共49页。07 07 二月二月 2023 2023存在(cnzi)量词的消去规则 EI/ES例例2.15 2.15 考察下面推论是否合乎规则？考察下面推论是否合乎规则？个体域个体域DIDI是自然数，是自然数，O(x)O(x)：x x是奇数是奇数(j sh)(j sh)，E(x)E(x)：x x是偶数是偶数已知前提：已知前提：(x)O(x)x)O(x)，(x)E(x)x)E(x)(1)(1)(x)O(x)x)O(x)P P(2)(2)O(y)O(y)EI(1)EI(1)(3)(3)(x)E(x)x)E(x)P P(4)(4)E(y)E(y)EI(3)EI(3)(5)(5)O(y)O(y)E(y)E(y)T(2)(4)T(2)(4)y y是是是是(2)(2)中的自由变元中的自由变元中的自由变元中的自由变元c c不能在前提或居先推导中、或不能在前提或居先推导中、或不能在前提或居先推导中、或不能在前提或居先推导中、或(x)A(x)x)A(x)中出现中出现中出现中出现y y不能是前提或居先推导中、或不能是前提或居先推导中、或不能是前提或居先推导中、或不能是前提或居先推导中、或(x)A(x)x)A(x)中的自由变元中的自由变元中的自由变元中的自由变元消去存在量词所新引入的变元，在消去存在量词所新引入的变元，在消去存在量词所新引入的变元，在消去存在量词所新引入的变元，在之前不能出现过。之前不能出现过。之前不能出现过。之前不能出现过。第19页/共49页第二十页，共49页。07 07 二月二月 2023 2023存在(cnzi)量词的消去规则 EI/ESl l个体域个体域DIDI是全体是全体(qunt)(qunt)实数，实数，G(x,y)G(x,y)：xyxyl l已知前提：已知前提：(x)(x)(y)G(x,y)y)G(x,y)l l(1)(1)(x)(x)(y)G(x,y)y)G(x,y)P Pl l(2)(2)(y)G(z,y)y)G(z,y)UI (1)UI (1)l l(3)(3)G(z,z)G(z,z)EI (2)EI (2)(3)G(z,c c)EI (2)(4)(x)G(z,x)x)G(z,x)A(c)或或 A(y)只是临时引入的一个假设前提，只是临时引入的一个假设前提，不能作为结论不能作为结论z z是是是是(2)(2)中的自由变元中的自由变元中的自由变元中的自由变元c c不能在前提或居先推导中、或不能在前提或居先推导中、或不能在前提或居先推导中、或不能在前提或居先推导中、或(x)A(x)x)A(x)中出现中出现中出现中出现y y不能是前提或居先推导中、或不能是前提或居先推导中、或不能是前提或居先推导中、或不能是前提或居先推导中、或(x)A(x)x)A(x)中的自由变元中的自由变元中的自由变元中的自由变元第20页/共49页第二十一页，共49页。07 07 二月二月 2023 2023存在量词(lingc)的产生规则 EG存在存在(cnzi)(cnzi)量词的产生规则量词的产生规则 EG EG也叫作存在也叫作存在(cnzi)(cnzi)推广规则推广规则(Existential Generalization)(Existential Generalization)规则内容：规则内容：A(c)A(c)(y)A(y)y)A(y)其中其中c c为某指定个体常元为某指定个体常元 A(x)A(x)(y)A(y)y)A(y)A(x)A(x)对对y y是自由的是自由的规则成立条件：规则成立条件：y y不在不在A(c)A(c)或或A(x)A(x)中出现中出现若若A(x)A(x)为推导行的公式，为推导行的公式，x x是由是由EIEI引入的，则不能用引入的，则不能用x x以外的个体变元作为约以外的个体变元作为约束变元束变元第21页/共49页第二十二页，共49页。07 07 二月二月 2023 2023存在量词(lingc)的产生规则 EG例例2.16 2.16 考察考察(koch)(koch)下面推论是否合乎规则？下面推论是否合乎规则？个体域个体域DIDI是全体实数，是全体实数，G(x,y)G(x,y)：xyxy已知前提：已知前提：(x)(x)(y)G(x,y)y)G(x,y)(1)(1)(x)(x)(y)G(x,y)y)G(x,y)P P(2)(2)(y)G(z,y)y)G(z,y)UI(1)UI(1)(3)(3)(y)(y)(y)G(y,y)y)G(y,y)EG(2)EG(2)y y在在在在(2)(2)中出现中出现中出现中出现(3)G(z,u)EI(2)(4)(z)G(z,z)EG(3)z z在在在在(3)(3)中出现中出现中出现中出现第22页/共49页第二十三页，共49页。07 07 二月二月 2023 2023全称量词(lingc)的产生规则 UG全称量词的产生规则全称量词的产生规则 UG UG也叫作全称推广规则也叫作全称推广规则(Universal Generalization)(Universal Generalization)规则内容规则内容(nirng)(nirng)：A(x)A(x)(y)A(y)y)A(y)A(x)A(x)对对y y是自由的是自由的规则成立条件：规则成立条件：前提前提A(x)A(x)对于对于x x的任意取值都成立的任意取值都成立x x不是由不是由EIEI引入引入由由EIEI引入的其他变元，不能出现在引入的其他变元，不能出现在A(x)A(x)中中第23页/共49页第二十四页，共49页。07 07 二月二月 2023 2023全称(qun chn)量词的产生规则 UG例例2.17 2.17 考察考察(koch)(koch)下面推论是否合乎规则？下面推论是否合乎规则？个体域个体域DIDI是全体实数，是全体实数，G(x,y)G(x,y)：xyxy已知前提：已知前提：(x)(x)(y)G(x,y)y)G(x,y)(1)(1)(x)(x)(y)G(x,y)y)G(x,y)P P(2)(2)(y)G(z,y)y)G(z,y)UI(1)UI(1)(3)(3)G(z,a)G(z,a)EI(2)EI(2)(4)(4)(x)G(x,a)x)G(x,a)UG(3)UG(3)(5)(5)(y)(y)(x)G(x,y)x)G(x,y)EG(4)EG(4)公式中含有由公式中含有由公式中含有由公式中含有由EIEI引入的引入的引入的引入的a a第24页/共49页第二十五页，共49页。07 07 二月二月 2023 2023谓词逻辑的推理：谓词逻辑的推理：UIUI和和EIEI主要用于推导主要用于推导(tudo)(tudo)过程中删除量词过程中删除量词UGUG和和EGEG主要用于使结论呈量化形式主要用于使结论呈量化形式注意：使用注意：使用EIEI而产生的自由变元不能保留在结论中，因为它只是暂时的假设，在推导而产生的自由变元不能保留在结论中，因为它只是暂时的假设，在推导(tudo)(tudo)结束之前，必须使用结束之前，必须使用EGEG规则使之成为约束变元规则使之成为约束变元谓词逻辑(lu j)的推理第25页/共49页第二十六页，共49页。07 07 二月二月 2023 2023例例2.20 2.20 证明证明(x)Q(x)x)Q(x)是是(x)(P(x)x)(P(x)Q(x)Q(x)和和(x)P(x)x)P(x)的有效的有效(yuxio)(yuxio)结论结论(1)(1)(x)P(x)x)P(x)P P(2)(2)P(y)P(y)EI(1)EI(1)(3)(3)(x)(P(x)x)(P(x)Q(x)Q(x)P P(4)(4)P(y)P(y)Q(y)Q(y)UI(3)UI(3)(5)(5)Q(y)Q(y)T(2)(4)I8T(2)(4)I8(6)(6)(x)Q(x)x)Q(x)EG(5)EG(5)谓词(wi c)逻辑的推理仅由谓词与个体仅由谓词与个体仅由谓词与个体仅由谓词与个体变元还不能构成变元还不能构成变元还不能构成变元还不能构成命题，所以需要命题，所以需要命题，所以需要命题，所以需要产生量词。产生量词。产生量词。产生量词。第26页/共49页第二十七页，共49页。07 07 二月二月 2023 2023例例2.20 2.20 证明证明(x)Q(x)x)Q(x)是是(x)(P(x)x)(P(x)Q(x)Q(x)和和(x)P(x)x)P(x)的有效结论的有效结论(jiln)(jiln)注意：下面推理是否有效？注意：下面推理是否有效？(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)P(y)P(y)Q(y)Q(y)UI(1)UI(1)(3)(3)(x)P(x)x)P(x)P P(4)(4)P(y)P(y)EI(3)EI(3)(5)(5)Q(y)Q(y)T(2)(4)I8T(2)(4)I8(6)(6)(x)Q(x)x)Q(x)EG(5)EG(5)谓词逻辑(lu j)的推理y y是是是是(2)(2)中的自由变元中的自由变元中的自由变元中的自由变元第27页/共49页第二十八页，共49页。07 07 二月二月 2023 2023例例2.21 2.21 证明或否定下面证明或否定下面(xi mian)(xi mian)推理：推理：每棵松树都是针叶松每棵松树都是针叶松每一冬季落叶的树都是非针叶松每一冬季落叶的树都是非针叶松所以，每一冬季落叶的树都不是松树所以，每一冬季落叶的树都不是松树解：令解：令P(x)P(x)：x x是松树，是松树，Q(x)Q(x)：x x是针叶松，是针叶松，R(x)R(x)：x x是冬季落叶的树是冬季落叶的树题目：题目：(x)(P(x)x)(P(x)Q(x),(Q(x),(x)(R(x)x)(R(x)Q(x)Q(x)(x)(R(x)x)(R(x)P(x)P(x)谓词(wi c)逻辑的推理第28页/共49页第二十九页，共49页。07 07 二月二月 2023 2023(x)(P(x)x)(P(x)Q(x),Q(x),(x)(R(x)x)(R(x)Q(x)Q(x)(x)(R(x)x)(R(x)P(x)P(x)(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)P(y)P(y)Q(y)Q(y)UI(1)UI(1)(3)(3)Q(y)Q(y)P(y)P(y)T(2)ET(2)E1111(4)(4)(x)(R(x)x)(R(x)Q(x)Q(x)P P(5)(5)R(y)R(y)Q(y)Q(y)UI(4)UI(4)(6)(6)R(y)R(y)P(y)P(y)T(3)(5)IT(3)(5)I1111(7)(7)(x)(R(x)x)(R(x)P(x)P(x)UG(6)UG(6)谓词逻辑(lu j)的推理P(x)：x是松树，是松树，Q(x)：x是针叶是针叶(zhn y)松，松，R(x)：x是冬季落叶的树是冬季落叶的树第29页/共49页第三十页，共49页。07 07 二月二月 2023 2023例例2.22 2.22 证明证明(zhngmng)(zhngmng)(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)Q(x)x)Q(x)证明证明(zhngmng)(zhngmng)：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)(x)(x)(P(x)P(x)Q(x)Q(x)T(1)E11T(1)E11(3)(3)(x)x)P(x)P(x)(x)Q(x)x)Q(x)T(2)QT(2)Q(4)(4)(x)P(x)x)P(x)(x)Q(x)x)Q(x)T(3)QT(3)Q(5)(5)(x)P(x)x)P(x)(x)Q(x)x)Q(x)T(4)E11T(4)E11谓词(wi c)逻辑的推理(x)(A(x)x)(A(x)B(x)B(x)(x)A(x)A(x)(x)B(x)B(x)(p43)第30页/共49页第三十一页，共49页。07 07 二月二月 2023 2023例例2.22 2.22 证明证明(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)Q(x)x)Q(x)证明：用反证法：证明：用反证法：(1)(1)(x)P(x)x)P(x)(x)Q(x)x)Q(x)P P（假设（假设(jish)(jish)前提）前提）(2)(2)(x)P(x)x)P(x)(x)Q(x)x)Q(x)T(1)E5T(1)E5(3)(3)(x)P(x)x)P(x)T(2)I1T(2)I1(4)(4)(x)x)P(x)P(x)T(3)QT(3)Q(5)(5)(x)Q(x)x)Q(x)T(2)I2T(2)I2(6)(6)(x)x)Q(x)Q(x)T(5)QT(5)Q谓词逻辑(lu j)的推理第31页/共49页第三十二页，共49页。07 07 二月二月 2023 2023(7)(7)P(y)P(y)EI(4)EI(4)(8)(8)Q(y)Q(y)UI(6)UI(6)(9)(9)P(y)P(y)Q(y)Q(y)T(7)(8)T(7)(8)(10)(10)(P(y)(P(y)Q(y)Q(y)T(9)E5T(9)E5(11)(11)(x)(P(x)x)(P(x)Q(x)Q(x)P P(12)(12)P(y)P(y)Q(y)Q(y)UI(11)UI(11)(13)(13)(P(y)(P(y)Q(y)Q(y)(P(y)(P(y)Q(y)Q(y)T(10)(12)T(10)(12)推出矛盾，因此推出矛盾，因此(ync)(ync)假设不成立。证毕。假设不成立。证毕。谓词(wi c)逻辑的推理(4)(x)P(x)T(3)QT(3)Q(6)(x)Q(x)T(5)QT(5)Q(7)Q(y)UI(6)UI(6)(8)P(y)EI(4)EI(4)y y是是是是(7)(7)中的自由变元中的自由变元中的自由变元中的自由变元消去时先消去存在量词，消去时先消去存在量词，消去时先消去存在量词，消去时先消去存在量词，再消去全称量词再消去全称量词再消去全称量词再消去全称量词第32页/共49页第三十三页，共49页。07 07 二月二月 2023 2023习题(xt)1919.19.构造证明构造证明(zhngmng)(zhngmng)下列各式下列各式20.20.(x)(P(x)x)(P(x)Q(x),(Q(x),(x)(Q(x)x)(Q(x)R(x)R(x)(x)(P(x)x)(P(x)R(x)R(x)21.21.(x)(H(x)x)(H(x)M(x),(M(x),(x)H(x)x)H(x)(x)M(x)x)M(x)22.22.(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)Q(x)x)Q(x)第35页/共49页第三十六页，共49页。07 07 二月二月 2023 2023习题(xt)19证明证明(zhngmng)(zhngmng)：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)P(y)P(y)Q(y)Q(y)UI(1)UI(1)(3)(3)(x)(Q(x)x)(Q(x)R(x)R(x)P P(4)(4)Q(y)Q(y)R(y)R(y)UI(3)UI(3)(5)(5)P(y)P(y)R(y)R(y)T(2)(4)T(2)(4)I11I11(6)(6)(x)(P(x)x)(P(x)R(x)R(x)UG(5)UG(5)1)1)(x)(P(x)x)(P(x)Q(x),(Q(x),(x)(Q(x)x)(Q(x)R(x)R(x)(x)(P(x)x)(P(x)R(x)R(x)第36页/共49页第三十七页，共49页。07 07 二月二月 2023 2023习题(xt)19证明证明(zhngmng)(zhngmng)：(1)(1)(x)H(x)x)H(x)P P(2)(2)H(y)H(y)EI(1)EI(1)(3)(3)(x)(H(x)x)(H(x)M(x)M(x)P P(4)(4)H(y)H(y)M(y)M(y)UI(3)UI(3)(5)(5)M(y)M(y)T(2)(4)I8T(2)(4)I8(6)(6)(x)M(x)x)M(x)EG(5)EG(5)2)2)(x)(H(x)x)(H(x)M(x),(M(x),(x)H(x)x)H(x)(x)M(x)x)M(x)第37页/共49页第三十八页，共49页。07 07 二月二月 2023 2023习题(xt)19证明证明(zhngmng)(zhngmng)：(1)(1)(x)(P(x)x)(P(x)Q(x)Q(x)P P(2)(2)P(y)P(y)Q(y)Q(y)EI(1)EI(1)(3)(3)P(y)P(y)T(2)I1T(2)I1(4)(4)(x)P(x)x)P(x)EG(3)EG(3)(5)(5)Q(y)Q(y)T(2)I2T(2)I2(6)(6)(x)Q(x)x)Q(x)EG(5)EG(5)(7)(7)(x)P(x)x)P(x)(x)Q(x)x)Q(x)T(4)(6)T(4)(6)3)3)(x)(P(x)x)(P(x)Q(x)Q(x)(x)P(x)x)P(x)(x)Q(x)x)Q(x)第38页/共49页第三十九页，共49页。07 07 二月二月 2023 2023习题(xt)22(1)22.22.符号化下列符号化下列(xili)(xili)各命题，并给出构造推理证明。各命题，并给出构造推理证明。23.23.每一个自然数不是奇数就是偶数每一个自然数不是奇数就是偶数24.24.自然数是偶数当且仅当它能被自然数是偶数当且仅当它能被2 2整除整除25.25.并不是所有自然数都能被并不是所有自然数都能被2 2整除整除26.26.所以：有的自然数是奇数所以：有的自然数是奇数设：设：N(x)：x是自然数，是自然数，O(x)：x是奇数，是奇数，E(x)：x是偶数，是偶数，T(x)：x能被能被2整除整除(x)(N(x)O(x)E(x)(x)(N(x)x)(N(x)(E(x)(E(x)T(x)T(x)(x)(N(x)x)(N(x)T(x)T(x)(x)(N(x)x)(N(x)O(x)O(x)第39页/共49页第四十页，共49页。07 07 二月二月 2023 2023习题(xt)22(1)前提：前提：(x)(N(x)x)(N(x)O(x)O(x)E(x),(E(x),(x)(N(x)x)(N(x)(E(x)(E(x)T(x),T(x),(x)(N(x)x)(N(x)T(x)T(x)结论结论(jiln)(jiln)：(x)(N(x)x)(N(x)O(x)O(x)证明：证明：(1)(1)(x)(N(x)x)(N(x)T(x)T(x)P P(2)(2)(x)(x)(N(x)N(x)T(x)T(x)T(1)E11 T(1)E11(3)(3)(x)(N(x)x)(N(x)T(x)T(x)T(2)Q,E1,E5T(2)Q,E1,E5(4)(4)N(y)N(y)T(y)T(y)EI(3)EI(3)(5)(5)N(y)N(y)T(4)I1T(4)I1(6)(6)(x)(N(x)x)(N(x)(E(x)(E(x)T(x)T(x)P P(7)(7)N(y)N(y)(E(y)(E(y)T(y)T(y)UI(6)UI(6)(8)(8)E(y)E(y)T(y)T(y)T(5)(7)I8T(5)(7)I8(9)(9)E(y)E(y)T(y)T(y)T(8)I18T(8)I18第40页/共49