离散数学答案解析(尹宝林版)第二章知识题解答 VIP专享VIP免费

**第二章谓词逻辑习题与解答1.将下列命题符号化：(1)所有的火车都比某些汽车快。(2)任何金属都可以溶解在某种液体中。(3)至少有一种金属可以溶解在所有液体中。(4)每个人都有自己喜欢的职业。(5)有些职业是所有的人都喜欢的。解(1)取论域为所有交通工具的集合。令T(x):x是火车，C(x):x是汽车，F(x,y):x比y跑得快。“所有的火车都比某些汽车快”可以符号化为x(T(x)y(C(y)F(x,y)))。(2)取论域为所有物质的集合。令M(x):x是金属，L(x):x是液体，D(x,y):x可以溶解在y中。“任何金属都可以溶解在某种液体中”可以符号化为x(M(x)y(L(y)D(x,y)))。(3)论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中”可以符号化为x(M(x)y(L(y)D(x,y)))。(4)取论域为所有事物的集合。令M(x):x是人，J(x):x是职业，L(x,y):x喜欢y。“每个人都有自己喜欢的职业”可以符号化为x(M(x)y(J(y)L(x,y)))(5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为**x(J(x)y(M(y)L(y,x)))。**x))3.取论域为实数集合，用函数，－(减法)和谓词将下列命题符号化：(1)没有既是奇数，又是偶数的正整数。(2)任何两个正整数都有最小公倍数。(3)没有最大的素数。(4)并非所有的素数都不是偶数。解先引进一些谓词如下：(1)“没有既是奇数，又是偶数的正整数”可表示为x(J(x)E(x))，并可进一步符号化为x(v(v?2x)v(v?2x))。(2)“任何两个正整数都有最小公倍数”可表示为xyz(D(z,x)D(z,y)u(D(u,x)D(u,y)并可进一步符号化为并可进一步符号化为x((x1)y((y1)u(v(v?uu(v(v?uy)x)uu1u1ux)y)yxy(4)“并非所有的素数都不是偶数”可表示为x(P(x)E(x))，并可进一步符号化为x((x1)u(v(v?ux)u1ux)v(v?2x))2.取论域为正整数集，用函数加法)，乘法)和谓词，将下列命题符号化：J(x):x是奇数，J(x)可表示为v(v?2E(x)x是偶数，E(x)可表示为v(v?2P(x)x是素数，P(x)可表示为(x1)v(v?yx)。x)。x)。u(v(v?ux)u1ux)。uzu))，xyz(v(v?xz)v(v?yz)u(v(v?xu)v(v?yu)zuzu))(3)“没有最大的素数”可表示为x(P(x)y(P(y)yxyx))D(x,y):x能被y整除，D(x,y)可表示为**(1)没有最大的实数。(2)任何两个不同的实数之间必有另一实数。(3)函数f(x)在点a处连续。(4)函数f(x)恰有一个根。(5)函数f(x)是严格单调递增函数。解(1)“没有最大的实数”符号化为xy(yxyx)。(2)“任何两个不同的实数之间必有另一实数”符号化为xy(xyz(xzzy))。(3)“函数f(x)在点a处连续”的定义是：任给0，总可以找到0，使得只要|xa|就有|f(x)f(a)|。“函数f(x)在点a处连续”符号化为(0(0x(axxaf(a)f(x)f(x)f(a))))(4)“函数f(x)恰有一个根”符号化为x(f(x)0y(f(y)0yx))。(5)“函数f(x)是严格单调递增函数”符号化为xy(xyf(x)f(y))。4.指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。(1)x(P(y,x)P(x,a))(2)xP(x)zQ(x,y)(3)x(P(x)R(x))xP(x)Q(x)(4)y(P(f(x,y),x)xP(z,g(x,y)))(5)x(P(x)Q(x)xR(x))R(x)解(1)变元x在x(P(y,x)P(x,a))中三次出现都是约束出现，x的唯一出现的辖**域是P(y,x)P(x,a)。(2)变兀x在xP(x)zQ(x,y)中的头两次出现是约束出现，第三次出现是自由出现。变兀y在xP(x)zQ(x,y)中的唯一出现是自由出现。变兀z在xP(x)zQ(x,y)中的唯一出现是约束出现。x的唯一出现的辖域是P(x)，z的唯一出现的辖域是Q(x,y)。(3)变兀x在x(P(x)R(x))xP(x)Q(x)中的头五次出现是约束出现，第六次出现是自由出现。x的第一次出现的辖域是P(x)R(x)，第二次出现的辖域是P(x)。(4)变兀x在y(P(f(x,y),x)xP(z,g(x,y)))中的头两次出现是自由出现，后两次出现是约束出现。x的唯一出现的辖域是P(z,g(x,y))，y的唯一出现的辖域是P(f(x,y),x)xP(z,g(x,y))。(5)变兀x在x(P(x)Q(x)xR(x))R(x)中的头五次出现是约束出现，第六次出现是自由出现。x的唯一出现的辖域是P(x)Q(x)xR(x)，x的唯一出现的辖域是R(x)。5.归纳证明：若t,t是项，则ttX也是项。证明①若t是X，则T是t,&x是项。②若t是不同于x的变兀y，则(仍是y,华是项。③若t是常兀a，则tf仍是a,tfX是项。④若t是f(t1,,tn)，则ttx是f©)：,,(tnf)，由归纳假设知(ti)tx,,舍)：都是项，所以tf是项。6.归纳证明：若t是项，A是公式，...