19.3 一阶逻辑的推理理论

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【19.3 有效推理】前提Γ={A₁,…,Aₖ}语义蕴涵B,记Γ⊨B,是说每个使前提全真的解释和赋值也使B真;有限Γ时等价于⊨((A₁∧…∧Aₖ)→B)。系统内能写出证明则记Γ⊢B。一个具体解释中前提为假,并不据此判定整个推理形式有效。

【推理定律的来源】(1)命题逻辑推理定律的代换实例,如全称公式的合取消去、析取附加。(2)等值式A⇔B给出A⇒B与B⇒A两条定律。(3)量词定律:

①(∀xA(x))∨∀xB(x)⇒∀x(A(x)∨B(x))。

②∃x(A(x)∧B(x))⇒(∃xA(x))∧∃xB(x)。

③∀x(A(x)→B(x))⇒((∀xA(x))→∀xB(x))。

④原书列“∃x(A(x)→B(x))⇒((∃xA(x))→∃xB(x))”一般不成立。反例D={0,1},A={0}、B=∅:x=1使A→B真,所以左真,但∃A真、∃B假,右假。应使用有效式∀x(A(x)→B(x))⇒((∃xA(x))→∃xB(x));它要求每个可能见证都保持蕴涵,不能仅凭另一个对象使蕴涵空真。

【四条量词规则】A[t/x]表示仅把A中自由x换为项t,要求t可自由代入,即不会被A中的量词捕获;Γ还包括当前所有未撤销的临时假设。

全称消去(∀−):

全称引入(∀+):

这里y为可任意选择的新参数,代入须安全且不能与A中其他自由参数混淆;最稳妥做法是先选完全新鲜的y,证明后再量化。

存在引入(∃+):

存在消去(∃−):

最后一条中c是新的见证参数,不出现在Γ、A、B中;从临时假设A[c/x]推得B后撤销该假设,c不能逃出子证明。用变量参数y时要求y不在Γ、B中自由出现,并安全代入。书中另写A(y)→B推出(∃xA(x))→B,是这种规则的条件证明形式;不能脱离新参数条件使用。

存在引入也可用于从B→A[t/x]推出B→∃xA;前提B仍在子证明中,不能顺手对其自由变量全称推广。个体常项也可作为合法项使用,但其解释必须属于非空域。

【定义19.3.1 自然推理系统】字母表和公式同18.2节。保留命题系统的前提引入、已证结论引入、等值置换、假言推理、附加、化简、拒取、假言三段论、析取三段论、构造性二难、合取引入,再加∀−、∀+、∃−、∃+,共15类规则。证明逐行写出公式、依据和依赖的假设;有条件证明或反证子证明时必须标明撤销范围。

【两类错误示范】(1)从∀x∃yR(x,y)不能不换名就推出∃yR(y,y),替换x为y被内层∃y捕获。R解释为实数上的>,原式由y=x−1恒真,结论要求y>y,恒假。先换内层y为z,正确实例是∃zR(y,z)。

(2)由∀x(P(x)→Q(x))和P(x)可得Q(x),但不能得∀xQ(x),因为x在未撤销前提P(x)中自由出现。整数域P、Q都取偶数性质,σ(x)=2,前提真、全称结论假。任取对象与预先满足特殊条件的对象不是一回事。

【例19.3.1】F(x):自然数,G(x):整数,域R。前提∀x(F(x)→G(x))、∃xF(x),结论∃xG(x)。证明:①选新鲜c,在子证明假设F(c);②∀−得F(c)→G(c);③假言推理得G(c);④∃+得∃xG(x);⑤由∃xF(x)和此子证明作∃−,撤销F(c),得到结论。c不在结论中。(例完)

【例19.3.2】前提∀x(F(x)→G(x))、∃x(F(x)∧H(x)),结论∃x(G(x)∧H(x))。选新鲜c,假设F(c)∧H(c),化简得F(c)、H(c);∀−得F(c)→G(c),得G(c);合取G(c)∧H(c),存在引入∃x(G(x)∧H(x));存在消去撤销见证假设。保留同一个见证,不能分别找两个对象拼成合取。(例完)

【例19.3.3】域R,F:无理数,G:有理数,H:能表示成分数。前提¬∃x(F(x)∧H(x))、∀x(G(x)→H(x)),结论∀x(G(x)→¬F(x))。第一前提等值于∀x(H(x)→¬F(x));任取新参数u,两次∀−得G(u)→H(u)、H(u)→¬F(u),由假言三段论得G(u)→¬F(u)。u不在两项闭前提中自由出现,故∀+得结论。原题旨在训练形式推理,不把“所有学生勤奋”等练习前提误当现实普遍事实。(例完)