习题19

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题19】共25组,保留题号并补出必要的证明与反例。所有前束化均在非空域中进行,先安全换名,再移动量词;所有存在消去均用新鲜见证参数。

【19.1】D={a,b,c},原式∀x(F(x)∧∃yG(y))。乙的关键步骤是∃yG(y)不含自由x,因而可移出∀x辖域,得到(∀xF(x))∧∃yG(y),再展开成(F(a)∧F(b)∧F(c))∧(G(a)∨G(b)∨G(c))。甲先展开内部∃再展开∀也正确;只是重复同一析取式三遍,利用结合、交换、幂等律可化到乙的结果。

【19.2】D={a,b,c},将有限合取、析取完全写出;第(4)中的y仍自由,不能替换为新加的量词见证。

(1)∀x∃y(F(x)∧G(y))⇔(F(a)∧F(b)∧F(c))∧(G(a)∨G(b)∨G(c))。

(2)∀x∀y(F(x)∨G(y))⇔(F(a)∨G(a))∧(F(a)∨G(b))∧(F(a)∨G(c))∧(F(b)∨G(a))∧(F(b)∨G(b))∧(F(b)∨G(c))∧(F(c)∨G(a))∧(F(c)∨G(b))∧(F(c)∨G(c))。

(3)(∀xF(x))→∀yG(y)⇔(F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c))。

(4)∀x(F(x,y)→∃yG(y))⇔(F(a,y)→(G(a)∨G(b)∨G(c)))∧(F(b,y)→(G(a)∨G(b)∨G(c)))∧(F(c,y)→(G(a)∨G(b)∨G(c)))。

【19.3】D={1,2},要求两式∀x(F(x)→G(x))、∃x(F(x)∧G(x))在同一解释同时真或同时假。I₁取F=G={1},两式真;I₂取F={1}、G={2},第一个在1处前真后假,第二个无交集,两式都假。不能给两式分别选不同的I₁来替代题意。

【19.4】A=(∃xF(x))→∀xF(x)。(1)单元素域{a}上等值F(a)→F(a),无论F如何解释都真。(2)n≥2时不一定,取F={a₁},存在前件真、全称后件由a₂反驳。若F=∅或F=D,A又真,故域大小本身不能确定A。

【19.5】D={3,4},f交换两元素,F为“不相等”关系。(1)∀x∃yF(x,y)真,每个x取另一个元素。(2)∃x∀yF(x,y)假,任取x,y=x时F假。(3)∀x∀y(F(x,y)→F(f(x),f(y)))真;x=y时前件假,x≠y时交换后仍不同,逐一检查四对也得到1。

【19.6】乙正确,甲的伸缩不合法:G(x,y)含自由x,违反另一分支不得含自由x的条件。反例D={0,1}、F=D、G={(0,0)}、σ(x)=σ(y)=0:原式∀x(F(x)→G(x,y))在x=1处假;甲所得(∃xF(x))→G(x,y)却真,故不等值。

【19.7】原演算从¬∃x∀y(F(x)∧(G(y)→H(x,y)))开始。第一处错误只翻转量词却丢掉内部否定;第二处把F∧(G→H)改成(F∧G)→H,不是有效命题等值。正确结果:∀x∃y¬(F(x)∧(G(y)→H(x,y)))⇔∀x∃y(¬F(x)∨(G(y)∧¬H(x,y)))。例如F假时第二种错误变形的后式可真而前式假。

【19.8】(1)域R,P(x):正数,N(y):负数,L(x,y):x<y。两种等值形式为¬∃x∃y(P(x)∧N(y)∧L(x,y))和∀x∀y((P(x)∧N(y))→¬L(x,y))。

(2)域为角,E(x,y):两角相等,V(x,y):两角互为对顶角。“相等未必为对顶角”写¬∀x∀y(E(x,y)→V(x,y)),或∃x∃y(E(x,y)∧¬V(x,y))。若上下文限定两个不同的角,则在两式的限制条件中都补x≠y;不能一式补一式不补。这里不是“每对相等角都不是对顶角”。

【19.9】错误是把∃对∧当作可分配的等值。存在有理数与存在无理数,可分别有不同见证,例如0与√2;不能推出存在同一个数兼具两性质。只有∃x(F(x)∧G(x))⇒(∃xF(x))∧∃xG(x)一般成立,反向不成立。

【19.10】¬∃x(F(x)∧G(x))本身不是前束范式,因为最前是¬,不是量词前缀或无量词母式;它等值于前束式∀x(¬F(x)∨¬G(x))。“能化为”不等于“已经是”。

