谓词逻辑习题及答案

第二章谓词逻辑题二一．将下列命题符号化。(一)某些实数是有理数。(二)每一个有理数都是实数。(三)不是每一个实数都是有理数。(四)并非所有素数都不是偶数。(五)没有不犯错误。(六)所有都会犯错误。(七)火车比轮船快。(八)有些液体能溶解任何金属。(九)金子都会闪光,但闪光未必是金子。(一零)存在一些是大学生。解答:设H(x)x是实数P(x):x是有理数。则命题可符号化为:(H(x)P())。(二)设H(x):x是有理数P(x):x是实数。则命题可符号化为:x)(H(x)P(x))。x)(H(x)P(x))。x)(H(x)P(x))。(H(x)P(x))。(三)设H(x):x是实数Px):x是有理数。则命题可符号化为:(四)设H(x):x是素数Px):x是偶数。则命题可符号化为:(五)设H(x):x是P(x:x会犯错误。则命题可符号化为:(六)设H(x):x是P(x:x会犯错误。则命题可符号化为:x)(H(x)P(x))。(七)设H(x):x是火车L(x):x是轮船;P(x,y):x比y快。则命题可符号化为:L()P(x,y))。x)y)(H(x)(八)设H(x):x是液体;(x):x是金属;P(x,y):x能溶解y。则命题可符号化为:(L()P(x,y)))。(x)(H(x)y)(九)设H(x):x是金子;P(x):x会闪光。则命题可符号化为:P(x)(H()P(x))。x)(H(x)(x)(一零)设H(x)x是P(x):x是大学生。则命题可符号化为:(H(x)P(x))。二．将下列命题译成自然语言。假定个体域D是正整数集合。(一)xy)P(,y),其,P(,y):yy。(二)xyG(,y),其,G(x,y):yx。(三)x)(N(二,x)E(x。(四)x)(E(x)y)(N(,y)E(y。其,N(,y):x可以整除yE(x):x是偶数。解答:对于任意正整数x都存在正整数y,(二)对于任意正整数x都存在正整数y使得yyyx(三)对于任意正整数x,若二可以整除x,则x是偶数。(四)对于任意正偶数x,若x可以整除y,则y是偶数。三．写出以下命题否定形式:(一)存在一些是大学生。(二)所有地都是要死地。解答:所有都不是大学生。(二)有些不会死。四．指出下列各式自由变元,约束变元以与量词辖域。(一)x)(F(x)(y)H(,y(二)x)(F(x)(x(R(y)S()二六离散数学解答:全称量词(x)地辖域为F(x)(H(,y),而存在量词()辖域为H(,,)因此x与y都是约束变元。(二)全称量词(x)地辖域为F(x)Q(x)而存在量词()辖域为R(y)有最后S(x)地x是自由变元,其余都是约束变元。五．将下面谓词公式量词消除,其个体域都是A={,b,c。(一)x)(P(x)G(x(二)x)P(x)(xG(x)(三)xy)P(,y)解答:x)(P(x)G(x(P(a)G(a(P)G(()G((二)x)P(x)(xG(x)(P(a)P)P(cG(a)G)G(c(三)xy)P(,y)x)(P(,a)(,)(,c(P(a,a)P(,)P(,c(P,a)P,)P,c(P(,a)P(,)P(,c六．设解释I如下:D={a,b;P(aa)=一;P(,b)=一P(a,b;P(ba)=零试确定下列公式在I下真值。(一)xy)P(,y)(二)yx)P(,y)(三)xy)P(,y)(四)xy)(P(,y)P(y,x解答:xy)P(,y)(P(,a)P(,(,a)P,(零一。(二)yx)P(,y)(P(,a)P,a(P(,)P,(零零。(三)xy)P(,y)((,a)(,(,a),零。(四)xy)(P(,y)P(y,xx)((P(,a)P(,x(P(,),x(P(,a)P(,a((,),a(,a)(,(,),一。七．判断下列谓词公式哪些是有效式?哪些是矛盾式??(一)(x)P(x)x)P(x)(二)(P(x)xQ(,y)P(x(三)x)P(x)x)P(x)R(y(一)当x)P(x)为真时,(x)P()为真当x)P()假时,(x)(x能为真也可能为假因此原公式是可满足式。(二)当P(x)为真时,xQ(,y)P(x),而P(x)xQ(,y)P(x为真,即原公式为假当P(x)为假时,P(x)xQ(,y)P(x必为真即原公式为假。因此原公式为矛盾式。(三)当x)P(x)为真时,x)P(x)R(y)必为真,因此不可能出现零地情况。原公式为有效式。八．用等值演算证明下列等式关系。(一)(x)(F(x)G(xx)F(x)(yG(y)(二)(xy)(F(x)(yx)F(x)(y(y)证明:(x)(F(x)G(x(xF(x)G(x(x)F(x)(G()x)F(x)(xG(x)x)F(x)(xG(x)x)F(x)(yG(y)。(二)(xy)(F(x)Q(y(xyF(x)(y(xF(x)(y(y(x)F(x)(yQ(y)x)F(x)(yQ(y)x)F(x)(yQ(y)。二七第二章谓词逻辑九．求下述公式地前束范式与Skolem范式。(一)x)P(x)(xQ(x)(二)x)(P(x)(xx)P(x)(x((三)x)(P(x)(y(,yz)R(z)解答:x)P(x)(xQ(x)x)P(x)(x(x)(x)()(()(xP(x)Q(x(前束范式)(二)x)(P(x)Q(xx)P(x)(x(xx)(P(x)Q(x))(x)P(x)(x)Q(x)(x)(P(x)Q(x))(x)P(x)(x)Q(x)(x)(P(x)Q(x))(y)P(y)(z)Q(z)xyz)(P(x)Q(x)P(y)(z(前束范式)(三)x)(P(x)(yQ(,yz)R(z)x)(P(x)(y)Q(x,y))(z)R(z)x)((y)(P(x)Q(x,y))(z)R(z))x)(y)(P(x)Q(x,y)(z)R(z))xyzP(x)(,y)R(z(前束范式)一零．判断以下逻辑推理关系是否成立,并说明理由。(一)x)P(,x)xy)P(,y)(二)(x)F(x)(xQ(x)(x)(F(x)Q(x(三)(x)F(x)xQ(x)(x)(F(x)Q(x解答:成立。若(x)P(,x)为真,则存在x使得P(x,x)为真,从而xy)P(,y)为零零零真,即不可能出现零地情况。因此,(x)P(,x)(xy)P(,y)为永真公式,原推理成立。(二)(x)F(x)(x(x)为真x,x使得F(x,Q(x)为真但未必零一零一存在x使得F(x)Q(x)为真。因此(x)F(x)(xQ(x)(x)(F(x)(x不一定为永真公式,原推理不成立。(三)不成立。若(x)F(x)x(x)为真可能出现(x)F(x)为假但xQ(x)为真地情况即不存在x使得F(x)为真而所有x都使得Q(x),F(x)Q()零零为假,从而(x)(F(x)Q(x为假。因此(x)F(x)xQ(x)(x)(F(x)(x不一定为永真公式原推理不成立。．构造下面推理地(一)前提:(x)F(x),x)(F(x)G(x)H(x结论:(x)H(x)(二)前提:(x)F(x)xG(x)结论:(x)(F(x)G(x(三)前提:(x(x),xy)(S(,y)P(y(yQ(y)R(,y结论:xy)(S(,y)P(y证明:证明过程如下:一)(x)F(x)P二)F(c)ES,一)二),IP三)Fc)Gc)四)x)(F(x)G(x)H(x五)F(c)G(c)Hc)六)H(c)US,四)三),五),I二八离散数学七)(x)H(x)(二)证明过程如下:六)一)(x)F(x)xG(x)P二)(x)F(x)三)xG(x)四)F(c)五)G(c)六)Fc)Gc)七)(x)(F(x)G(x一),I一),IES,二)US,三)四),五),I六)(三)证明过程如下:一)(x(x)二)xQ(x)P一),EUS,二)三),I六)五),EP三)Q(y)四)Q(y)R(,y)五)y(y)R(,y六)y(y)R(,y七)xy)(S(,y)P(y(yQ(y)R(,y八)(y)(S(,y)P(y(y(y)R(,y九)y)(S(,y)P(y七)六),八),I一零)yS(,y)P(y九),Ey)(S(,y)P(y一二)xy)(S(,y)P(y一零),E一二每个旅客当且仅当它富裕时坐头等舱有些旅客富裕但并非所有地集合）证明:设P(x):x坐头等舱Q(x:x坐经济舱R(x:x富裕。则原推理可符号化为x)(P(x)Q(xx)(P(x)R(x()(()()()()。证明如下:一)(x)R(x)二)R(c)三)x)(P(x)R(x四)Pc)Rc)五)P(c)六)x)(P(x)Q(x七)P(c)Q(c)八)Q(c)PES,一)PUS,三)二),四),IPUS,六)五),七),I八)九)(xQ(x)一三地教师任;,论断正确。证明:设H(x)x是学生K(x)x是教师L(xx是骗子P(x,y:x。则原推理可符号化为(x)(H(x)y)(K(y)P(,yy)(H()(y)(,y()(K()(证明如下:一)(x)(H(x)y)(K(y)P(,y二)Hc)y)(K(y)P,y三)H(c)PES,一)二),I二九第二章谓词逻辑四)y)(K(y)P,y五)K(x)P,x)二),