人工基础智能及逻辑 11

第3章谓词逻辑3.1实例分析超越命题逻辑的推理需求3.2谓词逻辑语言字符集、项与公式定义；量词辖域与变元出现3.3谓词逻辑语义模型与真值条件；有效性与等值3.4自然演绎系统量词的推理规则3.5元定理可靠性与完全性3.6结语3.1命题逻辑的局限性命题逻辑的不足命题逻辑通过对否定、合取、析取、实质蕴涵和实质等值进行解释，来研究哪些推理模式是有效的。它关注句子之间的逻辑联系。然而，许多推理和论证都远远超越了这一层次，我们需要考虑句子内部的结构。实例1：传递关系推理命题逻辑表示：p,q/rp：神经网络比决策树更精准q：决策树比线性模型更精准r：神经网络比线性模型更精准问题这个论证模式在命题逻辑中不是有效的，很容易构造反例。但直观上看，该论证是有效的。为什么直观有效？关键因素因为三个命题中都出现了"大于(>)"关系，该关系与几个对象的关联方式决定了论证是有效的。需要的能力为了刻画这些要素，需要在形式语言中能够指称对象与对象之间的关系。(1')改进的表示神经网络>决策树决策树>线性模型因此，神经网络>线性模型实例2：全称量化推理(2)所有的深度学习模型都能从数据中学习。ChatGPT是深度学习模型，所以它能从数据中学习。命题逻辑的困境在命题逻辑中，两个前提、结论都只能表示为一些原子命题，无法解释这个论证为什么是有效的。需要的能力我们需要在形式语言中能够谈论属性、满足某个属性的对象的集合。改进的表示(2')对于所有个体x，如果(x)是深度学习模型，则(x)能从数据中学习。ChatGPT是深度学习模型。所以，ChatGPT能从数据中学习。本章任务本章的主要任务就是介绍谓词逻辑的语言、语义，并能够判断类似上面的论证是否有效。与命题逻辑一样，我们关心的不是具体的论证，而是论证模式。3.2谓词逻辑语言的组成定义7(字符集)谓词逻辑语言L的字符集由以下部分组成：(1)谓词符$$A_1^i,\cdots,A_n^i,\cdots,A_1^k,\cdots,A_n^k,\cdots$$，对于任意元数$$i,k,\cdots$$；记作$$\mathrm{PRED}_L$$(2)个体常元$$c_1,\cdots,c_n,\cdots$$；记作$$\mathrm{CON}_L$$(3)个体变元$$x_1\cdotsx_n\cdots$$；记作$$\mathrm{VAR}_L$$项的定义定义8(项)$$L$$的项由$$L$$的个体常元和个体变元组成，记作$$\mathrm{TERM}_L$$。符号约定（为方便讨论）用$$P,Q,R,S,\cdots$$表示谓词符用$$a,b,c,\cdots$$表示个体常元符用$$x,y,z,\cdots$$表示个体变元符公式的递归定义定义9(公式)给定$$L$$的字符集，谓词逻辑语言$$L$$的公式集就是满足下面条件的最小集合：(1)原子公式如果$$A_i^n$$是一个$$n$$元的谓词符，$$t_1,\cdots,t_n$$是项，那么$$A_i^nt_1,\cdots,t_n$$是公式。(2)否定如果$$\varphi$$是公式，那么$$\neg\varphi$$也是公式。(3)联结词如果$$\varphi,\psi$$是公式，那么$$(\varphi\wedge\psi),(\varphi\vee\psi),(\varphi\rightarrow\psi),(\varphi\leftrightarrow\psi)$$也是公式。(4)量词如果$$\varphi$$是公式，$$x_j$$是一个变元，那么$$\forallx_j\varphi,\existsx_j\varphi$$也是公式。公式示例合式的原子公式PxRcdTsxy...量化公式$$\forallxRxc,\existsx(Px\wedge\forally(Qy\rightarrowSyx)),\existszPc$$空洞量化注意，最后一个例子中$$\existszPc$$是所谓的"空洞量化"(VacuousQuantification)。在$$Pc$$中没有出现变元$$z$$，因此该量词无效。另一个例子是$$\forallx\existsxPx$$，这里$$\forallx$$的出现是空洞的，但$$\existsx$$不是。量词的辖域定义10(量词出现的辖域)如果$$\forallx\psi$$是$$\varphi$$的子公式，那么$$\psi$$就被称为量词$$\forallx$$在$$\varphi$$中出现的辖域。练习16示例确定下列公式中量词出现的辖域：$$\forallx(\existsyRxy\rightarrowPx)$$$$\forallx\existsy(Rxy\rightarrowPx)$$$$\existsxPx\wedge\existsyRcy$$自由出现与约束出现定义11(自由出现和约束出现)自由出现在公式$$\varphi$$中，变元$$x$$的某次出现如果不是量词的一部分，且该次出现的$$x$$不在某个量词（如$$\forallx$$或$$\existsx$$）的辖域内，则称该次出现的$$x$$在$$\varphi$$中是自由的。约束出现如果$$\forallx\psi(\existsx\psi)$$是$$\varphi$$的一个子公式，且$$x$$在$$\psi$$中的一次出现是自由的，那么该次$$x$$的出现被称为由量词$$\forallx\psi(\existsx\psi)$$所约束。变元出现示例练习17示例确定下面的公式中变元的出现哪些是自由的，哪些是约束的：(1)$$\existsx(Px\landQx)$$x全部约束(2)$$\existsxPx\wedgeQx$$第一个x约束，第二个x自由(3)$$\forallx(Px\rightarrow\existsyRxy)$$x约束，y约束(4)$$\forallx(Px\rightarrow\existsxRxx)$$混合情况句子的定义定义12(句子)句子是指在语言$$L$$中不含自由变元出现的公式。练习18判断判断下列公式中哪些是句子：$$Pc$$—是句子$$Rcy$$—不是（y自由）$$\existsxRxc$$—是句子$$\forallzPx\rightarrowScz$$—不是（x自由）$$\forallxPy$$—不是（y自由）自然语言形式化步骤形式化过程解决实际问题时，最重要的一步是把自然语言表述的内容形式化为谓词逻辑的公式，这个过程可以按照下面的步骤进行：(1)指定论域确定所讨论对象的范围(2)指定译码为谓词符、常元等指定具体含义(3)尽可能细致地表述逻辑结构用形式语言精确刻画自然语言的逻辑关系形式化实例1(1)神经网络比决策树更精准，决策树比线性模型更精准，因此，神经网络比线性模型更精准。论域机器学习方法译码$$Pxy:x>y$$$$n$$：神经网络；$$t$$：决策树；$$l$$：线性模型形式化结果$$(1')\quadPnt,Ptl/Pnl$$增强版本（增加传递性前提）$$(1'')\quadPnt,Ptl,\forallx\forally\forallz((Pxy\landPyz)\rightarrowPxz)/Pnl$$形式化实例2(2)所有的深度学习模型都能从数据中学习。ChatGPT是深度学习模型，所以它能从数据中学习。论域深度学习模型译码$$Dx$$：$$x$$是深度学习模型$$Lx$$：$$x$$能从数据中学习$$c$$：ChatGPT形式化结果$$(2')\quad\forallx(Dx\rightarrowLx),Dc/Lc$$注意变元替换—$$\forallx(Dx\rightarrowLx)$$和$$\forally(Dy\rightarrowLy)$$等价。形式化练习练习19翻译下列句子，指定论域并给出译码：所有使用人工智能的人都是高效的。并非所有使用人工智能的人都理解其原理。有些算法是监督学习，有些算法是无监督学习。没有算法既是监督学习又是无监督学习。所有人工智能都是黑盒模型。每个开发者都讨厌那些谁都追捧的算法。如果一个人工智能系统能处理所有输入(所有输入包括它自身生成的反馈)，那么它也能自我优化。如果你什么都不训练，你就不会出现任何过拟合。人工智能做什么都做得很好。3.3.1模型与真值条件语义解释的核心为了给谓词逻辑公式赋予意义，需要定义：模型解释符号的结构真值条件在模型下公式何时为真模型的定义定义13(模型)谓词逻辑语言L的模型$$M$$是一个有序对$$\langleD_M,I_M\rangle$$，使得：$$D_M$$是一个非空集（论域）$$I_M$$是一个函数，使得：对于$$L$$中的任意个体常元$$c_i$$，$$I_M(c_i)\inD_M$$对于$$L$$中的任意谓词符$$A_i^n$$，$$I_M(A_i^n)\subseteqD_M^n$$解释个体常元指称论域中的元素一元谓词指称元素的集合$$n$$元关系指论域中元素的$$n$$元组的集合指派函数定义14(指派)给定模型$$M$$，指派$$G$$是从$$\mathrm{VAR}_L$$到$$D_M$$的所有函数$$g$$的集合。符号$$g[x/d]$$$$g[x/d]$$与$$g$$类似，唯一的区别在于$$g(x)=d$$对于所有$$y\neqx$$，$$g[x/d](y)=g(y)$$如果$$g(x)=d$$，那么$$g[x/d]=g$$扩展可以扩展到多个变元，如$$g[x_i/d_k,\cdots,x_n/d_l]$$项的解释定义15(项的解释)$$[[t]]_{M,g}=I_M(t)$$，若$$t$$是一个常元$$[[t]]_{M,g}=g(t)$$，若$$t$$是一个变元常元的解释由模型$$I_M$$决定变元的解释由指派函数$$g$$决定赋值函数定义16(赋值)假设$$M$$是$$L$$的一个模型$$\langleD,I\rangle$$，而$$G$$是指派函数的集合。赋值$$V_{M,g}$$是一个从$$L$$的公式集到$$\{0,1\}$$的函数，使得：(1)原子公式$$V_{M,g}(At_1\cdot\cdot\cdott_n)=1$$当且仅当$$\langle[[t_1]]_{M,g},\cdot\cdot\cdot,[[t_n]]_{M,g}\rangle\inI(A)$$(2)否定$$V_{M,g}(\neg\varphi)=1$$当且仅当$$V_{M,g}(\varphi)=0$$(3)合取$$V_{M,g}(\varphi\wedge\psi)=1$$当且仅当$$V_{M,g}(\varphi)=1$$并且$$V_{M,g}(\psi)=1$$(4)其他联结词$$\lor,\rightarrow,\leftrightarrow$$的情况可类似给出量词的真值条件(5)全称量词$$V_{M,g}(\forallx\varphi)=1$$当且仅当对于所有的$$d\inD:V_{M,g[x/d]}(\varphi)=1$$直观：如果$$\forallx\varphi$$为真，那么对于论域中的每个个体$$d$$来说，如果$$x$$指称$$d$$，那么$$\varphi$$为真。(6)存在量词$$V_{M,g}(\existsx\varphi)=1$$当且仅当存在一个$$d\inD:V_{M,g[x/d]}(\varphi)=1$$直观：如果$$\existsx\varphi$$为真，那么论域中至少存在一个个体$$d$$，当$$x$$指称$$d$$时，$$\varphi$$为真。存在量词示例示例：$$V_{M,g}(\existsx(Px\wedgeQx))=1$$当且仅当存在一个$$d\inD:V_{M,g[x/d]}(Px\landQx)=1$$当且仅当存在一个$$d\inD:V_{M,g[x/d]}(Px)=1$$并且$$V_{M,g[x/d]}(Qx)=1$$当且仅当存在一个$$d\inD:[[x]]_{M,g[x/d]}\inI_M(P)$$并且$$[[x]]_{M,g[x/d]}\inI_M(Q)$$当且仅当存在一个$$d\inD:g[x/d](x)\inI_M(P)$$并且$$g[x/d](x)\inI_M(Q)$$当且仅当存在一个$$d\inD:d\inI_M(P)$$并且$$d\inI_M(Q)$$模型的图示表示集合论描述vs图示表示当模型的论域变得很大，并且在其上定义了一个或多个关系时，使用纯集合论的术语描述模型会变得相当烦琐。在这种情况下，可以使用画图方式表示模型。示例模型$$D_M=\{1,2,3,4\}$$$$I_M(P)=\{1,3\}$$$$I_M(R)=\{\langle1,2\rangle,\langle2,1\rangle,\langle1,3\rangle,\langle3,3\rangle\}$$模型图示图3-1M图示说明论域的元素是图中的点点与点之间的箭头表示关系满足属性的点则用圆圈圈起来练习20考虑模型：$$D=\{1,2,3,4\}$$$$I(A)=\{1,4\}$$$$I(R)=\{\langle1,1\rangle,\langle1,2\rangle,\langle1,3\rangle,\langle1,4\rangle,\langle3,3\rangle,\langle4,1\rangle,\langle4,2\rangle,\langle4,3\rangle,\langle4,4\rangle\}$$(1)画出以上模型的图。(2)在该模型中，下列哪些公式为真？(a)$$\forallx(Ax\rightarrow\forallyRxy)$$(b)$$\forallx\forally(Rxy\rightarrowRyx)$$(c)$$\existsx\existsy(Rxy\landRyx)$$3.3.2重要事实事实7如果对$$\varphi$$中自由出现的任意变元$$v$$，有$$g(v)=g'(v)$$，那么：$$V_{M,g}(\varphi)=1$$当且仅当$$V_{M,g'}(\varphi)=1$$意义公式的真值只依赖于其中自由变元的指派句子的真值独立性事实8如果$$\varphi$$是一个句子，那么对于所有$$g,g'$$：$$V_{M,g}(\varphi)=1$$当且仅当$$V_{M,g'}(\varphi)=1$$重要性句子（不包含自由变元的公式）的真值不依赖于指派这是事实7的直接推论。替换事实事实9对所有的$$M$$和$$g$$：$$V_{M,g}([c/x]\varphi)=V_{M,g[x/I(c)]}(\varphi)$$证明思路对$$\varphi$$的结构施归纳。注意如果$$x$$没有在$$\varphi$$中自由出现，$$[c/x]\varphi=\varphi$$。事实9证明框架证明：施归纳于$$\varphi$$的结构。(1)原子公式情形：$$\varphi=At_1\dotst_n$$假设$$t_i=x$$。关键在于：$$[[x]]_{M,g[x/I(c)]}=I(c)=[[c]]_{M,g}$$(2)合取情形：$$\varphi=\psi\wedge\chi$$注意$$[c/x](\psi\wedge\chi)=[c/x]\psi\wedge[c/x]\chi$$，根据归纳假设即可得出。(3)全称量词情形：$$\varphi=\forally\psi$$注意$$[c/x]\forally\psi=\forally[c/x]\psi$$，对任意$$d$$应用归纳假设。可自由替换避免变元捕获如果用一个变元替换另一个变元，可能会发生新变元被约束的情况。例子$$[y/x]\existsyRxy=\existsyRyy$$尽管$$x$$在$$\existsyRxy$$中自由出现，$$[y/x]\existsyRxy$$中的$$y$$则被约束。定义17$$y$$在$$\varphi$$中对$$x$$可自由替换，当且仅当，$$x$$没有自由出现在$$\varphi$$中$$\existsy$$或$$\forally$$的辖域内。练习21考虑公式：$$\existsxRxy\wedge(\forallyRyx\veeRzz)$$问题$$y$$对$$x$$可自由替换吗？对于$$z$$呢？$$w$$对$$x$$可自由替换吗？$$x$$对$$y$$可自由替换吗？一般化的替换定理事实10对所有$$M$$和$$g$$：如果$$t$$在$$\varphi$$中对$$x$$可自由替换，则：$$V_{M,g}[t/x]\varphi=V_{M,g[x/[[t]]_{M,g}]}\varphi$$意义将事实9一般化到任意项的替换普遍有效性定义18(普遍有效性)$$\varphi$$是普遍有效的，当且仅当，对于所有$$M$$和$$g$$：$$V_{M,g}(\varphi)=1$$。记号$$\models\varphi$$意义公式在所有可能的模型和指派下都为真论证模式的有效性定义19(论证模式的有效性)$$\varphi_1\cdots\varphi_n/\psi$$是有效的，当且仅当，对于所有的$$M$$和$$g$$：如果$$V_{M,g}(\varphi_1)=\cdots=V_{M,g}(\varphi_n)=1$$，那么$$V_{M,g}(\psi)=1$$。记号$$\varphi_1\cdots\varphi_n\models\psi$$意义在所有使前提为真的模型和指派下，结论也为真演绎定理定理7(演绎定理)$$\varphi\models\psi$$当且仅当$$\models\varphi\rightarrow\psi$$$$\varphi_1\cdots\varphi_n\models\psi$$当且仅当$$\varphi_1\cdot\cdot\cdot\varphi_{n-1}\models\varphi_n\rightarrow\psi$$定理8(演绎定理的一般形式)$$\varphi_1\cdots\varphi_n\models\psi$$当且仅当：$$\models\varphi_1\rightarrow(\varphi_2\rightarrow(\cdots\rightarrow(\varphi_n\rightarrow\psi)\cdots))$$当且仅当：$$\models(\varphi_1\wedge\varphi_2\wedge\cdots\wedge\varphi_n)\rightarrow\psi$$证明有效性示例1证明：$$\models\existsx(Ax\wedgeBx)\rightarrow(\existsxAx\wedge\existsxBx)$$证明过程假设对任意$$M$$和$$g$$，$$V_{M,g}(\existsx(Ax\landBx))=1$$。那么，存在一个$$d$$使得$$V_{M,g[x/d]}(Ax\wedgeBx)=1$$（∃-真值条件）即使得$$V_{M,g[x/d]}(Ax)=1$$且$$V_{M,g[x/d]}(Bx)=1$$（∧-真值条件）由$$V_{M,g[x/d]}(Ax)=1$$，得出$$V_{M,g}(\existsxAx)=1$$（∃-真值条件）同理有$$V_{M,g}(\existsxBx)=1$$因而可以得出$$V_{M,g}(\existsxAx\land\existsxBx)=1$$（∧-真值条件）□证明有效性示例2证明：$$\models(\forallx\varphi\vee\forallx\psi)\rightarrow\forallx(\varphi\vee\psi)$$证明过程假设对任意$$M$$和$$g$$，$$V_{M,g}(\forallx\varphi)=1$$。那么，对所有$$d:V_{M,g[x/d]}(\varphi)=1$$（∀-真值条件）对任意$$d$$，由$$V_{M,g[x/d]}(\varphi)=1$$，得$$V_{M,g[x/d]}(\varphi\lor\psi)=1$$（∨-真值条件）这意味着$$V_{M,g}(\forallx(\varphi\lor\psi))=1$$□证明有效性示例3证明：$$\models\forallx\varphi\rightarrow[c/x]\varphi$$证明过程假设对任意$$M$$和$$g$$，$$V_{M,g}(\forallx\varphi)=1$$。那么，对所有$$d\inD:V_{M,g[x/d]}(\varphi)=1$$（∀-真值条件）因为$$I(c)\inD$$，得到$$V_{M,g[x/I(c)]}(\varphi)=1$$根据事实9，得到$$V_{M,g}([c/x]\varphi)=1$$□应用已证明的结论可以被用于后续的证明中练习22证明下列公式是普遍有效的：(1)$$[c/x]\varphi\rightarrow\existsx\varphi$$(2)$$(\forallx\varphi\land\forallx\psi)\rightarrow\forallx(\varphi\land\psi)$$(3)$$\forallx\varphi\rightarrow\existsx\varphi$$(4)$$\existsx\forallyRxy\rightarrow\existsxRxx$$逻辑等值定义20(逻辑等值)$$\varphi$$和$$\psi$$是(逻辑)等值的，当且仅当，对所有$$M$$和$$g$$：$$V_{M,g}(\varphi)=V_{M,g}(\psi)$$记号$$\varphi\Leftrightarrow\psi$$等值的等价刻画事实11下面三个断言是等价的：(1)$$\varphi\models\psi$$和$$\psi\models\varphi$$(2)$$\varphi\Leftrightarrow\psi$$(3)$$\models\varphi\leftrightarrow\psi$$常见逻辑等值式（1）量词与否定$$\forallx\neg\varphi\Leftrightarrow\neg\existsx\varphi$$$$\forallx\varphi\Leftrightarrow\neg\existsx\neg\varphi$$$$\lnot\forallx\varphi\Leftrightarrow\existsx\lnot\varphi$$$$\neg\forallx\neg\varphi\Leftrightarrow\existsx\varphi$$量词与联结词$$\forallx(\varphi\land\psi)\Leftrightarrow\forallx\varphi\land\forallx\psi$$$$\existsx(\varphi\lor\psi)\Leftrightarrow\existsx\varphi\lor\existsx\psi$$常见逻辑等值式（2）量词提取（$$x$$在$$\varphi$$中不自由出现）(7)$$\forallx(\varphi\lor\psi)\Leftrightarrow\varphi\lor\forallx\psi$$(8)$$\existsx(\varphi\land\psi)\Leftrightarrow\varphi\land\existsx\psi$$(9)$$\forallx(\varphi\rightarrow\psi)\Leftrightarrow\varphi\rightarrow\forallx\psi$$(10)$$\forallx(\varphi\rightarrow\psi)\Leftrightarrow\existsx\varphi\rightarrow\psi$$（$$x$$在$$\psi$$中不自由出现）常见逻辑等值式（3）量词交换$$\forallx\forally\varphi\Leftrightarrow\forally\forallx\varphi$$$$\existsx\existsy\varphi\Leftrightarrow\existsy\existsx\varphi$$变元替换（$$y$$在$$\varphi$$中对$$x$$可自由替换）$$\forallx\varphi\Leftrightarrow\forally[y/x]\varphi$$$$\existsx\varphi\Leftrightarrow\existsy[y/x]\varphi$$外延性定理定理9(外延性)$$\forallx_1\dotsx_n(\varphi\leftrightarrow\psi)\models\chi\leftrightarrow[\psi/\varphi]\chi$$其中，$$x_1\cdotsx_n$$在$$\varphi$$和$$\psi$$中是自由出现的变元。意义允许在一个更大的公式中用等值式替代其中的一部分公式等值证明示例证明：$$\existsx(\varphi\lor\psi)\Leftrightarrow\existsx\varphi\lor\existsx\psi$$证明过程根据等值式(4)，$$\existsx(\varphi\lor\psi)$$等值于$$\neg\forallx\neg(\varphi\lor\psi)$$根据德·摩根律，后者等值于$$\lnot\forallx(\lnot\varphi\land\lnot\psi)$$根据等值式(5)，得出其等值于$$\neg(\forallx\neg\varphi\land\forallx\neg\psi)$$再次运用德·摩根律，得$$\lnot\forallx\lnot\varphi\lor\lnot\forallx\lnot\psi$$给定等值式(4)，得出其等值于$$\existsx\varphi\lor\existsx\psi$$□练习23证明前面列出的其他等值式提示使用真值定义利用已证明的等值式应用外延性定理采用结构归纳无效性与反例证明无效性为证明公式$$\varphi$$不是普遍有效的，需要找到至少一个模型$$M$$和指派函数$$g$$，使得$$V_{M,g}(\varphi)=0$$。证明论证模式无效要证明论证模式$$\varphi_1\cdots\varphi_n/\psi$$无效，可以找到一个模型$$M$$和指派函数$$g$$，使得$$V_{M,g}(\varphi_1)=\cdots=V_{M,g}(\varphi_n)=1$$，且$$V_{M,g}(\psi)=0$$。这样的模型和指派函数被称为反例。反例示例论证模式：$$\forallx(Ax\rightarrowBx),\existsx\negBx/\neg\existsxAx$$反例$$D=\{d_1,d_2\},I(A)=I(B)=\{d_1\}$$验证定义域中的每个对象，如果具有性质$$A$$，则必定具有性质$$B$$（前提1真）定义域中确实存在一个不具有性质$$B$$的对象（前提2真）但"没有对象具有性质$$A$$"这一命题并不成立（结论假）练习24构造反例证明下列论证模式是无效的：(1)$$\existsxAx,\existsxBx/\existsx(Ax\landBx)$$(2)$$\forallx(Ax\lorBx),\existsx\negAx,\existsx\negBx,\forallx((Ax\landBx)\rightarrowCx)/\existsxCx$$(3)$$\forallx\existsyRxy/\existsxRxx$$(4)$$\existsx\forallyRxy,\forallxRxx/\forallx\forally(Rxy\veeRyx)$$(5)$$\forallx\existsyRxy,\forallx\forally(Rxy\lorRyx)/\forallx\forally\forallz((Rxy\landRyz)\rightarrowRxz)$$(6)$$\forallx\existsyRxy,\forallx\forally\forallz((Rxy\landRyz)\rightarrowRxz)/\existsxRxx$$3.4自然演绎系统扩展命题逻辑系统将扩展命题逻辑的自然演绎系统，以处理谓词逻辑。规则保留命题逻辑中定义的所有联结词规则将被完整保留。新增规则在此基础上额外引入关于量词的推理规则。这些规则同样分为两类：引入规则与消去规则。重要说明本节将仅涉及句子，也就是说，只考虑那些在公式中不含任何自由变元的推导。替换记号$$[c/x]\varphi$$：将$$\varphi$$中所有自由出现的$$x$$替换为$$c$$的结果。示例$$[c/x]Rxx=Rcc$$$$[c/x][c'/y]Rxy=[c/x]Rxc'=Rcc'$$$$[c/x]\existsyPy=\existsyPy$$$$[c/x][c'/x]Px=Pc'$$注意替换是"由内向外"进行的；替换顺序是相关的。存在量词引入规则$$I_\exists$$引入规则1....m.[c/x]φ...n.∃xφI∃,m规则含义如果一个公式中出现了$$c$$，就可以"抽取"(Extract)$$c$$，并用变元$$x$$替代，从而得出$$\existsx\varphi$$。直观意思包含常元$$c$$单次或多次出现的公式$$\varphi$$可以看作关于$$c$$的一个具体陈述。由此可以得出结论：至少存在一个对象使得该陈述成立（即$$c$$所指的对象）。$$I_\exists$$应用示例示例1：$$Raa\vdash\existsxRxx$$1.RaaA2.∃xRxxI∃,1因为$$Raa=[a/x]Rxx$$示例2：$$Raa\vdash\existsx\existsyRxy$$1.RaaA2.∃yRayI∃,13.∃x∃yRxyI∃,2因为$$Raa=[a/y]Ray$$且$$\existsyRay=[a/x]\existsyRxy$$练习25写出下列推导过程：(1)$$Pa,Qa\vdash\existsx(Px\landQx)$$(2)$$Pa,Qb\vdash\existsxPx\land\existsxQx$$(3)$$Bb\vdash\existsx\existszBz$$全称量词消去规则消去规则$$E_\forall$$1....m.∀xφ...n.[c/x]φE∀,m规则含义如果有$$\forallx\varphi$$，对任意常元$$c$$，可以推导出$$[c/x]\varphi$$。直观意思既然对所有$$x$$都有$$\varphi$$成立，那么对任何具体的对象$$c$$，$$\varphi$$也应该成立。$$E_\forall$$应用示例示例1：$$\forallx\forallyRxy\vdashRaa$$1.∀x∀yRxyA2.∀yRayE∀,13.RaaE∀,2因为$$[a/x]\forallyRxy=\forallyRay$$且$$[a/y]Ray=Raa$$示例2：$$\forallx\forallyRxy\vdashRab$$1.∀x∀yRxyA2.∀yRayE∀,13.RabE∀,2因为$$[a/x]\forallyRxy=\forallyRay$$且$$[b/y]Ray=Rab$$练习26写出下列推导过程(1)$$∀xPx,∀xQx⊢∃x(Px∧Qx)$$(2)$$∀x∀y(Rxy→Sxy),∀x∀y(Sxy→Txy)⊢Rաբ→Tab$$(3)$$Qd,∃xQx→∀xPx⊢Pd$$全称量词引入规则引入规则$$I∀$$1....m.[c/x]φ...n.∀xφI∀,m若满足以下条件条件(1)$$c$$没有出现在任何活跃的假设中条件(2)且$$c$$在$$φ$$中不出现$$I∀$$规则的直觉核心思想在尝试证明某个全称量化公式$$∀xφ$$成立时，通常会使用这一规则。任意性要求由于$$∀xφ$$对论域中的每一个元素都作出断言，可以任选论域中的一个元素，然后检验$$φ$$是否对该元素成立。关键对象（即常元）必须是任意的。两个条件的作用保障$$c$$的任意性违反条件(1)的例子错误推导（违反条件的步骤标注为⋆）：1.PaA2.*∀xPxI∀,1当然$$Pa⊬∀xPx$$，该推导无效。原因$$a$$出现在活跃的假设中，即论证的前件，因而$$a$$的选择不具有任意性。违反条件(2)的例子错误推导1.∀xRxxA2.RaaE∀,13.*∀xRaxI∀,2显然，该推导不应该被接受：$$∀xRxx⊬∀xRax$$。原因条件(2)确保这种推导不会发生：$$a$$出现在导出的$$∀xφ$$中。条件(2)的意义如果将$$I∀$$应用于包含任意常元$$c$$的公式$$[c/x]φ$$，那么$$[c/x]φ$$中所有出现的$$c$$都需要被$$x$$替换，并由引入的量词$$∀x$$约束。$$I∀$$应用示例1示例：$$∀x(Px∧Qx)⊢∀xPx∧∀xQx$$1.∀x(Px∧Qx)A2.Pa∧QaE∀,13.PaE∧,24.QaE∧,25.∀xPxI∀,36.∀xQxI∀,47.∀xPx∧∀xQxI∧,5,6$$I∀$$应用示例2示例$$∀x∀yRxy⊢∀x∀y(Rxy∧Ryx)$$1.∀x∀yRxyA2.∀yRayE∀,13.RabE∀,24.∀yRbyE∀,15.RbaE∀,46.Rab∧RbaI∧,3,57.∀y(Ray∧Rya)I∀,68.∀x∀y(Rxy∧Ryx)I∀,7$$I∀$$应用示例3示例$$¬∃xPx⊢∀x¬Px$$1.¬∃xPxA2.PaA3.∃xPxI∃,24.⊥E¬,1,35.¬PaI¬6.∀x¬PxI∀,5注意虽然$$a$$出现在第2步的假设中，只要该假设不被撤销，$$a$$就不是任意的，但到第6步时，第2步的假设在第5步已经被撤销了，即$$a$$是任意的，所以能够应用$$I∀$$。练习27写出下列推导过程(1)$$∀xPx,∀xQx⊢∀x(Px∧Qx)$$(2)$$∀xPx∨∀xQx⊢∀x(Px∨Qx)$$(3)$$∀x∀yRxy⊢∀y∀xRyx$$(4)$$Qd,∃xQx→∀xPx⊢Pd$$存在量词消去规则消去规则$$E∃$$：1....m₁.∃xφ...m₂.[c/x]φ→ψ...k.ψE∃,m₁,m₂若满足以下条件：条件(1)$$c$$不得出现在任何活跃的假设中条件(2)$$c$$不得出现在$$φ$$中条件(3)不得出现在$$ψ$$中$$E∃$$规则的直觉如何使用$$∃xφ$$？无效例子(3)如果张三来，小丽就会开心。有人来了，所以小丽开心。有效例子(4)如果有人来，小丽就会开心。有人来了，所以小丽开心。规则含义如果$$c$$是任意的，从$$∃xφ$$和$$[c/x]φ→ψ$$可以推导出公式$$ψ$$。三个条件的作用保证$$c$$的任意性违反条件(1)的例子错误推导1.∃x∃yRxyA2.∃yRay→BbA3.*BbE∃,1,2该推导不应被接受：$$∃x∃yRxy,∃yRay→Bb⊬Bb$$。原因：未满足条件(1)，因为$$a$$出现在活跃的假设中，且在运用消去规则的步骤时仍然活跃。违反条件(2)的例子错误推导1.∀x∃yRxyA2.∃yRayE∀,13.RaaA4.∃xRxxI∃,35.Raa→∃xRxxI→6.*∃xRxxE∃,2,5原因：不符合条件(2)：因为$$[a/y]Ray=Raa$$，即$$a$$出现在$$φ$$中。推导受阻：$$∀x∃yRxy⊬∃xRxx$$违反条件(3)的例子错误推导1.∃xRxxA2.RaaA3.∃yRayI∃,24.Raa→∃yRayI→5.*∃yRayE∃,2,46.∀x∃yRxyI∀,5原因第5步中应用$$E∃$$不符合条件(3)：$$a$$出现在$$ψ=∃yRay$$中。推导受阻：$$∃xRxx⊬∀x∃yRxy$$（注意，第6步中应用$$I∀$$是没有问题的）$$E∃$$应用示例1示例：$$∀x(Px→Qx),