17.2 自然推理系统P

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【17.2 自然推理系统P】证明是有限公式序列,每行说明它是前提,还是由此前哪几行按哪条规则得出。不能把想证明的结论未经许可当永久前提,也不能引用尚未证明的后续行。

【定义17.2.1 形式系统】由字母表A、合式公式集E、公理集Ax、推理规则集R组成,记(A,E,Ax,R)。前两项构成形式语言,后两项构成形式演算。自然推理侧重从给定假设推出相对结论,公理式演算侧重从列明公理和规则推导定理;并非任意形式系统的所有公理、定理都无条件是逻辑重言式,只有在相应逻辑公理及可靠规则的条件下才如此。不能将数学理论的特定公理与全部真值赋值上的永真式混为一谈。

【定义17.2.2 系统P】字母表含命题变项p,q,r,…及带下标变项、联结词¬,∧,∨,→,↔与括号逗号;合式公式沿用15.2。其公理集为空,使用给定前提及以下规则。

(1)前提引入:可随时引用Γ中已给前提。(2)已证结论重用:在同一有效假设范围内,已证公式可供后续引用。(3)等值置换:完整子公式可换成全局等值的公式。

(4)假言推理(分离):

(5)附加规则:

(6)化简规则:

(7)拒取式:

(8)假言三段论:

(9)析取三段论:

(10)构造性二难:

(11)破坏性二难:

(12)合取引入:

等价三段论可由等值式展开为两个方向的蕴涵,再用假言三段论组合得到,属于可派生规则。规则的分式横线表示由上面的前提导出下面的结论,不是数值相除。

【证明的定义】C₁,…,Cₘ中每项均为Γ的前提,或由序列先前公式按规则导出,且Cₘ=B,则是Γ⊢B的证明。逐行检查规则可保证Γ⊨B;有临时假设时还需记录其作用域及撤销步骤。

【例17.2.1】(1)前提p∨q、q→r、p→s、¬s,结论r∧(p∨q)。①p→s(前提);②¬s(前提);③¬p(①②拒取);④p∨q(前提);⑤q(③④析取三段论);⑥q→r(前提);⑦r(⑤⑥分离);⑧r∧(p∨q)(⑦④合取)。

(2)前提¬p∨q、r∨¬q、r→s,结论p→s。①¬p∨q;②p→q(①等值置换);③r∨¬q;④q→r(③交换及蕴涵式);⑤p→r(②④假言三段论);⑥r→s;⑦p→s(⑤⑥假言三段论)。原题第一句p前有¬,漏掉后结论不再有此证明。(例完)

【例17.2.2】p:a为实数,q:a有理,r:a无理,s:a可写为整数之比。前提p→(q∨r)、¬s→¬q、p∧¬s,结论r。①p∧¬s;②p(化简);③¬s(化简);④p→(q∨r);⑤q∨r(②④);⑥¬s→¬q;⑦¬q(③⑥);⑧r(⑤⑦析取三段论)。应将“分数”明确为整数之比且分母非0,而非任意实数的除法表达。(例完)

【附加前提证明法】要证Γ⊨A→B,可在临时假设A下推出B,再撤销A,得到A→B。理由是T→(A→B)⇔(T∧A)→B,其中T为原前提合取。B本身仍可能依赖临时A,撤销后只能保留A→B,不能直接宣称Γ⊨B。

【例17.2.3】p、q、r、s依次为小张、小王、小李、小赵去看电影。前提(p∧q)→r、¬s∨p、q,证s→r。临时①s;②¬s∨p(原前提);③p(①②析取三段论);④q(原前提);⑤p∧q(③④);⑥(p∧q)→r(原前提);⑦r(⑤⑥);⑧撤销①,得s→r。这样写出最后撤销行,比仅写到r更完整。(例完)

【归谬法】证Γ⊨B时,临时引入¬B,若推出D及¬D或0,说明T∧¬B不可满足,故T→B永真。最后须撤销¬B并得B;在本章经典逻辑下可用反证法,不能把局部矛盾作用域外的临时假设当作仍在使用。

【例17.2.4】p:小张守第一垒,q:小李向B队投球,r:A队取胜,s:A队联赛第一。前提(p∧q)→r、¬r∨s、¬s、p,证¬q。

临时①q(否定结论的否定,¬¬q等值于q);②¬r∨s、③¬s(原前提);④¬r(②③);⑤(p∧q)→r(原前提);⑥¬(p∧q)(④⑤拒取);⑦¬p∨¬q(⑥德摩根);⑧¬p(①⑦析取三段论);⑨p(原前提);⑩p∧¬p(⑧⑨);⑪撤销①,得¬q。

也可直接由⑦与p推出¬q,无须临时假设。两种方式都不能漏掉前提¬r∨s和¬s中的否定。(例完)