【19.11】同名指导变元不妨碍换名前束化。原题写(∀x(F(x)→G(x)))→∃xG(x,y),却同时用G的一元、二元形式;严格语言中应区分G₁和G₂。按修正记号,先换名为(∀t(F(t)→G₁(t)))→∃uG₂(u,y),得到∃t∃u((F(t)→G₁(t))→G₂(u,y))。y仍自由;更名修复元数问题与α换名是两件不同的事。

【19.12】逐题前束化,所列为一种结果,不要求唯一。

(1)(∀xF(x))→∀yG(x,y)⇔∃t∀y(F(t)→G(x,y)),右侧的自由x保留。

(2)∀x(F(x,y)→∃yG(x,y,z))⇔∀x∃t(F(x,y)→G(x,t,z)),自由y、z保留。

(3)(∀xF(x,y))↔∃xG(x,y)。注意原题是↔。拆成两个蕴涵,并为两份拷贝分别换名:[(∀uF(u,y))→∃vG(v,y)]∧[(∃wG(w,y))→∀tF(t,y)],得∃u∃v∀w∀t((F(u,y)→G(v,y))∧(G(w,y)→F(t,y)))。不能把↔当成→只处理一次。

(4)(∀x₁(F(x₁)→G(x₁,x₂)))→((∃x₂H(x₂))→∃x₃L(x₂,x₃))。为约束变量取u、v、w,前束式∃u∀v∃w((F(u)→G(u,x₂))→(H(v)→L(x₂,w)))。x₂始终自由,不能被中间的∃x₂捕获;内层前件∃移出变∀。

(5)(∃x₁F(x₁,x₂))→(F(x₁)→¬∃x₂G(x₁,x₂))。原题F混用二元与一元,改名为F₂、F₁。先换约束变量u、v,结果∀u∀v(F₂(u,x₂)→(F₁(x₁)→¬G(x₁,v)));自由变量仍{x₁,x₂}。

【19.13】宽域,C(x):汽车,T(x):火车,P(x):飞机,R(x,y):x比y快,S(x,y):x比y慢。

(1)有汽车比有火车快:∃x∃y(C(x)∧T(y)∧R(x,y))。

(2)有火车比所有汽车快:∃x∀y(T(x)∧(C(y)→R(x,y)))。从∃x(T(x)∧∀y(C(y)→R(x,y)))移出∀y,使用非空域。

(3)并非所有火车比所有汽车快:∃x∃y(T(x)∧C(y)∧¬R(x,y))。

(4)“有飞机比有汽车慢”不对:∀x∀y((P(x)∧C(y))→¬S(x,y))。不能凭“不是更慢”擅自改成“更快”,还可能同速。

【19.14】存在引入若允许捕获:从∀xR(x,y)直接把自由y存在化成∃x∀xR(x,x),内层∀x捕获新替换项。D={0,1}、R={(0,0),(1,0)}、σ(y)=0时前提真,结论要求R对角全真而假。正确换新名后应得∃z∀xR(x,z)。

存在消去若让见证逃出:由∃xF(x)任选旧常项a并断言F(a)不合法;D={0,1}、F={0}、a=1时前真后假。类似地,由∃xF(x)和∃xG(x)各自消去却强行使用同一见证,也会错得∃x(F(x)∧G(x))。存在消去的结论须与新参数无关。

【19.15】四个推理的证明。

(1)前提(∃xF(x))→∀y((F(y)∨G(y))→R(y))、∃xF(x),结论∃xR(x)。先假言推理得全称式;由存在前提选新见证c、假设F(c),附加得F(c)∨G(c),∀−得它蕴涵R(c),推得R(c),∃+得∃xR(x),∃−撤销见证假设。

(2)前提∀x(F(x)→(G(a)∧R(x)))、∃xF(x),结论∃x(F(x)∧R(x))。选新见证c得F(c),全称实例给G(a)∧R(c),化简取R(c),同F(c)合取后存在引入,再存在消去。G(a)虽可导出,但不在目标中。

(3)前提∀x(F(x)∨G(x))、¬∃xG(x),结论∃xF(x)。由第二前提得∀x¬G(x);取任意新参数u,全称实例得F(u)∨G(u)、¬G(u),析取三段论得F(u),存在引入即可。非空域保证可选对象。

(4)前提∀x(F(x)∨G(x))、∀x(¬G(x)∨¬R(x))、∀xR(x),结论∀xF(x)。任取u,得R(u)、¬G(u)∨¬R(u),析取三段论得¬G(u);与F(u)∨G(u)推F(u),∀+结束。u不在任何闭前提中自由出现。

