习题18

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题18 使用说明】本章14组题,按原题编号给出符号化、解释、答案及必要反例。默认个体域非空,N含0;省略括号处补足量词辖域。每道题单独声明谓词元数,不能把解释中变元的值带入量词绑定的同名字母。

【18.1】将五句话作命题层次的符号化。原书称“零元谓词”,这里使用没有个体参数的命题字母。

(1)p:小王学英语,q:小王学法语,答案p∧q。

(2)p:李健是东北人,q:李健怕冷。“除非p,否则q”写¬p→q,等价p∨q;不自动附加p→¬q。

(3)p:2>3,q:2>4,“p仅当q”写p→q,前后件不能倒置。

(4)p:3为偶数,答案¬p。

(5)p:2为素数,q:3为素数,答案p∨q,采用相容或,不附加“恰有一个”。

【18.2】(1)凡整数都能被2整除;(2)有整数能被2整除。

域Z,令E(x):2整除x,分别∀xE(x)为假,反例1;∃xE(x)为真,见证0或2。域R,令Z(x):x为整数,E(x):存在整数k使x=2k,分别∀x(Z(x)→E(x))为假、∃x(Z(x)∧E(x))为真。不要将实数x/2总存在误当成整数整除。

【18.3】令P(x)表示实数计算中的恒等式x²−2=(x+√2)(x−√2),Q(x)表示x+5=9。域N、R下,∀xP(x)均真,展开右侧即x²−2;∃xQ(x)均真,见证4。严格的一阶N语言中,√2不能作为指向域内对象的常项,通常减法也不是N上的全函数;在N情形应把整条实数等式定义成N上的一元性质P,再量化自然数x,不把√2硬解释成自然数。

【18.4】使用适当宽域:R(x):有理数,F(x):可表示为整数之比分数,B(x):游过八达岭长城,O(x):外地人,C(x):乌鸦,K(x):黑色,H(x):人,E(x):天天锻炼。

(1)没有不能表示成分数的有理数:¬∃x(R(x)∧¬F(x)),等价∀x(R(x)→F(x))。

(2)游过八达岭长城的人不全是外地人:∃x(B(x)∧¬O(x))。

(3)乌鸦都是黑色的:∀x(C(x)→K(x));这是原句的形式,不凭形式推定经验命题永真。

(4)有的人天天锻炼:∃x(H(x)∧E(x))。如果把“天天”进一步展开,可加日期域与每天锻炼的二元关系,但题中把它作为一个性质即可。

【18.5】F(x):火车,S(x):轮船,C(x):汽车,R(x,y):x比y快。

(1)火车都比轮船快:∀x∀y((F(x)∧S(y))→R(x,y))。

(2)有的火车比有的汽车快:∃x∃y(F(x)∧C(y)∧R(x,y))。

(3)不存在比所有火车都快的汽车:¬∃x(C(x)∧∀y(F(y)→R(x,y)))。

(4)“凡汽车都比火车慢”不对:¬∀x∀y((C(x)∧F(y))→R(y,x)),等价∃x∃y(C(x)∧F(y)∧¬R(y,x))。不是说每辆汽车都比每辆火车快,二者不构成穷尽的快慢反义。

【18.6】域R,写出公式并判真。

(1)∀x∃y(xy=0),真,每个x取y=0。

(2)∃x∀y(xy=0),真,固定x=0适用于所有y。

(3)∀x∃y(y=x+1),真,后继实数总存在。

(4)∀x∀y(xy=yx),真,实数乘法交换律。

(5)∀x∀y(xy=x+y),假,x=y=1时1≠2。

(6)∀x∃y(x²+y²<0),假,平方和恒非负;取任何x都不可能找到所需y。

【18.7】域Z。

(1)∀x∀y∃z(x−y=z):任意两整数之差仍为整数,真,取z=x−y。原题前两个量词均为∀。

(2)∀x∃y(xy=1):每个整数都有整数乘法逆元,假,x=0反驳,x=2也无整数解。

(3)∃x∀y∀z(x+y=z):存在同一个整数x使任意y、z满足此式,假;固定y=0,分别取z=0、1会要求x同时等于0和1。

【18.8】指出指导变元、辖域和自由/约束出现。只统计项中的出现。

(1)∀x(F(x)→G(x,y)):∀x辖域F(x)→G(x,y);x约束两次,y自由一次,自由集{y}。

(2)(∀xF(x,y))→∃yG(x,y):左∀x辖域F(x,y),右∃y辖域G(x,y);x左约束、右自由各一次,y左自由、右约束各一次,自由集{x,y}。

