人工基础智能及逻辑 12

第2章命题逻辑2.1智能家居系统命题设定逻辑规则场景推理2.2命题逻辑的语言公式定义联结词归纳证明2.3命题逻辑的语义真值表逻辑等值有效性2.4自然演绎系统推导规则引入与消去规则2.5元定理可靠性与完全性计算复杂性2.6结语2.1智能家居系统智能家居系统是命题逻辑实际应用的典型场景，通过逻辑规则管理多种设备的联动。本节将展示一个复杂的智能家居场景，包含：灯光控制窗帘系统安防系统空调控制命题设定基本命题符号用字母分别表示以下命题：a"有人在客厅"b"灯开着"c"窗帘关闭"d"室外亮度较低"e"安防系统已激活"f"窗户关闭"g"空调正在运行"h"室内温度超过30°C"逻辑规则（1）（1）灯光控制$$(a∧d)→b$$"如果有人在客厅且室外亮度较低，则打开灯光。"$$(¬a∨¬d)→¬b$$"如果客厅无人或室外亮度足够，则关闭灯光。"（2）窗帘与灯光联动$$b→c$$"如果灯光打开，则关闭窗帘（防止光污染）。"$$¬b→¬c$$"如果灯光关闭，则打开窗帘。"（3）安防系统$$(¬a∧f)→e$$"如果家中无人且窗户关闭，则激活安防系统。"$$(a∨¬f)→¬e$$"如果家中有人或窗户未关闭，则关闭安防系统。"（4）空调与温度控制$$h→g$$"如果室内温度超过30°C，则启动空调。"$$¬h→¬g$$"如果室温低于30°C，则关闭空调。"具体场景：逻辑推理当前环境状态a=0（客厅无人）d=1（室外亮度较低）h=1（室内温度超过30°C）f=1（窗户关闭）逻辑推理过程根据$$(¬a∨¬d)→¬b$$，灯光应关闭($$¬b$$)根据$$(¬a∧f)→e$$，安防系统激活($$e$$)根据$$h→g$$，空调启动($$g$$)根据灯光关闭($$¬b$$)，窗帘可保持打开($$¬c$$)最终状态与意义最终设备状态灯光关闭窗帘打开安防系统激活空调启动命题逻辑的重要性这个例子展示了如何使用命题逻辑：定义规则进行推理实现多设备的动态联动控制更复杂的任务需要更多命题和推理规则，因此构建智能推理系统显得尤为重要。2.2命题逻辑的语言通过将自然语言中的情景转化为命题逻辑中的符号和推理规则，建立智能系统，并利用其推理引擎快速推导出最优状态。本节系统地引入命题逻辑的形式语言。定义1（公式）公式的递归定义令$$VOC_L$$为命题字母的集合。给定$$VOC_L$$，L的公式集是根据以下规则生成的所有表达式构成的集合：（1）$$VOC_L$$中的所有命题字母都是L的公式；（2）如果$$φ$$是L的公式，那么$$¬φ$$也是L的公式；（3）如果$$φ$$和$$ψ$$是L的公式，那么$$(φ∧ψ)$$、$$(φ∨ψ)$$、$$(φ→ψ)$$和$$(φ↔ψ)$$也是L的公式；（4）只有能在有限步骤内由以上(1)~(3)生成的公式才是L的公式。公式的构成基本概念原子公式：命题字母是公式（常称为原子公式）命题变元：$$φ、ψ$$表示任意命题复合公式：通过$$（2）$$和$$（3）$$生成示例$$(p∧q)$$是公式$$((p∨q)∧(p∨r))$$是公式命题联结词：$$¬,∧,∨,→,↔$$$$¬$$是一元联结词$$∧,∨,→,↔$$是二元联结词简化规则在不引起歧义时，通常省略公式最外层的括号。子公式定义给定一个公式，在它生成过程中的每个步骤所用到的公式都是其子公式。例子考虑公式$$φ=(p→(q∧¬r))$$其所有子公式为$$\{(p→(q∧¬r)),p,(q∧¬r),q,¬r,r\}$$归纳证明方法基于公式复杂性的归纳证明要证明所有公式都具有A属性，只需证明以下三点：（1）命题字母具有A属性；（2）如果公式$$φ$$具有A属性，那么$$¬φ$$也一定具有A属性；（3）如果$$φ$$和$$ψ$$具有A属性，那么$$(φ∧ψ)$$、$$(φ∨ψ)$$、$$(φ→ψ)$$和$$(φ↔ψ)$$也一定具有A属性。原理：定义1的归纳子句(4)保证，每一个复合公式必然是由更简单的公式生成的，并且它从这些更简单的公式中继承了A属性。事实1：括号数量事实1命题逻辑语言的所有公式$$φ$$都有相等数量的左右括号。证明（施归纳于公式复杂度）（1）命题字母不包含括号，结论显然成立；（2）假设公式$$φ$$拥有相等数量的左右括号，那么$$¬φ$$的括号数量没有增减，因此具有相等数量的左右括号；（3）假设公式$$φ,ψ$$拥有相等数量的左右括号，$$($$φ∧ψ$$)$$、$$($$φ∨ψ$$)$$、$$($$φ→ψ$$)$$和$$($$φ↔ψ$$)$$正好添加了一个左括号和一个右括号，因此具有相等数量的左右括号。自然语言的形式化重要性要用命题逻辑研究日常推理，首先需要对自然语言进行形式化，将其转换为命题逻辑的公式，以便精确表达推理过程。这一步至关重要，是正确运用命题逻辑进行分析和推理的基础。练习1用命题逻辑的形式语言表示下面用自然语言表达的规则：如果车辆前方检测到障碍物，则自动驾驶系统将自动制动。如果车辆未完成高精度地图下载，则无法开启自动驾驶功能。如果天气条件恶劣或者道路湿滑，自动驾驶系统会降低车速。若传感器读取的行人距离小于5m且车辆速度大于30km/h，系统会发出警告。如果系统检测到侧方有车辆，则车辆不会变道；否则会根据导航规划变道。2.3命题逻辑的语义为了确定什么样的推理是有效的，本节将首先介绍命题逻辑的语义解释。基本约定用$$1$$表示"真"用$$0$$表示"假"使用真值表解释命题联结词的意义一旦理解了基本联结词的意义，就能够理解任何复合公式的意义。2.3.1真值表本小节将介绍各个命题联结词的真值表定义。命题联结词否定（Negation）：$$¬$$合取（Conjunction）：$$∧$$析取（Disjunction）：$$∨$$蕴涵（Implication）：$$→$$等价（Equivalence）：$$↔$$1.否定（Negation）定义一个公式为真，它的否定为假；一个公式为假，它的否定为真。说明在自然语言中，除了使用"不""不是""没有"等词语表示否定外，还有许多其他的否定表达方式。在对自然语言进行形式化的过程中，需要我们正确辨认。表2-1否定的真值表$$φ$$$$¬φ$$10012.合取（Conjunction）定义一个合取式为真，当且仅当，两个合取肢都为真，否则为假。表2-2合取的真值表$$φ$$$$ψ$$$$φ∧ψ$$1111000100003.析取（Disjunction）相容析取一个析取式为真，当且仅当，其中的一个析取肢为真。这是所谓"相容"析取式的真值表，即不排除两个析取肢都为真的析取。示例我喜欢哲学或计算机科学。可以通过阅读人工智能论文或与专家交流来学习深度学习。表2-3析取的真值表$$φ$$$$ψ$$$$φ∨ψ$$111101011000不相容析取定义不相容析取排除了析取肢都为真的情况。在汉语中通常用要么……要么……的结构表示。示例我要么学习人工智能理论，要么专注于编写代码。你可以要么从事计算机硬件开发，要么专注于软件工程。我们今晚要完成这篇论文，除非下午参加黑客马拉松。约定：在本书中，除非特别说明，当"或者"被使用时，会被理解为是相容析取。表2-4不相容析取的真值表$$φ$$$$ψ$$$$φ⊕ψ$$1101010110004.蕴涵（实质蕴涵）表2-5实质蕴涵的真值表$$φ$$$$ψ$$$$φ→ψ$$111100011001理解要点第二行容易理解：如果$$φ$$为真且$$ψ$$为假，那么$$φ→ψ$$为假。这很直观：要证明"如果$$φ$$，那么$$ψ$$"是假的，只需证明$$φ$$是真的，且$$ψ$$是假的。蕴涵的理解为什么其他行为真？事实上$$φ$$为真而$$ψ$$为假是我们可以断定$$φ→ψ$$为假的唯一情况。因为句子要么真要么假，这就意味着在所有其他情况下$$φ→ψ$$都是真的。例子"如果一个数字大于10，那么它就大于5。"这句话显然是真的。找不到一个数字n可以使得$$n>10$$且$$n\not>5$$。无论选择什么数n，都满足如果$$n>10$$，那么$$n>5$$。这也包括选取一个介于5和10之间的数的情况，即前件为假，后件为真的情况。蕴涵的自然语言表达注意在自然语言中，表示蕴涵的句子并不一定包含如果……（那么）……的表达式。示例为使液体溶解，有必要将其加热到至少60°C。为了让蒸汽消失，将其压力降至99kPa就足够了。改写为标准形式如果液体溶解了，它就被加热到了至少60°C。如果压力降至99kPa，蒸汽就会消失。5.等价表2-6等值的真值表$$φ$$$$ψ$$$$φ↔ψ$$111100010001定义根据表2-6，$$φ$$↔$$ψ$$为真，当且仅当，$$φ$$和$$ψ$$具有相同的真值。说明在数学和逻辑学之外，自然语言中出现当且仅当这一术语的情况非常少见。但是需要辨认句子之间的逻辑关系，做出正确的形式化。6.复合公式的语义计算方法一旦为所有命题字母指定了真值，并对联结词进行了解释，就可以继续使用真值表计算复合公式的真值。表2-7$$(p∨q)∧¬r$$的复合真值表pqrp∨q¬r(p∨q)∧¬r111100110111101100100111011100010111001000000010复合公式真值计算程序通用程序确定任意命题公式$$φ$$的真值：第一步确定在$$φ$$中出现了哪些命题字母$$p₁,p₂,⋯,pₙ$$；第二步绘制一张包含$$2ⁿ$$行的表，并在每一行填入$$p₁,p₂,⋯,pₙ$$的唯一真值组合；第三步按照$$φ$$的构造过程，为其中的每个子公式添加一列，并在每一行中计算其真值。练习2给出下面公式的复合真值表：$$¬¬¬¬p$$$$(p∧q)→¬r$$$$(p∨q)∧(r→¬s)$$$$(p→q)→(p→¬q)$$赋值的概念赋值（Valuation）赋值是一个函数，它为命题语言中的每个公式指派一个真值。重要限制并不是任何函数都可以成为有效的赋值，只有那些符合我们希望赋予联结词解释的函数才是恰当的赋值函数。换句话说，赋值必须确保逻辑联结词（如$$∧$$、$$∨$$、$$¬$$等）的语义解释在赋值中得到正确体现。定义2（赋值真值语义）赋值函数的定义赋值$$V$$是一个从$$FORM_L$$到$$\{0,1\}$$的函数，它满足以下要求：（1）$$V(pᵢ)∈\{0,1\}$$，对于所有的$$pᵢ∈VOC_L$$；（2）$$V(¬φ)=1\⟺V(φ)=0$$；（3）$$V(φ∧ψ)=1\⟺V(φ)=1$$且$$V(ψ)=1$$；（4）$$V(φ∨ψ)=1\⟺V(φ)=1$$或$$V(ψ)=1$$；（5）$$V(φ→ψ)=1\⟺V(φ)=0$$或$$V(ψ)=1$$；（6）$$V(φ↔ψ)=1\⟺V(φ)=V(ψ)$$；说明：这个定义与联结词的真值表是一致的。这里，只需说明公式在何种情况下为真，而其他情况则可以从赋值函数的规则中推导出来。2.3.2逻辑等值、重言式与矛盾式本节将介绍一些命题逻辑的重要概念：逻辑等值两个公式在所有赋值下具有相同真值重言式（Tautology）在所有赋值下均为真的公式矛盾式（Contradiction）在所有赋值下均为假的公式可满足式（Contingency）既非重言式也非矛盾式的公式1.逻辑等值的引入观察考虑复合真值表2-8，有两个不同的公式$$p→q$$和$$¬p∨q$$。如表2-8所示，这两个公式的真假情况在四种情形下完全一致。这时，称这两个公式逻辑等值（LogicallyEquivalent）。表2-8$$p→q$$和$$¬p∨q$$的复合真值表pq¬p$$p→q$$$$¬p∨q$$11011100000111100111逻辑等值的性质重要观察$$p→q$$和$$¬p∨q$$的逻辑等值并不依赖于其中出现的具体字母$$p$$和$$q$$。例如，$$r→s$$和$$¬r∨s$$也是逻辑等值的。关键：逻辑形式这里起作用的是逻辑形式：任何形为$$φ→ψ$$的公式都逻辑等值于形为$$¬φ∨ψ$$的公式。定义3（逻辑等值）定义$$\phi$$和$$\psi$$是逻辑等值的，当且仅当，对于所有赋值$$V$$:$$V(\phi)=V(\psi)$$。意义可以利用赋值真值定义代替真值表，证明两个公式是逻辑等值的。事实2（双重否定）事实2$$φ$$和$$¬¬φ$$是逻辑等值的。证明对任意的赋值$$V$$。假设$$V(φ)=1$$。那么$$V(¬φ)=0$$（根据赋值真值定义的第(2)条），进一步$$V(¬¬φ)=1$$（同上）。$$V(φ)=0$$的情况类似。练习3：逻辑等值关系证明下列公式是逻辑等值的1.$$φ$$,$$¬¬φ$$,$$φ∧φ$$,$$φ∨φ$$,$$φ∧(φ∨ψ)$$,$$φ∨(φ∧ψ)$$2.$$¬φ$$,$$φ→(ψ∧¬ψ)$$3.$$¬(φ∨ψ)$$,$$¬φ∧¬ψ$$（德·摩根律）4.$$¬(φ∧ψ)$$,$$¬φ∨¬ψ$$（德·摩根律）5.$$φ∨ψ$$,$$ψ∨φ$$（∨交换律）6.$$φ∧ψ$$,$$ψ∧φ$$（∧交换律）7.$$φ∧(ψ∨χ)$$,$$(φ∧ψ)∨(φ∧χ)$$（分配律）练习3（续）8.$$φ∨(ψ∧χ)$$,$$(φ∨ψ)∧(φ∨χ)$$（分配律）9.$$φ→ψ$$,$$¬φ∨ψ$$,$$¬(φ∧¬ψ)$$,$$¬ψ→¬φ$$10.$$φ→ψ$$,$$¬ψ→¬φ$$（逆否律）11.$$φ↔ψ$$,$$(φ→ψ)∧(ψ→φ)$$,$$(φ∧ψ)∨(¬φ∧¬ψ)$$12.$$(φ∨ψ)∧¬(φ∧ψ)$$,$$¬(φ↔ψ)$$,$$¬φ↔ψ$$13.$$(φ∨ψ)→χ$$,$$(φ→χ)∧(ψ→χ)$$14.$$φ→(ψ∧χ)$$,$$(φ→ψ)∧(φ→χ)$$15.$$φ→(ψ→χ)$$,$$(φ∧ψ)→χ$$定理1（替换）定理如果$$φ$$和$$ψ$$逻辑等值，那么$$χ$$与[$$φ$$/$$ψ$$]$$χ$$也逻辑等值。符号说明[$$α$$/$$β$$]$$γ$$表示用$$α$$替换$$γ$$中$$β$$的出现而得到的结果。证明思路施归纳于$$χ$$的结构。注意：$$φ$$,$$ψ$$,$$χ$$是复杂公式；命题字母根据定义是不等值的，且不包含子公式。替换定理的证明（部分）情况1：$$χ=¬ψ$$那么$$[φ/ψ]χ=¬φ$$因为对于所有的$$V$$:$$V(φ)=V(ψ)$$，所以对所有的$$V$$:$$V(¬φ)=V(¬ψ)$$。情况2：$$χ=ψ∧ξ$$那么$$[φ/ψ]χ=φ∧ξ$$因为对于所有的$$V$$:$$V(φ)=V(ψ)$$，所以，对所有的$$V$$:$$V(ψ∧ξ)=V(φ∧ξ)$$。其余情况留待读者自行验证。替换定理的意义真值条件特性替换定理揭示了命题语言公式的真值条件特性。核心原理由于公式的真假只取决于其子公式的真假，具有相同真值的等值公式可以相互替换，而不会改变整个公式的真值。练习4根据练习3中给出的等值式，证明下列公式是等值的：$$φ$$↔$$ψ$$和$$ψ$$↔$$φ$$（交换律）$$φ→¬φ$$和$$¬φ$$$$φ∧(ψ∧χ)$$和$$χ∧(ψ∧φ)$$$$φ⊕ψ$$和$$φ$$↔$$¬ψ$$$$φ⊕¬ψ$$,$$¬φ⊕ψ$$和$$φ$$↔$$ψ$$实质等值与逻辑等值的联系观察表2-9是一个简单的示例。对任意赋值$$V$$:$$V(φ)=V(¬¬φ)$$，因此，对任意$$V$$:$$V(φ↔¬¬φ)=1$$。表2-9$$φ$$↔$$¬¬φ$$的复合真值表$$φ$$$$¬φ$$$$¬¬φ$$$$φ↔¬¬φ$$10110101事实3事实3$$φ$$和$$ψ$$是逻辑等值的⟺对于任意赋值$$V$$:$$V(φ↔ψ)=1$$。说明显然，这对任意两个逻辑等值公式及其对应的实质等值关系都是成立的。2.重言式定义总是为真的公式构成了一个特殊的类别，称为重言式。例如，$$φ$$↔$$¬¬φ$$定义4（重言式）公式$$φ$$是重言式，记作：$$⊨φ$$，当且仅当，对于任意赋值$$V(φ)=1$$。重言式的证明方法两种证明方法与逻辑等值的情况一样，可以通过：给出复合真值表通过赋值真值定义来证明例子$$⊨φ→(ψ→φ)$$可由复合真值表2-10表示。表2-10$$φ→(ψ→φ)$$的复合真值表$$φ$$$$ψ$$$$ψ→φ$$$$φ→(ψ→φ)$$1111101101010011重言式的另一种证明证明假设$$φ→(ψ→φ)$$不成立，那么一定存在一个赋值$$V$$:$$V(φ)=1$$且$$V(ψ→φ)=0$$。如果$$V(φ)=1$$，那么$$V(ψ→φ)=1$$，因此有$$V(φ→(ψ→φ))=1$$。这与假设相矛盾，因此最初的假设不成立。方法：这个证明使用了所谓的归谬法（ReductioadAbsurdum）。要证明某个事实为真，先假设其为假，进一步说明依据这个假设会得到矛盾结论。练习5：证明重言式练习5证明下列公式是重言式（对于任意的$$φ$$、$$ψ$$和$$χ$$）：$$¬φ→(φ→ψ)$$（爆炸律）$$φ∨¬φ$$（排中律）$$(φ→(ψ→χ))→((φ→ψ)→(φ→χ))$$$$(φ→ψ)∨(ψ→φ)$$$$((φ→ψ)→φ)→φ$$（皮尔士律）练习6：判断重言式练习6判断下列公式是否为重言式：$$（¬p∨¬q）→¬（p∨q）$$$$((p∨q)∧(¬p→¬q))→q$$$$((p→q)→p)→((p→q)→q)$$$$((p→q)→r)→(p→(q→r))$$矛盾式定义与重言式相反的是那些永远为假的公式$$φ$$，被称为矛盾式，即对每个赋值$$V:V(φ)=0$$。例子$$φ∧¬φ$$是矛盾式，见表2-11。表2-11$$φ∧¬φ$$的复合真值表$$φ$$$$¬φ$$$$φ∧¬φ$$100010重言式与矛盾式的关系事实4如果$$φ$$是重言式，那么$$¬φ$$就是矛盾式。事实5如果$$φ$$是矛盾式，那么$$¬φ$$就是重言式。重要性质同重言式一样，所有的矛盾式都等值。可满足式定义除了重言式和矛盾式，第三类公式叫作（逻辑）可满足式。这些公式既不是重言式也不是矛盾式，即对于公式$$φ$$：既存在赋值$$V(φ)=1$$也存在赋值$$V(φ)=0$$特点在可满足式的真值表中，至少有一行是$$1$$，且至少有一行是$$0$$。与重言式和矛盾式不同，可满足式之间并不都是等值的。事实6事实6$$φ$$是可满足式，当且仅当，$$¬φ$$是可满足式。练习7令$$φ$$为重言式，$$ψ$$为矛盾式，$$χ$$为可满足式。判断下列哪些句子(i)是重言的，(ii)是矛盾的，(iii)是可满足的，(iv)是逻辑等值于$$χ$$的：$$φ∧χ$$(5)$$φ∧ψ$$$$φ∨χ$$(6)$$φ∨ψ$$$$ψ∧χ$$(7)$$χ→ψ$$$$ψ∨χ$$2.3.3有效性引言重言式是永真的公式，是普遍规律矛盾式是永假的公式，是在推理和思维中要绝对避免的要研究从前提到结论的逻辑推理，本节最后介绍一个重要的概念：有效性。定义5（论证模式）定义论证模式是一连串的公式$$φ₁,⋯,φₙ/ψ$$，其中：$$φ₁,⋯,φₙ$$称为前提$$ψ$$为结论定义6（有效性）定义一个论证模式$$φ₁,⋯,φₙ/ψ$$是有效的，当且仅当，对所有赋值$$V:V(φ₁)=⋯=V(φₙ)=1⟹V(ψ)=1$$。意义如果前提的真必然得到结论的真，那么论证模式就是有效的。或者换一种说法，不可能前提全部为真而结论为假。符号有效性：$$φ₁,⋯,φₙ⊨ψ$$无效：$$φ₁,⋯,φₙ⊭ψ$$特殊情况：当$$n=0$$时，$$φ₁,⋯,φₙ/ψ$$的有效性就会简化为$$ψ$$是重言式。有效性的证明方法两种证明方法与证明两个公式等值或一个公式是重言式的情况类似，命题逻辑中的论证模式的有效性既可以通过：真值表证明赋值真值定义和有效性定义加以证明真值表证明示例例子：$$p→(q∧r),q→¬r/¬p$$表2-12$$p→(q∧r),q→¬r/¬p$$的复合真值表pqrq∧rp→(q∧r)¬rq→¬r/¬p11111000110001101010001010000110011110010100111*10010101*10000111*1说明：用/列标注所有前提都是1的行（标记*）。如果结论在所有这些行中也都是1，那么该论证就是有效的。赋值真值定义证明示例证明假设该论证不是有效的，那么存在一个赋值V，使得$$V(p→(q∧r))=V(q→¬r)=1,V(¬p)=0$$（假设）那么$$V(p)=1$$（¬）所以$$V(q∧r)=1$$（前提一，→）那么$$V(q)=V(r)=1$$（∧）$$V(q)=1$$蕴涵$$V(¬r)=1$$（前提二，→）因此$$V(r)=0$$（¬）与$$V(r)=1$$相矛盾假设不成立，从而证明该论证是有效的。无效论证的例子例子：$$p→q$$,$$q$$/$$p$$（也称为"肯定后件的谬误"）表2-13$$p→q,q/p$$的复合真值表$$p$$$$q$$$$p→q$$$$/p$$111*11000011*00010反例有两行的前提都是1，其中一行的结论是0，这一行是前提为真而结论为假的情况，称为反例。使用复合真值表是寻找反例的一种高效的方法。练习8判断下列论证模式是否有效。如果模式无效，请给出反例。1–5$$p∧q/p$$$$p,¬p/q$$$$p∧q/q$$$$p→(q∧¬q)/¬p$$$$p∨q/p$$6–9$$p∨q,p→r,q→r/r$$$$p,q/p∧q$$$$p∨q,(p∧q)→r/r$$$$p/p∨q$$练习8（续）10–14$$p∨q,p→q/q$$$$q/p∨q$$$$p∨q,p→q/p$$$$p/p∧q$$$$p→q,¬q/¬p$$15–18$$p,p→q/q$$$$p→q/¬p→¬q$$$$p,q→p/q$$2.4自然演绎系统从语义到语法2.3节学习了如何使用语义的方法判断推理的有效性。本节将转向语法的视角介绍自然演绎系统，给出规则确保能够在该系统中进行严格的逻辑推导。推导的基本形式什么是推导？公式$$χ$$的推导是由公式组成的、有带编号的列表$$χ₁⋯χₘ⋯$$，且该列表以公式$$χ$$作为最后一个元素。推导的形式1.$$χ₁$$⋮m.$$χₘ$$⋮n.$$χ$$推导的标记两种得到公式的方式1.运用有穷规则中的一条规则2.基于假设标记方法注明所用规则，并标出运用该规则的公式行号如果是假设，则用A表示具体形式1.χ₁A⋮m.χₘRₖ,j⋮n.χRₗ,h,m假设的类型活跃假设与撤销假设关于假设，需要区分是："活跃的"（Active）假设"撤销的"（Withdrawn）假设稍后在讨论蕴涵规则时再讨论撤销的假设。论证前提注意，论证给出的前提总是活跃的假设，按照惯例，它们列在一个推导的开头。从前提出发的推导标准形式ψ从前提φ₁⋯φₙ出发的推导具有如下形式：1.φ₁A⋮n.φₙA⋮m.ψ符号表示用φ₁⋯φₙ⊢ψ表示论证模式φ₁⋯φₙ/ψ的推导。自然演绎的基本思想引入规则与消去规则自然演绎的基本思想是，每个联结词都有两条规则：引入规则（IntroductionRule）说明如何获得具有某种形式的公式消去规则（EliminationRule）说明如何使用具有某种形式的公式以下先介绍二元联结词∧、∨、→的引入和消去规则。1.合取的引入规则引入规则I∧⋮m₁.φ⋮m₂.ψ⋮n.φ∧ψI_∧,m₁,m₂说明I∧说的是，为了推导出一个合取式φ∧ψ，需要推导出它的两个合取肢，φ和ψ，或者，这两个合取肢是假设集中的公式。合取引入规则的例子证明p,q,r⊢q∧(p∧r)1.pA2.qA3.rA4.p∧rI∧,1,35.q∧(p∧r)I∧,2,4合取的消去规则消去规则E∧⋮m.φ∧ψ⋮k.φE∧,m并且⋮m.φ∧ψ⋮k.ψE∧,m说明E∧是一条规则，分成两部分：可以用合取式φ∧ψ分别推导它的两个合取肢，φ和ψ。合取交换律的证明例子："合取的交换律"p∧q/q∧p1.p∧qA2.pE∧,13.qE∧,14.q∧pI∧,3,2练习9证明下列论证模式是有效的：(p∧q)∧r⊢p∧(q∧r)（合取的结合律）p⊢p∧pp∧(q∧r)⊢r∧pp∧(q∧r)⊢(p∧q)∧(p∧r)(φ∧q)∧(p∧r)⊢p∧(q∧r)2.蕴涵的消去规则消去规则E→⋮m₁.$$φ→ψ$$⋮m₂.$$φ$$⋮k.$$ψ$$E→,m₁,m₂说明蕴涵的消去规则非常容易理解。如果有一个蕴涵式$$φ→ψ$$，它可能是推导的中间步骤，也可能是假设，只要得到前件$$φ$$，下一步就可以推导出$$ψ$$。蕴涵消去规则的例子证明p→(q∧r),r→s,p/s是有效的1.p→(q∧r)A2.r→sA3.pA4.q∧rE_→,1,35.rE_∧,46.sE_→,2,5练习10证明下列论证模式是有效的1.p∧r,r→q⊢p∧q2.p∧q,p→r,q→s⊢r∧s3.p,q,p∧q→r⊢r4.p∧q,p→(q→r)⊢r蕴涵的引入规则引入规则I→⋮m.φA⋮n-1.ψ─────────────────────n.φ→ψI→说明为推导出蕴涵式φ→ψ，首先引入前件φ作为假设，推导出后件ψ，然后撤销假设φ的同时推导出该蕴涵式。在这样的推导中，假设φ是在第m步提出的，在后面的第n步中撤销的，在第m+1步到第n-1步中是活跃的。强化前提的例子简单例子：同时使用了蕴涵的两种规则1.p→qA2.p∧rA3.pE∧,24.qE→,1,3─────────────────────5.(p∧r)→qI→这是一个"强化前提"的例子。蕴涵的传递性例子：证明p→q,q→r/p→r是有效的1.p→qA2.q→rA─────────────────────3.pA─────────────────────4.qE_→,1,35.rE_→,2,46.p→rI_→关于假设的问题活跃假设与撤销假设上面的例子表明，一个推导可以同时包含活跃和撤销的假设：p→q和q→r是活跃的假设（即论证的前提）p是撤销的假设p在提出时（第3步）是活跃的，直到第6步撤销。表示方法在推导中，从假设提出到假设撤销的步骤之间画一条线，表示该假设在此期间是活跃的。假设使用的条件正确使用假设的条件（1）撤销的假设不能在后续推导中继续使用。（2）如果一个公式依赖于已撤销的假设，那么假设撤销后，该公式也无法再使用。（3）如果有多个假设，应先撤销最后一个提出的假设。下面举例说明，当不满足这些条件时会导致哪些问题。违反条件（1）的例子错误示例─────────────────────1.p∧qA2.pE_∧,1─────────────────────3.(p∧q)→pI_→*4.qE_∧,1问题推导的第4步对p∧q使用了合取消去规则，但是这个公式是一个被撤销的假设，因此不再可用。如果允许这样做，就可以在没有任何假设的情况下推导出q，即q本身的有效性的证明。违反条件（2）的例子错误示例1.q→rA─────────────────────2.p∧qA3.qE∧,2─────────────────────4.(p∧q)→qI→*5.rE→,1,3问题在第5步中，使用了一个公式q，该公式是在假设p∧q的基础上推导出来的，而在推导过程中，假设p∧q已被撤销。违反条件（3）的例子错误示例1.p→qA2.pA3.qE_→,1,2*4.(p→q)→qI_→问题第4步撤销了一个假设，即p→q，从而抛弃了另一个假设，即p，这个假设是后来提出的，在该阶段仍然活跃。正确的撤销顺序按正确的顺序撤销假设从后往前的顺序撤销假设，就能得到正确的结果：─────────────────────1.p→qA─────────────────────2.pA3.qE_→,1,24.p→qI_→─────────────────────5.(p→q)→(p→q)I_→能够清楚地看到假设在哪里起作用。练习11证明下列论证模式是有效的1.⊢(p→(q→r))→((p∧q)→r)2.⊢(p→(p→q))→(p→q)3.p→q,p→r⊢p→(q∧r)4.p→(q→r)⊢(p∧q)→r重复规则RepetitionRule顾名思义，重复规则允许重复使用已经得到的公式：⋮m.φ⋮n.φRep,m使用条件被重复使用的公式不能是已撤销的假设，也不能依赖于已撤销的假设。例子：在推导⊢p→(q→p)时派上了用场错误使用下面的推导不满足条件会导致错误：重复规则的表达力重要说明事实上，重复规则并没有给系统增加任何表达力，它的作用也可以通过已有的规则实现。例子可以通过对φ运用I∧得到φ的"重复"，然后通过运用E∧从结果中推导出φ：练习12（1）展示如何使用蕴涵规则模拟重复规则的效果。（2）给出两个不同的推导证明⊢q→((p→q)→q)，一个使用重复规则，另一个不使用重复规则。3.析取的引入规则引入规则I∨m.φ⋮n.φ∨ψI_∨,m且m.ψ⋮n.φ∨ψI_∨,m说明这条规则不言自明：要推导出一个析取式φ∨ψ，只要推导出其中一个析取肢就足够了。析取的消去规则如何使用析取式？消去规则稍微复杂一些。如果有p∨q，无论是作为假设还是推导结果，能从中推导出什么呢？显然，p和q都不能直接从p∨q中推导出来。间接作用它的用途是间接的：如果能从每个析取肢中推导出同一个公式，那么通过这个析取式，就能推导出该公式。这正是消去规则的作用。析取消去规则E∨消去规则E∨⋮m₁.φ∨ψ⋮m₂.φ→χ⋮m₃.ψ→χ⋮k.χE∨,m₁,m₂,m₃说明因此，如果从假设φ和假设ψ分别可以推导出χ，同时有析取式φ∨ψ，那么就可以从φ∨ψ推导出χ。析取消去规则的例子证明p∨q⊢((p→q)→q)练习13证明下列论证模式是有效的1.p∨q⊢q∨p2.p∨(p∧q)⊢p3.p∨(q∨r)⊢(p∨q)∨r4.(p∨q)→r⊢p→r5.p∧(q∨r)⊢(p∧q)∨(p∧r)4.否定的消去规则复杂性关于否定的规则比二元联结词的情况更为复杂。这种复杂性与逻辑的强弱有关。消去规则E¬⋮m.¬φ⋮k.φ⋮n.⊥E¬,m,k恒假符号⊥是一个特殊的原子公式，叫作恒假（Falsum），表示矛盾式。否定消去规则的说明规则E¬的含义根据E¬，如果一个推导中同时得到¬φ和φ，那么结论可以得到⊥。例子：证明p,q→¬p,q⊢⊥1.pA2.q→¬pA3.qA4.¬pE→,2,35.⊥E¬,1,4注意在命题逻辑语言中添加⊥作为新的表达式，是为方便起见。也可以使用任意矛盾式代替⊥，例如q∧¬q。否定的引入规则引入规则I¬⋮m.φA⋮n-1.⊥─────────────────────n.¬φI¬说明如果从假设φ出发进行推导，最终得到⊥，那么下一步可以撤销假设、推导出¬φ。否定规则的例子证明⊢¬(p∧¬p)：同时使用了E¬和I¬─────────────────────1.p∧¬pA2.pE∧,13.¬pE∧,14.⊥E¬,2,3─────────────────────5.¬(p∧¬p)I¬练习14给出推导证明⊢¬((p→q)∧(p∧¬q))p→q,p→¬q⊢¬p⊢p→¬¬p⊢(p→q)→(¬q→¬p)¬p∨q⊢p→q¬p∨¬q⊢¬(p∧q)注意¬(p∧¬p)是¬(φ∧¬φ)的一个实例，被称为"无矛盾律"（PrincipleofNon-Contradiction）。EFSQ-规则（爆炸原则）ExFalsoSequiturQuodlibet拉丁语"ExFalsoSequiturQuodlibet"（EFSQ），意为"从矛盾中可以得出任何结论"。规则⋮n-1.⊥n.φEFSQ,n-1意义EFSQ-规则体现了系统中出现矛盾⊥的一个重要特性。EFSQ规则的应用例子：p∨q,¬p⊢q展示了EFSQ的作用1.p∨qA2.¬pA─────────────────────3.pA4.⊥E_¬,2,35.qEFSQ,46.p→qI_→─────────────────────7.qA8.q→qI_→─────────────────────9.qE_∨,1,6,8练习15推导证明下列公式是有效的1.⊢¬p→(p→q)2.⊢(p∧¬p)→q3.⊢(p→q)→((p→¬q)→(p→r))4.⊢((p→q)→p)→p双重否定规则最后一个规则：¬¬规则双重否定规则是自然演绎系统中的最后一条规则，用于处理双重否定的消去与引入。双重否定规则的应用例子：推导q→p,¬q→p⊢p展示了如何运用双重否定规则重要说明由上述所有规则构成的自然演绎系统所刻画的逻辑，与2.3节中语义刻画的逻辑相同，即古典逻辑。2.5元定理本节简要介绍逻辑系统的几个重要元定理，特别是一些计算性质。核心问题前文讨论了研究推理的两种方法——语义方法和语法方法，一个自然的问题是，它们之间的关系如何？核心定理可靠性和完全性定理正是回答这一问题的。定理2（可靠性）设$$Γ$$是命题公式的集合，$$φ$$是一个命题公式。如果$$Γ⊢φ$$，则$$Γ⊨φ$$。证明思路只需证明每个推理规则（引入和消去规则）都是"保真"的，即对任意的语义模型而言，若前提为真，结论一定为真。定理3（完全性）设Γ是命题公式的集合，φ是一个命题公式。如果Γ⊨φ，则Γ⊢φ。证明思路假设某公式φ不能从Γ推出（Γ⊬φ），可以使用极大一致集（MaximalConsistentSet）构造一个"反模型"，即一个使Γ中所有公式为真、但φ为假的模型。得到Γ⊭φ，由此通过逆否命题（Contraposition）可以得到：如果Γ⊨φ，就必然有Γ⊢φ。强完全性与弱完全性强完全性定理上面的定理一般称为强完全性定理。弱完全性定理当Γ为空集时，该定理又称为弱完全性定理。弱完全性定理是强完全性定理的特例。参考文献关于这些定理的详细证明，感兴趣的读者可参考文献ChiswellandHodges(2007)。判定问题计算角度的问题在命题逻辑中，有几个重要的判定问题可以从计算的角