【19.16】D={0,1}、F={0}、G=∅。∀F为假,故(∀F)→∀G真;∀x(F(x)→G(x))在0处假。因此二式不等值,前者只比较两个整体全称的真假,后者要求每个对象逐一保持性质。

【19.17】给定前提∀x(F(x)→¬G(x))、∀x(H(x)→G(x)),目标∀x(H(x)→¬F(x))。原“证明”临时假设∀xH(x),最后却只导出∀x¬F(x),没有撤销假设并回到目标;若撤销,只能得到(∀xH(x))→∀x¬F(x),它还不是所求公式。末步本身在临时假设是闭式的情况下可合法全称化,不能错误归因于“x在∀xH(x)中自由出现”;真正问题是附加假设过强且未正确处理目标和依赖。

【19.18】任取新参数u,临时假设H(u)。∀−得H(u)→G(u),推G(u);另一前提∀−得F(u)→¬G(u),由G(u)及拒取式得¬F(u)。撤销H(u),得H(u)→¬F(u);u不在剩余闭前提中自由出现,∀+得到目标∀x(H(x)→¬F(x))。必须先撤销局部H(u)再作最后全称化。

【19.19】前提(∃xF(x))→∀xG(x),结论∀x(F(x)→G(x))。任取u,假设F(u),∃+得∃xF(x),假言推理得∀xG(x),∀−得G(u);撤销F(u)得到F(u)→G(u),∀+结束。原题前件是∃xF(x),若误作∀xF(x),推理一般无效。

【19.20】(1)前提∀x(F(x)→G(x)),临时假设∀xF(x);任取u得到F(u)→G(u)、F(u),得G(u),∀+得∀xG(x);撤销全称假设,得到(∀xF(x))→∀xG(x)。

(2)前提∀x(F(x)∨G(x)),临时假设¬∀xF(x),等值得∃x¬F(x);以新见证c假设¬F(c),全称实例F(c)∨G(c)推出G(c),存在引入∃xG(x),存在消去撤销见证,再撤销外层假设,得到(¬∀xF(x))→∃xG(x)。

【19.21】宽域,C:乌鸦,W:白色,B:北京鸭。前提¬∃x(C(x)∧W(x))、∀x(B(x)→W(x)),目标∀x(B(x)→¬C(x))。第一项等值∀x(W(x)→¬C(x));任取u,实例化两全称并作假言三段论得B(u)→¬C(u),∀+完成。这是以给定前提为条件的形式证明。

【19.22】(1)整数域E:偶数、D:被2整除;前提∀x(E(x)→D(x))、E(6)。全称消去取6得E(6)→D(6),假言推理得D(6)。

(2)人的域S:大学生、D:勤奋,a:王晓山;前提∀x(S(x)→D(x))、¬D(a)。全称实例S(a)→D(a)与¬D(a)用拒取式得到¬S(a)。练习前提不是现实中“每个大学生都勤奋”的调查结论。

【19.23】(1)Q:有理数、R:实数、Z:整数;前提∀x(Q(x)→R(x))、∃x(Q(x)∧Z(x))。选新见证c,化简出Q(c)、Z(c),由全称实例得R(c),合取R(c)∧Z(c),存在引入,最后存在消去得∃x(R(x)∧Z(x))。

(2)域取复数,Q:有理数、I:无理数、R:实数、V:非实虚数;前提∀x(Q(x)→R(x))、∀x(I(x)→R(x))、∀x(V(x)→¬R(x))。任取u,假设V(u),得¬R(u),分别拒取得¬Q(u)、¬I(u),合取后撤销假设,再∀+得∀x(V(x)→(¬Q(x)∧¬I(x)))。“虚数”在本题取非实数意义,避免把0等实数混入。

【19.24】人的域,W:喜欢步行,B:喜欢骑车,C:喜欢乘汽车。前提∀x(W(x)→¬B(x))、∀x(B(x)∨C(x))、∃x¬C(x)。选新见证u,假设¬C(u),得B(u)∨C(u),从而B(u);由W(u)→¬B(u)及B(u)拒取得¬W(u);∃+得∃x¬W(x),∃−撤销见证。证明只需一个人不乘汽车,不能擅自假设所有人都不乘汽车。

【19.25】人的域,S:科学工作者,D:刻苦钻研,C:聪明,R:事业成功,a:王大海。前提∀x(S(x)→D(x))、∀x((D(x)∧C(x))→R(x))、S(a)∧C(a)。化简得S(a)、C(a);两次∀−分别得S(a)→D(a)、(D(a)∧C(a))→R(a);先得D(a),与C(a)合取,再假言推理得R(a)。这是给定抽象前提下的推论,不是对真实职业成功的无条件保证。