(3)(∀x∃y(F(x,y)∧G(y,z)))∨∃xH(x,y,z):外∀x辖域∃y(F(x,y)∧G(y,z)),内∃y辖域F(x,y)∧G(y,z),右∃x辖域H(x,y,z)。x两处都约束,但受不同量词约束;y左侧约束两次、右侧自由一次;z左、右各自由一次,自由集{y,z}。不能漏掉原题左侧的∀x∃y。

【18.9】解释D=R,a=0,f(u,v)=u−v,F(u,v):u=v,G(u,v):u<v;σ(x)=1、σ(y)=−1。

(1)∀x(G(x,y)→∃yF(x,y)),即∀x(x<−1→∃y(x=y)),真:满足前件时取内层y=x;外部自由y仍为−1。

(2)∀y(F(f(x,y),a)→∀xG(x,y)),即∀y((1−y=0)→∀x(x<y)),假:外层y=1使前件真,而内层x=1使后件假。原题这里是∀y,不能误识为∃y。

(3)(∃xG(x,y))→∀yF(f(x,y),a),即(∃x(x<−1))→∀y(1−y=0),假:前件由x=−2成立,后件由y=0反驳。原题前件是∃x,不能误识为∀x。

(4)(∀yG(f(x,y),a))→∃xF(x,y),即(∀y(1−y<0))→∃x(x=−1),真:前件假,例如y=0;后件也有见证x=−1。

【18.10】解释D=N,a=2,f加法,g乘法,F相等,σ(x)=2、σ(y)=3、σ(z)=4。

(1)∀xF(g(x,a),y)即∀x(2x=3),假,x=0反驳。

(2)(∃xF(f(x,a),y))→∃yF(f(y,a),x),即(∃x(x+2=3))→∃y(y+2=2),真,前件见证1,后件见证0;右侧自由x保留赋值2。N含0这一约定对后件重要。

(3)∀x∀y∃zF(f(x,y),z)即∀x∀y∃z(x+y=z),真,取z=x+y。

(4)∃xF(f(x,y),g(x,z))即∃x(x+3=4x),真,见证1。

【18.11】判断公式类型。

(1)F(x,y)→(G(x,y)→F(x,y)):永真,是p→(q→p)实例。

(2)(∀x(F(x)→F(x)))→∃y(G(y)∧¬G(y)):矛盾式,前件永真、后件永假。

(3)(∀x∃yF(x,y))→∃x∀yF(x,y):可满足但不永真。反例D={0,1}、F为相等关系:每个x有相等的y,但没有一个x等于两个不同y;成真模型可取同域F=D²。原题是∀x∃y,不是“∀yF(x,y)”;漏掉量词会把错误的推理判断为有效。

(4)(∃x∀yF(x,y))→∀y∃xF(x,y):永真,前件提供的同一x可以作为每个y的见证;它与(3)不同。

(5)∀x∀y(F(x,y)→F(y,x)):可满足但不永真;空关系成真,D={0,1}且F={(0,1)}成假。

(6)¬((∀xF(x))→∃yG(y))∧∃yG(y):矛盾式,形如¬(p→q)∧q。

【18.12】(1)F(x)→∀xF(x),可满足但不永真;D={0,1}、F={0}、σ(x)=0时假,F=D时真。

(2)(∃xF(x))→F(x),可满足但不永真;同域F={0}、σ(x)=1时假,F=D时真。

(3)(∀x(F(x)→G(x)))→((∀xF(x))→∀xG(x)),永真:前两项真时,对任意d有F(d)且F(d)→G(d),因而G(d)。

(4)((∀xF(x))→∀xG(x))→∀x(F(x)→G(x)),可满足但不永真。D={0,1},F={0}、G=∅时,∀F假、∀G假,前件蕴涵真,而右侧在0处假;F=G=D给出真模型。

【18.13】逐式给成真、成假解释:(1)∀x(F(x)∨G(x));(2)∃x(F(x)∧G(x)∧H(x));(3)∃x(F(x)∧∀y(G(y)∧H(x,y)))。分别在单元素域D={0}上,令所有出现的一元谓词解释为D、二元谓词解释为D²,三式都真;令这些关系全为空,三式都假。(2)的最外层是∃,不是∀;(3)的H二元而(2)的H一元,是不同题目的独立语言。

【18.14】证明两式既非永真也非矛盾:(1)∀x(F(x)→∃y(G(y)∧H(x,y)));(2)∀x∀y((F(x)∧G(y))→H(x,y))。两式均在D={0}、F=G={0}、H={(0,0)}时真;同域F=G={0}、H=∅时均假。第一式找不到y见证,第二式在x=y=0前真后假;给出这两类解释即可完成证明。